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

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?

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer
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

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.