Dushnik–Miller theorem

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]

Not to be confused with Erdős–Dushnik–Miller theorem.

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

References
  1. 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
  2. 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
  3. 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
  4. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.