Problem with the definition of tree in descriptive set theory

278 Views Asked by At

I have a problem with the standard definition of tree in descriptive set theory.
The following is the definition:

Definition: A tree on a set $A$ is a subset $T \subseteq A^{<\mathbb{N}}$ closed under initial segments, i.e. if $t \in T$ and $s \subseteq t$, then $s \in T$.

[Here, $A^{<\mathbb{N}}$ referes to the space of all finite sequences from $A$.]

My problem lies in particular in the next definition.

An infinite branch of $T$ is a sequence $x \in A^{\mathbb{N}}$ such that $x|n \in T$ for all $n \in \mathbb{N}$.

[Here, $x|n := (x_0, \dots, x_{n-1})$.]

So far, so good. I do understand the definition of infinite branch. What puzzles me is how we can have an infinite branch (that is indeed a $x \in A^{\mathbb{N}}$) in a tree $T \subseteq A^{<\mathbb{N}}$.

In other words, I don't see how is possible to make coexist an infinite object (the infinite branch) in a tree, given the very definition of tree as a subset of $A^{<\mathbb{N}}$.

As always, any feedback will be greatly welcome.
Thank you for your time and your help.

1

There are 1 best solutions below

9
On BEST ANSWER

Branches are equivalent to subsets of the tree, not to elements of the tree.

A branch, essentially, is a maximal chain, which need not have a maximal element. Note that the branch is a function in $A^\Bbb N$, not in $A^{<\Bbb N}$.

The definition you quote says the following: $x\colon\Bbb N\to A$ is called an infinite branch (in $T$), if $\{x\restriction\{0,\ldots,n-1\}\mid n\in\Bbb N\}$ is a maximal chain in $T$.

On the other hand, if $C$ is an infinite maximal chain in $T$, then $\bigcup C$ is a function from $\Bbb N$ to $A$, so it is an element of $A^\Bbb N$.