Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There is often a lot of confusion surrounding the differences between relativizing individual formulas to models and the expression of "is a model of" through coding the satisfaction relation with Gödel operations. I think part of this can be attributed to the common preference for using formulas over codings. For example, a standard proof showing that $V_{\kappa} \models ZFC$ for $\kappa$ inaccessible will appeal to the fact that all of the ZFC axioms relativized to $V_{\kappa}$ are true. But then one learns about the Lévy Reflection Theorem scheme which allows every (finite) conjunction of formulas to be reflected to some $V_{\alpha}$. Perhaps this knowledge is followed by a question of whether the Compactness theorem can be used to contradict Gödel's Second Incompleteness Theorem.

Specifically, consider the following erroneous proof that ZFC + CON(ZFC) proves its own consistency:

Introduce a new constant $M$ into the language of set theory and add to the axioms of ZFC all of its axioms $\varphi_n$ relativized to $M$, denoted $\varphi_n^M$. Provided that ZFC is consistent, every finite collection of this theory is consistent by the Lévy Reflection Theorem whereby the Compactness Theorem tells us that the entire theory ZFC + "$M \models ZFC$" will be consistent. Consequently, this theory has a (ZFC) model $N$ so in this model, there exists a model $M$ of ZFC. To summarize then, arguing in ZFC + CON(ZFC), we've seemingly proven that we have a ZFC model $N$ modeling the consistency of ZFC by virtue of it having the model $M$ (i.e., seemingly $N \models ZFC + CON(ZFC)$ so we would have a proof of CON(ZFC + CON(ZFC)).

The misstep in this proof is of course a misuse of the conclusion of the Compactness theorem, mainly the assumption that such an $N$ will think that $M$ is a ZFC model. With some enumeration of the formulas of the axioms $\{\varphi_n| n \in \mathbb{N}\}$ of ZFC, it is clear that $N$ will certainly think that $M \models \varphi_n$ for any particular $n \in \mathbb{N}$ analogous to how a nonstandard model of Peano arithmetic has an element $c$ satisfying $c > n$ for any particular $n \in \mathbb{N}$. The problem of course in the case of $N$ is that there may be formulas with nonstandard indices not accounted for just as there will definitely be nonstandard numbers greater than $c$ in the PA example.

If one were to carry out the same proof with the more tedious arithmetization of syntax, then this link may be more apparent.

To a lesser extent, there may also be confusion with the fact that $0^{\sharp}$ provides us with a proper class of $L(\alpha) \preceq L$. This may lead to the question of whether $L$ has its own truth predicate, contradicting Tarski's Theorem. But of course $L$ will only realize that each of these $\varphi^{L(\alpha)}$ is true for any ZFC axiom $\varphi$, and if one attempts to appeal to the arithmetization of syntax, one can begin to see the problem that these $\alpha$ may not (and of course will not) be definable (without parameters) in the constructible universe L.

Since these types of misconceptions can be common among logicians and non-logicians alike, I thought I would ask the highly intelligent mathematicians who have worked through such problems or helped illuminate them to others if they would do so here as well. I think compiling a collection of tidbits of wisdom in this area from the collective perspectives of the MO Community can be illuminating to all. As such, my question is as follows:

What insights can you share regarding the questions of formalizing "is a model of ZFC" in ZFC and the various "paradoxes" that arise?

For example, maybe you can show a related seemingly paradoxical problem and resolve it, or simply share your thoughts on how to avoid such traps of logic.

share|improve this question
    
Since the topic is mentioned, how does one escape from the following "proof" that ZFC is inconsistent? Specifically, ZFC proves Goedel's completeness theorem $\mathrm{Ct}$, so that there is a (transitive) $V'$ in $V$ with $V'\models \mathrm{Ct}$; again, there is a $V''$ in $V'$ with $V'\models \mathrm{Ct}$... this seems to give an infinite decreasing sequence of ordinals in the original model $V$ --- unless $V'$ can be wrong about either of "is a consistent theory" or "has a model". Or maybe I need to check whether $\mathrm{Ct}$ is really a first-order property of a model of set theory! –  some guy on the street Jan 11 '11 at 15:19
    
Why should the completeness thm give you a transitive model of ZFC, even if you live in a universe that thinks that ZFC is consistent? –  Stefan Geschke Jan 11 '11 at 17:12
    
oh, does Mostowski collapse forget stuff? –  some guy on the street Jan 12 '11 at 0:22
3  
No, it does not. But you can only collapse well-founded structures. Even though a model of ZFC thinks it is wellfounded it doesn't have to be. See my answer below. In such a case there is no Mostowski collapse. –  Stefan Geschke Jan 12 '11 at 0:59
    
Also, as Stefan alluded to in his first comment, why do you even expect that the Completeness Theorem should yield a model of ZFC? Despite the fact that $V$ is a model of ZFC, it may think that ZFC is inconsistent so the fact that Ct is true in $V$ wouldn't get you anywhere. Furthermore, even with the assumption that $V$ models the consistency of ZFC, there will have to eventually be some $V^{'(n)}$ in your sequence that either doesn't model the consistency of ZFC or is ill-founded (whereby Stefan's 2nd comment applies) exactly because the true ordinals are well-founded by the $\in$ relation. –  Jason Jan 12 '11 at 2:43

3 Answers 3

I suspect these sorts of problems arise in two ways: ignoring wrongness (e.g. Skolem's paradox, that there are countable models of set theory which believe in uncountable sets) and ignoring first-orderness: First-order theories with infinite models have models of every larger size; but in any universe there is exactly one isomorphism class of complete ordered field --- being a complete ordered field is NOT a first-order property of the field, but a first-order statement about a thing in some universe.

Contrapositivewise, teaching clearly about these two sorts of phenomena ought to help us keep clear of trouble. Unless, of course, ZFC proves itself consistent...

share|improve this answer
1  
I especially like the complete ordered field example because while Skolem's paradox is usually addressed in the context of the downward Löwenheim-Skolem Theorem in a logic class, the fact that the theory of $\mathbb{R}$ is not categorical may not be mentioned in an algebra or an analysis class when presenting the proof of the uniqueness of the Real numbers. –  Jason Jan 11 '11 at 22:34

Most of the confusion usually comes from the fact that there is a difference between what a model of ZFC believes to be a formula, i.e., an object in the model that satisfies the definition of a formula applied in the model, and a real world formula. While every real world formula can be translated into an object in the model, not everything that the model believes to be a formula has an analog in the real world. In particular, not everything that satisfies the definition of being an axiom of ZFC in the model corresponds to a real ZFC axiom. But this type of problem only arises in non-standard models (with a non-wellfounded set of natural numbers). However, the completeness theorem and the compactness theorem usually produce non-standard models.

Another source of confusion is the fact that there can be a model of ZFC without there being any transitive model (or equivalently, any well-founded model) of ZFC.
The point here is that even though ZFC contains the axiom of regularity which says the $\in$-relation is wellfounded, a model of set theory can believe that it is wellfounded while it really is not. This is due to the fact that from we outside we might see infinite decreasing $\in$-sequences, but the model contains none of them (only the individual elements of such a sequence, but not the sequence itself).

share|improve this answer
2  
I completely agree. I think these problems tend to stem from the fact that we study transitive models intensively, and it is easy to forget that some of the absoluteness that we take for granted is not necessarily applicable for the ill-founded models of set theory. To me this is similar to how we can take the implications of choice for granted when we wonder how $\aleph_1$ could ever be measurable. –  Jason Jan 11 '11 at 22:46

Here is a result along the lines you are requesting, which I find beautifully paradoxical.

Theorem. Every model of ZFC has an element that is a model of ZFC. That is, every $M\models ZFC$ has an element $m$, which $M$ thinks is a structure in the language of set theory, a set $m$ and a binary relation $e$ on $m$, such that if we consider externally the set of objects $\bar m=\{\ a\ |\ M\models a\in m\ \}$ with the relation $a\mathrel{\bar e} b\leftrightarrow M\models a\mathrel{e} b$, then $\langle \bar m,\bar e\rangle\models ZFC$.

Many logicians instinctively object to the theorem, on the grounds of the Incompleteness theorem, since we know that $M$ might model $ZFC+\neg\text{Con}(ZFC)$. And it is true that this kind of $M$ can have no model that $M$ thinks is a ZFC model. The paradox is resolved, however, by the kind of issues mentioned in your question and the other answers, that the theorem does not claim that $M$ agrees that $m$ is a model of the ZFC of $M$, but only that it externally is a model of the (actual) ZFC. After all, when $M$ is nonstandard, it may be that $M$ does not agree that $m$ satisfies ZFC, even though $m$ actually is a model of ZFC, since $M$ may have many non-standard axioms that it insists upon.

Proof of theorem. Suppose that $M$ is a model of ZFC. Thus, in particular, ZFC is consistent. If it happens that $M$ is $\omega$-standard, meaning that it has only the standard natural numbers, then $M$ has all the same proofs and axioms in ZFC that we do in the meta-theory, and so $M$ agrees that ZFC is consistent. In this case, by the Completeness theorem applied in $M$, it follows that there is a model $m$ which $M$ thinks satisfies ZFC, and so it really does.

The remaining case occurs when $M$ is not $\omega$-standard. In this case, let $M$ enumerate the axioms of what it thinks of as ZFC in the order of their Goedel numbers. An initial segment of this ordering consists of the standard axioms of ZFC. Every finite collection of those axioms is true in some $(V_\alpha)^M$ by an instance of the Reflection theorem. Thus, since $M$ cannot identify the standard cut of its natural numbers, it follows (by overspill) that there is some nonstandard initial segment of this enumeration that $M$ thinks is true in some $m=(V_\alpha)^M$. Since this initial segment includes all actual instances of the ZFC axioms, it follows that $m$ really is a model of ZFC, even if $M$ does not agree, since it may think that some nonstandard axioms might fail in $M$. QED

Note that in the case that $M$ is $\omega$-nonstandard, then we actually get that a rank initial segment $(V_\alpha)^M$ is a model of ZFC. This is a very nice transitive set from $M$'s perspective.

There are other paradoxical situations that occur with countable computably saturated models of ZFC. First, every such M contains rank initial segment $(V_\alpha)^M$, such that externally, $M$ is isomorphic to $(V_\alpha)^M$. Second, every such $M$ contains an element $m$ which $M$ thinks is an $\omega$-nonstandard model of a fragment of set theory, but externally, we can see that $M\cong m$. Switching perspectives, every such $M$ can be placed into another model $N$, to which it is isomorphic, but which thinks $M$ is nonstandard.

share|improve this answer
    
Hi Joel. This is an elegant proof. Isn't there a uniform argument along the lines of "formula $\phi$ defines a structure m", and for each axiom $\psi$ of ZFC, ZFC proves that "$m\models \psi$", but there is no ZFC proof that "$m\models$ZFC"? –  Andres Caicedo Jan 11 '11 at 21:05
    
Hi Andres (I was expecting to see you here in Oberwolfach!). Well, I guess the proof I give provides your statement, since the structures $m$ I give are each definable in $M$ (but the formula $\phi$ would merely hide the two cases). Did you have in mind a truly uniform argument? –  Joel David Hamkins Jan 11 '11 at 22:07
1  
Oh, I suppose one could give up on the $(V_\alpha)^M$, and just let $\phi$ define the Henkin model for the largest initial segment of the enumeration of the ZFC axioms that are consistent. This necessarily includes all the standard axioms, by the Reflection argument, and has the property you state. –  Joel David Hamkins Jan 11 '11 at 22:22
    
Oh, that's nice! –  Andres Caicedo Jan 11 '11 at 22:24
    
Thanks for the examples and explanation. These are great! –  Jason Jan 11 '11 at 22:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.