# Tanaka’s Theorem Revisited

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

Tanaka (1997) proved a powerful generalization of Friedman’s self-embedding
theorem that states that given a countable nonstandard model
$(\mathcal{M},\mathcal{A})$ of the subsystem $\mathrm{WKL}_{0}$ of second
order arithmetic, and any element $m$ of $\mathcal{M}$, there is a self-
embedding $j$ of $(\mathcal{M},\mathcal{A})$ onto a proper initial segment of
itself such that $j$ fixes every predecessor of $m$.

Here we extend Tanaka’s work by establishing the following results for a
countable nonstandard model $(\mathcal{M},\mathcal{A})\ $of $\mathrm{WKL}_{0}$
and a proper cut $\mathrm{I}$ of $\mathcal{M}$:

Theorem A. The following conditions are equivalent:

(a) $\mathrm{I}$ is closed under exponentiation.

(b) There is a self-embedding $j$ of $(\mathcal{M},\mathcal{A})$ onto a proper
initial segment of itself such that $I$ is the longest initial segment of
fixed points of $j$.

Theorem B. The following conditions are equivalent:

(a) $\mathrm{I}$ is a strong cut of $\mathcal{M}$ and
$\mathrm{I}\prec_{\Sigma_{1}}\mathcal{M}.$

(b) There is a self-embedding $j$ of $(\mathcal{M},\mathcal{A})$ onto a proper
initial segment of itself such that $\mathrm{I}$ is the set of all fixed
points of $j$.

##  1 Introduction

One of the fundamental results concerning nonstandard models of Peano
arithmetic $(\mathrm{PA}\mathsf{)}$ is Friedman’s theorem [4, Theorem 4.4]
that states every countable nonstandard model of $\mathrm{PA}$ is isomorphic
to a proper initial segment of itself. A notable generalization of Friedman’s
theorem was established by Tanaka [13] for models of the well-known subsystem
$\mathrm{WKL}_{0}$ of second order arithmetic, who established:

Theorem 1.1. (Tanaka) Suppose $(\mathcal{M},\mathcal{A})$ is a countable
nonstandard model of $\mathrm{WKL}_{0}$.

(a) There is a proper initial segment $\mathrm{I}$ of $\mathcal{M}$ and an
isomorphism $j$ between $(\mathcal{M},\mathcal{A)}$ and
$(\mathrm{I},\mathcal{A}_{\mathrm{I}})$, where
$\mathcal{A}_{\mathrm{I}}:=\\{\mathrm{A}\cap\mathrm{I}:\
\mathrm{A}\in\mathcal{A}\\}$.

(b) Given any prescribed $m$ in $\mathcal{M}$, there is an $\mathrm{I}$ and
$j$ as in (a) such that $j(x)=x$ for all $x\leq m.$

Tanaka’s principal motivation in establishing Theorem 1.1 was the development
of non-standard methods within $\mathrm{WKL}_{0}$ in the context of the
reverse mathematics research program; for example Tanaka and Yamazaki [14]
used Theorem 1.1 to show that the Haar measure over compact groups can be
implemented in $\mathrm{WKL}_{0}$ via a detour through nonstandard models.
This is in contrast to the previously known constructions of the Haar measure
whose implementation required the stronger subsystem ACA0. Other notable
applications of the methodology of nonstandard models can be found in the work
of Sakamato and Yokoyama [11], who showed that over the subsystem
$\mathrm{RCA}_{0}$ the Jordan curve theorem and the Schönflies theorem are
equivalent to $\mathrm{WKL}_{0}$; and in the work of Yokoyama and Horihata
[8], who established the equivalence of $\mathrm{ACA}_{0}$ and Riemann’s
mapping theorem for Jordan regions over $\mathrm{WKL}_{0}.$

Here we continue our work [1] on the study of fixed point sets of self-
embeddings of countable nonstandard models of I$\Sigma_{1}$ by focusing on the
behavior of fixed point sets in Tanaka’s theorem. Our methodology can be
generally described as an amalgamation of Enayat’s strategy for proving
Tanaka’s theorem [3] with some ideas and results from [1].111Enayat’s paper
[3] provides a complete proof of part (a) of Theorem 1.1, and an outline of
the proof of part (b) of Theorem 1.1. Before stating our results, recall that
$j$ is said to be a proper initial self-embedding of
$(\mathcal{M},\mathcal{A)}$ if there is a proper initial segment $\mathrm{I}$
of $\mathcal{M}$ and an isomorphism $j$ between $(\mathcal{M},\mathcal{A)}$
and $(\mathrm{I},\mathcal{A}_{\mathrm{I}})$, where
$\mathcal{A}_{\mathrm{I}}:=\\{\mathrm{A}\cap\mathrm{I}:\
\mathrm{A}\in\mathcal{A}\\}$; $\mathrm{I}_{\mathrm{fix}}(j)$ is the longest
initial segment of fixed points of $j$; and $\mathrm{Fix}(j)$ is the fixed
point set of $j$, in other words:

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

Our main results are Theorems A and B below. Note that Theorem A is a
strengthening of Tanaka’s Theorem (see Section 3 for more detail).

Theorem A. Suppose $(\mathcal{M},\mathcal{A})$ is a countable nonstandard
model of $\mathrm{WKL}_{0}.$The following conditions are equivalent for a
proper cut $\mathrm{I}$ of $\mathcal{M}$:

(1) There is a self-embedding $j$ of $(\mathcal{M},\mathcal{A})$ such that
$\mathrm{I}_{\mathrm{fix}}(j)=\mathrm{I}.$

(2) $\mathrm{I}$ is closed under exponentiation.

(3) There is a proper initial self-embedding $j$ of
$(\mathcal{M},\mathcal{A})$ such that
$\mathrm{I}_{\mathrm{fix}}(j)=\mathrm{I}.$

Theorem B. Suppose $(\mathcal{M},\mathcal{A})$ is a countable nonstandard
model of $\mathrm{WKL}_{0}.$The following conditions are equivalent for a
proper cut $\mathrm{I}$ of $\mathcal{M}$:

(1) There is a self-embedding $j$ of $(\mathcal{M},\mathcal{A})$ such that
$\mathrm{Fix}(j)=\mathrm{I}.$

(2) $\mathrm{I}$ is a strong cut of $\mathcal{M}$ and
$\mathrm{I}\prec_{\Sigma_{1}}\mathcal{M}.$

(3) There is a proper initial self-embedding $j$ of
$(\mathcal{M},\mathcal{A})$ such that ${\mathrm{Fix}(j)=\mathrm{I}.}$

Theorem A is established in Section 3, and Section 4 is devoted to proving
Theorem B.

Acknowledgment. I am indebted to my PhD supervisor, Ali Enayat, for his
encouragements, precious comments and feedback in the formation of this paper.

##  2 Preliminaries

In this section we review some definitions and basic results that are relevant
to the statements and proofs of our main results.

  * •

$\mathrm{WKL}_{0}$ is the second order theory whose models are of the form of
$(\mathcal{M},\mathcal{A}),$ where $(\mathcal{M},\mathcal{A})$ satisfies (1)
Induction for $\Sigma_{1}^{0}$ formulas; (2) Comprehension for
$\Delta_{1}^{0}$-formulas; and (3) Weak König’s Lemma (which asserts that
every infinite subtree of the full binary tree has an infinite branch).

  * •

$\mathrm{Exp}:=\forall x\exists y\ \mathrm{Exp}(x,y)$, where
$\mathrm{Exp}(x,y)$ is a $\Delta_{0}$-formula that expresses $2^{x}=y$ within
I$\Delta_{0}.$

  * •

The binary $\Delta_{0}$-formula $xEy$, known as Ackermann’s membership
relation, expresses “the $x$-th bit of the binary expansion of $y$ is 1”
within I$\Delta_{0}.$

  * •

A subset $\mathrm{X}$ of $\mathrm{M}$ is coded in $\mathcal{M}$ iff there is
some $a\in\mathrm{M}$ such that
$\mathrm{X}={\left(a_{E}\right)^{\mathcal{M}}:=\\{x\in\mathrm{M}:\mathcal{M}\models
xEa\\}}.$
Given $a\in\mathrm{M},$ by $\underline{a}$ we mean the set
$\\{x\in\mathrm{M}:x<a\\}$. Note that $\underline{a}$ is coded in
$\mathcal{M}$, where $\mathcal{M}$ is a model of $\mathrm{I}\Delta_{0}$,
provided $2^{a}$ exists in $\mathcal{M}$.
It is well-known that for any $n>0$ and
$\mathcal{M}\models\mathrm{I}\Sigma_{n}$, if $\varphi(x,a)$ is an unary
$\Sigma_{n}$-formula, where $a$ is a parameter from $\mathcal{M}$, then the
set
${\varphi^{\mathcal{M}}(a):={\\{}}b\in\mathrm{M}{{:\mathcal{M}\models\varphi(b,a)\\}}}$
is piece-wise coded in $\mathcal{M}$; i.e. for every $c\in\mathrm{M}$,
$\varphi^{\mathcal{M}}(a)\cap\underline{c}$ is coded in $\mathcal{M}$. More
specifically, there is some element less than $2^{c}$ which codes
$\varphi^{\mathcal{M}}(a)\cap\underline{c}$.
Moreover, the above statement holds for $n=0$ if
$\mathcal{M}\models\mathrm{I}\Delta_{0}+\mathrm{Exp}$.

  * •

For every cut $\mathrm{I}$ of $\mathcal{M}$, the $\mathrm{I}$-standard system
of $\mathcal{M}$, presented by $\mathrm{SSy}_{I}(\mathcal{M})$, is the family
consisting of sets of the form $a_{E}\cap\mathrm{I}$, where $a\in\mathrm{M}$;
in other words:

$\mathrm{SSy}_{\mathrm{I}}(\mathcal{M})=\\{\left(a_{E}\right)^{\mathcal{M}}\cap\mathrm{I}:\
a\in\mathrm{M}\\}.$

When $\mathrm{I}$ is the standard cut, i.e. $\mathrm{I}=\mathbb{N}$, we simply
write $\mathrm{SSy}(\mathcal{M})$ instead of
$\mathrm{SSy}_{\mathbb{N}}(\mathcal{M}).$

  * •

Given a proper cut $\mathrm{I}$ of $\mathcal{M}$, $\mathrm{I}$ is called a
strong cut, if for every coded function $f$ in $\mathcal{M}$ whose domain
contains $\mathrm{I}$, there exists some $s\in\mathrm{M}$ such that for every
$i\in\mathrm{I}$ it holds that $f(i)\notin\mathrm{I}$ iff $s<f(i)$.

  * •

$\mathrm{Sat}_{{}_{\Sigma_{n}}}$ is the arithmetical formula defining the
satisfaction predicate for $\Sigma_{n}$-formulas within
$\mathrm{I}\Delta_{0}+\mathrm{Exp}$. It is well-known that for each positive
$n\in\omega$, $\mathrm{Sat}_{{}_{\Sigma_{n}}}$ can be expressed by a
$\Sigma_{n}$-formula in $\mathrm{I}\Sigma_{n}$; furthermore, within a model of
${\mathrm{I}\Delta_{0}+\mathrm{Exp}}$ (with the help of a nonstandard
parameter if the model is nonstandard), $\mathrm{Sat}_{{}_{\Sigma_{0}}}$
(which is also written as $\mathrm{Sat}_{{}_{\Delta_{0}}}$) is expressible
both as a $\Sigma_{1}$ and $\Pi_{1}$-formula.

  * •

The strong $\Sigma_{n}$-Collection scheme consists of formulas of the
following form where $\varphi$ is a $\Sigma_{n}$-formula:

$\forall w\ \forall v\ \exists z\forall x<v(\exists y\
\varphi(x,y,w)\rightarrow\exists y<z\ \varphi(x,y,w)).$

It is well-known that the strong $\Sigma_{n}$-Collection scheme is provable in
$\mathrm{I}\Sigma_{n}$ for every $n>0.$

  * •

Every model $\mathcal{M}$ of $\mathrm{I}\Delta_{0}+\mathrm{Exp}$ satisfies the
Coded Pigeonhole Principle, i.e. if $b\in\mathrm{M}$, and
$f:\underline{b+1}\rightarrow\underline{b}$ is a coded function in
$\mathcal{M}$, then $f$ is not injective.

  * •

By an embedding $j$ from second order model $(\mathcal{M},\mathcal{A})$ into
$(\mathcal{N},\mathcal{B})$, we mean that $j$ is an embedding from
$\mathcal{M}$ into $\mathcal{N}$ such that for every $X\subseteq M$,
$X\in\mathcal{A}$ iff $j(X)=Y\cap j(M)$ for some $Y\in\mathcal{B}$.

  * •

When $\mathcal{M}$ and $\mathcal{N}$ are models of arithmetic and $b$ is in
$\mathrm{M}$, we write $\mathcal{M}\subseteq_{\mathrm{end,\Pi}_{1,\leq
b}}\mathcal{N}$, when $\mathcal{N}$ is an end extension of $\mathcal{M}$ and
all $\Pi_{1}$-formulas whose parameters are in $\underline{b+1}$ are absolute
in the passage between $\mathcal{M}$ and $\mathcal{N}$, i.e.,
$\mathrm{Th}_{\Pi_{1}}(\mathcal{M},m)_{m\leq
b}=\mathrm{Th}_{\Pi_{1}}(\mathcal{N},m)_{m\leq b}.$

Theorem 2.1. ([3, Theorem 3.2]) Let $(\mathcal{M},\mathcal{A})$ be a countable
model of $\mathrm{WKL}_{0}$ and let $b\in\mathrm{M}$. Then $\mathcal{M}$ has a
countable recursively saturated proper end extension $\mathcal{N}$ satisfying
$\mathrm{I}\Delta_{0}+\mathrm{Exp}+\mathrm{B}\Sigma_{1}$ such that
$\mathrm{SSy}_{\mathrm{M}}(\mathcal{N})=\mathcal{A}$, and
$\mathcal{M}\subseteq_{\mathrm{end,\Pi_{1},\leq b}}\mathcal{N}$.

Remark 2.2. The proofs of our main results take advantage of the following
additional features of the model $\mathcal{N}$ constructed in Enayat’s proof
of Theorem 2.1, namely: given $b$ in $\mathcal{M}$, there is an elementary
chain of models ${(\mathcal{N}_{n}:n\in\omega)}$ satisfying the following
three properties:

  1. $(i)$

$\mathcal{N}=\cup_{n\in\omega}\mathcal{N}_{n}$;

  2. $(ii)$

For every $n\in\omega$, $\mathcal{M}\subseteq_{\mathrm{end,\Pi_{1},\leq
b}}\mathcal{N}_{n}\prec\mathcal{N}$;

  3. $(iii)$

For every $n\in\omega$ the elementary diagram of
$(\mathcal{N}_{n},a)_{a\in\mathrm{N}_{n}}$ is available in
$(\mathcal{M},\mathcal{A})$ via some $\mathrm{ED}_{n}\in\mathcal{A}$. Note
that $\mathrm{Th}\left((\mathcal{N}_{n},a)_{a\in\mathrm{N}_{n}}\right)$ is a
proper subset of $\mathrm{ED}_{n}$ since $\mathrm{ED}_{n}$ includes sentences
of nonstandard length.

Remark 2.3. Enayat [3] noted that if $(\mathcal{M},\mathcal{A})$ is a model of
$\mathrm{WKL}_{0}$ and $b$ is in $\mathrm{M}$, and there is some end extension
$\mathcal{N}$ of $\mathcal{M}$ such that (1) $\mathcal{N}\models
I\Delta_{0}+\mathrm{Exp}$, (2)
$\mathrm{SSy}_{\mathrm{M}}(\mathcal{N})=\mathcal{A}$, and (3) there is an
initial self-embedding $j_{1}\ $of $\mathcal{N}$ onto an initial segment that
is bounded above by $b$, then the restriction $j$ of $j_{1}$ to $\mathcal{M}$
is an embedding of $\mathcal{M}$ onto an an initial segment $\mathrm{J}$ of
$\mathcal{M}$ that is below $b$ which has the important feature that $j$ is an
isomorphism between $(\mathcal{M},\mathcal{A})$ and
$(\mathrm{J},\mathcal{A}_{\mathrm{J}})$. Note that if $\mathrm{I}$ is a proper
cut of $\mathcal{M},$ then $\mathrm{I}_{\mathrm{fix}}(j_{1})=\mathrm{I}$
implies that $\mathrm{I}_{\mathrm{fix}}(j)=\mathrm{I}$; and
$\mathrm{Fix}(j_{1})=\mathrm{I}$ implies that $\mathrm{Fix}(j)=\mathrm{I}.$

  * •

The following theorem summarizes some of the results about
$\mathrm{I}_{\mathrm{fix}}(j)$ and $\mathrm{Fix}(j)$ from [1] which will be
employed in this paper:

Theorem 2.4. Suppose $\mathcal{M}\models\mathrm{I}\Delta_{0}+\mathrm{Exp}$ and
$j$ is a nontrivial self-embedding of $\mathcal{M}$. Then:

(a)
$\mathrm{I}_{\mathrm{fix}}(j)\models\mathrm{I}\Delta_{0}+\mathrm{B}\Sigma_{1}+\mathrm{Exp}$.

(b) If $\mathcal{M}\models\mathrm{I}\Sigma_{1}$ then $\mathrm{Fix}(j)$ is a
$\Sigma_{1}$-elementary submodel of $\mathcal{M}$. Moreover, if
$\mathrm{Fix}(j)$ is a proper initial segment of $\mathcal{M}$, then it is a
strong cut of $\mathcal{M}$.

  * •

Given two countable nonstandard model $\mathcal{M}$ and $\mathcal{N}$ of
$\mathrm{I}\Sigma_{1}$ which share a common proper cut $\mathrm{I}$, the
following theorem from [1, Cor. 3.3.1] provides a useful sufficient condition
for existence of a proper initial embedding between $\mathcal{M}$ and
$\mathcal{N}$ which fixes each element of $\mathrm{I}$:

Theorem 2.5. Let $\mathcal{M}$, $\mathcal{N}$ and $I$ be as above such that
$I$ is closed under exponentiation. The following are equivalent:

(1) There is a proper initial embedding $f$ of $\mathcal{M}$ into
$\mathcal{N}$ such that $f(i)=i$ _for all_ $i\in I.$

(2) $\mathrm{Th}_{\Sigma_{1}}(\mathcal{M},i)_{i\in
I}\subseteq\mathrm{Th}_{\Sigma_{1}}(\mathcal{N},i)_{i\in I}$ and
$\mathrm{SSy}_{I}(\mathcal{M})=\mathrm{SSy}_{I}(\mathcal{N}).$

  * •

Another prominent subsystem of second order arithmetic is $\mathrm{ACA_{0}}$,
in which the comprehension scheme is restricted to formulas with no second
order quantifier. The following results of Paris and Kirby [9] and Gaifman [6,
Thm. 4.9-4.11] concerning $\mathrm{ACA_{0}}$ are employed in the proof of
Theorem B.222Gaifman couched his results in terms of arbitrary models of
$\mathrm{PA}(\mathcal{L})$ for countable $\mathcal{L}$. Note that if
$(\mathcal{M},\mathcal{A})\models\mathrm{ACA}_{0}$, then the expansion
$(\mathcal{M},A)_{A\in\mathcal{A}}$ of $\mathcal{M}$ is a model of
$\mathrm{PA}(\mathcal{L})$, where $\mathcal{L}$ is the extension of
$\mathcal{L}_{A}$ by predicate symbols for each $A\in\mathcal{A}.$ Moreover,
the collection of subsets of $\mathrm{M}$ that are parametrically definable in
$(\mathcal{M},A)_{A\in\mathcal{A}}$ coincides with $\mathcal{A}$.

Theorem 2.6. (Paris and Kirby) Suppose
$\mathcal{M}\models\mathrm{I}\Delta_{0}$. The following are equivalent for a
proper cut $\mathrm{I}$ of $\mathcal{M}$:

(a) $\mathrm{I}$ is a strong cut of $\mathcal{M}$.

(b)
$(\mathrm{I},\mathrm{SSy}_{\mathrm{I}}(\mathcal{M}))\models\mathrm{ACA}_{0}.$

Theorem 2.7. (Gaifman) Given a countable model $(\mathcal{M},\mathcal{A})$ of
$\mathrm{ACA}_{0}$ and a linear order $\mathbb{L}$, there exists an end
extension $\mathcal{M}_{\mathbb{L}}$ of $\mathcal{M}$ such that there is an
isomorphic copy $\mathbb{L}^{\prime}=\\{c_{l}:l\in\mathbb{L\\}}$ of
$\mathbb{L}$ in $\mathrm{M}_{\mathbb{L}}\backslash\mathrm{M}$, and there is a
composition preserving embedding $j\mapsto\widehat{j}$ from the semi-group of
initial self-embeddings of $\mathbb{L}$ into the semi-group of initial self-
embeddings of $\mathcal{M}_{\mathbb{L}}$ that satisfy the following
properties:

(a) $\mathrm{SSy}_{\mathrm{M}}(\mathcal{M}_{\mathbb{L}})=\mathcal{A}$ and
$\mathrm{Fix}(\widehat{j})=M$ for each initial self-embedding $j$ of
${\mathbb{L}}$ that is fixed point free.

(b) For each initial self-embedding $j$ of ${\mathbb{L}}$, $\widehat{j}$ is an
elementary initial self-embedding of $\mathcal{N}_{\mathbb{L}}$, i.e.
$\widehat{j}(\mathcal{M}_{\mathbb{L}})\preceq_{\mathrm{end}}\mathcal{N}_{\mathbb{L}}$.

(c) $\mathbb{L}^{\prime}$ is downward cofinal in $M_{\mathbb{L}}\backslash M$
if $\mathbb{L}$ has no first element.

(d) For any $l_{0}\in\mathbb{L}$, $l_{0}$ is a strict upper bound for
$j(\mathbb{L})$ iff $c_{l_{0}}$ is a strict upper bound for
$\widehat{j}(M_{\mathbb{L}})$.

##  3 The longest cut fixed by self-embeddings

This section is devoted to the proof of Theorem A. Recall that if
$(\mathcal{M},\mathcal{A})$ is a model of $\mathrm{WKL}_{0}$ there are
arbitrary large as well as arbitrary small nonstandard cuts in $\mathcal{M}$
that are closed under exponentiation. More specifically, for every nonstandard
$a$ in $\mathrm{M}$, there are nonstandard cuts $\mathrm{I}_{1}$ and
$\mathrm{I}_{2}$ (as defined below) such that
$\mathrm{I}_{1}<a\in\mathrm{I}_{2}$, and both are closed under exponentiation:

$\mathrm{I}_{1}:=\\{x\in M:2_{n}^{x}<a\ \text{for all}\ n\in\omega\\}$, where
$2_{0}^{x}:=x$, and for every $n\in\omega$, $2_{n+1}^{x}:=2^{2_{n}^{x}}$;

$\mathrm{I}_{2}:=\\{x\in M:x<2_{n}^{a}\ \text{for some}\ n\in\omega\\}$.

So Theorem A implies that $\mathrm{I_{fix}}(j)$ can be arranged to be as high
or as low in the nonstandard part of $\mathcal{M}$ as desired. In particular,
Theorem A is a strengthening of Tanaka’s Theorem.

Proof of Theorem A. $(1)\Rightarrow(2)$ is an immediate consequence of Theorem
2.4.(a), and $(3)\Rightarrow(1)$ is trivial so we concentrate on establishing
$(2)\Rightarrow(3)$.

Assume that $\mathrm{I}$ is closed under exponentiation and fix some
$a\in\mathrm{M}\setminus\mathrm{I}$. We leave it as an exercise for the reader
to use strong $\Sigma_{1}$-Collection along with the fact that
Sat${}_{\Delta_{0}}$ has a $\Sigma_{1}$-description in $\mathcal{M}$ to show
that there is some $b\in\mathrm{M}$ such that:

$(\sharp)\ \ \ $ $\mathcal{M}\models\forall w<a\left(\exists z\
\delta(z,w)\rightarrow\exists z<b\ \delta(z,w\right))$, for all
$\Delta_{0}$-formulas $\delta$.

Next we invoke Theorem 2.1 to get hold of a countable recursively saturated
proper end extension $\mathcal{N}$ of $\mathcal{M}$ such that
$\mathcal{N}\models\mathrm{I}\Delta_{0}+\mathrm{B}\Sigma_{1}+\mathrm{Exp}$,
${\mathrm{SSy}_{\mathrm{M}}(\mathcal{N})=\mathcal{A}}$, and
$\mathcal{M}\subseteq_{\mathrm{end,\Pi_{1},\leq b}}\mathcal{N}$. Moreover, we
will safely assume that the model $\mathcal{N}$ additionally satisfies the
three properties listed in Remark 2.2. In light of Remark 2.3, in order to
establish (3) it suffices to construct a proper initial self-embedding $j$ of
$\mathcal{N}$ such that $j(\mathrm{N})<b$ and
$\mathrm{I}_{\mathrm{fix}}(j)=\mathrm{I}$. The construction of the desired $j$
is the novel element of the proof of Theorem A, which we now turn to.

To construct $j$ we will employ a modification of the strategy employed in the
proof of $(2)\Rightarrow(3)$ of [1, Theorem 4.1], using a 3-level back-and-
forth method. A modification is needed since we need to overcome the fact that
I$\Sigma_{1}$ need not hold in $\mathcal{N}$; instead we will rely on
recursive saturation of $\mathcal{N}$ and the properties of $\mathcal{N}$
listed in Remark 2.2. First, note that $(\sharp)$ together with the fact that
$\mathrm{Th}_{\Pi_{1}}(\mathcal{M},x)_{x\leq
b}=\mathrm{Th}_{\Pi_{1}}(\mathcal{N},x)_{x\leq b}$, implies:

$(\ast)\ \ \ $ $\mathcal{N}\models\forall w<a\left(\exists z\
\delta(z,w)\rightarrow\exists z<b\ \delta(z,w\right))$, for all
$\Delta_{0}$-formula $\delta$.

Since $\mathrm{I}$ is closed under exponentiation, we can choose
$\\{c_{n}:n\in\omega\\}$ that is downward cofinal in
$\mathrm{M}\setminus\mathrm{I}$ such that $c_{0}=a$ and $2^{c_{n+1}}<c_{n}$
for all $n\in\omega$.

The proof will be complete once we recursively construct finite sequences
$\bar{u}:=\left(u_{0},...,u_{m-1}\right)$ and
$\bar{v}:=\left(v_{0},...,v_{m-1}\right)$ of elements of $\mathcal{N}$ for all
$n\in\omega$ such that:

  * $(i)$

$u_{0}=0=v_{0}$.

  * $(ii)$

For every $c$ in $\mathrm{N}$ there is some $n\in\omega$ such that $c=u_{n}$.

  * $(iii)$

For every $n\in\omega$, $v_{n}<b$, and if for some $c$ in $\mathrm{N}$ it
holds that $c<v_{n}$, then there is some $m\in\omega$ such that $c=v_{m}$.

  * $(iv)$

For every $m\in\omega$ the following condition holds:

$(\ast_{m}):\ \ \ $ $\mathcal{N}\models\forall w<c_{m}\ \left(\exists z\
\delta(z,w,\bar{u})\rightarrow\exists z<b\ \delta(z,w,\bar{v})\right)$,
for every $\Delta_{0}$-formula $\delta$.

  * $(v)$

For every $m\in\omega$, there is some $n\in\omega$ such that $u_{n}<c_{m}$ and
$u_{n}\neq v_{n}$.

Note that $(\ast_{0})$ holds thanks to $(\ast)$ since $c_{0}=a.$ Let
$\\{a_{n}:n\in\omega\\}$ and $\\{b_{n}:n\in\omega\\}$ respectively be
enumerations of element of $\mathrm{N}$ and $\underline{b}$. By statement
$(i)$ and $(\ast_{0})$ the first step of induction holds. Suppose for
$m\in\omega$, $\bar{u}$ and $\bar{v}$ are constructed such that $(\ast_{m})$
holds. In order to find suitable $u_{m+1}$ and $v_{m+1}$, by considering
congruence modulo 3 we have three cases for $m+1$: Case 0 takes care of $(ii)$
and $(iv)$, Case 1 takes care of $(iii)$ and $(iv)$, and Case 2 takes care of
$(v)$ and $(iv)$.

CASE 0 ($\mathbf{m+1=3k}$, for some $\mathbf{k}\in\omega$): In this case if
$a_{k}$ is one of the elements of $\bar{u}$, put $u_{m+1}=u_{m}$ and
$v_{m+1}=v_{m}$. Otherwise, put $u_{m+1}=a_{k}$ and define:

$p(y):=\\{y<b\\}\cup\left\\{\forall w<c_{m+1}(\exists z\
\delta(z,w,\bar{u},a_{k})\rightarrow\exists z<b\
\delta(z,w,\bar{v},y)):\delta\ \mathrm{is\ a}\
\Delta_{0}\mathrm{-formula}\right\\}.$

Note that $p(y)$ is a recursive type. Since $\mathcal{N}$ is recursively
saturated, it suffices to prove that $p(y)$ is finitely satisfiable and let
$v_{m+1}$ be one of the realizations of $p(y)$ in $\mathcal{N}$. Since $p(y)$
is closed under conjunctions we only need to show that each formula in $p(y)$
is satisfiable. For this purpose, suppose $\delta$ is a $\Delta_{0}$-formula,
and let

$\mathrm{D}:=\left\\{w\in\underline{c_{m+1}}:\mathcal{N}\models\exists z\
\delta(z,w,\bar{u},a_{k})\right\\}.$

We claim that there is some $d<2^{c_{m+1}}$ which codes $\mathrm{D}$ in
$\mathcal{N}$. To see this, we note that in the above definition,
$\mathcal{N}$ can be safely replaced by some $\mathcal{N}_{n}$, where $n$ is
large enough to contain the parameters $\bar{u}$ and $a_{k}$ (thanks to
properties $(i)$ and $(ii)$ in Remark 2.2). On the other hand, by property
$(iii)$ in Remark 2.2, there is some $\mathrm{ED}_{n}\in\mathcal{A}$ such
that:

$\mathrm{D}=\left\\{w\in\underline{c_{m+1}}:\ulcorner\exists z\
\delta(z,w,\bar{u},a_{k})\urcorner\in\mathrm{ED}_{n}\right\\}.$

Since $(\mathcal{M},\mathcal{A})$ satisfies $\mathrm{I}\Sigma_{1}^{0}$, the
above characterization of $\mathrm{D}$ shows that $\mathrm{D}$ is coded in
$\mathcal{M}$ (and therefore in $\mathcal{N}$) by some $d<2^{c_{m+1}}$ (recall
that the code of each subset of $\underline{m}$ is below $2^{m}).$ Therefore
we have:

(1) $\mathcal{N}\models\forall w<c_{m+1}\left(wEd\rightarrow\exists z\
\delta(z,w,\bar{u},a_{k})\right);$

By putting (1) together with $\mathrm{B}\Sigma_{1}$ in $\mathcal{N}$, and
existentially quantifying $a_{k}$ we obtain:

$(2)$ $\mathcal{N}\models\exists t,x\ \forall
w<c_{m+1}\left(wEd\rightarrow\exists z<t\ \delta(z,w,\bar{u},x)\right).$

On the other hand, coupling (2) with $(\ast_{m})$ yields:

$(3)$ $\mathcal{N}\models\exists t,x<b\ \forall
w<c_{m+1}((wEd\rightarrow\exists z<t\ \delta(z,w,\bar{v},x))),$

which makes it clear that each formula in $p(y)$ is satisfiable in
$\mathcal{N}$.

CASE 1 ($\mathbf{m+1=3k+1}$, for some $\mathbf{k}\in\omega$): In this case if
${b_{k}\geq\mathrm{Max}\\{\bar{v}\\}}$ or if it is one of the elements of
$\bar{v}$, put $u_{m+1}=u_{m}$ and $v_{m+1}=v_{m}$. Otherwise, put
$v_{m+1}=b_{k}$ and define:

$q(x):=\left\\{\forall w<c_{m+1}(\forall z<b\
\lnot\delta(z,w,\bar{v},b_{k})\rightarrow\forall z\
\lnot\delta(z,w,\bar{u},x)):\delta\ \mathrm{is\ a}\
\Delta_{0}\mathrm{-formula}\right\\}.$

$q(x)$ is clearly a recursive type and closed under conjunctions, so by
recursive saturation of $\mathcal{N}$ it suffices to verify that each formula
in $q(x)$ is satisfiable in $\mathcal{N}$, and let $u_{m+1}$ be one of the
realizations of $q(x)$ in $\mathcal{N}$. Suppose some formula in $q$ is not
realizable in $\mathcal{N}$, then for some $\Delta_{0}$-formula $\delta$ we
have:

$\mathcal{N}\models\forall x\left(\exists w<c_{m+1}\left(\forall z<b\
\lnot\delta(z,w,\bar{v},b_{k})\wedge\exists z\
\delta(z,w,\bar{u},x)\right)\right).$

Let:

$\mathrm{R}:=\left\\{w\in\underline{c_{m+1}}:\mathcal{N}\models\forall z<b\
\lnot\delta(z,w,\bar{v},b_{k})\right\\}.$

Since $\mathrm{R}$ is $\Delta_{0}$-definable in $\mathcal{N}$ there exists
some $r<2^{c_{m+1}}$ which codes $\mathrm{R}$ in $\mathcal{N}$. Therefore,

(4) $\mathcal{N}\models\forall
x<\mathrm{\mathrm{Max}}\\{\bar{u}\\}\left(\exists
w<c_{m+1}\left(wEr\wedge\exists z\ \delta(z,w,\bar{u},x)\right)\right),$

which by $\Sigma_{1}$-Collection in $\mathcal{N}$ implies:

(5) $\mathcal{N}\models\exists t\ \forall
x<\mathrm{\mathrm{Max}}\\{\bar{u}\\}\left(\exists
w<c_{m+1}\left(wEr\wedge\exists z<t\ \delta(z,w,\bar{u},x)\right)\right).$

Putting (5) together with $(\ast_{m})$ yields:

$(6)$ $\mathcal{N}\models\exists t<b\ \forall
x<\mathrm{\mathrm{Max}}\\{\bar{v}\\}\left(\exists
w<c_{m+1}\left(wEr\wedge\exists z<t\ \delta(z,w,\bar{v},x)\right)\right).$

By substituting $b_{k}$ for $x$ in (6) we obtain:

(7) $\mathcal{N}\models\exists t<b\ \forall
x<\mathrm{\mathrm{Max}}\\{\bar{v}\\}\left(\exists
w<c_{m+1}\left(wEr\wedge\exists z<t\ \delta(z,w,\bar{v},b_{k})\right)\right).$

But (7) contradicts the assumption that $r$ codes $\mathrm{R}$. So $q(x)$ is
finitely satisfiable.

CASE 2 ($\mathbf{m+1=3k+2}$, for some $\mathbf{k}\in\omega$): Consider the
type $l(x,y):=\left\\{{x\neq y,x\leq c_{k}}\right\\}\cup l_{0}(x,y)$, where:

$l_{0}(x,y):=\left\\{{\forall w<c_{m+1}}\left({\exists z\
\delta(z,w,\bar{u},x)\rightarrow\exists z<b\
\delta(z,w,\bar{v},y)}\right):\delta\ \mathrm{is\ a}\
\Delta_{0}\mathrm{-formula}\right\\}.$

Once we demonstrate that $l(x,y)$ is realized in $\mathcal{N}$ we can define
$(u_{m+1},v_{m+1})$ as any realization in $\mathcal{N}$ of ${l(x,y)}$. Since
$l_{0}(x,y)$ is closed under conjunctions and $\mathcal{N}$ is recursively
saturated, to show that $l(x,y)$ is realized in $\mathcal{N}$ it suffices to
demonstrate that the conjunction of ${x\neq y}$ and ${x\leq c_{k}}$, and each
formula in $l_{0}(x,y)$ is satisfiable in $\mathcal{N}.$ So suppose $\delta$
is a $\Delta_{0}$-formula and for each $s<c_{k}$ consider the map $F$ from
$\underline{c_{k}}$ to the power set of $\underline{c_{m+1}}$ by:

$F(s):={\\{w\in\underline{c_{m+1}}:\ \mathcal{N}\models\exists z\
}$$\delta$${(z,w,\bar{u},s)\\}}.$

Thanks to properties $(i)$ through $(iii)$ of $\mathcal{N}$ listed in Remark
2.2, there is some $\mathrm{ED}_{n}\in\mathcal{A}$ such that:

$F(s)={\\{w\in\underline{c_{m+1}}:\ulcorner\exists z\
}$$\delta$${(z,w,\bar{u},s)\urcorner}\in\mathrm{ED}_{n}{\\}}.$

Since $(\mathcal{M},\mathcal{A})$ satisfies $\mathrm{I}\Sigma_{1}^{0}$, the
above characterization of $F(s)$ together with the veracity of
$\mathrm{I}\Sigma_{1}^{0}$ in $(\mathcal{M},\mathcal{A})$ makes it clear that
$F$ is coded in $\mathcal{M}$ by some $f$ (and therefore in $\mathcal{N}$)
that codes a function from ${\underline{{c_{k}}}}$ to
$\underline{2^{c_{m+1}}}$ with ${f(s):=\sum_{l\in F(s)}2^{l}}.$ On the other
hand the definition of $f(s)$ and the assumption that $2^{c_{n+1}}<c_{n}$ for
all $n\in\omega$ makes it clear that:

$f(s)\leq\sum_{l<c_{m+1}}2^{l}=2^{c_{m+1}}-1<2^{c_{m+1}}<c_{m}<c_{k}$.

So by the coded pigeonhole principle there are distinct ${s,s^{\prime}<c_{k}}$
such that $f(s)=f(s^{\prime})$, in other words:

$\mathcal{N}\models\forall w<c_{m+1}(\exists z\
\delta(z,w,\bar{u},s)\leftrightarrow\exists z\
\delta(z,w,\bar{u},s^{\prime})).$

Now by repeating the argument used in Case 0 for
$\left(\bar{u},s,s^{\prime}\right)$ we can find some $t,t^{\prime}<b$ such
that:

$\mathcal{N}\models\forall w<c_{m+1}(\exists z\
\delta(z,w,\bar{u},s,s^{\prime})\rightarrow\exists z<b\
\delta(z,w,\bar{v},t,t^{\prime})).$

Since $s\neq s^{\prime}$, either $s\neq t$ or $s\neq t^{\prime}$. So the
conjunction of ${x\neq y,}$ ${x\leq c_{k}}$, and each formula in $l_{0}(x,y)$
is satisfiable in $\mathcal{N}$, and the proof is complete. $\square$

##  4 Cuts which are fixed-point sets of self-embeddings

In this section we present the proof of Theorem B. But before going through
the proof, let us point out that a model of $\mathrm{WKL}_{0}$ does not
necessarily carry a cut satisfying statement (2) of Theorem B (see [1, Remark
5.1.1] for an explanation). However, if $\mathcal{M}\models\mathrm{PA}$, there
are arbitrarily high strong cuts $\mathrm{I}$ in $\mathcal{M}$ such that
$\mathrm{I}\prec_{\Sigma_{1}}\mathcal{M}$. To see this when $\mathcal{M}$ is a
countable model of $\mathrm{PA}$, let $\mathcal{A}$ be the family of definable
subsets of $\mathcal{M}$. Since
$(\mathcal{M},\mathcal{A})\models\mathrm{ACA}_{0}$ and $\mathrm{WKL}_{0}$ is a
subsystem of $\mathrm{ACA}_{0}$, by Theorem 1.1 (Tanaka’s theorem), for every
$a\in\mathrm{M}$ there is a cut $\mathrm{I}$ containing $a$ such that
$(\mathcal{M},\mathcal{A})\cong(\mathrm{I},\mathcal{A}_{\mathrm{I}})$ and
$\mathrm{I\prec_{\Sigma_{1}}}\mathcal{M}$. Furthermore, $\mathrm{I}$ is strong
cut of $\mathcal{M}$ by Theorem 2.6 since
$\mathcal{A}_{\mathrm{I}}=\mathrm{SSy}_{\mathrm{I}}(\mathcal{M})$.

Proof of Theorem B. $(1)\Rightarrow(2)$ is an immediate consequence of Theorem
2.4.(b), and $(3)\Rightarrow(1)$ is trivial; so we concentrate on the proof of
$(2)\Rightarrow(3)$.

Suppose $\mathrm{I}$ is a strong cut in $\mathcal{M}$ and
$\mathrm{I}\prec_{\mathrm{end},\ \Sigma_{1}}\mathcal{M}$. The proof of (3) is
inspired by the proof of [1, Theorem 5.1] and consists of the following four
stages:

Stage 1: Fix some $b_{0}\in\mathrm{M}\setminus\mathrm{I}$. Using Theorem 2.1,
let $\mathcal{N}$ be a model of
$\mathrm{I}\Delta_{0}+\mathrm{B}\Sigma_{1}+\mathrm{Exp}$ such that
$\mathrm{SSy}_{\mathrm{M}}(\mathcal{N})=\mathcal{A}$,
$\mathcal{M}\subseteq_{\mathrm{end,\Pi_{1},\leq b_{0}}}\mathcal{N}$, and the
three conditions specified in Remark 2.2 hold for $\mathcal{N}$.

Stage 2: Let $\mathbb{Q}$ be the set of rational numbers with its natural
ordering. Since $\mathrm{I}$ is a strong cut in $\mathcal{M}$, by Theorem 2.6,
and the case $\mathbb{L}=\mathbb{Q}$ of Theorem 2.7, we can find an elementary
end extension $\mathrm{I}_{\mathbb{Q}}$ of $\mathrm{I}$ such that
SSyI($\mathrm{I}_{\mathbb{Q}})=\mathcal{A}$ and
$\mathrm{I}_{\mathbb{Q}}\backslash\mathrm{I}$ contains a copy of
$\mathbb{Q}^{{}^{\prime}}:=\left\\{c_{q}:q\in\mathbb{Q}\right\\}$ of
$\mathbb{Q}$, and there is a composition preserving embedding
$j\mapsto\widehat{j}$ from the semi-group of initial self-embeddings of
$\mathbb{Q}$ into the semi-group of initial self-embeddings of
$\mathrm{I}_{\mathbb{Q}}$ that satisfies conditions (a) through (d) of Theorem
2.7. In particular $\mathbb{Q}^{{}^{\prime}}$ is downward cofinal in
$\mathrm{I}_{\mathbb{Q}}\backslash\mathrm{I.}$

Stage 3: An initial embedding
$k:\mathcal{N}\rightarrow\mathrm{I}_{\mathbb{Q}}$ is constructed such that $k$
fixes each element of $\mathrm{I}$. Note that Theorem 2.5 cannot be invoked
for this purpose since I$\Sigma_{1}$ need not hold in $\mathcal{N}$; instead,
we will take advantage of recursive saturation of $\mathcal{N}$, and the
properties of $\mathcal{N}$ listed in Remark 2.2. We will go through
construction of $k$ after describing stage 4 of the proof.

Stage 4: The desired self-embedding $j$ satisfying (3) of Theorem B can be
readily constructed as follows: Fix some $c_{q_{1}}<k(b_{0})$ in
$\mathbb{Q}^{{}^{\prime}}$ and let $j_{1}$ be a fixed-point free initial
embedding of $\mathbb{Q}$ such that $j_{1}(\mathbb{Q})<q_{1}$. Then define
$h:=k^{-1}\widehat{j_{1}}k$, and let $j$ be the restriction of $h$ to
$\mathcal{M}$. First, note that by the way $j_{1}$ is chosen, $h$ is well-
defined and $h(\mathrm{N})<b_{0}$. Therefore, $j$ is an isomorphism between
$\mathcal{M}$ and a proper cut $\mathrm{J}$ of $\mathcal{M}$. Moreover, Since
$\mathrm{Fix}(\widehat{j_{1}})=\mathrm{I}$ (as arranged in Stage 2) and $k$
fixes each element of $\mathrm{I}$ (as arranged in Stage 3), by Remark 2.3 we
may conclude that $\mathrm{Fix}(j)=\mathrm{I}$ and $j$ is an isomorphism
between $(\mathcal{M},\mathcal{A})$ and
$(\mathrm{J},\mathcal{A}_{\mathrm{J}})$.

The above description of the four stages of the proof should make it clear
that the proof of condition (3) of Theorem B will be complete once we verify
that Stage 3 can be carried out, so we focus on the construction of an initial
embedding $k$ of $\mathcal{N}$ into $\mathrm{I}_{\mathbb{Q}}$ that fixes each
element of $\mathrm{I}$. To do so, we first note that since $(i)$
$\mathrm{I}\Sigma_{1}$ holds in both $\mathcal{M}$ and
$\mathrm{I}_{\mathbb{Q}}$ , $(ii$)
$\mathrm{SSy}_{\mathrm{I}}(\mathcal{M})=\mathrm{SSy}_{\mathrm{I}}(\mathrm{I}_{\mathbb{Q}})$,
and $(iii)$
$\mathrm{Th}_{\Sigma_{1}}(\mathcal{M},i)_{i\in\mathrm{I}}=\mathrm{Th}_{\Sigma_{1}}(\mathcal{N}_{\mathbb{Q}},i)_{i\in\mathrm{I}}$
(because ${\mathrm{I}\prec_{\Sigma_{1}}\mathcal{M}}$, and
${\mathrm{I}}\prec\mathrm{I}_{\mathbb{Q}}$) by Theorem 2.5 there is a proper
initial embedding $f:\mathcal{M}\rightarrow\mathrm{I}_{\mathbb{Q}}$ such that
$f(i)=i$ for each $i\in I$ . In particular, $f(\mathrm{M})<e$ for some
$e\in\mathrm{I}_{\mathbb{Q}}$. Moreover, since
${\mathrm{Th}_{\Pi_{1}}(\mathcal{M},x)_{x\leq
b_{0}}=\mathrm{Th}_{\Pi_{1}}(\mathcal{N},x)_{x\leq b_{0}}}$ we have:

$(\ast_{0}):\ \ \ \mathcal{N}\models\exists z\
\delta(z,w)\Rightarrow\mathrm{I}_{\mathbb{Q}}\models\exists z<e\
\delta(z,f(w))$, for all $\Delta_{0}$-formulas $\delta$ and all $w<b_{0}.$

Now choose $\\{b_{n}:n\in\omega\\}$ to be a decreasing sequence in
$\mathrm{M}\setminus\mathrm{I}$ such that $b_{0}$ is the element chosen in
Stage 1, and $2^{b_{n+1}}<b_{n}$ for all $n\in\omega$. In order to construct
$k$, we recursively build finite sequences $\bar{u}:=(u_{0},...,u_{m})$ of
elements of $\mathrm{N}$ and $\bar{v}:=(v_{0},...,v_{m})<e$ for each
$m\in\omega$ such that:

  * $(i)$

$u_{0}=0=v_{0}$.

  * $(ii)$

For every $c$ in $\mathrm{N}$ there is some $n\in\omega$ such that $c=u_{n}$.

  * $(iii)$

For every $n\in\omega$, $v_{n}<b$, and if for some $c$ in
$\mathrm{I}_{\mathbb{Q}}$ it holds that $c<v_{n}$, then there is some
$m\in\omega$ such that $c=v_{m}$.

  * $(iv)$

For every $m\in\omega$ the following condition holds:

$(\ast_{m}):\ \ $ $\mathcal{N}\models\exists z\
\delta(z,w,\bar{u})\Rightarrow\mathrm{I}_{\mathbb{Q}}\models\exists z<e\
\delta(z,f(w),\bar{v})$ for all $\Delta_{0}$-formulas $\delta$ and all
$w<b_{m}$

Let $\\{a_{n}:n\in\omega\\}$ and $\\{d_{n}:n\in\omega\\}$ respectively be
enumerations of element of $N$ and
$\underline{e}\subset\mathrm{I}_{\mathbb{Q}}$, and
$\langle\delta_{r}:r\in\mathrm{M}\rangle$ be a canonical enumeration of
$\Delta_{0}$-formulas in $\mathcal{M}$. The first step of induction holds
thanks to $(\ast_{0})$ and the choice of $u_{0}$ and $v_{0}$ in statement
$(i)$. Next, suppose $\bar{u}:=(u_{0},...,u_{m})\in\mathrm{N}$ and
$\bar{v}:=(v_{0},...,v_{m})<e$ are constructed, for given $m\in\omega$. In
order to build $u_{m+1}$ and $v_{m+1}$ we distinguish two cases, one handling
the ‘forth’ step and the other handling the ‘back’ step of the back-and-forth
construction:

CASE 0 ($\mathbf{m+1=2k}$, for some $\mathbf{k}\in\omega$): In this case if
$a_{k}$ is one of elements of $\bar{u}$, put $u_{m+1}=u_{m}$ and
$v_{m+1}=v_{m}$. Otherwise, put $u_{m+1}=a_{k}$ and define:

$\mathrm{A}:=\\{\langle r,w\rangle<b_{m+1}:\mathcal{N}\models\exists z\
\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(z,w,\bar{u},a_{k}))\\}.$

Note that in the above definition, $\mathcal{N}$ can be safely replaced by
some $\mathcal{N}_{n}$, where $n$ is large enough to contain the parameters
$\bar{u}$ and $a_{k}$ (thanks to properties $(i)$ and $(ii)$ in Remark 2.2).
On the other hand, by property $(iii)$ in Remark 2.2, there is some
$\mathrm{ED}_{n}\in\mathcal{A}$ such that:

$\mathrm{A}=\left\\{\langle r,w\rangle<b_{m+1}:\ulcorner\exists z\
\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(z,w,\bar{u},a_{k})\urcorner\in\mathrm{ED}_{n}\right\\}.$

Since $(\mathcal{M},\mathcal{A})$ satisfies $\mathrm{I}\Sigma_{1}^{0}$, the
above characterization of $\mathrm{A}$ shows that $\mathrm{A}$ is coded in
$\mathcal{N}$ by some $a<2^{b_{m+1}}.$ Therefore we have:

(1) $\mathcal{N}\models\forall\langle r,w\rangle<b_{m+1}(\langle r,w\rangle
Ea\rightarrow\exists z\
\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(z,w,\bar{u},a_{k}))).$

Recall that $\mathrm{B}\Sigma_{1}$ holds in $\mathcal{N}$, and
$\mathrm{Sat}_{\Delta_{0}}$ has a $\Sigma_{1}$-description in $\mathcal{N},$
so (1) allows us to conclude:

(2) $\mathcal{N}\models\exists t\ \forall\langle r,w\rangle<b_{m+1}(\langle
r,w\rangle Ea\rightarrow\exists z<t\
\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(z,w,\bar{u},a_{k}))).$

By quantifying out $a_{k}$ in (2) and coupling it with $(\ast_{m})$, we
obtain:

(3) $\mathrm{I}_{\mathbb{Q}}\models\exists x,t<e\ \forall\langle
r,w\rangle<f(b_{m+1})\ (\langle r,w\rangle Ef(a)\rightarrow\exists z<t\
\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(z,w,\bar{v},x))).$

Clearly any element of $\mathrm{I}_{\mathbb{Q}}$ that witnesses $x$ in (3) can
serve as a suitable candidate for $v_{m+1}$.

CASE 1 ($\mathbf{m+1=2k+1}$, for some $\mathbf{k}\in\omega$): In this case if
${d_{k}\geq\mathrm{Max}\\{\bar{v}\\}}$ or if it is one of the elements of
$\bar{v}$, put $u_{m+1}=u_{m}$ and $v_{m+1}=v_{m}$. Otherwise, put
$v_{m+1}=b_{k}$ and define:

$\mathrm{B}:=\\{\langle
r,w\rangle<f(b_{m+1}):\mathrm{I}_{\mathbb{Q}}\models\forall
z(\mathrm{Sat}_{\Delta_{0}}(\delta_{r}(z,w,\bar{v},d_{k}))\rightarrow
b<z)\\}$.

Note that $\mathrm{B}$ is $\Sigma_{1}$-definable in $\mathrm{I}_{\mathbb{Q}}$,
so there is some $b<2^{f(b_{m+1})}=f(2^{b_{m+1}})$ which codes $\mathrm{B}$ in
$\mathrm{I}_{\mathbb{Q}}$. Therefore $b=f(c)$ for some $c<2^{b_{m+1}}$.
Define:

$p(x):=\\{\forall w<b_{m+1}(\langle\ulcorner\delta\urcorner,w\rangle
Ec\rightarrow\forall z\ \lnot\delta(z,w,\bar{u},x)):\delta\ \mathrm{is\ a}\
\Delta_{0}\mathrm{-formula}\\}$.

Since $\mathcal{N}$ is recursively saturated and $p(x)$ is recursive, in order
to find a suitable element in $\mathrm{N}$ which serves as $u_{m+1}$ , it
suffices to prove that $p(x)$ is finitely satisfiable. So suppose $p(x)$ is
not finitely satisfiable. It can be readily checked that $p(x)$ is closed
under conjunction, so we can safely assume there is a $\Delta_{0}$-formula
$\delta$ such that:

(4) $\mathcal{N}\models\forall x(\exists
w<b_{m+1}(\langle\ulcorner\delta\urcorner,w\rangle Ec\wedge\exists z\
\delta(z,w,\bar{u},x))).$

Clearly (4) implies:

(5) $\mathcal{N}\models\forall x<\mathrm{\mathrm{Max}}\\{\bar{u}\\}\ (\exists
w<b_{m+1}(\langle\ulcorner\delta\urcorner,w\rangle Ec\wedge\exists z\
\delta(z,w,\bar{u},x))).$

We can bound variable $z$ in (5) by using $\mathrm{B}\Sigma_{1}$ in
$\mathcal{N}$, and next employ $(\ast_{m})$ to deduce:

(6) $\mathrm{I}_{\mathbb{Q}}\models{\exists t<e\forall
x<\mathrm{\mathrm{Max}}\\{\bar{v}\\}(\exists
w<f(b_{m+1})(\langle\ulcorner\delta\urcorner,w\rangle Ef(c)\wedge\exists z<t\
\delta(z,w,\bar{v},x)))}.$

By replacing $x$ in (6) with $d_{k}$, we obtain:

(7) $\mathrm{I}_{\mathbb{Q}}\models\exists t<e\ (\exists
w<f(b_{m+1})(\langle\ulcorner\delta\urcorner,w\rangle Eb\wedge\exists z<t\
\delta(z,w,\bar{v},d_{k}))).$

But (7) contradicts the assumption that $b$ codes $\mathrm{B}$ in
$\mathrm{I}_{\mathbb{Q}}$. So $p(x)$ is finitely satisfiable. $\square$

## 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] C. Dimitracopoulos and J. Paris, A note on a theorem of H. Friedman, Math. Logic Quart. 34, 1988, pp. 13-17.
  * [3] A. Enayat, A new proof of Tanaka’s theorem, in New Studies in Weak Arithmetics, CSLI Lectures Notes 11, 2014, pp. 93-102.
  * [4] H. Friedman, Countable models of set theories, Lecture Notes in Math. 337, Springer, Berlin, 1973, pp. 539-573.
  * [5] H. Friedman, Some systems of second-order arithmetic and their use, Proceedings of the International Congress of Mathematicians, 1974, volume 1, pp. 235-242.
  * [6] H. Gaifman, Models and types of arithmetic, Ann. Math. Logic 9 (1976), pp. 223-306.
  * [7] P. Hájek and P. Pudlák, Two orderings of the class of all countable models of Peano arithmetic, Model theory of algebra and arithmetic, Lecture Notes in Math. 834, 1980, pp. 174-185.
  * [8] Y. Horihata and K. Yokoyama, Nonstandard second-order arithmetic and Riemann’s mapping theorem, Ann. Pure Appl. Logic vol. 165, 2014, pp. 520-551.
  * [9] J. Paris and L. Kirby, $\Sigma_{n}$-collection schemas in arithmetic, in Logic Colloquium ’77, North-Holland Publishing Company, Amsterdam, 1978, pp. 199-209.
  * [10] J.-P. Ressayre, Nonstandard universes with strong embeddings, and their finite approximations, Logic and combinatorics, Contemp. Math. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 333-358.
  * [11] N. Sakamoto and K. Yokoyama, The Jordan curve theorem and the Schönflies theorem in weak second-order arithmetic, Arch. Math. Logic 46, 2007, pp. 465-480.
  * [12] C. Smoryński,, Recursively saturated nonstandard models of arithmetic, J. Symb. Logic 46 (1981), pp. 259-286.
  * [13] K. Tanaka, The self-embedding theorem of $\mathrm{WKL}_{0}$ and a non-standard method, Ann. Pure Appl. Logic vol. 84 1997, pp. 41-49.
  * [14] K. Tanaka and T. Yamazaki, A non-Standard vonstruction of Haar Measure and weak König’s lemma, J. Symb. Logic, vol. 65, 2000, pp. 173-186.