Let $x, y$ be finite words over totally ordered alphabet and $<$ denote the lexicographical order, i.e for two not necessarily finite words we say $x < y$ iff one of the following holds

- There are words $u, x^\prime, y^\prime$ and letters $a < b$ such that $x = uax^\prime, y = uby^\prime$
- $y = xu$ for some non-empty word $u$

Then the following are equivalent

- $xy < yx$
- $x^\mathbb{N} < y^\mathbb{N}$, where $x^\mathbb{N}$ denotes infinite word $xxxx\ldots$

$x <^* y$ iff $xy < yx$ is a total order(which we're trying to prove by equivalence)

This new total order is another extension of "weak lexicographical order" where only first condition considered, i.e $x$ and $xu$ are incomparable for non-empty $u$(note that $xy$ and $yx$ always have the same length so we're not using "strong" order). It is naturally arising from the following problem:

Let $x_1, \ldots, x_n$ be finite words on totally ordered alphabet, find $\sigma \in S_n$ minimizing $x_{\sigma(1)}x_{\sigma(2)}\ldots x_{\sigma(n)}$

The solution is to sort $x_i$ with respect to order $<^*$. If the sequence is not sorted according to this order, then there are adjacent elements $x, y$ such that $xy > yx$, by swapping them we'll decrease word which we are minimizing.

But it might be tedious to prove that $<^*$ is transitive, so instead I suggest equivalent definition of $<^*$, that is $x <^* y$ iff $x^\mathbb{N} < y^\mathbb{N}$. Now transitivity is obvious.

But is there elegant and simple proof of equivalence not involving much of casework on $|x| <> |y|$, etc?

1more comment