I have read several times that assuming Con(ZFC), and using compactness it can be proved the existence of a model of ZFC with an ill-founded $\omega$. How is that? Any reference will be welcome.
[Math] Existence of an $\omega$-nonstandard model of ZFC from compactness
lo.logicmodel-theoryset-theory
Related Solutions
Guillaume :
There are several ways of making sense of forcing. It is useful to be able to move between all these versions, as each may have its specific advantages in some cases.
The approach of consider countable transitive models $M$ and their extensions by explicit construction of generic objects is very useful, although somewhat restrictive, and we do not really need the restrictions it imposes.
For example: One can use a purely syntactical approach, where we transform formulas into forcing statements, and never worry about models. In turn, there are several ways of doing this. We can, by simply manipulating formulas, check that the weakest condition forces the axioms of first order logic, and we can apply modus ponens and the rules about quantifiers to formulas forced by the empty condition. Then we can check that each axiom of ZFC is forced by the empty condition. Finally, we can check that if $p$ is a condition, the theory (without variables, but allowing appropriate names) that it forces is consistent.
(I actually wrote all of this down as a grad student. It is not entirely without pain. One can simplify this brutal approach at times, by using, say, the reflection theorem and a bit of the semantic approach you know of with countable models.)
Another approach is the Boolean-valued models construction. This is due to Dana Scott and Robert Solovay, and it is very flexible and useful. It makes sense over any model. This approach produces a proper class (from the point of view of the original model) and rather than being a model in the usual sense, truth-values are understood as varying over a complete Boolean algebra (the completion of the poset, from the point of view of the model). One can see that there is a natural way of interpreting the ground model as a (classical) substructure of its Boolean-valued extensions, so we can safely argue as if we had an ideal generic extension of the universe. If there are appropriate ultrafilters in the Boolean algebra (say, in the true universe of sets), then we can form a (Boolean) ultrapower and recover an honest model from a Boolean valued extension.
Sometimes, we can actually show that generics over certain ground models exist, and build transitive models even if the original model was uncountable. For example: Assuming appropriate large cardinals, the powet set of many posets in $L$ is actually countable in $V$, so we can find forcing extensions of $L$ as submodels of $V$. A cute example is that if $0^\sharp$ exists and $\kappa=\omega_1$ (of $V$, this is much larger than the $\omega_1$ of $L$), then in $V$ there is an inner model which is a forcing extension of $L$ by the poset ${\rm Col}(\omega,<\kappa)$, so this is a forcing extension of $L$ that computes $\omega_1$ correctly. However, we cannot have (in $V$) an inner model that is a forcing extension of $L$ and computes both $\omega_1$ and $\omega_2$ correctly (this would force $0^\sharp$ to belong to $L$).
As another example, under determinacy, given any (transitive) model of choice, a large initial segment of it is very small, so we can find generics over these models. This is useful to prove results about the models of determinacy, by arguing about its inner models of choice. A similar approach is used in Solovay's model to show Lebesgue measurability of all sets of reals. Essentially, by finding appropriate codes for the sets in small models of choice, and arguing that the sets the codes represent are measurable in these small models, and then using the codes to check that measurability is preserved.
A good reference for this question, as Amit mentioned, is Kunen's book, chapter VII. I strongly recommend that you begin by looking at this book.
If you want to delve deeper: For the Boolean-valued approach, the best reference is John Bell, "Set Theory: Boolean-Valued Models and Independence Proofs" (Oxford Logic Guides), of which the third edition just appeared, in 2005. When Scott and Solovay developed forcing in terms of Boolean algebras, they promised a paper explaining their approach. The paper never quite materialized and somehow morphed into this book by Bell.
I know some books try to avoid the "transitive models" approach since they are only interested in consistency results. I remember James Cummings criticized this avoidance a few years ago in a review (published in the JSL). For example, the countable models approach allows us to prove, using forcing, that $\Sigma^1_1$ sets are Lebesgue measurable (provably in ZFC), by adapting appropriately the argument I sort of hand-waved above about Solovay's model.
(The countable models version of forcing has other advantages. For example, to construct Suslin trees with special properties in $L$, one can proceed by induction on the levels of constructibility, and at appropriate limit stages choose the branches of the partially formed tree to be generic over the stage built so far.)
Once one realizes that forcing is essentially an internal construction, it is clear we do not really need the models we work with to be transitive, or countable, or any such thing. However, it is nice to see how to make explicit sense of the construction in other cases. The clearest presentation of this I have seen is by Woodin. You may want to look at the Woodin-Dales book, "An Introduction to Independence for Analysts", Cambridge UP (1987), and its sequel, "Super-Real Fields: Totally Ordered Fields with Additional Structure" London Mathematical Society Monographs New Series, Oxford UP (1996).
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$. $\Box$
I first learned of this theorem from Brice Halimi, who was visiting in New York in 2011, and who subsequently published his argument in:
Halimi, Brice, Models as universes, Notre Dame J. Formal Logic 58, No. 1, 47-78 (2017). ZBL06686417.
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.
Best Answer
This is a standard application of the Compactness Theorem, and works basically the same in producing nonstandard models of ZFC as it does for producing nonstandard models of PA or real-closed fields.
Consider the theory $T$, in the language of set theory augmented with an additional constant symbol $c$, consisting of all the ZFC axioms, plus the assertions that $c$ is a natural number, but not equal to $0$, not equal to $1$, and so on, including for each natural number $n$ the statement $\varphi_n$ that $c$ is not equal to $n$. (Note that all such $n$ are definable in set theory, and so we use the definition of $n$ in $\varphi_n$ when asserting that $c$ is not $n$.)
If there is a model $M$ of ZFC, then every finite subtheory of $T$ is consistent, since any finite subtheory of $T$ makes only finitely many assertions about $c$, and we may therefore interpret $c$ as any natural number of $M$ not mentioned in the subtheory.
Thus, by compactness, $T$ has a model. Any such model of $T$ will be $\omega$-nonstandard, since the interpretation of $c$ in the model will be a nonstandard natural number.
There are numerous other ways to produce $\omega$-nonstandard models of ZFC from existing models, the most common being ultrapowers.
The conclusion is that if there is any model of ZFC, then there are nonstandard models of ZFC. The converse of this is not true, for if there are any transitive models of ZFC, then there is an $\in$-minimal such model $M$, and being standard, $M$ will have the same arithmetic as the ambient universe, thus thinking Con(ZFC), but being minimal, will have no transitive models of ZFC inside it.