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.

  • 7
    $\begingroup$ Welcome to MathOverflow. The convention here is to state one's questions in the form of a question (preferably also with polite language), rather than textbook-exercise-style in the form of a command as you have. You can edit your question by clicking on 'edit'. $\endgroup$ – Joel David Hamkins Jun 10 '10 at 12:11
  • 1
    $\begingroup$ Context would help too since the statement to be proven is clearly false. (E.g. Con(PA) is a true Pi_1 statement.) Perhaps there is some restriction on the statement in question. $\endgroup$ – François G. Dorais Jun 10 '10 at 12:16
  • $\begingroup$ The paper that Wang Zirui is referring to is presumably this one: cs.technion.ac.il/~shai/ph.ps.gz, which he links to in his other question. Look at page 3 and footnote 2. I am not sure what they mean, but they do rule out Con(PA) and fixed-point-lemma self-referential statements. It isn't clear (at least upon quick perusal) whether they are making a strict mathematical claim or an empirical observation. $\endgroup$ – Joel David Hamkins Jun 10 '10 at 12:52
  • $\begingroup$ @Joel David Hamkins: Right, I mean Corollary 3 and possibly Lemma 6. They do use Corollary 3 to prove the main result, Corollary 6. What I want is to figure out the proof for Corollary 3 so that I can understand the main result. Many thanks in advance. $\endgroup$ – Zirui Wang Jun 10 '10 at 14:59

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.

  • 1
    $\begingroup$ +1. Of course the theorem only uses the fact that the statement is consistent with PA. That brings out an interesting modality: if S is Pi^0_1 then Con(S) implies S. So for an effective theory T, Con(Con(T)) implies Con(T). $\endgroup$ – Carl Mummert Jun 10 '10 at 13:07
  • $\begingroup$ You are certainly right, but unfortunately it's not what I'm asking. The theorem you guessed is also wrong. Could you please refer to Corollary 3 in Ben-David's paper? I refer to Corollary 3, or rather how it's used to prove Corollary 6. Thanks. $\endgroup$ – Zirui Wang Jun 10 '10 at 15:07
  • 2
    $\begingroup$ The paper explains what is meant by "current approaches", i.e., specifically what they indicate in Lemma 6, the model theoretic approach common to the usual independence proofs (Paris-Harrington-Kanamori-McAloon, Kirby-Paris,...). The key is indeed Lemma 5, for which a reference is given in the paper. Of course, as stated, the corollary is false. With the interpretation of "current approaches" given by Lemma 6, the proof of Corollary 6 is obvious. If Mr. Zirui still has doubts, I would suggest first studying the 3 classical proofs I just mentioned, and then rereading Joel's answer. $\endgroup$ – Andrés E. Caicedo Jun 10 '10 at 15:48

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.