Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.]

share|improve this answer
    
Scott's trick. I should have figured it out. –  Daniel Mehkeri Oct 17 '10 at 21:13

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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