Logic Seminar

Please note that the time is PST

There are two natural arithmetic operations on the class of linear orders, the sum + and lexicographic product ×. These operations generalize the sum and product of ordinals.

The arithmetic laws obeyed by the sum were uncovered in the pre-forcing days of set theory and are surprisingly nice. For example, while the right cancellation law A+X≅B+X⇒A≅B is not true for linear orders in general, its failure can be completely characterized: an order X fails to cancel in some such isomorphism if and only if there is a non-empty order R such that R+X≅X. Left cancellation is symmetrically characterized.

Tarski and Aronszajn characterized the commuting pairs of linear orders, i.e. the pairs X and Y such that X+Y≅Y+X. Lindenbaum showed that X+X≅Y+Y implies X≅Y for linear orders X and Y. More generally, we have the finite cancellation law nX≅nY⇒X≅Y. There is even a sense in which the Euclidean algorithm holds for sums of linear orders.

On the other hand, the arithmetic of the lexicographic product is much less well understood. The lone totally general classical result is due to Morel, who characterized the orders X for which the right cancellation law A×X≅B×X⇒A≅B holds. Morel showed that an order X fails to cancel in some such isomorphism if and only if there is a non-singleton order R such that R×X≅X, in analogy with the additive case.

In this talk we consider the question of whether Morel's cancellation theorem is true on the left. We'll show that, while the literal left-sided version of Morel's theorem is false, an appropriately reformulated version is true. Our results suggest that a complete characterization of left cancellation in lexicographic products is possible. We'll also discuss how our work might help in proving multiplicative versions of Tarski and Aronszajn's and Lindenbaum's additive laws.

This is joint work with Eric Paul.