4
$\begingroup$

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.

  • 2
    "Rooted tree" is a term I've seen when you have a partial ordering on nodes along with a least element.2012-09-05

1 Answers 1

2

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.

  • 2
    @MphLee: Ben Gurion University and teaching assistant.2013-05-08