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 AA, and vice versa.