Global or Relativised Dependent Choices - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T04:53:34Z http://mathoverflow.net/feeds/question/42538 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42538/global-or-relativised-dependent-choices Global or Relativised Dependent Choices Daniel Mehkeri 2010-10-17T20:35:47Z 2010-10-17T23:59:04Z <p>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. </p> <p>$(\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)))))$</p> <p>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.</p> http://mathoverflow.net/questions/42538/global-or-relativised-dependent-choices/42542#42542 Answer by Andres Caicedo for Global or Relativised Dependent Choices Andres Caicedo 2010-10-17T21:08:03Z 2010-10-17T21:08:03Z <p>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'}$. </p> <p>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&lt;\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. </p> <p>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$.</p> <p>[By the way, this is a standard approach, you replace your problem with one about ranks, and things become easier.]</p> http://mathoverflow.net/questions/42538/global-or-relativised-dependent-choices/42560#42560 Answer by Joel David Hamkins for Global or Relativised Dependent Choices Joel David Hamkins 2010-10-17T23:59:04Z 2010-10-17T23:59:04Z <p>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.</p>