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 $\mathsf{ZF}$ has an end-extension to a model of $\mathsf{ZFC} + V = L$.

If $M$ and $N$ are models of set theory then $N$ is an end-extension of $M$ if for every $a \in M$ and every $b \in N$ if $N \models b \in a$ then $b \in M$. That is, any new elements in $N$ cannot appear as members of old elements, and must come at the end of the epsilon relation. It’s easy to see that if $N$ is an elementary end extension of $M$ then in fact $N$ is a rank-extension of $M$—every new element has rank above the ordinals of $M$. But if we don’t have elementarity then an end-extension can be quite far from a rank-extension. For instance, if $M$ is an inner model of $N$ then $N$ end-extends $M$.

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 $\mathsf{ZF}$ and let $\varphi$ be a $\Sigma_1$ formula without parameters. Then $\varphi$ implies $\varphi^L$.

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) $\Sigma^1_2$ 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 $V$ and $L$. Let’s see how to get this other form.

Suppose that $\varphi = \exists x \psi(x)$ is true, where $\psi(x)$ only has bounded quantifiers. Then if $A$ is any transitive set containing a witness for $\psi(x)$ we have $A \models \varphi$. There must be such $A$, so by downward Löwenheim–Skolem we get a countable transitive $A$ so that $A \models \varphi$. But the assertion that there is countable such $A$ is $\Sigma^1_2$—there is a real coding a well-founded structure so that blah blah. So it must also be true in $L$ that there is such an $A$. And $\Sigma_1$ things are upward absolute between transitive models, so $L \models \varphi$, as desired. ∎

We can now prove Barwise’s theorem.

Proof of Barwise’s theorem: Let $M \models \mathsf{ZF}$ be countable and transitive. We will consider a theory in the logic $\mathcal L_M$, the countable admissible fragment of $\mathcal L_{\infty,\omega}$ associated with $M$ (that is, $\mathcal L_M = (\mathcal L_{\infty,\omega})^M$). Namely, our theory $T$ has as axioms:

  • Each axiom of $\mathsf{ZF}$ and
  • The infinitary $\in$-diagram of $M$, i.e. all sentences of the form $x \in a \Leftrightarrow \bigvee_{b \in a} x = b$, where “$x = b$” is an abbreviation for the $\mathcal L_M$-formula defining $b$. (Think of how every hereditarily finite set is definable in $\mathcal L_{\omega,\omega}$.)

Then $T$ is definable over $M$ by a $\Sigma_1$ formula $\tau(x)$. The point of including the infinitary $\in$-diagram of $M$ in $T$ is that it ensures that any model of $T$ must end-extend $M$.

Now suppose towards a contradiction that there is no model of $T + V = L$. Thus, $T \models V \ne L$. So by the Barwise completeness theorem we get that $T \vdash V \ne L$ is true in $M$. (This is where we use the assumption that $M$ 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 $M$ thinks that there is a proof of $V \ne L$ from the axioms of $T$ which only uses set-many axioms. A bit more formally, $M$ satisfies that there is a set $\Phi$ so that every $x \in \Phi$ has $\tau(x)$ and there is an infinitary proof of $\bigwedge \Phi \Rightarrow V \ne L$. Stare at that for a moment and convince yourself that this is a $\Sigma_1$ assertion (because it is $\Sigma_1$ to say that there is an infinitary proof of such and such).

By Shoenfield, we get that $L^M$ satisfies the same thing. And in $L^M$ we have that $\tau(x)$ defines the $\mathcal L_{L^M}$-theory whose axioms are $\mathsf{ZF}$ and the infinitary $\in$-diagram of $L^M$. Call this theory $T’$. So we get that there is $T_0 \subseteq T’$ with $T_0 \in L^M$ so that $T_0 \models V \ne L$. But this is impossible, since $L^M \models T_0 + V=L$. So our original assumption that $T + V = L$ has no model must be false, so $M$ has an end-extension to a model of $\mathsf{ZFC} + V=L$. ∎

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 $\mathsf{ZFC} + 0^\sharp$ exists, where this model has the real $0^\sharp$. How could we possibly end-extend to a model of $V = L$? Wouldn’t that contradict the well-known fact that $0^\sharp$ is not in $L$?

The answer is that the end-extension Barwise gives us must, in this case, be nonstandard. Our end-extension sees the real $0^\sharp$ and thinks that it is constructible, but it only shows up in $L_\alpha$ for some ersatz, ill-founded ‘ordinal’ $\alpha$. As a consequence, the end-extension does not recognize that the set we externally can see is $0^\sharp$ really is $0^\sharp$. 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 $L$).

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 $0^\sharp$ is not computable (from finitely many ordinal parameters) by a Turing machine with $<\mathrm{Ord}$ 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.