Global or Relativised Dependent Choices

Question

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.

Answer 1

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

Answer 2

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.