How can ZF prove relative consistency for itself?
This is related to my first question. In order to get what I don't get, I ll go with something much more specific here.
It is well known that $ZF vdash Con(ZF) longrightarrow Con(ZF + AF)$. The way I know to prove it uses :
Lemma 1 : If $T$ and $S$ are two theories in set theory language, $M$ is a class (i.e. a formula $phi(x)$ tell if $x$ is in $M$ or not) and $T vdash mbox{"}M$ is a model for $S$", then $Con(T) vdash Con(S)$
So we have to build a class, say $V=cup_{alpha in ORD} V_{alpha}$ and then $ZF$ is suppose to demonstrate, for instance, that $V$ satisfies comprehension axiom scheme.
We can use :
Lemma 2 : $(forall x in M$, $P(x) subset M) longrightarrow$ comprehension scheme is true in $M$
With Lemma 2, the proof is straightforward.
My problem is that I do not know why lemma 2 would be a ZF theorem. I don't even know how it could be written in ZF language, since there is an infinite number of axiom to write, and since $V$ is a class, there is no formula $theta(ulcorner f urcorner)$ saying $V vDash f$
Of course, for all formulas $F$ of the comprehension scheme, we can write
$ZF vdash (forall x in M$, $P(x) subset M) longrightarrow F^M$
but if we do that for all formulas, the proof will be infinite...
logic set-theory
add a comment |
This is related to my first question. In order to get what I don't get, I ll go with something much more specific here.
It is well known that $ZF vdash Con(ZF) longrightarrow Con(ZF + AF)$. The way I know to prove it uses :
Lemma 1 : If $T$ and $S$ are two theories in set theory language, $M$ is a class (i.e. a formula $phi(x)$ tell if $x$ is in $M$ or not) and $T vdash mbox{"}M$ is a model for $S$", then $Con(T) vdash Con(S)$
So we have to build a class, say $V=cup_{alpha in ORD} V_{alpha}$ and then $ZF$ is suppose to demonstrate, for instance, that $V$ satisfies comprehension axiom scheme.
We can use :
Lemma 2 : $(forall x in M$, $P(x) subset M) longrightarrow$ comprehension scheme is true in $M$
With Lemma 2, the proof is straightforward.
My problem is that I do not know why lemma 2 would be a ZF theorem. I don't even know how it could be written in ZF language, since there is an infinite number of axiom to write, and since $V$ is a class, there is no formula $theta(ulcorner f urcorner)$ saying $V vDash f$
Of course, for all formulas $F$ of the comprehension scheme, we can write
$ZF vdash (forall x in M$, $P(x) subset M) longrightarrow F^M$
but if we do that for all formulas, the proof will be infinite...
logic set-theory
Be careful with the fact that this approach to proving relative consistency takes place in the metatheory, not in the object language: math.stackexchange.com/a/1892103/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
See also: math.stackexchange.com/a/1368646/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
add a comment |
This is related to my first question. In order to get what I don't get, I ll go with something much more specific here.
It is well known that $ZF vdash Con(ZF) longrightarrow Con(ZF + AF)$. The way I know to prove it uses :
Lemma 1 : If $T$ and $S$ are two theories in set theory language, $M$ is a class (i.e. a formula $phi(x)$ tell if $x$ is in $M$ or not) and $T vdash mbox{"}M$ is a model for $S$", then $Con(T) vdash Con(S)$
So we have to build a class, say $V=cup_{alpha in ORD} V_{alpha}$ and then $ZF$ is suppose to demonstrate, for instance, that $V$ satisfies comprehension axiom scheme.
We can use :
Lemma 2 : $(forall x in M$, $P(x) subset M) longrightarrow$ comprehension scheme is true in $M$
With Lemma 2, the proof is straightforward.
My problem is that I do not know why lemma 2 would be a ZF theorem. I don't even know how it could be written in ZF language, since there is an infinite number of axiom to write, and since $V$ is a class, there is no formula $theta(ulcorner f urcorner)$ saying $V vDash f$
Of course, for all formulas $F$ of the comprehension scheme, we can write
$ZF vdash (forall x in M$, $P(x) subset M) longrightarrow F^M$
but if we do that for all formulas, the proof will be infinite...
logic set-theory
This is related to my first question. In order to get what I don't get, I ll go with something much more specific here.
It is well known that $ZF vdash Con(ZF) longrightarrow Con(ZF + AF)$. The way I know to prove it uses :
Lemma 1 : If $T$ and $S$ are two theories in set theory language, $M$ is a class (i.e. a formula $phi(x)$ tell if $x$ is in $M$ or not) and $T vdash mbox{"}M$ is a model for $S$", then $Con(T) vdash Con(S)$
So we have to build a class, say $V=cup_{alpha in ORD} V_{alpha}$ and then $ZF$ is suppose to demonstrate, for instance, that $V$ satisfies comprehension axiom scheme.
We can use :
Lemma 2 : $(forall x in M$, $P(x) subset M) longrightarrow$ comprehension scheme is true in $M$
With Lemma 2, the proof is straightforward.
My problem is that I do not know why lemma 2 would be a ZF theorem. I don't even know how it could be written in ZF language, since there is an infinite number of axiom to write, and since $V$ is a class, there is no formula $theta(ulcorner f urcorner)$ saying $V vDash f$
Of course, for all formulas $F$ of the comprehension scheme, we can write
$ZF vdash (forall x in M$, $P(x) subset M) longrightarrow F^M$
but if we do that for all formulas, the proof will be infinite...
logic set-theory
logic set-theory
edited Dec 26 at 4:32
Hans Hüttel
3,1872921
3,1872921
asked Mar 22 '11 at 16:26
Archimondain
63639
63639
Be careful with the fact that this approach to proving relative consistency takes place in the metatheory, not in the object language: math.stackexchange.com/a/1892103/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
See also: math.stackexchange.com/a/1368646/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
add a comment |
Be careful with the fact that this approach to proving relative consistency takes place in the metatheory, not in the object language: math.stackexchange.com/a/1892103/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
See also: math.stackexchange.com/a/1368646/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
Be careful with the fact that this approach to proving relative consistency takes place in the metatheory, not in the object language: math.stackexchange.com/a/1892103/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
Be careful with the fact that this approach to proving relative consistency takes place in the metatheory, not in the object language: math.stackexchange.com/a/1892103/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
See also: math.stackexchange.com/a/1368646/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
See also: math.stackexchange.com/a/1368646/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
add a comment |
1 Answer
1
active
oldest
votes
(In what follows, I am assuming that ZF consists of Extensionality, Pairing, Union, Comprehension, Replacement, Infinity and Power Set, and that AF is the Axiom of Foundation.)
I think that the somewhat formal way of looking at all of this is to basically work by contrapositive. Working in ZF, assume $neg mathrm{Con} ( text{ZF+AF} )$. Then there is a proof of some obvious contradiction, say $( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$, in ZF+AF. Furthermore, ZF is able to code proofs/formulas as sets/natural numbers in a standard manner. This proof can only consist of finitely many axioms from ZF+AF, say $phi_1 , ldots , phi_n$. Also in ZF we can construct the class of well-founded sets, denoted (as in Kunen) by $mathbf{WF}$, and in ZF we can prove that $mathbf{WF} models phi_1 wedge cdots wedge phi_n$, and therefore it must be that ''$mathbf{WF} models ( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$'' is a theorem of $text{ZF} + neg mathrm{Con} ( text{ZF+ AF} )$. Formally, using relativisation, we have that $$text{ZF} + neg mathrm{Con} ( text{ZF+AF} ) vdash ( forall x in mathbf{WF} ) ( x = x ) wedge neg ( forall x in mathbf{WF} ) ( x = x ),$$ and thus $text{ZF} vdash neg mathrm{Con} ( text{ZF+AF} ) rightarrow neg mathrm{Con} ( text{ZF} )$.
Awesome ! This answers everything I was wondering. thx a lot. So despite the fact that this is wrong to say $ZF vdash mbox{"}WF vDash ZFmbox{"}$, this is true to say $ZF vdash Con(ZF) rightarrow Con(ZF+AF)$
– Archimondain
Mar 22 '11 at 17:54
Actually, $neg Con(ZF + AF)$ says there is a proof of some obvios contradiction, but why would this proof be standard ? If it is not, how to proove $neg Con(ZF)$ ?
– Archimondain
Mar 23 '11 at 9:47
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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/3.0/"u003ecc by-sa 3.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%2fmath.stackexchange.com%2fquestions%2f28515%2fhow-can-zf-prove-relative-consistency-for-itself%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
(In what follows, I am assuming that ZF consists of Extensionality, Pairing, Union, Comprehension, Replacement, Infinity and Power Set, and that AF is the Axiom of Foundation.)
I think that the somewhat formal way of looking at all of this is to basically work by contrapositive. Working in ZF, assume $neg mathrm{Con} ( text{ZF+AF} )$. Then there is a proof of some obvious contradiction, say $( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$, in ZF+AF. Furthermore, ZF is able to code proofs/formulas as sets/natural numbers in a standard manner. This proof can only consist of finitely many axioms from ZF+AF, say $phi_1 , ldots , phi_n$. Also in ZF we can construct the class of well-founded sets, denoted (as in Kunen) by $mathbf{WF}$, and in ZF we can prove that $mathbf{WF} models phi_1 wedge cdots wedge phi_n$, and therefore it must be that ''$mathbf{WF} models ( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$'' is a theorem of $text{ZF} + neg mathrm{Con} ( text{ZF+ AF} )$. Formally, using relativisation, we have that $$text{ZF} + neg mathrm{Con} ( text{ZF+AF} ) vdash ( forall x in mathbf{WF} ) ( x = x ) wedge neg ( forall x in mathbf{WF} ) ( x = x ),$$ and thus $text{ZF} vdash neg mathrm{Con} ( text{ZF+AF} ) rightarrow neg mathrm{Con} ( text{ZF} )$.
Awesome ! This answers everything I was wondering. thx a lot. So despite the fact that this is wrong to say $ZF vdash mbox{"}WF vDash ZFmbox{"}$, this is true to say $ZF vdash Con(ZF) rightarrow Con(ZF+AF)$
– Archimondain
Mar 22 '11 at 17:54
Actually, $neg Con(ZF + AF)$ says there is a proof of some obvios contradiction, but why would this proof be standard ? If it is not, how to proove $neg Con(ZF)$ ?
– Archimondain
Mar 23 '11 at 9:47
add a comment |
(In what follows, I am assuming that ZF consists of Extensionality, Pairing, Union, Comprehension, Replacement, Infinity and Power Set, and that AF is the Axiom of Foundation.)
I think that the somewhat formal way of looking at all of this is to basically work by contrapositive. Working in ZF, assume $neg mathrm{Con} ( text{ZF+AF} )$. Then there is a proof of some obvious contradiction, say $( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$, in ZF+AF. Furthermore, ZF is able to code proofs/formulas as sets/natural numbers in a standard manner. This proof can only consist of finitely many axioms from ZF+AF, say $phi_1 , ldots , phi_n$. Also in ZF we can construct the class of well-founded sets, denoted (as in Kunen) by $mathbf{WF}$, and in ZF we can prove that $mathbf{WF} models phi_1 wedge cdots wedge phi_n$, and therefore it must be that ''$mathbf{WF} models ( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$'' is a theorem of $text{ZF} + neg mathrm{Con} ( text{ZF+ AF} )$. Formally, using relativisation, we have that $$text{ZF} + neg mathrm{Con} ( text{ZF+AF} ) vdash ( forall x in mathbf{WF} ) ( x = x ) wedge neg ( forall x in mathbf{WF} ) ( x = x ),$$ and thus $text{ZF} vdash neg mathrm{Con} ( text{ZF+AF} ) rightarrow neg mathrm{Con} ( text{ZF} )$.
Awesome ! This answers everything I was wondering. thx a lot. So despite the fact that this is wrong to say $ZF vdash mbox{"}WF vDash ZFmbox{"}$, this is true to say $ZF vdash Con(ZF) rightarrow Con(ZF+AF)$
– Archimondain
Mar 22 '11 at 17:54
Actually, $neg Con(ZF + AF)$ says there is a proof of some obvios contradiction, but why would this proof be standard ? If it is not, how to proove $neg Con(ZF)$ ?
– Archimondain
Mar 23 '11 at 9:47
add a comment |
(In what follows, I am assuming that ZF consists of Extensionality, Pairing, Union, Comprehension, Replacement, Infinity and Power Set, and that AF is the Axiom of Foundation.)
I think that the somewhat formal way of looking at all of this is to basically work by contrapositive. Working in ZF, assume $neg mathrm{Con} ( text{ZF+AF} )$. Then there is a proof of some obvious contradiction, say $( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$, in ZF+AF. Furthermore, ZF is able to code proofs/formulas as sets/natural numbers in a standard manner. This proof can only consist of finitely many axioms from ZF+AF, say $phi_1 , ldots , phi_n$. Also in ZF we can construct the class of well-founded sets, denoted (as in Kunen) by $mathbf{WF}$, and in ZF we can prove that $mathbf{WF} models phi_1 wedge cdots wedge phi_n$, and therefore it must be that ''$mathbf{WF} models ( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$'' is a theorem of $text{ZF} + neg mathrm{Con} ( text{ZF+ AF} )$. Formally, using relativisation, we have that $$text{ZF} + neg mathrm{Con} ( text{ZF+AF} ) vdash ( forall x in mathbf{WF} ) ( x = x ) wedge neg ( forall x in mathbf{WF} ) ( x = x ),$$ and thus $text{ZF} vdash neg mathrm{Con} ( text{ZF+AF} ) rightarrow neg mathrm{Con} ( text{ZF} )$.
(In what follows, I am assuming that ZF consists of Extensionality, Pairing, Union, Comprehension, Replacement, Infinity and Power Set, and that AF is the Axiom of Foundation.)
I think that the somewhat formal way of looking at all of this is to basically work by contrapositive. Working in ZF, assume $neg mathrm{Con} ( text{ZF+AF} )$. Then there is a proof of some obvious contradiction, say $( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$, in ZF+AF. Furthermore, ZF is able to code proofs/formulas as sets/natural numbers in a standard manner. This proof can only consist of finitely many axioms from ZF+AF, say $phi_1 , ldots , phi_n$. Also in ZF we can construct the class of well-founded sets, denoted (as in Kunen) by $mathbf{WF}$, and in ZF we can prove that $mathbf{WF} models phi_1 wedge cdots wedge phi_n$, and therefore it must be that ''$mathbf{WF} models ( forall x ) ( x = x ) wedge neg ( forall x ) ( x = x )$'' is a theorem of $text{ZF} + neg mathrm{Con} ( text{ZF+ AF} )$. Formally, using relativisation, we have that $$text{ZF} + neg mathrm{Con} ( text{ZF+AF} ) vdash ( forall x in mathbf{WF} ) ( x = x ) wedge neg ( forall x in mathbf{WF} ) ( x = x ),$$ and thus $text{ZF} vdash neg mathrm{Con} ( text{ZF+AF} ) rightarrow neg mathrm{Con} ( text{ZF} )$.
answered Mar 22 '11 at 17:30
user642796
44.5k559116
44.5k559116
Awesome ! This answers everything I was wondering. thx a lot. So despite the fact that this is wrong to say $ZF vdash mbox{"}WF vDash ZFmbox{"}$, this is true to say $ZF vdash Con(ZF) rightarrow Con(ZF+AF)$
– Archimondain
Mar 22 '11 at 17:54
Actually, $neg Con(ZF + AF)$ says there is a proof of some obvios contradiction, but why would this proof be standard ? If it is not, how to proove $neg Con(ZF)$ ?
– Archimondain
Mar 23 '11 at 9:47
add a comment |
Awesome ! This answers everything I was wondering. thx a lot. So despite the fact that this is wrong to say $ZF vdash mbox{"}WF vDash ZFmbox{"}$, this is true to say $ZF vdash Con(ZF) rightarrow Con(ZF+AF)$
– Archimondain
Mar 22 '11 at 17:54
Actually, $neg Con(ZF + AF)$ says there is a proof of some obvios contradiction, but why would this proof be standard ? If it is not, how to proove $neg Con(ZF)$ ?
– Archimondain
Mar 23 '11 at 9:47
Awesome ! This answers everything I was wondering. thx a lot. So despite the fact that this is wrong to say $ZF vdash mbox{"}WF vDash ZFmbox{"}$, this is true to say $ZF vdash Con(ZF) rightarrow Con(ZF+AF)$
– Archimondain
Mar 22 '11 at 17:54
Awesome ! This answers everything I was wondering. thx a lot. So despite the fact that this is wrong to say $ZF vdash mbox{"}WF vDash ZFmbox{"}$, this is true to say $ZF vdash Con(ZF) rightarrow Con(ZF+AF)$
– Archimondain
Mar 22 '11 at 17:54
Actually, $neg Con(ZF + AF)$ says there is a proof of some obvios contradiction, but why would this proof be standard ? If it is not, how to proove $neg Con(ZF)$ ?
– Archimondain
Mar 23 '11 at 9:47
Actually, $neg Con(ZF + AF)$ says there is a proof of some obvios contradiction, but why would this proof be standard ? If it is not, how to proove $neg Con(ZF)$ ?
– Archimondain
Mar 23 '11 at 9:47
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fmath.stackexchange.com%2fquestions%2f28515%2fhow-can-zf-prove-relative-consistency-for-itself%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
Be careful with the fact that this approach to proving relative consistency takes place in the metatheory, not in the object language: math.stackexchange.com/a/1892103/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34
See also: math.stackexchange.com/a/1368646/75867
– Ioannis Filippidis
Dec 10 '16 at 9:34