# tree (set theoretic)

## Primary tabs

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

## Mathematics Subject Classification

### Parents and Children

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 :)

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

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

### 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 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]

### 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 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/

### Re: Parents and Children

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

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

### 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 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/

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

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