Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my studies of choice principles, I've encountered the concept of a tree several times. Frustratingly, no two of the sources I've been working with define it in quite the same way!

Notation: Given a set $T$ with a strict partial order (say $\sqsubset$), and given any $x\in T$, let $pr_T(x):=\{y\in T:y\sqsubset x\}$ be the set of predecessors of $x$ in $T$.


Here are the variations of the definition that I've seen so far (in each case, $T$ a non-empty poset):

(i) $T$ is a tree iff for each element $x\in T$, we have that $pr_T(x)$ is linearly ordered.

(ii) $T$ is a tree iff for each element $x\in T$, we have that $pr_T(x)$ is linearly ordered with a least element.

(iii) $T$ is a tree iff for each element $x\in T$, we have that $pr_T(x)$ is well-ordered.

(iv) $T$ is a tree iff for each element $x\in T$, we have that $pr_T(x)$ is finite and linearly ordered.

(v) $T$ is a tree iff $T$ has a least element and for each element $x\in T$, we have that $pr_T(x)$ is linearly ordered.

(vi) $T$ is a tree iff $T$ has a least element and for each element $x\in T$, we have that $pr_T(x)$ is well-ordered.

(vii) $T$ is a tree iff $T$ has a least element and for each element $x\in T$, we have that $pr_T(x)$ is finite and linearly ordered.

Obviously, type (vii) tree $\Rightarrow$ type (vi) tree $\Rightarrow$ type (v) tree $\Rightarrow$ type (i) tree; type (vii) tree $\Rightarrow$ type (iv) tree $\Rightarrow$ type (iii) tree $\Rightarrow$ type (ii) tree $\Rightarrow$ type (i) tree; type (vi) tree $\Rightarrow$ type (iii) tree; type (v) tree $\Rightarrow$ type (ii) tree.

Question #1: Are there any implications that aren't covered by the above?


I'd prefer intuitiveness for these definitions. In particular, I don't like the fact that there needn't be roots (minimal elements) in type (i) trees, and I don't like the fact that type (ii) trees may have multiple components. I've got a notion of the "height" for trees of types (iii), (iv), (vi), and (vii), so there's no need for a different name for trees of type (iv) or (vii). For the rest, I'm considering the following terminology in going forward: (i) dispersing poset, (ii) grove, (iii) neat grove, (v) tree, (vi) neat tree.

Question #2: Has anyone encountered different names for these sorts of structures that are arguably better? I'm fairly happy with all of them--except "neat" and "dispersing poset" (I'd really appreciate any suggestions for better terminology for those two)--but if you've seen better ones, I'd love to hear them.

share|improve this question
2  
"Rooted tree" is a term I've seen when you have a partial ordering on nodes along with a least element. –  Hurkyl Sep 5 '12 at 20:16
add comment

1 Answer 1

up vote 2 down vote accepted

In the context of finite graphs I’d call (vii) a tree and (iv) a forest. In a general set-theoretic context I’d apply these terms to (vi) and (iii), respectively. I’ve not seen the term tree used when the partial order isn’t well-founded, but I might call (v) a tree-like poset, (ii) a forest-like poset, and (i) a rootless forest-like poset. More likely though, if I were actually working with such objects, I’d say outright that I was using tree to refer to (v), forest to refer to (ii), and rootless forest to refer to (i). I could then distinguish the more usual objects as well-founded trees/forests, if I had to distinguish them.

share|improve this answer
    
In the intro class at BGU trees are (i). As a TA I usually remarked that this is probably the broadest definition, and it is not usually the one used. –  Asaf Karagila Apr 19 '13 at 12:37
    
@AsafKaragila what BGU and TA mean? –  MphLee May 8 '13 at 9:31
2  
@MphLee: Ben Gurion University and teaching assistant. –  Brian M. Scott May 8 '13 at 12:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.