ZF shouldn’t be able to prove that some set is a model of ZF, because that’s not true in all models. Many models of ZF don’t contain any individual set well-populated enough for that one set to be a model of ZF all by itself.”
Is this true because of the absent C, true in the sense of the (larger) model, or just false?
ZF can’t prove that models of ZF exist because proving models of ZF exist is equivalent to proving that ZF is consistent, and ZF can’t prove its own consistency (if it is in fact consistent) by the incompleteness theorem. I don’t think ZFC can prove the consistency of ZF either, but I’m not a set theorist.
You can substitute ZFC for ZF throughout the quoted paragraph and it will still be true. I don’t know what you want me to get from the link given; it doesn’t seem to contradict the quoted paragraph. The part where the link talks about Vk entailing ZFC for inaccessible k is exactly what the quoted paragraph is saying.
So after reading that, I don’t see how it could be true even in the sense described in the article without violating Well Foundation somehow, but what it literally says at the link is that every model of ZFC has an element which encodes a model of ZFC, not is a model of ZFC, which I suppose must make a difference somehow—in particular it must mean that we don’t get A has an element B has an element C has an element D … although I don’t see yet why you couldn’t construct that set using the model’s model’s model and so on. I am confused about this although the poster of the link certainly seems like a legitimate authority.
But yes, it’s possible that the original paragraph is just false, and every model of ZFC contains a quoted model of ZFC. Maybe the pair-encoding of quoted models enables there to be an infinite descending sequence of submodels without there being an infinite descending sequence of ranks, the way that the even numbers can encode the numbers which contain the even numbers and so on indefinitely, and the reason why ZFC doesn’t prove ZFC has a model is that some models have nonstandard axioms which the set modeling standard-ZFC doesn’t entail. Anyone else want to weigh in on this before I edit? (PS upvote parent and great-grandparent.)
I don’t see how it could be true even in the sense described in the article without violating Well Foundation somehow
Here’s why I think you don’t get a violation of the axiom of well-foundation from Joel’s answer, starting from way-back-when-things-made-sense. If you want to skim and intuit the context, just read the bold parts.
1) Humans are born and see rocks and other objects. In their minds, a language forms for talking about objects, existence, and truth. When they say “rocks” in their head, sensory neurons associated with the presence of rocks fire. When they say “rocks exist”, sensory neurons associated with “true” fire.
2) Eventually the humans get really excited and invent a system of rules for making cave drawings like “∃” and “x” and “∈” which they call ZFC, which asserts the existence of infinite sets. In particular, many of the humans interpret the cave drawing “∃” to mean “there exists”. That is, many of the same neurons fire when they read “∃” as when they say “exists” to themselves. Some of the humans are careful not to necessarily believe the ZFC cave drawing, and imagine a guy named ZFC who is saying those things… “ZFC says there exists...”.
3) Some humans find ways to write a string of ZFC cave drawings which, when interpreted—when allowed to make human neurons fire—in the usual way, mean to the humans that ZFC is consistent. Instead of writing out that string, I’ll just write in place of it.
4) Some humans apply the ZFC rules to turn the ZFC axiom-cave-drawings and the cave drawing into a cave drawing that looks like this:
“∃ a set X and a relation e such that <(X,e) is a model of ZFC>”
where <(X,e) is a model of ZFC> is a string of ZFC cave drawings that means to the humans that (X,e) is a model of ZFC. That is, for each axiom A of ZFC, they produce another ZFC cave drawing A’ where “∃y” is always replaced by “∃y∈X”, and “∈” is always replaced by “e”, and then derive that cave drawing from the cave drawing ” and ” according to the ZFC rules.
Some cautious humans try not to believe that X really exists… only that ZFC and the consistency of ZFC imply that X exists. In fact if X did exist and ZFC meant what it usually does, then X would be infinite.
4) The humans derive another cave drawing from ZFC+:
“∃Y∈X and f∈X such that <(Y,f) is a model of ZFC>”,
6) The humans derive yet another cave drawing,
“∃ZeY and geX such that <(Z,g) is a model of ZFC>”.
Some of the humans, like me, think for a moment that Z∈Y∈X, and that if ZFC can prove this pattern continues then ZFC will assert the existence of an infinite regress of sets violating the axiom of well-foundation… but actually, we only have “ZeY∈X” … ZFC only says that Z is related to Y by the extra-artificial e-relation that ZFC said existed on X.
I think that’s why you don’t get a contradiction of well-foundation.
Well Foundation in V_alpha case seems quite simple: you build externally-countable chain of subsets which simply cannot be represented as a set inside the first model of ZFC. So the external WF is not broken because the element-relation inside the models is different, and the inner WF is fine because the chain of inner models of external ZFC is not an inner set.
In the standard case your even-numbers explanation nicely shows what goes on — quoting is involved.
I need to think a bit to say what woud halt our attempts to build a chain of transitive countable models...
Well, technically not every model of ZFC has a ZFC-modelling element. There is a model of “ZFC+¬Con(ZFC)”, and no element of this monster can be a model of ZFC. Not even with nonstandard element-relation.
Linked impressive authority says the model has a ZFC-model-encoding element, plus enough nonstandard quoted ZFC axioms in-model that in-model ZFC doesn’t think it’s a ZFC-model-encoding element. I.e., the formula for “semantically entails ZFC” is false within the model, but from outside, using our own standard list of axioms, we think the element is a model of ZFC.
I’ll make this more explicit, and note that at present I don’t see it affecting anyone’s argument:
ZF can’t prove its own self-consistency and thus can’t prove it has a model. You logician says that’s as it should be, since not every model of ZF contains another model—which seems true provided we treat each model more as an interpretation than as an object in a larger universe—and then says that a model has to be “well-populated”—which AFAICT holds for standard models, but not for all other interpretations like those your logician used in the previous sentence.
Is this true because of the absent C, true in the sense of the (larger) model, or just false?
ZF can’t prove that models of ZF exist because proving models of ZF exist is equivalent to proving that ZF is consistent, and ZF can’t prove its own consistency (if it is in fact consistent) by the incompleteness theorem. I don’t think ZFC can prove the consistency of ZF either, but I’m not a set theorist.
Also not a set theorist, but I’m pretty sure this is correct. ZF+Con(ZF) proves Con(ZFC) (see http://en.wikipedia.org/wiki/Constructible_universe), so if ZFC could prove Con(ZF) then it would also prove Con(ZFC).
You can substitute ZFC for ZF throughout the quoted paragraph and it will still be true. I don’t know what you want me to get from the link given; it doesn’t seem to contradict the quoted paragraph. The part where the link talks about Vk entailing ZFC for inaccessible k is exactly what the quoted paragraph is saying.
Zah? The linked answer says,
It goes on to say that this need not hold when we interpret “model of ZFC” in the sense of the (outer) model.
So after reading that, I don’t see how it could be true even in the sense described in the article without violating Well Foundation somehow, but what it literally says at the link is that every model of ZFC has an element which encodes a model of ZFC, not is a model of ZFC, which I suppose must make a difference somehow—in particular it must mean that we don’t get A has an element B has an element C has an element D … although I don’t see yet why you couldn’t construct that set using the model’s model’s model and so on. I am confused about this although the poster of the link certainly seems like a legitimate authority.
But yes, it’s possible that the original paragraph is just false, and every model of ZFC contains a quoted model of ZFC. Maybe the pair-encoding of quoted models enables there to be an infinite descending sequence of submodels without there being an infinite descending sequence of ranks, the way that the even numbers can encode the numbers which contain the even numbers and so on indefinitely, and the reason why ZFC doesn’t prove ZFC has a model is that some models have nonstandard axioms which the set modeling standard-ZFC doesn’t entail. Anyone else want to weigh in on this before I edit? (PS upvote parent and great-grandparent.)
Here’s why I think you don’t get a violation of the axiom of well-foundation from Joel’s answer, starting from way-back-when-things-made-sense. If you want to skim and intuit the context, just read the bold parts.
1) Humans are born and see rocks and other objects. In their minds, a language forms for talking about objects, existence, and truth. When they say “rocks” in their head, sensory neurons associated with the presence of rocks fire. When they say “rocks exist”, sensory neurons associated with “true” fire.
2) Eventually the humans get really excited and invent a system of rules for making cave drawings like “∃” and “x” and “∈” which they call ZFC, which asserts the existence of infinite sets. In particular, many of the humans interpret the cave drawing “∃” to mean “there exists”. That is, many of the same neurons fire when they read “∃” as when they say “exists” to themselves. Some of the humans are careful not to necessarily believe the ZFC cave drawing, and imagine a guy named ZFC who is saying those things… “ZFC says there exists...”.
3) Some humans find ways to write a string of ZFC cave drawings which, when interpreted—when allowed to make human neurons fire—in the usual way, mean to the humans that ZFC is consistent. Instead of writing out that string, I’ll just write in place of it.
4) Some humans apply the ZFC rules to turn the ZFC axiom-cave-drawings and the cave drawing into a cave drawing that looks like this:
“∃ a set X and a relation e such that <(X,e) is a model of ZFC>”
where <(X,e) is a model of ZFC> is a string of ZFC cave drawings that means to the humans that (X,e) is a model of ZFC. That is, for each axiom A of ZFC, they produce another ZFC cave drawing A’ where “∃y” is always replaced by “∃y∈X”, and “∈” is always replaced by “e”, and then derive that cave drawing from the cave drawing ” and ” according to the ZFC rules.
Some cautious humans try not to believe that X really exists… only that ZFC and the consistency of ZFC imply that X exists. In fact if X did exist and ZFC meant what it usually does, then X would be infinite.
4) The humans derive another cave drawing from ZFC+:
“∃Y∈X and f∈X such that <(Y,f) is a model of ZFC>”,
6) The humans derive yet another cave drawing,
“∃ZeY and geX such that <(Z,g) is a model of ZFC>”.
Some of the humans, like me, think for a moment that Z∈Y∈X, and that if ZFC can prove this pattern continues then ZFC will assert the existence of an infinite regress of sets violating the axiom of well-foundation… but actually, we only have “ZeY∈X” … ZFC only says that Z is related to Y by the extra-artificial e-relation that ZFC said existed on X.
I think that’s why you don’t get a contradiction of well-foundation.
Well Foundation in V_alpha case seems quite simple: you build externally-countable chain of subsets which simply cannot be represented as a set inside the first model of ZFC. So the external WF is not broken because the element-relation inside the models is different, and the inner WF is fine because the chain of inner models of external ZFC is not an inner set.
In the standard case your even-numbers explanation nicely shows what goes on — quoting is involved.
I need to think a bit to say what woud halt our attempts to build a chain of transitive countable models...
Well, technically not every model of ZFC has a ZFC-modelling element. There is a model of “ZFC+¬Con(ZFC)”, and no element of this monster can be a model of ZFC. Not even with nonstandard element-relation.
Linked impressive authority says the model has a ZFC-model-encoding element, plus enough nonstandard quoted ZFC axioms in-model that in-model ZFC doesn’t think it’s a ZFC-model-encoding element. I.e., the formula for “semantically entails ZFC” is false within the model, but from outside, using our own standard list of axioms, we think the element is a model of ZFC.
Ah, sorry, I didn’t notice that the question is about model of ZFC inside a “universe” modelling ZFC+Con^∞(ZFC)
The linked answer is talking about models of ZFC in an external sense and Eliezer is talking about them in an internal sense.
I’ll make this more explicit, and note that at present I don’t see it affecting anyone’s argument:
ZF can’t prove its own self-consistency and thus can’t prove it has a model. You logician says that’s as it should be, since not every model of ZF contains another model—which seems true provided we treat each model more as an interpretation than as an object in a larger universe—and then says that a model has to be “well-populated”—which AFAICT holds for standard models, but not for all other interpretations like those your logician used in the previous sentence.