In
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
, a tree is a
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) 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 ...
(''T'', <) such that for each ''t'' ∈ ''T'', the set is
well-ordered by the relation <. Frequently trees are assumed to have only one root (i.e.
minimal element), as the typical questions investigated in this field are easily reduced to questions about single-rooted trees.
Definition
A tree is a
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) 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 ...
(poset) (''T'', <) such that for each ''t'' ∈ ''T'', the set is
well-ordered by the relation <. In particular, each well-ordered set (''T'', <) is a tree. For each ''t'' ∈ ''T'', the
order type
In mathematics, especially in set theory, two ordered sets and are said to have the same order type if they are order isomorphic, that is, if there exists a bijection (each element pairs with exactly one in the other set) f\colon X \to Y suc ...
of 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. Trees in set theory are often defined to grow downward making the root the greatest node.
Trees with a single root may be viewed as rooted trees in the sense of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
in one of two ways: either as a
tree (graph theory)
In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ...
or as a
trivially perfect graph. In the first case, the graph is the undirected
Hasse diagram of the partially ordered set, and in the second case, the graph is simply the underlying (undirected) graph of the partially ordered set. However, if ''T'' is a tree of height >
ω, then the Hasse diagram definition does not work. For example, the partially ordered set
does not have a Hasse Diagram, as there is no predecessor to ω. Hence a height of at most ω is required in this case.
A ''branch'' of a tree is a maximal
chain
A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. ...
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
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 (posets). Whenever two posets are order isomorphic, they can be ...
to the branch. For each ordinal α, the ''α-th level'' of ''T'' is the set of all elements of ''T'' of height α. A tree is a κ-tree, for an ordinal number κ, if and only if it has height κ and every level has
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
less than the cardinality of κ. The ''width'' of a tree is the supremum of the cardinalities of its levels.
Any single-rooted tree of height
forms a meet-semilattice, where meet (common ancestor) is given by maximal element of intersection of ancestors, which exists as the set of ancestors is non-empty and finite well-ordered, hence has a maximal element. Without a single root, the intersection of parents can be empty (two elements need not have common ancestors), for example
where the elements are not comparable; while if there are an infinite number of ancestors there need not be a maximal element – for example,
where
are not comparable.
A ''subtree'' of a tree
is a tree
where
and
is
downward closed
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
under
, i.e., if
and
then
.
Set-theoretic properties
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. By
Kőnig's lemma, 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 trees. Given a
cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. ...
κ, a ''κ-
Suslin tree In mathematics, a Suslin tree is a tree of height ω1 such that
every branch and every antichain is at most countable. They are named after Mikhail Yakovlevich Suslin.
Every Suslin tree is an Aronszajn tree.
The existence of a Suslin tree is i ...
'' is a tree of height κ which has no chains or antichains of size κ. In particular, if κ is
singular
Singular may refer to:
* Singular, the grammatical number that denotes a unit quantity, as opposed to the plural and other forms
* Singular homology
* SINGULAR, an open source Computer Algebra System (CAS)
* Singular or sounder, a group of boar ...
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).
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
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.
The size of the largest antichain in a partially ordered set is known as its wi ...
of cardinality ω
1 or a branch of length ω
1.
See also
*
Cantor tree
*
Kurepa tree
*
Laver tree
*
Tree (descriptive set theory)
*
Continuous graph
*
Prefix order
References
*
* Chapter 2, Section 5.
*
*
* {{Cite book, last = Kechris , first = Alexander S. , authorlink = Alexander S. Kechris , title = Classical Descriptive Set Theory , others =
Graduate Texts in Mathematics
Graduate Texts in Mathematics (GTM) (ISSN 0072-5285) is a series of graduate-level textbooks in mathematics published by Springer-Verlag. The books in this series, like the other Springer-Verlag mathematics series, are yellow books of a standard ...
156 , publisher = Springer , year = 1995 , id = {{isbn, 0-387-94374-9 {{isbn, 3-540-94374-9
External links
Sets, Models and Proofsby
Ieke Moerdijk
Izak (Ieke) Moerdijk (; born 23 January 1958) is a Dutch mathematician, currently working at Utrecht University, who in 2012 won the Spinoza prize.
Education and career
Moerdijk studied mathematics, philosophy and general linguistics at the Un ...
an
Jaap van Oosten see Definition 3.1 and Exercise 56 on pp. 68–69.
b
Henryo
PlanetMathb
Henryo
PlanetMathb
uzeromayo
PlanetMath
Set theory
*