In descriptive set theory, a tree on a set
X
is a collection of finite sequences of elements of
X
such that every prefix of a sequence in the collection also belongs to the collection.
The collection of all finite sequences of elements of a set
X
is denoted
X
<
ω
. With this notation, a tree is a nonempty subset
T
of
X
<
ω
, such that if
⟨
x
0
,
x
1
,
…
,
x
n
−
1
⟩
is a sequence of length
n
in
T
, and if
0
≤
m
<
n
, then the shortened sequence
⟨
x
0
,
x
1
,
…
,
x
m
−
1
⟩
also belongs to
T
. In particular, choosing
m
=
0
shows that the empty sequence belongs to every tree.
Branches and bodies
A branch through a tree
T
is an infinite sequence of elements of
X
, each of whose finite prefixes belongs to
T
. The set of all branches through
T
is denoted
[
T
]
and called the body of the tree
T
.
A tree that has no branches is called wellfounded; a tree with at least one branch is illfounded. By König's lemma, a tree on a finite set with an infinite number of sequences must necessarily be illfounded.
A finite sequence that belongs to a tree
T
is called a terminal node if it is not a prefix of a longer sequence in
T
. Equivalently,
⟨
x
0
,
x
1
,
…
,
x
n
−
1
⟩
∈
T
is terminal if there is no element
x
of
X
such that that
⟨
x
0
,
x
1
,
…
,
x
n
−
1
,
x
⟩
∈
T
. A tree that does not have any terminal nodes is called pruned.
In graph theory, a rooted tree is a directed graph in which every vertex except for a special root vertex has exactly one outgoing edge, and in which the path formed by following these edges from any vertex eventually leads to the root vertex. If
T
is a tree in the descriptive set theory sense, then it corresponds to a graph with one vertex for each sequence in
T
, and an outgoing edge from each nonempty sequence that connects it to the shorter sequence formed by removing its last element. This graph is a tree in the graph-theoretic sense. The root of the tree is the empty sequence.
In order theory, a different notion of a tree is used: an order-theoretic tree is a partially ordered set with one minimal element in which each element has a well-ordered set of predecessors. Every tree in descriptive set theory is also an order-theoretic tree, using a partial ordering in which two sequences
T
and
U
are ordered by
T
<
U
if and only if
T
is a proper prefix of
U
. The empty sequence is the unique minimal element, and each element has a finite and well-ordered set of predecessors (the set of all of its prefixes). An order-theoretic tree may be represented by an isomorphic tree of sequences if and only if each of its elements has finite height (that is, a finite set of predecessors).
The set of infinite sequences over
X
(denoted as
X
ω
) may be given the product topology, treating X as a discrete space. In this topology, every closed subset
C
of
X
ω
is of the form
[
T
]
for some pruned tree
T
. Namely, let
T
consist of the set of finite prefixes of the infinite sequences in
C
. Conversely, the body
[
T
]
of every tree
T
forms a closed set in this topology.
Frequently trees on Cartesian products
X
×
Y
are considered. In this case, by convention, we consider only the subset
T
of the product space,
(
X
×
Y
)
<
ω
, containing only sequences whose even elements come from
X
and odd elements come from
Y
(e.g.,
⟨
x
0
,
y
1
,
x
2
,
y
3
…
,
x
2
m
,
y
2
m
+
1
⟩
). Elements in this subspace are identified in the natural way with a subset of the product of two spaces of sequences,
X
<
ω
×
Y
<
ω
(the subset for which the length of the first sequence is equal to or 1 more than the length of the second sequence). In this way we may identify
[
X
<
ω
]
×
[
Y
<
ω
]
with
[
T
]
for over the product space. We may then form the projection of
[
T
]
,
p
[
T
]
=
{
x
→
∈
X
ω
|
(
∃
y
→
∈
Y
ω
)
⟨
x
→
,
y
→
⟩
∈
[
T
]
}
.
