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

Posted on June 14, 2011 by alanmath

(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

This entry was posted in Descriptive Set Theory, Kechris. Bookmark the permalink.

Leave a comment