Independence of PA implies independence of PA union all true $\Pi_1$ statements - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T14:54:08Z http://mathoverflow.net/feeds/question/27670 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27670/independence-of-pa-implies-independence-of-pa-union-all-true-pi-1-statements Independence of PA implies independence of PA union all true $\Pi_1$ statements Zirui Wang 2010-06-10T09:13:25Z 2010-12-21T09:36:26Z <p>Prove that if a statement is independent of Peano Arithmetic (PA), then it's also independent of PA$_1$, where PA$_1$ is the union of the set of axioms in PA and the set of all true $\Pi_1$ statements.</p> <p>This claim appears in <a href="http://www.cs.technion.ac.il/~shai/ph.ps.gz" rel="nofollow">this paper</a> as Corollary 3. Ben-David attributes this theorem to "the folklore of proof theory". I want to see a proof.</p> http://mathoverflow.net/questions/27670/independence-of-pa-implies-independence-of-pa-union-all-true-pi-1-statements/27677#27677 Answer by Joel David Hamkins for Independence of PA implies independence of PA union all true $\Pi_1$ statements Joel David Hamkins 2010-06-10T10:52:27Z 2010-06-10T12:43:36Z <p>The claim you have asked us to prove is not true. If PA is consistent, then by the Incompleteness Theorem there are $\Pi_1$ statements that are independent of PA, such as Con(PA), which can be seen to be $\Pi_1$ when expressed in the form "no number is the code of a proof of a contradiction in PA". Thus, if PA is consistent, then Con(PA) is a statement that is independent of PA but provable in $PA_1$, so it is a counterexample to your claim. </p> <p>Perhaps a more striking counterexample would be $\neg\text{Con(PA)}$, which is independent of PA, but refutable in $\text{PA}_1$. More generally, any statement having complexity $\Sigma_1$ or $\Pi_1$ that is independent of PA will be a counterexample to your claim, since such statements are settled by $\text{PA}_1$.</p> <p>Perhaps the folklore result you meant to ask about is the following? </p> <p><b>Theorem.</b> If a $\Pi_1$ statement is independent of PA, then it is true. </p> <p>Proof. If a $\Pi_1$ statement $\sigma$ is independent of PA, then it is true in some model $M\models PA$. The standard model $\mathbb{N}$ is an initial segment of $M$, and since the statement $\sigma$ is $\Pi_1$, it has the form $\sigma = \forall n \varphi(n)$, where $\varphi$ has only bounded quantifiers. Since $\sigma$ holds in $M$, it holds for all standard $n$ in $M$ and hence $\sigma$ is true in the standard model. In other words, it is true. QED</p> <p>Note that the proof that $\sigma$ is true is not a proof in PA, but rather in a theory, such as ZFC, that is able to theorize about models of PA. So another way to view the theorem is as the claim that if ZFC can prove that a given $\Pi_1$ statement is independent of PA, then ZFC can also prove that it is true. </p> http://mathoverflow.net/questions/27670/independence-of-pa-implies-independence-of-pa-union-all-true-pi-1-statements/27709#27709 Answer by Timothy Chow for Independence of PA implies independence of PA union all true $\Pi_1$ statements Timothy Chow 2010-06-10T15:36:38Z 2010-06-10T15:36:38Z <p>As others have pointed out, the assertion is false. What the authors mean by calling it "folklore" is that virtually all the <i>known techniques</i> for proving a "natural" statement (like the Paris-Harrington theorem) independent of PA also prove the stronger result that the statement is independent of PA$_1$. Thus they are heuristically arguing that proving that $P\ne NP$ is independent of PA would require a new technique. Well, stated that way, that's not really news, but I think their ideas are still interesting.</p>