Proof First, we will inductively define the following $ \Delta _{0}$ -function (with parameters) in $\mathcal {M}$ :

$$ \begin{align*} &\qquad\qquad\qquad\quad\qquad\qquad\qquad\qquad\qquad g(0):=(a)_{0} , \\&\qquad\quad\qquad\quad\qquad\qquad\qquad\qquad\qquad\qquad \text{and}\\&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad g(x+1):=y \text{ iff } \\&\exists r<\mathrm{Len}(a) \left(\begin{array}{@{}c@{}} y=(a)_{r} \ \wedge \\ r= \mu_{z}\left(\begin{array}{@{}c@{}} \exists u<z \left(\begin{array}{@{}c@{}}g(x)=(a)_{u} \ \wedge \\ \forall w<z \ ( (a)_{w}\neq (a)_{z} \wedge \exists v\leq u ((a)_{w}=(a)_{v}) )\end{array}\right) \end{array}\right) \end{array}\right). \end{align*} $$

Note that by the way we defined $ g $ , its domain is an initial segment of $\mathcal {M}$ , and $ {\mathrm {Dom}(g)\leq \mathrm {Len}(a)} $ . Moreover, since I and $ M_{0} $ are not $ \Delta _{0}$ -definable in $\mathcal {M}$ , then $ I\subsetneq \mathrm {Dom}(g) $ . So by $ \Sigma _{1}$ -induction in $\mathcal {M}$ , we can find some $ d\in M $ such that $ (d)_{i}=g(i) $ for every $ i\in I $ . Clearly, $ (d)_{i}\neq (d)_{j} $ for every distinct $ i,j\in I $ , and $ {M_{0}\subseteq \lbrace (d)_{i}: \ i\in I\rbrace } $ . Now, in each case of the statement of the theorem we will prove that $ \lbrace (d)_{i}: \ i\in I\rbrace \subseteq M_{0} $ :

1. (1) Suppose $ I=\mathbb {N} $ . If $ \lbrace (d)_{n}: \ n\in \mathbb {N}\rbrace \nsubseteq M_{0} $ , then there exists the least number $ n\in \mathbb {N} $ such that $ (d)_{n}\notin M_{0} $ . So by the definition of $ g $ , there exist some $ m\in \mathbb {N} $ and some $ r\in M\setminus \mathbb {N} $ such that ${ (d)_{n-1}=(a)_{m}} $ and $ (d)_{n}=(a)_{r} $ . Therefore, by the definition of $ g $ , it holds that $ M_{0}=\lbrace (a)_{0},\ldots ,(a)_{m}\rbrace $ , which is a contradiction.

2. (2) In the general case with the extra assumption that I is strong in $\mathcal {M}$ , consider the following partial $ \Delta _{0}$ -function in $\mathcal {M}$ :

   $$ \begin{align*} h(x):=\mu_{r}( (d)_{x}=(a)_{r}). \end{align*} $$
   Since I is strong and $ I\subseteq \mathrm {dom}(h) $ (because $ g $ is well-defined on I), there exists some $ e\in M $ such that $ h(i)\in I$ iff $ h(i)<e $ , for all $ i\in I $ . Moreover, by the definition of $ d$ , $g $ and $ h $ , for every $ i\in I $ it holds that $ (d)_{i}=(a)_{h(i)} $ . So it suffices to prove that $ h(i)<e $ for every $ i\in I $ . Suppose not; so there exists some $ i_{0}\in I $ which is the least element of $ M $ such that $ h(i_{0})>e $ . Now, by the way we defined $ g $ and $ h $ , it holds that
   $$ \begin{align*} \mathcal{M}\models\forall i<h(i_{0}) \ ((a)_{i}\neq(a)_{h(i_{0})}\wedge \exists j\leq h(i_{0}-1) ((a)_{i}=(a)_{j})). \end{align*} $$
   Therefore, $ M_{0}=\lbrace x\in M: \ \mathcal {M}\models \exists i\leq h(i_{0}-1) \ x=(a)_{i} \rbrace $ . So $ M_{0} $ is $ \Delta _{0}$ -definable in $\mathcal {M}$ , which is a contradiction.

Proof

1. (1) First fix some arbitrary $ s>I $ . So by using strong $ \Sigma _{1}$ -Collection in $\mathcal {M}$ for the formula $ \mathrm {Sat}_{\Delta _{0}}(\delta _{r}(i,a,z)) $ , we will find some $ b\in M $ such that

   $$ \begin{align*} \mathcal{M}\models\forall \langle r,i\rangle<s \ ([f_{r}(i,a)\downarrow]\rightarrow[f_{r}(i,a)\downarrow]^{<b}). \end{align*} $$
   Then, by using $ \Sigma _{1}$ -induction we observe that $ \mathcal {M}\models \exists y \ \forall \langle r,i\rangle <s \ \varphi (y,r,i,a,b) $ , in which $ \varphi (y,r,i,a,b) $ is the following $ \Delta _{0}$ -formula:
   $$ \begin{align*} \left( \begin{array}{@{}c@{}} ([f_{r}(i,a)\downarrow]^{<b}\rightarrow(y)_{ \langle r,i\rangle}=f_{r}(i,a)) \ \wedge \ (\neg[f_{r}(i,a)\downarrow]^{<b}\rightarrow(y)_{ \langle r,i\rangle}=0) \end{array}\right). \end{align*} $$
   As a result, if $ d\in M $ is such that $ \mathcal {M}\models \forall \langle r,i\rangle <s \ \varphi (d,r,i,a,b) $ , then
   $$ \begin{align*} \mathrm{K}^{1}(\mathcal{M}; I\cup\lbrace a\rbrace)=\{(d)_{i}: \ i\in I \}. \end{align*} $$
   So by Lemma 3.1, $ \mathrm {K}^{1}(\mathcal {M}; I\cup \lbrace a\rbrace ) $ is $ I$ -small in $\mathcal {M}$ .

2. (2) The exact argument used in [Reference Enayat4, Theorem 4.5.1] works here: let $ { M_{0}=\lbrace (a)_{i}: \ i\in I\rbrace } $ for some $ a\in M $ such that $ (a)_{i}\neq (a)_{j} $ for all distinct $ i, j\in I $ . Then put

   $$ \begin{align*} { Z:=\lbrace \langle y,z\rangle\in M: \ \mathcal{M}\models (a)_{y}=z \rbrace }. \end{align*} $$
   Since $ Z $ is $ \Delta _{0}$ -definable in $\mathcal {M}$ , then $ X:= I\cap Z \in \mathrm {SSy}_{ I}(\mathcal {M}) $ . As a result, because $ I $ is strong in $\mathcal {M}$ , $ ( I; X)\models \mathrm {PA}^{*} $ . Now, suppose $ I\nsubseteq M_{0} $ . So $ ( I; X)\models \exists x \ (\forall y \ \langle y,x\rangle \notin X) $ . Let $ ( I, X)\models \textbf {x}_{0}:=\mu _{x} ( \forall y \ \langle y,x\rangle \notin X) $ . Therefore, $ \textbf {x}_{0}\notin M_{0} $ . So since $ \textbf {x}_{0}\neq 0 $ , and by the definition of $ \textbf {x}_{0} $ , we conclude that $ \textbf {x}_{0}-1\in M_{0} $ , which contradicts the fact that $ \mathcal {M}_{0} $ is a submodel of $\mathcal {M}$ .

3. (3) We will generalize the method used in [Reference Kossak and Schmerl12, Proposition 2.10]: let $ S $ be a nonstandard partial inductive satisfaction class for $\mathcal {M}$ such that $ (\mathcal {M}; S) $ is recursively saturated. Put $ \mathcal {M}^{*}:=(\mathcal {M}; S) $ , and $ \mathcal {N}:=\mathrm {K}(\mathcal {M}^{*};I\cup \{s\}) $ for some $ s>I $ . First, note that $ N $ is $ I$ -small in $\mathcal {M}$ : since $ \mathcal {M}^{*} $ is a countable recursively saturated model of $ \mathrm {PA}^{*}$ , so it also possesses an inductive satisfaction class. Moreover, I is also strong in $ \mathcal {M}^{*} $ . Therefore, by repeating the argument used in the proof of part (1) of this theorem, and Lemma 3.1(2), we can show that $ N $ is $ I$ -small in $\mathcal {M}$ .

   Moreover, on one hand, it is easy to see that $ S\cap N $ is a nonstandard satisfaction class for the $ \mathcal {L}_{A}$ -structure $ \mathcal {N} $ . So $ \mathcal {N} $ is also a recursively saturated model of $\mathrm {PA}$ . On the other hand, I is a proper initial segment of $ \mathcal {N} $ (because $ s>I $ ). Therefore, $ \mathcal {N} $ is of the form of $ \mathrm {K}(\mathcal {M};I\cup \{a\}) $ for no $ a\in M $ .

Proof Suppose $ \alpha \in M $ codes $ X $ in $\mathcal {M}$ . So $ \mathcal {M}\models \overset {\delta (\alpha ,\sigma ,i_{1})}{\overbrace {\alpha =\sum _{i<i_{1}}2^{(\sigma )_{i}}} }$ , in which $ i_{1}=\mathrm {Card}( X)\leq i_{0} $ and $ \sigma :=\langle x: \ x\mathrm {E}\alpha \rangle $ (so $ \mathrm {Len}(\sigma )=i_{1} $ ). Since $ \delta (x,y,z) $ is a $ \Delta _{0}$ -formula and $ \mathcal {M}_{0}\prec _{\Sigma _{1}}\mathcal {M} $ , it suffices to prove that $ \sigma \in M_{0} $ . For this purpose let $ Y:=\{i<i_{0}:\ \mathcal {M}\models (a)_{i}\mathrm {E}\alpha \} $ . Then there exists some $ \gamma \in I $ which codes $ Y $ .

Now, we define

$$ \begin{align*} h(z) := \begin{cases} \mu_{u}(\langle (a)_{x}: \ x\mathrm{E}z \rangle=(a)_{u}\wedge u<\mathrm{Len}(a)), & \text{if } \mathcal{M}\models\exists u<\mathrm{Len}(a) \ \langle (a)_{x}: \ x\mathrm{E}z \rangle=(a)_{u}, \\ 0, & \text{otherwise.} \end{cases} \end{align*} $$

Since $ I $ is strong in $\mathcal {M}$ , there exists some $ e $ such that $ h(i)>e $ iff $ h(i)>I $ , for all $ i\in I $ . We claim that $ \mathcal {M}\models \forall x \ \varphi (x,a,\gamma ,e) $ , where $\varphi (x,a,\gamma ,e) $ is the following $ \Delta _{0}$ -formula:

$$ \begin{align*} \forall y<\mathrm{Len}(x) \ \exists z\mathrm{E}\gamma \ ((x)_{y}=(a)_{z})\rightarrow\exists w<\min\{e,\mathrm{Len}(a)\} \ (x=(a)_{w}). \end{align*} $$

Therefore, $ \mathcal {M}\models \varphi (\sigma ,a,\gamma ,e) $ , which implies that $ \sigma =(a)_{c} $ for some $ c<\min \{e,\mathrm {Len}(a)\} $ . So $ \sigma =(a)_{h(\gamma )} $ and $ h(\gamma )<e $ , which implies that $ \sigma \in M_{_{0}} $ .

In order to prove the above claim, we will use $ \Delta _{0}$ -induction inside $\mathcal {M}$ : let $ \textbf {x}\in M $ such that $ {\mathcal {M}\models \varphi (w,a,\gamma ,e)} $ for every $ w<\textbf {x} $ , and $ \mathcal {M}\models \forall y<\mathrm {Len}(\textbf {x}) \ \exists z\mathrm {E}\gamma \ ((\textbf {x})_{y}=(a)_{z}) $ . So by induction hypothesis ${\mathcal {M}\models \textbf {x}\upharpoonright _{\mathrm {Len}(\textbf {x})-1}=(a)_{\textbf {z}} }$ for some $ \textbf {z}<\min \{e,\mathrm {Len}(a)\} $ . Then, we put $ Z:=\{i<\gamma : \ \mathcal {M}\models \exists y<\mathrm {Len}(\textbf {x})-1 \ (\textbf {x})_{y}=(a)_{i}\} $ , and let $ \textbf {z}_{0}\in I $ code $ Z $ . As a result, $ h(\textbf {z}_{0})\leq \textbf {z}<\min \{e,\mathrm {Len}(a)\} $ , which implies that $ \textbf {x}\upharpoonright _{\mathrm {Len}(\textbf {x})-1}=(a)_{h(\textbf {z}_{0})}\in M_{0} $ . So since $ \mathcal {M}_{0}\prec _{\Sigma _{1}}\mathcal {M} $ , then $ \textbf {x} $ is in $ M_{0} $ . Therefore, $ \textbf {x}=(a)_{i} $ for some $ i\in I<\min \{e,\mathrm {Len}(a)\} $ .

Proof By Theorem 2.1, $\mathcal {M}$ is a $ \Sigma _{1}$ -elementary initial segment of $ \mathcal {N} $ such that $ \mathcal {M}\models \mathrm {I}\Sigma _{1} $ . So it is easy to see that I is also strong in $\mathcal {M}$ . Moreover, since $ N_{0}\neq I $ , by using $ \Sigma _{1} $ -Overspill in $\mathcal {M}$ we can find the desired $ a\in M $ .

Proof We will prove part (i), and part (ii) will be proved similarly. Let

$$ \begin{align*} R:=\left\lbrace \langle \langle r,i\rangle,k,t\rangle\in I: \ \mathcal{M}\models \left(\begin{array}{@{}c@{}} ([f_{r}(\bar{u},m,(a)_{i})\downarrow]\wedge [f_{t}(\bar{u},(a)_{k})\downarrow])\rightarrow\\ f_{r}(\bar{u},m,(a)_{i})=f_{t}(\bar{u},(a)_{k}) \end{array}\right)\right\rbrace. \end{align*} $$

On one hand, since R is $\Pi _{1}$ -definable in $\mathcal {M}$ , then $ R\in \mathrm {SSy}_{ I}(\mathcal {M})$ . On the other hand, by Lemma 3.2(2), it holds that

$$ \begin{align*} { I\setminus C= \overset{ B}{\overbrace{\lbrace \langle r,i\rangle\in I: \ ( I, R)\models \exists k,t \ \langle\langle r, i\rangle,k,t\rangle\in R\rbrace}}}. \end{align*} $$

Since I is strong in $\mathcal {M}$ , which implies that $ (I,\mathrm {SSy}_{I}(\mathcal {M}))\models \mathrm {ACA}_{0} $ , and because $ B $ is arithmetical in $ R $ and $ R\in \mathrm {SSy}_{ I}(\mathcal {M}) $ , we may deduce that $ B\in \mathrm {SSy}_{ I}(\mathcal {M}) $ , and consequently $ C\in \mathrm {SSy}_{ I}(\mathcal {M}) $ .

Proof

1. (i) First note that since $ \mathrm {P}(\bar {u},\bar {v}) $ holds in $\mathcal {M}$ , Theorem 2.3 and Remark 1 imply that

   1. (1): There exists some initial self-embedding $ j_{0} $ of $\mathcal {M}$ such that $ j_{0}( M)<b $ , $ j_{0}(\bar {u})=\bar {v} $ , and $ N_{0}\subseteq \mathrm {Fix}(j_{0}) $ .

      Now, suppose that part (i) of this lemma does not hold; i.e., there is some $ k>0 $ for which there exist $ (k+1) $ -many elements $ \lbrace f,f_{n_{1}},\ldots ,f_{n_{k}}\rbrace $ of $ \mathcal {F} $ , and some $ \textbf {z}\in N_{0} $ such that for all $ s> I $ it holds that

      $$ \begin{align*}\mathcal{M}\models\forall y<b \ \neg \Psi(f,f_{n_{1}},\ldots ,f_{n_{k}},\bar{u},m,\bar{v},y,b,a,s,\alpha,\textbf{z},(a)_{\mathrm{i}}). \end{align*} $$

      Therefore, by $ \Sigma _{1}$ -Underspill in $\mathcal {M}$ , there exists some $ s\in I $ such that

      $$ \begin{align*}\mathcal{M}\models \forall y<b \ \neg\Psi(f,f_{n_{1}},\ldots ,f_{n_{k}},\bar{u},m,\bar{v},y,b,a,s,\alpha,\textbf{z},(a)_{\mathrm{i}}).\end{align*} $$

   2. (2): Let $ k_{0}\in \mathbb {N} $ be the least natural number, for which there exists a set $\lbrace f, f_{n_{1}},\ldots ,f_{n_{k_{0}}}\rbrace $ of elements of $ \mathcal {F} $ , some $ \textbf {z}_{0}\in N_{0} $ , and some $ s_{0}\in I $ such that

      $$ \begin{align*} {\mathcal{M}\models \forall y<b \ \neg\Psi(f,f_{n_{1}},\ldots ,f_{n_{k_{0}}}, \bar{u},m,\bar{v},y,b,a,s_{0},\alpha,\textbf{z}_{0},(a)_{\mathrm{i}})}. \end{align*} $$

      Put

      $$ \begin{align*} &\quad X:=\lbrace x\in M: \ \mathcal{M}\models\exists i<s_{0}(x=(a)_{i}\wedge [f(\bar{u},m,(a)_{i}, \textbf{z}_{0})\downarrow] ) \rbrace \\ &\qquad\qquad\qquad\qquad\qquad\qquad \quad \text{and}\\ & \kern-12pt X':=\lbrace \langle n,x\rangle\in M: \ \mathcal{M}\models\exists i<s_{0}(x=(a)_{i}\wedge \bigvee\nolimits_{t=1}^{\kern2pt k_{0}} n=n_{t} \wedge \langle n,i\rangle\mathrm{E}\alpha) \rbrace. \end{align*} $$
      By Lemma 3.3, there exist $ (a)_{\xi }\in N_{0} $ and $ (a)_{\zeta }\in N_{0} $ which code $ X $ and $ X', $ respectively. So we can restate statement (2) in the following form:

   3. (3): Let $ k_{0}\in \mathbb {N} $ be the least natural number, for which there exists a set $\lbrace f, f_{n_{1}},\ldots ,f_{n_{k_{0}}}\rbrace $ of elements of $ \mathcal {F} $ , some $ \textbf {z}_{0},(a)_{\zeta },(a)_{\xi }\in N_{0} $ such that

      $$ \begin{align*} \kern-40pt\mathcal{M}\models\forall y\leq t(\bar{v},(a)_{\mathrm{i}}) \left( \begin{array}{@{}c@{}} \forall \epsilon<(a)_{\xi}( \epsilon\mathrm{E}(a)_{\xi}\rightarrow[f(\bar{v},y,\epsilon,\textbf{z}_{0})\downarrow]^{<b} \rightarrow \\ \exists \varepsilon<\mathrm{E}(a)_{\zeta} \bigvee_{t=1}^{k_{0}} \left(\begin{array}{@{}c@{}} \langle n_{t},\varepsilon\rangle\mathrm{E}(a)_{\zeta} \ \wedge [f_{n_{t}}(\bar{v},y,\varepsilon)\downarrow]^{<b} \wedge \\ f_{n_{t}}(\bar{u},m,\varepsilon)= f_{n_{t}}(\bar{v},y,\varepsilon) \end{array}\right) \end{array}\right).\end{align*} $$
      Our plan is to consider two cases $ {k_{0}=1} $ and $ {k_{0}>1} $ , and in each case obtain a contradiction. But before dividing the cases we will define some $ \Sigma _{1} $ -functions which will help us in achieving the desired contradictions.

      First, by considering the code of the sequence ${ \langle f_{n_{t}}(\bar {u},m,\varepsilon ): \, \langle n_{t},\varepsilon \rangle \mathrm {E}(a)_{\zeta } \rangle } $ in $\mathcal {M}$ , we may quantify out $ f_{n_{t}}(\bar {u},m,\varepsilon ) $ s from the formula in statement $ (3) $ ; in other words, there exists some $ \textbf {x}\in M $ such that $ (\textbf {x})_{\langle n_{t},\varepsilon \rangle }=f_{n_{t}}(\bar {u},m,\varepsilon ) $ for every $\langle n_{t},\varepsilon \rangle \mathrm {E}(a)_{\zeta } $ . So we will deduce that

   4. (4): $ \mathcal {M}\models \exists x \forall y\leq t(\bar {v},(a)_{\mathrm {i}}) \ \theta (y,b,\bar {v},x,(a)_{\xi },(a)_{\zeta },\textbf {z}_{0}) $ , where $\theta (y,b,\bar {v},x, (a)_{\xi },(a)_{\zeta },\textbf {z}_{0})$ is the following $ \Delta _{0} $ -formula:

      $$ \begin{align*} \left( \begin{array}{@{}c@{}} \forall \epsilon<(a)_{\xi}( \epsilon\mathrm{E}(a)_{\xi} \rightarrow[f(\bar{v},y,\epsilon,\textbf{z}_{0})\downarrow]^{<b}) \rightarrow\\ \exists \langle n_{t},\varepsilon\rangle\mathrm{E}(a)_{\zeta} \left(\begin{array}{@{}c@{}} [f_{n_{t}}(\bar{v},y,\varepsilon)\downarrow]^{<b}\wedge (x)_{\langle n_{t},\varepsilon\rangle}= f_{n_{t}}(\bar{v},y,\varepsilon) \end{array}\right)\end{array}\right). \end{align*} $$
      Then, we will define $ \Sigma _{1}$ -definable partial functions $ b(\diamondsuit ,y,(a)_{\xi },(a)_{\zeta },\textbf {z}_{0}) $ and $g(\diamondsuit ,(a)_{\xi },(a)_{\zeta },\textbf {z}_{0},(a)_{\mathrm {i}}) $ , as follows (we omit the parameters $(a)_{\xi } $ , $ (a)_{\zeta } $ , $ (a)_{\mathrm {i}} $ , and $ \textbf {z}_{0} $ in the presentations of these functions for the sake of simplicity):

      1. – $b(\diamondsuit ,y):=\min \left \lbrace w: \left (\begin{array}{@{}c@{}} \forall \epsilon \mathrm {E}(a)_{\xi } \ ([f(\diamondsuit ,y,\epsilon ,\textbf {z}_{0})\downarrow ]^{<w})\wedge \\ \forall \langle n_{t},\varepsilon \rangle \mathrm {E}(a)_{\zeta } \ ([f_{n_{t}}(\diamondsuit ,y,\varepsilon )\downarrow ]^{<w}) \end {array}\right ) \right \rbrace. $

      2. – $ g(\diamondsuit ):=x $ iff $ \exists z \left (\begin{array}{@{}c@{}}(z)_{0}=x \ \wedge \\ z=\mu _{w} \ \forall y\leq t(\diamondsuit ,(a)_{\mathrm {i}}) \ \left (\begin{array}{@{}c@{}}[b(\diamondsuit ,y)\downarrow ]^{<(w)_{1}} \ \rightarrow \\ \theta (y,b(\diamondsuit ,y),\diamondsuit ,(w)_{0},(a)_{\xi },(a)_{\zeta },\textbf {z}_{0})\end {array}\right )\end {array}\right ); $ and $ g_{t}(\diamondsuit ,\varepsilon ):=(g(\diamondsuit ))_{\langle n_{t},\varepsilon \rangle } $ , for every $ \langle n_{t},\varepsilon \rangle \mathrm {E}(a)_{\zeta } $ .

      From the definition of $ g_{t}(\bar {v},\varepsilon ) $ s and statement (4) we may infer that

   5. (5): $ \mathcal {M}\models \forall y\leq t(\bar {v},(a)_{\mathrm {i}}) \left ( \begin{array}{@{}c@{}} ([b(\bar {v},y)\downarrow ]^{<b} \ \wedge \ \forall \epsilon <(a)_{\xi }( \epsilon \mathrm {E}(a)_{\xi }\rightarrow [f(\bar {v},y,\epsilon ,\textbf {z}_{0})\downarrow ]^{<b(\bar {v},y)})) \rightarrow \\ \exists \langle n_{t},\varepsilon \rangle \mathrm {E}(a)_{\zeta } \left (\begin{array}{@{}c@{}} [f_{n_{t}}(\bar {v},y,\varepsilon )\downarrow ]^{<b(\bar {v},y)} \wedge [g_{t}(\bar {v},\varepsilon )\downarrow ]^{<b(\bar {v},y)} \ \wedge \\ g_{t}(\bar {v},\varepsilon )= f_{n_{t}}(\bar {v},y,\varepsilon ) \end {array}\right ) \end {array}\right )$ . It is not difficult to express the formula in the statement (5) in the form of $ {\forall z<b \ \delta (\bar {v},(a)_{\xi },(a)_{\zeta },\textbf {z}_{0})} $ for some $ \Delta _{0}$ -formula $ \delta $ . Therefore, by the property $ \mathrm {P}(\bar {u},\bar {v}) $ , the definition of function $ s $ , and statement (5) we deduce that

   6. (6): $\mathcal {M}\models \forall y\leq t(\bar {u},(a)_{\mathrm {i}}) \left ( \begin{array}{@{}c@{}} ([b(\bar {u},y)\downarrow ] \ \wedge \ \forall \epsilon <(a)_{\xi }( \epsilon \mathrm {E}(a)_{\xi }\rightarrow [f(\bar {u},y,\epsilon ,\textbf {z}_{0})\downarrow ]^{<b(\bar {u},y)}) )\rightarrow \\ \exists \langle n_{t},\varepsilon \rangle \mathrm {E}(a)_{\zeta } \left (\begin{array}{@{}c@{}} [f_{n_{t}}(\bar {u},y,\varepsilon )\downarrow ]^{<b(\bar {u},y)} \wedge [g_{t}(\bar {u},\varepsilon )\downarrow ]^{<b(\bar {u},y)} ) \ \wedge \\ g_{t}(\bar {u},\varepsilon )= f_{n_{t}}(\bar {u},y,\varepsilon ) \end {array}\right )\end {array}\right )$ .

      Finally, we will simultaneously define two more $ \Sigma _{1}$ -definable functions in $\mathcal {M}$ :

      $$ \begin{align*} &\langle o(\diamondsuit,y),h(\diamondsuit,y)\rangle\\ & \quad := \min\left\lbrace\langle n_{t},\varepsilon\rangle \mathrm{E}(a)_{\zeta}: \left(\begin{array}{@{}c@{}} [b(\diamondsuit,y)\downarrow]\wedge\\ {}[ f_{n_{t}} ({\diamondsuit}, y, {\varepsilon}){\downarrow}]^{<b({\diamondsuit},y)} \ \wedge [g_{t} ({\diamondsuit},\varepsilon) {\downarrow}]^{< b (\diamondsuit,y)} \wedge\\ g_{t}(\diamondsuit,\varepsilon)= f_{n_{t}}(\diamondsuit,y,\varepsilon)\end{array}\right) \right\rbrace. \end{align*} $$
      (Note that, similar to the way we defined function g, we can express the above definition by a $\Sigma _{1}$ -formula.) Then, by statement (5) it holds that

   7. (7): $ \mathcal {M}\models \forall y\leq t(\bar {v},(a)_{\mathrm {i}}) \left (\begin{array}{@{}c@{}} ([b(\bar {v},y)\downarrow ]^{<b} \ \wedge \ \forall \epsilon <(a)_{\xi }( \epsilon \mathrm {E}(a)_{\xi }\rightarrow [f(\bar {v},y,\epsilon , \textbf {z}_{0})\downarrow ]^{<b})) \rightarrow\\ {}[\langle o(\bar {v},y),h(\bar {v},y)\rangle \downarrow ]\end {array}\right ) $ .

      Similarly, from statement (6) we may deduce that

   8. (8): $\mathcal {M}\models \forall y\leq t(\bar {u},(a)_{\mathrm {i}})\left (\begin{array}{@{}c@{}} ([b(\bar {u},y)\downarrow ] \ \wedge \ \forall \epsilon <(a)_{\xi }( \epsilon \mathrm {E}(a)_{\xi }\rightarrow [f(\bar {u},y,\epsilon ,\textbf {z}_{0})\downarrow]^{<b(\bar {u},y)})) \rightarrow \\ {}[\langle o(\bar {u},y),h(\bar {u},y)\rangle \downarrow] \end {array}\right ) $ .

      Now, we are ready to examine the mentioned underlined cases for $ k_{0} $ :

      1. – If $ k_{0}>1$ : By using Lemma 3.3, let $ (a)_{\rho }\in N_{0} $ be the code of the following subset of $ N_{0} $ :

         $$ \begin{align*} \kern-56pt A:=\left\lbrace\langle o(\bar{v},y),h(\bar{v},y)\rangle: \ \mathcal{M}\models \left(\begin{array}{@{}c@{}} y\leq t(\bar{v},(a)_{\mathrm{i}}) \wedge [\langle o(\bar{v},y),h(\bar{v},y)\rangle\downarrow]^{<b} \wedge\\ \forall \epsilon<(a)_{\xi}( \epsilon\mathrm{E}(a)_{\xi}\rightarrow[f(\bar{v},y,\epsilon,\textbf{z}_{0})\downarrow]^{<b} \wedge\\ \exists \varepsilon<(a)_{\zeta} \left(\begin{array}{@{}c@{}} \langle n_{1},\varepsilon\rangle\mathrm{E}(a)_{\zeta} \wedge [f_{n_{1}}(\bar{v},y,\varepsilon)\downarrow]^{<b} \wedge \\ f_{n_{1}}(\bar{v},y,\varepsilon)=f_{n_{1}}(\bar{u},m,\varepsilon) \end{array}\right) \end{array}\right) \right\rbrace .\end{align*} $$

      So, by statements (3), (7), and the definition of $ (a)_{\rho } $ , we conclude that

   9. (9): $\mathcal {M}\models \forall y\leq t(\bar {v},(a)_{\mathrm {i}}) \left ( \begin{array}{@{}c@{}} \forall \epsilon <(a)_{\xi }\left ( \begin{array}{@{}c@{}} \epsilon \mathrm {E}(a)_{\xi }\rightarrow [ f(\bar {v},y,\epsilon ,\textbf {z}_{0})\downarrow]^{<b} \wedge \\ {}[\langle o(\bar {v},y),h(\bar {v},y)\rangle \downarrow]^{<b} \wedge \\ \neg \langle o(\bar {v},y),h(\bar {v},y)\rangle \mathrm {E}(a)_{\rho } \end {array}\right ) \rightarrow \\ \exists \varepsilon <\mathrm {E}(a)_{\zeta }\bigvee _{t=2}^{k_{0}} \left (\begin{array}{@{}c@{}} \langle n_{t},\varepsilon \rangle \mathrm {E}(a)_{\zeta }\wedge [f_{n_{t}}(\bar {v},y,\varepsilon )\downarrow ]^{<b}\wedge \\ f_{n_{t}}(\bar {u},m,\varepsilon )= f_{n_{t}}(\bar {v},y,\varepsilon ) \end {array}\right ) \end {array}\right )$ .

      Let $ f'\in \mathcal {F} $ such that

      $$ \begin{align*} &\qquad\qquad f'(\diamondsuit,y,\epsilon,\langle\textbf{z}_{0},(a)_{\rho},(a)_{\zeta},(a)_{\xi}\rangle)=x \\ &\qquad\qquad\qquad\qquad\text{iff} \\ &x=f(\diamondsuit,y,\epsilon,\textbf{z}_{0})\ \wedge [\langle o(\diamondsuit,y),h(\diamondsuit,y)\rangle\downarrow] \wedge \neg \langle o(\diamondsuit,y),h(\diamondsuit,y)\rangle\mathrm{E}(a)_{\rho}. \end{align*} $$
      So by considering $ f' $ instead of $ f $ in statement (3) and $ \langle \textbf {z}_{0},(a)_{\rho },(a)_{\zeta },(a)_{\xi }\rangle $ instead of $ \textbf {z}_{0} $ , statement (9) leads to contradiction with the minimality of $ k_{0} $ .

      1. – If $ k_{0}=1 $ : In this case our plan for obtaining a contradiction is as follows: on one hand, by the definitions of $ h(\bar {u},y) $ and $ (a)_{\zeta } $ , $\mathcal {M}$ thinks that the cardinality of $ \{h(\bar {u},y): \ \mathcal {M}\models (y<t(\bar {u},(a)_{\mathrm {i}})\ \wedge \ [h(\bar {u},y)\downarrow ])\} $ is at most $ s_{0} $ . On the other hand, for every $ i\in I $ we will inductively define some $ \Sigma _{1} $ -functions, namely $ w(\bar {u},i) $ s, such that $ \mathcal {M}\models [w(\bar {u},i)\downarrow ]^{<t(\bar {u},(a)_{\mathrm {i}})} $ and $\mathcal {M}$ believes that there is a bijection between members of $ \{h(\bar {u},w(\bar {u},i)): \ i\in I \text { and } \mathcal {M}\models [h(\bar {u},w(\bar {u},i))\downarrow ]\} $ and the elements of I. So the contradiction is achieved. To be more precise, we define

         $$ \begin{align*} \kern-56pt w(\diamondsuit,0):=\min\left\lbrace y\leq t(\diamondsuit,(a)_{\mathrm{i}}): \ \left(\begin{array}{@{}c@{}}[b(\diamondsuit,y)\downarrow]\ \wedge \ [h(\diamondsuit,y)\downarrow]^{<(a)_{\zeta}} \wedge \\ \forall \epsilon<(a)_{\xi}( \epsilon\mathrm{E}(a)_{\xi}\rightarrow[f(\diamondsuit,y,\epsilon,\textbf{z}_{0})\downarrow]^{<b(\diamondsuit,y)} ) \end{array}\right) \right\rbrace, \end{align*} $$
         and

         $w(\diamondsuit ,i+1):= \min \left \lbrace y\leq t(\diamondsuit ,(a)_{\mathrm {i}}): \varphi (\diamondsuit ,i,y,(a)_{\zeta },(a)_{\xi },\textbf {z}_{0})\right \rbrace $ , where $ \varphi (\diamondsuit ,i,y,(a)_{\zeta },(a)_{\xi },\textbf {z}_{0}) $ is the following formula:

         $$ \begin{align*} \kern-24pt \left(\begin{array}{@{}c@{}} [b(\diamondsuit,y)\downarrow]\ \wedge [h(\diamondsuit,y)\downarrow]^{<(a)_{\zeta}} \wedge \\ \forall \epsilon<(a)_{\xi}( \epsilon\mathrm{E}(a)_{\xi}\rightarrow [f(\diamondsuit,y,\epsilon,\textbf{z}_{0})\downarrow]^{<b(\diamondsuit,y)}) \ \wedge \\ \forall x\leq i \left(\begin{array}{@{}c@{}} \left(\begin{array}{@{}c@{}} [h(\diamondsuit,w(\diamondsuit,x))\downarrow]^{<(a)_{\zeta}}\wedge\\ {}[f_{n_{1}}(\diamondsuit,y,h(\diamondsuit,w(\diamondsuit,x)))\downarrow]^{<b(\diamondsuit,y)}\wedge\\ {}[f_{n_{1}}(\diamondsuit,w(\diamondsuit,x),h(\diamondsuit,w(\diamondsuit,x)))\downarrow]^{<b(\diamondsuit,w(\diamondsuit,x))}\end{array}\right) \rightarrow \\ f_{n_{1}}(\diamondsuit,y,h(\diamondsuit,w(\diamondsuit,x)))\neq f_{n_{1}}(\diamondsuit,w(\diamondsuit,x),h(\diamondsuit,w(\diamondsuit,x))) \end{array}\right)\end{array}\right). \end{align*} $$

      First, we will show that $ \mathcal {M}\models [w(\bar {u},i)\downarrow ] $ for all $ i\in I $ . Otherwise, there exists the least $ 0<i_{0}\in I $ such that

   10. (10): $ \mathcal {M}\models \forall y\leq t(\bar {u},(a)_{\mathrm {i}}) \ \neg \varphi (\bar {u},i_{0},y,(a)_{\zeta },(a)_{\xi },\textbf {z}_{0})$ .

       Note that by the definition of $ (a)_{\xi } $ and $ (a)_{\zeta } $ it holds that

   11. (11): $\mathcal {M}\models ([b(\bar {u},m)\downarrow ] \ \wedge \ \forall \epsilon <(a)_{\xi }( \epsilon \mathrm {E}(a)_{\xi }\rightarrow [f(\bar {u},m,\epsilon ,\textbf {z}_{0})\downarrow ]^{<b(\bar {u},m)}) $ .

       So by statements (8), (10), and (11), there exists some $ i_{1}< i_{0} $ such that

   12. (12): $\mathcal {M}\models \left (\begin{array}{@{}c@{}} [h(\bar {u},w(\bar {u},i_{1}))\downarrow] \wedge [f_{n_{1}}(\bar {u},m,h(\bar {u},w(\bar {u},i_{1})))\downarrow] \wedge \\ {}[f_{n_{1}}(\bar {u},w(\bar {u},i_{1}),h(\bar {u},w(\bar {u},i_{1})))\downarrow] \wedge \\ f_{n_{1}}(\bar {u},m,h(\bar {u},w(\bar {u}, i_{1})))= f_{n_{1}}(\bar {u},w(\bar {u},i_{1}),h(\bar {u},w(\bar {u},i_{1}))) \end {array}\right ) $ .

       Clearly, $f_{n_{1}}(\bar {u},w(\bar {u},i_{1}),h(\bar {u},w(\bar {u},i_{1})))\in \mathrm {K}^{1}(\mathcal {M};N_{0}\cup \{\bar {u}\}) $ . So by statement (12), $f_{n_{1}}(\bar {u},m,h(\bar {u},w(\bar {u},i_{1}))) \in \mathrm {K}^{1}(\mathcal {M};M_{0}\cup \{\bar {u}\}) $ . So $ \mathcal {M}\models \neg \langle n_{1},h(\bar {u},w(\bar {u},i_{1}))\rangle \mathrm {E}(a)_{\zeta } $ (by the definition of $ (a)_{\zeta } $ ), which is in contradiction with the definition of the function $ h $ .

       Then, by the definition of $ w(\bar {u},i) $ s and statement (8), the function $ {i\mapsto h(\bar {u},w(\bar {u},i))} $ from $\{i: \ i\leq s_{0}+1\} $ into $ ((a)_{\zeta })_{\mathrm {E}} $ is well-defined and coded in $\mathcal {M}$ . So, since the cardinality of $ (a)_{\zeta } $ is less than $ s_{0}+1 $ , by $ \Sigma _{1}$ -Pigeonhole Principle in $\mathcal {M}$ , there exists some distinct $ i_{0}<i_{1}\leq s_{0}+1 $ such that

   13. (13): $\mathcal {M}\models h(\bar {u},w(\bar {u},i_{0}))=h(\bar {u},w(\bar {u},i_{1}))$ .

       Therefore, by statement (13) and the definition of $ h $ we conclude that

   14. (14): $ \mathcal {M}\models \left (\begin{array}{@{}c@{}} [g_{1}(\bar {u},h(\bar {u},w(\bar {u},i_{0})))\downarrow ] \wedge [g_{1}(\bar {u},h(\bar {u},w(\bar {u},i_{1})))\downarrow ]\wedge \\ g_{1}(\bar {u},h(\bar {u},w(\bar {u},i_{0})))=g_{1}(\bar {u},h(\bar {u},w(\bar {u},i_{1}))) \end {array}\right ) $ .

       Moreover, by the definition of $ h(\bar {u},w(\bar {u},i)) $ , for $ i=i_{0},i_{1} $ it holds that

   15. (15): $\mathcal {M}\models \left (\begin{array}{@{}c@{}} [f_{n_{1}}(\bar {u},w(\bar {u},i),h(\bar {u},w(\bar {u},i)))\downarrow ] \ \wedge [g_{1}(\bar {u},h(\bar {u},w(\bar {u})))\downarrow ] \wedge \\ f_{n_{1}}(\bar {u},w(\bar {u},i),h(\bar {u},w(\bar {u},i)))=g_{1}(\bar {u},h(\bar {u},w(\bar {u}))) \end {array}\right )$ .

       So statements (13–15) imply that

   16. (16): $\mathcal {M}\models f_{n_{1}}(\bar {u},w(\bar {u},i_{1}),h(\bar {u},w(\bar {u},i_{0})))=f_{n_{1}}(\bar {u}, w(\bar {u},i_{0}),h(\bar {u},w(\bar {u},i_{0}))) $ .

       But statement (16) is in contradiction with the definition of $ w(\bar {u},i_{1}) $ .

   17. (ii) Part (ii) of this lemma will be proved exactly like part (i), except we need an extra statement between statements (3) and (4): by using $ \Sigma _{1}$ -Collection, we deduce that

   18. (3’): $\mathcal {M}\models \exists w \forall x<u_{0} \left (\begin{array}{@{}c@{}} \forall \epsilon <(a)_{\lambda } \ ([f(\bar {u},x,\epsilon ,\textbf {z}_{0})\downarrow ]^{<w}\rightarrow \epsilon \mathrm {E}(a)_{\lambda })\rightarrow \\ \exists \varepsilon <(a)_{\eta } \bigvee _{t\leq k_{1}}\left (\begin{array}{@{}c@{}} \langle n_{t},\varepsilon \rangle \mathrm {E}(a)_{\eta }\wedge [f_{n_{t}}(\bar {u},x,\varepsilon )\downarrow ]^{<w}\wedge \\ f_{n_{t}}(\bar {u},x,\varepsilon )= f_{n_{t}}(\bar {v},m',\varepsilon ) \end {array}\right ) \end {array}\right ) $ ;

       in which $(a)_{\lambda }\in N_{0} $ and $ (a)_{\eta }\in N_{0} $ code the following Y and $Y',$ respectively:

       $$ \begin{align*} &Y:=\lbrace x\in M: \ \mathcal{M}\models\exists i<s_{0}(x=(a)_{i}\wedge[f(\bar{v},m',(a)_{i},\textbf{z}_{0})\downarrow]^{<b} ) \rbrace, \text{ and } \\ &Y':=\lbrace \langle n,x\rangle\in M: \ \mathcal{M}\models\exists i<s_{0}(x=(a)_{i}\wedge \bigvee_{t=0}^{k_{0}}n=n_{t} \wedge \langle n,i\rangle\mathrm{E}\alpha') \rbrace. \end{align*} $$

Proof of Theorem 3.4

By Lemma 3.4.1, there exists some $ a\in M $ such that $ {N_{0}=\{(a)_{i}: i\in I\}} $ and $ (a)_{i}\neq (a)_{i} $ for distinct $ i,j\in I $ . Now, in order to construct $ j $ , first by using strong $ \Sigma _{1}$ -Collection in $\mathcal {M}$ , we will find some $ b\in M $ such that

$$ \begin{align*} \mathcal{M}\models [f((a)_{i})\downarrow]\rightarrow[f((a)_{i})\downarrow]^{<b}, \text{ for all } f\in\mathcal{F} \text{ and all } i\in I. \end{align*} $$

Then, by using back-and-forth method we will inductively build finite functions $\bar {u}\mapsto \bar {v}$ such that $ \bar {u},\bar {v}\in M $ , and $\mathcal {M}\models (\bar {v}<b \ \wedge \ \mathrm {P}(\bar {u},\bar {v}) \ \wedge \mathrm {Q}(\bar {u},\bar {v}) )$ , where $ \mathrm {P}(\bar {u},\bar {v}) $ and $ \mathrm {Q}(\bar {u},\bar {v}) $ are properties as stated in Lemma 3.4.3. Through the “forth” stages of back-and-forth we shall make the domain of $ j $ to be equal to $ M $ , and “back” stages are for making the range of $ j $ to be an initial segment of $\mathcal {M}$ . For the first step of induction, we will choose $0\mapsto 0 $ . Then, suppose $\bar {u}\mapsto \bar {v}$ is built such that $\mathcal {M}\models (\bar {v}<b \ \wedge \ \mathrm {P}(\bar {u},\bar {v}) \ \wedge \mathrm {Q}(\bar {u},\bar {v}) )$ .

“Forth” stages: Let $ m\in M\setminus \{\bar {u}\} $ be arbitrary. By the definition of $\mathcal {M}$ , without loss of generality, we can assume that $ m\leq t(\bar {u},(a)_{\mathrm {i}}) $ for some $ t\in \mathcal {F} $ and $ \mathrm {i}\in I $ . Moreover, let $ \alpha \in M $ be as in Lemma 3.4.2. In order to find some image for $ m $ , for every $ s\in M $ we define the following bounded $ \Pi _{1} $ -type:

$$ \begin{align*} &\qquad p_{s}(y):= \lbrace y\leq t(\bar{v},(a)_{\mathrm{i}})\rbrace\cup p_{s1}(y)\cup p_{s2}(y), \text{where} \\ &\quad {p_{s1}(y):=\lbrace\forall i<s([f(\bar{u},m,(a)_{i})\downarrow]\rightarrow [f(\bar{v},y,(a)_{i})\downarrow]^{<b}): f\in\mathcal{F}\rbrace;} \\ &\qquad\qquad\qquad\qquad\qquad\text{and} \\ &p_{s2}(y):=\left\lbrace \forall i<s \left(\begin{array}{@{}c@{}} ([f_{n}(\bar{v},y,(a)_{i})\downarrow]^{<b} \wedge\langle n,i\rangle\mathrm{E}\alpha)\rightarrow \\ f_{n}(\bar{u},m,(a)_{i})\neq f_{n}(\bar{v},y,(a)_{i})\end{array}\right): \ n\in\mathbb{N} \right\rbrace. \end{align*} $$

We claim that there exists some $ s> I $ such that the type $ p_{s}(y) $ is finitely satisfiable in $\mathcal {M}$ . Then since $ p_{s} $ is a $ \Pi _{1} $ , bounded and recursive type in $\mathcal {M}$ , there exists some $ m' $ which realizes $ p_{s}(y) $ in $\mathcal {M}$ . Therefore, $\mathrm {P}((\bar {u},m),(\bar {v},m')) $ and $ \mathrm {Q}((\bar {u},m),(\bar {v},m')) $ hold in $\mathcal {M}$ , and this finishes the “forth” stage.

In order to prove the above claim, let $ d> I $ be an arbitrary and fixed element of $ M $ . Moreover, suppose $i,s\in M$ , and $ \Theta (s,i,\bar {u},m,\bar {v},b,a,\alpha ,\beta ,(a)_{\mathrm {i}}) $ is the following $ \Delta _{0}$ -formula:

$$ \begin{align*} {\forall r<i \ \exists y\leq t(\bar{v},(a)_{\mathrm{i}}) \left(\begin{array}{@{}c@{}} \forall w<s (\langle r,w\rangle\mathrm{E}\beta\rightarrow [f_{r}(\bar{v},y,(a)_{w})\downarrow]^{<b}) \ \wedge \\ \forall w<s \forall r'<i\left(\begin{array}{@{}c@{}} ([f_{r'}(\bar{v},y,(a)_{w})\downarrow]^{<b}\wedge \langle r',w\rangle\mathrm{E}\alpha)\rightarrow \\ f_{r'}(\bar{u},m,(a)_{w})\neq f_{r'}(\bar{v},y,(a)_{w}) \end{array}\right) \end{array}\right) }, \end{align*} $$

where $ \beta $ is the code of the following $ \Sigma _{1}$ -definable set in $\mathcal {M}$ :

$$ \begin{align*} L:=\lbrace \langle r,w\rangle<d: \ \mathcal{M}\models[f_{r}(\bar{u},m,(a)_{w})\downarrow]\rbrace. \end{align*} $$

Note that the parameter $ i $ in $ \Theta $ is for bounding indexes of functions which appear in $ \Theta $ . Moreover, the parameter $ s $ is for bounding elements of $ N_{0} $ appearing in $ \Theta $ ; i.e., if $ \Theta $ contains some element of the form $ (a)_{w} $ , then $ w<s $ . Now, for every $ i\in M $ , we let $\mathrm {G}(i) $ be an upper bound for parameters $ s $ as above. To be more precise, we define

$$ \begin{align*} \mathrm{G}(i):=\mathrm{max}\lbrace x<d: \ \mathcal{M}\models \Theta(x,i,\bar{u},m,\bar{v},b,a,\alpha,\beta,(a)_{\mathrm{i}}) \rbrace. \end{align*} $$

Clearly $ \mathrm {G} $ is $ \Delta _{0}$ -definable function in $\mathcal {M}$ , and $ I\subseteq \mathrm {Dom}(\mathrm {G}) $ (we assume $ \mathrm {max}(\emptyset )=0 $ ). Therefore, since $ I $ is strong, there exists some $ e> I $ such that for all $ i\in I $ , $ \mathrm {G}(i)> I $ iff $ \mathrm {G}(i)>e $ . We will show that $ p_{e}(y) $ is finitely satisfiable in $\mathcal {M}$ :

First, note that, $ p_{e1}(y) $ is closed under conjunctions. (This holds similar to the way statement (1) in the proof of Lemma 3.4.3 holds.) So let $f_{n}, f_{n_{1}},\ldots ,f_{n_{k}} $ be some finite number of elements of $ \mathcal {F} $ , and let $ n^{*}=\mathrm {max}\lbrace n,n_{0},\ldots ,n_{k}\rbrace $ . Then, use Lemma 3.4.3(i), $ (n^{*}+2)$ -many times; i.e., for every $ t=0,\ldots ,n^{*}+1 $ consider $ f_{t} $ instead of $ f $ in the assertion of Lemma 3.4.3(i), $ 0\in M_{0} $ instead of $ z $ , and $ f_{1},\ldots ,f_{n^{*}} $ . So by Lemma 3.4.3(i), for every $ t=0,\ldots ,n^{*}+1 $ there exists some $ s_{t}> I $ such that

1. (1): $ \mathcal {M}\models \exists y<b\ \Psi (f_{t},f_{1},\ldots ,f_{n^{*}}, \bar {u},m,\bar {v},y,b,a,s_{t},\alpha ,0,(a)_{\mathrm {i}}) $ .

   Then, let $ s^{*}:=\mathrm {min}\lbrace s_{t}: \ t<n^{*}+1\rbrace $ . Therefore, by statement (1) and the definitions of $ \Theta $ and $ \Psi $ it holds that

2. (2): $ {\mathcal {M}\models \Theta (s^{*},n^{*},\bar {u},m,\bar {v},b,a,\alpha ,\beta ,(a)_{\mathrm {i}})} $ .

   So from statement (2) and the definition of $ \mathrm {G} $ , we infer that $ \mathrm {G}(n^{*})>I$ and it holds that

3. (3): $ {\mathcal {M}\models \Theta (\mathrm {G}(n^{*}),n^{*}, \bar {u},m,\bar {v},b,a,\alpha ,\beta ,(a)_{\mathrm {i}})} $ .

   Consequently $ \mathrm {G}(n^{*})>e $ , and again by the definition of $ \Theta $ and statement (3), we deduce that

4. (4): $\mathcal {M}\models \Theta (e,n^{*},\bar {u},m,\bar {v},b,a,\alpha ,\beta ,(a)_{\mathrm {i}})$ .

   Statement (4) implies that

5. (4): $ \mathcal {M}\models \exists y\leq t(\bar {v},(a)_{\mathrm {i}}) \left (\begin{array}{@{}c@{}} \forall i<e ([f_{n}(\bar {u},m,(a)_{i})\downarrow ]\rightarrow [f_{n}(\bar {v},y,(a)_{i})\downarrow ]^{<b}) \ \wedge \\ \bigwedge _{t= 1}^{k}\forall i<e \left (\begin{array}{@{}c@{}} ([f_{n_{t}}(\bar {v},y,(a)_{i})\downarrow ]^{<b}\wedge \langle n_{t},i\rangle \mathrm {E}\alpha )\rightarrow \\ f_{n_{t}}(\bar {u},m,(a)_{i})\neq f_{n_{t}}(\bar {v},y,(a)_{i}) \end {array}\right ) \end {array}\right ) $ .

So statement (4) finishes the proof of the claim.

“Back” stages: Let $ m'\in M\setminus \{\bar {v}\} $ such that $ m'<v_{0}:=\max \{\bar {v}\} $ , and $ u_{0}:=\max \{\bar {u}\} $ . In order to find some element of $ M $ whose image is $ m' $ , we modify the proof of the “forth” stage in the following way:

• • Replace $ p_{s}(y) $ by

  $$ \begin{align*} &\qquad\qquad\qquad q_{s}(x):= \lbrace x<u_{0}\rbrace\cup q_{s1}(x)\cup q_{s2}(x) , \text{where,} \\ &{q_{s1}(x):= \lbrace\forall i<s(\neg [f(\bar{v},m', (a)_{i})\downarrow]^{<b}\rightarrow\neg [f(\bar{u},x,(a)_{i})\downarrow] ): f\in\mathcal{F}\rbrace;} \text{ and}\\ &\qquad {q_{s2}(x):=\left\lbrace\begin{array}{@{}c@{}} \forall i<s\left(\begin{array}{@{}c@{}} \left(\begin{array}{@{}c@{}}\langle n,i\rangle\mathrm{E}\alpha'\wedge\\ {}[f_{n}(\bar{u},x,(a)_{i})\downarrow]\end{array}\right)\rightarrow \\ f_{n}(\bar{u},x,(a)_{i})\neq f_{n}(\bar{v},m',(a)_{i}) \end{array}\right): \ n\in\mathbb{N} \end{array}\right\rbrace}. \end{align*} $$

• • Replace $ \Theta (s,i,\bar {u},m,\bar {v},b,a,\alpha ,\beta ) $ with $ \Theta '(s,i,\bar {u},\bar {v},m',b,a,\alpha ',\beta ') $ :

  $$ \begin{align*} \forall r<i \ \exists x<u_{0}\left(\begin{array}{@{}c@{}} \forall w<s(\langle x,r,w\rangle\mathrm{E}\beta'\rightarrow[f_{r}(\bar{v},m',(a)_{w})\downarrow]^{<b})\wedge \\ \forall w<s \forall r'<i \left(\begin{array}{@{}c@{}} (\langle r',w\rangle\mathrm{E}\alpha'\wedge\langle x,r',w\rangle\mathrm{E}\beta')\rightarrow\\ f_{r'}(\bar{u},m,(a)_{w})\neq f_{r'}(\bar{v},y,(a)_{w}))\end{array}\right) \end{array}\right),\end{align*} $$
  where $ \beta ' $ is the code of the following $ \Sigma _{1}$ -definable set in $\mathcal {M}$ :
  $$ \begin{align*} L':=\lbrace\langle x,r,w\rangle: \ \mathcal{M}\models (x<u_{0} \wedge w<d \wedge r<d \wedge [f_{r}(\bar{u},x,(a)_{w})\downarrow]) \rbrace. \end{align*} $$

The rest of the argument goes smoothly by modifying the “forth” stage according to the above changes, and this completes the proof.

Proof Suppose ${ M_{0}=\lbrace (a)_{i}: \ i\in I\rbrace } $ , for some $ a\in M $ such that $ (a)_{i}\neq (a)_{j} $ for all distinct $ i, j\in I $ .

$ (1)\Rightarrow (2) $ : If $ M_{0}=I $ , then by Theorem 2.4(2), we are done. So suppose $ I\subsetneq M_{0} $ . First, by using Theorem 3.4 let $ h $ be some proper initial self-embedding of $ \mathrm {H}^{1}(\mathcal {M};M_{0}) $ such that $ \mathrm {Fix}(h)=M_{0} $ . Moreover, fix some $b\in \mathrm {H}^{1}(\mathcal {M};M_{0})\setminus M_{0} $ such that $ h( \mathrm {H}^{1}(\mathcal {M};M_{0}))<b $ . Now, by using strong $ \Sigma _{1}$ -Collection in $ \mathrm {H}^{1}(\mathcal {M};M_{0}) $ , and since $ \mathrm {H}^{1}(\mathcal {M};M_{0})\prec _{\Sigma _{1}}\mathcal {M} $ , we can find some $ d\in \mathrm {H}^{1}(\mathcal {M};M_{0}) $ such that

$$ \begin{align*} \mathcal{M}\models [f((a)_{i},b)\downarrow]\rightarrow[f((a)_{i},b)\downarrow]^{<d}, \text{ for all } f\in\mathcal{F} \text{ and all } i\in I. \end{align*} $$

Therefore, by Theorems 2.1 and 2.3 and Remark 1, there exists some proper initial embedding $ k:\mathcal {M}\hookrightarrow \mathrm {H}^{1}(\mathcal {M};M_{0}) $ such that $ M_{0}\subseteq \mathrm {Fix}(k) $ , $ k(M)<d, $ and $ b\in k(M) $ (note that since $ \mathrm {H}^{1}(\mathcal {M};M_{0}) $ is an initial segment of $\mathcal {M}$ , then $ \mathrm {SSy}_{I}(\mathcal {M})=\mathrm {SSy}_{I}(\mathrm {H}^{1}(\mathcal {M};M_{0})) $ ). Finally, we put $ j:=k^{-1}hk $ . It is easy to check that $ j $ is a well-defined proper initial self-embedding of $\mathcal {M}$ such that $ \mathrm {Fix}(j)=M_{0} $ .

$ (2)\Rightarrow (1) $ : We combine the methods used in the proofs of Theorems 5.1 and 6.1 of [Reference Bahrami and Enayat1]. Suppose I is not strong; i.e., there exists some coded function $ f $ in $\mathcal {M}$ such that $ I\subseteq \mathrm {Dom}(f) $ , and the set $ {D:=\lbrace f(i): \ i\in I \wedge I<f(i)\rbrace } $ is downward cofinal in $ M\setminus I $ .

Let $ b\in M\setminus M_{0} $ and $ g:=j(f) $ . For every $ k\in M $ , we put

$$ \begin{align*} A_{k}:=\lbrace\langle r,y\rangle<k: \ \mathcal{M}\models\mathrm{Sat}_{\Delta_{0}}(\delta_{r}((a)_{y},b))\rbrace. \end{align*} $$

Since $ A_{k} $ is bounded and $ \Delta _{1}$ -definable, it is coded by some $ s_{k} $ in $\mathcal {M}$ . Moreover, the function $ k\mapsto s_{k} $ is $ \Delta _{1}$ -definable in $ \mathcal {M} $ . Now, we define

$$ \begin{align*} h(k):=\mu_{x} \ (\forall\langle r,y\rangle<k \ (\langle r,y\rangle\mathrm{E}s_{k}\rightarrow\mathrm{Sat}_{\Delta_{0}}(\delta_{r}((a)_{y},x)))). \end{align*} $$

So note that:

1. (I) For every $ k> I $ , we have $ \mathrm {Th}_{\Delta _{0}}(\mathcal {M};b,\{(a)_{i}\}_{i\in I})\subseteq \mathrm {Th}_{\Delta _{0}}(\mathcal {M};h(k),\{(a)_{i}\}_{i\in I})$ .

2. (II) For every $ i\in I $ , $ h(i)$ is well-defined and inside $ M_{0}=\mathrm {Fix}(j) $ ; the reason behind this statement is that for every $ i\in I $ we consider the following set:

   $$ \begin{align*} B_{i}:=\lbrace\langle r,\epsilon\rangle: \ \mathcal{M}\models \exists y<i ((a)_{y}=\epsilon\wedge \langle r,y\rangle\mathrm{E}s_{i})\rbrace. \end{align*} $$
   Then, by Lemma 3.3, $ B_{i} $ is coded by some $ \alpha _{i}\in M_{0}=\mathrm {Fix}(j) $ . So it holds that
   $$ \begin{align*} \mathcal{M}\models h(i)=\mu_{x}(\forall \langle r,\epsilon\rangle\mathrm{E}\alpha_{i} \ (\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(\epsilon,x))). \end{align*} $$
   As a result, since $ \mathcal {M}_{0}\prec _{\Sigma _{1}}\mathcal {M} $ , statement (II) holds.

Now, let $ h':=j(h) $ . So for all $ i\in I $ , and all $ u<i $ such that $ f(u)<i $ , statement (II) implies that

$$ \begin{align*} h'(g(u))=j(h)(j(f)(u))=j(h)(j(f)(j(u)))=j(h(f(u)))=h(f(u)). \end{align*} $$

Therefore, for all $ i\in I $ , $ \mathcal {M}\models \varphi (i,f,g,h,h') $ , where $ \varphi (i,f,g,h,h') $ is the following $ \Delta _{1}$ -formula:

$$ \begin{align*} \forall u<i \ (f(u)<i\rightarrow h(f(u))=h'(g(u))). \end{align*} $$

So by $ \Sigma _{1} $ -Overspill in $\mathcal {M}$ , there exists some $ s> I $ such that

$$ \begin{align*} (\spadesuit): \ \ \forall u<s \ (f(u)<s\rightarrow h(f(u))=h'(g(u))). \end{align*} $$

Since $ D $ is downward cofinal in $ M\setminus I $ , there is some $ i_{0}\in I $ such that $ I<f(i_{0})<s $ . Let $ c:=h(f(i_{0})) $ . On one hand, by (I), $ \mathrm {Th}_{\Delta _{0}}(\mathcal {M};b,\{(a)_{i}\}_{i\in I})\subseteq \mathrm {Th}_{\Delta _{0}}(\mathcal {M};c,\{(a)_{i}\}_{i\in I})$ . As a result, because $ b\notin M_{0} $ , we have $ c\notin M_{0}=\mathrm {Fix}(j) $ . On the other hand $ (\spadesuit ) $ implies that

$$ \begin{align*} j(c)=j(h(f(i_{0})))=j(h)(j(f)((j(i_{0})))=h'(g(i_{0}))=h(f(i_{0}))=c. \end{align*} $$

As a result, I has to be strong in $\mathcal {M}$ .

Proof

1. (1) Let $ a\in \mathrm {Fix}(j) $ be arbitrary and fixed. Since $ \mathrm {Fix}(j)\prec _{\Sigma _{1}}\mathcal {M} $ , it suffices to prove that $ \mathrm {K}^{1}(\mathcal {M};a) $ is not cofinal in $ \mathrm {Fix}(j) $ . Since $ \mathcal {M}\models \mathrm {B}^{+}\Sigma _{1} $ , there exists some $ t_{0}\in M $ such that $\mathrm {K}^{1}(\mathcal {M};a)<t_{0} $ . Moreover, by Lemma 2.5(2) there exists some $ t_{00}\in \mathrm {Fix}(j) $ such that ${\mathrm {Th}_{\Sigma _{1}}(\mathcal {M};t_{0},a)\subseteq \mathrm {Th}_{\Sigma _{1}}(\mathcal {M};t_{00},a)}$ . Therefore, $ \mathrm {K}^{1}(\mathcal {M};a)<t_{00} $ .

2. (2) By Theorem 2.2(2), and part (1) of this lemma, it suffices to prove that $ \mathbb {N} $ is not $ \Pi _{1}$ -definable in $ \mathrm {Fix}(j) $ . Suppose not; i.e., $ \mathbb {N} $ is definable in $ \mathrm {Fix}(j) $ by some $ \Pi _{1}$ -formula $ \pi (x) $ . By Lemma 2.5(1), $ \mathrm {Fix}(j)\cap M\setminus \mathbb {N} $ is downward cofinal in $ M\setminus \mathbb {N} $ . So by $ \Sigma _{1}$ -Underspill in $\mathcal {M}$ , there exists some $ n\in \mathbb {N} $ such that $ \mathcal {M}\models \neg \pi (n) $ , and consequently since $ \mathrm {Fix}(j)\prec _{\Sigma _{1}}\mathcal {M} $ , $ \mathrm {Fix}(j)\models \neg \pi (n) $ , which is a contradiction.

Proof By Theorem 2.2(1) and the previous lemma, it is enough to prove that $ {\mathrm {SSy}(\mathrm {Fix}(j))=\mathrm {SSy}(\mathcal {M})} $ . So let $ X=\mathbb {N}\cap a_{\mathrm {E}} $ for some $ a\in M $ . Since $ \mathbb {N} $ is not strong in $\mathcal {M}$ , by Lemma 2.5(2) there exists some $ b\in \mathrm {Fix}(j) $ such that $ \mathrm {Th}_{\Sigma _{1}}(\mathcal {M};a)\subseteq \mathrm {Th}_{\Sigma _{1}}(\mathcal {M};b) $ . Therefore, $ X=\mathbb {N}\cap b_{\mathrm {E}} $ , and this finishes the proof.

Proof The equivalences of statements (1)–(5) is a straightforward implication of Corollary 3.5 and Lemma 4.1(1). Moreover, $ (6)\Rightarrow (1) $ holds by Corollary 4.2. In order to prove $ (4)\Rightarrow (6) $ , similar to the proof of Theorem 3.2(3), we will find some small recursively saturated elementary submodel $ \mathcal {M}_{0} $ of $\mathcal {M}$ . So statement (4) will provide us with a proper initial self-embedding $ j $ of $\mathcal {M}$ such that $ \mathrm {Fix}(j)=M_{0} $ . Clearly $ \mathrm {Fix}(j)\models \mathrm {B}\Sigma _{1} $ . Moreover, as we mentioned in the beginning of Section 3, $ \mathrm {SSy}(\mathcal {M}_{0})\neq \mathrm {SSy}(\mathcal {M}) $ . As a result, $ \mathrm {Fix}(j) $ is isomorphic to no proper initial segment of $\mathcal {M}$ .

Proof Put $ I:=\mathrm {I}^{1}(\mathcal {M};M_{0}) $ , $ J:=\mathrm {I}^{1}(\mathcal {N};j(M_{0})) $ , and let $ A\subseteq M_{0} $ be arbitrary. If $ {A=I\cap (\alpha _{\mathrm {E}})^{\mathcal {M}}} $ for some $ \alpha $ in $\mathcal {M}$ , then clearly $ j(A)=J\cap ((\hat {j}(\alpha ))_{\mathrm {E}})^{\mathcal {N}}$ . Conversely, suppose $ j( A)\in \mathrm {SSy}_{J}(\mathcal {N}) $ . Since $ M_{0} $ is bounded in $\mathcal {M}$ , we have $ J\subsetneq _{e}\hat {j}( M) $ . As a result, $ j(A)\in \mathrm {SSy}_{J}(\hat {j}( M)) $ , which implies that $A\in \mathrm {SSy}_{I}(\mathcal {M}) $ .