# Question about trees and generalizing the Principle of Dependent Choices.

One form of the Principle of Dependent Choices is that for any tree $T$ of height $\omega$ such that every node of $T$ has a successor, there is a branch of $T$ of length $\omega$. In this post, I give two different (but equivalent) characterizations for a generalization of the Principle of Dependent Choices. Does anyone know of any characterization of this generalization that is in the form of a theorem about trees?

-

The one you called $\text{DC}_\kappa(2)$ seems to be equivalent to the statement "every tree of height $\le \kappa$ such that every branch of length $<\kappa$ can be continued has a branch of length $\kappa$."

This is also equivalent to the statement that every tree of height $\le \kappa$ has a maximal branch.

If every tree of height $\le \kappa$ has a maximal branch, and $T$ is a tree of height $\le \kappa$ such that every branch of length $<\kappa$ can be continued, then take a maximal branch. It can't have length $<\kappa$, so it must have length $\kappa$.

Conversely, if every tree of height $\le \kappa$ such that every branch of length $<\kappa$ can be continued has a branch of length $\kappa$, and $T$ is a tree of height $\le \kappa$, either it has a branch of length $<\kappa$ that can't be continued, or it has a branch of length $\kappa$. In either case, the branch is maximal.

By "tree of height $\le \kappa$" I mean a poset (with a least element, but this doesn't matter here) such that the set of predecessors of any given element is a well-ordering of length $<\kappa$. By "branch" I mean a well-ordered (equivalently, linearly ordered) subset that is downward closed. By "maximal" I mean "maximal under inclusion." By "can be continued" I mean "is not maximal."

-
By maximal, what do you mean? The definition of branch I'm using is a maximal (with respect to set inclusion) linearly ordered subset. –  Cameron Buie Dec 5 '12 at 2:29
I was thinking of trees of height $\le \kappa$ as subsets of $X^{<\kappa}$, closed under initial segments, for some set $X$. Then "maximal" means maximal with respect to inclusion. –  Trevor Wilson Dec 5 '12 at 2:32
Oops! The $\gamma$ was supposed to be an $\alpha$. Not sure how that happened. Also, we need $\beta<\alpha$, rather than $0<\beta<\alpha$, for it to be a tree in the sense you gave. By "branch of length $\alpha$", I mean that there's a maximal $\subseteq$-ordered subset of the tree of order type $\alpha$. In retrospect, you're right--it only refutes Brian's suggested correction, not Zorn's Lemma. :P –  Cameron Buie Dec 5 '12 at 3:19
@Cameron: You may be interested to know that $\mathbf{DC}_\kappa$ is equivalent to the assertion that every poset in which every chain of length $<\kappa$ has an upper bound has a maximal element. Namely, it is exactly as powerful as Zorn's lemma for posets of height $\leq\kappa$ (and maybe other non-well ordered, or much longer, chains as well). For details see Wolk, 1983 (there is just one paper on MathSciNet by Wolk from 1983). –  Asaf Karagila Dec 5 '12 at 7:07
I see it now. Thanks! (For some reason, I was convinced that your statement was equivalent to the strictly weaker Axiom of $\kappa$-Choice.) –  Cameron Buie Dec 5 '12 at 14:06

$\mathbf{DC}_\kappa(3)$. Every tree of height $\kappa$ in which every increasing sequence of $<\kappa$ points has an upper bound not in the sequence has a branch of length $\kappa$.

Note that this assumption implies that every point has a successor.

The assumption $\mathbf{DC}_\kappa(2)$ is implied this version. To see this, consider the $X$ and $R$ as in the requirement of $\mathbf{DC}_\kappa(2)$ and define the following subtree of $X^{<\kappa}$, $$f<_T g\iff \exists\beta<\kappa:g\upharpoonright\beta=f\land f\mathrel{R}g(\beta)$$

This is a tree of height $\kappa$, and if $\langle f_\gamma\mid\gamma<\lambda\rangle$ for some $\lambda<\kappa$ is an increasing sequence in $T$ then $f=\bigcup f_\gamma$ is an upper bound of the sequence, take any $x$ such that $f\mathrel{R} x$ and extend $f$ by one point with $x$, then this extension is an upper bound which is not in the sequence. Therefore there is a branch of length $\kappa$ in the tree. It is easy to see that the branch defines the function from $\kappa$ into $X$.

On the other direction if $\mathbf{DC}_\kappa(2)$ holds and $T$ is a tree of height $\kappa$ in which every short sequence has an upper bound not in the sequence, consider the relation $R$ on $T^{<\kappa}\times T$ defined by $f\mathrel{R} x$ if and only if $f$ is a branch cofinal strictly below $x$ or that $f$ does not define a branch but $x$ is a successor of someone which has no successors in the range of $f$ (or of a cofinal sequence below $x$ in the range of $f$). This is similar to what we did the previous time.

There is $f\colon\kappa\to T$ which we will now show must define a branch. For $0$, $f\upharpoonright 0\mathrel{R} f(0)$ which is to say that $f(0)$ has level zero, so we have a branch of length $1$.

Assume for $\beta<\alpha$ it holds that $f\upharpoonright\beta$ defines a branch below the $\beta+1$-th level. If $\alpha$ is a limit then for all $\beta<\alpha$ we have that $f$ defines a branch below the $\beta$ level, so it must be the same branch, so $f\upharpoonright\alpha$ must also define a branch up to level $\alpha+1$; if $\alpha=\beta+1$ then this is again have to be that we continue this branch.

Therefore $f$ is a branch of length $\kappa$ in $T$ as wanted.

-
Indeed, this was my first thought for such a statement, but I don't think it works. Start with the set $$X=\bigcup_{n<\omega}\omega_n\times\{n\},$$ partially ordered by the relation $\langle\alpha,m\rangle\sqsubset\langle\beta,n\rangle$ iff $m=n$ and $\alpha<\beta$, then append a least element to $X$ to get a tree $T$. Then $T$ has a branch of length $\omega_n$ for each $n<\omega$ (so $T$ has height $\omega_\omega=\sup_{n<\omega}\omega_n$), and every element of $T$ has a successor, but $T$ has no branch of length $\omega_\omega$. –  Cameron Buie Dec 5 '12 at 11:10
I think that you need to add the requirement that short branches are bounded or something like that. I am not by a keyboard, but when I return home I will edit. –  Asaf Karagila Dec 5 '12 at 11:32
I'm still not sure that works, though perhaps I'm misunderstanding what you mean by "upper bound". It seems like if I replace $\omega_n$ with $\omega_n+1$ in my definition of $X$, above, then we have a counterexample. I think we may well need to know that short branches are bounded in length somehow. –  Cameron Buie Dec 6 '12 at 4:06
I think I should have left the successor requirement. I will edit it back in shortly :-) –  Asaf Karagila Dec 6 '12 at 7:39
There, this is what I actually meant. I wanted to subsume the requirement for a successor in the requirement for short branches. Obviously it wasn't clear enough, but now it should be. –  Asaf Karagila Dec 6 '12 at 9:16