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 TT 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

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

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