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

Here's a question I can't answer by myself: The Reflection Principle in Set Theory states for each formula $\phi(v_{1},...,v_{n})$ and for each set M there exists a set N which extends M such that the following holds

$\phi^{N} (x_{1},...,x_{n})$ iff $\phi (x_{1},...,x_{n})$ for all $x_{1},...x_{n} \in N$

Thus if $\sigma$ is a true sentence then the RFP yields a model of it and as a consequence any finite set of axioms of ZFC has a model (as a consequence ZFC is not finitely axiomatizable by Gödel's Second Incompleteness Theorem)

But why can't I just use now the Compactness Theorem (stating that each infinte set of formulas such that each finite subset has a model, has a model itself) to obtain a model of ZFC (which is actually impossible)??

share|improve this question
    
I haven't really done set theory of this sort since my student days (and not a whole lot even then), but how is it impossible to get a model of ZFC? If you know this, then it seems that you know that ZFS is inconsistent, which nobody knows (as far as I know). There must be some context here that I haven't understood, perhaps. –  Harald Hanche-Olsen Mar 19 '10 at 20:29
    
Harald: it's not that the consistency of ZFC was in doubt. The question was basically, how come ZFC cannot prove its own consistency/that it has a model in a certain way (via the reflection theorem), contra Goedel's second incompleteness theorem? I've spelt out where this approach falters below. –  Sridhar Ramesh Mar 19 '10 at 20:39
    
Ah, is that what he was driving at … –  Harald Hanche-Olsen Mar 19 '10 at 21:12
3  
The Reflection Principle should be associated with Lévy (1960) as well as Montague (1961). –  Joel David Hamkins Mar 20 '10 at 1:55

2 Answers 2

up vote 17 down vote accepted

For any finite set of axioms K of ZFC, ZFC proves "K has a model", via the reflection principle as you note. However, ZFC does not prove "for any finite set of axioms K of ZFC, K has a model". The distinction between these two is what prevents ZFC from proving that ZFC has a model.

(That is, even though, as you note, ZFC proves "if every finite set of axioms K of ZFC has a model, then ZFC has a model", as ZFC proves compactness, it does not follow that ZFC proves the consequent of this implication, as in fact ZFC does not prove the antecedent; ZFC only proves each particular instance of the antecedent, but not the universal statement itself.)

share|improve this answer
    
Thank you very much Sridhar. –  Stefan Hoffelner Mar 19 '10 at 20:51

As Sridhar already explained, Lévy–Montague Reflection is a theorem scheme and not a single theorem which resolves the apparent contradiction, but here are a few additional cool facts.

First, note that ZFC is not finitely axiomatizable (otherwise we would indeed have a contradiction) but there is a recursive listing of the axioms of ZFC. Let's fix such a listing $\phi_0$,$\phi_1$,$\phi_2$,... If $M$ is a model of ZFC, then either $M$ is an $\omega$-model (i.e. the finite ordinals of $M$ are truly finite) or it is not (i.e. $M$ has some nonstandard finite ordinals). Let's see what happens in each case.

Suppose first that $M$ is an $\omega$-model. The recursive listing $\phi_0$,$\phi_1$,$\phi_2$,... exists in $M$ and, by Lévy–Montague, people living in $M$ believe that $\{\phi_0,\ldots,\phi_n\}$ has a model for each $n < \omega$. Since people living in $M$ also believe in the Compactness Theorem, they also believe that there is a model of ZFC. This is surprising, but note that the hypothesis that $M$ is an $\omega$-model is essential since without it we there is no reason for $M$'s notion of finite to agree with ours. This is where your initial reasoning strayed, you naturally assumed that every model of ZFC was an $\omega$-model.

Suppose now that $M$ is not an $\omega$-model. The recursive listing $\phi_0$,$\phi_1$,$\phi_2$,... makes sense in $M$, but since $M$ has nonstandard finite ordinals this listing continues beyond the true $\omega$ and people who live in $M$ believe that these nonstandard $\phi_N$'s are real axioms of ZFC! By Lévy–Montague, $M$ believes that $\{\phi_0,\ldots,\phi_n\}$ has a model for every standard $n$, but since Lévy–Montague Reflection doesn't say anything about nonstandard axioms, there may be some nonstandard finite ordinal $N$ in $M$ such that people living in $M$ do not believe that the nonstandard finite set $\{\phi_0,\ldots,\phi_N\}$ has a model.

Now here is a funny thing that was pointed out by Joel David Hamkins in answer to another question. Suppose $M$ is a model of ZFC + ¬Con(ZFC). Since people in $M$ believe that their finite ordinals are wellordered, there must be a first finite ordinal $N$ in $M$ such that $\{\phi_0,\ldots,\phi_N\}$ has no model in $M$. This $N$ must be nonstandard finite ordinal, and so must its predecessor $N-1$. By minimality of $N$, people in $M$ believe that $\{\phi_0,\ldots,\phi_{N-1}\}$ does have a model. Let $M'$ be such a model. Note that $M' \models \phi_n$ for every standard axiom $\phi_n$ since $n < N-1$. Therefore, although people living in $M$ certainly don't believe it, this $M'$ is in fact a model of ZFC!!!

Thus, Lévy–Montague Reflection does imply that every model of ZFC contains another model of ZFC, but the models are not necessarily aware of that fact...

share|improve this answer
    
Thank you very much for your answer. There is something I don't understand though: In your third break you write:" ...by Montague people living in $M$ believe that $\{ \phi_{0},...,\phi_{n} \}$ has a model for each $n< \omega$." And now you conclude with compactness that $M$ thinks there is a model of ZFC. But as Sridhar pointed out, ZFC does not prove " for any finite subset of axioms ZFC, there exists a model". Hence $M$ does not believe that $\{ \phi_{0},..,\phi_{n} \}$ has a model for each $n< \omega$ and one cannot derive that $M$ thinks that "there is a model of ZFC". Am I wrong? –  Stefan Hoffelner Mar 20 '10 at 10:16
    
Oktan, what François argued was that for any (standard) n, the people in M agree that the size n fragment of ZFC is consistent. But since M has no nonstandard natural numbers, this exhausts all of the natural numbers of M, and so M will believe the universal statement, that all finite fragments of ZFC are consistent. And this implies that ZFC is consistent. You wouldn't be able to make these last steps of the argument if M had a nonstandard omega, precisely because as Sridhar and François point out, you only get the Reflection Principle for standard finitely many statements. –  Joel David Hamkins Mar 20 '10 at 11:58
    
Thank you again. Your answers were really an eye-opener. Made my day –  Stefan Hoffelner Mar 20 '10 at 16:30
    
@oktan: It's a wonderful question that puzzles every novice set theorist at some point. I'm glad you gave us the opportunity to answer it here. –  François G. Dorais Mar 20 '10 at 19:25
    
@Joel: By the way, I'm sorry for "stealing" your cool fact. I waited a while before posting it, but you didn't seem to be around at the time and I couldn't bear not mentioning it... –  François G. Dorais Mar 20 '10 at 19:29

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.