Cantor's isomorphism theorem

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] Contents 1 Statement and examples 2 Proofs 3 Model theory 4 Related results 5 References Statement and examples Minkowski's question-mark function provides a concrete isomorphism from rationals to dyadic rationals Cantor's isomorphism theorem is stated using the following concepts: A linear order or total order is defined by a set of elements and a comparison operation that gives an ordering to each pair of distinct elements and obeys the transitive law. The familiar numeric orderings on the integers, rational numbers, and real numbers are all examples of linear orders. Unboundedness means that the ordering has no minimum or maximum element. All three of these examples are unbounded. The subset of real or rational numbers in the open unit interval (0,1) is similarly unbounded, but the closed unit interval [0,1] is not: it has a minimum element, 0, and a maximum element, 1. An ordering is dense when every pair of elements has another element between them. This is true for the rational numbers and real numbers, where the arithmetic mean of any two numbers belongs to the same set and lies between them, but not for the integers. For instance, there is no other integer between 0 and 1, so the integers are not dense.[2] The integers and rational numbers both form countable sets, but the real numbers do not, by a different result of Cantor, his proof that the real numbers are uncountable.[2] Two linear orders are order-isomorphic when there exists a one-to-one correspondence between them that preserves their ordering. For instance, the integers and the even numbers are order-isomorphic, under a bijection that multiplies each integer by two.

With these definitions in hand, Cantor's isomorphism theorem states that every two unbounded countable dense linear orders are order-isomorphic.[1] Within the rational numbers, certain subsets are also countable, unbounded, and dense. The rational numbers in the open unit interval are an example. Another example is the set of dyadic rational numbers, the numbers that can be expressed as a fraction with an integer numerator and a power of two as the denominator. By Cantor's isomorphism theorem, the dyadic rational numbers are order-isomorphic to the whole set of rational numbers. In this example, an explicit order isomorphism is provided by Minkowski's question-mark function.[3] Another example of a countable unbounded dense linear order is given by the set of real algebraic numbers, the real roots of polynomials with integer coefficients. In this case, they are a superset of the rational numbers, but are again order-isomorphic.[4] It is also possible to apply the theorem to other linear orders whose elements are not defined as numbers.

Proofs One proof of Cantor's isomorphism theorem, in some sources called "the standard proof",[5] 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.[6] 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.[6] 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.[6] 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][6] 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][7] The rational numbers provide a saturated model of this theory. However, this theory is not categorical for higher cardinalities.[8] Related results 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 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 characterize the ordering of the real numbers, an uncountable set. Unlike the rational numbers, the real numbers are Dedekind-complete, meaning that every 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.[9] 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 Zermelo–Fraenkel set theory with the axiom of choice (ZFC).[10] 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.[11] 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,[12] but independent of Martin's axiom.[13] References ^ Jump up to: a b c d e f g Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. (1997), "Rational numbers", Notes on infinite permutation groups, Texts and Readings in Mathematics, vol. 12, Berlin: Springer-Verlag, pp. 77–86, doi:10.1007/978-93-80250-91-5_9, ISBN 81-85931-13-5, MR 1632579 ^ Jump up to: a b Chekmasov, Andrei (October 23, 2019), "Curiosities of linearly ordered sets", Chalkdust ^ Girgensohn, Roland (1996), "Constructing singular functions via Farey fractions", Journal of Mathematical Analysis and Applications, 203 (1): 127–141, doi:10.1006/jmaa.1996.0370, MR 1412484 ^ Bosi, G.; Mehta, G. B. (2002), "Existence of a semicontinuous or continuous utility function: a unified approach and an elementary proof", Journal of Mathematical Economics, 38 (3): 311–328, doi:10.1016/S0304-4068(02)00058-7, MR 1940365; see Remark 3, p. 323 ^ Marzion, Evan (May 16, 2020), "Visualizing Cantor's Theorem on Dense Linear Orders Using Coq", Normal Form ^ Jump up to: a b c d Silver, Charles L. (1994), "Who invented Cantor's back-and-forth argument?", Modern Logic, 4 (1): 74–78, MR 1253680 ^ Büchi, J. Richard; Danhof, Kenneth J. (1973), "Variations on a theme of Cantor in the theory of relational structures", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 19: 411–426, doi:10.1002/malq.19730192604, MR 0337567 ^ Morley, Michael (1965), "Categoricity in power", Transactions of the American Mathematical Society, 114: 514–538, doi:10.2307/1994188, MR 0175782 ^ Jech, Thomas (2003), Set theory, Springer Monographs in Mathematics (3rd millenium ed.), Berlin: Springer-Verlag, Theorem 4.3, p. 38, doi:10.1007/3-540-44761-X, ISBN 3-540-44085-2, MR 1940513 ^ Devlin, Keith J.; Johnsbråten, Håvard (1974), The Souslin problem, Lecture Notes in Mathematics, vol. 405, Berlin & New York: Springer-Verlag, MR 0384542 ^ Sierpiński, Wacław (1932), "Généralisation d'un théorème de Cantor concernant les ensembles ordonnés dénombrables", Fundamenta Mathematicae (in French), 18: 280–284, doi:10.4064/fm-18-1-280-284, Zbl 0004.20502 ^ Baumgartner, James E. (1973), "All {displaystyle aleph _{1}} -dense sets of reals can be isomorphic", Fundamenta Mathematicae, 79 (2): 101–106, doi:10.4064/fm-79-2-101-106, MR 0317934 ^ Avraham, Uri; Shelah, Saharon (1981), "Martin's axiom does not imply that every two {displaystyle aleph _{1}} -dense sets of reals are isomorphic", Israel Journal of Mathematics, 38 (1–2): 161–176, doi:10.1007/BF02761858, MR 0599485 Categories: Order theoryModel theory

Si quieres conocer otros artículos parecidos a Cantor's isomorphism theorem puedes visitar la categoría Model theory.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.


Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información