First-order vs second-order provability - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T13:30:15Z http://mathoverflow.net/feeds/question/119730 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119730/first-order-vs-second-order-provability First-order vs second-order provability abo 2013-01-24T06:29:54Z 2013-01-24T12:54:15Z <p>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. </p> <p>Answering to a question by Russell Easterly, Emil Jerabek has shown that </p> <p><a href="http://mathoverflow.net/questions/119375/even-xor-odd-infinities" rel="nofollow">http://mathoverflow.net/questions/119375/even-xor-odd-infinities</a></p> <p>∃x(x≠0∧x+x=0) ∨ ∃x(x+x=S0)</p> <p>is unprovable in MA. There is, however, a proof in MA2.</p> <p>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.</p> <p>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.)</p> http://mathoverflow.net/questions/119730/first-order-vs-second-order-provability/119734#119734 Answer by Asaf Karagila for First-order vs second-order provability Asaf Karagila 2013-01-24T08:47:22Z 2013-01-24T08:47:22Z <p>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. </p> <p>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).</p> http://mathoverflow.net/questions/119730/first-order-vs-second-order-provability/119754#119754 Answer by Carl Mummert for First-order vs second-order provability Carl Mummert 2013-01-24T12:54:15Z 2013-01-24T12:54:15Z <p>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. </p> <p>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. </p>