Tree (set theory)
Encyclopedia
In set theory
, a tree is a partially ordered set
(poset) (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is well-ordered by the relation <. For each t ∈ T, the order type
of {s ∈ T : s < t} is called the height of t (denoted ht(t, T)). The height of T itself is the least ordinal
greater than the height of each element of T. A root of a tree T is an element of height 0. Frequently trees are assumed to have only one root (as the typical questions that are investigated in this field are easily reduced to questions about single-rooted trees).
Trees with a single root in which each element has finite height can be naturally viewed as rooted trees in the graph-theoretical sense
: there is an edge from x to y if and only if y is a direct successor of x (i.e., x<y, but there is no element between x and y). However, if T is a tree of height > ω, then there is no natural edge relation that will make T a tree in the sense of graph theory.
A branch of a tree is a maximal chain in the tree (that is, any two elements of the branch are comparable, and any element of the tree not in the branch is incomparable with at least one element of the branch). The length of a branch is the ordinal
that is order isomorphic
to the branch. A tree is a κ-tree if and only if it has height κ and every level has size less than κ. For each ordinal α, the α-th level of T is the set of all elements of T of height α. The width of a tree is the supremum of the cardinalities of its levels.
There are some fairly simply stated yet hard problems in infinite tree theory. Examples of this are the Kurepa conjecture and the Suslin conjecture. Both of these problems are known to be independent of Zermelo-Fraenkel set theory. König's lemma
states that every ω-tree has an infinite branch. On the other hand, it is a theorem of ZFC that there are uncountable trees with no uncountable branches and no uncountable levels; such trees are known as Aronszajn tree
s. A κ-Suslin tree
is a tree of height κ which has no chains or antichains of size κ. In particular, if κ is singular (i.e. not regular
) then there exists a κ-Aronszajn tree and a κ-Suslin tree. In fact, for any infinite cardinal κ, every κ-Suslin tree is a κ-Aronszajn tree (the converse does not hold).
Note: the Suslin conjecture was originally stated as a question about certain total orderings but it is equivalent to the statement: Every tree of height ω1
has an antichain
of cardinality ω1 or a branch of length ω1.
), which helps this definition to be used in automata theory
.
A tree is a set
such that if 
and 
then, 
and for all 
. The element of 
are known as nodes and empty word 
is root of 
. For every 
, the element 
is a successor of 
in direction 
. The number of successors of 
is called the degree or arity of 
and represented as 
. A node is a leaf if it has no successors. If every node of a tree has finitely many successors then it is finitely branching tree, otherwise infinitely branching tree. A path 
is a subset of 
such that 
and for every 
, either 
is a leaf or there exist a unique 
such that 
. A path may be a finite or infinite set. If all paths of a tree are finite then tree is called finite, otherwise infinite. A tree is called fully infinite if all paths of the tree are infinite. Given an alphabet 
, a 
-labeled tree is a pair 
, where T is a tree and 
maps each node of 
to a letter in 
. A labeled tree formally defines commonly used term tree structure. A set of labeled trees is called a tree language.
A tree is ranked if there is an order among successors of each node of the tree. Above definition of tree naturally suggest an order among successors, which can be used to make tree ranked. Sometimes, an extra function
is defined. This function associate a fixed arity to each letter of alphabet. In this case for each 
has to satisfy 
.
For example, above definition is used in defining infinite tree automaton
.
and 
. We define labeling function V as follows, labeling for root node is 
and, for every other node 
, the labellings for successor nodes are 
and 
. It is clear from the picture that T forms infinite(full) binary tree.
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, a tree is a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
(poset) (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is well-ordered by the relation <. For each t ∈ T, the order type
Order type
In mathematics, especially in set theory, two ordered sets X,Y are said to have the same order type just when they are order isomorphic, that is, when there exists a bijection f: X → Y such that both f and its inverse are monotone...
of {s ∈ T : s < t} is called the height of t (denoted ht(t, T)). The height of T itself is the least ordinal
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
greater than the height of each element of T. A root of a tree T is an element of height 0. Frequently trees are assumed to have only one root (as the typical questions that are investigated in this field are easily reduced to questions about single-rooted trees).
Trees with a single root in which each element has finite height can be naturally viewed as rooted trees in the graph-theoretical sense
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
: there is an edge from x to y if and only if y is a direct successor of x (i.e., x<y, but there is no element between x and y). However, if T is a tree of height > ω, then there is no natural edge relation that will make T a tree in the sense of graph theory.
A branch of a tree is a maximal chain in the tree (that is, any two elements of the branch are comparable, and any element of the tree not in the branch is incomparable with at least one element of the branch). The length of a branch is the ordinal
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
that is order isomorphic
Order isomorphism
In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets . Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that one of...
to the branch. A tree is a κ-tree if and only if it has height κ and every level has size less than κ. For each ordinal α, the α-th level of T is the set of all elements of T of height α. The width of a tree is the supremum of the cardinalities of its levels.
There are some fairly simply stated yet hard problems in infinite tree theory. Examples of this are the Kurepa conjecture and the Suslin conjecture. Both of these problems are known to be independent of Zermelo-Fraenkel set theory. König's lemma
König's lemma
König's lemma or König's infinity lemma is a theorem in graph theory due to Dénes Kőnig . It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic,...
states that every ω-tree has an infinite branch. On the other hand, it is a theorem of ZFC that there are uncountable trees with no uncountable branches and no uncountable levels; such trees are known as Aronszajn tree
Aronszajn tree
In set theory, an Aronszajn tree is an uncountable tree with no uncountable branches and no uncountable levels. For example, every Suslin tree is an Aronszajn tree...
s. A κ-Suslin tree
Suslin tree
In mathematics, a Suslin tree is a tree of height ω1 such thatevery branch and every antichain is at most countable. Every Suslin tree is an Aronszajn tree....
is a tree of height κ which has no chains or antichains of size κ. In particular, if κ is singular (i.e. not regular
Regular cardinal
In set theory, a regular cardinal is a cardinal number that is equal to its own cofinality. So, crudely speaking, a regular cardinal is one which cannot be broken into a smaller collection of smaller parts....
) then there exists a κ-Aronszajn tree and a κ-Suslin tree. In fact, for any infinite cardinal κ, every κ-Suslin tree is a κ-Aronszajn tree (the converse does not hold).
Note: the Suslin conjecture was originally stated as a question about certain total orderings but it is equivalent to the statement: Every tree of height ω1
First uncountable ordinal
In mathematics, the first uncountable ordinal, traditionally denoted by ω1 or sometimes by Ω, is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum of all countable ordinals...
has an antichain
Antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
of cardinality ω1 or a branch of length ω1.
Tree (automata theory)
Following definition of the tree is slightly different formalism of the tree compare to above introduction. For example, each node of the tree is a word over set of natural numbers(), which helps this definition to be used in automata theoryAutomata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
.
A tree is a set
such that if and then, and for all . The element of are known as nodes and empty word is root of . For every , the element is a successor of in direction . The number of successors of is called the degree or arity of and represented as . A node is a leaf if it has no successors. If every node of a tree has finitely many successors then it is finitely branching tree, otherwise infinitely branching tree. A path is a subset of such that and for every , either is a leaf or there exist a unique such that . A path may be a finite or infinite set. If all paths of a tree are finite then tree is called finite, otherwise infinite. A tree is called fully infinite if all paths of the tree are infinite. Given an alphabet , a -labeled tree is a pair , where T is a tree and maps each node of to a letter in . A labeled tree formally defines commonly used term tree structure. A set of labeled trees is called a tree language.A tree is ranked if there is an order among successors of each node of the tree. Above definition of tree naturally suggest an order among successors, which can be used to make tree ranked. Sometimes, an extra function
is defined. This function associate a fixed arity to each letter of alphabet. In this case for each has to satisfy .For example, above definition is used in defining infinite tree automaton
Infinite tree automaton
In computer science and mathematical logic, an infinite tree automaton is a state machine that deals with infinite tree structure. It can be viewed as an extension from a finite tree automaton, which accepts only finite tree structures...
.
Example
Let and . We define labeling function V as follows, labeling for root node is and, for every other node , the labellings for successor nodes are and . It is clear from the picture that T forms infinite(full) binary tree.See also
- Cantor treeCantor treeIn mathematical set theory, the Cantor tree is either the full binary tree of height ω + 1, or a topological space related to this by joining its points with intervals, that was introduced by Robert Lee Moore in the late 1920s as an example of a non-metrizable Moore space .-References: |...
- Kurepa tree
- Laver tree
- Tree (descriptive set theory)
- Continuous graph
External links
- Sets, Models and Proofs by Ieke MoerdijkIeke MoerdijkIzak Moerdijk is professor of Mathematics at the Mathematisch Instituut of the Radboud University Nijmegen. He is the author of several influential books.-Selected works:...
and Jaap van Oosten, see Definition 3.1 and Exercise 56 on pp. 68–69. - tree (set theoretic) by Henry on PlanetMath
- branch by Henry on PlanetMath
- example of tree (set theoretic) by uzeromay on PlanetMath