First-order vs second-order provability - MathOverflow

First-order vs second-order provability

2013-01-24T06:29:54Z

Modular Arithmetic (MA) has the same axioms as first order Peano Arithmetic (PA) except ∀x(Sx≠0) is replaced with ∃x(Sx=0). Let MA2 be the second-order variation, with second-order induction.

Answering to a question by Russell Easterly, Emil Jerabek has shown that

http://mathoverflow.net/questions/119375/even-xor-odd-infinities

∃x(x≠0∧x+x=0) ∨ ∃x(x+x=S0)

is unprovable in MA. There is, however, a proof in MA2.

There are mathematical examples which distinguish first-order and second-order PA, but they are more esoteric (Paris-Harrington Theorem) or less mathematical (the consistency of first-order PA). So the result of Jerabek seems IMHO to be of interest, by providing a simple mathematical proposition and system where the second-order system can prove the proposition but not the first-order.

Are there other simple examples of a first-order theory T and an assertion S where T cannot prove S but second-order T, with second-order induction, can prove S? (Obviously, the interest of Emil's result increases if there are none which aren't "reasonably" equivalent.)

Answer by Asaf Karagila for First-order vs second-order provability

2013-01-24T08:47:22Z

Replacing the induction with the Replacement Schema, it is a nice theorem that if $V_\kappa$ is a model of ZFC with second-order replacement axiom then $\kappa$ is inaccessible.

This is not true for first-order ZFC. In fact for first-order ZFC if there is such $\kappa$ then there is one which has cofinality $\omega$ (the least such cardinal has cofinality $\omega$, and the "next" cardinal with this property - whenever it exists - has cofinality $\omega$ as well).

Answer by Carl Mummert for First-order vs second-order provability

2013-01-24T12:54:15Z

I assume that you mean the second-order system with both second-order induction and the full second-order comprehension scheme. There are many "second order variations" of Peano Arithmetic, with different strengths, so care is required to specify which one is intended. The second-order induction axiom on its own does not allow you to prove any new sentences of first-order arithmetic, compared to Peano Arithmetic, because every model of Peano Arithmetic extends to a model of $\mathsf{ACA}_0$, and that extended model satisfies the second-order induction axiom.

Regardless, there are not going to be any completely elementary principles of number theory that are provable in full second order arithmetic ($Z_2$) but not in PA, because of the well-known phenomenon that all elementary principles are already provable in PA. It is very difficult to find "natural" true mathematical statements that can be expressed in the language of PA but cannot be proved in PA. The Paris--Harrington principle is, in some sense, as good as it gets, which is the main reason the Paris--Harrington theorem is of interest.