You are here
Hometree (set theoretic)
Primary tabs
tree (set theoretic)
In a set theory, a tree is defined to be a set $T$ and a relation $<_{T}\subseteq T\times T$ such that:

$<_{T}$ is a partial ordering of $T$

For any $t\in T$, $\{s\in T\mid s<_{T}t\}$ is wellordered
The nodes (elements of the tree) immediately greater than a node are termed its children, the node immediately less is its parent (if it exists), any node less is an ancestor and any node greater is a descendant. A node with no ancestors is a root.
The partial ordering represents distance from the root, and the wellordering requirement prohibits any loops or splits below a node (that is, each node has at most one parent, and therefore at most one grandparent, and so on). Conversely, if $a<_{T}d$ then there is exactly one $b\leq_{T}d$ such that $a<_{T}b$ and there is nothing between $a$ and $b$. Note that there is no requirement that a node have a parent–there could be an infinitely long branch $a_{1}<_{T}a_{2}<_{T}a_{2}<_{T}\cdots$ with each $a_{i}<_{T}b$.
Since there is generally no requirement that the tree be connected, the null ordering makes any set into a tree, although the tree is a trivial one, since each element of the set forms a single node with no children.
Since the set of ancestors of any node is wellordered, we can associate it with an ordinal. We call this the height, and write: $\operatorname{ht}(t)=\operatorname{o.t.}(\{s\in T\mid s<_{T}t\})$. This all accords with normal usage: a root has height $0$, something immediately above the root has height $1$, and so on. We can then assign a height to the tree itself, which we define to be the least number greater than the height of any element of the tree. For finite trees this is just one greater than the height of its tallest element, but infinite trees may not have a tallest element, so we define $\operatorname{ht}(T)=\sup\{\operatorname{ht}(t)+1\mid t\in T\}$.
For every $\alpha<_{T}\operatorname{ht}(T)$ we define the $\alpha$th level to be the set $T_{\alpha}=\{t\in T\mid\operatorname{ht}(t)=\alpha\}$. So of course $T_{0}$ is all roots of the tree. If $\alpha<_{T}\operatorname{ht}(T)$ then $T(\alpha)$ is the subtree of elements with height less than $\alpha$: $t\in T(\alpha)\leftrightarrow x\in T\wedge\operatorname{ht}(t)<\alpha$.
Mathematics Subject Classification
03E05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new question: numerical method (implicit) for nonlinear pde by roozbe
new question: Harshad Number by pspss
Sep 14
new problem: Geometry by parag
Aug 24
new question: Scheduling Algorithm by ncovella
new question: Scheduling Algorithm by ncovella
Attached Articles
Corrections
add to the defines by Mathprof ✓
please add to the defines list by Mathprof ✓
notation by Mathprof ✓
node by CWoo ✓
Comments
Parents and Children
Hi
The wellordering implies that for two nodes a < d in such a tree...
(i) there's exactly one direct child node b of a, with a < b <= d, and nothing between a and b.
(ii) there DOESN'T NEED to be a direct parent node c of d, with a <= c < d, and nothing in between c and d.
Am I right? If yes, it would be useful to explain that next to the definition...
Regards, Schneemann :)
Re: Parents and Children
Apart of that, I'd like to know the sense of that definition. Why is this a useful definition of a tree?
Re: Parents and Children
I'm not sure how to answer that other than that many theorems use it.
Basically, it takes a useful, intuitive notionthat we can take objects and organize them an a "treelike" fashion, with branches and leaves and nodesand formalizes it in a very general but sensible way. Just about anything that gets called a tree elsewhere in mathematics fits this definition, and conversely, most of methods that work on things called trees work with these objects (or very natural modificationssay, trees of a certain height, or trees with exactly one root).
Re: Parents and Children
I was asking this question because I once came up with a similar definition.. There a partially ordered set (L, <) is
 a "splinter poset", if for each x in L, the halfbounded interval [x, *] = {y in L  x <= y} is a chain.
 an "evolution poset", if for each x in L, the halfbounded interval [*, y] = {x in L  x <= y} is a chain.
Similar to the above, but instead of wellorderings I just use chains. Any further statement about wellordering or discrete ordering would require additional axioms.
There's a "practical" example for that: Imagine a set M of as many travelers as the real numbers (or even more, doesn't matter), all starting in 0, but each with a different destination. If two of them would meet in place x, then they travel together from 0 to x.
Now let G in Pot(M) be the set of all the temporary groups of travelers. Then (G, \subset) is obviously a splinter poset in the above sense (with M as the root), but it's not necessarily a tree in the sense given above.
I came up with the "splinter poset" when I was writing a seminar article for the university, about "connectivity classes" and multiscale connectivities. (if you are interested, you can use google or ask me to tell more about it..)
Re: Parents and Children
Correct me if I'm wrong, but isn't a splinter poset, as you've defined, simply a collection of chains, none of which are related to each other?

"It's John Ashcroft's vision of hell. It's a Tom Waits song."
Simon
Re: Parents and Children
It can, but doesn't need to.
Consider the poset
L = { {1}, {2}, {3}, {4}, {1, 2}, {3, 4}, {1, 2, 3, 4} }
with the subset relation.
(L, \subset) is a splinter poset:
[{1}, *] = {{1}, {1, 2}, {1, 2, 3, 4}} is a chain
(same for the others)
BUT two of these chains can meet somewhere:
[{2}, *] = {{2}, {1, 2}, {1, 2, 3, 4}} is a chain, too, and it meets the above chain in {1, 2}. From there up, they go the same way..
Re: Parents and Children
To compare the different definitions:
(i) Each directed forest in the graphtheoretic sense (with roots the smallest elements) has a transitive closure that is a tree, in the settheoretic sense,
but there are settheoretic trees that are NOT the transitive closure of a graphtheoretic forest.
(ii) Each tree in the settheoretic sense is also an evolution poset, but there are evolution posets that are NOT settheoretic trees.
example: The union of {[0, b]  0<=b<=1} and {{b}  0 < b < 1}, with the superset relation, is an evolution poset, but NOT a settheoretic tree, because the subset
[{0.4}, *] = {{0,4}} union {[0, b]  0.4<=b<=1}
is not wellordered (though it's a chain). Rather, it has the same order as the real numbers' interval [0.4, 1]
Re: Parents and Children
Oh, hi again.
Looks like my reply in the other thread was aimed at a bit too elementary level then, sorry didn't realise <g>.
The usefulness of wellordering usually lies in being able to do transfinite induction. Which is perhaps the most intuitive way to extend induction arguments to uncountably infinite sets. So i expect the tree definition evolved with that in mind.
Let me prune your tree down to a linear set of all closed intervals [0,b] for 0 <= b <= 1, with ancestors subsets, descendants supersets. Suppose we are given
1) Property A is true for node [0,0] i.e. {0}.
2) Property A is true for node X if it's true for all its ancestors
We cannot now conclude every node has property A. For example, if all nodes [0,b] with b <= 0.3 have the property, and others don't, then (1) and (2) still hold.
With a "tree" as defined in the entry, the corresponding (1) and (2) *would* imply A to be true for all its nodes.
regards, marijke
http://web.mat.bham.ac.uk/marijke/
Re: Parents and Children
For "your tree" read "your splinter set", or "evolution set".
regards, marijke
http://web.mat.bham.ac.uk/marijke/
Re: Parents and Children
You can omit premise 1)  the 0 element has no ancestors, so premise 2) applies. For an arbitrary poset, there remains only one necessary and sufficient condition to get the transinduction working. Let's call such posets transinductive.
I use the nonreflexive definition of posets, and the interval notations [*, x] and [*, x) as in my previous posts.
__________________
Thm. Let (L, <) be a poset. The following are equivalent.
(i) Every totally ordered subset S \subseteq L has a minimum.
(ii) If A \subseteq L, such that
for any x in L, if [*, x) \subseteq A, then x in A, Then A = L.
Def. A poset with the above property (i) is called transinductive.
__________________
Proof.
(i) => (ii): Assume A != L, but [*, x) in A always implies that x in A. Have a look at B = LA, and a chain C \subseteq B that's maximal in B.
[*, min(C)) = \emptyset \subseteq A => min(C) in A.
=> contradiction :)
!(i) => !(ii): Assume there's a chain C \subseteq L with no minimum. Let f: (\NN, >) > (C, <) be injective and orderpreserving. Set A = {f(2k)  k in \NN}.
A breaks the rule of (ii).
__________________
I have the strong suspicion that the following is also true.. maybe you find a proof? Guess it's easy, but I'm tired of proving.
__________________
Thm. Let (L, <) be a poset. The following two are equivalent.
(i) (L, <) is a tree in the settheoretic sense.
(ii) (L, <) is a transinductive evolution poset.
__________________
I will use (ii) in my article, if I continue to write .. it's less confusing for a technical audience (computer scientists, electrical engineers) who are used to trees in the graphtheoretic sense.
Re: Parents and Children
> You can omit premise 1)  the 0 element has no ancestors,
> so premise 2) applies.
Yes :)
> I have the strong suspicion that the following is also true..
> maybe you find a proof? Guess it's easy, but I'm tired of proving.
> __________________
>
> Thm. Let (L, <) be a poset. The following two are equivalent.
>
> (i) (L, <) is a tree in the settheoretic sense.
>
> (ii) (L, <) is a transinductive evolution poset.
Thought i had a proof, but it's a bit more tricky. I'll think about it.
regards, marijke
http://web.mat.bham.ac.uk/marijke/
Re: Parents and Children
Oops!
I need to change the definition to "every totally ordered NONEMPTY subset contains a minimum".
_______________________________
Now I can prove the theorem.
(i) => (ii): Let (L,<) be a settheoretic tree, x \in L and C \subseteq L a nonempty chain, with c \in C. Then
 [*, x] is wellordered and thus a chain.
 [*, c] \cap C is a subset of [*, c] and thus has a minimum. This minimum is also the minimum of C.
(ii) => (i): Let (L,<) be a transinductive evolution poset.
=> for each x \in L, [*, x] is a chain.
=> each C \subseteq [*, x] is a chain
=> C has a minimum.
=> [*, x] is a wellordering.
Re: Parents and Children
EDIT:
"(i) Every totally ordered subset S \subseteq L has a minimum."
needs to be replaced by
"(i) Every totally ordered NONEMPTY subset S \subseteq L has a minimum."