In mathematics, the Dushnik–Miller theorem is a result in order theory stating that every infinite linear order has a non-identity order embedding into itself.[1] It is named for Ben Dushnik and E. W. Miller, who published this theorem for countable linear orders in 1940. More strongly, they showed that in the countable case there exists an order embedding into a proper subset of the given order; however, they provided examples showing that this strengthening does not always hold for uncountable orders.[2]
In reverse mathematics, the Dushnik–Miller theorem for countable linear orders has the same strength as the arithmetical comprehension axiom (ACA0), one of the "big five" subsystems of second-order arithmetic.[1][3] This result is closely related to the fact that (as Louise Hay and Joseph Rosenstein proved) there exist computable linear orders with no computable non-identity self-embedding.[1][4]
See also
Laver's theorem
References
Hirschfeldt, Denis R. (2014), "10.1 The Dushnik–Miller theorem", Slicing the Truth, Lecture Notes Series of the Institute for Mathematical Sciences, National University of Singapore, 28, World Scientific
Dushnik, Ben; Miller, E. W. (1940), "Concerning similarity transformations of linearly ordered sets", Bulletin of the American Mathematical Society, 46: 322–326, doi:10.1090/S0002-9904-1940-07213-1, MR 0001919
Downey, Rodney G.; Jockusch, Carl; Miller, Joseph S. (2006), "On self-embeddings of computable linear orderings", Annals of Pure and Applied Logic, 138 (1–3): 52–76, doi:10.1016/j.apal.2005.06.008, MR 2183808
Rosenstein, Joseph G. (1982), Linear Orderings, Pure and Applied Mathematics, 98, Academic Press, Theorem 16.49, p. 447, ISBN 0-12-597680-1, MR 0662564
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
