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]