Existence of a model of ZFC in which the natural numbers are really the natural numbersAre omega-consistent extensions of PA always consistent with each other?Clearing misconceptions: Defining “is a model of ZFC” in ZFCZ_2 versus second-order PAAxiom to exclude nonstandard natural numbersModels of the natural numbers in ultrapowers in the universe.Are there non-commutative models of arithmetic which have a prime number structure?Is every order type of a PA model the omega of some ZFC model?Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?Is second-order logic *with standard semantics* necessary to categorically characterise the natural number structure?
Existence of a model of ZFC in which the natural numbers are really the natural numbers
Are omega-consistent extensions of PA always consistent with each other?Clearing misconceptions: Defining “is a model of ZFC” in ZFCZ_2 versus second-order PAAxiom to exclude nonstandard natural numbersModels of the natural numbers in ultrapowers in the universe.Are there non-commutative models of arithmetic which have a prime number structure?Is every order type of a PA model the omega of some ZFC model?Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?Is second-order logic *with standard semantics* necessary to categorically characterise the natural number structure?
$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?
set-theory model-theory peano-arithmetic
asked May 18 at 21:25
GLeGLe
1571 silver badge13 bronze badges
$endgroup$
add a comment
|
$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?
set-theory model-theory peano-arithmetic
asked May 18 at 21:25
GLeGLe
1571 silver badge13 bronze badges
$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 mathbbN$" 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
add a comment
|
$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?
set-theory model-theory peano-arithmetic
asked May 18 at 21:25
GLeGLe
1571 silver badge13 bronze badges
$endgroup$
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?
set-theory model-theory peano-arithmetic
set-theory model-theory peano-arithmetic
asked May 18 at 21:25
GLeGLe
1571 silver badge13 bronze badges
asked May 18 at 21:25
GLeGLe
1571 silver badge13 bronze badges
edited May 18 at 21:39
GLe
asked May 18 at 21:25
GLeGLe
1571 silver badge13 bronze badges
asked May 18 at 21:25
GLeGLe
1571 silver badge13 bronze badges
asked May 18 at 21:25
GLeGLe
1571 silver badge13 bronze badges
1571 silver badge13 bronze badges
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 mathbbN$" 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
add a comment
|
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 mathbbN$" 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
4
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
$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
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 mathbbN$" 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
$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 mathbbN$" 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
add a comment
|
1 Answer
1
active
oldest
votes
$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 NvDash Con(ZFC)$, and since $mathbb N^Mcongmathbb N$, $mathbb N^MvDash Con(ZFC)$, and hence $MvDash 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.
answered May 18 at 21:39
WojowuWojowu
9,0741 gold badge36 silver badges65 bronze badges
$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
|
show 1 more comment
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "504"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f331897%2fexistence-of-a-model-of-zfc-in-which-the-natural-numbers-are-really-the-natural%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 NvDash Con(ZFC)$, and since $mathbb N^Mcongmathbb N$, $mathbb N^MvDash Con(ZFC)$, and hence $MvDash 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.
answered May 18 at 21:39
WojowuWojowu
9,0741 gold badge36 silver badges65 bronze badges
$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
|
show 1 more comment
$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 NvDash Con(ZFC)$, and since $mathbb N^Mcongmathbb N$, $mathbb N^MvDash Con(ZFC)$, and hence $MvDash 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.
answered May 18 at 21:39
WojowuWojowu
9,0741 gold badge36 silver badges65 bronze badges
$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
|
show 1 more comment
$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 NvDash Con(ZFC)$, and since $mathbb N^Mcongmathbb N$, $mathbb N^MvDash Con(ZFC)$, and hence $MvDash 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.
answered May 18 at 21:39
WojowuWojowu
9,0741 gold badge36 silver badges65 bronze badges
$endgroup$
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 NvDash Con(ZFC)$, and since $mathbb N^Mcongmathbb N$, $mathbb N^MvDash Con(ZFC)$, and hence $MvDash 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.
answered May 18 at 21:39
WojowuWojowu
9,0741 gold badge36 silver badges65 bronze badges
edited May 19 at 8:23
answered May 18 at 21:39
WojowuWojowu
9,0741 gold badge36 silver badges65 bronze badges
answered May 18 at 21:39
WojowuWojowu
9,0741 gold badge36 silver badges65 bronze badges
answered May 18 at 21:39
WojowuWojowu
9,0741 gold badge36 silver badges65 bronze badges
9,0741 gold badge36 silver badges65 bronze badges
$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
|
show 1 more comment
$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
$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
$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
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
$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
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
$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
1
$begingroup$
@WillSawin The answer is negative, see the edit to my answer.
$endgroup$
– Wojowu
May 19 at 8:24
$begingroup$
@WillSawin The answer is negative, see the edit to my answer.
$endgroup$
– Wojowu
May 19 at 8:24
3
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
$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
|
show 1 more comment
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f331897%2fexistence-of-a-model-of-zfc-in-which-the-natural-numbers-are-really-the-natural%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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 mathbbN$" 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