Dushnik–Miller theorem
In mathematics, the Dushnik–Miller theorem is a result in order theory stating that every countably infinite linear order has a non-identity order embedding into itself.[1] It is named for Ben Dushnik and E. W. Miller, who proved this result in a paper of 1940; in the same paper, they showed that the statement does not always hold for uncountable linear orders, using the axiom of choice to build a suborder of the real line of cardinality continuum with no non-identity order embeddings into itself.[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.[3][4]
See also
[edit]References
[edit]- ^ a b 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
- ^ Dushnik, Ben; Miller, E. W. (1940), "Concerning similarity transformations of linearly ordered sets", Bulletin of the American Mathematical Society, 46 (4): 322–326, doi:10.1090/S0002-9904-1940-07213-1, MR 0001919
- ^ a b 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, vol. 28, World Scientific
- ^ Rosenstein, Joseph G. (1982), Linear Orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Theorem 16.49, p. 447, ISBN 0-12-597680-1, MR 0662564