Fork me on GitHub
Math for the people, by the people.

User login

You are here

Home

tree (set theoretic)

Primary tabs

tree (set theoretic)

In a set theory, a tree is defined to be a set TTT and a relation <T⊆T×TfragmentssubscriptTTT<_{T}\subseteq T\times T such that:

  • <TsubscriptT<_{T} is a partial ordering of TTT

  • For any t∈TtTt\in T, {s∈T∣s<Tt}conditional-setsTsubscriptTst\{s\in T\mid s<_{T}t\} is well-ordered

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 well-ordering requirement prohibits any loops or splits below a node (that is, each node has at most one parent, and therefore at most one grand-parent, and so on). Conversely, if a<TdsubscriptTada<_{T}d then there is exactly one b≤TdsubscriptTbdb\leq_{T}d such that a<TbsubscriptTaba<_{T}b and there is nothing between aaa and bbb. Note that there is no requirement that a node have a parent–there could be an infinitely long branch a1<Ta2<Ta2<T⋯subscriptTsubscripta1subscripta2subscriptTsubscripta2subscriptTnormal-⋯a_{1}<_{T}a_{2}<_{T}a_{2}<_{T}\cdots with each ai<TbsubscriptTsubscriptaiba_{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 well-ordered, we can associate it with an ordinal. We call this the height, and write: ht⁡(t)=o.t.⁡({s∈T∣s<Tt})httfragmentsonormal-.tnormal-.conditional-setsTsubscriptTst\operatorname{ht}(t)=\operatorname{o.t.}(\{s\in T\mid s<_{T}t\}). This all accords with normal usage: a root has height 000, something immediately above the root has height 111, 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 ht⁡(T)=sup⁡{ht⁡(t)+1∣t∈T}htTsupremumconditional-sethtt1tT\operatorname{ht}(T)=\sup\{\operatorname{ht}(t)+1\mid t\in T\}.

For every α<Tht⁡(T)subscriptTαhtT\alpha<_{T}\operatorname{ht}(T) we define the αα\alpha-th level to be the set Tα={t∈T∣ht⁡(t)=α}subscriptTαconditional-settThttαT_{\alpha}=\{t\in T\mid\operatorname{ht}(t)=\alpha\}. So of course T0subscriptT0T_{0} is all roots of the tree. If α<Tht⁡(T)subscriptTαhtT\alpha<_{T}\operatorname{ht}(T) then T⁢(α)TαT(\alpha) is the subtree of elements with height less than αα\alpha: t∈T⁢(α)↔x∈T∧ht⁡(t)<αnormal-↔tTαxThttαt\in T(\alpha)\leftrightarrow x\in T\wedge\operatorname{ht}(t)<\alpha.

We call a tree a κκ\kappa-tree for any cardinal κκ\kappa if |T|=κTκ|T|=\kappa and ht⁡(T)=κhtTκ\operatorname{ht}(T)=\kappa. If κκ\kappa is finite, the only way to do this is to have a single branch of length κκ\kappa.

Defines: 
level,root, height, tree, child, children, parent, ancestor, descendant, $\alpha$-th level, $\kappa$-tree
Related: 
Antichain, Aronszajn, SuslinTree
Synonym: 
tree
Type of Math Object: 
Definition
Major Section: 
Reference

Mathematics Subject Classification

03E05 no label found

Comments

Submitted by Schneemann on Wed, 02/15/2006 - 17:39

Hi
The well-ordering 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 :)

Submitted by Schneemann on Wed, 02/15/2006 - 17:41

Apart of that, I'd like to know the sense of that definition. Why is this a useful definition of a tree?

Submitted by Henry on Wed, 02/15/2006 - 17:56

I'm not sure how to answer that other than that many theorems use it.

Basically, it takes a useful, intuitive notion--that we can take objects and organize them an a "tree-like" fashion, with branches and leaves and nodes--and 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 modifications--say, trees of a certain height, or trees with exactly one root).

Submitted by Schneemann on Wed, 02/15/2006 - 23:29

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 half-bounded interval [x, *] = {y in L | x <= y} is a chain.

- an "evolution poset", if for each x in L, the half-bounded interval [*, y] = {x in L | x <= y} is a chain.

Similar to the above, but instead of well-orderings I just use chains. Any further statement about well-ordering 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..)

Submitted by vernondalhart on Thu, 02/16/2006 - 01:50

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

Submitted by Schneemann on Thu, 02/16/2006 - 01:58

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..

Submitted by Schneemann on Thu, 02/16/2006 - 02:27

To compare the different definitions:

(i) Each directed forest in the graph-theoretic sense (with roots the smallest elements) has a transitive closure that is a tree, in the set-theoretic sense,
but there are set-theoretic trees that are NOT the transitive closure of a graph-theoretic forest.

(ii) Each tree in the set-theoretic sense is also an evolution poset, but there are evolution posets that are NOT set-theoretic 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 set-theoretic tree, because the subset
[{0.4}, *] = {{0,4}} union {[0, b] | 0.4<=b<=1}
is not well-ordered (though it's a chain). Rather, it has the same order as the real numbers' interval [0.4, 1]

Submitted by marijke on Thu, 02/16/2006 - 15:05

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 well-ordering 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/

Submitted by marijke on Thu, 02/16/2006 - 15:06

For "your tree" read "your splinter set", or "evolution set".
--regards, marijke
http://web.mat.bham.ac.uk/marijke/

Submitted by Schneemann on Thu, 02/16/2006 - 16:12

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 trans-inductive.

I use the non-reflexive 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 trans-inductive.
__________________

Proof.

(i) => (ii): Assume A != L, but [*, x) in A always implies that x in A. Have a look at B = L-A, 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 order-preserving. 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 set-theoretic sense.

(ii) (L, <) is a trans-inductive 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 graph-theoretic sense.

Submitted by marijke on Thu, 02/16/2006 - 17:31

> 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 set-theoretic sense.
>
> (ii) (L, <) is a trans-inductive 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/

Submitted by Schneemann on Thu, 02/16/2006 - 20:42

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 set-theoretic tree, x \in L and C \subseteq L a nonempty chain, with c \in C. Then
- [*, x] is well-ordered 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 trans-inductive 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 well-ordering.

Submitted by Schneemann on Thu, 02/16/2006 - 20:44

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."

Subscribe to Comments for "tree (set theoretic)"

Info

Owner: Henry
Added: 2002-07-27 - 00:30
Author(s): Henry

Versions

(v14) by Henry 2013-03-22
Powered By: = + + ♡