The Additive Arithmetic of Linear Orders

Abstract

We present a systematic development of the arithmetic of the class of linear orders under the ordered sum $(LO,+)$ and prove a number of new results. Our approach is based on a Euclidean algorithm for pairs of linear orders that almost additively commute. Among our results: (i.) We generalize and give unified proofs of the main classical theorems for $(LO,+)$, including Lindenbaum's division theorem for $(LO,+)$ and a representation theorem for additively commuting pairs of linear orders due to Aronszajn. (ii.) We solve the following problem, posed by Tarski in 1956: is it true that for every pair of linear orders $A,B$ and quadruple of natural numbers $n,m,k,l\ge 1$, if $nA+mB\cong kB+lA$ then $A+B\cong B+A$? Tarski and Chang showed the answer is yes for certain choices of the coefficients $n,m,k,l$. We show the answer is yes in general. (iii.) We prove the following characterization of the additively commuting pairs in $LO$: $A+B\cong B+A$ if and only if $\omega A$ embeds initially in $\omega B$ and ${\omega }^{\ast }A$ embeds finally in ${\omega }^{\ast }B$, or vice versa. We show this can be viewed as a correctly revised version of a refuted conjecture of Tarski. (iv.) We characterize the commutative semigroups $(S,\oplus )$ that can be represented in $(LO,+)$ and show in particular they are all subsemigroups of naturally totally ordered semigroups in the sense of Clifford.

108 pages