# what kind of relationship is "is prefix of"?

Consider the "is prefix of" relationship on a set that corresponds to the words of some alphabet. E.g. "ab" is prefix of "abc". This relationship is:

• antisymmetric
• transitive
• reflexive ("ab" is a prefix of "ab")

I understand then that it can be used to define a partially order set.

However, my problem is that the visualization of a partially order set is a Hasse diagram which is a form of DAG. However, I understand the "is prefix of" relationship to be properly resulting in a forest of directed trees. A directed tree is a more specialized data structure than a DAG in that there's at most one path between any two nodes whereas in a DAG you can have more than one. Thinking about the "is prefix of" relationship I don't see how you can get more than one paths between any two words.

E.g. consider the set {"a", "ab", "af", "abc", "abcde", "f", "fg"}

One gets the following forest of trees for the "is prefix of" relationship:

a-->ab-->abc-->abcde
\-->af

f-->fg


I don't see how one could have another path from the "a" node to the "abcde" node without going through the existing "a, ab, abc, abcde" branch. So it appears that the graph is a directed tree and not just a DAG.

So I think that the "is prefix of" relationship must also have some other property in addition to the three noted above (antisymmetric, transitive, reflexive) that ensures that its Hasse diagram is in fact a tree, and not just a DAG. But which property is that?

• I guess the property is that if $a\preceq c$ and $b\preceq c$ then either $a\preceq b$ or $b\preceq a$, but I don't know the name for it.
– user856
May 16 '14 at 14:48
• I've seen this property called "tree-like", but not often enough that I'd consider it standard terminology. May 16 '14 at 15:46
• In Kayne 1994 it's called "locally total": as @Rahul said, it means that the set $\{x : x\le c\}$ is totally ordered for all $c$. I don't think this term is in wide use, though.
– user21467
May 16 '14 at 15:48
• Oh, and I'd suggest including the empty string, so that the Hasse diagram is really a tree and not a forest.
– user21467
May 16 '14 at 15:49
• Consider perusing lotpublications.nl/publish/articles/000400/bookpart.pdf :) Jun 28 '14 at 19:35

The order relation is not a tree or forest in the graph theoretical sense as it contains not only the pairs $(a,ab)$ and $(ab,abc)$, but also $(a,abc)$. Thus, I'd prefer to call it forest order or – if you add the empty string as Steven suggests – tree order. But there are also people around who call the ordered set a tree. There is a difference between the graph theoretic and the order theoretic definitions iff some order ideal (downset) is infinite.
It is easy to prove the tree property if you consider the set of all possible words as a free semigroup, in particular a free monoid, over your alphabet where the neutral element is the empty word. That means all possible words form the base set and your operation $⋅$ is the concatenation. Concatenating a word with the empty word results in the original word. Then the is-prefix-of relation is is the relation: $x≤y :⇔ ∃z:x⋅z = y$. As in the free monoid such an equation has either no solution at all, or the solution is uniqe, the order relation $≤$ is a tree-like order, consequently the induced suborder of any subset is also a forest-like order.