Every countable model of set theory end-extends to a model of V = L
by kamerynwilliams
This theorem has popped up in my life a few times in the past week, and it’s one of the coolest results I know of, so I wanted to share it with the world.
Theorem (Barwise): Every countable transitive model of has an end-extension to a model of .
If and are models of set theory then is an end-extension of if for every and every if then . That is, any new elements in cannot appear as members of old elements, and must come at the end of the epsilon relation. It’s easy to see that if is an elementary end extension of then in fact is a rank-extension of —every new element has rank above the ordinals of . But if we don’t have elementarity then an end-extension can be quite far from a rank-extension. For instance, if is an inner model of then end-extends .
If you’re like me when I first learned of this result, your reaction at this point is probably disbelief. So let’s see why Barwise’s theorem is true. We will use the following version of Shoenfield’s lemma.
Lemma (Shoenfield): Work over and let be a formula without parameters. Then implies .
Let me give a proof that assumes a fragment of choice. Chapter V.8 of Barwise’s Admissible Sets and Structures has a proof that goes through without using any choice. (Thanks to Asaf Karagila for catching my mistake here.)
Proof: The usual version of Shoenfield’s lemma is that (lightface) formulae, i.e. formulae of the form “there is a real so that for all reals some arithmetical property (without parameters) holds”, are absolute between and . Let’s see how to get this other form.
Suppose that is true, where only has bounded quantifiers. Then if is any transitive set containing a witness for we have . There must be such , so by downward Löwenheim–Skolem we get a countable transitive so that . But the assertion that there is countable such is —there is a real coding a well-founded structure so that blah blah. So it must also be true in that there is such an . And things are upward absolute between transitive models, so , as desired. ∎
We can now prove Barwise’s theorem.
Proof of Barwise’s theorem: Let be countable and transitive. We will consider a theory in the logic , the countable admissible fragment of associated with (that is, ). Namely, our theory has as axioms:
- Each axiom of and
- The infinitary -diagram of , i.e. all sentences of the form , where “” is an abbreviation for the -formula defining . (Think of how every hereditarily finite set is definable in .)
Then is definable over by a formula . The point of including the infinitary -diagram of in is that it ensures that any model of must end-extend .
Now suppose towards a contradiction that there is no model of . Thus, . So by the Barwise completeness theorem we get that is true in . (This is where we use the assumption that is countable.) Similar to how ordinary proofs in first-order logic can only use finitely many axioms, infinitary proofs can only use set-many axioms. So thinks that there is a proof of from the axioms of which only uses set-many axioms. A bit more formally, satisfies that there is a set so that every has and there is an infinitary proof of . Stare at that for a moment and convince yourself that this is a assertion (because it is to say that there is an infinitary proof of such and such).
By Shoenfield, we get that satisfies the same thing. And in we have that defines the -theory whose axioms are and the infinitary -diagram of . Call this theory . So we get that there is with so that . But this is impossible, since . So our original assumption that has no model must be false, so has an end-extension to a model of . ∎
Let me put a horizontal rule here to indicate that you should pause for a moment to appreciate the beauty of Barwise’s proof.
Why isn’t this theorem paradoxical? Suppose we started with, say, a countable transitive model of exists, where this model has the real . How could we possibly end-extend to a model of ? Wouldn’t that contradict the well-known fact that is not in ?
The answer is that the end-extension Barwise gives us must, in this case, be nonstandard. Our end-extension sees the real and thinks that it is constructible, but it only shows up in for some ersatz, ill-founded ‘ordinal’ . As a consequence, the end-extension does not recognize that the set we externally can see is really is . It thinks it’s just some constructible real. Similarly, we could start with a model which has measurable cardinals, or supercompact cardinals, or any other creature of the higher infinite, and the end-extension will think that all the witnessing measures are constructible (but appearing at some nonstandard stage in the construction of ).
So what Barwise gives us is another example of the nonabsoluteness phenomenon for nonstandard models. The classical example of this is provability, where end-extending a model of arithmetic can change what is provable. The standard model thinks that there is no proof of 0=1 from the axioms of Peano arithmetic, but if we end extend to the right nonstandard model we can get such a ‘proof’. Or phrased in terms of Turing machines: the TM which searches for a proof of 0=1 from the axioms of PA doesn’t halt. But it can halt if we wait a nonstandard amount of time (in the right model). And in light of Koepke’s work on the connection between infinite time&space Turing machines and constructibility, the Barwise phenomenon can also be phrased in terms of computability: While is not computable (from finitely many ordinal parameters) by a Turing machine with time and space, it does become ‘computable’ if we allow a nonstandard amount of time and space (in the right model).
Finally, let me remark that Barwise’s theorem also holds for countable ill-founded models. But the proof requires going through the admissible cover. This is a rather fantastic piece of machinery (also due to Barwise), but expositing it would be too much for this blog post. See the appendix to Barwise’s Admissible Sets and Structures for facts about the admissible cover, as well as a proof for the ill-founded version of his theorem.
For the Levy–Shoenfield Absoluteness Lemma, how do you get a countable transitive model without using DC? (Or in other words, how do you prove the Löwenheim–Skolem theorem without DC (quick answer: you can’t, and you don’t)).
However, it seems to me that the Barwise compactness theorem should let you prove the lemma since it proves that every model of ZF is a transitive part of a model of V=L (and thus of DC). But it would be circular.
As far as the appeal to sharps as a counterintuitive answer, note that just by Shoenfield’s usual absoluteness lemma, if 0# lies in a transitive model, then there is a transitive model of ZFC+0# in L already. How is that possible? Well, it’s not the “real” sharp, it’s just a fake one.
I think that the important consequence of Shoenfield’s Absoluteness is that the true set theoretic meta-theory is irrelevant, since if we care about forcing, about inner models, and we care about countable transitive models, then the universe can be L just as well. Of course, we already know that, because we also know that we can formalize the whole damn thing in PRA as a syntactic manipulation of proofs…
D’oh, that was a silly error on my part. Thanks for catching the mistake.
(The lemma still holds in ZF. Barwise has a proof in his book, but it’s more complicated because it can’t just appeal to Löwenheim–Skolem.)
What makes Barwise’s theorem different is that it works even if the model has the real . So we get a model which thinks that the set, which we from recognize is , is constructible. (But which only shows up at some ill-founded stage.) With the fake sharps we can recognize they are fake by building along an actual ordinal, but higher than the height of the model.