Model theory is really meta, so you will have to pay attention here.
Roughly, a “model of ” is a set with a binary relation that satisfies the axioms, just as a group is a set with a binary operation that satisfies the group axioms. Unfortunately, unlike with groups, it is very hard for me to give interesting examples of models, for the simple reason that we are literally trying to model the entire universe.
Prototypical example for this section: obeys , is a model for inaccessible (later).
Definition 1 A model consists of a set and a binary relation . (The relation is the “” for the model.)
Remark 2 I’m only considering set-sized models where is a set. Experts may be aware that I can actually play with being a class, but that would require too much care for now.
If you have a model, you can ask certain things about it. For example, you can ask “does it satisfy ?”. Let me give you an example of what I mean, and then make it rigorous.
Example 3 (A Stupid Model) Let’s take . This is not a very good model of , but let’s see if we can make sense of some of the first few axioms.
- satisfies , which is the sentence
This just follows from the fact that is actually .
- satisfies , which is the sentence
Namely, take .
- does not satisfy , since is not in , even though .
- Miraculously, satisfies , since for any , is (unless ). The Union axiom statements that
An important thing to notice is that the “” ranges only over the sets in the model of the universe, .
Example 4 (Important: This Stupid Model Satisfies ) Most incredibly of all: satisfies . This is a really important example. You might think this is ridiculous. Look at . The power set of this is which is not in the model, right?
Well, let’s look more closely at . It states that:
What happens if we set ? Well, actually, we claim that works. The key point is “for all ” — this only ranges over the objects in . In , the only subsets of are , and . The “set” in the “real world” (in ) is not a set in the model .
In particular, you might say that in this strange new world, we have , since really does have only subsets.
Example 5 (Sentences with Parameters) The sentences we ask of our model are allowed to have “parameters” as well. For example, if as before then satisfies the sentence
2. Sentences and Satisfaction
With this intuitive notion, we can define what it means for a model to satisfy a sentence.
Definition 6 Note that any sentence can be written in one of the following five forms:
- (“not ”) for some shorter sentence
- (“` or ”) for some shorter sentences ,
- (“exists ”) for some shorter sentence .
Ques 7 What happened to (and) and (for all)? (Hint: use .)
Often (almost always, actually) we will proceed by so-called “induction on formula complexity”, meaning that we define or prove something by induction using this. Note that we require all formulas to be finite.
Now suppose we have a sentence , like or , plus a model . We want to ask whether satisfies .
To give meaning to this, we have to designate certain variables as parameters. For example, if I asked you “Does ?” the first question you would ask is what and are. So , would be parameters: I have to give them values for this sentence to make sense.
On the other hand, if I asked you “Does ?” then you would just say “yes”. In this case, and are not parameters. In general, parameters are those variables whose meaning is not given by some or .
In what follows, we will let denote a formula , whose parameters are , \dots, . Note that possibly , for example all axioms have no parameters.
Ques 8 Try to guess the definition of satisfaction before reading it below. (It’s not very hard to guess!)
Definition 9 Let be a model. Let be a sentence, and let . We will define a relation
and say satisfies the sentence with parameters .
The relationship is defined by induction on formula complexity as follows:
- If is “” then .
- If is “” then .
(This is what we mean by “ interprets ”.)
- If is “” then .
- If is “” then means for some .
- Most important case: suppose is . Then if and only if
Note that has one extra parameter.
Notice where the information of the model actually gets used. We only ever use in interpreting ; unsurprising. But we only ever use the set when we are running over (and hence ). That’s well-worth keeping in mind: The behavior of a model essentially comes from and , which search through the entire model .
Definition 10 A model of is a model satisfying all axioms.
We are especially interested in models of the form , where is a transitive set. (We want our universe to be transitive, otherwise we would have elements of sets which are not themselves in the universe, which is very strange.) Such a model is called a transitive model. If is a transitive set, the model will be abbreviated to just .
Definition 11 An inner model of is a transitive model satisfying .
3. The Levy Hierarchy
Prototypical example for this section: is absolute. The axiom is , is .
A key point to remember is that the behavior of a model is largely determined by and . It turns out we can say even more than this.
Consider a formula such as
which checks whether a given set has a nonempty element. Technically, this has an “” in it. But somehow this does not really search over the entire model, because it is bounded to search in . That is, we might informally rewrite this as
which doesn’t fit into the strict form, but points out that we are only looking over . We call such a quantifier a bounded quantifier.
We like sentences with bounded quantifiers because they designate properties which are absolute over transitive models. It doesn’t matter how strange your surrounding model is. As long as is transitive,
will always hold. Similarly, the sentence
Sentences with this property are called or .
The situation is different with a sentence like
which in English means “ is the power set of ”, or just . The is not bounded here. This weirdness is what allows things like
which was our stupid example earlier. The sentence consists of an unbounded followed by an absolute sentence, so we say it is .
More generally, the Levy hierarchy keeps track of how bounded our quantifiers are. Specifically,
- Formulas which have only bounded quantifiers are .
- Formulas of the form where is are consider .
- Formulas of the form where is are consider .
(A formula which is both and is called , but we won’t use this except for .)
Example 12 (Examples of Sentences)
- The sentences , , as discussed above.
- The formula “ is transitive” can be expanded as a sentence.
- The formula “ is an ordinal” can be expanded as a sentence.
Exercise 13 Write out the expansions for “ is transitive” and “ is ordinal” in a form.
Example 14 (More Complex Formulas)
- The axiom is ; it is , and is .
- The formula “” is , as discussed above.
- The formula “ is countable” is . One way to phrase it is “ an injective map ”, which necessarily has an unbounded “”.
- The axiom is :
4. Substructures, and Tarski-Vaught
Let and be models.
Definition 15 We say that if and agrees with ; we say is a substructure of .
That’s boring. The good part is:
Definition 16 We say , or is an elementary substructure of , if for every sentence and parameters , we have
In other words, and agree on every sentence possible. Note that the have to come from ; if the came from then asking something of wouldn’t make sense.
Let’s ask now: how would fail to be true? If we look at the possibly sentences, none of the atomic formulas, nor the “” and “”, are going to cause issues.
The intuition you should be getting by now is that things go wrong once we hit and . They won’t go wrong for bounded quantifiers. But unbounded quantifiers search the entire model, and that’s where things go wrong.
To give a “concrete example”: imagine is MIT, and is the state of Massachusetts. If thinks there exist hackers at MIT, certainly there exist hackers in Massachusetts. Where things go wrong is something like:
This is true for because we can take the witness , say. But it’s false for , because at MIT all courses are numbered or something similar. The issue is that the witness for statements in do not necessarily propagate up down to witnesses for , even though they do from to .
The Tarski-Vaught test says this is the only impediment: if every witness in can be replaced by one in then .
Lemma 17 (Tarski-Vaught) Let . Then if and only if for every sentence and parameters : if there is a witness to then there is a witness to .
Proof: Easy after the above discussion. To formalize it, use induction on formula complexity.
5. Obtaining the Axioms of
Extending the above ideas, one can obtain without much difficulty the following. The idea is that almost all the axioms are just claims about certain desired sets, and so verifying an axiom reduces to checking some appropriate “closure” condition: that the witness to the axiom is actually in the model.
For example, the axiom is “”, and so we’re happy as long as , which is of course true for any nonempty transitive set .
- satisfies , , .
- if .
- if .
- if .
- if for every and every function which is -definable with parameters, we have as well.
- as long as .
Here, a set is -definable with parameters if it can be realized as
for some (fixed) choice of parameters . We allow , in which case we say is -definable without parameters. Note that need not itself be in ! As a trivial example, is -definable without parameters (just take to always be true), and certainly we do not have .
Exercise 19 Verify (i)-(iv) above.
Remark 20 Converses to the statements of Lemma 18 are true for all claims other than (vii).
6. Mostowski Collapse
Up until now I have been only talking about transitive models, because they were easier to think about. Here’s a second, better reason we might only care about transitive models.
Lemma 21 (Mostowski Collapse) Let be a model such that . Then there exists an isomorphism for a transitive model .
This is also called the transitive collapse. In fact, both and are unique.
Proof: The idea behind the proof is very simple. Since is well-founded and extensional, we can look at the -minimal element of with respect to . Clearly, we want to send that to .
Then we take the next-smallest set under , and send it to . We “keep doing this”; it’s not hard to see this does exactly what we want.
To formalize, define by transfinite recursion:
This , by construction, does the trick.
The picture of this is quite “collapsing” the elements of down to the bottom of , hence the name.
7. Adding an Inaccessible, Skolem Hulls, and Going Insane
Prototypical example for this section:
At this point you might be asking, well, where’s my model of ?
I unfortunately have to admit now: can never prove that there is a model of (unless is inconsistent, but that would be even worse). This is a result called Gödel’s Incompleteness Theorem.
Nonetheless, with some very modest assumptions added, we can actually show that a model does exist: for example, assuming that there exists a strongly inaccessible cardinal would do the trick, it turns out will be such a model. Intuitively you can see why: is so big that any set of rank lower than it can’t escape it even if we take their power sets, or any other method that lets us do.
More pessimistically, this shows that it’s impossible to prove in that such a exists. Nonetheless, we now proceed under for convenience, which adds the existence of such a as a final axiom. So we now have a model to play with. Joy!
Great. Now we do something really crazy.
Theorem 22 (Countable Transitive Model) Assume . Then there exists a transitive model of such that is a countable set.
Proof: Fasten your seat belts.
Start with the set . Then for every integer , we do the following to get .
- Start with containing very element of .
- Consider a formula and in . Suppose that thinks there is an for which
We then add in the element to .
- We do this for every possible formula in the language of set theory. We also have to put in every possible set of parameters from the previous set .
At every step is countable. Reason: there are countably many possible finite sets of parameters in , and countably many possible formulas, so in total we only ever add in countably many things at each step. This exhibits an infinite nested sequence of countable sets
None of these is a substructure of , because each by relies on witnesses in . So we instead take the union:
This satisfies the Tarski-Vaught test, and is countable.
There is one minor caveat: might not be transitive. We don’t care, because we just take its Mostowski collapse.
Please take a moment to admire how insane this is. It hinges irrevocably on the fact that there are countably many sentences we can write down.
Remark 23 This proof relies heavily on the Axiom of Choice when we add in the element to . Without Choice, there is no way of making these decisions all at once.
Usually, the right way to formalize the Axiom of Choice usage is, for every formula , to pre-commit (at the very beginning) to a function , such that given any will spit out the suitable value of (if one exists). Personally, I think this is hiding the spirit of the proof, but it does make it clear how exactly Choice is being used.
These ‘s have a name: Skolem functions.
The trick we used in the proof works in more general settings:
Theorem 24 (Downward Löwenheim-Skolem Theorem) Let be a model, and . Then there exists a set (called the Skolem hull of ) with , such that , and
In our case, what we did was simply take to be the empty set.
Ques 25 Prove this. (Exactly the same proof as before.)
8. FAQ’s on Countable Models
The most common one is “how is this possible?”, with runner-up “what just happened”.
Let me do my best to answer the first question. It seems like there are two things running up against each other:
- is a transitive model of , but its universe is uncountable.
- tells us there are uncountable sets!
(This has confused so many people it has a name, Skolem’s paradox.)
The reason this works I actually pointed out earlier: countability is not absolute, it is a notion.
Recall that a set is countable if there exists an injective map . The first statement just says that in the universe , there is a injective map . In particular, for any (hence , since is transitive), is countable in . This is the content of the first statement.
But for to be a model of , only has to think statements in are true. More to the point, the fact that tells us there are uncountable sets means
In other words,
The key point is the searches only functions in our tiny model . It is true that in the “real world” , there are injective functions . But has no idea they exist! It is a brain in a vat: is oblivious to any information outside it.
So in fact, every ordinal which appears in is countable in the real world. It is just not countable in . Since , is going to think there is some smallest uncountable cardinal, say . It will be the smallest (infinite) ordinal in with the property that there is no bijection in the model between and . However, we necessarily know that such a bijection is going to exist in the real world .
Put another way, cardinalities in can look vastly different from those in the real world, because cardinality is measured by bijections, which I guess is inevitable, but leads to chaos.
9. Picturing Inner Models
Here is a picture of a countable transitive model .
Note that and must agree on finite sets, since every finite set has a formula that can express it. However, past the model and the true universe start to diverge.
The entire model is countable, so it only occupies a small portion of the universe, below the first uncountable cardinal (where the superscript means “of the true universe ”). The ordinals in are precisely the ordinals of which happen to live inside the model, because the sentence “ is an ordinal” is absolute. On the other hand, has only a portion of these ordinals, since it is only a lowly set, and a countable set at that. To denote the ordinals of , we write , where the superscript means “the ordinals as computed in ”. Similarly, will now denote the “set of true ordinals”.
Nonetheless, the model has its own version of the first uncountable cardinal . In the true universe, is countable (below ), but the necessary bijection witnessing this might not be inside . That’s why can think is uncountable, even if it is a countable cardinal in the original universe.
So our model is a brain in a vat. It happens to believe all the axioms of , and so every statement that is true in could conceivably be true in as well. But can’t see the universe around it; it has no idea that what it believes is the uncountable is really just an ordinary countable cardinal.
Problem 1 Show that for any transitive model , the set of ordinals in is itself some ordinal.
Problem 2 Assume . Show that
- If is , then .
- If is , then .
- If is , then .
Problem 3 (Reflection) Let be an inaccessible cardinal such that for all . Prove that for any there exists such that ; in other words, the set of such that is unbounded in . This means that properties of reflect down to properties of .
Problem 4 (Inaccessible Cardinal Produce Models) Let be an inaccessible cardinal. Prove that is a model of .