Tree (set theory)

Tree (set theory)

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 &gt; &omega;, 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 trees. 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.

See also

*Kurepa tree
*Laver tree
* Tree (descriptive set theory)

External links

* [http://www.math.uu.nl/people/jvoosten/syllabi/logicasyllmoeder.pdf Sets, Models and Proofs] by I. Moerdijk and [http://www.math.uu.nl/people/jvoosten/ Jaap van Oosten] , see Definition 3.1 and Exercise 56 on pp. 68–69.
* [http://planetmath.org/encyclopedia/TreeSetTheoretic.html tree (set theoretic)] by [http://planetmath.org/?op=getuser&id=455 Henry] on [http://planetmath.org/ PlanetMath]
* [http://planetmath.org/encyclopedia/Branch.html branch] by [http://planetmath.org/?op=getuser&id=455 Henry] on [http://planetmath.org/ PlanetMath]
* [http://planetmath.org/encyclopedia/ExampleOfTreeSetTheoretic.htm example of tree (set theoretic)] by [http://planetmath.org/?op=getuser&id=4983 uzeromay] on [http://planetmath.org/ PlanetMath]

References

*
* Chapter 2, Section 5.
*
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Tree (descriptive set theory) — In descriptive set theory, a tree on a set X is a set of finite sequences of elements of X that is closed under subsequences. More formally, it is a subset T of X^{ …   Wikipedia

  • Tree (graph theory) — Trees A labeled tree with 6 vertices and 5 edges Vertices v Edges v 1 Chromatic number …   Wikipedia

  • List of set theory topics — Logic portal Set theory portal …   Wikipedia

  • Morass (set theory) — For the variety of wetland, see marsh. In axiomatic set theory, a mathematical discipline, a morass is an infinite combinatorial structure, used to create large structures from a small number of small approximations. They were invented by Ronald… …   Wikipedia

  • Tree structure — A tree structure showing the possible hierarchical organization of an encyclopedia …   Wikipedia

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Tree (disambiguation) — A tree is a woody plant.Tree may also refer to: *Tree structure, a way of representing the hierarchical nature of a structure in a graphical form *Tree (data structure), a widely used computer data structure that emulates a tree structure with a… …   Wikipedia

  • Set — 1. v. (setting; past and past part. set) 1 tr. put, lay, or stand (a thing) in a certain position or location (set it on the table; set it upright). 2 tr. (foll. by to) apply (one thing) to (another) (set pen to paper). 3 tr. a fix ready or in… …   Useful english dictionary

  • set — 1. v. (setting; past and past part. set) 1 tr. put, lay, or stand (a thing) in a certain position or location (set it on the table; set it upright). 2 tr. (foll. by to) apply (one thing) to (another) (set pen to paper). 3 tr. a fix ready or in… …   Useful english dictionary

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”