6
$\begingroup$

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?

2 Answers 2

4

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

  • 0
    By maximal, what do you mean? The definition of branch I'm using is a maximal (with respect to set inclusion) linearly ordered subset.2012-12-05
  • 0
    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.2012-12-05
  • 0
    More generally, if a tree of height $\le \kappa$ means a poset with a least element such that the set of predecessors of any element has order type $<\kappa$, then a maximal branch is a $\subset$-maximal wellordered subset of the poset, or equivalently, a $\subset$-maximal linearly ordered subset of the poset.2012-12-05
  • 0
    @Trevor: So far as I can see, your *maximal branch* is Cameron’s (and my) *branch*; I think that in your second sentence you want ‘has a maximal branch whose length is the height of the tree’.2012-12-05
  • 0
    Consider, then, the tree of all functions $f:\alpha\to\kappa$ with $0<\alpha<\kappa$ such that $f(\beta)=\gamma$ for all $\beta<\alpha$, along with all their restrictions $f\restriction\beta$ with $0<\beta<\alpha$. I believe that this meets your definition of a tree, but it fails to have a branch of length $\kappa$, though it certainly has a (maximal) branch. Check me on this one @Brian. I think your first proposed equivalence may be correct, though. I'll think on it.2012-12-05
  • 0
    I will edit the answer to clarify my terminology. It looks like Cameron's last comment refutes the thing Brian thinks I wanted and not what I actually said :)2012-12-05
  • 0
    It actually refutes both what you said *and* Brian's proposed correction. That ability to continue is quite crucial.2012-12-05
  • 0
    @CameronBuie Actually I spoke too soon, because I don't understand your example at all. What is $\gamma$, and do you mean "branch of length $\alpha$"?2012-12-05
  • 0
    Note that Zorn's lemma (applied to the set of branches under inclusion) implies that every tree has a maximal branch. So I hope you're not trying to refute the statement in my second paragraph outright :)2012-12-05
  • 1
    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. :P2012-12-05
  • 0
    It does, though, show that your statement is not equivalent to $\text{DC}_\kappa$.2012-12-05
  • 0
    @CameronBuie Could you explain how, perhaps with reference to my purported proof?2012-12-05
  • 2
    @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).2012-12-05
  • 0
    @Asaf: Thanks for the reference!2012-12-05
  • 1
    I see it now. Thanks! (For some reason, I was convinced that your statement was equivalent to the strictly weaker Axiom of $\kappa$-Choice.)2012-12-05
  • 0
    Trevor, the clock is ticking, the semester is about the end. Did you badger Magidor some more?2012-12-07
  • 0
    @AsafKaragila I badgered him a little bit this morning per your request :)2012-12-13
2

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

  • 0
    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$.2012-12-05
  • 0
    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.2012-12-05
  • 0
    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.2012-12-06
  • 0
    I think I should have left the successor requirement. I will edit it back in shortly :-)2012-12-06
  • 0
    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.2012-12-06
  • 0
    Thanks again, Asaf. I'll work on understanding your proof that $\text{DC}_\kappa(2)$ implies $\text{DC}_\kappa(3)$ (or come up with my own). I'll let you know if I have any questions.2012-12-07
  • 0
    Sure! I enjoyed these two proofs!2012-12-07