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.

What would be a natural order of rational trees? Rational trees arise naturally from free algebras if we view a term as a finite tree. For example the term f(a,g(b,c)) could be viewed as the following finite tree:

      /  \
     a    g
         / \
        b   c

Rational trees are now the terms that emerge when we look at a diagram as above and drop the restriction that it must be a finite tree. So if we allow graphs. Here is an example of a rational tree:

      / \
     /   s
    /   / \
   /   s   0
   \_/  \

Since its possible to lexically order finite trees, can we also put rational trees into a strict total order? What is a natural one that is closest to the lexical order?

Best Regards

P.S.: The above rational tree is a counter example that shows that a lexical order is not always possible, communicated by Mats Carlsson. Take A=s(B,0), B=s(A,1), then the assumption A<B leads to B>A, and vice versa.

share|improve this question
Are the roots of these trees distinguished? Say I write a tree with root r and children c1, c2… as [r, c1, c2, …]. Then your finite tree above is [f, a, [g, b, c]], and your infinite tree is T = [s, [s, T, 1], 0]. Is your infinite tree the same as the tree T = [s, [s, T ,0], 1], or is it a different infinite tree? –  MJD Oct 10 '12 at 23:05
Yes, roots are important. T = s(s(T,1),0) is not the same as S = s(s(S,0),1). –  Cookie Monster Oct 10 '12 at 23:55

1 Answer 1

up vote 1 down vote accepted

Since lexicographic order is looking for a difference with a depth-first search (which can look arbitrarily far down one branch without going into any of the others), why not look for a difference with a breadth-first search ?

More precisely, define $A_n$, the $n$th truncation of a term $A$ as only the first $(n+1)$ levels in the tree. On your counterexample with $A = s(s(A,1),0)$, the $0$th truncation of $A$ is $s$, the $1$st truncation is $s(s,0)$, then $s(s(s,1),0)$ etc. Put any orders $<_n$ you want on the sets of $n$ levelled trees (for example, lexicographical), then define $A' = (A_0,A_1,A_2,\ldots)$ and define the order by $A < B \iff A' <_{lex} B' \iff \exists n. (\forall m. m<n \implies A_m = B_m) \land (A_n <_n B_n)$

If $A$ and $B$ are the same at every level, I think you would agree that they are the same trees, so this order is total, and transitivity follows from that of $<_{lex}$ and $<_n$

share|improve this answer
Is it decidable for rational trees? –  Cookie Monster Oct 12 '12 at 16:27
If two trees are distincts then there is a level that distinguishes them, and so you don't need to look infinitely far down the tree to decide how they are ordered. You just need to check level after level until you find the difference. So it boils down to deciding equality among rational trees –  mercio Oct 12 '12 at 17:26

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.