# Self-embeddings of models of arithmetic; fixed points, small submodels, and
extendability

Saeideh Bahrami
<EMAIL_ADDRESS>
###### Abstract

In this paper we will show that for every cut $I$ of any countable nonstandard
model $\mathcal{M}$ of $\mathrm{I}\Sigma_{1}$, each $I$-small
$\Sigma_{1}$-elementary submodel of $\mathcal{M}$ is of the form of the set of
fixed points of some proper initial self-embedding of $\mathcal{M}$ iff $I$ is
a strong cut of $\mathcal{M}$. Especially, this feature will provide us with
some equivalent conditions with the strongness of the standard cut in a given
countable model $\mathcal{M}$ of $\mathrm{I}\Sigma_{1}$. In addition, we will
find some criteria for extendability of initial self-embeddings of countable
nonstandard models of $\mathrm{I}\Sigma_{1}$ to larger models.

##  1 Introduction

In 1973, Harvey Friedman proved a striking result for countable nonstandard
models of finite set theory, and consequently for countable models of Peano
arithmetic, $\mathrm{PA}$, stating that every countable nonstandard model of
$\mathrm{PA}$ carries a proper initial self-embedding; here an initial self-
embedding is a self-embedding whose image is an initial segment of the ground
model [5]. Afterwards, many versions of Friedman’s style Theorem appeared in
the literature of model theory of arithmetic (e.g. see [3] or [16]). In [1],
it is shown that some results on the set of fixed points of automorphism of
countable recursively saturated models of $\mathrm{PA}$ can be generalized for
initial self-embeddings of countable nonstandard models of
$\mathrm{I}\Sigma_{1}$ (see Theorem 2.4 below). In this paper, inspired by
results about automorphisms of models of $\mathrm{PA}$, we will investigate
some more properties of countable models of $\mathrm{I}\Sigma_{1}$ through
initial self-embeddings.

In [4], Enayat generalized the notion of a small submodel from [15], to
$I$-small111In his paper [4], Enayat called such submodels $I$-coded. The name
$I$-small is borrowed from Kossak-Schmerl’s book [14]. for a given cut $I$ of
a model of $\mathrm{PA}$ (see Definition 1 below), and proved that:

######  Theorem 1.1 (Enayat).

Suppose $\mathcal{M}\models\mathrm{PA}$ is countable, recursively saturated,
and $I$ is a strong cut of $\mathcal{M}$. Moreover, let $\mathcal{M}_{0}$ be
an $I$-small elementary submodel of $\mathcal{M}$. Then there exists some
automorphism $j$ of $\mathcal{M}$ such that $M_{0}$ is equal to the set of
fixed points of $j$.

In section 3 of this paper, after investigating some basic properties of
$I$-small $\Sigma_{1}$-elementary submodels of a countable model $\mathcal{M}$
of $\mathrm{I}\Sigma_{1}$ for some cut $I$ of $\mathcal{M}$, we will refine
the above theorem for initial self-embeddings; i.e we will show that $I$ is
strong in $\mathcal{M}$ iff every $I$-small $\Sigma_{1}$-elementary submodel
of $\mathcal{M}$ is equal to the set of fixed points of some proper initial
self-embedding of $\mathcal{M}$. This result also generalizes one of the main
theorems of [1] (see Corollary 4.3 below).

Section 4 of this paper, is devoted to the investigation of equivalent
conditions to strongness of the standard cut, denoted by $\mathbb{N}$, in a
countable model of $\mathrm{I}\Sigma_{1}$, through the set of fixed points of
initial self-embeddings. In [13], it is shown that:

######  Theorem 1.2 (Kossak-Schmerl).

Suppose $\mathcal{M}$ is a countable recursively saturated model of
$\mathrm{PA}$. If $\mathbb{N}$ is not strong in $\mathcal{M}$, then for every
automorphism $j$ of $\mathcal{M}$ the set of fixed points of $j$ is isomorphic
to $\mathcal{M}$.

In Corollary 4.2, we will show that for every countable nonstandard model
$\mathcal{M}$ of $\mathrm{I}\Sigma_{1}$, if $\mathbb{N}$ is not strong in
$\mathcal{M}$, then the set of fixed points of any initial self-embedding $j$
of $\mathcal{M}$ is either a model of $\neg\mathrm{B}\Sigma_{1}$, or is
isomorphic to some proper initial segment of $\mathcal{M}$. Then, we conclude
that $\mathbb{N}$ is strong in a countable recursively saturated model
$\mathcal{M}$ of $\mathrm{PA}$ iff there exists some proper initial self-
embedding $j$ of $\mathcal{M}$ such that the set of fixed points of $j$ is
small in $\mathcal{M}$ and consequently it is not isomorphic to any proper
initial segment of $\mathcal{M}$.

In section 5, we will study the extendability of initial embeddings of models
of $\mathrm{I}\Sigma_{1}$ to larger models. In particular, we will prove that
any isomorphism between two $\Sigma_{1}$-elementary initial segment of a
countable nonstandard model $\mathcal{M}$ of $\mathrm{I}\Sigma_{1}$ is
extendable to some initial self-embedding of $\mathcal{M}$ iff it preserves
coded subsets (for the case of automorphisms of countable recursively
saturated models of $\mathrm{PA}$ this condition is only a necessary condition
for extendability to larger models [11]).

##  2 Preliminaries

In this section we will review some definitions and results which are used
through this paper. All unexplained notions can be found in [6] and [7].

  * •

Through this paper, we will work in the language of arithmetic
${\mathcal{L}_{A}:=\\{+,.,<,0,1\\}}$. For a given class $\Gamma$ of
$\mathcal{L}$-formulas (where $\mathcal{L}\supseteq\mathcal{L}_{A}$),
$\mathrm{I}\Gamma$ is the fragment of
$\mathrm{PA}^{*}:=\mathrm{PA}(\mathcal{L})$ with the induction scheme limited
to formulas of $\Gamma$. The $\Gamma$-Collection scheme, denoted by
$\mathrm{B}\Gamma$, consists of the formulas of the following form for every
$\varphi\in\Gamma$:

$\forall\bar{z},u\ ((\forall x<u\ \exists y\
\varphi(x,y,\bar{z}))\rightarrow\exists v\ (\forall x<u\ \exists y<v\
\varphi(x,y,\bar{z}))).$

Moreover, the strong $\Gamma$-Collection scheme, denoted by
$\mathrm{B}^{+}\Gamma$, consists of the formulas of the following form for
every $\varphi\in\Gamma$:

$\forall\bar{z},u\ \exists v\ \forall x<u\ (\exists y\
\varphi(x,y,\bar{z})\rightarrow\exists y<v\ \varphi(x,y,\bar{z})).$

It is folklore that
$\mathrm{I}\Sigma_{n+1}\vdash\mathrm{B}^{+}\Sigma_{n+1}\vdash\mathrm{B}\Sigma_{n+1}$
for all $n\in\omega$; moreover, for every $n\in\omega$, neither
$\mathrm{I}\Sigma_{n}\nvdash\mathrm{B}\Sigma_{n+1}$, nor
$\mathrm{I}\Sigma_{n}\nvdash\neg\mathrm{B}\Sigma_{n+1}$ (see [6, Ch. I]).

  * •

Within $\mathrm{I}\Delta_{0}+\mathrm{Exp}$, the $\Delta_{0}$-formula
$x\mathrm{E}y$ denotes the Ackermann’s membership relation, asserting that
”the $x$-th bit of the binary expansion of $y$ is 1”. For every
${\mathcal{M}\models\mathrm{I}\Delta_{0}+\mathrm{Exp}}$ and each $a\in M$,
$a_{\mathrm{E}}$ denotes the set of $\mathrm{E}$-members of $a$ in
$\mathcal{M}$. Moreover, the $\Delta_{0}$-formulas $\mathrm{Card}(x)=y$,
$\langle\bar{x}\rangle=y$, $\mathrm{Len}(x)=y$, $(x)_{y}=z$, and
$x\upharpoonright_{y}=z$ respectively express that ”there exists some
bijection between $y$ and the set coded by $x$”, ”the sequence number of
$\bar{x}$ is $y$”, ”length of the sequence coded by $x$ is $y$”, ”the $y$-th
element of the sequence number $x$ is $z$”, and ”the restriction of the
sequence number $x$ to $y$ is $z$”. In addition, for every formula
$\varphi(x)$, by the formula $y=\mu_{x}\ \varphi(x)$ we mean ”y is the least
element such that $\varphi(y)$ holds”.

Furthermore, for every $n\in\omega$ there exist $\mathcal{L}_{A}$-formulas
$\mathrm{Sat}_{\Sigma_{n}}$ and $\mathrm{Sat}_{\Pi_{n}}$ which define the
satisfaction predicate for $\Sigma_{n}$-formulas and $\Pi_{n}$-formulas
respectively, in an ambient model. For every natural number $n>0$, it can be
shown that $\mathrm{Sat}_{\Sigma_{n}}$ and $\mathrm{Sat}_{\Pi_{n}}$ are
$\Sigma_{n}$ and $\Pi_{n}$ respectively in $\mathrm{I}\Sigma_{1}$. Moreover,
$\mathrm{Sat}_{\Delta_{0}}\in\Delta_{1}^{\mathrm{I}\Sigma_{1}}$ [6, ch. I,
Thm. 1.75]. If $\mathcal{M}$ is a nonstandard model of $\mathrm{I}\Sigma_{n}$,
the aforementioned feature along with $\Sigma_{n}$-Overspill in $\mathcal{M}$
imply that every coded $\Sigma_{n}$-type and every coded bounded
$\Pi_{n}$-type is realized in $\mathcal{M}$.

  * •

$\Sigma_{n}$-Pigeonhole Principle. For every $n>0$, if
$\mathcal{M}\models\mathrm{I}\Sigma_{n}$, $a\in M$, and $\varphi$ is a
$\Sigma_{1}$-formula which defines a function from $a+1$ into $a$ in
$\mathcal{M}$, then $\varphi$ is not one-to-one [6].

  * •

Given $\mathcal{L}_{A}$-structure $\mathcal{M}$ and subset $X$ of $M$, for
every $n>0$, we define:

    * –

$\mathrm{K}^{n}(\mathcal{M};X):=$the set of all $\Sigma_{n}$-definable element
of $\mathcal{M}$ with parameters from $X$;

    * –

$\mathrm{I}^{n}(\mathcal{M};X):=\\{x:\ x\leq a\text{ for some
}a\in\mathrm{K}^{n}(\mathcal{M};X)\\}$;

    * –

$\mathrm{H}^{n}(\mathcal{M};X):=\bigcup_{k\in\omega}\mathrm{H}_{k}^{n}(\mathcal{M};X)$,
where:

$\mathrm{H}_{0}^{n}(\mathcal{M};X):=\mathrm{I}^{n}(\mathcal{M};X),$ and

$\mathrm{H}_{k+1}^{n}(\mathcal{M};X):=\mathrm{I}^{n}(\mathcal{M};\mathrm{H}_{k}^{n}(\mathcal{M};X))$.

    * –

${\mathrm{K}(\mathcal{M};X):=\cup_{n\in\omega}\mathrm{K}^{n}(\mathcal{M};X)}$.

(When $X=\emptyset$, we omit $X$ from the notations.) Clearly,
$\mathrm{I}^{n}(\mathcal{M};X)$ and $\mathrm{H}^{n}(\mathcal{M};X)$ are
initial segments of $\mathcal{M}$. The following properties of these submodels
of $\mathcal{M}$ are well-known (e.g. see [6, Ch. IV, Thm. 1.33]):

######  Theorem 2.1.

Suppose $n>0$, and $\mathcal{M}\models\mathrm{I}\Sigma_{n}$ and $X\subseteq
M$, then the following hold:

    * (1)

$\mathrm{K}^{n}(\mathcal{M};X)\prec_{\Sigma_{n}}\mathcal{M}$, and if
$\mathrm{K}^{n}(\mathcal{M})$ is nonstandard, then
$\mathrm{K}^{n}(\mathcal{M})\models\neg\mathrm{B}\Sigma_{n}$.

    * (2)

$\mathrm{I}^{n}(\mathcal{M};X)\prec_{\Sigma_{n-1}}\mathcal{M}$, and if
$\mathrm{K}^{n}(\mathcal{M};X)$ is nonstandard, then
$\mathrm{I}^{n}(\mathcal{M};X)\models\mathrm{B}\Sigma_{n}$.

    * (3)

$\mathrm{H}^{n}(\mathcal{M};X)\prec_{\Sigma_{n}}\mathcal{M}$ , and if
$\mathrm{K}^{n}(\mathcal{M};X)$ is nonstandard, then
$\mathrm{H}^{n}(\mathcal{M};X)\models\mathrm{B}\Sigma_{n+1}$.

  * •

A given structure $\mathcal{M}$ is called recursively saturated if it realizes
every recursive type with finite parameters in $M$. In [2], Barwise and
Shilipf showed that any countable model $\mathcal{M}$ of $\mathrm{PA}$ is
recursively saturated iff it carries an inductive satisfaction class; here an
inductive satisfaction class $S$ of $\mathcal{M}$ is a subset of $M$ which
contains $\langle\varphi,a\rangle$ such that (1)
$\mathcal{M}\models\mathrm{Form}(\varphi)$, (2)
$(\mathcal{M};S)\models\mathrm{PA}^{*}$, and (3) $(\mathcal{M};S)$ satisfies
Tarski’s inductive conditions for satisfaction (for a more precise definition
see [7]). It is folklore that for every countable recursively saturated model
$\mathcal{M}$ of $\mathrm{PA}$ there exists some inductive satisfaction class
$S$ such that $(\mathcal{M};S)$ is also recursively saturated (e.g. see [10]).

  * •

For every cut $I$ of $\mathcal{M}$ the $I$-Standard System of $\mathcal{M}$,
denoted by $\mathrm{SSy}_{I}(\mathcal{M})$, is the family of subsets of $I$ of
the form $I\cap a_{\mathrm{E}}$ for some $a\in M$. By
$\mathrm{SSy}(\mathcal{M})$ we mean $\mathrm{SSy}_{\mathbb{N}}(\mathcal{M})$.
It is well-known that for every model $\mathcal{M}$ of $\mathrm{I}\Sigma_{n}$
(for $n>0$), $\mathrm{SSy}_{I}(\mathcal{M})$ is equal to the family of subsets
of $I$ which are $\Sigma_{n}$-definable (with parameters) in $\mathcal{M}$
(see [6, Ch. I]). Moreover, it is easy to check that if $\mathcal{N}$ is an
initial segment and a submodel of $\mathcal{M}$ containing $I$, then
$\mathrm{SSy}_{I}(\mathcal{M})=\mathrm{SSy}_{I}(\mathcal{N})$ (see [7]).

  * •

A given model $\mathcal{M}$ of $\mathrm{I}\Delta_{0}$ is called 1-tall if
$\mathrm{K}^{1}(\mathcal{M};a)$ is cofinal in $\mathcal{M}$ for no $a\in M$;
and it is called 1-extendable if it possesses some end extension
$\mathcal{N}\models\mathrm{I}\Delta_{0}$ such that
$\mathrm{Th}_{\Sigma_{1}}(\mathcal{M})=\mathrm{Th}_{\Sigma_{1}}(\mathcal{N})$.
Dimitracopoulos and Paris, in [3] showed that:

######  Theorem 2.2 (Dimitracopoulos-Paris).

    * (1)

For any two countable and nonstandard models $\mathcal{M}$ and $\mathcal{N}$
of $\mathrm{I}\Delta_{0}+\mathrm{Exp}$ such that $\mathcal{M}$ is 1-extendable
and $\mathcal{N}$ is 1-tall, there exists a proper initial embedding from
$\mathcal{M}$ into $\mathcal{N}$ iff
$\mathrm{SSy}(\mathcal{M})=\mathrm{SSy}(\mathcal{N})$ and
$\mathrm{Th}_{\Sigma_{1}}(\mathcal{M})\subseteq\mathrm{Th}_{\Sigma_{1}}(\mathcal{N})$.

    * (2)

Any 1-tall countable model $\mathcal{M}$ of
$\mathrm{B}\Sigma_{1}+\mathrm{Exp}$ in which $\mathbb{N}$ is not
$\Pi_{1}$-definable (without parameters), is 1-extendable.

  * •

A given cut $I$ of a model $\mathcal{M}$ is called strong if for every coded
function $f$ of $\mathcal{M}$ whose domain contains $I$, there exists some
$e>I$ such that $f(i)\in I$ iff $f(i)<e$ for all $i\in I$. Paris and Kirby, in
[9], proved that  $I$ is a strong cut of a model $\mathcal{M}$ of
$\mathrm{I}\Delta_{0}+\mathrm{Exp}$ iff
$(I,\mathrm{SSy}_{I}(\mathcal{M}))\models\mathrm{ACA}_{0}$ (here
$\mathrm{ACA}_{0}$ is the subsystem of second order arithmetic with the
comprehension scheme restricted to formulas with no second order quantifier).

  * •

For given $\mathcal{L}_{A}$-structures $\mathcal{M}$ and $\mathcal{N}$, an (a
proper) initial embedding $j$ is an embedding from $\mathcal{M}$ into
$\mathcal{N}$ whose image is an (a proper) initial segment of $\mathcal{N}$.
To every self-embedding $j$ of $\mathcal{M}$, we associate two subsets of $M$:

$\mathrm{I}_{\mathrm{fix}}(j):=\\{m\in M:\forall x\leq m\ j(x)=x\\},$ and

$\mathrm{Fix}(j):=\\{m\in M:j(m)=m\\}.$

In [1], it is shown that for every model $\mathcal{M}$ of
$\mathrm{I}\Sigma_{1}$, and any self-embedding $j$ of $\mathcal{M}$, it holds
that
$K^{1}(\mathcal{M})\prec_{\Sigma_{1}}\mathrm{Fix}(j)\prec_{\Sigma_{1}}\mathcal{M}$.
Consequently, $\mathrm{Fix}(j)\models\mathrm{I}\Delta_{0}+\mathrm{Exp}.$ The
following results on the set of fixed points of initial self-embeddings were
also proved in [1]:

######  Theorem 2.3 (B-Enayat).

Let $\mathcal{M}$ and $\mathcal{N}$ be countable nonstandard models of
$\mathrm{I}\Sigma_{1}$, $c\in M$ and $d,b\in N$, and $I$ be a proper cut
shared by $\mathcal{M}$ and $\mathcal{N}$ which is closed under
exponentiation. Then the following are equivalent:

    * (1)

There exists some proper initial embedding $j$ from $\mathcal{M}$ into
$\mathcal{N}$ such that $I\subseteq\mathrm{I}_{\mathrm{fix}}(j)$, $j(M)<b$,
and $j(c)=d$.

    * (2)

$\mathrm{SSy}_{I}(\mathcal{M})=\mathrm{SSy}_{I}(\mathcal{N})$, and for every
$\Delta_{0}$-formula $\delta(z,x,y)$ and every $i\in I$ it holds that:

$\mathcal{M}\models\exists z\ \delta(z,c,i)\ \Rightarrow\
\mathcal{N}\models\exists z<b\ \delta(z,d,i).$

######  Remark 1.

With the above assumptions, suppose $a\in M\cap N$ such that for all
$\Delta_{0}$-formula $\delta$ and for every $i\in I$ it holds that:

$\mathcal{M}\models\exists z\ \delta(z,c,(a)_{i})\ \Rightarrow\
\mathcal{N}\models\exists z<b\ \delta(z,d,(a)_{i})$.

Then, by an appropriate modification in the proof of Theorem 2.3, we can
manage to construct the above proper initial embedding $j$ with the additinal
feature that ${j((a)_{i})=(a)_{i}}$ for every $i\in I$.

######  Theorem 2.4 (B-Enayat).

Suppose $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ is countable and nonstandard
and $I$ is a cut of $\mathcal{M}$. Then the following hold:

    * (1)

$I$ is closed under exponentiation iff there exists some proper initial self-
embedding $j$ of $\mathcal{M}$ such that $\mathrm{I}_{\mathrm{fix}}(j)=I$.

    * (2)

$I$ is strong in $\mathcal{M}$ and $I\prec_{\Sigma_{1}}\mathcal{M}$, iff there
exists some proper initial self-embedding $j$ of $\mathcal{M}$ such that
$\mathrm{Fix}(j)=I$.

    * (3)

$\mathbb{N}$ is strong in $\mathcal{M}$ iff there exists some proper initial
self-embedding $j$ of $\mathcal{M}$ such that
$\mathrm{Fix}(j)=\mathrm{K}^{1}(\mathcal{M})$.

  * •

The following lemma from [1] will be useful in section 4 of this paper:

######  Lemma 2.5.

Suppose $\mathcal{M}\models\mathrm{I}\Delta_{0}+\mathrm{Exp}$ in which
$\mathbb{N}$ is not a strong cut, then for any self-embedding $j$ of
$\mathcal{M}$, the following hold:

    * (1)

The nonstandard fixed points of $j$ are downward cofinal in the nonstandard
part of $\mathcal{M}$.

    * (2)

For every element $a\in M$, and $m\in\mathrm{Fix}(j)$ there exists an element
$b\in\mathrm{Fix}(j)$ such that:

$\mathrm{Th}_{\Sigma_{1}}(\mathcal{M};a,m)\subseteq\mathrm{Th}_{\Sigma_{1}}(\mathcal{M};b,m).$

  * •

Convention. Suppose $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ and
$\langle\delta_{r}:\ r\in M\rangle$ is a canonical enumeration of
$\Delta_{0}$-formulas in $\mathcal{M}$. For every $r\in M$:

    * –

$f_{r}(\diamondsuit)=\blacklozenge$ denotes the following partial
$\Sigma_{1}$-function in $\mathcal{M}$:

$\exists z((z)_{0}=\blacklozenge\ \wedge\
z=\mu_{y}\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(\diamondsuit,(y)_{0},(y)_{1})).$

    * –

The notation $[f_{r}(\bar{x})\downarrow]$ denotes the $\Sigma_{1}$-formula
$\exists z,y\ \mathrm{Sat}_{\Delta_{0}}(\delta_{r}(\bar{x},y,z))$, and
${[f_{r}(\bar{x})\downarrow]^{<w}}$ stands for the formula $\exists z,y<w\
\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(\bar{x},y,z))$.

Finally, we put $\mathcal{F}(\mathcal{M})$ to be the collection of all
$\emptyset$-definable partial $\Sigma_{1}$-functions in $\mathcal{M}$. As
noted in [1], if $\mathcal{M}$ and $\mathcal{N}$ are two models of
$\mathrm{I}\Delta_{0}$ such that
$\mathrm{Th}_{\Sigma_{1}}(\mathcal{M})=\mathrm{Th}_{\Sigma_{1}}(\mathcal{N})$,
then
$\mathcal{F}(\mathcal{M})=\mathcal{F}(\mathcal{N})=\mathcal{F}:=\\{f_{n}:n\in\mathbb{N}\\}$.
Moreover, in [1] it is shown that:

$\mathrm{K}^{1}(\mathcal{M};a)=\\{f(a):\ f\in\mathcal{F}\text{ and
}\mathcal{M}\models[f(a)\downarrow]\\}.$

##  3 $I$-small $\Sigma_{1}$-elementary submodels

In [15], Lascar introduced a class of submodels of models of arithmetic,
namely small submodels, which resemble those submodels of a model of set
theory whose cardinality is less than the cardinality of the ground model.
Then, Enayat inspired by a result of Schmerl (stated without proof as Theorem
5.7 in [8]), generalized this notion in [4]. In this section we will prove
some results about these submodels.

######  Definition 1.

For a given proper cut $I$ of a model $\mathcal{M}$ of
$\mathrm{I}\Delta_{0}+\mathrm{Exp}$, subset $X$ of $M$ is called $I$-small in
$\mathcal{M}$ if there exists some $a\in M$ such that $X=\\{(a)_{i}:\ i\in
I\\}$, and $(a)_{i}\neq(a)_{j}$ for all distinct $i,j\in I$. When
$I=\mathbb{N}$, we simply use small for $\mathbb{N}$-small.

It is easy to see that for every model $\mathcal{M}$ of
$\mathrm{I}\Sigma_{1}$, each proper cut $I$ of $\mathcal{M}$ is $I$-small.
Moreover, for every $a\in M$, $\mathrm{K}^{1}(\mathcal{M};a)$ is small in
$\mathcal{M}$. In [13], it is shown that every recursively saturated model
$\mathcal{M}$ of $\mathrm{PA}$ possesses some small submodel which is not
finitely generated. This result can be generalized for $I$-small submodels,
when $I$ is a strong cut of $\mathcal{M}$ (see Theorem 3.2 below).
Furthermore, By using compactness arguments, for every model $\mathcal{M}$ of
$\mathrm{I}\Sigma_{1}$, we can find some elementary extension of $\mathcal{M}$
in which it is small. And finally, in [12] it is shown that every nonstandard
small submodel is a mixed submodel (i.e. neither cofinal, nor initial
segment). In a similar manner, for every cut $I$ of a model $\mathcal{M}$ of
$\mathrm{I}\Sigma_{1}$, and each $I$-small submodel $\mathcal{M}_{0}$ of
$\mathcal{M}$, if $I\subsetneq M_{0}$ then $M_{0}$ is mixed in $\mathcal{M}$
(since if $M_{0}:=\\{(a)_{i}:\ i\in I\\}$, and $A:=\\{i\in I:\
\mathcal{M}\models\neg i\mathrm{E}(a)_{i}\\}$, then
$A\in\mathrm{SSy}_{I}(\mathcal{M})\setminus\mathrm{SSy}_{I}(\mathcal{M}_{0})$.
So $\mathcal{M}_{0}$ cannot be an initial segment of $\mathcal{M}$).

In the following lemma we will show that in the definition of $I$-small, if
$I$ is a strong cut or it is equal to $\mathbb{N}$, then the condition
$(a)_{i}\neq(a)_{j}$ for all distinct $i,j\in I$ , can be eliminated:

######  Lemma 3.1.

Suppose $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ is nonstandard,
$I\subsetneq_{e}\mathcal{M}$, $\mathcal{M}_{0}$ is a submodel of $\mathcal{M}$
such that $M_{0}=\\{(a)_{i}:\ i\in I\\}$ for some $a\in M$. Then the following
hold:

  * (1)

If $I=\mathbb{N}$, then $\mathcal{M}_{0}$ is small.

  * (2)

If $I$ is strong in $\mathcal{M}$, then $\mathcal{M}_{0}$ is $I$-small.

###### Proof.

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

$g(0):=(a)_{0}$,

and

$g(x+1):=y$ 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)$.

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\\{(d)_{i}:\ i\in I\\}}$. Now, in each case of the statement
of theorem we will prove that $\\{(d)_{i}:\ i\in I\\}\subseteq M_{0}$:

  * (1)

Suppose $I=\mathbb{N}$. If $\\{(d)_{n}:\ n\in\mathbb{N}\\}\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}=\\{(a)_{0},...,(a)_{m}\\}$, which is a contradiction.

  * (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}$:

$h(x):=\mu_{r}((d)_{x}=(a)_{r})$.

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:

$\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}))$.

Therefore, $M_{0}=\\{x\in M:\ \mathcal{M}\models\exists i\leq h(i_{0}-1)\
x=(a)_{i}\\}$. So $M_{0}$ is $\Delta_{0}$-definable in $\mathcal{M}$, which is
a contradiction.

∎

In the following theorem, we will show that when $I$ is strong, the basic
properties which hold for small submodels, also hold for $I$-small ones.

######  Theorem 3.2.

Let $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ be nonstandard, and $I$ be a
strong cut of $\mathcal{M}$. Then:

  * (1)

For every $a\in M$, $\mathrm{K}^{1}(\mathcal{M};I\cup\\{a\\})$ is $I$-small.

  * (2)

If $\mathcal{M}_{0}$ is an $I$-small submodel of $\mathcal{M}$, then
$I\subseteq M_{0}$.

  * (3)

If $\mathcal{M}\models\mathrm{PA}$ is countable and recursively saturated,
then there exists some $I$-small elementary submodel of $\mathcal{M}$ which is
not of the form of $\mathrm{K}(\mathcal{M};I\cup\\{a\\})$ for any $a\in M$.

###### Proof.

  * (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:

$\mathcal{M}\models\forall\langle r,i\rangle<s\
([f_{r}(i,a)\downarrow]\rightarrow[f_{r}(i,a)\downarrow]^{<b})$.

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:

$\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)$.

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:

$\mathrm{K}^{1}(\mathcal{M};I\cup\\{a\\})=\\{(d)_{i}:\ i\in I\\}.$

So by Lemma 3.1, $\mathrm{K}^{1}(\mathcal{M};I\cup\\{a\\})$ is $I$-small in
$\mathcal{M}$.

  * (2)

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

${Z:=\\{\langle y,z\rangle\in M:\ \mathcal{M}\models(a)_{y}=z\\}}.$

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)

We will generalize the method used in [13, Pro. 2.10]: let $S$ be a
nonstandard 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$.

∎

The following lemma will be useful in the proof of the main theorem of this
section:

######  Lemma 3.3.

Suppose $\mathcal{M}\models\mathrm{I}\Sigma_{1}$, $I$ is a strong cut of
$\mathcal{M}$, and $a\in M\setminus I$ such that $(a)_{i}\neq(a)_{j}$ for all
distinct $i,j\in I$. Moreover, let ${M_{0}=\\{(a)_{i}:\ i\in I\\}}$ be a
$\Sigma_{1}$-elementary submodel of $\mathcal{M}$, $X\subseteq M_{0}$ be coded
in $\mathcal{M}$, and $i_{0}\in I$ such that $i<i_{0}$ for all $(a)_{i}\in X$.
Then $X$ is coded in $\mathcal{M}_{0}$.

###### 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:

$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}$

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:

$\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})$.

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 x is in
$M_{0}$. Therefore, $\textbf{x}=(a)_{i}$ for some $i\in
I<\min\\{e,\mathrm{Len}(a)\\}$. ∎

Now we are ready to prove the main theorem and corollary of this section. The
method we use for proving Theorem 3.4 is a a combination of the back-and-forth
method used in [1, Thm. 6.1] and [8, Thm. 5.6].

######  Theorem 3.4.

Assume $\mathcal{N}\models\mathrm{I}\Sigma_{1}$ is countable and nonstandard,
$I$ is a strong cut of $\mathcal{N}$, and $\mathcal{N}_{0}$ is an $I$-small
$\Sigma_{1}$-elementary submodel of $\mathcal{N}$ such that $I\neq N_{0}$.
Then there exists some proper initial self-embedding $j$ of
$\mathrm{H}^{1}(\mathcal{N};N_{0})$ such that ${N_{0}=\mathrm{Fix}(j)}$.

###### Proof.

Put $\mathcal{M}:=\mathrm{H}^{1}(\mathcal{N};N_{0})$. So 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}$, and 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 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$. In order to construct $j$, first by using strong $\Sigma_{1}$-Collection
in $\mathcal{M}$, we will find some $b\in M$ such that:

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

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}))$, in which:

$\mathrm{P}(\bar{u},\bar{v})\equiv[f(\bar{u},(a)_{i})\downarrow]\rightarrow[f(\bar{v},(a)_{i})\downarrow]^{<b}$,
for all $f\in\mathcal{F}$ and $i\in I$;

and

$\mathrm{Q}(\bar{u},\bar{v})\equiv\left(\begin{array}[]{c}[f(\bar{u},(a)_{i})\downarrow]\wedge[f(\bar{v},(a)_{i})\downarrow]^{<b}\wedge\\\
f(\bar{u},(a)_{i})\notin
N_{0}\end{array}\right)\Rightarrow{f(\bar{u},(a)_{i})\neq
f(\bar{v},(a)_{i})}$, for all $f\in\mathcal{F}$ and all $i\in I$.

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}\\}$. By the definition of
$\mathcal{M}$, without loss of generality, we can assume that $m\leq
t(\bar{u},\mathrm{(a)_{\textbf{i}}})$ for some $t\in\mathcal{F}$ and
$\textbf{i}\in I$. In order to find some image for $m$, first note that since
$\mathrm{P}(\bar{u},\bar{v})$ holds in $\mathcal{M}$, Theorem 2.3 and Remark 1
imply that:

$(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})$.

Then, we define:

$C:=\left\\{\langle r,i\rangle\in I:\
\mathcal{M}\models[f_{r}(\bar{u},m,(a)_{i})\downarrow]\ \text{and}\
f_{r}(\bar{u},m,(a)_{i})\notin\mathrm{K}^{1}(\mathcal{M};N_{0}\cup\\{\bar{u}\\})\right\\}$.

We claim that $C\in\mathrm{SSy}_{I}(\mathcal{M})$; so there exists some
$\alpha\in M$ such that $C=I\cap\alpha_{\mathrm{E}}$. To prove this claim,
let:

$R:=\left\\{\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\\}$.

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:

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

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})$.

Now, for every $s\in M$, we define:

$p_{s}(y):=\\{y\leq t(\bar{v},\mathrm{(a)_{\textbf{i}}})\\}\cup p_{s1}(y)\cup
p_{s2}(y)$; where:

${p_{s1}(y):=\\{\forall
i<s([f(\bar{u},m,(a)_{i})\downarrow]\rightarrow[f(\bar{v},y,(a)_{i})\downarrow]^{<b}):f\in\mathcal{F}\\};}$

and

$p_{s2}(y):=\left\\{\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\\}$.

We shall show that there is some $s>I$ such that $p_{s}$ is finitely
satisfiable; then since $p_{s}$ is $\Pi_{1}$, bounded and recursive, there
exists some $m^{\prime}$ which realises $p_{s}$ in $\mathcal{M}$. Therefore,
$m^{\prime}$ serves as the image of $m$, and this finishes the ‘forth’ stage.

In order to find such $s$, we claim that for every $k\in\mathbb{N}$ it holds
that:

$(\ast_{k}):\\\ \ \left(\begin{array}[]{c}\text{For every
}f\in\mathcal{F},\text{ every }z\in N_{0},\\\ \text{ and any nonempty finite
set }\\{f_{n_{0}},...,f_{n_{k}}\\}\text{ of elements of }\mathcal{F},\\\
\text{ there exists some }s>I\text{ such that
}\mathcal{M}\models\Psi(f,f_{n_{0}},...,f_{n_{k}},\bar{u},m,\bar{v},b,a,s,\alpha,z,\mathrm{(a)_{\textbf{i}}}),\\\
\text{ where
}\Psi(f,f_{n_{0}},...,f_{n_{k}},\bar{u},m,\bar{v},b,a,s,\alpha,z,\mathrm{(a)_{\textbf{i}}})\text{
is the following }\Pi_{1}\text{-formula: }\\\ {\exists y\leq
t(\bar{v},\mathrm{(a)_{\textbf{i}}})\left(\begin{array}[]{c}\forall
i<s([f(\bar{u},m,(a)_{i},z)\downarrow]\rightarrow[f(\bar{v},y,(a)_{i},z)\downarrow]^{<b})\
\wedge\\\ \forall i<s\bigwedge_{t\leq
k}\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})\par\end{array}\right)\end{array}\right)}\end{array}\right)$.

This claim completes the proof in the following way:

Let $d>I$ be an arbitrary and fixed element of $M$. Suppose $i,s\in M$, and
$\Theta(s,i,\bar{u},m,\bar{v},b,a,\alpha,\beta,\mathrm{(a)_{\textbf{i}}})$ is
the following $\Delta_{0}$-formula:

${\forall r<i\ \exists y\leq
t(\bar{v},\mathrm{(a)_{\textbf{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^{\prime}<i\left(\begin{array}[]{c}([f_{r^{\prime}}(\bar{v},y,(a)_{w})\downarrow]^{<b}\wedge\langle
r^{\prime},w\rangle\mathrm{E}\alpha)\rightarrow\\\
f_{r^{\prime}}(\bar{u},m,(a)_{w})\neq
f_{r^{\prime}}(\bar{v},y,(a)_{w})\end{array}\right)\end{array}\right)}$;

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

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

Now, for every $i\in M$, we define:

$g(i):=\mathrm{max}\\{x<d:\
\mathcal{M}\models\Theta(x,i,\bar{u},m,\bar{v},b,a,\alpha,\beta,\mathrm{(a)_{\textbf{i}}})\\}$.

Clearly $g$ is $\Delta_{0}$-definable function in $\mathcal{M}$, and
$I\subseteq\mathrm{Dom}(g)$ (we assume $\mathrm{max}(\emptyset)=0$).
Therefore, since $I$ is strong, there exists some $e>I$ such that for all
$i\in I$, $g(i)>I$ iff $g(i)>e$. We will show that $p_{e}(y)$ is a finitely
satisfiable type. First, note that by statement $(1)$, $p_{e1}(y)$ is closed
under conjunctions. So let $f_{n},f_{n_{0}},...,f_{n_{k}}$ be some finite
number of elements of $\mathcal{F}$, and let
$n^{*}=\mathrm{max}\\{n,n_{0},...,n_{k}\\}$. Then, use $(\ast_{n^{*}})$,
$(n^{*}+2)$-many times; i.e for every $t=0,...,n^{*}+1$ consider $f_{t}$
instead of $f$ in the assertion of $(\ast_{n^{*}})$, $0\in M_{0}$ instead of
$z$, and $f_{1},...,f_{n^{*}}$. So by statement $(\ast_{n^{*}})$, for every
$t=0,...,n^{*}+1$ there exists some $s_{t}>I$ such that
$\mathcal{M}\models\Psi(f_{t},f_{0},...,f_{n^{*}+1},\bar{u},m,\bar{v},b,a,s_{t},\alpha,0,\mathrm{(a)_{\textbf{i}}})$.
Then, let $s^{*}:=\mathrm{min}\\{s_{t}:\ t<n^{*}+1\\}$. Therefore,
${\mathcal{M}\models\Theta(s^{*},n^{*},\bar{u},m,\bar{v},b,a,\alpha,\beta,\mathrm{(a)_{\textbf{i}}})}$.
It is easy to see that if $d\leq s^{*}$ then $g(n^{*})=d-1$, and if $s^{*}<d$
then $s^{*}\leq g(n^{*})$; so in both cases $g(n^{*})>I$ and consequently
$g(n^{*})>e$. So
$\mathcal{M}\models\Theta(e,n^{*},\bar{u},m,\bar{v},b,a,\alpha,\beta,\mathrm{(a)_{\textbf{i}}})$;
this proves that $p_{e}$ is finitely satisfiable.

Proof of the claim $(\ast_{k})$ for every $k\in\mathbb{N}$: Suppose the claim
is not true; i.e there is some $k\in\mathbb{N}$ for which there exists some
nonempty finite set $\\{f,f_{n_{0}},...,f_{n_{k}}\\}$ of elements of
$\mathcal{F}$, and some $\textbf{z}\in N_{0}$ such that for all $s>I$ it holds
that:

$\mathcal{M}\models\neg\Psi(f,f_{n_{0}},...,f_{n_{k}},\bar{u},m,\bar{v},b,a,s,\alpha,\textbf{z},\mathrm{(a)_{\textbf{i}}}).$

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

$\mathcal{M}\models\neg\Psi(f,f_{n_{0}},...,f_{n_{k}},\bar{u},m,\bar{v},b,a,s,\alpha,\textbf{z},\mathrm{(a)_{\textbf{i}}}).$

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

${\mathcal{M}\models\neg\Psi(f,f_{n_{0}},...,f_{n_{k_{0}}},\bar{u},m,\bar{v},b,a,s_{0},\alpha,\textbf{z}_{0},\mathrm{(a)_{\textbf{i}}})}.$

Put:

$X:=\\{x\in M:\ \mathcal{M}\models\exists
i<s_{0}(x=(a)_{i}\wedge[f(\bar{u},m,(a)_{i},\textbf{z}_{0})\downarrow])\\}$;

and

$X^{\prime}:=\\{\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)\\}.$

By Lemma 3.3, there exist $(a)_{\xi}\in N_{0}$ and $(a)_{\zeta}\in N_{0}$
which code $X$ and $X^{\prime}$ respectively. So we can restate statement (2)
in the following form:

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

$\mathcal{M}\models\forall y\leq
t(\bar{v},\mathrm{(a)_{\textbf{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=0}^{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)\par\par\end{array}\right)\end{array}\right)$.

Now, by considering the sequence number of ${\langle
f_{n_{t}}(\bar{u},m,\varepsilon):\ \langle
n_{t},\varepsilon\rangle\mathrm{E}(a)_{\zeta}\rangle}$ in $\mathcal{M}$, we
may quntify out $f_{n_{t}}(\bar{u},m,\varepsilon)$s from the formula in
statement $(3)$, and deduce that:

$(4):\ \ $ $\mathcal{M}\models\exists x\forall y\leq
t(\bar{v},\mathrm{(a)_{\textbf{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:

$\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).$

Then, we will define $\Sigma_{1}$-definable partial functions
$b(\diamondsuit,y,(a)_{\xi},(a)_{\zeta},\textbf{z}_{0})$ and
$s(\diamondsuit,(a)_{\xi},(a)_{\zeta},\textbf{z}_{0},\mathrm{(a)_{\textbf{i}}})$,
as follows (we omit the parameters $(a)_{\xi}$, $(a)_{\zeta}$,
$\mathrm{(a)_{\textbf{i}}}$, and $\textbf{z}_{0}$ in the presentations of
these functions for the sake of simplicity):

  * •

$b(\diamondsuit,y):=\min\left\\{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})\par\end{array}\right)\right\\}.$

  * •

$s(\diamondsuit):=x$ iff $\exists z\left(\begin{array}[]{c}(z)_{0}=x\
\wedge\\\ z=\mu_{w}\ \forall y\leq t(\diamondsuit,\mathrm{(a)_{\textbf{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 $s_{t}(\diamondsuit,\varepsilon):=(s(\diamondsuit))_{\langle
n_{t},\varepsilon\rangle}$, for every $\langle
n_{t},\varepsilon\rangle\mathrm{E}(a)_{\zeta}$.

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

$(5):\ \ $ $\mathcal{M}\models\forall y\leq
t(\bar{v},\mathrm{(a)_{\textbf{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[s_{t}(\bar{v},\varepsilon)\downarrow]^{<b(\bar{v},y)}\
\wedge\\\
s_{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):\ \ $$\mathcal{M}\models\forall y\leq
t(\bar{u},\mathrm{(a)_{\textbf{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\par[s_{t}(\bar{u},\varepsilon)\downarrow]^{<b(\bar{u},y)})\
\wedge\\\
s_{t}(\bar{u},\varepsilon)=f_{n_{t}}(\bar{u},y,\varepsilon)\end{array}\right)\end{array}\right)$.

Now, we will simultaneously define two more $\Sigma_{1}$-definable functions
in $\mathcal{M}$:

$\langle o(\diamondsuit,y),h(\diamondsuit,y)\rangle:=\min\left\\{\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\par[s_{t}(\diamondsuit,\varepsilon)\downarrow]^{<b(\diamondsuit,y)}\wedge\\\
s_{t}(\diamondsuit,\varepsilon)=f_{n_{t}}(\diamondsuit,y,\varepsilon)\end{array}\right)\right\\}$.

(Note that, similar to the way we defined function $s$, we can express the
above definition by a $\Sigma_{1}$-formula.) Then, by statement (5) it holds
that:

$(7):\ \ $ $\mathcal{M}\models\forall y\leq
t(\bar{v},\mathrm{(a)_{\textbf{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):\ \ $ $\mathcal{M}\models\forall y\leq
t(\bar{u},\mathrm{(a)_{\textbf{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)$.

Finally, we obtain a contradiction by dividing $k_{0}$ into two cases in the
following way:

  * •

If $k_{0}=1$, we inductively define the following $\Sigma_{1}$-function in
$\mathcal{M}$:

$w(\diamondsuit,0):=\min\left\\{y\leq
t(\diamondsuit,\mathrm{(a)_{\textbf{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\\}$,
and

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

$\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_{0}}(\diamondsuit,y,h(\diamondsuit,w(\diamondsuit,x)))\downarrow]^{<b(\diamondsuit,y)}\wedge\\\
[f_{n_{0}}(\diamondsuit,w(\diamondsuit,x),h(\diamondsuit,w(\diamondsuit,x)))\downarrow]^{<b(\diamondsuit,w(\diamondsuit,x))}\end{array}\right)\rightarrow\\\
f_{n_{0}}(\diamondsuit,y,h(\diamondsuit,w(\diamondsuit,x)))\neq
f_{n_{0}}(\diamondsuit,w(\diamondsuit,x),h(\diamondsuit,w(\diamondsuit,x)))\end{array}\right)\end{array}\right).$

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:

$(9):\ \ $$\mathcal{M}\models\forall y\leq
t(\bar{u},\mathrm{(a)_{\textbf{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:

$(10):\ \ $ $\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), (9) and (10), there exists some $i_{1}<i_{0}$ such that:

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

Clearly,
$f_{n_{0}}(\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 (11),
$f_{n_{0}}(\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_{0},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$.

As a result, by the definition of $w(\bar{u},i)$ 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:

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

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

$(13):\ \ $
$\mathcal{M}\models\left(\begin{array}[]{c}[s_{0}(\bar{u},h(\bar{u},w(\bar{u},i_{0})))\downarrow]\wedge[s_{0}(\bar{u},h(\bar{u},w(\bar{u},i_{1})))\downarrow]\wedge\\\
s_{0}(\bar{u},h(\bar{u},w(\bar{u},i_{0})))=s_{0}(\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:

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

So statements (12), (13) and (14) imply that:

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

But statement (15) is in contradiction with the definition of
$w(\bar{u},i_{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}$:

$A:=\left\\{\langle o(\bar{v},y),h(\bar{v},y)\rangle:\
\mathcal{M}\models\left(\begin{array}[]{c}y\leq
t(\bar{v},\mathrm{(a)_{\textbf{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_{0},\varepsilon\rangle\mathrm{E}(a)_{\zeta}\wedge[f_{n_{0}}(\bar{v},y,\varepsilon)\downarrow]^{<b}\wedge\\\
f_{n_{0}}(\bar{v},y,\varepsilon)=f_{n_{0}}(\bar{u},m,\varepsilon)\end{array}\right)\end{array}\right)\right\\}$.

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

$(16):\ \ $$\mathcal{M}\models\forall y\leq
t(\bar{v},\mathrm{(a)_{\textbf{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=1}^{k_{0}}\par\left(\begin{array}[]{c}\langle
n_{t},\varepsilon\rangle\mathrm{E}(a)_{\zeta}\wedge\par[f_{n_{t}}(\bar{v},y,\varepsilon)\downarrow]^{<b}\wedge\\\
f_{n_{t}}(\bar{u},m,\varepsilon)=f_{n_{t}}(\bar{v},y,\varepsilon)\par\par\end{array}\right)\end{array}\right)$.

Let $f^{\prime}\in\mathcal{F}$ such that:

$f^{\prime}(\diamondsuit,y,\epsilon,\langle\textbf{z}_{0},(a)_{\rho},(a)_{\zeta},(a)_{\xi}\rangle)=x$

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}$.

So by considering $f^{\prime}$ instead of $f$ in statement (3), statement (16)
leads to contradiction with the minimality of $k_{0}$.

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

  * •

Let $\alpha^{\prime}$ be the code of the following set in $\mathcal{M}$:

${C^{\prime}:=\\{\langle r,i\rangle\in I:\
\mathcal{M}\models[f_{r}(\bar{v},m^{\prime},(a)_{i})\downarrow]^{<b}\
\text{and}\
f_{r}(\bar{v},m^{\prime},(a)_{i})\notin\mathrm{K}^{1}(\mathcal{M};N_{0}\cup\\{\bar{v}\\})\\}}$.

  * •

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

$q_{s}(x):=\\{x<u_{0}\\}\cup q_{s1}(x)\cup q_{s2}(x)$; where:

${q_{s1}(x):=\\{\forall
i<s(\neg[f(\bar{v},m^{\prime},(a)_{i})\downarrow]^{<b}\rightarrow\neg[f(\bar{u},x,(a)_{i})\downarrow]):f\in\mathcal{F}\\};}$
and

${q_{s2}(x):=\left\\{\begin{array}[]{c}\forall
i<s\left(\begin{array}[]{c}\left(\begin{array}[]{c}\langle
n,i\rangle\mathrm{E}\alpha^{\prime}\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^{\prime},(a)_{i})\end{array}\right):\
n\in\mathbb{N}\end{array}\right\\}}$.

  * •

Let:
$(\ast^{\prime}_{k}):\ \ \left(\begin{array}[]{c}\text{For every
}f\in\mathcal{F},\text{ every }z\in N_{0},\\\ \text{ and any nonempty finite
set }\\{f_{n_{0}},...,f_{n_{k}}\\}\text{ of elements of }\mathcal{F},\\\
\text{ there exists some }s>I\text{ such that:}\\\
\vspace{.3cm}{\mathcal{M}\models\exists x<u_{0}\left(\begin{array}[]{c}\forall
i<s(\neg[f(\bar{v},m^{\prime},(a)_{i},z)\downarrow]^{<b}\rightarrow\neg[f(\bar{u},x,(a)_{i},z)\downarrow])\
\wedge\\\ \forall i<s\bigwedge_{t\leq k}\left(\begin{array}[]{c}(\langle
n_{t},i\rangle\mathrm{E}\alpha^{\prime}\wedge[f_{n_{t}}(\bar{u},x,(a)_{i})\downarrow])\rightarrow\\\
f_{n_{t}}(\bar{u},x,(a)_{i})\neq
f_{n_{t}}(\bar{v},m^{\prime},(a)_{i})\end{array}\right)\end{array}\right)}\end{array}\right)$.

  * •

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

$\forall r<i\ \exists x<u_{0}\left(\begin{array}[]{c}\forall w<s(\langle
x,r,w\rangle\mathrm{E}\beta^{\prime}\rightarrow[f_{r}(\bar{v},m^{\prime},(a)_{w})\downarrow]^{<b})\wedge\\\
\forall w<s\forall r^{\prime}<i\left(\begin{array}[]{c}(\langle
r^{\prime},w\rangle\mathrm{E}\alpha^{\prime}\wedge\langle
x,r^{\prime},w\rangle\mathrm{E}\beta^{\prime})\rightarrow\\\
f_{r^{\prime}}(\bar{u},m,(a)_{w})\neq
f_{r^{\prime}}(\bar{v},y,(a)_{w}))\end{array}\right)\end{array}\right)$;

where $\beta^{\prime}$ is the code of the following $\Sigma_{1}$-definable set
in $\mathcal{M}$:

$L^{\prime}:=\\{\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])\\}$.

  * •

Between statements (3) and (4) we need to use $\Sigma_{1}$-Collection to
deduce:

$(3^{\prime}):\ \ $ $\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^{\prime},\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^{\prime}$ respectively:

${Y:=\\{x\in M:\ \mathcal{M}\models\exists
i<s_{0}(x=(a)_{i}\wedge[f(\bar{v},m^{\prime},(a)_{i},\textbf{z}_{0})\downarrow]^{<b})\\}}$,
and
${Y^{\prime}:=\\{\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^{\prime})\\}}$.

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

######  Corollary 3.5.

Assume $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ is countable and nonstandard,
$I$ is a proper cut of $\mathcal{M}$, and $\mathcal{M}_{0}$ is an $I$-small
$\Sigma_{1}$-elementary submodel of $\mathcal{M}$. Then the following are
equivalent:

  * 1)

$I$ is strong in $\mathcal{M}$.

  * 2)

There exists some proper initial self-embedding $j$ of $\mathcal{M}$ such that
${M_{0}=\mathrm{Fix}(j)}$.

###### Proof.

Suppose ${M_{0}=\\{(a)_{i}:\ i\in I\\}}$, 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:

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

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 proof of Theorem 5.1
and 6.1 of [1]. 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:=\\{f(i):\ i\in I\wedge I<f(i)\\}}$ 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:

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

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:

$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))))$.

So note that:

  * (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})$.

  * (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:

$B_{i}:=\\{\langle r,\epsilon\rangle:\ \mathcal{M}\models\exists
y<i((a)_{y}=\epsilon\wedge\langle r,y\rangle\mathrm{E}s_{i})\\}$.

Then, by Lemma 3.3, $B_{i}$ is coded by some $\alpha_{i}\in
M_{0}=\mathrm{Fix}(j)$. So it holds that:

$\mathcal{M}\models h(i)=\mu_{x}(\forall\langle
r,\epsilon\rangle\mathrm{E}\alpha_{i}\
(\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(\epsilon,x)))$.

As a result, since $\mathcal{M}_{0}\prec_{\Sigma_{1}}\mathcal{M}$, statement
(II) holds.

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

$h^{\prime}(g(u))=j(h)(j(f)(u))=j(h)(j(f)(j(u)))=j(h(f(u)))=h(f(u)).$

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

$\forall u<i\ (f(u)<i\rightarrow h(f(u))=h^{\prime}(g(u)))$.

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

$(\spadesuit):\ \ $ $\forall u<s\ (f(u)<s\rightarrow
h(f(u))=h^{\prime}(g(u)))$.

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:

$j(c)=j(h(f(i_{0})))=j(h)(j(f)((j(i_{0})))=h^{\prime}(g(i_{0}))=h(f(i_{0}))=c$.

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

∎

##  4 Strongness of the standard cut and fixed points

In this section, we will show some properties of $\mathrm{Fix}(j)$, when
$\mathbb{N}$ is not strong in $\mathcal{M}$. Then we will conclude some
criteria for stongness of $\mathbb{N}$ in a countable nonstandard model of
$\mathrm{I}\Sigma_{1}$ through the set of fixed points of its initial self-
embeddings.

######  Lemma 4.1.

Suppose $\mathcal{M}$ is a nonstandard model of $\mathrm{I}\Sigma_{1}$ in
which $\mathbb{N}$ is not strong. Then for any self-embedding $j$ of
$\mathcal{M}$ the following hold:

  * (1)

$\mathrm{Fix}(j)$ is 1-tall.

  * (2)

If $\mathrm{Fix}(j)$ is a countable model of $\mathrm{B}\Sigma_{1}$, then it
is 1-extendable.

###### Proof.

  * (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)

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.

∎

The following corollary generalizes Theorem 1.2:

######  Corollary 4.2.

Let $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ be countable and nonstandard in
which $\mathbb{N}$ is not strong, and $j$ is an initial self-embedding of
$\mathcal{M}$ such that $\mathrm{Fix}(j)\models\mathrm{B}\Sigma_{1}$. Then
$\mathrm{Fix}(j)$ is isomorphic to a proper cut of $\mathcal{M}$.

###### 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. ∎

We conclude this section with a generalization of a similar result about
automorphisms of countable recursively saturated models of $\mathrm{PA}$ in
[13]. Moreover, the following corollary refines Theorem 2.4(3).

######  Corollary 4.3.

Let $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ be countable and nonstandard.
Then the following are equivalent:

  * 1)

$\mathbb{N}$ is strong in $\mathcal{M}$.

  * 2)

There exists some proper initial self-embedding $j$ of $\mathcal{M}$ such that
$\mathrm{Fix}(j)=\mathrm{K}^{1}(\mathcal{M}).$

  * 3)

There exists some proper initial self-embedding $j$ of $\mathcal{M}$, and some
small $\mathcal{M}_{0}\prec_{\Sigma_{1}}\mathcal{M}$, such that
$\mathrm{Fix}(j)=M_{0}.$

  * 4)

For every small $\mathcal{M}_{0}\prec_{\Sigma_{1}}\mathcal{M}$ there exists
some proper initial self-embedding $j$ of $\mathcal{M}$ such that
$\mathrm{Fix}(j)=M_{0}.$

  * 5)

There exists some proper initial self-embedding $j$ of $\mathcal{M}$ such that
$\mathrm{Fix}(j)\subseteq\mathrm{I}^{1}(\mathcal{M})$.

If $\mathcal{M}\models\mathrm{PA}$ and it is recursively saturated, then the
above statements are equivalent to the following:

  * 6)

There exists some proper initial self-embedding $j$ of $\mathcal{M}$ such that
$\mathrm{Fix}(j)\models\mathrm{B}\Sigma_{1}$ and it is isomorphic to no proper
initial segments of $\mathcal{M}$.

###### Proof.

The equivalences of statements (1) to (5) is a straightforward implication of
Corollary 3.5 and Theorem 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}$.
∎

##  5 Extendability

In this section, we will study the extendability of initial embeddings. Most
of the theorems of this section are generalizations of results about
automorphisms of countable recursively saturated models of $\mathrm{PA}$
obtained in [11] and [12].

######  Definition 2.

Suppose $\mathcal{M}$ and $\mathcal{N}$ are models of $\mathrm{I}\Sigma_{1}$,
$\mathcal{M}_{0}$ and $\mathcal{N}_{0}$ are bounded submodels (or proper cuts)
of $\mathcal{M}$ and $\mathcal{N}$ respectively. We call an initial embedding
$j:\mathcal{M}_{0}\hookrightarrow\mathcal{N}_{0}$ an initial
$(\mathcal{M},\mathcal{N})$-embedding if for every $A\subseteq M_{0}$ it holds
that:

$A\in\mathrm{SSy}_{I}(\mathcal{M})$ iff
$j(A)\in\mathrm{SSy}_{J}(\mathcal{N})$,

where $I:=\mathrm{I}^{1}(\mathcal{M};M_{0})$, and
$J:=\mathrm{I}^{1}(\mathcal{N};j(M_{0}))$.

If $\mathcal{M}=\mathcal{N}$, we call such $j$ an initial
$\mathcal{M}$-embedding.

First, in the next lemma we will show that the condition in the above
definition, i.e. preserving coded subsets, is a necessary condition for
extendability of an initial embedding:

######  Lemma 5.1.

Suppose $\mathcal{M}$ and $\mathcal{N}$ are models of $\mathrm{I}\Sigma_{1}$,
$\mathcal{M}_{0}\subseteq\mathcal{M}$ and
$\mathcal{N}_{0}\subseteq\mathcal{N}$ are bounded submodels (or proper cuts),
and $j:\mathcal{M}_{0}\hookrightarrow\mathcal{N}_{0}$ is an initial embedding.
If $j$ is extendable to some initial embedding
$\hat{j}:\mathcal{M}\hookrightarrow\mathcal{N}$, then $j$ is an initial
$(\mathcal{M},\mathcal{N})$-embedding.

###### 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})$. ∎

Converse of the above lemma holds, when $\mathcal{M}_{0}$ and $j(M_{0})$ are
$\Sigma_{1}$-elementary initial segments of $\mathcal{M}$ and $\mathcal{N}$:

######  Theorem 5.2.

Suppose $\mathcal{M}$ and $\mathcal{N}$ are countable and nonstandard models
of $\mathrm{I}\Sigma_{1}$, and $I$ and $J$ are $\Sigma_{1}$-elementary initial
segments of $\mathcal{M}$ and $\mathcal{N}$, respectively. Then for any
isomorphism ${j:I\rightarrow J}$ which is an initial
$(\mathcal{M},\mathcal{N})$-embedding and each $b>J$, there exists some proper
initial embedding $\hat{j}:\mathcal{M}\hookrightarrow\mathcal{N}$ such that
$\hat{j}\upharpoonright_{I}=j$ and $\hat{j}(M)<b$.

###### Sketch of proof.

The proof is conducted by a back-and-forth argument similar to the one used in
the proof of [1, Thm. 3.3]; we will build finite partial functions
$\bar{u}\mapsto\bar{v}$ such that the following induction hypothesis holds:

If $\mathcal{M}\models[f(\bar{u},i)\downarrow]$, then
$\mathcal{N}\models[f(\bar{v},j(i))\downarrow]^{<b}$,

for every $f\in\mathcal{F}$ and $i\in I$.

For the ‘forth’ steps, if $\bar{u}\mapsto\bar{v}$ is built, for given $m\in M$
we define:

$H:=\\{\langle r,i\rangle\in I:\
\mathcal{M}\models[f_{r}(\bar{u},m,i)\downarrow]\\}$.

Then, let $h\in M$ such that $H=I\cap h_{\mathrm{E}}$. Since $j$ is an initial
$(\mathcal{M},\mathcal{N})$-embedding, there exists some $h^{\prime}\in N$
such that $j(H)=J\cap h^{\prime}_{\mathrm{E}}$. Therefore, by induction
hypothesis for every $s\in I$ it holds that:

$(1):\ \ $ $\mathcal{N}\models\exists x,w<b\ \forall\langle r,i\rangle<j(s)\
(\langle
r,i\rangle\mathrm{E}h^{\prime}\rightarrow[f_{r}(\bar{v},x,i))\downarrow]^{<w})$.

Since $j$ is onto, statement (1) implies that for every $t\in J$ it hold that:

$(2):\ \ $ $\mathcal{N}\models\exists x,w<b\ \forall\langle r,i\rangle<t\
(\langle
r,i\rangle\mathrm{E}h^{{}^{\prime}}\rightarrow[f_{r}(\bar{v},x,i))\downarrow]^{<w})$.

Therefore, by using $\Sigma_{1}$-Overspill in $\mathcal{N}$, we will find some
image for $m$, for which induction hypothesis holds. The ‘back’ stages can be
done similarly. ∎

The proof of the above theorem can also be modified for $I$-small submodels:

######  Theorem 5.3.

Suppose $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ is countable and nonstandard,
$I$ is a strong cut of $\mathcal{M}$, $\mathcal{M}_{0}$ is an $I$-small
$\Sigma_{1}$-elementary submodel of $\mathcal{M}$ such that
$M_{0}:=\\{(a)_{i}:i\in I\\}$, and $j$ is an initial embedding of
$\mathcal{M}_{0}$ such that $j(I)\subseteq_{e}\mathcal{M}$. Then the following
are equivalent:

  * (1)

$j\upharpoonright_{I}$ is an initial $\mathcal{M}$-embedding, and there exists
some $b\in M$ such that ${\mathcal{M}\models j((a)_{i})=(b)_{j(i)}}$ for all
$i\in I$.

  * (2)

$j$ extends to some proper initial self-embedding of $\mathcal{M}$.

###### Sketch of proof.

$(2)\Rightarrow(1)$ holds by Lemma 5.1. In order to prove $(1)\Rightarrow(2)$,
we will use a similar argument to the proof of [1, Thm. 3.3] to obtain an
extension $\hat{j}$ of $j$. For this purpose, first we will fix some $d\in M$
which is an upper bound for $M_{0}$. Then, we will build finite partial
functions $\bar{u}\mapsto\bar{v}$ such that the following induction hypothesis
holds:

$\mathcal{M}\models[f(\bar{u},(a)_{i})\downarrow]\rightarrow[f(\bar{v},(b)_{j(i)})\downarrow]^{<d}$,

for every $f\in\mathcal{F}$ and $i\in I$.

Here, we outline the proof for the ‘back’ steps and the proof of ‘forth’ steps
is left to the reader. Suppose $\bar{u}\mapsto\bar{v}$ is built, and
$m<\max\\{\bar{v}\\}$ is given. We define:

$L:=\\{\langle r,i\rangle\in j(I):\
\mathcal{M}\models\neg[f_{r}(\bar{v},m,(b)_{i})]^{<d}\\}$.

Then, let $l\in M$ such that $L=j(I)\cap l_{\mathrm{E}}$. Since
$j\upharpoonright_{I}$ is an initial $\mathcal{M}$-embedding, then there
exists some $l^{\prime}\in M$ such that $j^{-1}(L)=I\cap
l^{\prime}_{\mathrm{E}}$. Moreover, by using Lemma 3.3, for every $s\in I$
there exists some $(a)_{i_{s}}\in M_{0}$ which codes of the following subset
of $M_{0}$:

$A:=\\{\langle r,(a)_{i}\rangle:\ \mathcal{M}\models(\langle r,i\rangle<s\
\wedge\langle r,i\rangle\mathrm{E}l^{\prime})\\}.$

By $\Pi_{1}$-Overspill, it suffices to prove that for every $s\in I$ it holds
that:

$(\star):\ \ $ $\mathcal{M}\models\exists x<\max\\{\bar{u}\\}\ \forall\langle
r,i\rangle<s\ (\langle
r,i\rangle\mathrm{E}l^{\prime}\rightarrow\neg[f_{r}(\bar{u},x,(a)_{i})\downarrow])$.

Suppose not; i.e. there exists some $s\in I$ which for statement $(\star)$
does not hold. So we have:

$(i):\ \ $ $\mathcal{M}\models\forall x<\max\\{\bar{u}\\}\ \exists\langle
r,i\rangle<s\ (\langle r,i\rangle\mathrm{E}l^{\prime}\
\wedge[f_{r}(\bar{u},x,(a)_{i})\downarrow])$.

As a result, by using $\Sigma_{1}$-Collection in $\mathcal{M}$, from statement
$(i)$, induction hypothesis, and the way we chose $(a)_{i_{s}}$, we may
conclude that:

$(ii):\ \ $ $\mathcal{M}\models\forall x<\max\\{\bar{v}\\}\ \exists\langle
r,\epsilon\rangle\mathrm{E}(b)_{j(i_{s})}\
([f_{r}(\bar{v},x,\epsilon)\downarrow]^{<d})$.

So by statement $(ii)$, there exists some $\langle r,i\rangle<s$ such that:

$(iii):\ \ $ $\mathcal{M}\models(\langle r,i\rangle\mathrm{E}l^{\prime}\
\wedge\ [f_{j(r)}(\bar{v},m,(b)_{j(i)})\downarrow]^{<d})$.

But statement $(iii)$ is in direct contradiction with the way we chose
$l^{\prime}$.

∎

In the last theorem, we investigate whether we can control the set of fixed
points, while extending an isomorphism to an initial self-embeddings with
larger domain:

######  Theorem 5.4.

Suppose $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ is countable and nonstandard,
$I$ is a strong $\Sigma_{1}$-elementary initial segment of $\mathcal{M}$, and
$j:I\rightarrow I$ is an isomorphism and an initial $\mathcal{M}$-embedding.
Then there exists some proper initial self-embedding $\hat{j}$ of
$\mathcal{M}$ such that $\hat{j}\upharpoonright_{I}=j$, and
${\mathrm{Fix}(\hat{j})=\mathrm{Fix}(j)}$.

###### Sketch of proof.

First, we will fix some arbitrary $a>I$. Since $I$ is strong in $\mathcal{M}$,
there exists some $b>I$ such that:

$(\star):\ \ $ if $\mathcal{M}\models[f(a,i)\downarrow]$ and $f(a,i)>I$ then
$f(a,i)>b$, for all $f\in\mathcal{F}$ and $i\in I$.

So by Theorem 5.2, there exists some proper initial self-embedding $\bar{j}$
of $\mathcal{M}$ such that $\bar{j}\upharpoonright_{I}=j$ and $\bar{j}(M)<b$.
If $\mathrm{Fix}(\bar{j})=\mathrm{Fix}(j)$, then we are done. Otherwise we
will build $\hat{j}$ in the following way:

  * •

By using a similar argument to the proof of Theorem 3.4, we construct some
proper initial self-embedding $h$ of
$\mathcal{N}:=\mathrm{H}^{1}(\mathcal{M};a)$ such that
$h\upharpoonright_{I}=j$, $\mathrm{Fix}(h)=\mathrm{Fix}(j)$, and $h(N)<b$. In
order to construct such $h$, we will inductively construct finite functions
$\bar{u}\mapsto\bar{v}$ such that:

$\mathrm{P}(\bar{u},\bar{v})\equiv[f(\bar{u},i)\downarrow]\rightarrow[f(\bar{v},j(i))\downarrow]^{<b}$,
for all $f\in\mathcal{F}$ and $i\in I$; and
$\mathrm{Q}(\bar{u},\bar{v})\equiv\left(\begin{array}[]{c}[f(\bar{u},i)\downarrow]\wedge[f(\bar{v},j(i))\downarrow]^{<b}\wedge\\\
f(\bar{u},i)\notin I\end{array}\right)\Rightarrow f(\bar{u},i)\neq
f(\bar{v},j(i))$, for all $f\in\mathcal{F}$ and all $i\in I$.

    * –

For the first step of induction, we will take $a\mapsto\bar{j}(a)$; clearly
$\mathrm{P}(a,\bar{j}(a))$ holds in $\mathcal{M}$. Moreover, by statement
$(\star)$ and since $\mathrm{Fix}(\bar{j})<b$, the property
$\mathrm{Q}(a,\bar{j}(a))$ also holds in $\mathcal{M}$.

    * –

Then suppose $\bar{u}\mapsto\bar{v}$ is built. We will just mention the
changes that should be made in the ‘forth’ steps of Theorem 3.4, and ‘back’
steps should be modified similarly:

      * *

Suppose $m\in N\setminus\\{\bar{u}\\}$ is given. By the definition of
$\mathcal{N}$, without loss of generality, we may assume that $m\leq
t(\bar{u},a)$ for some $t\in\mathcal{F}$. Put:

$C:=\\{\langle r,i\rangle\in
I:\mathcal{N}\models[f_{r}(\bar{u},m,i)\downarrow]\wedge
f_{r}(\bar{u},m,i)\notin\mathrm{K}^{1}(\mathcal{N};I\cup\\{\bar{u}\\})\\}.$

Let $\alpha,\alpha^{\prime}\in N$ such that $C=I\cap\alpha_{\mathrm{E}}$ and
$j(C)=I\cap\alpha^{\prime}_{\mathrm{E}}$ (note that since $\mathcal{N}$ is a
$\Sigma_{1}$-elementary initial segment of $\mathcal{M}$ containing $I$, $j$
is an initial $\mathcal{N}$-embedding):

      * *

Let $L:=\\{\langle r,i\rangle\in
I:\mathcal{N}\models[f_{r}(\bar{u},m,i)\downarrow]\\}$,
$L=I\cap\beta_{\mathrm{E}}$, and $j(L)=I\cap\beta^{\prime}_{\mathrm{E}}$ for
$\beta,\beta^{\prime}\in N$.

      * *

For every $s\in\bar{j}(N)$ such that $\bar{j}(s^{\prime})=s$ for some
$s^{\prime}\in N$, let:
$p_{s}(y):=\\{y<t(\bar{v},\bar{j}(a))\\}\cup p_{s1}(y)\cup p_{s2}(y)$; where:
${p_{s1}(y):=\\{\forall i<s(\langle
n,i\rangle\mathrm{E}\beta^{\prime}\rightarrow[f_{n}(\bar{v},y,i)\downarrow]^{<b}):\
n\in\mathbb{N}\\};}$ and
$p_{s2}(y):=\left\\{\forall w<s^{\prime}\ \forall
i<s\left(\begin{array}[]{c}\left(\begin{array}[]{c}\langle
n,w\rangle\mathrm{E}\alpha\ \wedge\ \langle
n,i\rangle\mathrm{E}\alpha^{\prime}\ \wedge\\\
[f_{n}(\bar{v},y,i)\downarrow]^{<b}\end{array}\right)\rightarrow\\\
f_{n}(\bar{u},m,w)\neq f_{n}(\bar{v},y,i)\end{array}\right):\
n\in\mathbb{N}\right\\}$.

      * *

In order to find some $s>I$ such that $s\in\bar{j}(N)$ and $p_{s}(y)$ is
finitely satisfiable, we will adapt the rest of the proof of Theorem 3.4
accordingly; for instance, we will mention two of these adaptations:

      * $(1)$

Let $d^{\prime}\in N$ such that $d^{\prime}>I$ and $d:=\bar{j}(d^{\prime})$.
Moreover, for every $i,s,s^{\prime}\in N$, let
$\Theta(s,s^{\prime},i,\bar{u},m,\bar{v},b,\bar{j}(a),\alpha,\alpha^{\prime},\beta^{\prime})$
be the following $\Delta_{0}$-formula:

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

Then, for every $i\in M$, we define:

$g(i):=\mathrm{max}\\{w<d^{\prime}:\ \mathcal{M}\models\exists x\leq d\
\Theta(x,w,i,\bar{u},m,\bar{v},b,\bar{j}(a),\alpha,\alpha^{\prime},\beta^{\prime})\\}$.

Since $I$ is strong, there exists some $e^{\prime}>I$ such that
$e^{\prime}\leq d^{\prime}$, and for all $i\in I$, $g(i)>I$ iff
$g(i)>e^{\prime}$. Then, for every $i\in M$ put:

$l(i):=\mathrm{max}\left\\{x<\bar{j}(e^{\prime}):\
\mathcal{M}\models\left(\begin{array}[]{c}[g(i)\downarrow]^{<d^{\prime}}\
\wedge\ g(i)>e^{\prime}\ \wedge\\\
\Theta(x,g(i),i,\bar{u},m,\bar{v},b,\bar{j}(a),\alpha,\alpha^{\prime},\beta^{\prime})\end{array}\right)\right\\}$.

Again, since $I$ is strong, there exists some $e>I$ such that $e\leq d$, and
for all $i\in I$, $l(i)>I$ iff $l(i)>e$. Then $p_{e}(y)$ is a finitely
satisfiable type.

      * $(2)$

Instead of the function $\langle o(\diamondsuit,y),h(\diamondsuit,y)\rangle$
we need to define the following function:

$\langle
o(\diamondsuit,y),h(\diamondsuit,y),h^{\prime}(\diamondsuit,y)\rangle:=\min\left\\{\langle
n_{t},i,w\rangle\mathrm{E}\alpha_{s_{{}_{0}}}:\left(\begin{array}[]{c}[b(\diamondsuit,y)\downarrow]\wedge\\\
[f_{n_{t}}(\diamondsuit,y,i)\downarrow]^{<b(\diamondsuit,y)}\ \wedge\\\
[s_{t}(\diamondsuit,w)\downarrow]^{<b(\diamondsuit,y)}\wedge\\\
s_{t}(\diamondsuit,w)=f_{n_{t}}(\diamondsuit,y,i)\end{array}\right)\right\\}$;
where $\alpha_{s_{0}}\in I$ is the code of the following subset of $I$:

$\\{\langle n,i,w\rangle:\ \mathcal{M}\models i<s_{0}\wedge
w<j^{-1}(s_{0})\wedge\langle n,w\rangle\mathrm{E}\alpha\wedge\langle
n,i\rangle\mathrm{E}\alpha^{\prime}\\}.$

The rest of the adaptations should be made similar to statements (1) and (2)
in order to construct $h$.

    * –

If $\mathcal{M}=\mathcal{N}$, then we are done. Otherwise, by using Theorem
2.3 we shall find some proper initial embedding
$k:\mathcal{M}\hookrightarrow\mathcal{N}$ such that
$I\subseteq\mathrm{I}_{\mathrm{fix}}(k)$ and $b\in k(M)$.

    * –

Finally, we put $\hat{j}:=k^{-1}hk$.

∎

######  Remark 2.

If we let $j$ be the trivial automorphism of $I$, then Theorem 5.4 implies
Theorem 2.4(2).

## References

  * [1] S. Bahrami and A. Enayat, Fixed points of self-embeddings of models of arithmetic, Ann. Pure Appl. Logic 169, 2018, pp. 487-513.
  * [2] J. Barwise and J. Schlipf, On recursively saturated models of arithmetic, Model Theory and Algebra: a memorial tribute to A. Robinson (edited by D. Saracino and V. Weispfenning), Springer Lecture Notes in Mathematics, vol. 498, 1976, pp. 42-55.
  * [3] c. Dimitracopoulos, J. Paris, A note on a theorem of H. Friedman, Z. Math. Logik Grundlag. Math., 34(1), 1988, pp. 13–17.
  * [4] A. Enayat, Automorphisms of models of arithmetic: a unified view, Ann. Pure Appl. Logic 145 (2007), pp. 16-36.
  * [5] H. Friedman, Countable models of set theories, Lecture Notes in Math. 337, Springer, Berlin, 1973, pp. 539-573.
  * [6] P. Hájek and P. Pudlák, Metamathematics of First Order Arithmetic, Springer, Heidelberg, 1993.
  * [7] R. Kaye, Models of Peano Arithmetic, Oxford University Press, Oxford, 1991.
  * [8] R. Kaye, R. Kossak, and H. Kotlarski, Automorphisms of recursively saturated models of arithmetic, Ann. Pure Appl. Logic 55 1991, pp. 67-99.
  * [9] L. Kirby and J. Paris, $\Sigma_{n}$-Collection schemas in arithmetic, in Logic Colloquium ’77, North-Holland Publishing Company, Amsterdam, 1978, pp. 199-209.
  * [10] R. Kossak, A note on satisfaction classes, Notre Dame of Formal Logic, vol. 26, 1985, pp. 1-8.
  * [11] R. Kossak, and H. Kotlarski, Results on automorphisms of recursively saturated models of $\mathrm{PA}$. Fund. Math., 129(1), 1988, pp. 9–15.
  * [12] R. Kossak, and H. Kotlarski, On extending automorphisms of models of Peano arithmetic, Fund. Math., 149(3), 1996, pp. 245–263.
  * [13] R. Kossak and J. Schmerl, Arithmetically saturated models of arithmetic, Notre Dame J. Formal Logic 36(4), 1995, pp. 531–546
  * [14] R. Kossak and J. Schmerl,, The Structure of Models of Peano Arithmetic, Oxford, 2006.
  * [15] D. Lascar, The small index property and recursively saturated models of Peano arithmetic, Automorphisms of first-order structures, Oxford University Press, New York, 1994 pp. 281–292.
  * [16] A. Wilkie, On the theories of end-extensions of models of arithmetic, Lecture Notes in Mathematics, 619, 1977, pp. 305–310.