Tree (descriptive set theory)
Encyclopedia
In descriptive set theory
, a tree on a set
is a set of finite sequences of elements of 
that is closed under initial segments.
More formally, it is a subset
of 
, such that if
and
,
then
.
In particular, every nonempty tree contains the empty sequence.
A branch through
is an infinite sequence
of elements of 
such that, for every natural number
,
,
where
denotes the sequence of the first 
elements of 
. The set of all branches through 
is denoted 
and called the body of the tree 
.
A tree that has no branches is called wellfounded; a tree with at least one branch is illfounded.
A node (that is, element) of
is terminal if there is no node of 
properly extending it; that is, 
is terminal if there is no element 
of 
such that that 
. A tree with no terminal nodes is called pruned.
If we equip
with the product topology
(treating X as a discrete space
), then every closed subset of
is of the form 
for some pruned tree 
(namely, 
). Conversely, every set 
is closed.
Frequently trees on cartesian product
s
are considered. In this case, by convention, the set 
is identified in the natural way with a subset of 
, and 
is considered as a subset of 
. We may then form the projection of 
,
Every tree in the sense described here is also a tree in the wider sense
, i.e., the pair (T, <), where < is defined by
is a partial order in which each initial segment is well-ordered. The height of each sequence x is then its length, and hence finite.
Conversely, every partial order (T, <) where each initial segment { y: y < x0 } is well-ordered is isomorphic to a tree described here, assuming that all elements have finite height.
Descriptive set theory
In mathematical logic, descriptive set theory is the study of certain classes of "well-behaved" subsets of the real line and other Polish spaces...
, a tree on a set
is a set of finite sequences of elements of that is closed under initial segments.More formally, it is a subset
of , such that ifand
,then
.In particular, every nonempty tree contains the empty sequence.
A branch through
is an infinite sequence of elements of such that, for every natural number
,,where
denotes the sequence of the first elements of . The set of all branches through is denoted and called the body of the tree .A tree that has no branches is called wellfounded; a tree with at least one branch is illfounded.
A node (that is, element) of
is terminal if there is no node of properly extending it; that is, is terminal if there is no element of such that that . A tree with no terminal nodes is called pruned.If we equip
with the product topologyProduct topology
In topology and related areas of mathematics, a product space is the cartesian product of a family of topological spaces equipped with a natural topology called the product topology...
(treating X as a discrete space
Discrete space
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points are "isolated" from each other in a certain sense.- Definitions :Given a set X:...
), then every closed subset of
is of the form for some pruned tree (namely, ). Conversely, every set is closed.Frequently trees on cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
s
are considered. In this case, by convention, the set is identified in the natural way with a subset of , and is considered as a subset of . We may then form the projection of ,
Every tree in the sense described here is also a tree in the wider sense
Tree (set theory)
In set theory, a tree is a partially ordered set In set theory, a tree is a partially ordered set (poset) In set theory, a tree is a partially ordered set (poset) (T, In set theory, a tree is a partially ordered set (poset) (T, ...
, i.e., the pair (T, <), where < is defined by
- x<y ⇔ x is a proper initial segment of y,
is a partial order in which each initial segment is well-ordered. The height of each sequence x is then its length, and hence finite.
Conversely, every partial order (T, <) where each initial segment { y: y < x0 } is well-ordered is isomorphic to a tree described here, assuming that all elements have finite height.