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.
For instance, Minkowski's question-mark function produces an isomorphism (a one-to-one order-preserving correspondence) between the numerical ordering of the rational numbers and the numerical ordering of the dyadic rationals.
The theorem is named after Georg Cantor, who first published it in 1895, using it to characterize the (uncountable) ordering on the real numbers.
It can be proved by a back-and-forth method that is also sometimes attributed to Cantor but was actually published later, by Felix Hausdorff.
The same back-and-forth method also proves that countable dense unbounded orders are highly symmetric, and can be applied to other kinds of structures.
In terms of model theory, the isomorphism theorem can be expressed by saying that the first-order theory of unbounded dense linear orders is countably categorical, meaning that it has only one countable model, up to logical equivalence.
In this application, the theorem implies that it is sufficient to use intervals of rational numbers to model intervals of time: using irrational numbers for this purpose will not lead to any increase in logical power.
Cantor's isomorphism theorem is stated using the following concepts: With these definitions in hand, Cantor's isomorphism theorem states that every two unbounded countable dense linear orders are order-isomorphic.
In this example, an explicit order isomorphism is provided by Minkowski's question-mark function.
[5] It is also possible to apply the theorem to other linear orders whose elements are not defined as numbers.
[8] 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, his Grundzüge der Mengenlehre.
[9] One way of describing Cantor's isomorphism theorem uses the language of model theory.
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.
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.
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.
-element sets of points is summarized by saying that the group of symmetries of a countable dense linear order is "highly homogeneous".
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.
[1] Cantor used the isomorphism theorem to characterize the ordering of the real numbers, an uncountable set.
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).
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
It states that each two such sets are order-isomorphic, providing in this way another higher-cardinality analogue of Cantor's isomorphism theorem (
[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.
