4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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
    Commented Jun 10, 2010 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
    Commented Jun 10, 2010 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
    Commented Jun 10, 2010 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
    Commented Jun 10, 2010 at 14:59

2 Answers 2

Reset to default
23
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Jun 10, 2010 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
    Commented Jun 10, 2010 at 15:07
  • 3
    $\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
    Commented Jun 10, 2010 at 15:48
5
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .