On trees: Compactness and finite splitting

Terms and notation are defined here.

(Kechris exercise 4.11)
(a) Let T be a pruned tree on A.  It follows that [T] is compact iff T is finite splitting.
(b) In particular, if K \subset \mathcal{N} = \mathbb{N}^\mathbb{N} is compact, there is x \in \mathcal{N} such that for all y \in K, y(n) \le x(n) for every n.  Conclude that \mathcal{N} is not a countable union of compact sets.


(a) “\Rightarrow”. Suppose T is not finite splitting.  So there exists s \in T, of length n - 1, such that infinitely many a \in A satisfy s \land a \in T.  For each a here, there exists x_a \in [T] such that x_a|n = s \land a \in T. Pick sequence (x_{a_i})_{i = 0}^\infty.  Then, d(x_{a_i}, x_{a_j}) = 2^{-n - 1}, for any i, j \in \mathbb{N}.  Hence, there is no convergent subsequence.  Hence, [T] is not compact.

\Leftarrow”.  Suppose T is finite splitting.  Let (x_n) be a sequence in [T].  If s \in [T], k \in \mathbb{N}, let P(s, k) be the following statement: B_{s}^k := \{ t \in (x_n) : t|k = s | k \} is an infinite
set. Then, it is clear that there exists y_1 \in (x_n) such that P(y_1, 1) holds, since there are only finitely many sequences of length 1 in T (since T is finite splitting).

Now, assume inductively that there exists y_k \in (x_n) such that P(y_k, k) holds.  Then, again since T is finite splitting, there are only finitely many choices for y_k(k + 1).  Hence, since B_{y_k}^k is infinite, there must exist y_{k + 1} \in B_{y_k}^k such that P(y_{k + 1}, k + 1)

Hence we have inductively defined a sequence (y_k) \subset (x_n) such that y_k \to s for some s \in [T].  That is, (x_n) contains a convergent subsequence, so [T] is compact.

(b) Let K \subset \mathcal{N} be compact.  Then K is closed, and hence corresponds to a pruned tree T, such that K = [T].  So, for each n, \{ y(n): y \in K \} := A_n is finite (by the above).  So define x \in \mathcal{N} by x(n) = \text{ max}A_n.  This x satisfies the above property.

Now, suppose U = \bigcup_{i = 0}^\infty K_i, where each K_i is compact.  Then for each K_i we have x_i such that y \in K_i implies y(n) \le x_i(n) for all n.  Now define z: \mathbb{N} \to \mathbb{N} by z(n) = x_n(n) + 1.  Then, z \notin K_i for any i.  Therefore, U \ne \mathcal{N}.

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

2 Responses to On trees: Compactness and finite splitting

  1. Cenzer says:

    In part (a), you need to say that $y_{k+1}$ agrees with $y_k$ up to $k$, so that the sequence converges.

    I would prefer an argument based on trees. That is, suppose that K_i = [S_i]$ is a decreasing sequence of nonempty closed sets, where $S_i$ is a subtree of $T$ and show that $S = \Cap_i S_i$ is infinite and therefore [S] = \Cap [S_i]$ is nonempty.

  2. alanmath says:

    Thank you Dr. Cenzer. Here is an alternate proof, along the lines you suggested.
    Proof 2.
    \Leftarrow”. Suppose T is finite splitting. Let (K_i = [S_i]) be a descending sequence of nonempty closed sets, where S_i is a pruned subtree of T.

    (i) S = \bigcap_i S_i is infinite.
    Proof. S = \bigcap_i S_i is obviously a tree. Suppose S were finite. Let x \in S be an element of maximum length. Since x \in S_i, \forall i, x = \alpha_i|n for some \alpha_i \in [S_i], \forall i. Consider \{ \alpha_i( n + 1 ): i \in \mathbb{N} \} = \{ \beta_1, \ldots, \beta_m \}, since T is finite splitting. For each \beta_j, 1 \le j \le m, there exists S_{k_j} such that \beta_j \notin S_{k_j}. Let k = \max k_j. Since [S_k] \subset [S_{k_j}] \, \forall j, \beta_j \notin S_k \, \forall j. But this is a contradiction, showing that S is infinite.

    (ii) [S] = \bigcap_i [S_i] is nonempty.
    Proof. Since S is infinite, and finite splitting, we must have [S] \neq \emptyset. It is easy to see that [S] = \bigcap_i [S_i]. Hence, \bigcap_i K_i \neq \emptyset, so [T] is compact.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s