In mathematics, the Dushnik–Miller theorem is a result in
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
stating that every infinite
linear order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexiv ...
has a non-identity
order embedding In order theory, a branch of mathematics, an order embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, order embeddings constitute a notion which is st ...
into itself. It is named for Ben Dushnik and E. W. Miller, who published this theorem for
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural number ...
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.
In
reverse mathematics
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in cont ...
, the Dushnik–Miller theorem for countable linear orders has the same strength as the
arithmetical comprehension axiom (ACA
0), one of the "big five" subsystems of
second-order arithmetic
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics.
A precu ...
. This result is closely related to the fact that (as
Louise Hay
Louise Lynn Hay (October 8, 1926 – August 30, 2017) was an American motivational author and the founder of Hay House. She authored several New Thought self-help books, including the 1984 book '' You Can Heal Your Life''.
Early life and c ...
and Joseph Rosenstein proved) there exist
computable linear orders with no computable non-identity self-embedding.
See also
*
Cantor's isomorphism theorem
*
Laver's theorem Laver's theorem, in order theory, states that order embeddability of countable total orders is a well-quasi-ordering. That is, for every infinite sequence of totally-ordered countable sets, there exists an order embedding from an earlier member of ...
References
{{DEFAULTSORT:Dushnik-Miller theorem
Order theory