## Trees

Definitions and notation for trees.

$A^{< \mathbb{N}} = \bigcup_n A^n$.  If $x \in A^n \cup A^\mathbb{N}$, and $k \in \mathbb{N}$, $x|k = (x_0, \ldots, x_{k - 1}) \in A^k$.  If $s \in A^n, t \in A^m$, the concatenation of $s$ and $t$ is defined by $s \land t = (s_0, \ldots, s_{n - 1}, t_0, \ldots, t_{m -1}) \in A^{n + m}$.  If $s \in A^n$, $t \in A^m$, then $s$ is an initial segment of $t$ and $t$ is an extension of $s$ (written $s \subset t$), if $s = t | k$, for some $k \le m$.

A tree on a set $A$ is a subset $T \subset A^{< \mathbb{N}}$ closed under initial segments. The body of $T$, $[T] = \{ x \in A^{\mathbb{N}} : \forall n(x | n \in T) \}$.  An element $s$ of $T$ is called terminal if $s \in T$ and $s \land a \notin T$ for all $a \in A$.

Let $T$ is a tree on $A$. $T$ is finite splitting if for every $s \in T$ there only finitely many $a \in A$ such that $s \land a \in T$$T$ is pruned if every $s \in T$ has a proper extension $t \supsetneqq s, t \in T$.

Fact.   If $T$ is finite splitting, for every $n \in \mathbb{N}$, the number of strings in $T$ of length $n$ is finite.
Proof.
Assume that for some $n$, the number of strings in $T$ of length $n$ is infinite.  Then, there must be a minimal number $k \le n$, which satisfies the property that infinitely many of the strings differ at position $k$, but agree at all previous positions.  Then $T$ is not finite splitting. $\blacksquare$