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 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
Product 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.