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
    @AsafKaragila I badgered him a little bit this morning per $y$our reques$t$ :)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
    Sure! I enjoyed these two proofs!2012-12-07