## 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.

Proof.

(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)$
holds.

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.
(a)
$\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.