18
$\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?

Improve this question
$\endgroup$
6
  • 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
    Commented May 19, 2019 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
    Commented May 19, 2019 at 19:44
  • $\begingroup$ first comment link moved to here: neugierde.github.io/cantors-attic/ZFC#omega-models-of-textzfc $\endgroup$
    – Ben Burns
    Commented Dec 12, 2022 at 20:47
  • $\begingroup$ Sorry, but how the natural numbers in a model of ZFC be nonstandard? If $(\mathbb{N}^M,\emptyset,\in)$ is a nonstandard model of PA, then it properly contains the stardard one, which is a smaller inductive set. Pardon me if I have said something nonsense. $\endgroup$
    – Jianing Song
    Commented Sep 12, 2023 at 3:25
  • $\begingroup$ @JianingSong $\mathbb{N}^M$ is the smallest inductive set in $M$, but not the smallest inductive set externally. In general, if $M$ has a non-standard part of natural numbers, then no set in $M$ is isomorphic to $\mathbb{N}$. $\endgroup$
    – Hanul Jeon
    Commented May 27 at 22:00

1 Answer 1

Reset to default
32
$\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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I like this answer, but why is the existence of a model of ZFC an arithmetic statement? Is it a standard fact? $\endgroup$
    – display llvll
    Commented May 18, 2019 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
    Commented May 18, 2019 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
    Commented May 18, 2019 at 23:40
  • 1
    $\begingroup$ @WillSawin The answer is negative, see the edit to my answer. $\endgroup$
    – Wojowu
    Commented May 19, 2019 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
    Commented May 19, 2019 at 8:50

You must log in to answer this question.

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