Cantor's isomorphism theorem

One way of describing Cantor's isomorphism theorem uses the language of model theory. The first-order theory of unbounded dense linear orders consists of sentences in mathematical logic concerning variables that represent the elements of an order, with a binary relation used as the comparison operation of the ordering. Here, a sentence means a well-formed formula that has no free variables. These sentences include both axioms, formulating in logical terms the requirements of a dense linear order, and all other sentences that can be proven as logical consequences from those axioms. The axioms of this system can be expressed as:^[10][11]

Axiom	Explanation
${\displaystyle \forall a\,{\bigl (}\lnot (a<a){\bigr )}}$	Comparison is irreflexive: no element is less than itself.
${\displaystyle \forall a\,\forall b\,(a=b\vee a<b\vee b<a)}$	Comparison is connected or total, meaning every two distinct elements are comparable.
${\displaystyle \forall a\,\forall b\,\forall c\,{\bigl (}(a<b\wedge b<c)\Rightarrow a<c{\bigr )}}$	Comparison is transitive: each triple of elements is consistently ordered.
${\displaystyle \forall a\,\exists b\,(b<a)}$	There is no lower bound; every element ${\displaystyle a}$ has a smaller element ${\displaystyle b}$.
${\displaystyle \forall a\,\exists b\,(a<b)}$	There is no upper bound; every element ${\displaystyle a}$ has a larger element ${\displaystyle b}$.
${\displaystyle \forall a\,\forall b\,{\bigl (}a<b\Rightarrow \exists c\,(a<c\wedge c<b){\bigr )}}$	The order is dense: every two elements ${\displaystyle a}$ and ${\displaystyle b}$ have an element ${\displaystyle c}$ between them.

A model of this theory is any system of elements and a comparison relation that obeys all of the axioms; it is a countable model when the system of elements forms a countable set. For instance, the usual comparison relation on the rational numbers is a countable model of this theory. Cantor's isomorphism theorem can be expressed by saying that the first-order theory of unbounded dense linear orders is countably categorical: it has only one countable model, up to logical equivalence.^[1][12] However, it is not categorical for higher cardinalities: for any higher cardinality, there are multiple inequivalent dense unbounded linear orders with the same cardinality.^[13]

A method of quantifier elimination in the first-order theory of unbounded dense linear orders can be used to prove that it is a complete theory. This means that every logical sentence in the language of this theory is either a theorem, that is, provable as a logical consequence of the axioms, or the negation of a theorem. This is closely related to being categorical (a sentence is a theorem if it is true of the unique countable model; see the Łoś–Vaught test) but there can exist multiple distinct models that have the same complete theory. In particular, both the ordering on the rational numbers and the ordering on the real numbers are models of the same theory, even though they are different models. Quantifier elimination can also be used in an algorithm for deciding whether a given sentence is a theorem.^[11]

The same back-and-forth method used to prove Cantor's isomorphism theorem also proves that countable dense linear orders are highly symmetric. Their symmetries are called order automorphisms, and consist of order-preserving bijections from the whole linear order to itself. By the back-and-forth method, every countable dense linear order has order automorphisms that map any set of ${\displaystyle k}$ points to any other set of ${\displaystyle k}$ points. This can also be proven directly for the ordering on the rationals, by constructing a piecewise linear order automorphism with breakpoints at the ${\displaystyle k}$ given points. This equivalence of all ${\displaystyle k}$-element sets of points is summarized by saying that the group of symmetries of a countable dense linear order is "highly homogeneous". However, there is no order automorphism that maps an ordered pair of points to its reverse, so these symmetries do not form a 2-transitive group.^[1]

The isomorphism theorem can be extended to colorings of an unbounded dense countable linear ordering, with a finite or countable set of colors, such that each color is dense, in the sense that a point of that color exists between any other two points of the whole ordering. The subsets of points with each color partition the order into a family of unbounded dense countable linear orderings. Any partition of an unbounded dense countable linear orderings into subsets, with the property that each subset is unbounded (within the whole set, not just in itself) and dense (again, within the whole set) comes from a coloring in this way. Each two colorings with the same number of colors are order-isomorphic, under any permutation of their colors. Bhattacharjee et al. (1997) give as an example the partition of the rational numbers into the dyadic rationals and their complement; these two sets are dense in each other, and their union has an order isomorphism to any other pair of unbounded linear orders that are countable and dense in each other. Unlike Cantor's isomorphism theorem, the proof needs the full back-and-forth argument, and not just the "going forth" argument.^[1]

Cantor used the isomorphism theorem to characterize the ordering of the real numbers, an uncountable set. Unlike the rational numbers, the real numbers are Dedekind-complete, meaning that every nonempty subset of the reals that has a finite upper bound has a real least upper bound. They contain the rational numbers, which are dense in the real numbers. By applying the isomorphism theorem, Cantor proved that whenever a linear ordering has the same properties of being Dedekind-complete and containing a countable dense unbounded subset, it must be order-isomorphic to the real numbers.^[14] Suslin's problem asks whether orders having certain other properties of the order on the real numbers, including unboundedness, density, and completeness, must be order-isomorphic to the reals; the truth of this statement is independent of Zermelo–Fraenkel set theory with the axiom of choice (ZFC).^[15]

Although uncountable unbounded dense orderings may not be order-isomorphic, it follows from the back-and-forth method that any two such orderings are elementarily equivalent.^[7][16] Another consequence of Cantor's proof is that every finite or countable linear order can be embedded into the rationals, or into any unbounded dense ordering. Calling this a "well known" result of Cantor, Wacław Sierpiński proved an analogous result for higher cardinality: assuming the continuum hypothesis, there exists a linear ordering of cardinality ${\displaystyle \aleph _{1}}$ into which all other linear orderings of cardinality ${\displaystyle \aleph _{1}}$ can be embedded.^[17] Baumgartner's axiom, formulated by James Earl Baumgartner in 1973 to study the continuum hypothesis, concerns ${\displaystyle \aleph _{1}}$-dense sets of real numbers, unbounded sets with the property that every two elements are separated by exactly ${\displaystyle \aleph _{1}}$ other elements. It states that each two such sets are order-isomorphic, providing in this way another higher-cardinality analogue of Cantor's isomorphism theorem (${\displaystyle \aleph _{1}}$ is defined as the cardinality of the set of all countable ordinals). Baumgartner's axiom is consistent with ZFC and the negation of the continuum hypothesis, and implied by the proper forcing axiom,^[18] but independent of Martin's axiom.^[19]

In temporal logic, various formalizations of the concept of an interval of time can be shown to be equivalent to defining an interval by a pair of distinct elements of a dense unbounded linear order. This connection implies that these theories are also countably categorical, and can be uniquely modeled by intervals of rational numbers.^[20][21]

Sierpiński's theorem stating that any two countable metric spaces without isolated points are homeomorphic can be seen as a topological analogue of Cantor's isomorphism theorem, and can be proved using a similar back-and-forth argument.