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. 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.

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. 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.

References

| doi-access = free

| title-link = Slicing the Truth