11
$\begingroup$

I have a big trouble in my mind, here is my false reasoning:

  1. The Goodstein's theorem is undecidable in (first order) Peano Arithmetic.

    • There exist a non standard model N of PA where the Goodstein's theorem is false.
  2. The Goodstein's theorem is provable in ZFC, using ordinals below $\epsilon_{0}$.

    • Since a statement provable in a theory T is true in all models of T, the Goodstein's theorem must be true in all models of ZFC. (?)
    • The ordinals of a ZFC model are well-founded from the internal point of view of this model.
  3. If there exist a model M of ZFC where the model N is the naturals numbers of M. (?)

    • The Goodstein's theorem is false in M by definition of N, but true by 2), we can prove it in M using the $\epsilon_{0}$ of M, like in our universe.

Where I have gone wrong?

$\endgroup$
  • 6
    $\begingroup$ Why would 3. be correct ? $\endgroup$ – Max Jun 19 '17 at 13:48
  • 11
    $\begingroup$ Nowhere. This shows that not every model of PA is the natural numbers of a model of ZFC. $\endgroup$ – Andrés E. Caicedo Jun 19 '17 at 13:49
  • 12
    $\begingroup$ But you can see this without appealing to results related to Goodstein's theorem: For example, ZFC proves the arithmetic statement that PA is consistent. Thus, the $\mathbb N $ of any model of ZFC is a model of PA+Con(PA). $\endgroup$ – Andrés E. Caicedo Jun 19 '17 at 13:53
  • $\begingroup$ Clearly PA cannot perform transfinite induction up to $\epsilon_{0}$, but it would be interesting to address such a thing to higher-order arithmetic. $\endgroup$ – user101052 Jun 20 '17 at 6:52
22
$\begingroup$

As Andrés points out in the comments, your question seems to be resolved by the observation that not every model of PA can arise as the $\mathbb{N}$ of a model of ZFC.

Meanwhile, one can attempt to understand more deeply exactly which models of PA do arise as the $\mathbb{N}$ of a model of set theory. Let us say that a model $N\models\text{PA}$ is a standard model of arithmetic (as opposed to the standard model of arithmetic), or alternatively is a ZFC-standard model of arithmetic, if $N=\mathbb{N}^M$ for some $M\models\text{ZFC}$.

Thus, a model of arithmetic is a standard model of arithmetic, if it is the standard model of arithmetic from the perspective of some model of set theory. These are the models of PA that seem to be at the heart of your question.

We can characterize exactly what these models are as follows.

Theorem. (Ali Enayat) The following are equivalent, for a countable nonstandard model $N\models\text{PA}$.

  1. $N$ arises as $\mathbb{N}^M$ for some model $M\models\text{ZFC}$.

  2. $N$ is computably saturated and satisfies all the arithmetic consequences of ZFC.

In statement 2, what we mean is that $N\models\varphi$, whenever $\varphi$ is an arithmetic statement that is provable from ZFC. For example, this includes the case where $\varphi$ is Goodstein's theorem, and this is exactly what is going on in your question. Obviously, any model of PA arising as the $\mathbb{N}$ of a model of ZFC set theory must satisfy all the arithmetic consequences of ZFC, and this is essentially how you are reasoning in statement 3 of the question. The interesting part is that this is also sufficient, when combined with computable saturation.

You can find a proof of the theorem in my paper: J. D. Hamkins and R. Yang, Satisfaction is not absolute, to appear in the Review of Symbolic Logic, pp. 1-34. (arxiv:1312.0670) (see proposition 3).

$\endgroup$
  • $\begingroup$ But is it possible to "visualize" such nonstandard models of PA? What are their distinguishing features in terms of, say, order type? What enables them to "deceive" a model of ZFC? Also, your 2. somehow suggests that if a model is of this kind then $M$ in your 1. could be arbitrary? $\endgroup$ – მამუკა ჯიბლაძე Jun 19 '17 at 17:40
  • 4
    $\begingroup$ Yes, I believe one can come to know these models quite well, and those who study these models develop a deep insight into them. But order-type is not the way to do it, since all countable nonstandard models of PA have the same order type, which is $\mathbb{N}+\mathbb{Z}\cdot\mathbb{Q}$. And I don't know to what kind of deception you refer. Yes, the M in statement 1 can be arbitrary, for then you get $N$ as the $\mathbb{N}$ of that model. The point is that we can identify the necessary and sufficient properties on $N$ that it would arise that way, at least for countable models. $\endgroup$ – Joel David Hamkins Jun 19 '17 at 18:12
  • 6
    $\begingroup$ @მამუკაჯიბლაძე: What enables them to "deceive" a model of ZFC is that they resemble a $\mathbb{N}$ much more thoroughly than an arbitrary nonstandard model: indeed, they satisfy all the arithmetic consequences of ZFC. $\endgroup$ – Henry Towsner Jun 19 '17 at 18:47
  • 6
    $\begingroup$ @მამუკაჯიბლაძე: 1) Certainly not: the $\Pi^0_n$ consequences of ZFC do not imply the $\Pi^0_{n+1}$ consequences, so, at a minimum, it requires specifying properties of arbitrary complexity. 2) No; indeed, take any model $M$ of ZFC; it contains countably saturated nonstandard models of the language of arithmetic elementarily equivalent to $\mathbb{N}^M$. Such a model is the natural numbers of some model of ZFC, but $M$ can distinguish it from the standard model because $M$ can see that $\mathbb{N}^M$ is a proper initial segment. $\endgroup$ – Henry Towsner Jun 19 '17 at 18:59
  • 3
    $\begingroup$ @მამუკაჯიბლაძე: Because it can identify non-arithmetic properties---the sentence "there is a set closed under successor which is a proper initial segment" is $\Sigma^1_1$, not arithmetical, and is the thing that actually distinguishes a standard model from a non-standard one. $\endgroup$ – Henry Towsner Jun 20 '17 at 17:59
7
$\begingroup$

The resolution to your confusion is simply that there is no model $M$ of $ZFC$ for which $N$ is the set of natural numbers. Being the set of natural numbers of a model of $ZFC$ is very rare for models of $PA$, because a set of natural numbers for a model of $ZFC$ has to satisfy all kinds of statements that $ZFC$ can prove about natural numbers and $PA$ cannot, whereas in many models of $PA$ some or all of those statements are false.

The contradiction that you demonstrated is actually a proof that there is no model of $ZFC$ which has $N$ as its to set of natural numbers.

$\endgroup$

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.