I have found a new proof of the Barwise extension theorem, that wonderful yet quirky result of classical admissible set theory, which says that every countable model of set theory can be extended to a model of .
Barwise Extension Theorem. (Barwise 1971) Every countable model of set theory has an end-extension to a model of .

The Barwise extension theorem is both (i) a technical culmination of the pioneering methods of Barwise in admissible set theory and infinitary logic, including the Barwise compactness and completeness theorems and the admissible cover, but also (ii) one of those rare mathematical theorems that is saturated with significance for the philosophy of mathematics and particularly the philosophy of set theory. I discussed the theorem and its philosophical significance at length in my paper, The multiverse perspective on the axiom of constructibility, where I argued that it can change how we look upon the axiom of constructibility and whether this axiom should be considered ‘restrictive,’ as it often is in set theory. Ultimately, the Barwise extension theorem shows how wrong a model of set theory can be, if we should entertain the idea that the set-theoretic universe continues growing beyond it.
Regarding my new proof, below, however, what I find especially interesting about it, if not surprising in light of (i) above, is that it makes no use of Barwise compactness or completeness and indeed, no use of infinitary logic at all! Instead, the new proof uses only classical methods of descriptive set theory concerning the representation of sets with well-founded trees, the Levy and Shoenfield absoluteness theorems, the reflection theorem and the Keisler-Morley theorem on elementary extensions via definable ultrapowers. Like the Barwise proof, my proof splits into cases depending on whether the model is standard or nonstandard, but another interesting thing about it is that with my proof, it is the -nonstandard case that is easier, whereas with the Barwise proof, the transitive case was easiest, since one only needed to resort to the admissible cover when was ill-founded. Barwise splits into cases on well-founded/ill-founded, whereas in my argument, the cases are -standard/-nonstandard.
To clarify the terms, an end-extension of a model of set theory is another model , such that the first is a substructure of the second, so that and , but further, the new model does not add new elements to sets in . In other words, is an -initial segment of , or more precisely: if , then and hence .
Set theory, of course, overflows with instances of end-extensions. For example, the rank-initial segments end-extend to their higher instances , when ; similarly, the hierarchy of the constructible universe are end-extensions; indeed any transitive set end-extends to all its supersets. The set-theoretic universe is an end-extension of the constructible universe and every forcing extension is an end-extension of its ground model , even when nonstandard. (In particular, one should not confuse end-extensions with rank-extensions, also known as top-extensions, where one insists that all the new sets have higher rank than any ordinal in the smaller model.)
Let’s get into the proof.
Proof. Suppose that is a model of set theory. Consider first the case that is -nonstandard. For any particular standard natural number , the reflection theorem ensures that there are arbitrarily high satisfying , where refers to the first axioms of in a fixed computable enumeration by length. In particular, every countable transitive set has an end-extension to a model of . By overspill (that is, since the standard cut is not definable), there must be some nonstandard for which thinks that every countable transitive set has an end-extension to a model of , which we may assume is countable. This is a statement about , which will therefore also be true in , by the Shoenfield absolutenss theorem. It will also be true in all the elementary extensions of , as well as in their forcing extensions. And indeed, by the Keisler-Morley theorem, the model has an elementary top extension . Let be a new ordinal on top of , and let be the -rank-initial segment of , which is a top-extension of . Let be a forcing extension in which has become countable. Since the statement is true in , there is an end-extension of to a model that thinks satisfies . Since is nonstandard, this theory includes all the axioms, and since end-extends , we have found an end-extension of to a model of , as desired.
It remains to consider the case where is -standard. By the Keisler-Morley theorem, let be an elementary top-extension of . Let be an ordinal of above , and consider the corresponding rank-initial segment , which is a transitive set in that covers . If has an end-extension to a model of , then we’re done, since such a model would also end-extend . So assume toward contradiction that there is no such end-extension of . Let be a forcing extension in which has become countable. The assertion that has no end-extension to a model of is actually true and hence true in . This is a assertion there about the real coding . Every such assertion has a canonically associated tree, which is well-founded exactly when the statement is true. Since the statement is true in , this tree has some countable rank there. Since these models have the standard , the tree associated with the statement is the same for us as inside the model, and since the statement is actually true, the tree is actually well founded. So the rank must come from the well-founded part of the model.
If happens to be countable in , then consider the assertion, “there is a countable transitive set, such that the assertion that it has no end-extension to a model of has rank .” This is a assertion, since it is witnessed by the countable transitive set and the ranking function of the tree associated with the non-extension assertion. Since the parameters are countable, it follows by Levy reflection that the statement is true in . So has a countable transitive set, such that the assertion that it has no end-extension to a model of has rank . But since is actually well-founded, the statement would have to be actually true; but it isn’t, since itself is such an extension, a contradiction.
So we may assume is uncountable in . In this case, since was actually well-ordered, it follows that is well-founded beyond its . Consider the statement “there is a countable transitive set having no end-extension to a model of .” This is a sentence, which is true in by our assumption about , and so by Shoenfield absoluteness, it is true in and hence also . So thinks there is a countable transitive set having no end-extension to a model of . This is a assertion about , whose truth is witnessed in by a ranking of the associated tree. Since this rank would be countable in and this model is well-founded up to its , the tree must be actually well-founded. But this is impossible, since it is not actually true that has no such end-extension, since itself is such an end-extension of . Contradiction.
One can prove a somewhat stronger version of the theorem, as follows.
Theorem. For any countable model of , with an inner model , and any statement true in , there is an end-extension of to a model of . Furthermore, one can arrange that every set of is countable in the extension model.
In particular, one can find end-extensions of , for any statement true in .
Proof. Carry out the same proof as above, except in all the statements, ask for end-extensions of , instead of end-extensions of , and also ask that the set in question become countable in that extension. The final contradictions are obtained by the fact that the countable transitive sets in do have end-extensions like that, in which they are countable, since is such an end-extension.
For example, we can make the following further examples.
Corollaries.
- Every countable model of with a measurable cardinal has an end-extension to a model of .
- Every countable model of with extender-based large cardinals has an end-extension to a model satisfying .
- Every countable model of with infinitely many Woodin cardinals has an end-extension to a model of .
And in each case, we can furthermore arrange that every set of is countable in the extension model .
This proof grew out of a project on the -definable universal finite set, which I am currently undertaking with Kameryn Williams and Philip Welch.
Jon Barwise. Infinitary methods in the model theory of set theory. In Logic
Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969), pages
53–66. North-Holland, Amsterdam, 1971.
This new proof is very nice to see, thanks for posting it.
I just have one comment: in case a countable model of ZF is not -standard, then there is a self-embedding theorem that yields Barwise’s result as a corollary.
To state the relevant self-embedding theorem, I will use the notation to denote the submodel of consisting of the hereditrarily countable sets in the sense of the inner model .
Here is the relevant theorem: Suppose is a countable model of ZF that is not -standard. Then there is a embedding of into such that is an initial submodel of (i.e., ends extends j(M)$).
The above theorem will appear in a joint paper of Zach McKenzie and myself; it is proved by an appropriate variation of the proof of Friedman’s self-embedding theorem.
Thanks, Ali, that is interesting! I’ll look forward to the paper. It reminds me a little of the version of my embedding theorem (http://jdh.hamkins.org/every-model-embeds-into-own-constructible-universe/), which shows that every countable model of set theory is isomorphic to a substructure of the hereditary *finite* sets of any other -nonstandard model. That argument, ultimately, also proceeds by a back-and-forth type construction. But of course, with H-finite, one cannot expect an epsilon-initial segment, and so perhaps they are not so closely related.
Pingback: The -definable universal finite sequence | Joel David Hamkins