Global or Relativised Dependent Choices - MathOverflow

Global or Relativised Dependent Choices

2010-10-17T20:35:47Z

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 by Andres Caicedo for Global or Relativised Dependent Choices

2010-10-17T21:08:03Z

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 by Joel David Hamkins for Global or Relativised Dependent Choices

2010-10-17T23:59:04Z

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.