Are all the theorems true? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T02:35:56Z http://mathoverflow.net/feeds/question/103711 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103711/are-all-the-theorems-true Are all the theorems true? Alex Gavrilov 2012-08-01T17:49:30Z 2012-08-02T13:46:01Z <p>The title sounds a bit philosophical, but it is<br> about mathematics. Let me explain. </p> <p>Consider a first order theory $T$, which is an extension of Peano Arithmetic. Call this theory "good" if it is consistent and satisfies the following</p> <p><em>Property</em>: For any <code>$\phi\in\Sigma^0_{n+1}$</code> such that <code>$T\vdash \phi$</code> there exists <code>$\psi\in\Pi^0_{n}$</code> such that <code>$T\vdash\psi$</code> and <code>$PA\vdash\psi\to\phi$</code>.</p> <p><em>Question 1</em>. Is $ZFC$ "good"?</p> <p><em>Question 2</em>. The same for $ZFC+something$ (from the lot of proposed new axioms). </p> <p><em>Motivation</em>. </p> <p>If $ZFC$ is not "good" then there (EDIT) may be theorems which can be proved in $ZFC$ despite they are false (in the standard model of PA). I believe that $ZFC$ is "good". However, I would like to know if there is a formal proof. (Admittedly, I don't have a slightest idea what a proof may be like). By the way, "goodness" implies consistency, hence a proper proof requires some new axioms (a large cardinal, perhaps). </p> <p>(EDIT). As Andreas Blass pointed out correctly, even if a theory is not "good" in the above sense, it does not yet follow that some of the theorems are wrong (an obvious fact which I have missed somehow). Still, the question if ZFC is "good" may be of some interest, in my opinion.</p> <p><em>Question 3</em>. Is "goodness" equivalent to consistency? (I doubt this).</p> <p>EDIT: (Clarification). In this question, the theory $T$ is supposed to be "good" and at least as strong as $ZFC$. (Thus, the answer to Question 1 must be yes). The question is, whether <code>$T\vdash Con(T)\to Good(T)$</code>, where $Good(T)$ is a formalization of "goodness"; note that <code>$Good(T)\in \Pi^0_{2}$</code>.</p> <p>P.S. Is there a standard term for "good"? </p> http://mathoverflow.net/questions/103711/are-all-the-theorems-true/103720#103720 Answer by Sridhar Ramesh for Are all the theorems true? Sridhar Ramesh 2012-08-01T19:17:20Z 2012-08-01T19:17:20Z <p>"goodness" appears to be your attempt to describe the property of having existential witnesses (that whenever $T$ proves there exists an $x$ such that $P(x)$, there is also a specific numeral n such that $T$ proves $P(n)$). There are also other related ideas such as $\omega$-consistency. But "goodness" doesn't quite match any of these exactly.</p> <p>Re: question 3: No, "goodness" is not equivalent to consistency. After all, PA plays an unduly special role in the definition of "good", and not such a special role in the idea of "consistent". An example of a theory which is consistent (on the standard assumption that PA is) but not "good" is PA + "PA is inconsistent". This proves the $\Sigma_1$ statement "PA is inconsistent", but no $\Pi_0$ statement entailing this in PA.</p> http://mathoverflow.net/questions/103711/are-all-the-theorems-true/103776#103776 Answer by Emil Jeřábek for Are all the theorems true? Emil Jeřábek 2012-08-02T11:46:26Z 2012-08-02T13:46:01Z <p>$\def\zfc{\mathrm{ZFC}}\def\pa{\mathrm{PA}}$First, there is no consistent recursively axiomatizable theory extending Robinson’s arithmetic which has the property of having existential witnesses as described by Sridhar Ramesh. Let $\pi=\forall x\,\theta(x)$ be a true but $T$-unprovable $\Pi^0_1$ sentence with $\theta$ bounded, which exists by Gödel’s theorem. Then $\exists y\,(\theta(y)\to\forall x\,\theta(x))$ is a tautology, but there is no $n\in\omega$ such that $T\vdash\theta(n)\to\forall x\,\theta(x)$: since $\pi$ is true, $\theta(n)$ is provable in Robinson’s arithmetic, hence $T$ would prove $\pi$.</p> <p>In fact, an iteration of the same idea shows that the only consistent theory with the property of having existential witnesses is the true arithmetic $\mathrm{Th}(\mathbb N)$.</p> <p>The situation with goodness is more complicated: there are good theories, such as any consistent theory axiomatizable over $\pa$ by a set of $\Pi^0_1$ sentences. Nevertheless, neither $\zfc$ nor any its recursively axiomatized extension is good.</p> <p>Let $T=\zfc$, or more generally, let $T$ be any recursively axiomatizable extension of $\pa$ which proves the local $\Sigma^0_1$-reflection principle for $\pa$. Let $\Box_\pa$ denote the provability predicate for $\pa$, and $T_{\Pi^0_1}$ the set of all $\Pi^0_1$ theorems of $T$. By a theorem of Lindström, there exists a $\Pi^0_1$ sentence $\pi$ such that $\pa+\pi$ is a $\Sigma^0_1$-conservative extension of $\pa+T_{\Pi^0_1}$. $T$ proves the reflection principle $\tag{*}\Box_\pa(\neg\pi)\to\neg\pi$ which can be written as a $\Sigma^0_2$ sentence, hence assuming $T$ is good, $(*)$ is provable in $\pa+T_{\Pi^0_1}$, and a fortiori in $\pa+\pi$. But then $\pa+\pi$ proves its own consistency, hence by Gödel’s theorem, it is inconsistent. By $\Sigma^0_1$-conservativity, $\pa+T_{\Pi^0_1}$ is also inconsistent, hence $T$ is inconsistent, contradicting its goodness.</p> <p>Reference:</p> <p>Per Lindström, <a href="http://www.jstor.org/stable/2045318" rel="nofollow"><em>On partially conservative sentences and interpretability</em></a>, Proc. AMS 91 (1984), no. 3, pp. 436–443.</p>