Transitivity of concat comparison
We denote the concatenation of $x$ and $y$ by $xy$. Your relation is $x \prec y$ iff $xy &lt; yx$ (where $&lt;$ is the lexicographic order). You want to show that $x \prec y \prec z$ implies $x \prec z$. Suppose therefore that $xy &lt; yx$ and $yz &lt; zy$. Our goal is to show that $xz &lt; zx$.

Say that two strings $s,t$ are incompatible if neither is a prefix of the other. If $s \prec t$ and $s,t$ are incompatible then there is an index on which they differ, and the first such index $i$ satisfies $s_i &lt; t_i$. Conversely, if there exists an index on which $s,t$ differ and the first such index $i$ satisfies $s_i &lt; t_i$ then $s,t$ are incompatible and $s \prec t$.

The proof is by induction on $|x|+|y|+|z|$. We consider several cases.

Case 1. $x,y$ are incompatible, and $y,z$ are incompatible. Let $i$ be the first index on which $x,y$ differ, and let $j$ be the first index on which $y,z$ differ. Then $k = \min(i,j)$ is the minimal index on which $x,z$ differ and $x_k &lt; z_k$, implying $x \prec z$. 

Case 2. $x = yw$. In this case $xy &lt; yx$ implies $ywy &lt; yyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = ywz &lt; yzw &lt; zyw = zx$.

Case 3. $z = yw$. In this case $yz &lt; zy$ implies $yyw &lt; ywy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xyw &lt; yxw &lt; ywx = zx$.

Case 4. $x = zw$. In this case $xy &lt; yx$ implies $zwy &lt; yzw &lt; zyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = zwz &lt; zzw = zx$.

Case 5. $z = xw$. In this case $yz &lt; zy$ implies $xyw &lt; yxw &lt; xwy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xxw &lt; xwx = zx$.

Case 6. $y = xw$ and $x,z$ are incompatible. In this case $xy &lt; yx$ implies $xxw &lt; xwx$, and so $x \prec w$. Moreover, $yz &lt; zy$ implies $xwz &lt; zxw &lt; zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x_i &lt; z_i$. It follows that $x \prec z$.

Case 7. $y = zw$ and $x,z$ are incompatible. In this case $yz &lt; zy$ implies $zwz &lt; zzw$, and so $w \prec z$. Moreover, $xy &lt; yx$ implies $xwz &lt; xzw &lt; zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x_i &lt; z_i$. It follows that $x \prec z$.