# Can Goodstein's theorem be false in some model of Peano arithmetic? How?

I read that Goodstein's theorem is not provable in Peano arithmetic, but is provable in ZFC.

Now, using Godel's completeness theorem, we can say that, since Goodstein's theorem is not provable in Peano arithmetic, there exists a model of Peano arithmetic where the Goodstein theorem is true, and a model where the Goodstein theorem is false. ZFC is an example of the former model. Is there an example of the latter model?

What I am extremely confused about is that Goodstein's theorem seems to be about an objective statement about arithmetic : You either always reach zero using the steps, or there exists a counter-example. If the theorem has been proven to be true, how can we ever find a model where it's false (without us re-defining the meaning of arithmetic operations)?

If this theorem is false in a non-standard model, can that model produce a counter-example number for which this theorem is false? I want to understand how a seemingly absolute statement's truth can actually be relative to the model.

• ZFC is not a model in PA. A model of PA in which the theorem is false cannot be a model in ZFC (to be honest , I have difficulties to understand this, but I am sure someone here can completely clarify it). I am unfortunately not very firm with mathematical logic. Commented Mar 7, 2023 at 10:53
• "the theorem has been proven to be true" in the standard model. According to GIT (incompleteness) and other results, there are non-standard ones. Commented Mar 7, 2023 at 11:29
• An "actual number" which is a counterexample (in the model in with Goodstein is false) will (i think) be a non-standard (i.e. infinite) element in the model. So, for example, it's likely NOT something you can plug into a compueter program to see what happens.
– Ned
Commented Mar 7, 2023 at 12:23
• "Re-defining the meaning of arithmetic operations" is exactly what a model is. A model is just any set equipped with some operations that satisfy the axioms; those operations don't have to be the usual arithmetic operations (and the set does not have to be the usual natural numbers). Commented Mar 7, 2023 at 15:25
• @RobertShore Yes - you basically say "For every starting number $n$ there is a code for a finite sequence beginning with $n$, ending with $0$, and following the Goodstein rule." Commented Mar 7, 2023 at 19:23

I think it's helpful to consider $$(i)$$ a simpler statement than Goodstein's theorem and $$(ii)$$ a weaker theory than $$\mathsf{PA}$$. The reason for the former is that Goodstein's theorem has lots of complexity which isn't really germane to the general logical issues at play; the reason for the latter is that there is a particular technical result (Tennenbaum's theorem) which prevents us from having any too-nicely-describable nonstandard models of $$\mathsf{PA}$$ at all, and again that makes the logical issues look more troubling than they really are.

So let's take as our statement "Every number is either even or odd" which we can formally express as $$(\star):\quad\forall x\exists y(y+y=x\vee y+y+1=x),$$ and let's take as our theory Robinson's arithmetic $$\mathsf{Q}$$. This theory, in contrast with $$\mathsf{PA}$$, has lots of easily-describable nonstandard models. In particular, my favorite nonstandard model of $$\mathsf{Q}$$ is the set $$\mathfrak{P}$$ of polynomials in a single variable $$x$$ with integer coefficients and nonnegative leading coefficient, ordered by eventual domination as $$x\rightarrow\infty$$. (More snappily, take the ring $$\mathbb{Z}[x]$$, order it so that $$p>q$$ whenever $$p$$ is a polynomial of higher degree than $$q$$, and look at the nonnegative elements of that ordered ring.)

Now it's easy to show that $$\mathfrak{P}$$ does not satisfy $$(\star)$$: just consider the polynomial $$x$$ by itself. To us, this is not a natural number, but "within $$\mathfrak{P}$$" it looks perfectly fine. Perhaps belaboring the point, there is a unique way embedding of $$\mathbb{N}$$ inside $$\mathfrak{P}$$, and $$x$$ is not in the image of that embedding.

The case of $$\mathsf{PA}$$ and Goodstein's theorem is fundamentally no different: we can find a (necessarily nonstandard) model $$\mathfrak{M}$$ of $$\mathsf{PA}$$ such that $$\mathfrak{M}$$ "thinks" that Goodstein's theorem fails. But any of the things $$\mathfrak{M}$$ thinks are counterexamples to Goodstein will be nonstandard, just as $$x$$ was a nonstandard element of $$\mathfrak{P}$$ in the example above.

The following old answers of mine cover related material: on $$\mathfrak{P}$$ specifically and on nonstandard models in general (the latter is a bit technical unfortunately).

• Nice answer. I think it would help the OP if you added a bit about how Goodstein's theorem can be stated in PA. Also, although Tenebaum's theorem forbids a recursive nonstandard model of PA, we can still demand that the domain is $\mathbb{N}$ with "funny operations". This may make it seem more concrete. Commented Mar 7, 2023 at 20:02
• Much thanks. This is extremely interesting. I want to know, what is the mathematical definition of "standard arithmetic"? I mean, for the set of natural numbers that humans use, "every number is either even or odd" clearly holds. Goodstein's theorem also holds. But how to mathematically define the system of arithmetic/natural numbers that humans use? We can't use any axiomatic system (like even ZFC) to define it because any axiomatic system will always be satisfied by non-standard models too. So is there a definition of it without using axiomatic systems? Commented Mar 8, 2023 at 4:01
• I've asked the above in a separate question : math.stackexchange.com/questions/4654746/… Commented Mar 8, 2023 at 11:36
• In the model of $Q$ described above, with integer polynomials, what is the successor of a polynomial? Commented Mar 10, 2023 at 12:37
• @Weier $P(x)+1$ is the successor of $P(x)$, for any polynomial $P$ (remember that the coefficients have to be integers). Commented Mar 10, 2023 at 12:47