12
$\begingroup$

I know that, from compactness theorem, one can prove that there are models of first order arithmetic in which there is some "number" which is not a successor of zero, in the sense that it is strictly bigger than any successor of zero (i.e. any element of the model obtained by applying the successor function to zero finitely many times).

From the axiom of infinity, it follows that every model of ZFC must contain an element which one can think of as "the natural numbers", in the sense that it is a model of Peano Axioms. Peano Axioms are a second-order theory, since the principle of induction is a second order axiom, and from the principle of induction it follows that the Peano Axioms have a unique model in ZFC, so that we can call this model among the others of first-order arithmetic, the "standard" model of arithmetic.

But picking one model of ZFC, how do we know what's really inside its standard model of arithmetic? How do we know there is nothing else than the successors of zero? After all, every model of ZFC thinks that his natural numbers are the standard ones, so one can use compactness to produce a model of ZFC which has non-standard natural numbers from an external point of view, and in which there will be a standard natural numbers object containing elements bigger than any successor of zero.

So, if one wants to do mathematics inside a model of a first order theory of sets, how can one know that he is able to pick a model in which the natural numbers are not non-standard?

$\endgroup$
  • 4
    $\begingroup$ The models you ask about are known as $\omega$-models of ZFC (see here). Note that this is weaker than being a well-founded model (see here). $\endgroup$ – Gro-Tsen May 19 at 0:52
  • 1
    $\begingroup$ You can construct a Turing machine that enumerates every sequence of arithmetical statements, and checks whether it is a valid proof in ZFC + whatever axioms you like that machine M halts or doesn't halt on input I. If your chosen axioms are consistent, then some choices of (M, I) must fail to have proofs, or else it would violate the halting problem. Then "Machine M, with input I, halts in $\alpha$ steps, and $\alpha \in \mathbb{N}$" is independent of your chosen axioms. $\alpha$ must be nonstandard, of course, because otherwise a proof would necessarily exist. $\endgroup$ – Kevin May 19 at 19:44
27
$\begingroup$

This, in fact, cannot be proven, even in $ZFC+Con(ZFC)$. This is because $ZFC$ proves the following statement:

If we have a model $M$ of $ZFC$ whose natural numbers are standard, then $M$ satisfies $ZFC+Con(ZFC)$.

Indeed, $Con(ZFC)$ is an arithmetic statement. Since we are assuming that $ZFC$ has a model $M$, and hence that $ZFC$ is consistent, $\mathbb N\vDash Con(ZFC)$, and since $\mathbb N^M\cong\mathbb N$, $\mathbb N^M\vDash Con(ZFC)$, and hence $M\vDash Con(ZFC)$.

Now if $ZFC$ could prove "if there is a model of $ZFC$, then there is a model of $ZFC$ with standard $\mathbb N$", then we would get that $ZFC+Con(ZFC)$ proves that $ZFC+Con(ZFC)$ has a model, contradicting Godel's second incompleteness theorem.

Therefore, we cannot conclude, from existence of a model, existence of a model with standard $\mathbb N$.


Thought it might be worth mentioning that this reasoning is under the assumption that $ZFC+Con(ZFC)$ is consistent. In the other case, $ZFC$ proves that $ZFC$ has no models, so the implication I discuss holds vacuously.


Will Sawin asks whether existence of a model of $ZFC$ with standard $\mathbb N$ (apparently called $\omega$-models, as Gro-Tsen's comment to the question notes) is equivalent to ZFC being arithmetically sound. The answer is negative (of course, again, under blanket consistency assumptions).

The idea is very similar. Suppose $ZFC$ is arithmetically sound, and that there is an $\omega$-model $M$ of $ZFC$. We claim $M$ satisfies "$ZFC$ is arithmetically sound". If we show that then we're done, since "$ZFC$ is arithmetically sound" cannot prove $Con$("$ZFC$ is arithmetically sound").

Arithmetic soundness is equivalent to "for all $n$, $ZFC$ is $\Sigma^0_n$-sound, and $\Sigma^0_n$-soundness is an arithmetic statement for each $n$. Since $M$ has standard $\mathbb N$, $\Sigma^0_n$-soundness holds in $M$ as well. Now we use standardness of $M$'s $\mathbb N$ again, to observe that $\Sigma^0_n$-soundness in $M$ for all $n$ in (external) $\mathbb N$ is equivalent to arithmetic soundness internally in $M$.

As you can see, existence of an $\omega$-model is a fairly strong property, much stronger than any consistency or soundness assumption.

$\endgroup$
  • $\begingroup$ I like this answer, but why is the existence of a model of ZFC an arithmetic statement? Is it a standard fact? $\endgroup$ – GLe May 18 at 21:56
  • 4
    $\begingroup$ By Godel's completeness theorem, "ZFC has a model" is equivalent to "ZFC does not prove contradiction", and the latter can be expressed as an arithmetic statement. For instance, if you are familiar with how Turing machines can be encoded arithmetically, ZFC not proving a contradiction is equivalent to a certain TM not halting. $\endgroup$ – Wojowu May 18 at 21:59
  • 2
    $\begingroup$ Is it equivalent to arithmetic soundness of ZFC, i.e. that all statements of PA proven by ZFC are true? $\endgroup$ – Will Sawin May 18 at 23:40
  • 1
    $\begingroup$ @WillSawin The answer is negative, see the edit to my answer. $\endgroup$ – Wojowu May 19 at 8:24
  • 3
    $\begingroup$ @WillSawin: Note that there are numerous different notions of 'correctness' that one can come up with, including consistency, arithmetical soundness, $Σ_n$-soundness, ω-consistency, existence of ω-model, and so on. The existence of an ω-model implies all the others I mentioned. And arithmetical soundness implies $Σ_n$-soundness for each natural $n$. But arithmetical soundness and ω-consistency are incomparable (as briefly sketched here). However, ω-consistency implies $Σ_1$-soundness, which implies consistency. All the implications are strict. $\endgroup$ – user21820 May 19 at 8:50

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.