The proof-theoretic strength of the Dushnik-Miller Theorem for countable linear orders
Rodney G. Downey, Steffen Lempp · 1999
. We show that the Dushnik-Miller Theorem for countable linear orderings (stating that any countable linear ordering has a nontrivial self-embedding) is equivalent (over recursive comprehension (RCA 0 )) to arithmetic comprehension (ACA 0 ). This paper presents a result in reverse mathematics, a program initiated by H. Friedman and S. Simpson, trying to determine the weakest possible "set-theoretical" axiom (system) to prove a given theorem of "ordinary" mathematics by trying to prove the axiom from the theorem (over a weaker "base system"). The "set-theoretical" axiom systems we will be concerned with are weak subsystems of second-order arithmetic. (We refer to Simpson [Sita] for a detailed exposition of such systems.) In particular, we will use the axiom system RCA 0 of recursive comprehension (with \\Sigma 0 1 -induction) as a base system and exhibit a theorem which is equivalent (over the base system RCA 0 ) to the axiom system ACA 0 of arithmetic comprehension (with \\Sigma 0 1 -...