Proof. In many of these instances, the interpretation is obtained by defining a suitable inner model of the desired theory. For example, in any model of $\mathrm {ZF}$ , we can define the constructible universe, and thereby find an interpretation of $\mathrm {ZFC}+V=L$ and hence $\mathrm {ZFC}+\mathrm {GCH}$ and so forth in $\mathrm {ZF}$ . Some of the interpretations involve forcing, however, which we usually conceive as a method for constructing outer models, rather than defining models inside the original model. Nevertheless, one can use forcing via the Boolean ultrapower method to define interpreted models of the forced theory inside the original model. Let us illustrate the general method by explaining how to interpret the theory $\mathrm {ZFC}+\neg \mathrm {CH}$ in $\mathrm {ZF}$ . In $\mathrm {ZF}$ , we may define L, and thereby define a model of $\mathrm {ZFC}$ with a definable global well-order. Inside that model, consider the forcing notion $\mathop {\mathrm {Add}}(\omega ,\omega _2)$ to add $\omega _2$ many Cohen reals. Let ${\mathbb B}$ be the Boolean completion of this forcing notion in L, and let $U\subseteq {\mathbb B}$ be the L-least ultrafilter on this Boolean algebra. Using the Boolean ultrapower method, we define the quotient structure $L^{\mathbb B}/U$ on the class of ${\mathbb B}$ -names by the relations:

$$ \begin{align*} \begin{array}{rcl}\sigma=_U\tau & \mathrel{\Longleftrightarrow} & \mathopen{\lbrack\!\lbrack}\,\sigma=\tau\,\mathclose{\rbrack\!\rbrack}\in U; \\[6pt] \sigma\in_U\tau & \mathrel{\Longleftrightarrow} & \mathopen{\lbrack\!\lbrack}\,\sigma\in\tau\,\mathclose{\rbrack\!\rbrack}\in U. \end{array}\end{align*} $$

The model $L^{\mathbb B}/U$ consists of the $=_U$ equivalence classes of ${\mathbb B}$ -names in L under the membership relation $\in _U$ . The Boolean ultrapower Łoś theorem shows that $L^{\mathbb B}/U$ satisfies every statement $\varphi $ whose Boolean value $\mathopen {\lbrack \!\lbrack }\,\varphi \,\mathclose {\rbrack \!\rbrack }$ is in U, and so this is a model of $\mathrm {ZFC}+\neg \mathrm {CH}$ . We should like to emphasize that there is no need in the Boolean ultrapower construction for the ultrafilter U to be generic in any sense, and $U\in L$ is completely fine (see extensive explanation in [Reference Hamkins and Seabold18, Section 2]). By using the L-least such ultrafilter U on ${\mathbb B}$ , therefore, we eliminate the need for parameters—the Boolean ultrapower quotient $L^{\mathbb B}/U$ is a definable interpreted model of $\mathrm {ZFC}+\neg \mathrm {CH}$ inside the original model, as desired.

The same method works generally. Any forceable theory will hold in an interpreted model, using the forcing notion and the ultrafilter U in the original model as parameters; when forcing over L or $\mathrm {HOD}$ one may use the corresponding definable well-order to eliminate the need for parameters, as we did above. Any theory that is provably forceable over a definable inner model will be forceable over L and therefore amenable to this parameter-elimination method. ⊣

Proof. The latter theory, describing what it would be like in a forcing extension of M by ${\mathbb B}$ , is the same theory as used in the naturalist account of forcing in [Reference Hamkins12]. The theory has a predicate symbol $\check M$ for an inner model and asserts that this satisfies the same theory as M and that the universe is a forcing extension $\check M[G]$ for some $\check M$ -generic filter $G\subseteq \check {\mathbb B}$ . To be clear, we are not saying that the model M is mutually interpretable with some actual forcing extension model $M[G]$ , but rather only that the theory of M is mutually interpretable with the theory expressing what it is like in such a forcing extension. We allow parameters in the interpretation definitions, although in many cases these are eliminable. Assume that ${\mathbb B}$ is a complete Boolean algebra in M, and let $U\subseteq {\mathbb B}$ be an ultrafilter in M. Inside M, we may define the forcing Boolean ultrapower $M^{{\mathbb B}}/U$ as described above, and this is a model of the theory asserting (in the forcing language) that the universe is a forcing extension of $\check M$ by $\check {\mathbb B}$ . That this is true is part of the theory of M, and so this interpretation works inside any model of the theory of M. Conversely, inside any model of the latter theory, we can define the ground model $\check M$ , which will be a model of the theory of M. ⊣

Proof. The argument amounts to what is known as “Scott’s trick.” If $\simeq $ is a definable equivalence relation in a model $M\models \mathrm {ZF}$ , then let us replace every equivalence class $[a]_{\simeq }$ with the Scott class $[a]^{*}_{\simeq }$ , which consists of the elements of the equivalence class having minimal possible $\in $ -rank in that class. This is a definable set in M, and from the Scott class one can identity the original $\simeq $ equivalence class. So we can replace the original interpretation modulo $\simeq $ with the induced interpretation defined on the Scott classes. And since two Scott classes correspond to the same interpreted object if and only if they are equal, we have thereby eliminated the need for the equivalence relation. ⊣

Question 10. Is there a structure that is interpretable in a model of $\mathrm {ZFC}^{-}$ , but only by means of a nontrivial equivalence relation?

Proof. Assume that M is a well-founded model of $\mathrm {ZF}^-$ , which we may assume without loss to be transitive, and that $\langle M,\in \rangle $ is interpreted in itself via the interpretation map , where is a definable class in M with a definable relation , and $\simeq $ is a definable equivalence relation on , which is a congruence with respect to .

Figure 6

Self interpretation.

Since models of set theory admit pair functions, however, we may assume directly that rather than with k-tuples.

Let be the inverse map, viewed as a map on . Since i is an isomorphism, it follows that , and consequently, . Thus, $\pi $ is precisely the Mostowski collapse of the relation on , which is well-founded precisely because it has a quotient that is isomorphic to $\langle M,\in \rangle $ . Thus, the map i is unique, for it is precisely the inverse of the Mostowski collapse of , as computed externally to M in the context where i exists.

What remains is to show that M itself can undertake this Mostowski collapse. While the $\simeq $ -quotient of is a well-founded extensional relation, the subtle issue is that may not literally be set-like, since the $\simeq $ -equivalence classes themselves may be proper classes, and in $\mathrm {ZF}^-$ we are not necessarily able to pick representatives globally from the equivalence classes. So it may not be immediately clear that M can undertake the Mostowski collapse. But, we show, it can.

In M, let I be the class of pairs $(a,\bar a)$ where $a\in M$ and and there is a set with (i) ; (ii) is transitive with respect to modulo $\simeq $ , in the sense that if , then there is some such that $x\simeq x'$ ; and (iii) is isomorphic to $\left \langle \mathop {\mathrm {TC}}(\left \{{a}\right \}),\in \right \rangle $ . Note that if $(a,\bar a)$ are like this, then the isomorphism will be exactly the inverse of the Mostowski collapse of .

We claim by -induction (externally to M) that every is associated in this way with some $a\in M$ , and furthermore, the association I is simply the map $i:a\mapsto \bar a$ . To see this, suppose and every -element of $\bar a$ is associated via I. Since i is an isomorphism, there is some a such that $i(a)=\bar a$ . Inductively, every is associated with some b for which $i(b)=\bar b$ , and all such b are necessarily elements of a. So M can see that every is associated by the class I with a unique element $b\in a$ . For each b, there are various sets with largest element $\bar b$ realizing that $(b,\bar b)\in I$ . By the collection axiom, we can find a single set B containing such a set for every $b\in a$ , serving as a single witnessing set. Let , where $\bar a$ is a representative of the $\simeq $ -class of $i(a)$ . This is a set in M, it is contained in , and it is transitive with respect to modulo $\simeq $ . Since , the Mostowski collapse of agrees with the collapse of , and so sends $\bar b$ to b, for every $b\in a$ . So this set witnesses that $(a,\bar a)\in I$ , and agrees with i on a. So the map i is definable in M, as desired. ⊣

Proof. This follows immediately from Theorem 11, since any instance of mutual interpretation leads to an instance of a model being interpreted inside itself, and so by Theorem 11 the interpretation maps will be definable. ⊣

Proof. Assume that M and N are mutually interpreted models of $\mathrm {ZF}$ , where N is definable in M and is a definable copy of M inside N, with an isomorphism that is definable in M, as illustrated in the Figure 8.

Figure 8

Bi-interpretation in a model of ZF.

Suppose that N thinks A is a nonempty subclass of . Consider the pre-image $A'=\{\,{i^{-1}(x)\mid x\in ^N A}\,\}$ , which is a nonempty class in M. So it must have an $\in ^M$ -minimal element $a \in ^M A'$ . It follows that $i(a)$ is an -minimal element of A, and so N sees as well founded. Because of this fact, the ordinals of the models will be comparable, and they will have some ordinals isomorphically in common. We claim that for these common ordinals, the rank-initial segments of M, N, and are isomorphic. Specifically, if $\alpha $ is an ordinal in M, which is isomorphic to the ordinal in , and this happens to be isomorphic in N to an ordinal $\alpha ^*$ in N, then we claim that N can see that ${\left \langle V_{\alpha ^*},\in \right \rangle }^N$ is isomorphic to , which we know is isomorphic to ${\left \langle V_\alpha ,\in \right \rangle }^M$ . This is certainly true when $\alpha =0$ , and if it is true at $\alpha $ , then it will also be true at $\alpha +1$ , because every subset of $V_\alpha ^N$ exists also as a class in M and therefore can be pushed via i to the corresponding subset of ; and conversely, every subset of in exists also as a class in N and can be pulled back by the isomorphism with $V_{\alpha ^*}^N$ . So in N we may extend the isomorphism canonically from to . Furthermore, because $V_{\alpha ^*}^N$ is transitive in N and transitive sets are rigid, the isomorphisms must be unique, and so at limit stages the isomorphism will simply be the coherent union of the isomorphisms at the earlier stages.

If the ordinals of N run out before the ordinals of M, then ${\mathrm {Ord}}^N$ is isomorphic to an ordinal $\lambda $ in M and hence to in . In this case, the isomorphism from the previous paragraph will mean that , which is isomorphic to $V_\lambda ^M$ . So M will see that N is bijective with a set. But M has a bijection of itself with , which is contained in N. So M will think that the universe is bijective with a set, which is impossible in $\mathrm {ZF}$ .

If in contrast the ordinals of M and hence run out before the ordinals of N, then N would recognize that is isomorphic to a transitive set $V^N_{\alpha ^*}$ . Since it is a set, N has a truth predicate for it, and so N can define a truth predicate for . Since N and i are definable in M, we can pull this truth predicate back via i to produce an M-definable truth predicate on M, contrary to Tarski’s theorem on the nondefinability of truth.

So the ordinals of the three models must be exactly isomorphic, and so the isomorphisms of the rank-initial segments of the models in fact produce an isomorphism of $N=V_{{\mathrm {Ord}}}^N$ with and hence with M, as desired. ⊣

Proof. Corollary 12 shows that every instance of mutual interpretation amongst the well-founded models of $\mathrm {ZF}$ is a bi-interpretation, but Theorem 13 shows that bi-interpretation amongst models of $\mathrm {ZF}$ occurs only between isomorphic models. ⊣

Proof. Let us begin by observing that by the foundation axiom, every nonempty definable $\in $ -class will admit an $\in $ -minimal element, and similarly every nonempty definable -class will have an -minimal element. Thus, both $\in $ and will be well-founded relations in this model, regardless of whether we use $\in $ or as the membership relation. In particular, the orders $\langle {\mathrm {Ord}}^{\left \langle V,\in \right \rangle },\in \rangle $ and will be comparable well-ordered classes, and we may assume without loss that the former is isomorphic to an initial segment of the latter. Thus, for every $\in $ -ordinal $\alpha $ , there is an -ordinal to which it is isomorphic, and furthermore this ordinal is unique, and the isomorphism is unique. We claim that , by induction on $\alpha $ . Since these are transitive sets and hence rigid, the isomorphism is unique. The claim is clearly true for $\alpha =0$ . It remains true through limit ordinals, since the isomorphism in that case is simply the union of the previous isomorphisms. At successor stages, we need only observe that any isomorphism of $\left \langle V_\alpha ,\in \right \rangle $ with extends to an isomorphism of the power set, since any $\in $ -subset of $V_\alpha $ transfers to an -subset of by pointwise application of the isomorphism, and vice versa. If is taller than ${\mathrm {Ord}}^{\left \langle V,\in \right \rangle }$ , then we can see that , where is the first -ordinal not arising from an $\in $ -ordinal. But now , which is the -power set of , is a subclass of V and therefore injects into , contrary to Cantor’s theorem. So the ordinals are the same height, and thus we have achieved . This isomorphism is definable, since every $V_\alpha $ is isomorphic to by a unique isomorphism. ⊣

Proof. Let us argue first merely that the situation is consistent with $\mathrm {ZFC}$ . Assume that Luzin’s hypothesis holds, that is, $2^\omega =2^{\omega _1}$ ; for example, this holds after adding $\omega _2$ many Cohen reals over a model of $\mathrm {GCH}$ , since in this case we would have $2^\omega =2^{\omega _1}=\omega _2$ . It follows that $H_{\omega _1}$ and $H_{\omega _2}$ are equinumerous, and so there is a bijection $\pi :H_{\omega _1}\to H_{\omega _2}$ . Let $\tilde \in $ be the image of $\in \upharpoonright H_{\omega _1}$ under this bijection, and let

be the preimage of $\in \upharpoonright H_{\omega _2}$ . Thus, $\pi $ is an isomorphism of the structures

The first of these is a model of

, using $\in $ as membership, since $H_{\omega _1}$ is a model of $\mathrm {ZFC}^{-}$ with respect to any predicate. Similarly, the second is a model of $\mathrm {ZFC}^{-}(\tilde \in )$ , again using $\in $ as membership, since we can likewise augment $H_{\omega _2}$ with any predicate. By following the isomorphism, an equivalent way to say this is that

is a model of

, using $\in $ as membership and

as predicate, and also a model of

, using

as membership this time and $\in $ as a class predicate. But $\left \langle H_{\omega _1},\in \right \rangle $ is not isomorphic to

, because the first thinks every set is countable and the second does not. So this model is just as desired.

To get outright existence of the models, observe first that by taking an elementary substructure, we can find a countable model of the desired form in the forcing extension. Furthermore, the existence of a countable well-founded model with the desired properties is a $\Sigma ^1_2$ assertion, which is therefore absolute to the forcing extension by Shoenfield’s absoluteness theorem. And so therefore there must have already been such an example in the ground model, without need for any forcing. ⊣

Proof. Let us assume we have the two properties isolated above. The structure $\left \langle H_{\omega _1},\in \right \rangle $ , of course, is a definable substructure of $\left \langle H_{\omega _2},\in \right \rangle $ , which gives one direction of the interpretation. It remains to interpret $\left \langle H_{\omega _2},\in \right \rangle $ inside $\left \langle H_{\omega _1},\in \right \rangle $ and to prove that this is a bi-interpretation. The second assumption above implies, of course, that $2^\omega =2^{\omega _1}$ , and so at least the two structures have the same cardinality. But more, because the almost-disjoint sequence is definable in $H_{\omega _1}$ and all the reals are there, the structure $\left \langle H_{\omega _1},\in \right \rangle $ in effect has access to the full power set $P(\omega _1)$ ; the subsets $A\subseteq \omega _1$ are uniformly definable in the structure $\left \langle H_{\omega _1},\in \right \rangle $ from real parameters. And furthermore, every set in $H_{\omega _2}$ is coded by a subset of $\omega _1$ . Specifically, if $x\in H_{\omega _2}$ then x is an element of a transitive set t of size $\omega _1$ , with $\left \langle t,\in \right \rangle \cong \left \langle \omega _1,E\right \rangle $ for some well-founded extensional relation E on $\omega _1$ . The set x can be in effect coded by specifying E and the ordinal $\alpha $ representing x in the structure $\left \langle \omega _1,E\right \rangle $ . Since $H_{\omega _1}$ contains all countable sequences of ordinals, it can correctly identify which relations E on $\omega _1$ , as encoded by a real via the almost-disjoint coding, are well-founded and extensional. Let us define an equivalence relation $a\simeq a'$ for reals $a,a'\subseteq \omega $ coding such pairs $(\alpha ,E)$ and $(\alpha ',E')$ that represent the same set, which happens just in case there is an isomorphism of the hereditary E-predecessors of $\alpha $ to the hereditary $E'$ -predecessors of $\alpha '$ ; in other words, when the transitive closures of the corresponding encoded sets $\left \{{x}\right \}$ and $\left \{{x'}\right \}$ are isomorphic. The isomorphism itself is a map of size at most $\omega _1$ , which can therefore be seen definably in the structure $\left \langle H_{\omega _1},\in \right \rangle $ . And we can recognize when the set x coded by $(\alpha ,E)$ is an element of the set y coded by $(\beta ,F)$ , since this just means that $(\alpha ,E)$ is equivalent to $(\gamma ,F)$ for some $\gamma \mathrel {F}\beta $ . Since every element of $H_{\omega _2}$ is coded in this way by relations on $\omega _1$ and hence ultimately by reals $a\subseteq \omega $ , we see that $\left \langle H_{\omega _2},\in \right \rangle $ is interpreted in $\left \langle H_{\omega _1},\in \right \rangle $ by the codes $(\alpha ,E)$ for well-founded extensional relations E on $\omega _1$ , which are themselves coded by reals via almost-disjoint coding. Ultimately, objects $x\in H_{\omega _2}$ are represented by a real $a\subseteq $ coding a pair $(\alpha ,E)$ which codes a transitive set having x as an element at index $\alpha $ in that coding.

This interpretation is a bi-interpretation, because $H_{\omega _1}$ can construct suitable codes for any object $x\in H_{\omega _1}$ , and thereby recognize how itself arises within the interpreted copy of $H_{\omega _2}$ . And conversely, $H_{\omega _2}$ can define $H_{\omega _1}$ as a submodel and it can see how the objects in $H_{\omega _2}$ are represented inside that model via almost disjoint coding. The models $\left \langle H_{\omega _1},\in \right \rangle $ and $\left \langle H_{\omega _2},\in \right \rangle $ are therefore well-founded models of $\mathrm {ZFC}^{-}$ that are bi-interpretable, but they are not isomorphic, because the first model thinks every set is countable and the second does not. ⊣

Proof. The argument relies on a result of Leo Harrington [Reference Harrington16], showing that it is relatively consistent with $\mathrm {ZFC}$ that $\mathrm {MA}+\neg \mathrm {CH}$ hold, yet there is a projectively definable well-ordering of the reals; in fact, Harrington achieves this in a forcing extension of L. (Many thanks to Gabe Goldberg [Reference Goldberg11] for pointing out Harrington’s paper in response to our MathOverflow question concerning the possibility of this theorem.) In such a model, we can choose least elements within each equivalence class of reals in the interpretation used in the proof of Theorem 18, and thereby omit the need for an equivalence relation in the first place. So every element of $H_{\omega _2}$ will be coded by a real. Since the decoding of hereditarily countable sets can be undertaken inside $H_{\omega _1}$ , we thereby have a definable injection of $H_{\omega _1}$ into the coding reals, and so by the Cantor–Schröder–Bernstein theorem, $H_{\omega _1}$ is bijective with the coding reals. Because the Cantor–Schröder–Bernstein theorem is sufficiently constructive, this bijection is definable inside $\left \langle H_{\omega _1},\in \right \rangle $ , and so we may pull back the interpreted membership relation on the coding reals to get a definable relation on all of $H_{\omega _1}$ , such that , as desired. This is a bi-interpretation synonymy, since $H_{\omega _1}$ can see how it is represented in that coding, and $H_{\omega _2}$ can define $H_{\omega _1}$ and also see how its elements are coded. ⊣

Proof. If $H_{\omega _2}$ were interpreted in $H_{\omega _1}\!$ , then since the former structure definitely has an $\omega _1$ -sequence of distinct reals, such a sequence would be definable (from parameters) in the structure $\left \langle H_{\omega _1},\in \right \rangle $ . But this latter structure is interpreted in the reals in second-order arithmetic, by coding hereditarily countable sets by relations on $\omega $ . By means of this interpretation, first-order assertions in $\left \langle H_{\omega _1},{\in }\right \rangle $ can be viewed as projective assertions. And so there would be a projectively definable $\omega _1$ -sequence of distinct reals, contrary to our assumption. ⊣

Proof. By Theorem 19, there are such transitive sets in a forcing extension of L. In that model, by taking a countable elementary substructure, we can find countable transitive sets with the desired feature. And furthermore, the assertion that there are such countable transitive sets like that, for which the particular bi-interpretation definitions work and form a synonymy, is a statement of complexity $\Sigma ^1_2$ . By Shoenfield absoluteness, this statement must already be true in L, and hence also in V. So there are countable transitive models $\left \langle M,\in \right \rangle $ and $\left \langle N,\in \right \rangle $ of $\mathrm {ZFC}^{-}$ that form a bi-interpretation synonymy, but are not isomorphic. ⊣

Proof. We shall find two extensions of $\mathrm {ZFC}^{-}$ that are bi-interpretable, but not the same theory. Let us take $T_1$ and $T_2$ be the theories describing the situation of $\left \langle H_{\omega _1},\in \right \rangle $ and $\left \langle H_{\omega _2},\in \right \rangle $ in Theorem 18. Specifically, let $T_2$ assert $\mathrm {ZFC}^{-}$ plus the assertion that $\omega _1$ exists but not $\omega _2$ , that $\omega _1=\omega _1^L$ , that $\omega _2=\omega _2^L$ , and that every subset of $\omega _1$ is coded by a real using the almost-disjoint coding with respect to the L-least almost-disjoint family $\left \langle a_\alpha \mid \alpha <\omega _1\right \rangle $ . Let $T_1$ be the theory $\mathrm {ZFC}^{-}$ plus the assertion that every set is countable and that the interpretation of $H_{\omega _2}$ in $H_{\omega _1}$ used in the proof of Theorem 18 defines a model of $T_2$ . That is, $T_1$ asserts that the interpretation does indeed interpret a model of $T_2$ . These two theories are bi-interpretable, using the interpretations provided in the proof of Theorem 18, because any model of $T_1$ interprets a model of $T_2$ , and any model of $T_2$ can define its $H_{\omega _1}$ , which will be a model of $T_1$ , and the composition maps are definable just as before. ⊣

Proof. The isomorphism from V to $V^{(a)}$ is simply the operation replacing every hereditary instance of $\varnothing $ in a set with a. Specifically, we define the replacing operation $x\mapsto x^{(a)}$ as follows:

$$ \begin{align*} \varnothing^{(a)} &= a.\\ x^{(a)} &= \{y^{(a)} \mid y\in x\}. \end{align*} $$

A simple argument by transfinite induction now shows that this is an isomorphism of every $V_\alpha $ with $V^{(a)}_\alpha $ , which establishes the theorem. ⊣

Proof. Suppose that a is an infinite transitive set in M. It therefore obeys the growth rate requirement, and so there is some k for which $|a\cap V_n|\leq b_k(n)$ for every n. Notice that $a\cup V_\alpha ^{(a)}$ is a transitive set, and since (i) $u^{(a)}$ is infinite for every set u, and (ii) every element of $V_n$ is hereditarily finite, it follows that

$$ \begin{align*}(a\cup V_\alpha^{(a)})\cap V_n=a\cap V_n.\end{align*} $$

Consequently, $a\cup V_\alpha ^{(a)}$ obeys the growth-rate requirement, and consequently every $V^{(a)}_\alpha $ is in M. So $V^{(a)}\subseteq M$ .⊣

Proof. One might naturally want to define $V^{(a)}$ in M by transfinite recursion, as we did in defining the hierarchy $V^{(a)}_\alpha $ above. The problem with this is that M is a model merely of Zermelo set theory, in which such definitions by transfinite recursion do not necessarily succeed. Nevertheless, in instances as here where we know independently that the recursion does have a solution in M, the recursive definition does in fact succeed in defining it.

But instead of that definition, let us consider another simple definition. Define that a terminal $\in $ -descent from a set x is a finite $\in $ -descending sequence of sets from x to $\varnothing $

$$ \begin{align*}x=x_n\ni x_{n-1}\ni\cdots\ni x_1\ni x_0=\varnothing.\end{align*} $$

We claim that $V^{(a)}$ consists in M precisely of those sets x for which every terminal $\in $ -descent passes through the set a, in the sense that $a=x_i$ for some i. Certainly every $x\in V^{(a)}$ is like this, since if $y\in x\in V^{(a)}_{\alpha +1}$ , then either $x=a$ or $y\in V^{(a)}_\alpha $ , and by induction the terminal descents from y will pass through a. Conversely, assume that every terminal $\in $ -descent from x passes through a. So either $x=a$ , in which case it is in $V^{(a)}$ , or else the assumption about terminal descents is also true of the elements of x. By $\in $ -induction, therefore, the elements of x are all in $V^{(a)}$ , and this implies that x is in $V^{(a)}_\gamma $ at an ordinal stage $\gamma $ beyond the stages where the elements of x are placed into $V^{(a)}$ .⊣

Proof. We’ve seen already that M is a definable transitive inner model of V, and $ \langle V,\in \rangle $ is definably isomorphic to its copy $ \langle V^{(a)},\in \rangle $ in M, isomorphic by the map $x\mapsto x^{(a)}$ , which is definable in V, assuming as we have that we use $a=\omega $ or some other definable infinite transitive set in M.

Conversely, we’ve seen that M can define the model $ \langle V^{(a)},\in \rangle $ . Inside that model, we define the copy $M^{(a)}$ of M, just as M is definable in V. For this to be a bi-interpretation, we need to show that the isomorphism of M with $M^{(a)}$ is definable in M. This isomorphism is precisely the function $i:x\mapsto x^{(a)}$ , applied to $x\in M$ . The problem again, however, is that M is not able in general to undertake recursive definitions, since it satisfies only Zermelo set theory, which does not prove that recursive definitions have solutions. Nevertheless, we claim that $i\upharpoonright x\in M$ for any $x\in M$ . The reason is that the transitive closure of $i\upharpoonright x=\{\,{(y,y^{(a)})\mid y\in x}\,\}$ can be seen to obey the growth-rate requirement, as x does with its transitive closure and the sets $y^{(a)}$ are either a or have no elements in any $V_n$ , as in Lemma 26 above. Thus, M can see the isomorphism $i\upharpoonright x$ of $ \langle x,\in \rangle $ with $ \langle x^{(a)},\in \rangle $ for any set $x\in M$ . If x is transitive, then since transitive sets are rigid, this isomorphism is unique, and since different transitive sets are never isomorphic, $ \langle x,\in \rangle $ will not be isomorphic to any $ \langle y,\in \rangle $ that $M^{(a)}$ thinks is transitive. So M can define $i\upharpoonright x$ for transitive sets x by the assertions that it is an isomorphism of $ \langle x,\in \rangle $ with a set $ \langle y,\in \rangle $ for a set y that $M^{(a)}$ thinks is transitive. These maps all agree with and union up to the full isomorphism $x\mapsto x^{(a)}$ of M with $M^{(a)}$ , which is therefore definable in M. So we have a bi-interpretation of $ \langle V,\in \rangle $ with $ \langle M,\in \rangle $ . ⊣

Proof of Theorem 23 The argument we have given shows that every model $V\models \mathrm {ZF}$ is bi-interpretable with a transitive inner model M of Zermelo set theory, which is not a model of $\mathrm {ZF}$ , because it does not even have $V_\omega $ as an element. This establishes statement (2) of Theorem 23.

For statement (1), we can perform the construction inside a well-founded model of some sufficient fragment of $\mathrm {ZF}$ . For example, let us undertake the entire construction inside some $V_\lambda $ , satisfying $\Sigma _2$ -collection, say. We thereby get a transitive model $M_\lambda \subseteq V_\lambda $ of Zermelo set theory, without $V_\omega $ , but with $\langle V_\lambda ,\in \rangle $ and $\left \langle M_\lambda ,\in \right \rangle $ bi-interpretable. So there are well-founded models of Zermelo set theory that are bi-interpretable, but not isomorphic.

Finally, let us consider statement (3). We consider the two extensions of Zermelo set theory describing the situation that enabled us to make the main example for statement (2). That is, the first theory is $\mathrm {ZF}$ itself; and the second theory, which we denote ZM, asserts Zermelo set theory Z, plus the assertion that the class $V^{(\omega )}$ , defined as in our main argument, is a model of $\mathrm {ZF}$ , and the assertion that M is isomorphic to $M^{(\omega )}$ inside that class by the isomorphism definition we provided. These two theories are different, but the argument that we gave above for the models shows that they are bi-interpretable. ⊣

Proof. We use $M=\bigcup T^{Q,G}$ , where $Q:\lambda \to V_\lambda $ is $Q(\alpha )=V_\alpha $ , and G consists of the functions f that are bounded by one of the functions $b_\beta $ , for some $\beta <\lambda $ , defined by

1. (1) $b_0(\alpha ) = \alpha $ ;

2. (2) $b_{\beta +1}(\alpha ) = 2^{b_\beta (\alpha )}$ ;

3. (3) if $\eta $ is a limit ordinal, then $b_\eta (\alpha ) = {\text {sup}}_{\beta <\eta }b_\beta (\alpha )$ .

This is defined with cardinal arithmetic, not ordinal arithmetic. The class $T^{Q,G}$ consists of all transitive sets x whose rate-of-growth function

$$ \begin{align*} f_x^Q(\alpha)=|x\cap V_\alpha| \end{align*} $$

is bounded by one of the functions $b_\beta $ , for some $\beta <\lambda $ . It follows that $T^{Q,G}$ is a fruitful class, and the resulting Zermelo model $M=\bigcup T^{Q,G}$ is a transitive inner model of Zermelo set theory with foundation (in the form of the $\in $ -induction scheme). Every $V_\alpha $ for $\alpha <\lambda $ is in M, with growth rate bounded by $b_\alpha $ , but $V_\lambda $ is not in M, since this growth rate exceeds any given $b_\beta $ for fixed $\beta <\lambda $ . And $\left \langle V,\in \right \rangle $ is bi-interpretable with $\left \langle M,\in \right \rangle $ by analogous arguments to the above. ⊣

Proof. Consider the theories

1. (1) $T_1 = \mathrm {ZF}$ .

2. (2) $T_2 = \{\alpha \lor \beta \mid \alpha \in \mathrm {ZF} \land \beta \in \mathrm {ZM}\}$ (That is, $T_2 = \mathrm {ZM} \lor \mathrm {ZF}.$ ),

where ZM is the theory used in the proof of Theorem 23. Observe that $M\models T_2$ if and only if $M\models \mathrm {ZF}$ or $M\models \mathrm {ZM}$ . The reverse implication is immediate, and if the latter fails, then $M\not \models \alpha $ and $M\not \models \beta $ for some $\alpha \in \mathrm {ZF}$ and $\beta \in \mathrm {ZM}$ , which would mean $M\not \models \alpha \lor \beta $ , violating the former.

Now observe simply that every model of $\mathrm {ZF}$ is bi-interpretable with itself, of course, and this is a model of $T_2$ . And conversely, every model of $T_2$ is either a model of $\mathrm {ZF}$ already, or else a model of $\mathrm {ZM}$ , which is bi-interpretable with a model of $\mathrm {ZF}$ . So these two theories are model-by-model bi-interpretable.

Let us now prove that the theories are not bi-interpretable. Suppose toward contradiction that $(I,J)$ form a bi-interpretation, so that I defines a model of $T_1$ inside any model of $T_2$ and J defines a model of $T_2$ inside any model of $T_1$ , and the theories prove this and furthermore have definable isomorphisms of the original models with their successive double-interpreted copies. Let M be a model of $\mathrm {ZM}$ that is not a model of $\mathrm {ZF}$ . Let $I^M$ be the interpreted model of $\mathrm {ZF}$ defined inside M. This is also a model of $\mathrm {ZM}$ , since $\mathrm {ZM}\subseteq \mathrm {ZF}$ , and so we may use I again to define $I^{I^M}$ to get another model of $\mathrm {ZF}$ inside that model. Because we interpreted a model of $T_2$ by I, it follows that $I^{I^M}$ and $I^M$ are bi-interpretable as models. But these are both models of $\mathrm {ZF}$ , and so by Theorem 13 they are isomorphic. By interpreting with J to get the corresponding interpreted $\mathrm {ZM}$ models, it follows that $J^{I^{I^M}}$ and $J^{I^M}$ are isomorphic. Because $(I,J)$ form a bi-interpretation, the first of these is isomorphic to $I^M\!$ , which is a $\mathrm {ZF}$ model, while the second is isomorphic to M, which is not. This is a contradiction, and so the theories are not bi-interpretable.⊣