Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:



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?

share|cite|improve this question
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. – Rahul 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. – Andreas Blass 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 :) – Musa Al-hassy Jun 28 '14 at 19:35
up vote 2 down vote accepted

The first thing you should keep in mind is that there is a difference between the Hasse diagram or the corresponding neighbourhood relation and the order itself. The next problematic term is the word “tree”. A tree in graph theory is generally an acyclic graph, which may have some other properties that are fine tuned by the corresponding definition that should be provided.

The relationship you mentioned is a (partial) order (relation) on the given base set. So you don't have to define it. Maybe it helps to know that in order theory partial orders are often called orders and the linearity of an order relation is explicitly spelled out.

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.

BTW. Between the tree-like orders and the order relations there are also some notions of directed orders (those that countain lower/upper bounds) and semilattices.

share|cite|improve this answer

Your Answer


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.