37
$\begingroup$

I have been thinking about the difference between provability and truth and think this example can illustrate what I have been wondering about:

We know that Goodstein's theorem (G) is unprovable in Peano arithmetic (PA), yet true in certain extended formal systems. However, it seems like the theorem has a kind of truth that transcends the formal system you use: if you compute the Goodstein sequence for any natural number, it will end at 0 no matter what formal system you use. If you were to consider the system PA $+$ $\lnot G$, wouldn't G still hold in the sense that you could never find a counterexample? Is any of this true, or am I just misunderstanding something?

$\endgroup$
49
$\begingroup$

Good question!

If you were to consider the system PA + $\neg$G, wouldn't G still hold in the sense that you could never find a counterexample?

This gets at an important subtlety here - the issue of models. Any first-order theory like PA, PA+$\neg$G, ZFC, ... has (assuming it's consistent!) many models. Some theories, like PA, have an "intended model," but by the compactness theorem every (interesting) theory will have lots of nonisomorphic models. In particular, in addition to the standard model $(\mathbb{N}; +, \times, 0,1, <)$ of PA, there will also be lots of "nonstandard" models of PA. These models are difficult to describe (for good reason), but very vaguely they're ordered semirings (like $\mathbb{N}$) with "$\mathbb{N}$-ish" properties - in particular, they have a definable notion of exponentiation which behaves the way we're used to and lets the model talk about "finite" sequences of "numbers." The key difference is that a nonstandard model of PA will have elements which are actually infinite.

Such a nonstandard element can constitute an apparent failure of G within that model. If $M$ is a model of PA+$\neg$G, then there is some $m\in M$ which according to $M$ is a counterexample to $G$. However, this $m$ won't actually be a "true" natural number: it won't be $0$, or $1$, or $1+1$, or ...


At this point it might help to get a little more concrete. As I said above, nonstandard models of PA are difficult to visualize. However, if we look at a weaker theory of arithmetic - say, Robinson's Q - things get much better. Q is a very weak theory indeed, and has many easily-describable nonstandard models. Perhaps the nicest of these is what I'll call $\mathcal{P}$, the set of integer-coefficient polynomials in one variable $x$ with positive leading coefficient (okay fine and also the zero polynomial should be included).

$\mathcal{P}$ has a number of bizarre arithmetic properties. For instance, "every number is even or odd" is false in $\mathcal{P}$! The polynomial "$x$" is neither even nor odd, since no element $p$ of $\mathcal{P}$ satisfies either $p+p=x$ or $p+p+1=x$. There are many other examples of such strangeness. (Incidentally, this shows that you need induction to prove that every number is either even or odd! :P)

So what's going on? Well, of course in "reality" (that is, $\mathbb{N}$) every number is even or odd. The problem is that $\mathcal{P}$, while satisfying the axioms of $Q$, has "too many numbers" including some very strange ones which as far as $\mathcal{P}$ is concerned are in fact counterexamples to the statement "every number is either even or odd." So this shows that the statement "every number is either even or odd" can't be proved from $Q$ alone.

Exactly the same thing is going on with Goodstein's theorem G; it's just that the theory in question being PA, the "bad" models are much harder to visualize and so the independence is more mysterious.

$\endgroup$
  • $\begingroup$ So I looked up Goodstein's theorem. Very interesting. But regarding proving it in PA: Is it clear (and/or true) that it's even possible to "state" it in the language of first-order PA? $\endgroup$ – David C. Ullrich Jan 19 '18 at 2:36
  • $\begingroup$ @DavidC.Ullrich Sure: "For every $n$, there is a $k$ which codes a finite sequence beginning with $n$, ending with $1$, and satisfying the 'Goodstein rule.'" You only run into problems if you're not talking about finite sequences. $\endgroup$ – Noah Schweber Jan 19 '18 at 2:40
  • $\begingroup$ Ok. Ah - I was stuck on how to say "sequence". You don't, you define that "coding" and say there exists a $k$ which codes etc. Shoulda realized, duh, finite sequences "are" just natural numbers... $\endgroup$ – David C. Ullrich Jan 19 '18 at 2:43
  • 2
    $\begingroup$ @SamMayo It's an informal term. There are very few times in fact that it makes sense to speak of an intended model of a theory. But some theories, like PA, are quite clearly designed with a single model in mind. Now, there are absolutely precise features which make $\mathbb{N}$ stand out as a model of PA - e.g. it's the unique model of PA (up to isomorphism) which has a homomorphism into every other model - but that's a separate issue. $\endgroup$ – Noah Schweber Jan 19 '18 at 3:27
  • 1
    $\begingroup$ @SamMayo The usual process is to start with a model and then try to find a set of axioms that describes it. People had been working with positive whole numbers for millennia before Peano came along. So, the intended model is the one you want to describe. $\endgroup$ – Stig Hemmer Jan 19 '18 at 10:07
15
$\begingroup$

It's important not to conflate the system PA with the natural numbers themselves. There are other "nonstandard" models of PA: sets other than the natural numbers that admit definitions of $\{S,+,×\}$ which satisfy all the axioms of PA. (In particular, the Löwenheim–Skolem theorem implies that you can even find uncountable sets that admit such definitions.)

Any nonstandard model of PA would have to contain an isomorphic copy of the "actual" natural numbers, and that copy of the natural numbers would have to satisfy Goodstein's Theorem for the reason you stated, but the "nonstandard" elements of the model might have nonconvergent Goodstein sequences.

$\endgroup$
  • 2
    $\begingroup$ It should be kept in mind that the belief in "the natural numbers" (with a definite article) is in the category of faith. See this 2017 publication in Real Analysis Exchange for some details. $\endgroup$ – Mikhail Katz Jan 19 '18 at 7:52
  • 1
    $\begingroup$ @MikhailKatz Or at least Platonism. $\endgroup$ – Shufflepants Jan 19 '18 at 15:57

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.