20
$\begingroup$

Specifically, the Paris-Harrington theorem.

In what sense is it true? True in Peano arithmetic but not provable in Peano arithmetic, or true in some other sense?

$\endgroup$
1
  • 3
    $\begingroup$ Next time, you should wait a couple of hours before accepting any answer... $\endgroup$
    – Asaf Karagila
    Oct 13, 2012 at 21:37

5 Answers 5

21
$\begingroup$

Peano Arithmetic is a particular proof system for reasoning about the natural numbers. As such it does not make sense to speak about something being "true in PA" -- there is only "provable in PA", "disprovable in PA", and "independent of PA".

When we speak of "truth" it must be with respect to some particular model. In the case of arithmetic statements, the model we always speak about unless something else is explicitly specified is the actual (Platonic) natural numbers. Virtually all mathematicians expect these numbers to "exist" (in whichever philosophical sense you prefer mathematical objects to exist in) independently of any formal system for reasoning about them, and the great majority expect all statements about them to have objective (but not necessarily knowable) truth values.

We're very sure that everything that is "provable in PA" is also "true about the natural numbers", but the converse does not hold: There exist sentences that are "true about the actual natural numbers" but not "provable in PA". This was famously proved by Gödel -- actually he gave a (formalizable, with a few additional technical assumptions) proof that a particular sentence was neither "provable in PA" nor "disprovable in PA", and a convincing (but not strictly formalizable) argument that this sentence is true about the actual natural numbers.

Paris-Harrington shows that another particular sentence is of this kind: not provable in PA, yet true about the actual natural numbers.

$\endgroup$
5
  • 2
    $\begingroup$ You might mention that, regardless of how convincing is the argument that the Gödel sentence $G$ is true, the proof that it is not disprovable in PA also shows that $\lnot G$ is not provable in PA, and so one of $G$ and $\lnot G$ must be true but not provable. So it is possible to be convinced that there a sentence tha tis true but not provable in PA, without being convinced that $G$ is true. $\endgroup$
    – MJD
    Oct 13, 2012 at 20:37
  • 2
    $\begingroup$ It should be noted that the statement which Paris-harrington proves undecidable (unprovable, yet true in some models) was, the first non-synthetic statement for which this was shown. The statements which Gödels proved unprovable are very synthetic, and unlikely to occur as actual number-theoretic questions. The strengthened Ramsey theorem that Paris-Harrington proved undecidable, OTOH, is argueable of some pratical interest apart from the fact that it's undecidable in PA. $\endgroup$
    – fgp
    Oct 13, 2012 at 20:41
  • 1
    $\begingroup$ Also there could be "provable and disprovable in PA"? $\endgroup$
    – hjg
    Oct 14, 2012 at 0:04
  • $\begingroup$ @hjg: that would mean that PA is inconsistent. PA is widely believed to be consistent, and it can also be proven consistent on the basis of various weak assumptions (see for example en.wikipedia.org/wiki/Gentzen's_consistency_proof ), but of course those assumptions might themselves be inconsistent.... Certain ultrafinitists might not believe that PA is consistent. $\endgroup$ Oct 14, 2012 at 7:20
  • $\begingroup$ @Henning: this question is related to your answer: math.stackexchange.com/q/590378/630 $\endgroup$ Dec 3, 2013 at 12:16
16
$\begingroup$

The Paris-Harrington theorem is actually the theorem that states that the strengthened [finite] Ramsey theorem is unprovable in first-order Peano Arithmetic.

However, since the Ramsey theorem is provable in second-order arithmetic, and therefore true in the standard model of Peano arithmetic, we can say that the theorem is true in a very deep and concrete sense.

Generally speaking, when we say a statement about the integer is true we mean that it is true in the standard model, which is the model of second-order Peano arithmetic, and it is all the numbers which can be generated by finitely many iteration of the successor function from zero. (Non-standard models of first-order PA exist, and there are non-standard integers which cannot be generated by finite iterations of the successor from zero.)

You may also want to read this thread about the difference between truth and provability.

$\endgroup$
12
  • $\begingroup$ So if something is provable in second-order arithmetic, then it is true in Peano arithmetic? $\endgroup$
    – fhyve
    Oct 13, 2012 at 20:12
  • 1
    $\begingroup$ @fhyve It is then true in the standard model of peano arithmetic (if it's expression in first-order language, that is). It is not true in peano arithmetic in general (which is a set of axioms, not a particular model), i.e. there are models of peano arithmetic where it's false. $\endgroup$
    – fgp
    Oct 13, 2012 at 20:16
  • 3
    $\begingroup$ @fhyve: The second-order theory of Peano arithmetic has exactly one model up-to isomorphism (unlike the first-order theory which has many non-isomorphic countable models). This model is known as the standard model of PA, and it is [trivially] a model for first-order PA. The strengthened finite Ramsey theorem can be stated in first-order PA, but cannot be proven using it. It can be proved using second-order so it is true in the model of second-order PA, which means it is true in the standard model of first-order PA as well. $\endgroup$
    – Asaf Karagila
    Oct 13, 2012 at 20:16
  • 1
    $\begingroup$ So I am confusing formal theory with model when I say "something is true in peano arithmetic"? $\endgroup$
    – fhyve
    Oct 13, 2012 at 20:21
  • 2
    $\begingroup$ @fhyve: Yes; see my answer. $\endgroup$ Oct 13, 2012 at 20:22
16
+100
$\begingroup$

The other answers are excellent, but I would like to point out that Peano arithmetic is a particularly bad first example for understanding the distinction between truth and provability because

  • you have an intuitive notion of what the word "true" means that is getting in the way, and
  • there are, roughly speaking, two levels of mathematics going on and it is easy to confuse them.

So let's pick a better example where there's no possibility of confusion: the first-order theory of groups. I'm not going to spell out in detail what this is; consider it an exercise to write it down in full. After writing down the language of groups, write down the group theory axioms.

"Provable" has an unambiguous meaning here: it means "provable from the axioms of group theory." By the completeness theorem, this is equivalent to "true for all groups."

"True" is meaningless here unless you take it to mean "true for all groups," which is not the sense in which the Paris-Harrington theorem is true. What is meaningful is to say that a statement in the language of groups is true in a particular model: for example, the statement

$$\exists g : g \neq e, g^2 = e$$

is true in a group $G$ precisely when that group has a nontrivial element of order $2$.

The difference between group theory and first-order Peano arithmetic is that when it comes to Peano arithmetic, mathematicians have a special model that they really like, namely the "actual natural numbers," and "true" in this context means "true of this special model." As Asaf says, one way to define this model is as the unique model of second-order Peano arithmetic; however, first-order Peano arithmetic does not have a unique model (e.g. by upward Löwenheim-Skolem).

This is very different from the situation with group theory; nobody has a group $G$ that they like so much that they would define "true" to mean "true of $G$"!

As a final remark, note that by the completeness theorem, "true of the actual natural numbers but not provable" is equivalent to "true of the actual natural numbers but false for some other model of Peano arithmetic." This may seem like a strange state of affairs, but the analogous situation in group theory ("true of some group but false of some other group") is not so strange.

$\endgroup$
4
  • 1
    $\begingroup$ That last sentence was especially helpful in light of the other comments. Thanks $\endgroup$
    – fhyve
    Oct 13, 2012 at 20:46
  • $\begingroup$ Actually PA is a good example, once you understand what is a model of a theory. This is because there is exactly one model of second-order PA means that we can treat that as the standard model of first-order PA, and define a statement as "true" if it is true in that model. $\endgroup$
    – Asaf Karagila
    Oct 13, 2012 at 20:50
  • 6
    $\begingroup$ @Asaf: but my point is precisely that PA is a bad example if you don't understand what a model of a theory is and are trying to learn. Nonstandard models of Peano arithmetic look like this bizarre thing instead of a general feature of first-order logic, and thinking about other first-order theories first seems to me to be a much better way of coming to terms with this idea. $\endgroup$ Oct 13, 2012 at 20:53
  • 1
    $\begingroup$ I do agree that for understanding the difference between semantic and syntax, and so on, models of PA are messy. Yes, group theory makes a much nicer example (or my preferred example: field theory and the number of roots for $x^3-2$). However I strongly agree with Carl in the comments to fgp's answer. When talking about PA, we have a concrete meaning when we say that a statement is "true". $\endgroup$
    – Asaf Karagila
    Oct 13, 2012 at 21:06
12
$\begingroup$

You seem to be confused about the meaning of true when it comes to peano arithmetic. Peano arithmetic usually refers to a particular set of axions about the natural numbers, formalized in first-order predicate logic.

If you have a statement $A$ and a set of axioms $T$ it can be that

  1. $A$ is provable in $T$. $A$ is then true in every model of $T$ (A model is a particular implementation of a set of axioms if you will - it assigns actual values to all constant symbols which occur in the axioms, actual functions to all functions which occur in the axioms, and so on).
  2. $A$ is true in every model of $T$. In first-order predicate logic this implies that $A$ is provable in $T$. (Note that this is not the case in second-order predicate logic!). Some people might abbreviate this as "$A$ is true in $T$", but that may be missunderstood as "$A$ is true in the standard model of $T$", so this abbreviation should be avoided.
  3. $A$ is true in a particular model of $T$. This implies nothing about the truth of $A$ in other models, and nothing about whether $A$ is provable. It does imply, however, that the opposite of $A$ cannot be profable, otherwise that particular model would have to satisfy $A$ and its opposite.
  4. $A$ contradicts $T$. This is the same as $T$ proving the opposite of $A$, and obivously no model can then fulfill $A$, since all fulfill the opposite of $A$.

In the case of PA, people might also say "True over the integers" or simply "true" instead of "True over the standard model of PA". Especially because PA is not the only axiomatization of the integers.

The generalized Ramsey theorem (sometimes called Paris-Harrington Principle, btw) is not provable in PA, but it is true in the stanard model of PA, i.e. in the usual integers. We know that because it is provable in second-order arithmetic, i.e. a second-order axiomatization of the integers.

$\endgroup$
10
  • $\begingroup$ So it is kind of like how if you say something is true about a field, then it is true about the field of real numbers? And as an analogy in this case, a field is like peano arithmetic and the field of real numbers is like a model in that it is a specific instantiation of a field? $\endgroup$
    – fhyve
    Oct 13, 2012 at 20:37
  • $\begingroup$ @fhyve Yes, exactly! $\endgroup$
    – fgp
    Oct 13, 2012 at 20:43
  • 1
    $\begingroup$ You are somewhat missing the point, though. Since PA has a standard model, we can say that something is true if it holds in the standard model. $\endgroup$
    – Asaf Karagila
    Oct 13, 2012 at 20:51
  • $\begingroup$ @AsafKaragila But we wouldn't say "True over PA" if we mean "True in the standard model of PA". Or at least I'd find that quite confusing. The point I was trying to make was precisly that people sometimes do say "True over PA" when the actually mean "Provable over PA" or equivalently "True over all models of PA" and not "True over the standard integers". And, while that may be a bit confusing, it's not wrong - Gödel's completeness theorem guarantees that. $\endgroup$
    – fgp
    Oct 13, 2012 at 20:59
  • 8
    $\begingroup$ @fgp: that is correct in a sense, but also we don't usually say "true over PA"; that is not a phrase I would use. The question does say "true in PA" but that is a sign that the asker has not yet figured out how to ask the question correctly. When they read "true but not provable in PA" they appear to mistakenly think this means "true in PA but not provable in PA" when it really means "true in $\mathbb{N}$ but not provable in PA". $\endgroup$ Oct 13, 2012 at 21:04
0
$\begingroup$

Note that (according to Wikipedia) the proof of the Paris-Harrington theorem goes by assuming it is true in Peano arithmetic and showing this can prove Peano is consistent (within Peano).

Because Gödel has shown this is not possible, it must not be possible to prove the theorem in Peano.

So as far as understanding it, you can fall back on Gödel: he showed there are statements in a formal theory that cannot be proved (or disproved) by that theory but are true in a formal theory with more axioms. This is one of those statements for Peano.

$\endgroup$

You must log in to answer this question.

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