(An earlier version of this had a terribly false statement about transitive models of ZF. It has been fixed.)
My goal with the next few posts is to present one of my favorite forcing arguments:
Let be the -product of the Cohen forcing with full support. Forcing with collapses the reals.
We need a fair bit of background to get there. Instead of dumping a bunch of unmotivated information about forcing and collapsing cardinals on you just to get this one result, I’m going to take a more circuitous route and see some cool things along the way. Today, we’re talking about models of set theory. In particular:
(Assuming ZF is consistent,) there are non-well-founded models of ZF.
If you’re familiar with the ZF axioms, this may seem strange, since the axiom of foundation seems to say that the universe is well-founded. A bit of model theory will show us what’s going on.
A brief technical point: for all of the posts “Towards forcing”, the metasystem is ZF, so a theorem like “All foos are bar” really means . This distinction may seem pedantic, but it does become important when discussing models of set theory. Since we’re discussing the model theory of ZF, using ZF as the metasystem brings certain technical problems: we cannot prove in ZF that ZF has any models. There are lots of ways around this; the easy (albeit unsatisfying) way is: Assume ZF is consistent. From here on, I’ll leave this implicit most of the time, so our theorem “all foos are bar” should be read .
If you haven’t studied much logic or set theory, I may be starting to lose you. So let’s back up a bit: what’s a “model of set theory” anyway? First,
Definition. A relational structure is a set together with a binary relation .
The idea is that a “set theory” will be a set of rules governing a binary relation; ZF, for example is simply such a set of rules. A model of set theory is a relational structure: a set which represents the universe, together with the relation we consider membership. Of course, there are certain things we expect from sets, certain axioms we expect our membership relation to satisfy.
In order to talk about a “theory”, we need these axioms to be properties of the theory, rather than properties of the model; that is, they need to be first order. A first-order property is one which can be written as a (set of) first order formulas. A formula is first order if it only uses variables, logical symbols (, , etc.) and whatever “extra symbols” we’ve added to our language. In this case, our only extra symbol is . Then, given a (first order) formula , we can interpret in a structure by replacing a quantifier with , and replacing the symbol with the relation , to get a statement which the structure either satisfies or doesn’t.
With a first order theory, anything which has meaning “in the theory” can be interpreted in the same way as a formula.. For example, if I can define some set in ZF, then in any model of ZF (that is, in any relational structure satisfying all the ZF axioms), there is some “set” (object of ) , called the interpretation of . A convenient intuition is that “ thinks that is .”
We’ll be very liberal with what is required to call a relational structure a “model of set theory” and only impose the axiom of extensionality:
Definition. A model of set theory is a relational structure which satisfies the axiom of extensionality. That is, In English: x is equal to y if and only if precisely when .
This relation doesn’t have to be “real” membership–it can be anything we like, so long as it’s extensional. Here’s an example: Let the universe be and the “membership relation” be the usual ordering . This is extensional, since for any we have either or , but not both.
And a non-example: Let be the Cantor tree (the complete binary tree), and for two vertices , say iff is a child of . This is a relational structure, but it's not a model of set theory, since the left and right child of any node have the same "elements".
You’re probably familiar with induction for numbers, and perhaps “structural induction” on, say, the structure of formulas or graphs. Very often you can do induction over a relational structure in much the same way: Given a relational structure and a property , we can prove $\forall x\in V, P(x)$ by proving for each that . However, we need to impose a condition called “well-foundedness” on to avoid “infinite loops”.
Definition. A relational structure is called well-founded if for every subset , there is an element such that .
If we think of as being “order-like”, this is just saying that every subset of has an -least element. The condition of well-foundedness ensures that there is no infinite descent in . But notice, we make critical use of in the definition of well-foundedness. In fact, well-foundedness is not a first order property! In other words, we can’t say “V is well-founded” as an axiom.
To get around this, we need to come up with a local version of well-foundedness. Instead of taking all subsets of , what if we only take the subsets for some ? This allows us to write
Definition. The Axiom of Foundation is the formula . Again in English: For every element in our structure, if isn’t “empty”, then contains an element “disjoint” from .
The example structure above satisfies the axiom of foundation. In fact, this structure is well-founded. An example which satisfies the axiom of foundation, but isn’t well-founded is the set of negative integers, with iff (the predecessor relation). Here, every “set” has exactly one element, which is clearly disjoint from it so foundation is satisfied, but any is the successor of some other non-negative integer, so the structure is not well-founded.
From the title of the post, we can stop there, but really, we’re interested in non-well-founded models of ZF, so we have to do a little more work.
A more interesting model of foundation is the structure . If you aren’t familiar with the cumulative hierarchy, is the set , and is the real, actual membership relation (in our metasystem), just restricted to . Besides being a model of all ZFC axioms except infinity, this structure has two very interesting properties:
- is a transitive set, meaning that every element is a subset of .
- The relation is, well, actually the membership relation.
Such models are called transitive models. Transitive models are important because,
Theorem. (Mostowski Collapse). Let be an extensional, well-founded relational structure (i.e., a well-founded model of set theory). Then is canonically isomorphic to a unique transitive model. (“canonically isomorphic” means there is a unique isomorphism.)
I won’t go into the proof, but the sketch is: Define (where is the universe of sets) recursively by . Some simple induction (and the axiom of replacement) gives us that the image of is a transitive set, and the isomorphism follows directly. Uniqueness is proved by induction.
So far, we’ve been talking about models of set theory in general. Now let’s jump all the way to models of ZF: that is, relational structures that satisfy all the ZFC axioms. We can finally prove
Theorem. (If ZF is consistent), then ZF has non-well-founded models.
Proof. Suppose ZF is consistent. If there are no well-founded models then we are done. Otherwise, by Mostowski’s collapse, we may consider only those well-founded models which are transitive. The ordering given by on transitive models is well-founded, so we have a minimal transitive model, .
The interpretation of internal to must also be a model of ZF. But it cannot be transitive, as is the minimal transitive model. That is is a non-well-founded model of ZF.
There are several other ways to prove that ZF has non-well-founded models. Most of them are actually more intuitive, but they don’t hit the points I want to hit.