Let $(T,\leq)$ be a tree of height $\kappa$ ($\kappa$ infinite cardinal), all levels of which are finite. Prove that $T$ has a branch of length $\kappa$. A hint is given: Let $U_\alpha=\{x\in T_\alpha\mid |\{y\in T\mid x\leq y\}|=\kappa\}$. Prove that $\{|U_\alpha|\mid\alpha<\kappa\}\subseteq\mathbb{N}$ is bounded. Let $m$ be its maximum ($m\geq 1$). Show $T$ has exactly $m$ branches of length $\kappa$. (Exercise 3.3, Ch 12 from Introduction to Set Theory by Hrbacek and Jech.)

First of all, can we think of $T$ as some subtree of $\kappa^{<\omega}$ or relate it to some $\theta^{<\lambda}$? I'm not really sure how to form the correspondence.

I don't see what goes wrong if $\{|U_\alpha|\mid\alpha<\kappa\}\subseteq\mathbb{N}$ is unbounded. We get a countable set of distinct nodes, with each node having $\kappa$-many nodes above it; does that give us a subset of $T$ with size greater than $\kappa$?

I'm new to this and I'm quite confused. Thanks in advance for any help.


The hint actually does make a misleading oversight. In fact, it not generally true that $|U_\alpha|$ is bounded. First off, there is clearly a counterexample with height $\omega$: simply take a binary tree of that height. But it fails for some larger heights as well. For instance, we can make a tree of height $\aleph_\omega$ that starts with one branch, splits into two branches at level $\aleph_1,$ then the two branches each split into two at $\aleph_2,$ and so on. Then, it's clear that $|U_\alpha|$ is unbounded, but the levels are all finite. A similar counterexample will work whenever the height $\kappa$ has cofinality $\omega.$

But notice these counterexamples still have a branch of length $\kappa.$ In fact, we can see for $cf(\kappa) =\omega$ that we will always have a branch of length $\kappa,$ by just repeating the argument for Konig's lemma on a cofinal sequence of levels. So the theorem is still true for these $\kappa,$ even if the hint is not.

On the other hand, if $cf(\kappa) > \omega,$ then $|U_\alpha|$ is bounded like the hint suggests. Otherwise let $\alpha_n$ be the smallest level such that $|U_\alpha|\ge n.$ Then $\alpha_n$ will be a cofinal sequence in $\kappa$, contradicting $cf(\kappa) > \omega.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.