Natural order of rational trees?

Question

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:

        f
      /  \
     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
   \_/  \
         1

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.

Answer 1

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$