Tree (descriptive set theory)
Encyclopedia
In descriptive set theory
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<yx 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.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK