7
$\begingroup$

My understanding is that every theorem $\phi$ of $PA$ is true in $N$ because

  1. $N$ is a model for $PA$, $N\models PA$.
  2. By completeness of first order logic, "$PA\vdash\phi$" implies that "if $N\models PA$ then $N\models \phi$".

Hence $\phi$ is true in $N$, $N\models \phi$.

But I was confused upon reading the following from Godel's Theorem: An Incomplete Guide to Its Use and Abuse, p31:

We know that there are consistent theories extending PA that prove false mathematical statement ... So we have no mathematical basis for concluding that (say) the twin prime conjecture is true from the two premises "PA is consistent" and "PA proves the twin prime conjecture".

According to my understanding above, "PA is consistent" and "PA proves the twin prime conjecture" are enough for concluding truth of the conjecture (in the standard model). Theories extending PA may prove false theorem (relative to the standard model), but surely this is not the case for PA?

$\endgroup$
4
  • 1
    $\begingroup$ Line 3, it is not by Completeness. But of course if PA proves the twin prime conjecture then the conjecture is true in $\mathbb{N}$. $\endgroup$ Commented Oct 27, 2013 at 15:02
  • $\begingroup$ I think the idea is that "PA is consistent" extends PA. There are clearly models of PA such that "PA is consistent" does not hold (or by completeness, $PA \vdash$ "PA is consistent"). In wanting to know if the twin prime conjecture is true, you want to know that $PA\vdash TPC$, but knowing that $TPC$ holds in every model that satisfies Con(PA) doesn't tell you if it holds in every model of PA. Or something. Model theory's not my strong suit... $\endgroup$ Commented Oct 27, 2013 at 15:08
  • $\begingroup$ @AndréNicolas, I agree with you, see my answer, but the Completeness Theorem is often stated as “consistent if and only if has a model”, and in this sense (2) is a consequence of this theorem, even though this real content of the theorem is the other implication. $\endgroup$ Commented Oct 27, 2013 at 15:16
  • $\begingroup$ This emperor has no clothes. By which I mean to say that there is a lot of discussion here about something that is obviously wrong as the result of an evident typo in the text. Fix the typo and the problem disappears. $\endgroup$ Commented Oct 30, 2013 at 22:58

4 Answers 4

Reset to default
5
$\begingroup$

First a minor remark: I personally prefer to refer to the implication that you use in (2) as soundness and to reserve the term completeness for the other direction. It takes no Gödel to prove soundness ;)

You are correct in the mathematics before the quotation. I think the point that the author tries to make in that quotation is merely that the truth of theorems of PA is not a consequence of the consistency of PA. He does not question the truth of theorems of PA. Note that you also never invoke the consistency of PA in your argument, but the (stronger, because of soundness) statement that the natural numbers are a model. Indeed, as Franzén points out, if you have a statement $\phi$ that is true in $N$ but not provable in $PA$ then $PA+\neg\phi$ is a consistent theory that proves $\neg\phi$, but this does not make $\neg\phi$ true. Truth is not a consequence of consistency.

And by the way, I think that this is an excellent book.

$\endgroup$
4
  • $\begingroup$ Do you mean "soundness", rather than "correctness"? $\endgroup$ Commented Oct 27, 2013 at 15:15
  • $\begingroup$ @AsafKaragila, thank you, I will correct this. I took my logic class in German ;) (So I was right in claiming that I like to refer to it as correctness, just wrong in doing so.) $\endgroup$ Commented Oct 27, 2013 at 15:18
  • $\begingroup$ Thanks to the good folks of Israeli math enthusiasts (and students) the Hebrew Wikipedia has a lot of Hebrew entries, at least for undergrad level entries, so it's easy to use Wikipedia as some infernal translation engine. $\endgroup$ Commented Oct 27, 2013 at 15:22
  • $\begingroup$ @CarstenSchultz, I think you are right the author is merely making the point that truth is not a consequence of consistency. I confused the terms. Thank you for the answer. I'll keep reading:) $\endgroup$ Commented Oct 27, 2013 at 15:27
1
$\begingroup$

I think it might be helpful to have both paragraphs:

Similarly, when we talk about arithmetical statements being true but undecidable in PA, there is no need to assume that we are introducing any problematic philosophical notions. That the twin prime conjecture may be true although undecidable in PA simply means that it may be the case that there are infinitely many primes $p$ such that $p + 2$ is also a prime, even though this is undecidable in PA. To say that there are true statements of the form “the Diophantine equation $D(x_1, \ldots, x_n) = 0$ has no solution” that are undecidable in PA is to make a purely mathematical statement, not to introduce any philosophically problematic ideas about mathematical truth.

Similar remarks apply to the observations made earlier regarding consistent systems and their solutions of problems. It was emphasized that the mere fact of a consistent system S proving, for example, that there are infinitely many twin primes by no means implies that the twin prime hypothesis is true. Here again it is often thought that such an observation involves dubious metaphysical ideas. But no metaphysics is involved, only ordinary mathematics. We know that there are consistent theories extending PA that prove false mathematical statements—we know this because this fact is itself a mathematical theorem—and so we have no mathematical basis for concluding that the twin prime conjecture is true, which is to say,that there are infinitely many twin primes, from the two premises “PA is consistent” and “PA proves the twin prime hypothesis.”

From the earlier paragraphs in the section, it seems that 'mathematical truth' is essentially truth in $\mathbb{N}$ (or $\mathbb{R}$, or whatever natural universe we're working in). I believe the point here is that PA is not complete, so there are (or, at least, there could be) consistent extensions S of PA which could prove both that PA is consistent and that the twin prime hypothesis is true. But that these extensions could also state, for instance, that some other theorem of $\mathbb{N}$ is false. So the statements 'PA is consistent' and 'PA proves the twin prime hypothesis' formally imply that the twin prime hypothesis is true, but care should be taken as to what consistent system this is being proved in (in particular, what system is proving that PA proves the twin prime hypothesis).

But there's nothing wrong with your reasoning. If $PA \vdash \phi$, then of course $\mathbb{N} \vDash \phi$.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for providing the extra context. The statement taken literally is clearly wrong: from the premise "PA proves the twin prime hypothesis" alone, the soundness of PA is a cast iron mathematical basis for concluding that the twin prime conjecture is true. I think the author meant to say something like the truth of the twin prime conjecture does not follow from the premises "$PA + X$ is consistent" and "$PA + X$ proves the twin prime hypothesis". $\endgroup$ Commented Oct 27, 2013 at 15:41
0
$\begingroup$

I am now convinced from a rereading of the extended extract provided by Salman that this obviously wrong statement is just the result of two typos. If you change the last two occurrences of "PA" in the extract to "S" it all makes perfect sense (S being the name for a consistent extension of PA introduced earlier in the extract).

$\endgroup$
0
$\begingroup$

I believe the quotation is intended to mean: one cannot conclude

the twin prime conjecture is true

from

PA is consistent

and

PA proves the twin prime conjecture

without invoking

$\mathbb N\models\mathrm{PA}$.

By writing this, I am by no means doubting the truth of $\mathbb N\models\mathrm{PA}$ though.

$\endgroup$
5
  • $\begingroup$ If $\mathbb{N} \models PA$, then the truth of "PA proves the twin prime conjecture" implies that the twin prime conjecture is true. The statement that "PA is consistent" is not needed to draw this conclusion, so the coupling of "PA is consistent" and "PA proves the twin prime conjecture" is otiose in this context. Unfortunately Torkel is dead, so we can't check with him, but his argument becomes crystal-clear if we replace "PA" by "S" in these statements. If you are going to suggest a correction, then that is the only one that makes sense. $\endgroup$ Commented Oct 28, 2013 at 21:03
  • $\begingroup$ @Rob: I agree with your first sentence, but it does not contradict what I said, because it invokes $\mathbb N\models\mathrm{PA}$. If one does not invoke $\mathbb N\models\mathrm{PA}$, then even if one has the consistency of PA at hand, one is not able to establish the truth of the twin prime conjecture. $\endgroup$ Commented Oct 29, 2013 at 12:22
  • $\begingroup$ @Rob (cont'd): I have not read the book myself, but I guess the paragraph quoted intends to deal with the unfortunate fact that some people mistakenly think establishing the consistency of a theory helps establish what is true in $\mathbb N$. This mistake probably originates from the strong emphasis on consistency proofs in the history of logic. $\endgroup$ Commented Oct 29, 2013 at 12:26
  • $\begingroup$ I don't disagree with the mathematical content of your answer. When you wrote "I believe the quotation is intended to say", I read that as a suggested correction to the text. I believe that my suggested correction was more likely (it really is obviously a typo). From your response I don't think you meant to suggest a textual correction. $\endgroup$ Commented Oct 29, 2013 at 22:30
  • $\begingroup$ @Rob: Sorry, my wording was ambiguous. Hopefully it looks better now after an additional edit. Thank you for pointing this out. $\endgroup$ Commented Oct 30, 2013 at 10:52

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.