Questions about generalizations of the Principle of Dependent Choices

Question

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.

Answer 1

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)$.

Answer 2

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