2 Preliminaries

Throughout this paper $\mathcal {L}$ will denote the usual language of set theory whose only nonlogical symbol is the membership relation. Structures will usually be denoted using upper-case calligraphic Roman letters ( $\mathcal {M}, \mathcal {N}$ , etc.) and the corresponding plain font letter ( $M, N$ , etc.) will be used to denote the underlying set of that structure. If $\mathcal {M}$ is an $\mathcal {L}^\prime $ -structure where $\mathcal {L}^\prime \supseteq \mathcal {L}$ and $a \in M$ , then we will use $a^*$ to denote the set $\{x \in M \mid \mathcal {M} \models (x \in a)\}$ where the background model, $\mathcal {M}$ , used in definition of $a^*$ will be clear from the context.

In addition to the Lévy classes of $\mathcal {L}$ -formulae $\Delta _0= \Sigma _1=\Pi _0$ , $\Sigma _1$ , $\Pi _1$ , etc., we will also have cause to consider the Takahashi classes $\Delta _0^{\mathcal {P}}$ , $\Sigma _1^{\mathcal {P}}$ , $\Pi _1^{\mathcal {P}}$ , etc. $\Delta _0^{\mathcal {P}}$ is the smallest class of $\mathcal {L}$ -formulae that contains all atomic formulae, contains all compound formulae formed using the connectives of first-order logic, and is closed under quantification in the form $\mathcal {Q} x \in y$ and $\mathcal {Q} x \subseteq y$ where x and y are distinct variables, and $\mathcal {Q}$ is $\exists $ or $\forall $ . The classes $\Sigma _1^{\mathcal {P}}, \Pi _1^{\mathcal {P}}$ , etc. are defined inductively from the class $\Delta _0^{\mathcal {P}}$ in the same way that the classes $\Sigma _1, \Pi _1$ , etc. are defined from $\Delta _0$ . If $\Gamma $ is a collection of formulae and T is a theory, then we will write $\Gamma ^T$ for the collection of formulae that are T-provably equivalent to a formula in $\Gamma $ . If T is an $\mathcal {L}$ -theory, then $\Delta _n^T$ is the collection of all $\mathcal {L}$ -formulae that are T-provably equivalent to both a $\Sigma _n$ -formula and a $\Pi _n$ -formula. Similarly, $(\Delta _n^{\mathcal {P}})^T$ is the collection of all $\mathcal {L}$ -formulae that are T-provably equivalent to both a $\Sigma _n^{\mathcal {P}}$ -formula and a $\Pi _n^{\mathcal {P}}$ -formula.

Let $\mathcal {M}$ and $\mathcal {N}$ be $\mathcal {L}$ -structures. We write $\mathcal {M} \equiv \mathcal {N}$ to indicate that $\mathcal {M}$ and $\mathcal {N}$ satisfy the same $\mathcal {L}$ -sentences, and write $\mathcal {M} \subseteq \mathcal {N}$ to indicate that $\mathcal {M}$ is a substructure (also referred to as a submodel) of $\mathcal {N}$ . If $\Gamma $ is a class of $\mathcal {L}$ -formulae, then we will write $\mathcal {M} \prec _\Gamma \mathcal {N}$ if $\mathcal {M} \subseteq \mathcal {N}$ and for every finite tuple $\vec {a} \in M$ , $\vec {a}$ satisfies the same $\Gamma $ -formulae in both $\mathcal {M}$ and $\mathcal {N}$ . In the case that $\Gamma $ is $\Pi _\infty $ (i.e., all $\mathcal {L}$ -formulae) or $\Gamma $ is $\Sigma _n$ , we will abbreviate this notation by writing $\mathcal {M} \prec \mathcal {N}$ and $\mathcal {M} \prec _n \mathcal {N}$ respectively. If $\mathcal {M} \subseteq \mathcal {N}$ and for all $x \in M$ and $y \in N$ ,

$$ \begin{align*}\text{if } \mathcal{N} \models (y \in x) \text{ then } y \in M,\end{align*} $$

then we say that $\mathcal {N}$ is an end-extension of $\mathcal {M}$ (equivalently: $\mathcal {M}$ is an initial submodel of $\mathcal {N}$ , or $\mathcal {M}$ is a transitive submodel of $\mathcal {N}$ ) and write $\mathcal {M} \subseteq _e \mathcal {N}$ . It is well-known that if $\mathcal {M} \subseteq _e \mathcal {N}$ , then $\mathcal {M} \prec _0 \mathcal {N}$ . The following is a slight generalisation of the notion of a powerset preserving end-extension that was first studied by Forster and Kaye in [Reference Forster and Kaye8].

Just as end-extensions preserve $\Delta _0$ -properties, powerset preserving end-extensions preserve $\Delta _0^{\mathcal {P}}$ -properties. The following is a slight modification of a result proved in [Reference Forster and Kaye8]:

Let $\Gamma $ be a class of $\mathcal {L}$ -formulae. The following define the restriction of some commonly encountered axiom and theorem schemes of $\mathrm {ZFC}$ to formulae in the class $\Gamma $ :

• ( $\Gamma $ -Separation) For all $\phi (x, \vec {z}) \in \Gamma $ ,

  $$ \begin{align*}\forall \vec{z} \forall w \exists y \forall x(x \in y \iff (x \in w) \land \phi(x, \vec{z})).\end{align*} $$

• ( $\Gamma $ -Collection) For all $\phi (x, y, \vec {z}) \in \Gamma $ ,

  $$ \begin{align*}\forall \vec{z} \forall w((\forall x \in w) \exists y \phi(x, y, \vec{z}) \Rightarrow \exists c (\forall x \in w)(\exists y \in c) \phi(x, y, \vec{z})).\end{align*} $$

• (Strong $\Gamma $ -Collection) For all $\phi (x, y, \vec {z}) \in \Gamma $ ,

  $$ \begin{align*}\forall \vec{z} \forall w \exists C (\forall x \in w)(\exists y \phi(x, y, \vec{z}) \Rightarrow (\exists y \in C) \phi(x, y, \vec{z})).\end{align*} $$

• ( $\Gamma $ -Foundation) For all $\phi (x, \vec {z}) \in \Gamma $ ,

  $$ \begin{align*}\forall \vec{z}(\exists x \phi(x, \vec{z}) \Rightarrow \exists y(\phi(y, \vec{z}) \land (\forall x \in y) \neg \phi(x, \vec{z}))).\end{align*} $$
  If $\Gamma = \{x \in z\}$ then we will refer to $\Gamma $ -Foundation as Set Foundation.

We will use $\bigcup x \subseteq x$ to abbreviate the $\Delta _0$ -formula that says “x is transitive,” i.e., $(\forall y \in x)(\forall z \in y)(z \in x)$ . We will also make reference to the axiom of transitive containment ( $\mathrm {TCo}$ ), Zermelo’s well-ordering principle ( $\mathrm {WO}$ ), Axiom H, and for all $n \in \omega $ , the axiom scheme of $\Delta _n$ -Separation:

• ( $\mathrm {TCo}$ )

  $$ \begin{align*}\forall x \exists y \left(\bigcup y \subseteq y \land x \subseteq y \right).\end{align*} $$

• ( $\mathrm {WO}$ )

  $$ \begin{align*}\forall x \exists r (r \text{ is a well-ordering of } x).\end{align*} $$

• (Axiom H)

  $$ \begin{align*}\forall u \exists t \left(\bigcup t \subseteq t \land \forall z(\bigcup z \subseteq z \land |z| \leq |u| \Rightarrow z \subseteq t) \right).\end{align*} $$

• ( $\Delta _n$ -separation) For all $\Sigma _n$ -formulae $\phi (x, \vec {z})$ and $\psi (x, \vec {z})$ ,

  $$ \begin{align*}\hspace{-7pt}\forall \vec{z} \ \forall w(\forall x(\phi(x, \vec{z}) \iff \neg \psi(x, \vec{z})) \Rightarrow \exists y \forall x(x \in y \iff (x \in w) \land \phi(x, \vec{z}))).\end{align*} $$

For $\alpha $ an ordinal, the $\alpha $ -dependent choice scheme ( $\Pi ^1_\infty \text{-}\mathrm {DC}_\alpha $ ) is the natural class version of Lévy’s axiom $\mathrm {DC}_\alpha $ [Reference Lévy19] that generalises Tarski’s Dependent Choice Principle by facilitating $\alpha $ -sequences of dependent choices.

• ( $\Pi ^1_\infty \text{-}\mathrm {DC}_\alpha $ ) For all $\mathcal {L}$ -formulae $\phi (x, y, \vec {z})$ ,

  $$ \begin{align*}\hspace{-5pt}\forall \vec{z} \left(\begin{array}{c} \forall g(\forall \gamma \in \alpha)((g \text{ is a function})\land (\mathrm{dom}(g)= \gamma) \Rightarrow \exists y \phi(g, y, \vec{z})) \Rightarrow\\ \exists f ( (f \text{ is a function})\land (\mathrm{dom}(f)= \alpha) \land (\forall \beta \in \alpha)\phi(f \upharpoonright \beta, f(\beta), \vec{z})) \end{array}\right).\end{align*} $$

We will have cause to consider the following subsystems of $\mathrm {ZFC}$ :

• • $\mathbf {M}^-$ is the $\mathcal {L}$ -theory with axioms: Extensionality, Emptyset, Pair, Union, Infinity, $\mathrm {TCo}$ , $\Delta _0$ -Separation, and Set Foundation.

• • $\mathbf {M}$ is obtained from $\mathbf {M}^-$ by adding the powerset axiom.

• • $\mathrm {Mac}$ is obtained from $\mathbf {M}$ by adding the axiom of choice.

• • $\mathrm {KPI}$ is obtained from $\mathbf {M}^-$ by adding $\Delta _0$ -Collection and $\Pi _1$ -Foundation.

• • $\mathrm {KP}$ is obtained from $\mathrm {KPI}$ by removing the axiom of infinity.

• • $\mathrm {KP}^{\mathcal {P}}$ is obtained from $\mathbf {M}$ by adding $\Delta _0^{\mathcal {P}}$ -Collection and $\Pi _1^{\mathcal {P}}$ -Foundation.

• • $\mathrm {MOST}$ is obtained from $\mathrm {Mac}$ by adding $\Sigma _1$ -Separation and $\Delta _0$ -Collection.

• • $\mathrm {ZF}^-$ is obtained by adding $\Pi _\infty $ -Collection to $\mathrm {KPI}$ .

The theories $\mathbf {M}$ , $\mathrm {KPI}$ , $\mathrm {KP}$ , and $\mathrm {KP}^{\mathcal {P}}$ are studied in [Reference Mathias20]. In contrast with the version of Kripke–Platek Set Theory studied in [Reference Barwise3, Reference Friedman9], which includes $\Pi _\infty $ -Foundation, we follow [Reference Mathias20], by only including $\Pi _1$ -Foundation in the theories $\mathrm {KP}$ and $\mathrm {KPI}$ , and only including $\Pi _1^{\mathcal {P}}$ -Foundation in the theory $\mathrm {KP}^{\mathcal {P}}$ . The theory $\mathrm {KPI}$ , as defined here, plays a key role in [Reference Friedman, Li and Wong11], where it is referred to as $\mathrm {KP}^- + \mathrm {infinity} + \Pi _1$ -Foundation.

The results of [Reference Zarach26] and, more recently, [Reference Gitman, Hamkins and Johnstone12] highlight the importance of axiomatising $\mathrm {ZF}^-+\mathrm {WO}$ using the collection scheme ( $\Pi _\infty $ -Collection) instead of the replacement scheme. The strength of Zermelo’s well-order principle $\mathrm {WO}$ in the $\mathrm {ZF}^-$ context is revealed in [Reference Zarach25], which shows that, in the absence of the powerset axiom, the statement that every set of nonempty sets has a choice function does not imply $\mathrm {WO}$ .Footnote ¹

Let $\mathrm {ZF}^-+ \mathrm {GWO}(R)$ be the extension of $\mathrm {ZF}^-+\mathrm {WO}$ obtained as follows: introduce a new binary relation symbol, R, to the language of set theory, and then add an axiom asserting that R is a bijection between the universe and the class of ordinals (a global well-order), and also extend the schemes of separation and collection so as to ensure that formulae mentioning R can be used. As a consequence of a result of Flannagan [Reference Flannagan7, Theorem 7.1], $\mathrm {ZF}^-+ \mathrm {GWO}(R)$ is a conservative extension of the theory $\mathrm {ZF}^-+\mathrm {WO}+\forall \alpha \ \Pi ^1_\infty \text{-}\mathrm {DC}_\alpha $ . Recent work of S. Friedman, Gitman, and Kanovei [Reference Friedman, Gitman and Kanovei10] shows that $\Pi ^1_\infty \text{-}\mathrm {DC}_{\omega }$ is independent of $\mathrm {ZF}^-+\mathrm {WO}$ .

Next we record the following useful relationships between fragments of Collection, Separation, and Foundation over the base theory $\mathbf {M}^-$ .

As indicated by the following well-known result, over the theory $\mathbf {M}^-$ , $\Pi _n$ -Collection implies that the classes $\Pi _{n+1}$ and $\Sigma _{n+1}$ are essentially closed under bounded quantification (part (3) of Lemma 2.4 is used in the proof).

The theory $\mathrm {KPI}$ and its variants that include the scheme of full class foundation have been widely studied [Reference Barwise3, Reference Friedman9, Reference Friedman, Gitman and Kanovei11, Reference McKenzie21]. One appealing feature of this theory is the fact that it is strong enough to carry out many of the fundamental set-theoretic constructions such as defining set-theoretic rank, proving the existence of transitive closures, defining satisfaction, and constructing Gödel’s L hierarchy.

• • For all sets X, we use $\mathrm {TC}(X)$ to denote the $\subseteq $ -least transitive set with X as a subset. The theory $\mathrm {KPI}$ proves that the function $X \mapsto \mathrm {TC}(X)$ is total. Moreover, the proof of [Reference Mathias20, Proposition 1.29] shows that the formulae “ $x = \mathrm {TC}(y)$ ” and “ $x \in \mathrm {TC}(y)$ ” with free variables x and y are $\Delta _1^{\mathrm {KP}}$ , and “ $x = \mathrm {TC}(y)$ ” is also $\Delta _0^{\mathcal {P}}$ .

• • The theory $\mathrm {KP}$ is capable of defining and proving the totality of the rank function $\rho $ satisfying

  $$ \begin{align*}\rho(a)= \mathop{\mathrm{sup}}\limits \left\{ \rho(b)+1: b\in a \right\}.\end{align*} $$
  The formula “ $\rho (x)=y$ ” with free variables x and y is $\Delta _1^{\mathrm {KP}}$ [Reference Friedman9, Theorem 1.5].

• • As verified in [Reference Barwise3, Section III.1], satisfaction in set structures is definable in $\mathrm {KPI}$ . In particular, if $\mathcal {N}$ is a set structure in a model $\mathcal {M}$ of $\mathrm {KPI}$ , $\mathcal {L}(\mathcal {N})$ is the language of $\mathcal {N}$ , $\vec {a}$ is an $\mathcal {M}$ -finite sequence of members of $\mathcal {N}$ , and $\phi $ is an $\mathcal {L}(\mathcal {N})$ -formula in the sense of $\mathcal {M}$ whose arity agrees with the length of $\vec {a}$ , then “ $\mathcal {M} \models \phi [\vec {v}/\vec {a}]$ ” is definable in $\mathcal {M}$ by a formula that is $\Delta _1^{\mathrm {KPI}}$ .

• • As shown in [Reference Barwise3, Chapter II] the theory $\mathrm {KPI}$ is capable of constructing the levels of Gödel’s L hierarchy. The following operation can be defined using a formula for satisfaction for set structures in $\mathrm {KPI}$ : for all sets X,

  $$ \begin{align*}\mathrm{Def}(X)= \{Y \subseteq X \mid Y \text{ is a definable subclass of } \langle X, \in \rangle\}.\end{align*} $$

  The levels of the L hierarchy are then recursively defined by:

  $$ \begin{align*}L_0= \emptyset \text{ and } L_\alpha= \bigcup_{\beta < \alpha} L_\beta \text{ if }\alpha \text{ is a limit ordinal},\end{align*} $$
  $$ \begin{align*}L_{\alpha+1}= L_\alpha \cup \mathrm{Def}(L_\alpha),\end{align*} $$
  $$ \begin{align*}L= \bigcup_{\alpha \in \mathrm{Ord}} L_\alpha.\end{align*} $$
  The function $\alpha \mapsto L_\alpha $ is total and $\Delta _1^{\mathrm {KP}}$ . As usual, we will use $V=L$ to abbreviate the axiom that says that every set is a member of some $L_\alpha $ , i.e., $\forall x \exists \alpha (x \in L_\alpha )$ .

The fact that $\mathrm {KPI}$ can express satisfaction in set structures can be used, in this theory, to express satisfaction for $\Delta _0$ -formulae in the universe via the definition below.

Definition 2.7. The formula $\mathrm {Sat}_{\Delta _0}(q, x)$ is defined as

$$ \begin{align*}\begin{array}{c@{}} (q \in \omega) \land (q= \ulcorner \phi(v_1, \ldots, v_m) \urcorner \text{ where } \phi \text{ is } \Delta_0) \land (x= \langle x_1, \ldots, x_m \rangle){} \land{}\\ \exists N \left( \bigcup N \subseteq N \land (x_1, \ldots, x_m \in N) \land (\langle N, \in \rangle \models \phi[x_1, \ldots, x_m]) \right). \end{array}\end{align*} $$

The absoluteness of $\Delta _0$ properties between transitive structures and the universe, and the availability of $\mathrm {TCo}$ in $\mathrm {KPI}$ imply that the formula $\mathrm {Sat}_{\Delta _0}$ is equivalent, in the theory $\mathrm {KPI}$ , to the formula

$$ \begin{align*}\begin{array}{c@{}} (q \in \omega) \land (q= \ulcorner \phi(v_1, \ldots, v_m) \urcorner \text{ where } \phi \text{ is } \Delta_0) \land (x= \langle x_1, \ldots, x_m \rangle) {}\land{}\\ \forall N \left( \bigcup N \subseteq N \land (x_1, \ldots, x_m \in N) \Rightarrow (\langle N, \in \rangle \models \phi[x_1, \ldots, x_m]) \right) .\end{array}\end{align*} $$

Therefore, the fact that “ $\langle N, \in \rangle \models \phi [\cdots ]$ ” is $\Delta _1^{\mathrm {KPI}}$ implies that $\mathrm {Sat}_{\Delta _0}(q, x)$ is also $\Delta _1^{\mathrm {KPI}}$ , and $\mathrm {Sat}_{\Delta _0}(q, x)$ expresses satisfaction for $\Delta _0$ -formulae in the theory $\mathrm {KPI}$ . We can now inductively define formulae $\mathrm {Sat}_{\Sigma _n}(q, x)$ and $\mathrm {Sat}_{\Pi _n}(q, x)$ that express satisfaction for formulae in the classes $\Sigma _n$ and $\Pi _n$ .

Definition 2.8. The formulae $\mathrm {Sat}_{\Sigma _n}(q, x)$ and $\mathrm {Sat}_{\Pi _n}(q, x)$ are defined recursively for $n>0$ . $\mathrm {Sat}_{\Sigma _{n+1}}(q, x)$ is defined as the formula

$$ \begin{align*}\exists \vec{y} \exists k \exists b \left( \begin{array}{@{}c@{}} (q= \ulcorner\exists \vec{u} \phi(\vec{u}, v_1, \ldots, v_l)\urcorner \text{ where } \phi \text{ is } \Pi_n)\land (x= \langle x_1, \ldots, x_l \rangle)\\ \land (b= \langle \vec{y}, x_1, \ldots, x_l \rangle) \land (k= \ulcorner \phi(\vec{u}, v_1, \ldots, v_l) \urcorner) \land \mathrm{Sat}_{\Pi_n}(k, b) \end{array}\right),\end{align*} $$

and $\mathrm {Sat}_{\Pi _{n+1}}(q, x)$ is defined as the formula

$$ \begin{align*}\forall \vec{y} \forall k \forall b \left( \begin{array}{@{}c@{}} (q= \ulcorner\forall \vec{u} \phi(\vec{u}, v_1, \ldots, v_l) \urcorner \text{ where } \phi \text{ is } \Sigma_n)\land (x= \langle x_1, \ldots, x_l \rangle)\\ \land ((b= \langle \vec{y}, x_1, \ldots, x_l \rangle) \land (k= \ulcorner\phi(\vec{u}, v_1, \ldots, v_l)\urcorner) \Rightarrow \mathrm{Sat}_{\Sigma_n}(k, b)) \end{array}\right).\end{align*} $$

Theorem 2.9. Suppose $n \in \omega $ and $m=\max \{ 1, n \}$ . The formula $\mathrm {Sat}_{\Sigma _n}(q, x) ($ respectively $\mathrm {Sat}_{\Pi _n}(q, x))$ is $\Sigma _n^{\mathrm {KPI}} (\Pi _n^{\mathrm {KPI}}$ , respectively $)$ . Moreover, $\mathrm {Sat}_{\Sigma _n}(q, x) ($ respectively $\mathrm {Sat}_{\Pi _n}(q, x))$ expresses satisfaction for $\Sigma _n$ -formulae $(\Pi _n$ -formulae, respectively $)$ in the theory $\mathrm {KPI}$ , i.e., if $\mathcal {M} \models \mathrm {KPI}$ , $\phi (v_1,\ldots ,v_k)$ is a $\Sigma _n$ -formula, and $x_1,\ldots ,x_k$ are in M, then for $q = \ulcorner \phi ( v_1, \ldots , v_k) \urcorner $ , $\mathcal {M}$ satisfies the universal generalization of the following formula $:$

$$ \begin{align*}x= \langle x_1, \ldots,x_k \rangle \Rightarrow \left( \phi(x_1,\ldots,x_k) \leftrightarrow \mathrm{Sat}_{\Sigma_{n}}(q, x) \right).\end{align*} $$

The following result appears in [Reference Friedman, Li and Wong11, Theorem 3.8].

The following theorem highlights the important fact that the $\Sigma _1^{\mathcal {P}}$ -Recursion Theorem is provable in the theory $\mathrm {KP}^{\mathcal {P}}$ [Reference Mathias20, Theorem 6.26].

Note that under Definition 2.12, if $V_\alpha $ exists, then $V_\beta $ exists for all $\beta <\alpha $ . The following consequence of the $\Sigma _1^{\mathcal {P}}$ -Recursion Theorem is Proposition 6.28 of [Reference Mathias20].

Section 3 of [Reference Mathias20] contains the verification of the following lemma.

We also record the following consequence of $\mathrm {MOST}$ that are proved in [Reference Mathias20, Section 3]:

The following result is [Reference Enayat, Kaufmann and McKenzie6, Lemma 3.3] combined with the refinement of a theorem due to Takahashi proved in [Reference Mathias20, Proposition Scheme 6.12]:

We next recall a remarkable absoluteness phenomenon unveiled by Lévy [Reference Lévy19], which shows that, provably in ZF, $H^{L}_{\aleph _1}$ (i.e., the collection of sets that are hereditarily countable, as computed in the constructible universe) is a $\Sigma _1$ -elementary submodel of the universe of sets.Footnote ²

Theorem 2.17 (Lévy–Shoenfield Absoluteness)

Let $\theta (x,y)$ be a $\Sigma _1^{\mathrm {ZF}}$ -formula with no free variables except x and y, then the universal generalization of the following formula is provable in $\mathrm {ZF}:$

$$ \begin{align*}\left(y \in H^{L}_{\aleph_1} \land \exists x\ \theta(x,y) \right)\Rightarrow \exists x(x\in H^{L}_{\aleph_1} \land \theta(x,y)).\end{align*} $$

The Lévy–Shoenfield Absoluteness Theorem readily implies the following corollary that shows that the $\Sigma _1$ -theory of every model of ZF coincides with the $\Sigma _1$ -theory of $H_{\aleph _1}$ of the constructible universe of the same model.

Corollary 2.18. Let $\delta (\vec {x})$ be a $\Delta _0^{\mathrm {ZF}}$ -formula, and $\mathcal {M}$ be a model of $\mathrm {ZF}$ . Then

$$ \begin{align*}\mathcal{M} \models \exists \vec{x}\ \delta(\vec{x}) \Longleftrightarrow H^{L^{\mathcal{M}}}_{\aleph_1} \models \exists \vec{x}\ \delta(\vec{x}).\end{align*} $$

Any model of $\mathrm {KPI}$ comes equipped with its well-founded part that consists of all sets in this structure whose rank is a standard ordinal, as indicated by the following definition.

Definition 2.19. Let $\mathcal {M} \models \mathrm {KP}$ . The well-founded part or standard part of $\mathcal {M}$ , denoted $\mathrm {WF}(\mathcal {M})$ , is the substructure of $\mathcal {M}$ with underlying set

$$ \begin{align*}\mathrm{WF}(M)&= \{x \in M \mid \neg \exists f(f: \omega \longrightarrow M\land(\forall n \in \omega)\\[-1pt]&\quad \times(f(0)= x \land f(n+1)\in^{\mathcal{M}} f(n)))\}.\end{align*} $$

If $\mathrm {WF}(\mathcal {M})\neq \mathcal {M}$ , then we say that $\mathcal {M}$ is nonstandard. The standard ordinals of $\mathcal {M}$ , denoted $\mathrm {o}(\mathcal {M})$ , is the substructure of $\mathcal {M}$ with underlying set $\mathrm {o}(M)= \mathrm {WF}(M)\cap \mathrm {Ord}^{\mathcal {M}}$ . If $\omega ^{\mathcal {M}} \in \mathrm {o}(M)$ , then we say that $\mathcal {M}$ is $\mathbf {\omega }$ -standard $;$ otherwise $\mathcal {M}$ is said to be $\mathbf {\omega }$ -nonstandard. Mostowski’s Collapsing Lemma ensures that both $\mathrm {o}(\mathcal {M})$ and $\mathrm {WF}(\mathcal {M})$ are isomorphic to transitive sets. In particular, $\mathrm {o}(\mathcal {M})$ is isomorphic to an ordinal that is called the standard ordinal of $\mathcal {M}$ .

The following definition generalises the notion of standard system that plays an important role in the study of models of arithmetic.

Definition 2.20. Let $\mathcal {M} \models \mathrm {KPI}$ . The standard system of $\mathcal {M}$ is the set

$$ \begin{align*}\mathrm{SSy}(\mathcal{M})= \{y^* \cap \mathrm{WF}(\mathcal{M}) \mid y \in M\}.\end{align*} $$

If $A \in \mathrm {SSy}(\mathcal {M})$ and $y \in M$ is such that $A= y^* \cap \mathrm {WF}(\mathcal {M})$ , then we say that y codes A.

Definition 2.21. Let $\mathcal {M}$ and $\mathcal {N}$ be $\mathcal {L}$ -structures. An embedding of $\mathcal {M}$ into $\mathcal {N}$ is an injection $j: M \longrightarrow N$ such that for all $x, y \in M$ ,

$$ \begin{align*}\mathcal{M} \models x \in y \text{ if and only if } \mathcal{N} \models j(x) \in j(y).\end{align*} $$

Note that we will often write $j: \mathcal {M} \longrightarrow \mathcal {N}$ to indicate that j is an embedding of $\mathcal {M}$ into $\mathcal {N}$ . If $j: \mathcal {M} \longrightarrow \mathcal {N}$ is an embedding of $\mathcal {M}$ into $\mathcal {N}$ , then we write $j[\mathcal {M}]$ for the substructure of $\mathcal {N}$ whose underlying set is $\mathrm {rng}(j)$ .

Next, we take advantage of the rank function available in $\mathrm {KP}$ to define the notion of rank extension, and the notion of rank-initial embedding.

Note that a rank-initial embedding $j: \mathcal {M} \longrightarrow \mathcal {N}$ , where $\mathcal {M}, \mathcal {N} \models \mathrm {KP}$ , is also $\mathcal {P}$ -initial. The following result of Gorbow [Reference Gorbow13, Corollary 4.6.12] shows that if the source and target model of a $\mathcal {P}$ -initial embedding both satisfy $\mathrm {KP}^{\mathcal {P}}$ , then this embedding is also rank-initial.

Note that, in any model of $\mathrm {ZFC}$ , L is a powerset preserving end-extension of $H_{\aleph _\omega }^L$ and $H_{\aleph _\omega }^L$ satisfies $\mathrm {MOST}+\Pi _\infty \text {-Separation}$ . This example shows that the assumption that $\mathcal {M}$ satisfies $\Delta _0^{\mathcal {P}}\text {-Collection}$ in Lemma 2.26 cannot be relaxed to $\Delta _0\text {-Collection}$ even in the presence of the full scheme of separation.

H. Friedman’s seminal [Reference Friedman9] pioneered the study of rank-initial self-embeddings of $\mathrm {KP}^{\mathcal {P}}+\Pi _\infty \text {-Foundation}$ . His work was refined and extended by Ressayre [Reference Ressayre24], and more recently by Gorbow [Reference Gorbow13]. The following theorem of Gorbow guarantees the existence of proper rank-initial self-embeddings of countable nonstandard models of an extension of $\mathrm {KP}^{\mathcal {P}}$ . Gorbow’s theorem refines [Reference Friedman9, Theorem 4.3], and is a consequence of results proved in [Reference Gorbow13, Section 5.2].

We also note the following self-embedding theorem that is readily obtained by putting [Reference Enayat, Kaufmann and McKenzie6, Theorem 5.6] together with [Reference Mathias20, Proposition Scheme 6.12].

3 The well-founded part

In this section we present results about well-founded parts of models of set theory that are relevant to the proofs of the main result of this paper. H. Friedman [Reference Friedman9] systematically studied the structure of the well-founded part of a nonstandard model of Kripke–Platek Set Theory and [Reference Friedman9, Theorem 2.1] showed that such a well-founded part must be isomorphic to an admissible set. This result is also a consequence of [Reference Barwise3, Lemma 8.4]. As we mentioned earlier, the versions of Kripke–Platek Set Theory studied in [Reference Barwise3, include $\Pi _\infty $ -Foundation. An examination of these proofs reveals that the well-founded part of a model of $\mathrm {KPI}+\Sigma _1\text {-Foundation}$ is isomorphic to an admissible set. Before proving this, we will first verify in the lemma below that any nonstandard model of $\mathrm {KPI}$ is a topless powerset preserving end-extension of its well-founded part.

Lemma 3.1. Let $\mathcal {M}$ be a nonstandard model of $\mathrm {KPI}$ . Then

$$ \begin{align*}\mathrm{WF}(\mathcal{M}) \subseteq_{\mathrm{topless}}^{\mathcal{P}} \mathcal{M}.\end{align*} $$

Lemma 3.2. Let $\mathcal {M}$ be a nonstandard model of $\mathrm {KPI}$ . Then $\mathrm {WF}(\mathcal {M})$ satisfies Extensionality, Emptyset, Pair, Union, $\Delta _0$ -Separation, and $\Pi _\infty $ -Foundation. Moreover, for all $x \in M$ ,

$$ \begin{align*}x \in \mathrm{WF}(M) \text{ if and only if } \rho^{\mathcal{M}}(x) \in \mathrm{WF}(M).\end{align*} $$

Proof The fact $\mathrm {WF}(\mathcal {M}) \subseteq _e^{\mathcal {P}} \mathcal {M}$ implies that $\mathrm {WF}(\mathcal {M})$ satisfies Extensionality, Emptyset, Pair, Union, and $\Delta _0$ -Separation. The fact that $\mathrm {WF}(\mathcal {M})$ is well-founded ensures that $\Pi _\infty $ -Foundation holds in $\mathrm {WF}(\mathcal {M})$ . Now, to prove the last statement, consider

$$ \begin{align*}a= \{x \in \mathrm{WF}(M) \mid \rho^{\mathcal{M}}(x) \notin \mathrm{WF}(M) \}.\end{align*} $$

Suppose that $a \neq \emptyset $ and let $z \in a$ be a $\in ^{\mathcal {M}}$ -least member of a. Working inside $\mathcal {M}$ , consider

$$ \begin{align*}b= \{ \rho(y)+1 \mid y \in z\}.\end{align*} $$

Next we observe that b is a set and $b^* \subseteq \mathrm {WF}(M)$ , so $b \in \mathrm {WF}(M)$ . It now follows that $\rho ^{\mathcal {M}}(z)= (\mathop {\mathrm {sup}}\limits b)^{\mathcal {M}} \in \mathrm {WF}(M)$ , which is a contradiction. This shows that if $x \in \mathrm {WF}(M)$ , then $\rho ^{\mathcal {M}}(x) \in \mathrm {WF}(M)$ . Conversely, consider

$$ \begin{align*}c= \{\rho^{\mathcal{M}}(x) \mid x \notin \mathrm{WF}(M)\}.\end{align*} $$

Suppose, for a contradiction, that $c \cap \mathrm {WF}(M)\neq \emptyset $ . Let $\alpha \in c$ be least and let $z \in M$ with $z \notin \mathrm {WF}(M)$ be such that $\mathcal {M} \models \rho (z)= \alpha $ . Since $\alpha $ is least, $z^* \subseteq \mathrm {WF}(M)$ . Since $\mathrm {WF}(\mathcal {M}) \subseteq _{\mathrm {topless}}^{\mathcal {P}} \mathcal {M}$ , this implies that $z \in \mathrm {WF}(M)$ , which is a contradiction.⊣

We next verify that under the additional assumption that the nonstandard model of $\mathrm {KPI}$ satisfies $\Sigma _1$ -Foundation, the well-founded part also satisfies $\Delta _0$ -Collection.

Proof We need to show that $\mathrm {WF}(\mathcal {M})$ satisfies all of the axioms of $\mathrm {KP}$ . By Lemma 3.2, we are left to verify that $\mathrm {WF}(\mathcal {M})$ satisfies $\Delta _0$ -Collection. Let $\phi (x, y, \vec {z})$ be a $\Delta _0$ -formula and let $a, \vec {b} \in \mathrm {WF}(M)$ be such that

$$ \begin{align*}\mathrm{WF}(\mathcal{M}) \models (\forall x \in a) \exists y \phi(x, y, \vec{b}).\end{align*} $$

Since $\mathrm {WF}(\mathcal {M}) \prec _{\Delta _0^{\mathcal {P}}} \mathcal {M}$ ,

$$ \begin{align*}\mathcal{M} \models (\forall x \in a) \exists y \phi(x, y, \vec{b}).\end{align*} $$

Consider $\theta (\gamma , \vec {z}, w)$ defined by

$$ \begin{align*}(\forall x \in w)(\exists \alpha \in \gamma)\exists y (\phi(x, y, \vec{z})\land \rho(y)= \alpha).\end{align*} $$

Recall that $\Sigma _1$ -Collection in $\mathcal {M}$ implies that $\theta (\gamma , \vec {z}, w)$ is equivalent to a $\Sigma _1$ -formula. Therefore, using $\Sigma _1$ -Foundation, let $\delta \in M$ be the least element of

$$ \begin{align*}A= \{ \beta \in M \mid \mathcal{M} \models \theta(\beta, \vec{b}, a)\}.\end{align*} $$

Now, every nonstandard $\mathcal {M}$ -ordinal is an element of A and so $\delta \in \mathrm {WF}(M)$ . Let $\psi (x, z, \gamma , \vec {w})$ be the $\Sigma _1$ -formula

$$ \begin{align*}\exists y \exists \alpha(z= \langle y, \alpha\rangle \land (\alpha \in \gamma)\land \rho(y)= \alpha \land \phi(x, y, \vec{w})).\end{align*} $$

Therefore,

$$ \begin{align*}\mathcal{M} \models (\forall x \in a) \exists z \psi(x, z, \delta, \vec{b}).\end{align*} $$

Work inside $\mathcal {M}$ . By $\Sigma _1$ -Collection, there exists d such that $(\forall x \in a) (\exists z\in d) \psi (x, z, \delta , \vec {b})$ . Let $c= \mathrm {dom}(d)$ . Note that by Lemma 3.2, $c^* \subseteq \mathrm {WF}(M)$ and so $c \in \mathrm {WF}(M)$ . Hence

$$ \begin{align*}\mathrm{WF}(\mathcal{M}) \models (\forall x \in a) (\exists y \in c) \phi(x, y, \vec{b}),\end{align*} $$

and therefore $\Delta _0$ -Collection holds in $\mathrm {WF}(\mathcal {M})$ . So, the Mostowski collapse of $\mathrm {WF}(\mathcal {M})$ witnesses the fact that $\mathrm {WF}(\mathcal {M})$ is isomorphic to an admissible set.

In Definitions 3.4 and 3.5, we introduce two relationships between models of set theory and their well-founded parts that will be shown to be linked to the existence of proper initial self-embeddings in Sections 4 and 5.

In Section 4 we will see that the well-founded part being c-bounded prevents a model of $\mathrm {KPI}$ from admitting a proper initial self-embedding. In contrast, the following condition will be used in Section 5 to show that nonstandard models of certain extensions of $\mathrm {KPI}$ are guaranteed to admit proper initial self-embedding.

The next result shows that if the well-founded part of an $\omega $ -standard model is contained, then Theorem 3.3 can be extended to show that the well-founded part satisfies all of the axioms of $\mathrm {KP}^{\mathcal {P}}$ .

Proof Suppose that the well-founded part of $\mathcal {M}$ is contained. Let $c \in M$ be such that $\mathrm {WF}(M) \subseteq c^*$ . Since $\omega \in \mathrm {WF}(M)$ , $\mathrm {WF}(\mathcal {M})$ satisfies the axiom of infinity. By Lemma 3.2, we are left to verify that Powerset and $\Delta _0^{\mathcal {P}}$ -Collection hold in $\mathrm {WF}(\mathcal {M})$ . To see that Powerset holds, let $x \in \mathrm {WF}(M)$ . It follows from Lemma 3.2 that if $y \in M$ with $\mathcal {M} \models y \subseteq x$ , then $y \in \mathrm {WF}(M)$ . Note that $\Delta _0$ -Separation in $\mathcal {M}$ ensures that

$$ \begin{align*}A= \{ y \in c \mid y \subseteq x\}\end{align*} $$

is a set. Moreover, $\mathcal {M} \models (A= \mathcal {P}(x))$ . Now, $A^* \subseteq \mathrm {WF}(M)$ and so, by Lemma 3.1, $A \in \mathrm {WF}(M)$ . Therefore, $\mathrm {WF}(\mathcal {M})\models \text {Powerset}$ . We are left to verify $\Delta _0^{\mathcal {P}}$ -Collection. Let $\phi (x, y, \vec {z})$ be a $\Delta _0^{\mathcal {P}}$ -formula. Let $a, \vec {b} \in \mathrm {WF}(M)$ be such that

$$ \begin{align*}\mathrm{WF}(\mathcal{M}) \models (\forall x \in a) \exists y \phi(x, y, \vec{b}).\end{align*} $$

Since $\mathrm {WF}(\mathcal {M}) \subseteq _{\mathrm {topless}}^{\mathcal {P}} \mathcal {M}$ ,

$$ \begin{align*}\mathcal{M}\models (\forall x \in a) (\exists y \in c) \phi(x, y, \vec{b}).\end{align*} $$

Let $\phi ^c(x, y, \vec {z})$ be the $\Delta _0$ -formula obtained by restricting all of the quantifiers in $\phi (x, y, \vec {z})$ to elements of c. Since $\mathrm {WF}(M) \subseteq c^*$ and $\mathrm {WF}(\mathcal {M}) \subseteq _e^{\mathcal {P}} \mathcal {M}$ , for all $x, y, \vec {z} \in \mathrm {WF}(M)$ ,

$$ \begin{align*}\mathcal{M} \models \phi(x, y, \vec{z}) \text{ if and only if } \mathrm{WF}(\mathcal{M}) \models \phi^c(x, y, \vec{z}).\end{align*} $$

Work inside $\mathcal {M}$ . Let

$$ \begin{align*}B= \{y \in c \mid (\exists x \in a)(\phi^c(x, y, \vec{b}) \land (\forall w \in c)(\phi^c(x, w, \vec{b}) \Rightarrow \rho(y) \leq \rho(w)))\}.\end{align*} $$

Now, $\Delta _1$ -Separation ensures that B is a set. Lemma 3.2 implies that $B^* \subseteq \mathrm {WF}(M)$ . Therefore, since $\mathrm {WF}(\mathcal {M}) \subseteq _{\mathrm {topless}}^{\mathcal {P}} \mathcal {M}$ , $B \in \mathrm {WF}(M)$ . This shows that

$$ \begin{align*}\mathrm{WF}(\mathcal{M}) \models (\forall x \in a)(\exists y \in B) \phi(x, y, \vec{b}),\end{align*} $$

and $\mathrm {WF}(\mathcal {M})\models \mathrm {KP}^{\mathcal{P}}\kern-1pt.$ ⊣

Note that if $\mathcal {M}$ is a model of $\mathrm {KPI}$ that is not $\omega $ -standard, then $\mathrm {WF}(\mathcal {M})$ is isomorphic to $V_\omega $ (the hereditarily finite sets of the metatheory). This observation combined with Theorem 3.6 and Corollary 2.13 makes it clear that if the well-founded part of a model of $\mathrm {KPI}$ is contained, then the well-founded part of that model has access to sequences enumerating the $V_\alpha $ s (as in Definition 2.12), thereby yielding the corollary below.

We can now see that if the well-founded part of a model of $\mathrm {KPI}$ is contained, then the well-founded part is c-bounded in that model.

The next lemma shows that in the special case when a countable model $\mathcal {M}$ of $\mathrm {KPI}$ is $\omega $ -nonstandard, the axioms of $\mathrm {KPI}$ are sufficient to ensure that the well-founded part is contained (note that the well-founded part of an $\omega $ -nonstandard is isomorphic to the hereditarily finite sets).

Similarly, if $\mathcal {M}$ is nonstandard and satisfies all of the axioms of $\mathrm {KP}^{\mathcal {P}}$ , then the well-founded part of $\mathcal {M}$ is contained.

Over the theory $\mathrm {ZF}^-+\mathrm {WO}+\forall \alpha \ \Pi _\infty ^1\text{-}\mathrm {DC}_\alpha $ , we get a converse to Theorem 3.8.

Lemma 3.11. Let $\mathcal {M}$ be a model of $\mathrm {ZF}^-+\mathrm {WO}+\forall \alpha \ \Pi _\infty ^1\text{-}\mathrm {DC}_\alpha $ . If the well-founded part of $\mathcal {M}$ is c-bounded in $\mathcal {M}$ , then

$$ \begin{align*}\mathrm{WF}(\mathcal{M}) \models \mathrm{Powerset}.\end{align*} $$

Proof Suppose that the well-founded part of $\mathcal {M}$ is c-bounded in $\mathcal {M}$ . Using the axiom WO and transitive collapse inside $\mathcal {M}$ , let $\kappa \in M$ be such that $\mathcal {M} \models (\kappa \text { is a cardinal})$ and for all $X \in \mathrm {WF}(M)$ , $\mathcal {M} \models |X| < \kappa $ . Since $\mathrm {WF}(\mathcal {M}) \subseteq _{\mathrm {topless}}^{\mathcal {P}} \mathcal {M}$ , to see that $\mathrm {WF}(\mathcal {M}) \models \mathrm {Powerset}$ it is sufficient to show that for all $X \in \mathrm {WF}(M)$ , $\mathcal {M}$ thinks that $\mathcal {P}(X)$ exists. Suppose, for a contradiction, that $Y \in \mathrm {WF}(M)$ is such that $\mathcal {M}$ believes that the powerset of Y does not exist. Note that if $Z \in M$ with $\mathcal {M} \models Z \subseteq Y$ , then $Z \in \mathrm {WF}(M)$ . Consider the formula $\phi (f, y, Y, \kappa )$ defined by

$$ \begin{align*}(\exists \alpha \in \kappa)(f \text{ is a function with domain } \alpha) \Rightarrow (y \subseteq Y) \land (y \notin \mathrm{rng}(f)).\end{align*} $$

Now, suppose that there exists $f \in M$ such that $\mathcal {M} \models \forall y \neg \phi (f, y, Y, \kappa )$ . It follows that

$$ \begin{align*}\mathcal{M} \models (f \text{ is a function}) \land (\mathrm{rng}(f)= \mathcal{P}(Y)),\end{align*} $$

which contradicts the fact that the powerset of Y does not exist. Therefore

$$ \begin{align*}\mathcal{M} \models \forall f \exists y \phi(f, y, Y, \kappa),\end{align*} $$

and so, by $\Pi ^1_\infty \text{-}\mathrm {DC}_\kappa $ , there exists $f \in M$ such that

$$ \begin{align*}\mathcal{M} \models (f \text{ is a function}) \land (\mathrm{dom}(f)= \kappa) \land (\forall \alpha \in \kappa)\phi(f\upharpoonright \alpha, f(\alpha), Y, \kappa).\end{align*} $$

Work inside $\mathcal {M}$ . If $\alpha \in \kappa $ is least such that $f(\alpha ) \nsubseteq Y$ , then $\phi (f \upharpoonright \alpha , f(\alpha ), Y, \kappa )$ does not hold. Therefore for all $y \in \mathrm {rng}(f)$ , $y \subseteq Y$ . If $\alpha \in \kappa $ is least such that there exists $\beta \in \alpha $ with $f(\alpha ) = f(\beta )$ , then $\phi (f \upharpoonright \alpha , f(\alpha ), Y, \kappa )$ does not hold. This shows that f is injective. Therefore, we have $\mathrm {rng}(f)^* \subseteq \mathrm {WF}(M)$ and $\mathcal {M} \models \kappa \leq |\mathrm {rng}(f)|$ . And, since $\mathrm {WF}(\mathcal {M}) \subseteq _{\mathrm {topless}}^{\mathcal {P}} \mathcal {M}$ , $\mathrm {rng}(f) \in \mathrm {WF}(M)$ , and the fact that $\mathcal {M} \models \kappa \leq |\mathrm {rng}(f)|$ contradicts our choice of $\kappa $ . This shows that $\mathrm {WF}(\mathcal {M})$ satisfies the powerset axiom.

Lemma 3.12. Let $\mathcal {M}$ be a model of $\mathrm {ZF}^-+\mathrm {WO}$ . If $\mathcal {M}$ is nonstandard and

$$ \begin{align*}\mathrm{WF}(\mathcal{M}) \models \mathrm{Powerset},\end{align*} $$

then the well-founded part of $\mathcal {M}$ is contained.⊣

Proof Suppose that $\mathcal {M}$ is nonstandard and

$$ \begin{align*}\mathrm{WF}(\mathcal{M}) \models \mathrm{Powerset}.\end{align*} $$

Consider the formula $\phi (f, \alpha )$ that expresses that f is a function with domain $\alpha $ such that $f(\beta )=V_\beta $ for all $\beta <\alpha $ . Suppose that the class $\{ \alpha \in \mathrm {Ord}^{\mathcal {M}} \mid \mathcal {M} \models \neg \exists f \phi (f, \alpha )\}$ is nonempty and, using foundation, let $\xi \in \mathrm {Ord}^{\mathcal {M}}$ be the least element of this class. We claim that $\xi \notin \mathrm {o}(M)$ . Suppose, for a contradiction, that $\xi \in \mathrm {o}(M)$ . Since $\mathrm {WF}(\mathcal {M}) \models \mathrm {Powerset}$ , $\xi $ is not a successor ordinal and therefore must be a limit ordinal. Work inside $\mathcal {M}$ . Using Collection and Separation in $\mathcal {M}$ , the class

$$ \begin{align*}A= \{ f \mid (\exists \alpha \in \xi) \phi(f, \alpha)\}\end{align*} $$

is a set. Now, $\bigcup A$ is a function that satisfies $\phi \left (\bigcup A, \xi \right )$ , which contradicts our choice of $\xi $ . This shows that if $\{ \alpha \in \mathrm {Ord}^{\mathcal {M}} \mid \mathcal {M} \models \neg \exists f \phi (f, \alpha )\}$ is nonempty, then its least element cannot be standard. Therefore, since $\mathcal {M}$ is nonstandard, there exists $f \in M$ and $\gamma \in \mathrm {Ord}^{\mathcal {M}} \backslash \mathrm {o}(M)$ such that $\mathcal {M} \models \phi (f, \gamma )$ . Moreover, since $\mathrm {WF}(\mathcal {M}) \subseteq _{\mathrm {topless}}^{\mathcal {P}} \mathcal {M}$ , there exists $\nu \in \gamma ^*\backslash \mathrm {o}(M)$ . A standard induction argument inside $\mathcal {M}$ shows that

$$ \begin{align*}\mathcal{M} \models \forall x( x \in f(\nu) \iff \rho(x)< \nu).\end{align*} $$

Therefore, by Lemma 3.2 and the fact that $\nu $ is nonstandard, $\mathrm {WF}(M) \subseteq f(\nu )^*$ . This shows that the well-founded part of $\mathcal {M}$ is contained.⊣

Proof Suppose that the well-founded part of $\mathcal {M}$ is c-bounded in $\mathcal {M}$ . Therefore $\mathcal {M}$ is nonstandard and, by Lemma 3.11,

$$ \begin{align*}\mathrm{WF}(\mathcal{M})\models \mathrm{Powerset}.\end{align*} $$

The fact that the well-founded part of $\mathcal {M}$ is contained now follows from Lemma 3.12.⊣

4 Obstructing initial self-embeddings

In this section we establish the first main result of the paper (Theorem 4.6) on the existence of countable nonstandard models of $\mathrm {ZF}^-+\mathrm {WO}$ with no nontrivial initial self-embeddings. Furthermore, in Theorem 4.7 we exhibit nonstandard uncountable models of ZF with no proper initial self-embeddings.

We begin with verifying that an initial embedding of a model of $\mathrm {KPI}$ must fix the well-founded part of this model. This result will allow us to show that models of $\mathrm {KPI}$ in which the well-founded part is c-unbounded (in the sense of Definition 3.4) do not admit proper initial self-embedding.

Corollary 4.2. Let $\mathcal {M} \models \mathrm {KPI}$ . If $j: \mathcal {M} \longrightarrow \mathcal {M}$ is a proper initial self-embedding, then

$$ \begin{align*}\mathrm{WF}(\mathcal{M}) \subseteq_{\mathrm{topless}}^{\mathcal{P}} j[\mathcal{M}].\end{align*} $$

The next lemma shows that in addition to containing the well-founded part, the fixed point set $\mathrm {Fix}(j)$ of a proper initial self-embedding $j: \mathcal {M} \longrightarrow \mathcal {M}$ also contains all points that are $\Sigma _1$ -definable in $\mathcal {M}$ from points in $\mathrm {Fix}(j)$ .

Proof Suppose that $\phi (z, \vec {y})$ is a $\Sigma _1$ -formula, $\vec {a} \in \mathrm {Fix}(j)$ , and $x \in M$ is the unique element of M such that

$$ \begin{align*}\mathcal{M} \models \phi(x, \vec{a}).\end{align*} $$

Therefore, since $\vec {a} \in \mathrm {Fix}(j)$ ,

$$ \begin{align*}j[\mathcal{M}] \models \phi(j(x), \vec{a}).\end{align*} $$

And, since $j[\mathcal {M}] \subseteq _e \mathcal {M}$ and $\phi $ is a $\Sigma _1$ -formula,

$$ \begin{align*}\mathcal{M} \models \phi(j(x), \vec{a}).\end{align*} $$

By the uniqueness of x, $j(x)= x$ and $x \in \mathrm {Fix}(j)$ .⊣

In particular, if $j: \mathcal {M} \longrightarrow \mathcal {M}$ is a proper initial self-embedding and $x \in M$ is a point that is $\Sigma _1$ -definable in $\mathcal {M}$ from points in the well-founded part of $\mathcal {M}$ , then x must be fixed by j. This observation allows us to show if the well-founded part of a nonstandard model of $\mathrm {KPI}$ is c-unbounded, then that model admits no proper initial self-embedding.

Proof Assume that the well-founded part of $\mathcal {M}$ is c-unbounded in $\mathcal {M}$ and suppose that $j: \mathcal {M} \longrightarrow \mathcal {M}$ is an initial self-embedding. We will show that j must be the identity function. Let $x \in M$ . Let $y \in M$ be such that

$$ \begin{align*}\mathcal{M} \models y= \mathrm{TC}^{\mathcal{M}}(\{x\}).\end{align*} $$

Let $X \in \mathrm {WF}(M)$ be such that

$$ \begin{align*}\mathcal{M} \models |y| \leq |X|.\end{align*} $$

Work inside $\mathcal {M}$ . Let $f: y \longrightarrow X$ be injective. Let $X^\prime = \mathrm {rng}(f)$ . Consider

$$ \begin{align*}Y= \{\langle u, v\rangle \in X \times X \mid (u, v \in \mathrm{rng}(f))\land (f^{-1}(u) \in f^{-1}(v))\}.\end{align*} $$

Now, $Y, X^\prime \in \mathrm {WF}(M)$ . Consider $\phi (z, W, Z)$ defined by

$$ \begin{align*}\exists w\exists f \!\left(\!\!\!\begin{array}{c} (f:w \kern1.5pt{\longrightarrow}\kern1.5pt W \text{ is a bijection})\land (\forall u, v \in w)(u \in v {\iff} \langle f(u), f(v)\rangle \in Z)\\ \land (Z\subseteq W \times W)\land \bigcup w \subseteq w \land (z \in w)\land (\forall u \in w)(z \notin u) \end{array}\!\!\!\!\right)\!.\end{align*} $$

Note that $\phi (z, W, Z)$ is a $\Sigma _1$ -formula and x is the unique point in M such that

$$ \begin{align*}\mathcal{M} \models \phi(x, X^\prime, Y).\end{align*} $$

Therefore, by Lemma 4.3, $j(x)=x$ . Since $x \in M$ was arbitrary, this shows that j is the identity embedding, as desired.⊣

This allows us to show that there are nonstandard $\omega $ -standard models of $\mathrm {ZF}^-+\mathrm {WO}$ that are not isomorphic to a transitive subclass of themselves. To build such a model we will employ the following consequence of [Reference Friedman9, Theorem 2.2].

We conclude this section by exhibiting uncountable nonstandard models of $\mathrm {ZF}$ that carry no proper initial self-embeddings. Before doing so, let us note that it is well-known that every consistent extension of $\mathrm {ZF}$ has a model of cardinality $\aleph _1$ that carries no proper rank-initial self-embedding. To see this, recall that by a classical result due to Keisler and Morley (first established in [Reference Keisler and Morley18], and exposited as Theorem 2.2.18 of [Reference Chang and Keisler5]) every countable model of $\mathrm {ZF}$ has a proper elementary end-extension. It is easy to see that an elementary end-extension of a model of $\mathrm {ZF}$ is a rank-extension. Now if T is a consistent extension of $\mathrm {ZF}$ , we can readily build a countable nonstandard model of T and use the Keisler–Morley theorem $\aleph _1$ -times (while taking unions at limit ordinals) to build a so-called $\aleph _1$ -like model of T, i.e., a model $\cal {M}$ of power $\aleph _1$ such that $a^*$ is finite or countable for each $a \in M$ . It is evident that $\cal {M}$ is nonstandard. Moreover, $\cal {M}$ carries no proper rank initial embedding j since any such embedding j would have to have the property that $j[\mathcal {M}]$ is a submodel of some structure of the form $V^{\mathcal {M}}_{\alpha }$ for some “ordinal” $\alpha $ of $\mathcal {M}$ , which is impossible, since $(V^{\mathcal {M}}_{\alpha })^*$ is countable thanks to the fact that $\cal {M}$ is $\aleph _1$ -like.

5 Constructing initial self-embeddings

In the previous section we saw that if the well-founded part of a model $\mathcal {M}$ of $\mathrm {KPI}$ is c-unbounded (in the sense of Definition 3.4) in $\mathcal {M}$ , then there is no proper initial self-embedding of $\mathcal {M}$ . In this section we prove an adaption of H. Friedman’s Self-embedding Theorem [Reference Friedman9, Theorem 4.1] that ensures the existence of proper initial self-embeddings of models of extensions of $\mathrm {KPI}$ with contained well-founded parts.Footnote ³

We now turn to the investigation of conditions under which models of $\mathrm {KPI}$ with contained well-founded parts admit proper initial self-embeddings. We begin with the verification that $\Delta _1$ -Separation ensures that $\Sigma _0$ -types with parameters from the well-founded part that are realised are coded in the standard system, and that for $n>0$ , $\Sigma _n$ -Separation is sufficient to ensure the corresponding condition for $\Sigma _n$ -types.

Lemma 5.1. Footnote ⁴ Suppose $n \in \omega $ and $\mathcal {M}$ is a model of $\mathrm {KPI}+\Sigma _{n}\text {-Separation}$ such that the well-founded part of $\mathcal {M}$ is contained. If $\vec {a} \in M$ , then

$$ \begin{align*}\{\langle \ulcorner \phi(x, \vec{y}) \urcorner, b\rangle \mid \phi \text{ is } \Sigma_{n}, \ b \in \mathrm{WF}(M) \text{ and } \mathcal{M} \models \phi(b, \vec{a}) \} \in \mathrm{SSy}(\mathcal{M}).\end{align*} $$

Proof Let $C \in M$ be such that $\mathrm {WF}(M) \subseteq C^*$ . Let $a_1, \ldots , a_l \in M$ . Work inside $\mathcal {M}$ . Consider

$$ \begin{align*}D= \{\langle q, b\rangle \in C \mid (q \in \omega) \land (a= \langle b, a_1, \ldots, a_l \rangle) \land \mathrm{Sat}_{\Sigma_n}(q, a) \}.\end{align*} $$

Thanks to Theorem 2.9, $\Sigma _n$ -Separation ( $\Delta _1$ -Separation when $n=0$ ) ensures that D is a set in $\mathcal {M}$ . It is clear that D codes

$$ \begin{align*}\{\langle \ulcorner \phi(x, \vec{y}) \urcorner, b\rangle \mid \phi \text{ is } \Sigma_n, b \in \mathrm{WF}(M) \text{ and } \mathcal{M} \models \phi(b, \vec{a}) \}.\\[-32pt]\end{align*} $$

⊣

As verified in the next lemma, in the special case when the model is not $\omega $ -standard, in Lemma 5.1 the assumption that the well-founded part is contained can be dropped and the assumption that $\Sigma _n$ -Separation holds can be replaced by a fragment of the collection scheme coupled with a fragment foundation scheme.

Lemma 5.2. Suppose that $n \in \omega $ , $m= \max \{1, n\}$ , and $\mathcal {M}$ is an $\omega $ -nonstandard model of $ \mathrm {KPI}+ \Pi _{m-1}\text {-Collection}+\Pi _{n+1}\text {-Foundation}$ . If $\vec {a} \in M$ , then

$$ \begin{align*}\{\langle \ulcorner \phi(x, \vec{y}) \urcorner, b\rangle \mid \phi \text{ is } \Sigma_n, b \in \mathrm{WF}(M) \text{ and } \mathcal{M} \models \phi(b, \vec{a}) \} \in \mathrm{SSy}(\mathcal{M}).\end{align*} $$

Proof By Lemma 3.9, the well-founded part of $\mathcal {M}$ is contained. Let $C \in M$ be such that $\mathrm {WF}(M) \subseteq C^*$ . Let $a_1, \ldots , a_m \in M$ . Let $\psi _1(\alpha , f,C)$ be the formula:

$$ \begin{align*}\left(\begin{array}{c} \alpha \in \omega \land \mathrm{dom}(f)= \alpha+1 \land f(0)= \emptyset \ \land \\ (\forall \beta \in \mathrm{dom}(f))(\forall y \in C)(y \in f(\beta+1) \iff y \subseteq f(\beta)) \end{array}\right).\end{align*} $$

Consider the formula $\theta (\alpha , \omega , a_1, \ldots , a_m)$ defined by:

$$ \begin{align*}\exists v (\exists f \in C) \left( \psi_1(\alpha, f,C) \land \psi_2(\alpha, f,C,v,a_1,\ldots,a_m)\right),\end{align*} $$

where $\psi _2(\alpha , f,C,v, a_1,\ldots ,a_m) $ is:

$$ \begin{align*}\left(\begin{array}{c} (\forall \langle q, b\rangle \in C)\left(\begin{array}{c} \langle q, b \rangle \in v \cap f(\alpha) \iff\\ (\langle q, b\rangle \in f(\alpha))\land \mathrm{Sat}_{\Sigma_n}(q, \langle b, a_1, \ldots, a_m \rangle) \end{array}\right) \end{array}\right).\end{align*} $$

By $\Pi _{m-1}$ -Collection, the formula $\theta (\alpha , \omega , a_1, \ldots , a_m)$ is equivalent to a $\Sigma _{n+1}$ -formula. Now, since $\mathrm {WF}(\mathcal {M})$ is isomorphic to $V_\omega $ , for all $\alpha \in \mathrm {o}(M)$ ,

$$ \begin{align*}\mathcal{M} \models \theta(\alpha, \omega, a_1, \ldots, a_m).\end{align*} $$

Therefore, by $\Pi _{n+1}$ -Foundation, there exists $\gamma \in (\omega ^{\mathcal {M}})^* \backslash \mathrm {WF}(M)$ such that

$$ \begin{align*}\mathcal{M} \models \theta(\gamma, \omega, a_1, \ldots, a_m).\end{align*} $$

Let $v \in M$ be such that

$$ \begin{align*}\mathcal{M} \models (\exists f \in C) \left( \psi_1(\gamma, f,C) \land \psi_2(\gamma, f,C,v,a_1,\ldots,a_m)\right).\end{align*} $$

Since $\gamma \in (\omega ^{\mathcal {M}})^*$ is nonstandard, it follows that v codes

$$ \begin{align*}\{\langle \ulcorner \phi(x, \vec{y}) \urcorner, b\rangle \mid \phi \text{ is } \Sigma_n, b \in \mathrm{WF}(M) \text{ and } \mathcal{M} \models \phi(b, \vec{a}) \} \in \mathrm{SSy}(\mathcal{M}).\\[-32pt]\end{align*} $$

⊣

Lemma 5.1 allows us to prove the following theorem that gives a sufficient condition for nonstandard models of extensions of $\mathrm {KPI}$ to admit proper initial self-embeddings.

Proof It follows from (II) that $B \in M$ witnesses the fact that the well-founded part of $\mathcal {M}$ is contained. Let $\langle d_i \mid i \in \omega \rangle $ be an enumeration of M such that $d_0= b$ . Let $\langle e_i \mid i \in \omega \rangle $ be an enumeration of $B^*$ in which every element of $B^*$ appears infinitely often. We will construct an initial embedding $j: \mathcal {M} \longrightarrow \mathcal {M}$ by constructing sequences $\langle u_i \mid i \in \omega \rangle $ of elements of M and $\langle v_i \mid i \in \omega \rangle $ of elements of $B^*$ and defining $j(u_i)= v_i$ for all $i \in \omega $ . After stage $n \in \omega $ , we will have chosen $u_0, \ldots , u_{n} \in M$ and $v_0, \ldots , v_{n} \in B^*$ and maintained

• ( $\dagger _n$ ) for all $\Pi _{p}$ -formulae, $\phi (\vec {x}, z, y_0, \ldots , y_{n})$ , and for all $a \in \mathrm {WF}(M)$ ,

  $$ \begin{align*}\text{if } \mathcal{M} \models \exists \vec{x} \phi(\vec{x}, a, u_0, \ldots, u_{n}), \text{ then } \mathcal{M} \models (\exists \vec{x} \in B)\phi(\vec{x}, a, v_0, \ldots, v_{n}).\end{align*} $$

At stage $0$ , let $u_0= b$ and let $v_0= c$ . By (III), this choice of $u_0$ and $v_0$ satisfy ( $\dagger _0$ ). Let $n \in \omega $ with $n \geq 1$ . Assume that we have chosen $u_0, \ldots , u_{n-1} \in M$ and $v_0, \ldots , v_{n-1} \in B^*$ and that ( $\dagger _{n-1}$ ) holds.

Case $n=2k+1$ for $k \in \omega $ : This step will ensure that the embedding $j: \mathcal {M} \longrightarrow \mathcal {M}$ is initial. If

$$ \begin{align*}\mathcal{M}\models e_k \notin \mathrm{TC}(\{v_0, \ldots, v_{n-1}\}),\end{align*} $$

then let $u_n= u_0$ and $v_n= v_0$ . This choice of $u_n$ and $v_n$ ensure that $u_0, \ldots , u_n \in M$ and $v_0, \ldots , v_n \in B^*$ satisfy ( $\dagger _{n}$ ). If

$$ \begin{align*}\mathcal{M}\models e_k \in \mathrm{TC}(\{v_0, \ldots, v_{n-1}\}),\end{align*} $$

then let $v_n= e_k$ and we need to choose $u_n$ to satisfy ( $\dagger _{n}$ ). By Lemma 5.1, $\Sigma _{p+1}$ -separation, and $\Pi _p$ -collection, there exists $D \in M$ that codes the class

$$ \begin{align*}&\{ \langle \ulcorner\phi(\vec{x}, z, y_0, \ldots, y_{n}) \urcorner, a \rangle \mid a \in \mathrm{WF}, \phi \text{ is } \Sigma_{p} \text{ and } \mathcal{M} \models (\forall \vec{x} \in B)\phi(\vec{x}, a, v_0, \ldots, v_n)\} \\&\quad \in \mathrm{SSy}(\mathcal{M}).\end{align*} $$

By Corollary 3.7, the well-founded part of $\mathcal {M}$ believes that ranks exist. For all $\alpha \in \mathrm {o}(M)$ , let $D_\alpha \in M$ be such that

$$ \begin{align*}\mathcal{M} \models D_\alpha= D \cap V_\alpha.\end{align*} $$

Note that for all $\alpha \in \mathrm {o}(M)$ , $D_\alpha \in \mathrm {WF}(M)$ . We have that for all $\alpha \in \mathrm {o}(M)$ ,

(1) $$ \begin{align} &\mathcal{M} \models \exists v((v \in \mathrm{TC}(\{v_0, \ldots, v_{n-1}\}) \land (\forall \langle m, a \rangle \in D_\alpha) (\forall \vec{x} \in B) \nonumber\\&\quad\quad\kern4pt \times\mathrm{Sat}_{\Sigma_{p}}(m, \langle \vec{x}, a, v_0, \ldots, v_{n-1}, v \rangle)). \end{align} $$

Claim. For all $\alpha \in \mathrm {o}(M)$ ,

(2) $$ \begin{align} \mathcal{M} \models (\exists v \in \mathrm{TC}(\{u_0, \ldots, u_{n-1}\}))(\forall \langle m, a\rangle \in D_\alpha)\forall \vec{x}\ \mathrm{Sat}_{\Sigma_p}(m, \langle \vec{x}, a, u_0, \ldots, u_{n-1}, v\rangle). \end{align} $$

To prove this claim, suppose not, and let $\alpha \in \mathrm {o}(M)$ be such that

$$ \begin{align*}\mathcal{M} \models (\forall v \in \mathrm{TC}(\{u_0, \ldots, u_{n-1}\}))(\exists \langle m, a\rangle \in D_\alpha) \exists \vec{x}\ \neg \mathrm{Sat}_{\Sigma_p}(m, \langle \vec{x}, a, u_0, \ldots, u_{n-1}, v \rangle).\end{align*} $$

By $\Pi _p$ -collection,

(3) $$ \begin{align} &\mathcal{M} \models \exists C (\forall v \in \mathrm{TC}(\{u_0, \ldots, u_{n-1}\}))(\exists \langle m, a\rangle \in D_\alpha) (\exists \vec{x} \in C)\nonumber\\ &\quad\qquad \neg \mathrm{Sat}_{\Sigma_p}(m, \langle \vec{x}, a, u_0, \ldots, u_{n-1}, v \rangle). \end{align} $$

Now, $\Pi _p$ -Collection implies that (3) is equivalent to a $\Sigma _{p+1}$ -formula. Therefore, by ( $\dagger _{n-1}$ ),

$$ \begin{align*}&\mathcal{M} \models (\exists C \in B)(\forall v \in \mathrm{TC}(\{v_0, \ldots, v_{n-1}\}))(\exists \langle m, a\rangle \in D_\alpha) (\exists \vec{x} \in C)\\ &\quad\qquad \neg \mathrm{Sat}_{\Sigma_p}(m, \langle \vec{x}, a, v_0, \ldots, v_{n-1}, v \rangle).\end{align*} $$

But then

$$ \begin{align*}&\mathcal{M} \models (\forall v \in \mathrm{TC}(\{v_0, \ldots, v_{n-1}\}))(\exists \langle m, a\rangle \in D_\alpha) (\exists \vec{x} \in B)\\ &\qquad\kern10pt \neg \mathrm{Sat}_{\Sigma_p}(m, \langle \vec{x}, a, v_0, \ldots, v_{n-1}, v \rangle),\end{align*} $$

which contradicts (1). This proves the claim.

Consider the formula $\theta (\alpha , D, B, u_0, \ldots , u_{n-1})$ defined by:

$$ \begin{align*}(\exists f \in B) \left( \psi_1(\alpha,f,B) \land \psi_2(\alpha,f, D, u_0, \ldots, u_{n-1}) \right),\end{align*} $$

where $\psi _1(\alpha ,f,B)$ is:

$$ \begin{align*}\left(\begin{array}{c} (\alpha \text{ is an ordinal}) \land \mathrm{dom}(f)= \alpha \land f(0)= \emptyset \ \land \\ (\forall \beta \in \mathrm{dom}(f))\left((\beta \text{ is a limit ordinal}) \Rightarrow f(\beta)= \bigcup_{\xi < \beta} f(\xi) \right) \land\\ (\forall \beta \in \mathrm{dom}(f))(\forall y \in B)(y \in f(\beta+1) \iff y \subseteq f(\beta)) \end{array}\right),\end{align*} $$

and $\psi _2(\alpha ,f, D, u_0, \ldots , u_{n-1})$ is:

$$ \begin{align*}(\exists v \in \mathrm{TC}(\{u_0, \ldots, u_{n-1}\}))(\forall \langle m, a\rangle \in D \cap f(\alpha))\forall \vec{x}\ \mathrm{Sat}_{\Sigma_p}(m, \langle \vec{x}, a, u_0, \ldots, u_{n-1}, v\rangle).\end{align*} $$

Now, for all $\alpha \in \mathrm {o}(M)$ ,

$$ \begin{align*}\mathcal{M} \models \theta(\alpha, D, B, u_0, \ldots, u_{n-1}).\end{align*} $$

And $\Pi _p$ -Collection implies that $\theta (\alpha , D, B, u_0, \ldots , u_{n-1})$ is equivalent to a $\Pi _{p+1}$ -formula. Therefore, by $\Sigma _{p+1}$ -Foundation, there exists $\gamma \in \mathrm {Ord}^{\mathcal {M}} \backslash \mathrm {o}(M)$ and $f \in M$ such that

$$ \begin{align*}\mathcal{M} \models \psi_1(\gamma,f,B),\end{align*} $$

and

$$ \begin{align*}\mathcal{M} \models \psi_2(\gamma, f,D,u_0,\ldots,u_{n-1}).\end{align*} $$

Let $v \in M$ be such that

$$ \begin{align*}\mathcal{M} \models v \in \mathrm{TC}(\{u_0, \ldots, u_{n-1}\}),\end{align*} $$

and

$$ \begin{align*}\mathcal{M} \models (\forall \langle m, a\rangle \in D \cap f(\gamma))\forall \vec{x}\ \mathrm{Sat}_{\Sigma_p}(m, \langle \vec{x}, a, u_0, \ldots, u_{n-1}, v\rangle).\end{align*} $$

Let $u_n= v$ . This choice of $u_n$ ensures that $u_0, \ldots , u_n \in M$ and $v_0, \ldots , v_n \in B^*$ satisfy ( $\dagger _{n}$ ).

Case $n=2k$ for $k \in \omega $ : Let $u_n= d_k$ . This choice will ensure that the domain of j is all of M. By Lemma 5.1, there exists $A \in M$ that codes the class

$$ \begin{align*}\{ \langle\ulcorner \phi(\vec{x}, z, y_0, \ldots, y_{n})\urcorner, a\rangle {\,\mid\,} a \in \mathrm{WF}, \phi \text{ is } \Pi_{p} \text{ and }\\ \mathcal{M} \models \exists \vec{x} \phi(\vec{x}, a, u_0, \ldots, u_{n})\} {\,\in\,} \mathrm{SSy}(\mathcal{M}).\end{align*} $$

Now, by Corollary 3.2, the well-founded part of $\mathcal {M}$ believes that ranks exist. For all $\alpha \in \mathrm {o}(M)$ , let $A_\alpha \in M$ be such that

$$ \begin{align*}\mathcal{M} \models A_\alpha= V_\alpha \cap A.\end{align*} $$

Note that for all $\alpha \in \mathrm {o}(M)$ , $A_\alpha \in \mathrm {WF}(M)$ . We have that for all $\alpha \in \mathrm {o}(M)$ ,

$$ \begin{align*}\mathcal{M} \models (\forall \langle m, a \rangle \in A_\alpha) \exists \vec{x} \ \mathrm{Sat}_{\Pi_p}(m, \langle \vec{x}, a, u_0, \ldots, u_n\rangle).\end{align*} $$

So, for all $\alpha \in \mathrm {o}(M)$ ,

$$ \begin{align*}\mathcal{M}\models \exists v (\forall \langle m, a\rangle \in A_\alpha) \exists \vec{x} \ \mathrm{Sat}_{\Pi_p}(m, \langle \vec{x}, a, u_0, \ldots, u_{n-1}, v \rangle),\end{align*} $$

and, using $\Pi _p$ -Collection, this formula is equivalent to a $\Sigma _{p+1}$ -formula with parameters $A_\alpha \in \mathrm {WF}(M)$ and $u_0, \ldots , u_{n-1}$ . Therefore, by ( $\dagger _{n-1}$ ) and (I), for all $\alpha \in \mathrm {o}(M)$ ,

$$ \begin{align*}\mathcal{M} \models (\exists v \in B)(\forall \langle m, a\rangle \in A_\alpha) (\exists \vec{x} \in B) \mathrm{Sat}_{\Pi_p}(m, \langle \vec{x}, a, v_0, \ldots, v_{n-1}, v \rangle).\end{align*} $$

Consider the formula $\theta (\alpha , A, B, v_0, \ldots , v_{n-1})$ defined by

$$ \begin{align*}(\exists v, f \in B)\left(\psi_1(\alpha,f,B) \land \psi_2(\alpha,A,B,v_0,\ldots,v_{n-1},v) \right),\end{align*} $$

where $\psi _1(\alpha ,f,B)$ is as in the proof of Case $(2n=k+1)$ , and $\psi _2(\alpha ,A,B,v_0,\ldots , v_{n-1},v)$ is:

$$ \begin{align*}(\forall \langle m, a \rangle \in A \cap f(\alpha))((\exists \vec{x} \in B) \mathrm{Sat}_{\Pi_p}(m, \langle\vec{x}, a, v_0, \ldots, v_{n-1}, v \rangle)) .\end{align*} $$

Note that $\theta (\alpha , A, B, v_0, \ldots , v_{n-1})$ is equivalent to a $\Pi _{p}$ -formula and for all $\alpha \in \mathrm {o}(M)$ ,

$$ \begin{align*}\mathcal{M} \models \theta(\alpha, A, B, v_0, \ldots, v_{n-1}).\end{align*} $$

Therefore, by $\Sigma _{p}$ -Foundation, there exists $\gamma \in \mathrm {Ord}^{\mathcal {M}} \backslash \mathrm {o}(M)$ such that:

$$ \begin{align*}\mathcal{M} \models \theta(\gamma, A, B, v_0, \ldots, v_{n-1}).\end{align*} $$

Let $f, v \in B^*$ be such that

$$ \begin{align*}\mathcal{M} \models \left( \psi_1(\gamma,f,B^*) \land \psi_2(\gamma, f,A,B,v_0,\ldots,v_{n-1},v) \right),\end{align*} $$

and let $v_n= v$ . Therefore

$$ \begin{align*}\mathcal{M} \models (\forall \langle m, a \rangle \in A \cap f(\gamma))((\exists \vec{x} \in B) \mathrm{Sat}_{\Pi_p}(m, \langle \vec{x}, a, v_0, \ldots, v_n \rangle)),\end{align*} $$

and this choice of $v_n$ ensures that $u_0, \ldots , u_n \in M$ and $v_0, \ldots , v_n \in B^*$ satisfy ( $\dagger _{n}$ ). This completes the case where $n=2k$ and shows that we can construct sequences $\langle u_i \mid i \in \omega \rangle $ and $\langle v_i \mid i \in \omega \rangle $ while maintaining the conditions ( $\dagger _n$ ) at each stage of the construction. Now, define $j: \mathcal {M} \longrightarrow \mathcal {M}$ by: for all $i \in \omega $ , $j(u_i)= v_i$ . Our “back-and-forth” construction ensures that j is a proper initial self-embedding with $j[\mathcal {M}] \subseteq _e B^*$ , $j(b)= c$ , and $j[\mathcal {M}] \prec _p \mathcal {M}$ .⊣

In the proof of Theorem 5.3, the only use of $\Sigma _{p+1}$ -Separation is to prove $\Sigma _{p+1}$ - and $\Pi _{p+1}$ -Foundation, and to satisfy the assumptions of Lemma 5.1. Therefore, in the special case where the model involved is $\omega $ -nonstandard, we can replace Lemma 5.1 with Lemma 5.2 to obtain the following simplified variant of Theorem 5.3.

Equipped with Theorems 5.3 and 5.4, we are now able to demonstrate in Theorem 5.5 and Corollary 5.6 that a variety of nonstandard models of $\mathrm {KPI}$ are isomorphic to $\Sigma _n$ -elementary transitive substructures of themselves.

Proof Let $C \in M$ be such that $\mathrm {WF}(M) \subseteq C^*$ . Work inside $\mathcal {M}$ . Consider the formula $\theta (x, y, b)$ defined by

$$ \begin{align*}x= \langle m, a \rangle \land (m \in \omega) \land y= \langle y_1, \ldots, y_k\rangle \land \mathrm{Sat}_{\Pi_p}(m, \langle y_1, \ldots, y_k, a, b\rangle).\end{align*} $$

Note that if $p \geq 1$ , then $\theta (x, y, b)$ is equivalent to a $\Pi _p$ -formula, and if $p=0$ , then $\theta (x, y, b)$ is equivalent to a $\Sigma _1$ -formula. By Lemma 2.4, Strong $\Pi _p$ -Collection holds in $\mathcal {M}$ . Therefore, there exists a set D such that

$$ \begin{align*}(\forall x \in C)(\exists y \theta(x, y) \Rightarrow (\exists y \in D)\theta(x, y)).\end{align*} $$

Let $B= \mathrm {TC}(D)$ . Now, $B \in M$ is transitive set in $\mathcal {M}$ with $\mathrm {WF}(M) \subseteq B^*$ , and for all $\Pi _p$ -formulae $\phi (\vec {x}, y, z)$ and for all $a \in \mathrm {WF}(M)$ ,

$$ \begin{align*}\text{if } \mathcal{M} \models \exists \vec{x} \phi(\vec{x}, a, b), \text{ then } \mathcal{M} \models (\exists \vec{x} \in B) \phi(\vec{x}, a, b).\end{align*} $$

Therefore, by Theorem 5.3, there exists a proper initial self-embedding $j: \mathcal {M} \longrightarrow \mathcal {M}$ such that $j[\mathcal {M}] \subseteq _e B^*$ , $j(b)=b$ , and $j[\mathcal {M}] \prec _p \mathcal {M}$ .⊣

Theorem 5.5 also yields the following results that provide two different sufficient conditions for models of $\mathrm {KPI}+\Sigma _{1}\text {-Separation}$ to admit proper initial self-embeddings.

This allows us to give an example of a countable $\omega $ -nonstandard model of $\mathrm {MOST}+\Pi _1\text {-Collection}$ that admits a proper initial self-embedding, but no proper $\mathcal {P}$ -initial self-embedding.

Example 5.9. Let $\mathcal {M}$ be a countable model of $\mathrm {ZF}+V=L$ that is not $\omega $ -standard. Let $\mathcal {N}$ be the substructure of $\mathcal {M}$ with underlying set

$$ \begin{align*}N= \bigcup_{n \in \omega} (H_{\aleph_n}^{\mathcal{M}})^*.\end{align*} $$

The fact that $\mathcal {N} \models \mathrm {Mac}$ follows immediately from the fact that $\mathcal {N} \models \text {Powerset}$ and $\mathcal {N} \subseteq _e^{\mathcal {P}} \mathcal {M}$ . Since $\mathcal {M}$ satisfies the Generalised Continuum Hypothesis, $\mathcal {N} \models \text {Axiom }\mathrm {H}$ . Therefore, by Lemma 2.14, $\mathcal {N} \models \mathrm {MOST}$ . It follows from Lemma 2.16 that $\mathcal {N} \models \mathrm {MOST}+\Pi _1\text {-Collection}$ . By Corollary 5.8, $\mathcal {N}$ admits a proper initial self-embedding. Now, suppose that $j: \mathcal {N} \longrightarrow \mathcal {N}$ is a proper $\mathcal {P}$ -initial self-embedding. But this is impossible, because, since $j[\mathcal {N}] \subseteq _e^{\mathcal {P}} \mathcal {N}$ , cardinals are preserved between $j[\mathcal {N}]$ and $\mathcal {N}$ .

We are also able to find an example of a countable $\omega $ -nonstandard model of $\mathrm {MOST}+\Pi _1\text {-Collection}$ that admits a proper $\mathcal {P}$ -initial self-embedding, but no proper rank-initial self-embedding.