# Natural order of rational trees?

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.

-
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). –  j4n bur53 Oct 10 '12 at 23:55

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$