Independence of PA implies independence of PA union all true $\Pi_1$ statements - MathOverflow

Independence of PA implies independence of PA union all true $\Pi_1$ statements

2010-06-10T09:13:25Z

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.

This claim appears in this paper as Corollary 3. Ben-David attributes this theorem to "the folklore of proof theory". I want to see a proof.

Answer by Joel David Hamkins for Independence of PA implies independence of PA union all true $\Pi_1$ statements

2010-06-10T10:52:27Z

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.

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$.

Perhaps the folklore result you meant to ask about is the following?

Theorem. If a $\Pi_1$ statement is independent of PA, then it is true.

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

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.

Answer by Timothy Chow for Independence of PA implies independence of PA union all true $\Pi_1$ statements

2010-06-10T15:36:38Z

As others have pointed out, the assertion is false. What the authors mean by calling it "folklore" is that virtually all the known techniques 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.