Cantor's isomorphism theorem

In order theory and model theory, branches of mathematics, Cantor's isomorphism theorem states that every two countable dense unbounded linear orders are order-isomorphic. It is named after Georg Cantor, and can be proved by the back-and-forth method sometimes attributed to Cantor, but Cantor's original proof only used the "going forth" half of this method.^[1]

Examples[]

Minkowski's question-mark function provides a concrete isomorphism from rationals to dyadic rationals

Examples of orderings that are isomorphic according to this theorem are the numeric orderings on the rational numbers and dyadic rational numbers, for which an explicit order isomorphism is provided by Minkowski's question-mark function.^[2]

A total order or linear order is dense when every two elements of the order have another element between them. Unboundedness means that the ordering has no minimum or maximum element. For both the rational numbers and the dyadic rationals, there is no minimum or maximum, and an element can be found between any two elements by taking their average. Both of these sets are countable; the countability of the rationals was also observed by Cantor,^[3] and countability of the dyadic rationals follows from the fact that they are a subset of the rationals. Therefore, they are isomorphic to each other, and to every other countable dense linear orders without endpoints.

The integers are countable and have no endpoints, but are not dense: there is no integer between 0 and 1. The real numbers are dense and have no endpoints, but are not countable.^[3] Therefore, Cantor's theorem does not apply to these orderings.

Proofs[]

One proof of Cantor's isomorphism theorem, in some sources called "the standard proof",^[4] uses the back-and-forth method. This proof builds up an isomorphism between any two given orders, using a greedy algorithm, in an ordering given by a countable enumeration of the two orderings. In more detail, the proof maintains two order-isomorphic finite subsets ${\displaystyle A}$ and ${\displaystyle B}$ of the two given orders, initially empty. It repeatedly increases the sizes of ${\displaystyle A}$ and ${\displaystyle B}$ by adding a new element from one order, the first missing element in its enumeration, and matching it with an order-equivalent element of the other order, proven to exist using the density and lack of endpoints of the order. It alternates between the two orders for which one it searches for the first missing element, and which one it uses to find a matching element. Every element of each ordering is eventually matched with an order-equivalent element of the other ordering, so the two orderings are isomorphic.^[5]

Although the back-and-forth method has also been attributed to Cantor, Cantor's original publication of this theorem in 1895–1897 used a different proof.^[5] In an investigation of the history of this theorem by logician Charles L. Silver, the earliest instance of the back-and-forth proof found by Silver was in a 1914 textbook by Felix Hausdorff.^[5]

Instead of building up order-isomorphic subsets ${\displaystyle A}$ and ${\displaystyle B}$ by going "back and forth" between the enumeration for the first order and the enumeration for the second order, Cantor's original proof only uses the "going forth" half of the back-and-forth method.^[1] It repeatedly augments the two finite sets ${\displaystyle A}$ and ${\displaystyle B}$ by adding to ${\displaystyle A}$ the earliest missing element of the first order's enumeration, and adding to ${\displaystyle B}$ the order-equivalent element that is earliest in the second order's enumeration. This naturally finds an equivalence between the first ordering and a subset of the second ordering, and Cantor then argues that the entire second ordering is included.^[1][5]

Model theory[]

Cantor's isomorphism theorem can be expressed in the language of model theory by saying that the first-order theory of unbounded dense linear orders is countably categorical.^[1][6] The rational numbers provide a saturated model of this theory. However, this theory is not categorical for higher cardinalities.^[7]

Related results[]

The same back-and-forth method used to prove Cantor's isomorphism theorem also proves that every two sets of ${\displaystyle k}$ points in an unbounded dense countable linear order can be mapped to each other by an order automorphism. 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. In this sense, the group of symmetries of such an ordering is said to be "highly homogeneous", even though it is not a 2-transitive group (pairs of points cannot be swapped for each other by a symmetry, because that would change their ordering).^[1]

The isomorphism theorem can be extended to systems of any finite or countable number of linearly ordered unbounded sets, each dense in each other. All such systems with the same number of sets are order-isomorphic, under any permutation of their sets. 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 prove that every Dedekind-complete linear ordering that contains a dense subset isomorphic to the rationals must be isomorphic to the real numbers.^[8] Suslin's problem asks whether orders having certain other properties of the order on the real numbers, including unboundedness, density, and the cardinality of the continuum, must be order-isomorphic to the reals; its truth is independent of ZFC.^[9]

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.^[10] Baumgartner's axiom 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. It is consistent with ZFC and the negation of the continuum hypothesis, and implied by the proper forcing axiom,^[11] but independent of Martin's axiom.^[12]

References[]