3
$\begingroup$

I am talking about the principle that is to DC what the global choice is to the usual axiom of choice. Global choice involves existential quantification over classes, but global DC can be stated as a schema in first-order set theory.

$(\forall x (\phi(x) \to \exists y (\phi(y) \wedge \psi(x,y)))) \to \forall x (\phi(x) \to \exists f (f(0)=x \wedge \forall n \in \omega (\phi(f(n)) \wedge \psi(f(n),f(n+1)))))$

Searching for this I come up with nothing, other than in constructive set theory, where it is called "relativised" DC, and has a simple computational interpretation. I guess that classically, it just follows from ZF+DC. Is that right? I can't figure out how.

$\endgroup$

2 Answers 2

3
$\begingroup$

Given any $x$, let $\alpha_x$ be 0 if $\phi(x)$ fails. If it holds, for each $x'$ with $\phi(x')$ and $x'$ of set-theoretic rank less than or equal to $x$, let $\alpha^{x'}$ be the least ordinal $\alpha$ such that there is a $y$ of rank $\alpha$ with $\phi(y)\land\psi(x',y)$. Now set $\alpha_x$ as the supremum of the $\alpha^{x'}$.

Then $\alpha_x$ is an upper bound for the rank of a `witness' $y$ when $\phi(x)$ holds. By replacement, there is a sequence $(g(n)\mid n<\omega)$ with $g(0)$ the rank of $x$, $g(1)$ an upper bound for the rank of a $y$ with $\phi(y)\land\psi(x,y)$, $g(2)$ an upper bound for the rank of a $z$ such that there is a $y$ with $\phi(y)\land\psi(x,y)\land\phi(z)\land\psi(y,z)$, etc.

Taking $\beta$ as the supremum of the $g(n)$, we see that $\beta$ is such that if we restrict $\phi$, $\psi$ to sets of rank at most $\beta$, then DC ensures that there is an $f$ as wanted, starting with $f(0)=x$.

[By the way, this is a standard approach, you replace your problem with one about ranks, and things become easier.]

$\endgroup$
1
  • $\begingroup$ Scott's trick. I should have figured it out. $\endgroup$ Oct 17, 2010 at 21:13
2
$\begingroup$

Another economical way to think about it is to use the Reflection theorem (although unwinding this amounts just to Andres' argument). Namely, by the Reflection Theorem there is an ordinal $\theta$ such that the formulas $\phi(x)$, $\psi(x,y)$ and $\exists y\,\psi(x,y)$ are absolute between $V_\theta$ and $V$. By the Separation axiom, the restriction of the relation $\psi$ to $V_\theta$ is now a set for which the ordinary DC principle provides the desired chain.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.