# What kind of order is binary tree ancestry?

Let isAncestor be a relation on binary tree nodes such that isAncestor x y means y can be reached from x in n steps from parent to child, where n may be zero. It is clear from this definition that isAncestor is a partial order. (Two nodes are mutual ancestors if and only if they are identical, and ancestors of ancestors are also ancestors.)

But on a second reflection, isAncestor is not just a partial order. For instance, it has the property forall x y z, isAncestor x z -> isAncestor y z -> ( isAncestor x y \/ isAncestor y x ), which I don't think is common to all partial orders.

Is there a kind of order that precisely designates isAncestor? Since binary trees are extensively studied in CS, I'm guessing there must be a name and a well known set of properties for this kind of relation.

• This might be a better fit for Mathematics. But please don't double-post. If you don't get a satisfactory answer here, you can delete and repost over there or ask a Mod to migrate the question. Sep 10 '14 at 10:35
• Indeed, all ancestors of a given node form a linear order. Also, there is a root, the ancestor of everyone. I presume such an order is a tree, or can be defined as "nested sets". I do not know a special name? Sep 10 '14 at 12:06
• Note that a "precise" notion might not exist. Every relation has infinitely many properties and the class of all isomorphic relations (which share all these properties) might not be very interesting/rich. Common notions are common because they summarise a few frequently useful properties.
– Raphael
Sep 10 '14 at 13:07

Your condition is almost equivalent to the statement that the partial order is a tree.

Consider the following two conditions on a partial order $\ge$:

C1: There exists a top element $r$ (also called "the root") such that $\forall x . r \ge x$.

C2: For all $x,y,z$, $x \ge z \land y \ge z$ implies $x \ge y \lor y \ge x$ (this is your condition).

Notice that every tree satisfies both conditions (i.e., its isAncestor partial order satisfies both of these conditions).

Moreover, I claim that every partial order that satisfies both of these conditions has a Hasse diagram that is a tree.

Why? Well, if C1 is true, then C2 is equivalent to

C3: For all $v$, there is a single unique path from $v$ to the root $r$ in the Hasse diagram of $\ge$.

This is easy to prove by looking at the contrapositive: if there were two incomparable paths from $v$ to the root, then we could find a violation of C2 (let $x,y$ be two incomparable elements, each on one of the paths).

And if C1 and C3 is true, then the Hasse diagram is a tree.

Bottom line: there's no particular reason to expect any special name for your property. Your property almost characterizes trees, once we take into account the correspondence between a partial order and its Hasse diagram (which is a DAG).