## König’s Lemma (p20 (A))

(Exercise 4.12)
Let $T$ be a tree on $A$.  If $T$ is finite splitting, then $[T] \neq \emptyset$ iff $T$ is infinite.  Show that this fails if $T$ is not finite splitting.

Proof.

$\Rightarrow$”. Suppose $T$ is finite.  Then, obviously, $[T] = \emptyset$.
$\Leftarrow$”. Suppose $T$ is infinite.  Since $T$ is finite splitting, for every $n \in \mathbb{N}$, the number of strings in $T$ of length $n$ is finite. (see Fact here)

Now, there is no terminal string of maximal length. For if there were, $T$ would be finite.  That is, for each $n$, there exists terminal string $s^n$, where $\text{length}(s^n) = m \ge n$.  Let $C := \{ s^n : n \in \mathbb{N} \}$. Now, there must be an infinite subset $B_1 \subset C$ such that $r, s \in B_1$ implies $r|1 = s|1$, for otherwise the fact that there are only finitely many sequences of length $1$ would be contradicted.  Define $t^1 := r|1$.

Now, suppose that for $k \in \mathbb{N}$, there exists $B_k \subset B_{k - 1}$ such that $B_k$ is infinite, $r, s \in B_k$ implies $s|k = r|k := t^k$, and $t^k \supset t^{k - 1}$.  Now, there must exist infinite $B_{k + 1} \subset B_k$ such that $r, s \in B_{k + 1}$ implies $r|(k + 1) = s|(k + 1) := t^{k + 1}$, for otherwise the fact that there are only finitely many sequences of length $k + 1$ would be contradicted. Also, $t^{k + 1} \supset t^k$.

So, we have inductively constructed a sequence $(t^n) \subset T$ with $t^n \subset t^{n + 1}$ for all $n$.  Thus, there exists $x \in A^{\mathbb{N}}$ such that $x|n = t^n \in T$; that is $[T] \neq \emptyset$.

Finally, define $T := \{ \emptyset \} \cup \{ (n) : n \in \mathbb{N} \}$.  Then $T$ is infinite and $[T] = \emptyset$.  But $T$ is not finite splitting.

$\blacksquare$