Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've encountered two different generalizations of the Principle of Dependent Choices (DC) to initial ordinals $\kappa>\omega$. First, some notation. By $A\prec B$, I indicate that $A$ is injectable into, but not bijectable with, $B$. Given a function $f$ on a set $A$ and a subset $B$ of $A$, I denote the restriction of $f$ to $B$ by $f\restriction B$. Given an ordinal $\alpha$ and a set $X$, I denote the set of functions $\beta\to X$ where $\beta<\alpha$ by $X^{<\alpha}$.

Now, the generalizations are as follows:

$\text{DC}_\kappa(1)$: If $X$ is a non-empty set and $R\subseteq\mathcal{P}(X)\times X$ is a relation such that $$\text{dom}(R)\supseteq\{Y\in\mathcal{P}(X):Y\prec\kappa\},$$ then there exists some $f:\kappa\to X$ such that $$\text{ran}(f\restriction\alpha)\:R\:f(\alpha)$$ for all $\alpha<\kappa$.

$\text{DC}_\kappa(2)$: If $X$ is a non-empty set and $R\subseteq X^{<\kappa}\times X$ is a relation such that $$\text{dom}(R)=X^{<\kappa},$$ then there exists some $f:\kappa\to X$ such that $$(f\restriction\alpha)\:R\:f(\alpha)$$ for all $\alpha<\kappa$.

I can see that $\text{DC}_\omega(1)$ and $\text{DC}_\omega(2)$ are equivalent to DC.

I've been trying to show that $\text{DC}_\kappa(1)$ and $\text{DC}_\kappa(2)$ are equivalent. Showing that $\text{DC}_\kappa(2)$ implies $\text{DC}_\kappa(1)$ is fairly straightforward, but I have thus far been stymied on proving the other direction. The approach I've been trying to take is to suppose some relation $R$ satisfies the hypotheses of $\text{DC}_\kappa(2)$, constructed a related relation $S$ satisfying the hypotheses of $\text{DC}_\kappa(1)$, yielding a function $f$ satisfying the conclusion of the $\text{DC}_\kappa(1)$, and from that trying to show that $f$ satisfies the conclusions of $\text{DC}_\kappa(2)$, or using $f$ somehow to construct another function $g$ that does.

Can anyone give me any hints as to how I might accomplish this task?

Edit: Let me show you one of my abortive attempts to prove the trickier direction, to make it easier to advise me on this.

Suppose $\text{DC}_\kappa(1)$ holds for some initial ordinal $\kappa>\omega$, and suppose $R$ satisfies the hypotheses of $\text{DC}_\kappa(2)$.

Given $Y\subseteq X$, define $I(Y,\kappa)$ to be the set of all injections $Y\to\kappa$ if $Y\prec\kappa$, and otherwise define $I(Y,\kappa):=\emptyset$. Given $h\in I(Y,\kappa)$, and well-ordering $Y$ by proxy using $h$, there is a unique ordinal $\alpha_h$ isomorphic to $Y$ in this well-ordering, and a unique isomorphism. In this way, $h\in I(Y,\kappa)$ uniquely determines an ordinal $\alpha_h<\kappa$ and a bijection $F_h:\alpha_h\to Y$.

Now, given any $\alpha<\kappa$ and any $h:\alpha\to X$, the map $\text{ran}(h)\to\alpha$ given by $x\mapsto\min h^{-1}(x)$ lets us well-order $\text{ran}(h)$ by proxy, uniquely determining an ordinal $\beta_h<\kappa$ and an isomorphism $G_h:\text{ran}(h)\to\beta_h.$ Each $G_h$ is then an injection from a subset of $X$ into (but not onto) $\kappa$.

Define $S\subseteq\mathcal{P}(X)\times X$ by $Y\:S\:y$ iff there is some $\alpha<\kappa$ and some $h:\alpha\to X$ such that $Y=\text{dom}(G_h)$ and $h\:R\:y$.

Take any $Y\subseteq X$ with $Y\prec\kappa$ and any $h\in I(Y,\kappa)$. Then $F_h\in X^{<\kappa}$, so by assumption there is some $y\in X$ such that $F_h\:R\:y$. Moreover, $Y=\text{dom}(G_{F_h})$, so by definition, $Y\:S\:y$. Thus, by $\text{DC}_\kappa(1),$ there is some $f:\kappa\to X$ such that $\text{ran}(f\restriction\alpha)\:S\:f(\alpha)$ for all $\alpha<\kappa$.

Sticking Point: I don't believe we can conclude that $(f\restriction\alpha)\:R\:f(\alpha)$ for all $\alpha<\kappa$, but I'd like to be able to use $f$ to construct a function $\hat f:\kappa\to X$ such that $(\hat f\restriction\alpha)\:R\:\hat f(\alpha)$ for all $\alpha<\kappa$. I'm not sure how I might do this, though.

share|cite|improve this question
You can, and maybe should, write $^{<\kappa}X$ or $X^{<\kappa}$ instead of the horrid union. It's common, simpler and nicer on the eyes. :-) – Asaf Karagila Dec 4 '12 at 18:39
I should also note that you are missing some conditions in both the formulations of $\mathrm{DC}$ you have given here. You need to add that for every $Y$ there is some $x$ such that $\langle Y,x\rangle\in R$. (Or for every $f\colon\alpha\to X$...) – Asaf Karagila Dec 4 '12 at 18:51
I think the bits about $\text{dom}(R)$ are equivalent to those conditions, aren't they? – Cameron Buie Dec 4 '12 at 19:28
Hmmm. Maybe, I think that you are right. By requiring the sets/functions to be in the domain we actually say that there is someone standing with them in the relation. You will have to require $X$ non-empty in the first formulation anyway. – Asaf Karagila Dec 4 '12 at 19:31
Ah! You're right. I'll fix that. – Cameron Buie Dec 4 '12 at 20:05
up vote 3 down vote accepted

Well, note that $Y\prec\kappa$ if and only if there is some injection $f\colon\alpha\to X$ such that $\alpha<\kappa$ and $\operatorname{rng}(f)=Y$.

Also note that $\mathrm{DC}_\kappa$, in the way that I know should be stated as (I'm giving the second formulation, but you can deduce what is missing for the first as well):

For every non-empty set $X$ and a binary relation $R$ such that for every $\alpha<\kappa$ and every $f\colon\alpha\to\kappa$ there is some $x\in X$ such that $f\mathrel{R}x$. Then there exists $f\colon\kappa\to X$ such that for all $\alpha<\kappa$, $$f\upharpoonright\alpha\mathrel{R} f(\alpha).$$

Of course you can always assume that $R\subseteq X^{<\kappa}\times X$, and you can even assume that all the functions are injective to begin with (although that makes it much harder to prove that $\mathrm{DC_\kappa\implies DC_\lambda}$ for $\lambda<\kappa$.

Now it should be much clearer how the equivalence goes. Simply exchange $f\mathrel{R_2}x$ by $\operatorname{rng}(f)\mathrel{R_1} x$; and $Y\mathrel{R_1} x$ by adding all enumerations of $Y$ as $f\colon\alpha\to X$ for some $\alpha<\kappa$.

Edit: Proposed solution:

Let $S\subseteq [R]^{<\kappa}\times R$ be defined as: $$\langle Y,\langle f,x\rangle\rangle\in S\iff \begin{cases} &\exists\langle g,y\rangle\in Y\forall\langle g',y'\rangle\in Y: g\subseteq g'\leftrightarrow g'=g\land\exists\beta\notin\operatorname{dom}(g): f=g\cup\{\langle\beta,y\rangle\} &\text{or}\\ &Y=\varnothing\land\operatorname{dom} f=0&\text{or}\\ &\operatorname{dom}(f)=\delta\in\mathrm{Lim}\exists\{\alpha_i\mid <\operatorname{cf}(\delta)\}\sup\alpha_i=\delta\exists\langle f_i,x_i\rangle\in Y: f_i=f\upharpoonright\alpha_i\land f(\alpha_i)=x_i \end{cases} $$

Namely the set $Y$ is in relation with the pair $\langle f,x\rangle$ if and only if either $Y$ is empty and $f$ is empty, or there is someone in $Y$ which is not extended within $Y$, and $f$ extends it in a coherent way, or if there is an unbounded coherent sequence which $f$ extends properly.

Now every set of size $<\kappa$ is in the domain of the relation. If it is empty then of course; if it is a chain then of course; and if it is not a chain then either it contains a coherent chain, or it contains a function which is terminal and then you can extend it as you'd like.

By $\mathrm{DC}_\kappa(1)$ there is $F\colon\kappa\to R$ such that $\operatorname{rng}(F\upharpoonright\alpha)\mathrel{S}F(\alpha)$.

Denote $Y_\alpha=\operatorname{rng}(F\upharpoonright\alpha)$ and $F(\alpha)=\langle f_\alpha,x_\alpha\rangle$. We will show by induction that this must generate a coherent sequence.

Suppose that for all $\beta<\alpha$ we have that up to $\beta$ the set $Y_\beta$ is an increasing chain and $\operatorname{dom}(f_\beta)=\beta$ (note it holds immediately for zero, so we're off with a nice start).

We know that $Y_\alpha\mathrel{S}\langle f_\alpha,x_\alpha\rangle$. If $\alpha$ is a limit then $Y_\alpha$ must contain a coherent chain which is unbounded below $\alpha$, it has to be a coherent sequence to begin with, otherwise there would be some $\beta<\alpha$ in which there is a splitting point, which is contradictory to the induction hypothesis.

If $\alpha=\beta+1$ then by the assumption $Y_\beta$ is a coherent sequence, and it has a maximal element. Note that the only $\langle g,y\rangle\in Y_\beta$ for which $g$ is not a subset of any other function is $\langle f_\beta,x_\beta\rangle$. Then by the definition of $S$ we have that $f_\alpha$ extends $f_\beta$ by $x_\beta$.

Now the function $f\colon\kappa\to X$ for which $f(\alpha)=x_\alpha$ works just fine for $\mathrm{DC}_\kappa(2)$.

share|cite|improve this answer
I did notice that. The trouble was in appropriately defining the relation $S$ so that I could use that fact. I'll add what I've tried so far to the post. – Cameron Buie Dec 4 '12 at 18:50
Cameron, did my added part help? – Asaf Karagila Dec 4 '12 at 19:34
I'll play with it and see if I can get anywhere. Thanks, Asaf. – Cameron Buie Dec 4 '12 at 20:06
@Cameron: I see where the problem is (I am trying to write the complete proof of what you did, unfortunately I have to go out in a few minutes. I will continue to think about it and I will post additional information later). I am not deleting this answer so other people could see what is written here and perhaps build on that. – Asaf Karagila Dec 4 '12 at 20:40
I'm not familiar with the notation $[R]^{<\kappa}$, but it does look promising. – Cameron Buie Dec 4 '12 at 21:42

Here is a different approach using the fact that $X^{<\kappa} \subseteq \mathcal{P}(\kappa\times X)$. This is a bit simpler than Asaf's but a little too slick since it makes the inductive magic less obvious.

Suppose that $R \subseteq X^{<\kappa}\times X$ has domain $X^{<\kappa}$. Pick some $x_0 \in X$ and define $S \subseteq \mathcal{P}(\kappa\times X)\times (\kappa\times X)$ by two cases:

  • If $t \in X^{<\kappa}$, then $t \mathrel{S} (\alpha,x)$ iff $\mathrm{dom}(t) = \alpha$ and $t \mathrel{R} x$.

  • If $t \in \mathcal{P}(\kappa\times X) - X^{<\kappa}$, then $t \mathrel{S} (\alpha,x)$ iff $\alpha = 0$ and $x = x_0$.

The second clause is arbitrary but it ensures that the domain of $S$ is all of $\mathcal{P}(\kappa \times X)$.

Now suppose $F:\kappa\to\kappa\times X$ satisfies $\mathrm{ran}(F \upharpoonright \alpha) \mathrel{S} F(\alpha)$ for all $\alpha < \kappa$. By induction, we see that $f = \mathrm{ran}(F)$ is a function $\kappa\to X$ such that $(f\upharpoonright\alpha) \mathrel{R} f(\alpha)$ for every $\alpha < \kappa$.

share|cite|improve this answer
I worked really hard on my solution! And now you come with all that razzmatazz and do it in six lines! Unfair! :-) – Asaf Karagila Dec 5 '12 at 20:01

Your Answer


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.