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

User login

tree (set theoretic)

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

03E05 no label found

Comments

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

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

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

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

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

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

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]

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/

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

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.

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

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.

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