Monday 20 November 2006

set theory - Montague's Reflection Principle and Compactness Theorem

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...

No comments:

Post a Comment