# Conservation of Ramsey’s theorem for pairs
and well-foundedness

Quentin Le Houérou  Ludovic Levy Patey  Keita Yokoyama

###### Abstract

In this article, we prove that Ramsey’s theorem for pairs and two colors is
$\Pi^{1}_{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$ and over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\bigcup_{n}\mathsf{WF}(\omega^{\omega}_{n})$.
These results improve theorems from Chong, Slaman and Yang [6] and
Kołodziejczyk and Yokoyama [20] and belong to a long line of research towards
the characterization of the first-order part of Ramsey’s theorem for pairs.

##  1 Introduction

We investigate the proof-theoretic strength of Ramsey’s theorem for pairs and
some of its consequences, by proving that they are $\Pi^{1}_{1}$-conservative
over the base theory of Reverse Mathematics ($\mathsf{RCA}_{0}$), augmented
with the collection principle for $\Sigma^{0}_{2}$ formulas
($\mathsf{B}\Sigma^{0}_{2}$) and the assumption that some appropriate ordinals
are well-founded ($\mathsf{WF}(\alpha)$). This article belongs to a long line
of research towards the characterization of the first-order part of Ramsey’s
theorem for pairs, and is part of a larger foundational program known as
Reverse Mathematics, and whose goal is to find optimal axioms for proving
ordinary theorems. See Simpson [30] or Dzhafarov and Mummert [7] for a
reference book on Reverse Mathematics, and Hirschfeldt [8] to a gentle
introduction to the reverse mathematics of combinatorial principles.

Ramsey’s theorem is the founding theorem of Ramsey’s theory, a field of
research which studies the conditions under which structure appears among a
sufficiently large amount of data. We identify a set $k$ with its ordinal
$\\{0,1,\dots,k-1\\}$. Given a set $X\subseteq\mathbb{N}$ and some integer
$n\in\mathbb{N}$, we let $[X]^{n}$ denote the set of all unordered $n$-tuples
over $X$. Given a coloring $f:[\mathbb{N}]^{n}\to k$, a set
$H\subseteq\mathbb{N}$ is _$f$ -homogeneous (for color $i<k$)_ if
$f(\sigma)=i$ for every $\sigma\in[\mathbb{N}]^{n}$.

######  Statement 1.1 (Ramsey’s theorem).

Given $n,k\in\mathbb{N}$, $\mathsf{RT}^{n}_{k}$ is the statement “Every
coloring $f:[\mathbb{N}]^{n}\to k$ admits an infinite $f$-homogeneous set”.

The proof-theoretic strength of Ramsey’s theorem for triples and larger size
of tuples is well-understood: $\mathsf{RT}^{n}_{k}$ is equivalent to the
Arithmetic Comprehension Axiom ($\mathsf{ACA}_{0}$) over $\mathsf{RCA}_{0}$
whenever $n\geq 3$ and $k\geq 2$ (see Jockusch [18] for a computability-
theoretic equivalence, and Simpson [30, Theorem III.7.6] for a proof-theoretic
version of it). The first-order part of $\mathsf{ACA}_{0}$ is precisely Peano
Arithmetic.

Ramsey’s theorem for pairs and two colors ($\mathsf{RT}^{2}_{2}$) can be
phrased as stating, for every infinite graph, the existence of an infinite
subset of vertices such that the induced subgraph is either a clique or an
anticlique. $\mathsf{RT}^{2}_{2}$ is known to be strictly weaker than
$\mathsf{ACA}_{0}$ over $\mathsf{RCA}_{0}$ (see Seetapun and Slaman [29]), and
incomparable with weak König’s lemma ($\mathsf{WKL}_{0}$), the restriction of
König’s lemma to binary trees (see Liu [24]). The characterization of the
first-order part of Ramsey’s theorem for pairs and two colors is a long-
standing open question.

######  Definition 1.2 (Collection principle).

Given a family $\Gamma$ of formulas, $\mathsf{B}\Gamma$ is the statement “For
every formula $\varphi\in\Gamma$, and every $a\in\mathbb{N}$, if $\forall
x<a\exists y\varphi(x,y)$, then there is some $b\in\mathbb{N}$ such that
$\forall x<a\exists y<b\varphi(x,y)$”.

Ramsey’s theorem for pairs implies $\mathsf{B}\Sigma^{0}_{2}$ over
$\mathsf{RCA}_{0}$ (see Hirst [16]). The following question is a major open
problem in Reverse Mathematics:

######  Question 1.3.

Is $\mathsf{RT}^{2}_{2}$ a $\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$?

###  1.1 Well-foundedness and bounded monotone enumerations

In Computability Theory, the ability to compute fast-growing functions can be
seen as a unified framework to measure the strength of some Turing degrees,
e.g., hyperimmune degrees, high degrees, and degrees admitting a modulus. In
Proof Theory, the strength of a theory is better measured by the ability to
prove the well-foundedness of some ordinals. The _$\Pi^{1}_{1}$ proof-
theoretic ordinal_ of a theory $T$ is the least ordinal $\alpha$ such that $T$
does not prove its well-foundedness ($\mathsf{WF}(\alpha)$). For instance, the
$\Pi^{1}_{1}$ proof-theoretic ordinals of $\mathsf{RCA}_{0}$ and
$\mathsf{ACA}_{0}$ are $\omega^{\omega}$ and $\epsilon_{0}$, respectively (see
Simpson [30]).

The well-foundedness of ordinals naturally occured in the proof-theoretic
analysis of Ramsey’s theorem for pairs. Chong, Slaman and Yang [6] proved that
$\mathsf{RT}^{2}_{2}$ does not imply the induction scheme for $\Sigma^{0}_{2}$
formulas ($\mathsf{I}\Sigma^{0}_{2}$) over $\mathsf{RCA}_{0}$ using a model of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\neg\mathsf{I}\Sigma^{0}_{2}$ which
furthermore satisfied a principle called Bounded Monotone Enumeration
($\mathsf{BME}$).

######  Definition 1.4 ([6]).

Let $E$ be a procedure to recursively enumerate a finite branching enumerable
tree. We say that $E$ is a _monotone enumeration_ if and only if the following
conditions apply to its stage-by-stage behavior.

  1. (1)

The empty sequence is enumerated by E during stage 0.

  2. (2)

Only finitely many sequences are enumerated by $E$ during any stage.

  3. (3)

Suppose $T[s]$ is the tree enumerated by $E$ at the end of stage $s$. Then any
sequence enumerated by $E$ during stage $s+1$ must extend some terminal node
of $T[s]$.

A monotone enumeration $E$ is _$b$ -bounded_ if every node in $E$ has length
at most $b$.

######  Statement 1.5.

$\mathsf{BME}_{\star}$ is the statement “Every bounded monotone enumeration is
finite”.

The statement $\mathsf{BME}$ is an iterated version of $\mathsf{BME}_{\star}$.
Its formal definition is rather technical and will not be used within this
article. Kreuzer and Yokoyama [22] proved that $\mathsf{BME}_{\star}$ is
equivalent to $\mathsf{WF}(\omega^{\omega})$ over $\mathsf{I}\Sigma^{0}_{1}$,
and that $\mathsf{BME}$ is equivalent to
$\bigcup_{k}\mathsf{WF}(\omega^{\omega}_{k})$, where
$\omega^{\alpha}_{0}=\alpha$ and
$\omega^{\alpha}_{k+1}=\omega^{\omega_{k}^{\alpha}}$.

The principles $\mathsf{BME}$ and $\mathsf{BME}_{\star}$ naturally occur in
the proofs of conservation of Ramsey’s theorem for pairs. On the other hand,
Patey and Yokoyama [28] proved that $\mathsf{RT}^{2}_{2}$ is
$\forall\Pi^{0}_{3}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$, which implies in particular that
the $\Pi^{1}_{1}$ proof-theoretic ordinal of $\mathsf{RT}^{2}_{2}$ is
$\omega^{\omega}$, hence that $\mathsf{RT}^{2}_{2}$ does not imply
$\mathsf{BME}_{\star}$ over $\mathsf{RCA}_{0}$.

In this article, we show that the separation of Chong, Slaman and Yang [6] of
$\mathsf{RT}^{2}_{2}$ from $\mathsf{I}\Sigma^{0}_{2}$ only depends on the
assumption that the original model satisfies
$\mathsf{B}\Sigma^{0}_{2}+\mathsf{BME}$, by proving the following conservation
theorems.

######  Main Theorem 1.6.

Fix $n\geq 2$. Let $T_{n}$ be either $\mathsf{B}\Sigma^{0}_{n}$ or
$\mathsf{I}\Sigma^{0}_{n}$.
$\mathsf{RCA}_{0}+T_{n}+\mathsf{RT}^{2}_{2}+\mathsf{WKL}+\mathsf{WF}(\epsilon_{0})$
is a $\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\epsilon_{0})$.

######  Main Theorem 1.7.

Fix $n\geq 2$. Let $T_{n}$ be either $\mathsf{B}\Sigma^{0}_{n}$ or
$\mathsf{I}\Sigma^{0}_{n}$.
$\mathsf{RCA}_{0}+T_{n}+\mathsf{RT}^{2}_{2}+\mathsf{WKL}+\bigcup_{k\in\omega}\mathsf{WF}(\omega^{\omega}_{k})$
is a $\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+T_{n}+\bigcup_{k\in\omega}\mathsf{WF}(\omega^{\omega}_{k})$.

This strengthens a result from Kołodziejczyk and Yokoyama [20] who showed that
$\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}+\mathsf{BME}$ is a
$\Pi^{0}_{4}$-conservative extension of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{BME}$. By Cholak, Jockusch
and Slaman [3], the result holds when
$\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$ is replaced by
$\mathsf{I}\Sigma^{0}_{2}$. Thus, conservations over
$\mathsf{RCA}_{0}+(\mathsf{WF}(\epsilon_{0})\vee\mathsf{I}\Sigma^{0}_{2})$ and
over
$\mathsf{RCA}_{0}+(\bigcup_{n\in\omega}\mathsf{WF}(\omega^{\omega}_{n})\vee\mathsf{I}\Sigma^{0}_{2})$
are the best known results.

In order to better understand the computational and proof-theoretic content of
Ramsey’s theorem for pairs, two main decompositions of $\mathsf{RT}^{2}_{2}$
into combinatorially weaker statements have been studied. These decompositions
will be used to prove separate conservation theorems for simpler statements,
and then combined to obtain our main theorems. We now detail those statements.

###  1.2 Tournaments and linear orders

Ramsey’s theorem for pairs and two colors can be decomposed into the Erdős-
Moser theorem about infinite tournaments, and the Ascending Descending
Sequence principle.

######  Definition 1.8.

A _tournament_ on a domain $D$ is an irreflexive binary relation $R\subseteq
D^{2}$ such that for every $a,b\in D$ with $a\neq b$, exactly one of $R(a,b)$
and $R(b,a)$ holds. A tournament $R$ is _transitive_ if for every $a,b,c\in
D$, if $R(a,b)$ and $R(b,c)$ then $R(a,c)$.

A subtournament of $R\subseteq\mathbb{N}^{2}$ is fully characterized by its
domain and the parent tournament $R$. We therefore identify subtournaments
with infinite sets $H\subseteq\mathbb{N}$. The following statement is known as
the Erdős-Moser theorem, and is an infinitary version of some theorem by Erdős
and Moser [9].

######  Statement 1.9 (Erdős-Moser).

$\mathsf{EM}$ is the statement “Every infinite tournament admits an infinite
transitive subtournament”.

There exists a one-to-one correspondence between a tournament $R$ and a
coloring $f:[\mathbb{N}]^{2}\to 2$, by letting $f(\\{x,y\\})=1$ if
$(R(x,y)\leftrightarrow x<_{\mathbb{N}}y)$. $\mathsf{EM}$ can the restated as
“for every coloring $f:[\mathbb{N}]^{2}\to 2$, there exists an infinite _$f$
-transitive_ subset $H$, that is, for every $x,y,z\in H$ such that $x<y<z$ and
every $i<2$, then if $f(\\{x,y\\})=f(\\{y,z\\})=i$, we have $f(\\{x,z\\})=i$”.

######  Statement 1.10 (Ascending Descending Sequence).

$\mathsf{ADS}$ is the statement “Every infinite linear order admits an
infinite ascending or descending subsequence”.

Here again, there is a one-to-one correspondence between linear orders
$\mathcal{L}=(\omega,<_{\mathcal{L}})$, and transitive colorings
$f:[\mathbb{N}]^{2}\to 2$, by letting $f(\\{x,y\\})=1$ if
$(x<_{\mathbb{N}}y\leftrightarrow x<_{\mathcal{L}}y)$. Then $\mathsf{ADS}$ can
be restated as “for every transitive coloring $f:[\mathbb{N}]^{2}\to 2$, there
exists an infinite $f$-homogeneous set”. Using the reformulations of
$\mathsf{EM}$ and $\mathsf{ADS}$, the following proposition is immediate:

######  Proposition 1.11 (Bovyking and Weiermann [2]).

$\mathsf{RCA}_{0}\vdash\mathsf{RT}^{2}_{2}\leftrightarrow\mathsf{EM}\wedge\mathsf{ADS}$

###### Proof.

$\mathsf{EM}$ and $\mathsf{ADS}$ are both particular cases of
$\mathsf{RT}^{2}_{2}$, hence
$\mathsf{RCA}_{0}\vdash\mathsf{RT}^{2}_{2}\rightarrow\mathsf{EM}\wedge\mathsf{ADS}$.
On the other hand, given a coloring $f:[\mathbb{N}]^{2}\to 2$, first apply
$\mathsf{EM}$ to obtain an infinite $f$-transitive subset
$X=\\{x_{0}<x_{1}<\dots\\}$. Let $g:[\mathbb{N}]^{2}\to 2$ be the transitive
coloring defined by $g(a,b)=f(x_{a},x_{b})$. By $\mathsf{ADS}$, there exists
an infinite $g$-homogeneous subset $H\subseteq\mathbb{N}$. The set
$\\{x_{a}:a\in H\\}$ is infinite and $f$-homogeneous. ∎

From a combinatorial viewpoint, the decomposition of $\mathsf{RT}^{2}_{2}$
into $\mathsf{EM}$ and $\mathsf{ADS}$ divides the difficulty of Ramsey’s
theorem for pairs as follows: the combinatorics of $\mathsf{EM}$ are very
close to those of $\mathsf{RT}^{2}_{2}$, but without the disjunctive nature of
$\mathsf{RT}^{2}_{2}$. Thus, there is no need to work with pairing arguments.
On the other hand, $\mathsf{ADS}$ has very simple combinatorics, and does not
imply any form of compactness, but is a disjunctive statement.

From a reverse mathematical viewpoint, the decomposition is non-trivial, in
that $\mathsf{EM}$ and $\mathsf{ADS}$ are both strictly weaker than
$\mathsf{RT}^{2}_{2}$ (see Lerman, Solomon and Towsner [23]).

From a proof-theoretic viewpoint, both statements imply
$\mathsf{B}\Sigma^{0}_{2}$ over $\mathsf{RCA}_{0}$ (see Hirschfeldt and Shore
[15, Proposition 4.5] and Kreuzer [21, Proposition 16]), and
$\mathsf{RCA}_{0}+\mathsf{ADS}$ is known to be $\Pi^{1}_{1}$-conservative
extension of $\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$ (see Chong, Slaman
and Yang [5]). By an amalgamation theorem of Yokoyama [33], it follows that
$\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}$ is $\Pi^{1}_{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$ iff so is
$\mathsf{RCA}_{0}+\mathsf{EM}$.

###  1.3 Cohesiveness and stability

The second (and historically the first) decomposition of $\mathsf{RT}^{2}_{2}$
was done by Cholak, Jockusch and Slaman [3] in their seminal article on
Ramsey’s theorem for pairs. It consists in reducing $\mathsf{RT}^{2}_{2}$ to a
stable version of it ($\mathsf{SRT}^{2}_{2}$), using the Cohesiveness
principle ($\mathsf{COH}$). Then, it is easy to see that
$\mathsf{SRT}^{2}_{2}$ is equivalent to the infinite pigeonhole principle for
$\Delta^{0}_{2}$ instances, which is a combinatorialy simple statement.

######  Definition 1.12.

A coloring $f:[\mathbb{N}]^{2}\to k$ is _stable_ if for every
$x\in\mathbb{N}$, $\lim_{y}f(x,y)$ exists. Given an infinite sequence of sets
$\vec{R}=R_{0},R_{1},\dots$, an infinite set $C$ is _$\vec{R}$ -cohesive_ if
for every $s\in\mathbb{N}$, $C\subseteq^{*}R_{s}$ or
$C\subseteq^{*}\overline{R}_{s}$, where $\subseteq^{*}$ denotes inclusion up
to finite changes.

######  Statement 1.13 (Stable Ramsey’s theorem for pairs).

$\mathsf{SRT}^{2}_{k}$ denotes the restriction of $\mathsf{RT}^{2}_{k}$ to
stable colorings.

######  Statement 1.14 (Cohesiveness).

$\mathsf{COH}$ is the statement “Every infinite sequence of sets has a
cohesive set”.

The following equivalence is essentially due to Cholak, Jockusch and Slaman
[3], with the proof $\mathsf{RCA}_{0}\vdash\mathsf{RT}^{2}_{2}\to\mathsf{COH}$
fixed by Mileti [25, Appendix A].

######  Proposition 1.15.

$\mathsf{RCA}_{0}\vdash\mathsf{RT}^{2}_{2}\leftrightarrow\mathsf{SRT}^{2}_{2}\wedge\mathsf{COH}$.

###### Proof.

The proof of the forward direction will be omitted, as it will be of no use in
the article. Let us prove that
$\mathsf{RCA}_{0}\vdash\mathsf{SRT}^{2}_{2}\wedge\mathsf{COH}\to\mathsf{RT}^{2}_{2}$.
Given a coloring $f:[\mathbb{N}]^{2}\to 2$, define the sequence of sets
$\vec{R}=R_{0},R_{1},\dots$ by $R_{x}=\\{y:f(x,y)=1\\}$. Given an infinite
$\vec{R}$-cohesive set $C=\\{x_{0}<x_{1}<\dots\\}$, let $g:[\mathbb{N}]^{2}\to
2$ be defined by $g(\\{a,b\\})=f(\\{x_{a},x_{b}\\})$. By cohesiveness of $C$,
the coloring $g$ is stable, so by $\mathsf{SRT}^{2}_{2}$, there is an infinite
$g$-homogeneous set $H$. The set $\\{x_{a}:a\in H\\}$ is infinite and
$f$-homogeneous. ∎

From a reverse mathematical viewpoint, the decomposition of
$\mathsf{RT}^{2}_{2}$ into $\mathsf{SRT}^{2}_{2}$ and $\mathsf{COH}$ is also
non-trivial (see Hirschfeldt et al. [14] and Monin and Patey [26]).

The computability-theoretic content of the cohesiveness principle is well-
understood: it admits a maximally complex instance, which is the sequence of
all primitive recursive sets. A cohesive set for this sequence is called _p-
cohesive_. For every uniformly computable sequence of sets $\vec{R}$, every
$p$-cohesive set computes an $\vec{R}$-cohesive set. Moreover, a Turing degree
bounds a p-cohesive set iff its jump is PA over $\mathsf{0}^{\prime}$. See
Jockusch and Stephan [17].

The idea of using cohesiveness to transform a coloring into a stable one can
be applied to $\mathsf{EM}$ and $\mathsf{ADS}$. We call $\mathsf{SEM}$ and
$\mathsf{SADS}$ the restriction of $\mathsf{EM}$ and $\mathsf{ADS}$ to stable
tournaments and linear orders, respectively. Stable linear orders can be of
three types: $\omega+\omega^{*}$, $\omega+k$ and $k+\omega^{*}$, for some
$k\in\omega$. The two former cases are computably true, so the only
interesting case if whenever it is of order type $\omega+\omega^{*}$. This is
why $\mathsf{SADS}$ is often defined as the statement “Every linear order of
type $\omega+\omega^{*}$ admits an infinite ascending or descending sequence”.

Combining the two kind of decompositions, we shall use the following
equivalence:

######  Proposition 1.16.

$\mathsf{RCA}_{0}\vdash\mathsf{RT}^{2}_{2}\leftrightarrow\mathsf{SEM}\wedge\mathsf{SADS}\wedge\mathsf{COH}$

We will therefore prove conservation results about
$\mathsf{WKL},\mathsf{COH},\mathsf{SEM}$ and $\mathsf{SADS}$ independently,
and use the previous decomposition to obtain our main theorems.

###  1.4 Definitions and notation

Since $[X]^{n}$ is in one-to-one correspondence with the set of all $n$-tuples
in increasing order, given a coloring $f:[\mathbb{N}]^{n}\to k$, we might omit
the brackets, and simply write $f(x_{0},x_{1},\dots,x_{n-1})$ instead of
$f(\\{x_{0},x_{1},\dots,x_{n-1}\\})$, assuming that $x_{0}<\dots<x_{n-1}$.

A _$\Pi^{1}_{2}$ problem_ $\mathsf{P}$ is a formula $\forall
X[\varphi(X)\rightarrow\psi(X,Y)]$ where $\varphi$ and $\psi$ are arithmetic
formulas. A set $X$ such that $\varphi(X)$ holds is a _$\mathsf{P}$
-instance_, and a $Y$ such that $\psi(X,Y)$ holds is a _$\mathsf{P}$
-solution_ to $X$.

Theories. Let $\mathsf{I}\Sigma^{0}_{n}$ be the following induction scheme for
every $\Sigma^{0}_{n}$ formula $\phi$:

$\phi(0)\wedge\forall x[\phi(x)\rightarrow\phi(x+1)]\rightarrow\forall
x\phi(x)$

Let $\Delta^{0}_{n}$-$\mathsf{CA}$ be the following comprehension scheme for
every $\Sigma^{0}_{n}$ formula $\phi$ and every $\Pi^{0}_{n}$ formula $\psi$:

$\forall x[\phi(x)\leftrightarrow\psi(x)]\rightarrow\exists A\forall x[x\in
A\leftrightarrow\phi(x)]$

$\mathsf{RCA}_{0}^{*}$ denotes the theory of Robinson arithmetic ($Q$)
augmented with the comprehension axiom for $\Delta^{0}_{1}$ predicates
($\Delta^{0}_{1}$-$\mathsf{CA}$), the collection scheme for $\Sigma^{0}_{1}$
formulas ($\mathsf{B}\Sigma^{0}_{1}$) and the totality of the exponentiation
function ($\mathsf{exp}$). $\mathsf{RCA}_{0}$ is the theory of
$Q+\Delta^{0}_{1}\mbox{-}\mathsf{CA}+\mathsf{I}\Sigma^{0}_{1}$. Note that
$\mathsf{RCA}_{0}$ entails $\mathsf{RCA}_{0}^{*}$. The theory
$\mathsf{RCA}_{0}$ is the base theory of Reverse Mathematics, but
$\mathsf{RCA}_{0}^{*}$ is sometimes more convenient to use, as shown by
Belanger [1].

Models. A _model_ is a second-order structure
$\mathcal{M}=(M,S,+_{M},\times_{M},<_{M})$, where $M$ is the first-order part,
that is, the set of integers and $S\subseteq\mathcal{P}(M)$ is the second-
order part. We will usually omit the operations, and simply write
$\mathcal{M}=(M,S)$. A model $\mathcal{M}=(M,S)$ is _topped_ if there is some
set $X\in S$ such that every $Y\in S$ is $\Delta^{0}_{1}(X)$. A model
$\mathcal{N}=(N,T)$ is an _$\omega$ -submodel_ of $\mathcal{M}=(M,S)$ if $N=M$
and $T\subseteq S$. Note that the notion of $\omega$-submodel must not be
confused with the notion of $\omega$-model, in which $M=\omega$, that is, is
the set of all standard integers.

Given a model $\mathcal{M}=(M,S)$ and a set $G\subseteq M$, we write
$\mathcal{M}[G]$ for the model whose first-order part is $M$, and whose
second-order part consists of all $\Delta^{0}_{1}(X,G)$ sets for $X\in S$.
Therefore, if $\mathcal{M}\models\mathsf{RCA}_{0}$, and
$\mathcal{M}\cup\\{G\\}\models\mathsf{I}\Sigma^{0}_{1}$, then
$\mathcal{M}[G]\models\mathsf{RCA}_{0}$.

A set $X$ is _$M$ -bounded_ if there is some $x\in M$ such that $\forall y\in
X,\ y\leq x$. A set $X$ is _$M$ -finite_ or _$M$ -coded_ if there exists some
$x\in M$ such that $x=\sum_{n\in X}2^{n}$.

Given two sets $X$ and $Y$, we write $X\gg Y$ to say that $X$ is of PA degree
over $Y$. More formally, it means that $\Delta^{0}_{1}(Y)$ infinite binary
tree admits a $\Delta^{0}_{1}(X)$ path.

Ordinals. In this article, we shall work with ordinals smaller than
$\epsilon_{0}$ in models of weak arithmetic. By Cantor’s normal form theorem,
every ordinal $\alpha$ below $\epsilon_{0}$ can be written uniquely as
$\alpha=\omega^{\gamma_{1}}n_{1}+\dots+\omega^{\gamma_{k}}n_{k}$ for some
ordinals $\gamma_{k}<\dots<\gamma_{1}<\alpha$ and positive integers
$n_{1},\dots,n_{k}$. So, every such ordinal can be represented as a finite
rooted tree and therefore be coded by an integer which will be called its
”index”. For a suitable encoding of the finite rooted trees, the cantor normal
form of any ordinal below $\epsilon_{0}$ and the standard operations on
ordinals (sums, product, comparaison) are computable from their indexes. See
Hájek and Pudlák [13, Chapter II.3] for a formal study of ordinals in the
context of weak arithmetic.

###  1.5 Structure of the paper

In Section 2, we develop some basic techniques about
$\Pi^{1}_{1}$-conservation over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$. We prove in
particular that
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)+\Gamma$ is a
$\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$ for
$\Gamma\in\\{\mathsf{COH},\mathsf{WKL}\\}$ and $\alpha$ any primitive
recursive ordinal.

In Section 3, we handle the case of $\mathsf{SADS}$ and $\mathsf{SEM}$ which
does not admit such a direct preservation of well-foundedness. In these cases,
one needs to assume $\mathsf{WF}(\omega^{\alpha\dottimes\omega})$ to obtain an
$\omega$-extension satisfying $\mathsf{WF}(\alpha)$, where
$\alpha\leq\epsilon_{0}$. We prove in particular that
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})+\Gamma$
is a $\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$ for
$\Gamma\in\\{\mathsf{SADS},\mathsf{SEM}\\}$.

In Section 4, we combine the previous conservation theorems to obtain our main
theorems. Last, in Section 5, we state some remaining open questions.

##  2 Conservation over $\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$

In this section, we introduce the framework for preserving
$\mathsf{WF}(\alpha)$ for an ordinal $\alpha\leq\epsilon_{0}$ over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$. We then prove that
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)+\mathsf{WKL}$
and
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)+\mathsf{COH}$
are both $\Pi^{1}_{1}$-conservative extensions of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

The proofs of conservation will all follow the same pattern: Given a countable
topped model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$,
and an instance $I\in S$ of our problem $\mathsf{P}$, we will show the
existence of a $\mathsf{P}$-solution $G\subseteq M$ of $I$ such that
$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.
Then, the conservation result follows from a standard argument that we give
for the sake of completeness:

######  Definition 2.1.

A _$\Pi^{1}_{2}$ -problem_ $\mathsf{P}$ is a statement of the form $\forall
X\Phi(X)\rightarrow\exists Y\Psi(X,Y)$ for some arithmetical formulas $\Phi$
and $\Psi$. A _$\mathsf{P}$ -instance_ is a set $X$ such that $\Phi(X)$ holds.
A _$\mathsf{P}$ -solution_ of a $\mathsf{P}$-instance $X$ is a set $Y$ such
that $\Psi(X,Y)$ holds.

In particular, $\mathsf{RT}^{2}_{2}$, $\mathsf{EM}$ and $\mathsf{ADS}$ are
$\Pi^{1}_{2}$-problems. For example, an $\mathsf{RT}^{2}_{2}$-instance is a
coloring $f:[\mathbb{N}]^{2}\to 2$ and an $\mathsf{RT}^{2}_{2}$-solution to
$f$ is an infinite $f$-homogeneous set.

######  Theorem 2.2.

Let $\mathsf{P}$ be a $\Pi_{2}^{1}$ problem and $\alpha\leq\epsilon_{0}$ be an
ordinal such that for every countable topped model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$
and for every $\mathsf{P}$-instance $I\in\mathcal{M}$, there exists a
$\mathsf{P}$-solution $G\subset M$ of $I$ such that
$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.
Then
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)+\mathsf{P}$ is
$\Pi_{1}^{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

###### Proof.

Assume
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)\not\vdash\forall
X\phi(X)$ for $\phi$ an arithmetic formula. Then by the completeness theorem
and the downward Löwenheim–Skolem theorem, there is a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)+\neg\phi(A)$
with $A\in S$. We can furthermore assume that $\mathcal{M}$ is topped by $A$.

From our assumption, we can build a sequence
$\mathcal{M}=\mathcal{M}_{0}\subseteq\mathcal{M}_{1}=(M,S_{1})\subseteq\mathcal{M}_{2}=(M,S_{2})\subseteq\dots$
of countable topped model of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$ such that
every $\mathsf{P}$-instance appearing in one of the $\mathcal{M}_{i}$ will
eventually have a solution in one $\mathcal{M}_{j}$. Then
$\bigcup_{n<\omega}\mathcal{M}_{n}$ is a model of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)+\mathsf{P}+\neg\phi(A)$.
So
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)+\mathsf{P}\not\vdash\forall
X\phi(X)$. ∎

###  2.1 Conservation over $\mathsf{B}\Sigma^{0}_{2}$

There exist two main methods for extending a model $\mathcal{M}$ into a model
$\mathcal{M}[G]$: by external forcing, and by an internal construction. In the
case of conservation theorems over
$\mathsf{B}\Sigma^{0}_{2}+\neg\mathsf{I}\Sigma^{0}_{2}$, one arguably needs to
use an internal construction. Indeed, using an isomorphism theorem for
$\mathsf{WKL}^{*}_{0}$, Fiori-Carones et al [11] proved that
$\Pi^{1}_{1}$-conservation of any $\Pi^{1}_{2}$ problem over
$\mathsf{B}\Sigma^{0}_{2}+\neg\mathsf{I}\Sigma^{0}_{2}$ is equivalent to a
formalized version of the first-jump control.

Let $\mathsf{I}\Delta^{0}_{n}$ be the following induction scheme for every
$\Sigma^{0}_{n}$ formula $\phi$ and every $\Pi^{0}_{n}$ formula $\psi$:

$\forall x[\phi(x)\leftrightarrow\psi(x)]\wedge\phi(0)\wedge\forall
x[\phi(x)\rightarrow\phi(x+1)]\rightarrow\forall x\phi(x)$

A set $X$ is _$M$ -regular_ (or _piecewise-coded_ , or even _amenable_) if all
its initial segments are $M$-finite. Over this article, we will use the
following characterizations of $\mathsf{B}\Sigma^{0}_{2}$:

######  Proposition 2.3 (Chong and Mourad [4] and Slaman [32]).

The following are equivalent over $\mathsf{RCA}_{0}$:

  1. (1)

$\mathsf{B}\Sigma^{0}_{2}$

  2. (2)

The induction principle for $\Delta^{0}_{2}$ predicates
($\mathsf{I}\Delta^{0}_{2}$)

  3. (3)

Every $\Delta^{0}_{2}$ set is regular

Given a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$
for some $\alpha\leq\epsilon_{0}$ topped by a set $Y\in S$, and a
$\mathsf{P}$-instance $I\in S$ for some $\Pi^{1}_{2}$ problem $\mathsf{P}$, we
will create a decreasing sequence of conditions $c_{0}\geq c_{1}\geq\dots$
(for the appropriate notion of forcing depending on $\mathsf{P}$) such that

  1. (a)

The sequence is $\Delta^{0}_{1}(P)$ for some set $P\subseteq M$ such that
$\mathcal{M}[P]\models\mathsf{I}\Delta^{0}_{1}$

  2. (b)

The set of $s\in M$ such that $c_{s}$ is defined is a cut

  3. (c)

For every $k\in M$, there is some $s\in M$ such that $c_{s}$ decides $(G\oplus
Y)^{\prime}{\upharpoonright}_{k}$

  4. (d)

For every $k\in M$, there is some $s\in M$ such that $c_{s}$ forces
$\Phi_{e}^{G\oplus Y}$ not to be an infinite $\alpha$-decreasing sequence for
every $e<k$

The item (a) will ensure that there is a $\Delta^{0}_{1}(P)$ formula $\psi(s)$
stating that the construction can be pursued up to stage $s$. By item (b),
$\\{s:\psi(s)\\}$ is a cut, so by $\mathsf{I}\Delta^{0}_{1}(P)$, the
construction can be pursued at every stage. By item (c), $(G\oplus
Y)^{\prime}$ will be $\Delta^{0}_{1}(P)$, hence
$\mathcal{M}[G]\models\mathsf{B}\Sigma^{0}_{2}$. Last, by item (d),
$\mathcal{M}[G]\models\mathsf{WF}(\alpha)$.

The use of an internal construction prevents from using a bijection between
$M$ and $\omega$ to satisfy the requirements one by one. Therefore, one must
use _Shore blocking_ arguments, that is, force the requirements simultaneously
for larger and larger initial segments of $M$, as mentioned in items (c) and
(d).

###  2.2 Well-foundedness and Shore blocking

Before working on $\Pi^{1}_{1}$-conservation of $\mathsf{WKL}$ and
$\mathsf{COH}$, we prove two combinatorial lemma which say that Shore blocking
comes for free for preserving $\mathsf{WF}(\alpha)$ for any ordinal
$\alpha\leq\epsilon_{0}$. Instead of using the standard sums and products over
ordinals, the natural (Hessenberg) sums and products will be more convenient:

######  Definition 2.4 (Natural sum and product).

Let $\alpha$ and $\beta$ be two ordinals less than $\epsilon_{0}$. Let
$\alpha=\omega^{\gamma_{1}}n_{1}+\dots+\omega^{\gamma_{k}}n_{k}$ and
$\beta=\omega^{\gamma_{1}}m_{1}+\dots+\omega^{\gamma_{k}}m_{k}$ (We allow the
$n_{i}$ and $m_{i}$ to be equal to $0$ in order to write $\alpha$ and $\beta$
using the same exponents $\gamma_{i}$). We define the natural sum of $\alpha$
and $\beta$ (denoted by $\alpha\dotplus\beta$) to be the following ordinal (It
does not depend on the choice of the family $(\gamma_{i})$) :

$\omega^{\gamma_{1}}(n_{1}+m_{1})+\dots+\omega^{\gamma_{k}}(n_{k}+m_{k})$

We also define $\alpha\dottimes k$ to be equal to be the natural sum of
$\alpha$ with itself $k$ times and
$\alpha\dottimes\omega=\omega^{\gamma_{1}+1}n_{1}+\dots+\omega^{\gamma_{k}+1}n_{k}$
(whereas $\alpha\times\omega=\omega^{\gamma_{1}+1}n_{1}$)

Note that $\alpha\dottimes k\leq\alpha\times\omega$, where
$\alpha\times\omega=\sup_{k<\omega}\alpha\times k=\omega^{\gamma_{1}+1}n_{1}$
is the usual ordinal product.

######  Proposition 2.5.

For all $\beta<\epsilon_{0}$, and $\alpha^{\prime}<\alpha<\epsilon_{0}$ :
$\alpha^{\prime}\dotplus\beta<\alpha\dotplus\beta$ and
$\beta\dotplus\alpha^{\prime}<\beta\dotplus\alpha$.

###### Proof.

Clear from the definition of $\dotplus$. ∎

######  Lemma 2.6.

Let $\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{WF}(\alpha)$ for
$\alpha$ an ordinal less than $\epsilon_{0}$. Then
$\mathcal{M}\models\mathsf{WF}(\alpha\dottimes k)$ for every $k\in M$.

###### Proof.

Since $\alpha\dottimes k\leq\alpha\times\omega$ for every $k\in M$ and
$\mathsf{RCA}_{0}$ proves that the product of two well-orders is a well-order,
hence
$\mathsf{RCA}_{0}\vdash\mathsf{WF}(\alpha)\rightarrow\mathsf{WF}(\alpha\times\omega)$,
we get the desired result.

∎

######  Lemma 2.7.

Consider a model $\mathcal{M}=(M,S)$ and $\alpha\in M$ an ordinal less than
$\epsilon_{0}$. For every $k\in M$, there is a Turing functional $\Gamma_{k}$
such that, letting $\beta\in\alpha$ be the largest ordinal less than $\alpha$
of index at most $k$, for every $X\in 2^{M}$ such that
$\mathcal{M}[X]\models\mathsf{RCA}_{0}$, if there is some $e<k$ such that
$\Phi^{X}_{e}$ is an $M$-infinite decreasing sequence of elements smaller than
$\beta$, then $\Gamma^{X}_{k}$ is an $M$-infinite decreasing sequence of
elements smaller than $\beta\dottimes k$.

Moreover, an index of $\Gamma_{k}$ can be found computably in $k$.

###### Proof.

By twisting the Turing functionals, we can assume that for every $e,n\in M$,
if $\Phi^{\sigma}_{e}(n)\downarrow$, then

  * (1)

$n<|\sigma|$ ;

  * (2)

$\Phi^{\sigma}_{e}(m)\downarrow$ for every $m<n$ ;

  * (3)

$\Phi^{\sigma}_{e}(0),\Phi^{\sigma}_{e}(1),\dots,\Phi^{\sigma}_{e}(m)$ is a
strictly decreasing sequence of elements smaller than $\beta$.

Given $\sigma\in 2^{<M}$ and $e<k$, let
$\alpha(\sigma,e)=\Phi^{\sigma}_{e}(s)$ for the largest $s<|\sigma|$ such that
$\Phi^{\sigma}_{e}(s)\downarrow$. If there is no such $s$, then
$\alpha(\sigma,e)=\beta$. Note that if $\sigma^{\prime}\succeq\sigma$, then
$\alpha(\sigma^{\prime},e)\leq\alpha(\sigma,e)$.

Let $\sigma_{-1}=\epsilon$. Let $\Gamma^{X}_{k}$ be the Turing functional
which, on input $n$, searches for some $x>|\sigma_{n-1}|$ and some
$\sigma_{n}\prec X$ such that $\Phi_{e}^{\sigma_{n}}(x)\downarrow$ for some
$e<k$. If found, it outputs
$\alpha(\sigma,0)\dotplus\dots\dotplus\alpha(\sigma,k-1)$. Note that if
$\Gamma^{X}_{k}(n)\downarrow$, then by (3), $\Gamma^{X}(n)$ is an ordinal
smaller than $\beta\dottimes k$.

Suppose that $X$ is such that $\mathcal{M}[X]\models\mathsf{RCA}_{0}$ and
there is an $e<k$ is such that $\Phi_{e}^{X}$ is total. Since
$\mathcal{M}[X]\models\mathsf{I}\Sigma^{0}_{1}$, then $\Gamma^{X}$ is total.

Moreover, since $x>|\sigma_{n-1}|$, then letting $e<k$ be such that
$\Phi_{e}^{\sigma_{n}}(x)\downarrow$, by (1) we have
$\Phi_{e}^{\sigma_{n-1}}(x)\uparrow$, so by (2) and (3),
$\alpha(\sigma_{n+1},e)<\alpha(\sigma_{n},e)$, hence
$\Gamma^{X}_{k}(n+1)<\Gamma^{X}_{k}(n)$. It follows that $\Gamma^{X}_{k}$ is
an $M$-infinite decreasing sequence of ordinals smaller than $\beta\dottimes
k$. ∎

###  2.3 $\Pi^{1}_{1}$-conservation of $\mathsf{COH}$

We now turn to the proof that
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)+\mathsf{COH}$
is $\Pi^{1}_{1}$-conservative of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$ for every
ordinal $\alpha\leq\epsilon_{0}$. In particular, letting $\alpha=\omega$, we
reprove the theorem of Chong, Slaman and Yang [5] stating that
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{COH}$ is
$\Pi^{1}_{1}$-conservative over $\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$.
Note that the original proof by Chong, Slaman and Yang uses a case analysis,
depending on whether the model satisfies $\mathsf{I}\Sigma^{0}_{2}$ or not.
Belanger [1] gave a more direct proof using characterization of p-cohesive
sets are those whose jump is PA over 0’ (see Jockusch and Stephan [17]). Our
proof follows the ideas from Belanger, but with an even more direct
construction based on an instance-wise correspondence between instances of
$\mathsf{COH}$ and $\Pi^{0}_{1}(\emptyset^{\prime})$ classes. As in Belanger’s
proof, the proof relies on the following theorem:

######  Theorem 2.8 (Simpson–Smith [31]).

Every countable model of $\mathsf{RCA}_{0}^{*}$ can be $\omega$-extended into
a model of $\mathsf{RCA}_{0}^{*}+\mathsf{WKL}$.

######  Proposition 2.9.

Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$
topped by a set $Y\in S$, where $\alpha\leq\epsilon_{0}$ is an ordinal. Then
for every $\vec{R}\in S$ and every $P\gg Y^{\prime}$ such that
$\mathcal{M}[P]\models\mathsf{RCA}_{0}^{*}$, there exists $G\subseteq M$ such
that

  1. 1.

$G$ is $\vec{R}$-cohesive ;

  2. 2.

$P\geq_{T}(G\oplus Y)^{\prime}$ ;

  3. 3.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

###### Proof.

Fix a $\Delta^{0}_{2}(Y)$ tree $T$ such that $[T]=\mathcal{C}(\vec{R})$. In
particular, $T$ is $\Delta^{0}_{1}(Y^{\prime})$, so since $P\gg Y^{\prime}$,
there is a $\Delta^{0}_{1}(P)$ set $Q\in[T]$.

We will define the set $G$ using an infinite $\Delta^{0}_{1}(P)$ decreasing
sequence of Mathias-like conditions.

######  Definition 2.10.

A _condition_ is a pair of $M$-finite binary strings $(\sigma,\rho)$ such that
$\rho\prec Q$. We have $(\sigma_{2},\rho_{2})\leq(\sigma_{1},\rho_{1})$ if
$\sigma_{2}\succ\sigma_{1}$, $\rho_{2}\succ\rho_{1}$ and
$\sigma_{2}-\sigma_{1}\subseteq R_{\rho_{1}}$ (where $\sigma_{2}-\sigma_{1}$
is the difference between the sets corresponding to the two sequences).

One can think of a condition $(\sigma,\rho)$ as a Mathias condition
$(\sigma,\vec{R}_{\rho})$. Requiring that $\rho\prec Q$ ensures that
$\vec{R}_{\rho}$ is $M$-infinite. When increasing the length of $\rho$, we
make progress in cohesiveness. Note that being a condition is a
$\Delta^{0}_{1}(Q)$ predicate, as it simply requires checking that
$\sigma\prec Q$, while the extension relation is $\Delta^{0}_{1}(Y)$. In
particular, both are $\Delta^{0}_{1}(Q\oplus Y)$, so $\Delta^{0}_{1}(P)$.

A sequence $\tau$ is said to be _compatible_ with a condition $(\sigma,\rho)$
if $\sigma\prec\tau$ and $\tau-\sigma\subseteq R_{\rho}$.

######  Definition 2.11.

Let $(\sigma,\rho)$ be a condition, and $\Phi_{e}$ be a Turing functional.

  1. 1.

$(\sigma,\rho)\Vdash\exists x\Phi^{G\oplus Y}_{e}(x)\downarrow$ if there is
some $x,t<|\sigma|$ such that $\Phi^{\sigma\oplus Y}_{e}(x)[t]\downarrow$

  2. 2.

$(\sigma,\rho)\Vdash\forall x\Phi^{G\oplus Y}_{e}(x)\uparrow$ if for every
$\tau$ compatible with $(\sigma,\rho)$ and every $x\in M$, $\Phi^{\tau\oplus
Y}_{e}(x)\uparrow$.

Note that the relations $(\sigma,\rho)\Vdash\exists x\Phi^{G\oplus
Y}_{e}(x)\downarrow$ and $(\sigma,\rho)\Vdash\forall x\Phi^{G\oplus
Y}_{e}(x)\uparrow$ are $\Delta^{0}_{0}(Y)$ and $\Pi^{0}_{1}(Y)$, respectively.

To ensure that $P\geq_{T}(G\oplus Y)^{\prime}$, we will also construct
$(G\oplus Y)^{\prime}$ in parallel.

For this, we will need to satisfy three kind of requirements for every $k\in
M$:

  * •

$\mathcal{R}_{k}$: $(G\oplus Y)^{\prime}{\upharpoonright}_{k}$ is decided

  * •

$\mathcal{S}_{k}$: for every $e<k$, $\Phi^{G}_{e}$ is not an $M$-infinite
$\alpha$-decreasing sequence

  * •

$\mathcal{T}_{k}$: for every $e<k$, $G\subseteq^{*}R_{e}$ or
$G\subseteq^{*}\overline{R}_{e}$

We will need the following two technical lemmas, which are Shore blocking
arguments for satisfying the two kind of requirements, namely, deciding the
jump and preserving $\mathsf{WF}(\alpha)$. In what follows,
$(\tau,\rho)\Vdash(G\oplus Y)^{\prime}{\upharpoonright}_{k}=\sigma^{\prime}$
means that for every $e<|\sigma^{\prime}|$, if $\sigma^{\prime}(e)=1$ then
$(\tau,\rho)\Vdash\Phi^{G\oplus Y}_{e}(e)\downarrow$ and if
$\sigma^{\prime}(e)=0$, then $(\tau,\rho)\Vdash\Phi^{G\oplus
Y}_{e}(e)\uparrow$. Thus, this relation is $\Pi^{0}_{1}(Y)$.

######  Lemma 2.12.

Let $(\sigma,\rho)$ be a condition. For every $k\in M$, there exists some
$M$-finite $\sigma^{\prime}\in 2^{k}$ and an extension
$(\tau,\rho)\leq(\sigma,\rho)$ such that $(\tau,\rho)\Vdash(G\oplus
Y)^{\prime}{\upharpoonright}_{k}=\sigma^{\prime}$.

###### Proof.

Let $W$ be the set of all $\sigma^{\prime}\in 2^{k}$ such that
$(\exists\tau\succ\sigma)(\exists t)(\forall e<s)(\tau-\sigma\in
R_{\rho}\wedge|\tau-\sigma|\geq
1\wedge\sigma^{\prime}(e)=1\to\Phi_{e}^{\sigma\oplus Y}(e)[t]\downarrow)$.
Note that $W$ is $\Sigma^{0}_{1}(Y)$, hence is $M$-finite. Moreover, $W$ is
non-empty, as it contains the string $000\dots$. Let $\sigma^{\prime}\in W$ be
the lexicographically maximal element, and let $\tau\succeq\sigma$ witness
that $\sigma^{\prime}\in W$.

We claim that $(\tau,\rho)$ forces $(G\oplus
Y)^{\prime}{\upharpoonright}_{k}=\sigma^{\prime}$. Fix some $e<k$.

Case (a): $\sigma^{\prime}(e)=1$. Then $\Phi_{e}^{\tau\oplus Y}(e)\downarrow$,
hence for every $G$ compatible with $(\tau,\rho)$, $e\in(G\oplus Y)^{\prime}$.

Case (b): $\sigma^{\prime}(e)=0$. The maximality of $\sigma^{\prime}$ ensures
that for every $\mu$ compatible with $(\tau,\rho)$, $\Phi^{\mu\oplus
Y}(e)\uparrow$. It follows that $\Phi^{G\oplus Y}_{e}(e)\uparrow$, hence
$e\not\in(G\oplus Y)^{\prime}$. ∎

######  Lemma 2.13.

Let $(\sigma,\rho)$ be a condition. For every $k\in M$, there exists some
$n\in M$ an extension $(\tau,\rho)\leq(\sigma,\rho)$ forcing
$\Phi_{e}^{G\oplus Y}$ not to be an $\alpha$-decreasing sequence of length
more than $n$ for every $e<k$.

###### Proof.

By twisting the Turing functionals, we can assume that for every $e,n\in M$,
if $\Phi^{\sigma}_{e}(n)\downarrow$, then

  * •

$\Phi^{\sigma}_{e}(m)\downarrow$ for every $m<n$

  * •

$\Phi^{\sigma}_{e}(0),\Phi^{\sigma}_{e}(1),\dots,\Phi^{\sigma}_{e}(m)$ is a
strictly $\alpha$-decreasing sequence

Suppose the lemma does not hold. Then in particular, for every $M$-finite
string $\tau$ compatible with $(\sigma,\rho)$ and every $n\in M$, there is
some $\tau_{1}\succeq\tau$ compatible with $(\sigma,\rho)$ and some $e<k$ such
that $\Phi^{\tau_{1}\oplus Y}(n)\downarrow$.

Build $Y$-recursively an infinite sequence
$\tau_{0}\preceq\tau_{1}\preceq\tau_{2}\preceq\dots$ such that for every $n$,

  * •

$\tau_{n}$ is compatible with $(\sigma,\rho)$

  * •

$\Phi^{\tau_{n}\oplus Y}_{e}(n)\downarrow$ for some $e<k$ (which depends on
$n$)

Since $\mathcal{M}\models\mathsf{B}\Sigma^{0}_{2}$, then
$\mathcal{M}\models\forall k\mathsf{RT}^{1}_{k}$, so there is an $M$-infinite
set $Z\in\mathcal{M}$ and some $e<k$ such that for every $n\in Z$,
$\Phi^{\tau_{n}\oplus Y}_{e}(n)\downarrow$.

Then, letting $f(n)=\Phi^{\tau_{n}\oplus Y}_{e}(n)$, we have an $M$-infinite
$\alpha$-decreasing sequence, contradicting
$\mathcal{M}\models\mathsf{WF}(\alpha)$. ∎

Note that the statement ”$(\tau,\rho)$ forces $\Phi_{e}^{G\oplus Y}$ not to be
an $\alpha$-decreasing sequence of length more than $n$ for every $e<k$” is
$\Pi^{0}_{1}(Y)$. Indeed, it means that for every $\mu$ compatible with
$(\tau,\rho)$ and every $e<k$, $\Phi_{e}^{\mu\oplus Y}(n)\uparrow$.”

Construction. We will build a decreasing sequence $(\sigma_{s},\rho_{s})$ of
conditions and then take for $G$ the union of the $\sigma_{s}$. We will also
build an increasing sequence $(\sigma^{\prime}_{s})$ such that $(G\oplus
Y)^{\prime}$ will be the union of the $\sigma^{\prime}_{s}$. Initially, we
take $\sigma_{0}=\sigma^{\prime}_{0}=\rho_{0}=\epsilon$, and during the
construction, we will ensure that we have
$|\sigma_{s}|,|\sigma^{\prime}_{s}|,|\rho_{s}|\leq s$ at every stage. Each
stage will be either of type $\mathcal{R}$, of type $\mathcal{S}$ or of type
$\mathcal{T}$. The stage $0$ is of type $\mathcal{R}$.

Assume that $(\sigma_{s},\rho_{s})$ and $\sigma^{\prime}_{s}$ are already
defined. Let $s_{0}<s$ be the latest stage at which we switched the stage
type. We have three cases.

Case 1: $s$ is of type $\mathcal{R}$. If there exists some $\tau\in 2^{\leq
s}$ and some $\sigma^{\prime}\in 2^{s_{0}}$ such that
$(\tau,\rho_{s})\leq(\sigma_{s},\rho_{s})$, and $(\tau,\rho_{s})$ forces
$(G\oplus Y)^{\prime}{\upharpoonright}_{s_{0}}=\sigma^{\prime}$, then let
$\sigma_{s+1}=\tau$, $\rho_{s+1}=\rho_{s}$,
$\sigma^{\prime}_{s+1}=\sigma^{\prime}$ and let $s+1$ be of type
$\mathcal{S}$. Otherwise, the elements are left unchanged and we go to the
next stage.

Case 2: $s$ is of type $\mathcal{S}$. If there exists some $\tau\in 2^{\leq
s}$ such that $(\tau,\rho_{s})\leq(\sigma_{s},\rho_{s})$, and
$(\tau,\rho_{s})$ forces $\mathcal{S}_{s_{0}}$, then let $\sigma_{s+1}=\tau$,
$\rho_{s+1}=\rho_{s}$, $\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$ and let
$s+1$ be of type $\mathcal{T}$. Otherwise, the elements are left unchanged and
we go to the next stage.

Case 3: $s$ is of type $\mathcal{T}$. If there exists some $\tau\in 2^{\leq
s}$ such that $(\tau,\rho_{s})\leq(\sigma_{s},\rho_{s})$ and
$\tau-\sigma_{s}\neq\emptyset$. Then let $\sigma_{s+1}=\tau$,
$\rho_{s+1}=P{\upharpoonright}_{s_{0}}$,
$\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$, and let $s+1$ be of type
$\mathcal{R}$. Otherwise, the elements are left unchanged and we go to the
next stage.

This completes the construction.

Verification. Since the size of $\sigma_{s},\sigma^{\prime}_{s}$ and
$\rho_{s}$ are bounded by $s$, there is a $\Delta_{1}^{0}(Y^{\prime}\oplus
Q)$-formula $\phi(s)$ stating that the construction can be pursued up to stage
$s$. Our construction implies that the set $\\{s|\phi(s)\\}$ is a cut, so by
$\mathsf{I}\Delta^{0}_{1}(P)$, the construction can be pursued at every stage.

Let $G=\bigcup_{s\in M}\sigma_{s}$. By Lemma 2.12 and Lemma 2.13 and the fact
that each $R_{\rho_{s}}$ is $M$-infinite, each type of stage changes
$M$-infinitely often. Thus, $G$ is $M$-infinite and
$\\{|\sigma^{\prime}_{s}|:s\in M\\}$ is $M$-infinite, so $P\geq_{T}(G\oplus
Y)^{\prime}$. In particular,
$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$. Moreover,
for every $e\in M$, there is a stage $s_{0}>e$ at which the stage type
switches from $\mathcal{R}$ to $\mathcal{S}$, and a stage $s>s_{0}$ at which
the stage switches from $\mathcal{S}$ to $\mathcal{T}$. Then,
$(\sigma_{s+1},\rho_{s+1})$ forces $\mathcal{S}_{s_{0}}$, so $\Phi^{G\oplus
Y}_{e}$ is not an $M$-infinite $\alpha$-decreasing sequence. Thus,
$\mathcal{M}[G]\models\mathsf{WF}(\alpha)$. Similarly, for every $e\in M$,
there is a stage $s>e$ such that the stage type switches from $\mathcal{S}$ to
$\mathcal{T}$. Then $(\sigma_{s+1},\rho_{s+1})$ is such that $|\rho_{s+1}|>e$,
so $G\subseteq^{*}R_{e}$ or $G\subseteq^{*}\overline{R}_{e}$. Thus $G$ is
$\vec{R}$-cohesive. This completes the proof of Proposition 2.9. ∎

######  Corollary 2.14.

Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$
topped by a set $Y\in S$, where $\alpha\leq\epsilon_{0}$ is an ordinal. Then
for every $\vec{R}\in S$, there exists $G\subseteq M$ such that

  1. 1.

$G$ is $\vec{R}$-cohesive ;

  2. 2.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

###### Proof.

By Theorem 2.8, there exists a set $P\subseteq M$ such that $P\gg Y^{\prime}$
and $\mathcal{M}[P]\models\mathsf{RCA}_{0}^{*}$. The conclusion follows from
Proposition 2.9. ∎

We therefore obtain our first conservation theorem:

######  Theorem 2.15.

Fix an ordinal $\alpha\leq\epsilon_{0}$.
$\mathsf{RCA}_{0}+\mathsf{COH}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$
is $\Pi_{1}^{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

###### Proof.

Immediate by Proposition 2.9 and Theorem 2.2. ∎

###  2.4 $\Pi^{1}_{1}$-conservation of $\mathsf{WKL}$

We now turn to the proof of $\Pi^{1}_{1}$-conservation of $\mathsf{WKL}_{0}$.
As for $\mathsf{COH}$, in the case $\alpha=\omega$, we recover the well-known
conservation theorem of Hájek [12] stating that
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WKL}$ is a
$\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$.

######  Proposition 2.16.

Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$
topped by a set $Y\in S$, where $\alpha\in M$ is an ordinal
$\leq\epsilon_{0}$. Then for every $M$-infinite primitive $Y$-recursive tree
$T\in S$, there exists $G\subseteq M$ such that

  1. 1.

$G$ is a path in $T$ ;

  2. 2.

$Y^{\prime}\geq_{T}(G\oplus Y)^{\prime}$ ;

  3. 3.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$

###### Proof.

We will build the path $G$ using forcing on trees. A condition will be a pair
$(\sigma,T^{\prime})$ with $T^{\prime}\in S$ an $M$-infinite primitive
$Y$-recursive subtree of $T$ with root $\sigma$ and we will have
$(\sigma,T_{1})\leq(\tau,T_{2})$ if $\tau\prec\sigma$ and $T_{1}\subseteq
T_{2}$.

######  Definition 2.17.

Let $(\sigma,U)$ be a condition, and $\Phi_{e}$ be a Turing functional.

  1. 1.

$(\sigma,U)\Vdash\exists x\Phi_{e}^{G\oplus Y}(x)\downarrow$ if there is some
$x,t<|\sigma|$ such that $\Phi_{e}^{\sigma\oplus Y}(x)[t]\downarrow$

  2. 2.

$(\sigma,U)\Vdash\forall x\Phi_{e}^{G\oplus Y}(x)\uparrow$ if for every
$\tau\in U$ and every $x\in M$, $\Phi_{e}^{\tau\oplus Y}(x)\uparrow$.

Note that the relations $(\sigma,U)\Vdash\exists x\Phi^{G\oplus
Y}_{e}(x)\downarrow$ and $(\sigma,U)\Vdash\forall x\Phi^{G\oplus
Y}_{e}(x)\uparrow$ are $\Delta^{0}_{0}(Y)$ and $\Pi^{0}_{1}(Y)$, respectively.

For our construction, we want to satisfy the following requirements :

  * •

$\mathcal{R}_{k}$: $(G\oplus Y)^{\prime}{\upharpoonright}_{k}$ is decided.

  * •

$\mathcal{S}_{k}$: Let $\beta\in\alpha$ be the $<_{\epsilon_{0}}$-biggest
element of index less than $k$, for every $e<k$, $\Phi_{e}^{G\oplus Y}$ is not
an $M$-infinite $<_{\epsilon_{0}}$-decreasing sequence of elements smaller
than $\beta$.

  * •

$\mathcal{T}_{k}$: $|\sigma|\geq k$.

We first prove a simple technical lemma saying that there exists arbitrarily
large extendible nodes. This lemma even holds over $\mathsf{RCA}_{0}^{*}$ and
can be found in various places in the literature.

######  Lemma 2.18 (Fernandes et al [10]).

Let $\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}^{*}$ be a model and $T\subseteq
2^{<M}$ be an $M$-infinite tree in $\mathcal{M}$. Then for every $\ell\in M$,
there is some $\sigma\in T$ of length $\ell$ such that $\\{\tau\in
T:\tau\mbox{ is comparable with }\sigma\\}$ is $M$-infinite.

###### Proof.

Assume by contradiction that for every $\sigma\in 2^{\ell}$ the tree

$\\{\tau\in T:\tau\mbox{ is comparable with }\sigma\\}$

is $M$-bounded, this means that $\mathcal{M}\models\forall\sigma\in
2^{\ell}\exists b_{\sigma}\forall\tau\in
2^{b_{\sigma}},\sigma\prec\tau\Rightarrow\tau\notin T$.

The formula $\forall\tau\in
2^{b_{\sigma}},\sigma\prec\tau\Rightarrow\tau\notin T$ is $\Delta_{0}^{0}(T)$
and therefore $\Delta_{1}^{0}$ in $\mathcal{M}$. Therefore, we can use
$\mathsf{B}\Sigma^{0}_{1}$ (which holds in $\mathsf{RCA}_{0}^{*}$) to get :

$\mathcal{M}\models\exists b\forall\sigma\in 2^{\ell}\exists
b_{\sigma}<b\forall\tau\in 2^{b_{\sigma}},\sigma\prec\tau\Rightarrow\tau\notin
T$

Which yields that $T$ is bounded by such a $b$, contradicting our assumption
that $T$ is $M$-infinite. So there is some $\sigma\in T$ of length $\ell$ such
that $\\{\tau\in T:\tau\mbox{ is comparable with }\sigma\\}$ is $M$-infinite.
∎

We will need the following two technical lemmas, which are Shore blocking
arguments for satisfying the two kind of requirements, namely, deciding the
jump and preserving $\mathsf{WF}(\alpha)$. In what follows,
$(\tau,U)\Vdash(G\oplus Y)^{\prime}{\upharpoonright}_{k}=\sigma^{\prime}$
means that for every $e<|\sigma^{\prime}|$, if $\sigma^{\prime}(e)=1$ then
$(\tau,U)\Vdash\Phi^{G\oplus Y}_{e}(e)\downarrow$ and if
$\sigma^{\prime}(e)=0$, then $(\tau,U)\Vdash\Phi^{G\oplus Y}_{e}(e)\uparrow$.
Thus, this relation is $\Pi^{0}_{1}(Y)$.

######  Lemma 2.19.

Let $(\sigma,T_{1})$ a condition. For every $k\in M$, there exists some
$M$-finite $\sigma^{\prime}$ and an extension $(\tau,T_{2})\leq(\sigma,T_{1})$
forcing $(G\oplus Y)^{\prime}{\upharpoonright}_{k}=\sigma^{\prime}$.

###### Proof.

Let $W$ be the set of all $\sigma^{\prime}\in 2^{k}$ such that the tree
$\\{\rho\in T_{1}|\sigma^{\prime}(e)=0\to\Phi_{e}^{\rho\oplus
Y}(e)\uparrow\\}$ is $M$-infinite. $W$ is $\Pi_{0}^{1}(Y)$ and hence
$M$-finite, and it is non-empty as it contains the string $1111\dots$.

We can consider $\sigma^{\prime}\in W$ its lexicographically minimal element,
and consider the corresponding tree $T_{3}$. For every $e<k$ such that
$\sigma^{\prime}(e)=1$, the minimality of $\sigma^{\prime}$ gives us that the
set of $\tau\in T_{3}$ such that $\Phi_{e}^{\tau\oplus Y}(e)\uparrow$ is
$M$-finite, so we have a level $h_{e}$ such that for every $\tau\in T_{3}\cap
2^{h_{e}}$, $\Phi_{e}^{\tau\oplus Y}(e)\downarrow$. The set
$\\{e<k|\sigma^{\prime}(e)=1\\}$ is $M$-finite, so we can consider an
upperbound $h$ of all the $h_{e}$. Finally, by Lemma 2.18, there is a $\tau\in
T_{3}\cap 2^{h}$ such that $T_{2}:=\\{\rho\in T_{3}:\rho\textit{ is comparable
with }\tau\\}$ is $M$-infinite (since $T_{3}$ is $M$-infinite).

We claim that $(\tau,T_{2})$ forces $(G\oplus
Y)^{\prime}{\upharpoonright}_{k}=\sigma^{\prime}$. Fix some $e<k$.

Case (a): $\sigma^{\prime}(e)=0$. Then $\Phi_{e}^{\tau\oplus Y}(e)\downarrow$
for every $\tau\in T_{2}$ (since $T_{2}\subseteq T_{3}$), hence for every $G$
compatible with $(\tau,T_{2})$, so $e\notin(G\oplus Y)^{\prime}$.

Case (b): $\sigma^{\prime}(e)=1$. The definition of $\tau$ ensure that
$\Phi_{e}^{\tau\oplus Y}(e)\downarrow$, so $e\in(G\oplus Y)^{\prime}$. ∎

######  Lemma 2.20.

Let $(\sigma,T_{1})$ be a condition. For every $k\in M$, letting $\Gamma_{k}$
be the functional of Lemma 2.7, there is an extension
$(\sigma,T_{2})\leq(\sigma,T_{1})$ forcing $\Gamma^{G\oplus Y}_{k}$ to be
partial.

###### Proof.

By twisting $\Gamma_{k}$, we can assume that for every $e,n\in M$, if
$\Gamma^{\sigma\oplus Y}_{k}(n)\downarrow$, then

  * •

$\Gamma^{\sigma\oplus Y}_{k}(m)\downarrow$ for every $m<n$ ;

  * •

$\Gamma^{\sigma\oplus Y}_{k}(0),\Gamma^{\sigma\oplus
Y}_{k}(1),\dots,\Gamma^{\sigma\oplus Y}_{k}(m)$ is a strictly
$<_{\epsilon_{0}}$-decreasing sequence of ordinals smaller than
$\beta\dottimes k$.

We have two cases.

Case 1: there exists some $n\in M$ such that for every $\ell\in M$, there is
some $\tau\in T_{1}$ of length $\ell$ such that $\Gamma^{\sigma\oplus
Y}_{k}(n)\uparrow$. Let $T_{2}=\\{\tau\in T_{1}:\Gamma^{\sigma\oplus
Y}_{k}(n)\uparrow\\}$. Note that the set $T_{2}$ is a $Y$-primitive recursive,
as the set $T_{1}$ and the predicate $\Gamma^{\sigma\oplus Y}_{k}(n)\uparrow$
are $Y$-primitive recursive. The set $T_{2}$ is closed-downward, and by
assumption, is $M$-infinite. Then $(\sigma,T_{2})\leq(\sigma,T_{1})$.
Moreover, by construction, $(\sigma,T_{2})\Vdash\Gamma_{k}^{G\oplus
Y}(n)\uparrow$.

Case 2: for every $n\in M$, there is some $\ell_{n}\in M$ such that for every
$\sigma\in T$ of length $\ell_{n}$, $\Gamma^{\sigma}_{k}(n)\downarrow$.

Then, for every $n$, let $\alpha_{n}=\max\ \\{\Gamma^{\sigma}_{k}(n):\sigma\in
T_{1}\wedge|\sigma|=\ell_{n}\\}$. We claim that for every $n\in M$,
$\alpha_{n+1}<_{\epsilon_{0}}\alpha_{n}$. Indeed, for every $\sigma\in T_{1}$
such that $|\sigma|=\ell_{n+1}$,
$\Gamma^{\sigma}_{k}(n+1)<_{\epsilon_{0}}\Gamma^{\sigma{\upharpoonright}\ell_{n}}_{k}$,
so

$\max\ \\{\Gamma^{\sigma}_{k}(n+1):\sigma\in
T_{1}\wedge|\sigma|=\ell_{n+1}\\}<_{\epsilon_{0}}\max\
\\{\Gamma^{\sigma}_{k}(n):\sigma\in T_{1}\wedge|\sigma|=\ell_{n}\\}$

So $\mathcal{M}\not\models\mathsf{WF}(\alpha\dottimes k)$. However, by Lemma
2.6, since $\mathcal{M}\models\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$,
then $\mathcal{M}\models\mathsf{WF}(\alpha\dottimes k)$. Contradiction. ∎

Note that the statement “$(\sigma,U)$ forces $\Gamma_{k}^{G\oplus
Y}(n)\uparrow$” is $\Pi^{0}_{1}(Y)$.

Construction We will build a decreasing sequence $(\sigma_{s},T_{s})$ of
conditions and then take $G$ for the union of the $\sigma_{s}$. We will also
build an increasing sequence $(\sigma_{s}^{\prime})$ such that $G^{\prime}$
will be the union of the $\sigma_{s}^{\prime}$. Initially we take
$\sigma_{0}=\sigma_{0}^{\prime}=\epsilon$ and $T_{0}=T$, and during the
construction we will ensure that we have
$|\sigma_{s}|,|\sigma^{\prime}_{s}|\leq s$ and that the index describing
$T_{s}$ is also less than $s$ at every stage. Each stage will be either of
type $\mathcal{R}$, of type $\mathcal{S}$ or of type $\mathcal{T}$. The stage
$0$ is of type $\mathcal{R}$.

Assume that $(\sigma_{s},T_{s})$ and $\sigma^{\prime}_{s}$ are already
defined. Let $s_{0}<s$ be the latest stage at which we switched the stage
type. We have three cases.

Case 1: $s$ is of type $\mathcal{R}$. If there exists some index $e\leq s$
such that the $e$-th primitive recursive tree $T^{\prime}$ is $M$-infinite and
satisfy $(\sigma_{s},T^{\prime})\leq(\sigma_{s},T_{s})$ and is such that
$(\sigma_{s},T^{\prime})$ forces $(G\oplus
Y)^{\prime}{\upharpoonright}_{k}=\sigma^{\prime}$ for a $\sigma^{\prime}\in
2^{s_{0}}$. Then let $\sigma_{s+1}=\sigma_{s}$, $T_{s+1}=T^{\prime}$,
$\sigma^{\prime}_{s+1}=\sigma^{\prime}$ and let $s+1$ be of type
$\mathcal{S}$. Otherwise, the elements are left unchanged and we go to the
next stage.

Case 2: $s$ is of type $\mathcal{S}$. If there exists some $e,n\leq s$ such
that the $e$-th primitive recursive tree $T^{\prime}$ is $M$-infinite and
$(\sigma_{s},T^{\prime})$ forces $\Gamma_{k}^{G\oplus Y}(n)\uparrow$, then let
$\sigma_{s+1}=\sigma_{s}$, $T_{s+1}=T^{\prime}$,
$\sigma_{s+1}^{\prime}=\sigma^{\prime}_{s}$ and let $s+1$ be of type
$\mathcal{T}$. Otherwise, the elements are left unchanged and we go to the
next stage.

Case 3: $s$ is of type $\mathcal{T}$. Then we can find a $\sigma\in 2^{s}$
such that $\\{\rho\in T_{s}|\rho\textit{ compatible with }\sigma\\}$ is
$M$-infinite (with $\mathsf{B}\Sigma^{0}_{2}$). We then take this tree for
$T_{s+1}$ and let $\sigma_{s+1}=\sigma$,
$\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$ and let $s+1$ be of type
$\mathcal{R}$.

This completes the construction.

Verification. Since the size of $\sigma_{s},\sigma^{\prime}_{s}$ and the index
of $T_{s}$ are bounded by $s$, there is a $\Delta_{1}^{0}(Y^{\prime})$-formula
$\phi(s)$ stating that the construction can be pursued up to stage $s$. Our
construction implies that the set $\\{s|\phi(s)\\}$ is
$\Delta_{1}^{0}(Y^{\prime})$ and forms a cut, so by
$\mathsf{I}\Delta^{0}_{1}(Y^{\prime})$, the construction can be pursued at
every stage.

Let $G=\bigcup_{s\in M}\sigma_{s}$. By Lemma 2.19 and Lemma 2.20, each type of
stage changes $M$-infinitely often. Thus, $\\{|\sigma^{\prime}_{s}|:s\in M\\}$
is $M$-infinite, so $Y^{\prime}\geq_{T}(G\oplus Y)^{\prime}$. In particular,
$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$.

Moreover, the stages $s_{0}$ where we force $\mathcal{S}_{s_{0}}$ are
infinite, so for every $\beta\in\alpha$ and $e\in M$, there is a stage that
will force $\Phi^{G\oplus Y}_{e}$ not to be an $M$-infinite
$\alpha$-decreasing sequence of elements less than $\beta$. And thus
$\Phi^{G\oplus Y}_{e}$ will not be an $M$-infinite $\alpha$-decreasing
sequence for any $e$, so $\mathcal{M}[G]\models\mathsf{WF}(\alpha)$.

For every $e\in M$, there is a stage $s>e$ such that the stage type switches
from $\mathcal{S}$ to $\mathcal{T}$. Then $(\sigma_{s+1},T_{s+1})$ is such
that $|\sigma_{s+1}|=s$, so $G$ is a path in $T$. This completes the proof of
Proposition 2.16. ∎

######  Theorem 2.21.

Fix an ordinal $\alpha\leq\epsilon_{0}$.
$\mathsf{RCA}_{0}+\mathsf{WKL}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$
is $\Pi_{1}^{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

###### Proof.

Immediate by Proposition 2.16 and Theorem 2.2. ∎

##  3 Conservation over $\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$

The cases of $\mathsf{SEM}$ and $\mathsf{SADS}$ is more complicated than
$\mathsf{WKL}$ and $\mathsf{COH}$, as
$\mathsf{WF}(\omega^{\alpha\dottimes\omega})$ seems to be necessary to
preserve $\mathsf{WF}(\alpha)$ where $\alpha\leq\epsilon_{0}$. We therefore
get a fixed-point in the preservation of well-foundedness by letting
$\alpha=\epsilon_{0}$.

###  3.1 $\Pi^{1}_{1}$-conservation of $\mathsf{SEM}$

As mentioned in the introduction, the bounded monotone enumeration principle
naturally shows up when formalizing the first-jump control of Ramsey’s theorem
for pairs. Within the decomposition of $\mathsf{RT}^{2}_{2}$ into
$\mathsf{COH}+\mathsf{SADS}+\mathsf{SEM}$ of Proposition 1.16, $\mathsf{SEM}$
is the only statement not known to be $\Pi^{1}_{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$. It is therefore natural to expect
to involve $\mathsf{BME}_{*}$ in the proof below. Since $\mathsf{BME}_{*}$ is
equivalent to $\mathsf{WF}(\omega^{\omega})$ and we suppose
$\mathcal{M}\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\omega^{\alpha\dottimes\omega})$,
we will be able to use $\mathsf{BME}_{*}$.

######  Proposition 3.1.

Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\omega^{\alpha\dottimes\omega})$
topped by a set $Y\in S$, where $\alpha\in M$ is a non-zero ordinal
$\leq\epsilon_{0}$. Then for every infinite stable tournament $R$ in $S$ and
every set $P\gg Y^{\prime}$ such that
$\mathcal{M}[P]\models\mathsf{RCA}_{0}^{*}$, there exists $G\subseteq M$ such
that

  1. 1.

$G$ is an $M$-infinite transitive subtournament ;

  2. 2.

$P\geq_{T}(G\oplus Y)^{\prime}$ ;

  3. 3.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

###### Proof.

Fix a uniform enumeration of all $Y$-primitive recursive non-empty tree
functionals $T_{0},T_{1},\dots$, that is, for every $n\in M$ and every $X$,
$T_{n}^{X}$ is an $M$-infinite tree. Let

$\mathcal{C}=\\{\bigoplus_{a}X_{a}:\forall a\forall n\ X_{\langle
a,n\rangle}\in[T_{n}^{Y\oplus X_{0}\oplus\dots\oplus X_{a}}]\\}$

The class $\mathcal{C}$ is $\Pi^{0}_{1}(Y)$ and non-empty. There exists a
primitive $Y$-recursive tree whose infinite path are the elements of
$\mathcal{C}$, so Proposition 2.16 gives us a set
$\vec{X}=\bigoplus_{a}X_{a}\in\mathcal{C}$ such that
$Y^{\prime}\geq_{T}(\vec{X}\oplus Y)^{\prime}$ and
$\mathcal{M}[\vec{X}]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\omega^{\alpha\dottimes\omega})$.

Furthermore, Proposition 2.9 applied on $\mathcal{M}[\vec{X}]$ gives us a set
$C\subseteq M$ satisfying :

  * •

$C$ is $\vec{X}$-cohesive ;

  * •

$P\geq_{T}(C\oplus\vec{X}\oplus Y)^{\prime}$ ;

  * •

$\mathcal{M}[\vec{X}\oplus
C]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\omega^{\alpha\dottimes\omega})$

Let $A_{0}(R):=\\{x:\forall^{\infty}yR(x,y)\\}$ and
$A_{1}(R):=\\{x:\forall^{\infty}yR(y,x)\\}$. The stability of $R$ gives us
$A_{0}(R)\sqcup A_{1}(R)=M$, so $A_{0}(R)$ and $A_{1}(R)$ are
$\Delta_{2}^{0}(Y)$.

######  Definition 3.2.

For two sets $F$ and $G$, the notation $F\to_{R}G$ denotes the formula
$(\forall x\in F)(\forall y\in G)R(x,y)$.

######  Definition 3.3 (Minimal interval).

Let $a,b\in\mathcal{M}$, the interval $(a,b)$ is the set of all $x$ such that
$R(a,x)$ and $R(x,b)$.

Let $F$ be an $M$-finite transitive subtournament of $R$, for $a,b\in
F\cup\\{-\infty,+\infty\\}$ we say that $(a,b)$ is a minimal interval of $F$
is $F\cap(a,b)=\emptyset$, where we consider that $R(-\infty,x)$ and
$R(x,+\infty)$ holds for every $x\in\mathcal{M}$.

######  Definition 3.4.

A condition is a pair $(\sigma,a)$ where $\sigma$ is a $M$-finite binary
string corresponding to an $R$-transitive subtournament, $a\in\mathcal{M}$ is
such that $C\subseteq^{*}X_{a}$ and $X_{a}$ is included in a minimal interval
of $\sigma$.

Being a condition is a $\Delta_{1}^{0}((C\oplus X_{a}\oplus
Y)^{\prime})$-formula. Indeed, being a finite $R$-transitive subtournament is
$Y$ computable, checking that $X_{a}$ is included in a minimal interval of
$\sigma$ is $(X_{a}\oplus Y)^{\prime}$-computable, and checking if
$C\subseteq^{*}X_{a}$ can be decided using $(C\oplus X_{a})^{\prime}$ (since
$C$ is $\vec{X}$-cohesive, we know that $C\subseteq^{*}X_{a}$ or
$C\subseteq^{*}\bar{X_{a}}$ and these events are $\Sigma_{2}^{0}(C\oplus
X_{a})$). Since $P\geq_{T}(C\oplus\vec{X}\oplus Y)^{\prime}$, it is a
$\Delta_{1}^{0}(P)$-formula.

######  Definition 3.5.

A condition $(\tau,b)$ extends a condition $(\sigma,a)$ (and we write
$(\tau,b)\leq(\sigma,a)$) if $\sigma\prec\tau$, $X_{b}\subseteq X_{a}$ and
$\tau-\sigma\subseteq X_{a}$.

For our construction, we want to satisfy the following requirements :

  * •

$\mathcal{R}_{k}$: $(G\oplus Y)^{\prime}{\upharpoonright}_{k}$ is decided.

  * •

$\mathcal{S}_{k}$: Let $\beta<\alpha$ be the $<_{\epsilon_{0}}$-biggest
ordinal of index less than $k$, for every $e<k$, $\Phi_{e}^{G\oplus Y}$ is not
an $M$-infinite $<_{\epsilon_{0}}$-decreasing sequence of elements smaller
than $\beta$.

  * •

$\mathcal{T}_{k}$: $\operatorname{card}G\geq k$.

We will need two technical lemmas, which are Shore blocking arguments for
satisfying the two kinds of requirements, namely, deciding the jump and
preserving $\mathsf{WF}(\alpha)$. Before this, we introduce some basic
combinatorial concepts which will be useful for both lemmas. A
$\Sigma^{0}_{1}$ formula $\varphi(G)$ is in _normal form_ if
$\varphi(G)\equiv\exists i\psi(G{\upharpoonright}i)$ for a $\Delta^{0}_{0}$
formula $\psi$.

######  Definition 3.6.

Fix a condition $(\sigma,a)$.

  1. (1)

A _$(\sigma,a)$ -node_ is an $M$-finite sequence of the form

$\nu=\langle(i_{0},\rho_{0}),(i_{1},\rho_{1}),\dots(i_{q-1},\rho_{q-1})\rangle$

such that for every $s<q$, $i_{s}<2$, $\rho_{s}\subseteq X_{a}$ is a non-empty
$M$-finite $R$-transitive set with $\min\rho_{s}>\max\rho_{s-1}$ (letting
$\rho_{-1}=\sigma$), and for every $s<t<q$, if $i_{s}=0$ then
$\rho_{s}\to_{R}\rho_{t}$, and if $i_{s}=1$ then $\rho_{t}\to_{R}\rho_{s}$. We
then write

$\pi(\nu)=\sigma\cup\rho_{0}\cup\dots\cup\rho_{q-1}$

  2. (2)

This $(\sigma,a)$-node is _valid_ if for every $s<q$, $\rho_{s}\subseteq
A_{i_{s}}(R)$

  3. (3)

A $(\sigma,a)$-node $\nu$ _satisfies_ a $\Sigma^{0}_{1}(\mathcal{M})$-formula
$\varphi(G,x)\equiv\exists i\psi(G{\upharpoonright}i,x)$ if
$\psi(\pi(\nu),|\nu|-1)$ holds.

######  Lemma 3.7.

Fix a $(\sigma,a)$-node $\nu$. Then $\pi(\nu)$ is $R$-transitive.

###### Proof.

Say
$\nu=\langle(i_{0},\rho_{0}),(i_{1},\rho_{1}),\dots(i_{q-1},\rho_{q-1})\rangle$.
We prove by $\Sigma^{0}_{0}$-induction that for every $\ell<t$, $\rho_{\ell}$
is an $R$-transitive tournament included in a minimal interval of
$\sigma\cup\rho_{0}\cup\dots\cup\rho_{\ell-1}$ and that
$\sigma\cup\rho_{0}\cup\dots\cup\rho_{\ell}$ is $R$-transitive.

This is true for $\ell=0$ since $(\sigma,a)$ is a condition. And assuming the
property to be true at a rank $\ell<t-1$, the construction of $\rho_{\ell+1}$
ensures that it is included in the minimal interval of $(\sigma,a)$ and that
$\rho_{\ell+1}\to_{R}\rho_{j}$ if $i_{j}=1$ and $\rho_{j}\to_{R}\rho_{\ell+1}$
if $i_{j}=0$, so no elements of $\sigma\cup\rho_{0}\cup\dots\cup\rho_{\ell}$
is between two elements of $\rho_{\ell+1}$. Since
$\sigma\cup\rho_{0}\cup\dots\cup\rho_{\ell}$ is $R$-transitive (by the
induction hypothesis), this means that $\rho_{\ell+1}$ is included in one of
its minimal intervals, and since it is itself $R$-transitive,
$\sigma\cup\rho_{0}\cup\dots\cup\rho_{\ell}\cup\rho_{\ell+1}$ is
$R$-transitive. ∎

######  Lemma 3.8.

Fix a valid $(\sigma,a)$-node $\nu$. Then $(\pi(\nu),b)$ is an extension of
$(\sigma,a)$ for some $b\in M$.

###### Proof.

Say
$\nu=\langle(i_{0},\rho_{0}),(i_{1},\rho_{1}),\dots(i_{q-1},\rho_{q-1})\rangle$.
By definition of validity and stability of $R$, for every $s<q$, if $i_{s}=0$
then $\forall x\in\rho_{s}\forall^{\infty}y\in X_{a}$, $R(x,y)$, and if
$i_{s}=1$ then $\forall x\in\rho_{s}\forall^{\infty}y\in X_{a}$, $R(y,x)$. By
$\mathsf{B}\Sigma^{0}_{2}$, there exists some $r\in M$ such that for every
$s<q$, if $i_{s}=0$ then $\rho_{s}\to_{R}X_{a}\setminus\\{0,\dots,r\\}$, and
if $i_{\ell}=1$ then $X_{a}\setminus\\{0,\dots,r\\}\to_{R}\rho_{s}$. Let $b\in
M$ be such that $X_{b}=X_{a}\setminus\\{0,\dots,r\\}$ and let
$\tau=\sigma\cup\rho_{0}\cup\dots\cup\rho_{t-1}$. By Lemma 3.7, $\tau$ is
$R$-transitive and by construction, $X_{b}\subseteq X_{a}$ is included in a
minimal interval of $\tau$. Thus $(\tau,b)$ is an extension of $(\sigma,a)$. ∎

######  Definition 3.9.

Fix a condition $(\sigma,a)$.

  1. (1)

A _$(\sigma,a)$ -tree_ is a set of $(\sigma,a)$-nodes closed downard under the
prefix relation.

  2. (2)

A $(\sigma,a)$-tree $E$ is _universal_ if for every $(\sigma,a)$-node $\nu$
which is not a leaf, there is some $r\in M$ such that for every $M$-finite
2-partition $A_{0}\sqcup A_{1}=\\{0,\dots,r-1\\}$, there is a side $i<2$ and
an $M$-finite $R$-transitive $\rho\subseteq A_{i}\cap X_{a}$ such that
$\nu\cdot\langle i,\rho\rangle\in E$.

  3. (3)

A $(\sigma,a)$-tree $E$ satisfies a $\Sigma^{0}_{1}(\mathcal{M})$ formula if
all its nodes satisfies it.

######  Lemma 3.10.

For every $\Sigma^{0}_{1}(\mathcal{M})$ formula $\varphi(G,x)$ and every
condition $(\sigma,a)$, there is a monotone enumeration of a maximal (for
inclusion) universal $(\sigma,a)$-tree $E$ satisfying $\varphi(G,x)$.

###### Proof.

At stage $0$ enumerate the empty sequence $\langle\rangle$. At stage $s$, for
every leaf $\nu\in E$, if for every 2-partition $A_{0}\sqcup
A_{1}=\\{0,\dots,s\\}$, there is some $i<2$ and some $\rho\subseteq A_{i}$ for
which

  1. (i)

$\varphi(\pi(\nu)\cup\rho,|\nu|)$ holds

  2. (ii)

$\nu\cdot\langle(i,\rho)\rangle$ is a $(\sigma,a)$-node.

then enumerate $\nu\cdot\langle(i,\rho)\rangle$ for all such partitions, and
go to the next stage. If nothing is enumerated, simply go to the next stage. ∎

A maximal universal $(\sigma,a)$-tree is not necessarily $M$-finite.

######  Lemma 3.11.

Every $M$-finite universal $(\sigma,a)$-tree $E$ has a valid leaf.

###### Proof.

We prove it by $\mathsf{I}\Delta^{0}_{2}$ induction. The root $\langle\rangle$
is vacuously valid. Assume $\nu\in E$ is a valid non-leaf. By universality of
$E$, there is some $r\in M$ such that for every $M$-finite 2-partition
$A_{0}\sqcup A_{1}=\\{0,\dots,r-1\\}$, there is a side $i<2$ and an $M$-finite
$R$-transitive $\rho\subseteq A_{i}\cap X_{a}$ such that $\nu\cdot\langle
i,\rho\rangle\in E$. By $\mathsf{BC}\Delta^{0}_{2}(Y)$ (which is equivalent to
$\mathsf{B}\Sigma^{0}_{2}(Y)$), the following partition is $M$-finite:

$A_{0}(R){\upharpoonright}_{r}\sqcup
A_{1}(R){\upharpoonright}_{r}=\\{0,\dots,r-1\\}$

Thus, there exists some $i<2$ and some $\rho\subseteq A_{i}(R)$ such that
$\nu\cdot\langle i,\rho\rangle\in E$. By choice of $i$ and $\rho$, the node
$\nu\cdot\langle i,\rho\rangle$ is valid. ∎

######  Lemma 3.12.

Let $(\sigma,a)$ be a condition, $\varphi(G,x)$ be a
$\Sigma^{0}_{1}(\mathcal{M})$ formula, and $E$ be an $M$-finite maximal
universal $(\sigma,a)$-tree satisfying $\varphi(G,x)$. Then there is an
extension $(\tau,c)\leq(\sigma,a)$ and some $q\in M$ such that
$(\tau,c)\Vdash\varphi(G,q-1)$ and $(\tau,c)\Vdash\neg\varphi(G,q)$.

###### Proof.

By Lemma 3.11, there is a valid leaf $\nu\in E$. Since $E$ satisfies
$\varphi(G,x)$, then $\varphi(\pi(\nu),|\nu|-1)$ holds. By Lemma 3.8, there is
some $b\in M$ such that $(\pi(\nu),b)\leq(\sigma,a)$.

By maximality of the tree, for every $s\in M$, there exists a 2-partition
$A_{0}\sqcup A_{1}=\\{0,\dots,s\\}$, such that for every side $i<2$ and every
$M$-finite $\rho\subseteq A_{i}\cap X_{a}$ such that $\nu\cdot\langle
i,\rho\rangle$ is a $(\sigma,a)$-node, then $\varphi(\pi(\nu)\cup\rho,|\nu|)$
does not hold.

Note that by choice of $X_{b}$, for every $M$-finite $R$-transitive
$\rho\subseteq A_{i}\cap X_{b}$, $\nu\cdot\langle i,\rho\rangle$ is a
$(\sigma,a)$-node. Thus, for every $s\in M$, there exists a 2-partition
$A_{0}\sqcup A_{1}=\\{0,\dots,s\\}$, such that (P) for every side $i<2$ and
every $M$-finite $R$-transitive $\rho\subseteq A_{i}\cap X_{b}$,
$\varphi(\pi(\nu)\cup\rho,|\nu|)$ does not hold.

By compactness, there exists a 2-partition $A_{0}\sqcup A_{1}=X_{b}$ such that
(P) holds. Moreover, the class $\mathcal{C}$ of all such partitions is
$\Pi^{0}_{1}(Y\oplus X_{b})$ and non-empty. By definition of $\vec{X}$, there
exists some $c,d\in M$ such that $X_{c},X_{d}$ is a 2-partition of $X_{b}$ in
$\mathcal{C}$. Moreover, since $G\subseteq^{*}X_{b}$, then either
$G\subseteq^{*}X_{c}$ or $G\subseteq^{*}X_{d}$. Since they play a symmetric
role, say $G\subseteq^{*}X_{c}$. Then $(\tau,c)$ is an extension of $(\tau,b)$
forcing $\varphi(G,|\nu|-1)$ and $\neg\varphi(G,|\nu|)$. ∎

We are now ready to prove our two Shore blocking lemmas.

######  Lemma 3.13.

Let $(\sigma,a)$ be a condition. For every $k\in M$, there exists some
$M$-finite $\sigma^{\prime}\in 2^{k}$ and an extension
$(\tau,b)\leq(\sigma,a)$ such that $(\tau,b)\Vdash(G\oplus
Y)^{\prime}{\upharpoonright}k=\sigma^{\prime}$

###### Proof.

Let $\varphi(G,x)$ be the $\Sigma^{0}_{1}(Y)$ formula which holds if there
exists some $e_{0}<\dots<e_{x-1}<k$ such that for every $s<x$, $\Phi^{G\oplus
Y}_{e_{s}}(e_{s})\downarrow$.

By Lemma 3.10, there exists a monotone enumeration of a maximal universal
$(\sigma,a)$-tree $E$ satisfying $\varphi(G,x)$. Moreover, since
$\varphi(G,k+1)$ never holds, then $E$ is $k$-bounded. Since $\alpha>0$, then
$\mathcal{M}\models\mathsf{WF}(\omega^{\omega})$, hence
$\mathcal{M}\models\mathsf{BME}_{*}$, so $E$ is $M$-finite. By Lemma 3.12,
there is an extension $(\tau,c)\leq(\sigma,a)$ and some $q\in M$ such that
$(\tau,c)\Vdash\varphi(G,q-1)$ and $(\tau,c)\Vdash\neg\varphi(G,q)$. Let
$\sigma^{\prime}=\\{e<k:\Phi^{\tau\oplus Y}_{e}(e)\downarrow\\}$. Then
$(\tau,b)\Vdash(G\oplus Y)^{\prime}{\upharpoonright}k=\sigma^{\prime}$. ∎

######  Lemma 3.14.

Let $(\sigma,a)$ be a condition. For every $k\in M$, letting $\Gamma_{k}$ be
the functional of Lemma 2.7 for the order $\alpha$, there is an extension
$(\tau,b)\leq(\sigma,a)$ forcing $\Gamma^{G\oplus Y}_{k}$ to be partial.

###### Proof.

By twisting $\Gamma_{k}$, we can assume that for every $e,n\in M$, if
$\Gamma^{\sigma\oplus Y}_{k}(n)\downarrow$, then

  * •

$\Gamma^{\sigma\oplus Y}_{k}(m)\downarrow$ for every $m<n$ ;

  * •

$\Gamma^{\sigma\oplus Y}_{k}(0),\Gamma^{\sigma\oplus
Y}_{k}(1),\dots,\Gamma^{\sigma\oplus Y}_{k}(m)$ is a strictly
$<_{\epsilon_{0}}$-decreasing sequence of elements smaller than
$\beta\dottimes k$.

Let $\varphi(G,x)$ be the $\Sigma^{0}_{1}(Y)$ formula which holds if
$\Gamma^{G\oplus Y}_{k}(x)\downarrow$. By Lemma 3.10, there exists a monotone
enumeration of a maximal universal $(\sigma,a)$-tree $E$ satisfying
$\varphi(G,x)$. We have two cases.

Case 1: $E$ is $M$-finite. Then by Lemma 3.12, there is an extension
$(\tau,c)\leq(\sigma,a)$ and some $q\in M$ such that
$(\tau,c)\Vdash\varphi(G,q-1)$ and $(\tau,c)\Vdash\neg\varphi(G,q)$. In
particular, $(\tau,c)\Vdash\Gamma^{G\oplus Y}_{k}(x)\uparrow$.

Case 2: $E$ is not $M$-finite. Then there exists $M$-infinitely many stages
$s\in M$ such that $E[s]\neq E[s+1]$. By speeding up the enumeration, we can
assume without loss of generality that $E[s+1]\neq
E[s]\neq\\{\langle\rangle\\}$ for every $s\in M$.

For every $s\in M$ and $\nu\in E[s]$, let

$\zeta_{s}(\nu)=\left\\{\begin{array}[]{ll}\omega^{\Gamma_{k}^{\pi(\nu)\oplus
Y}(|\nu|-1)}&\mbox{ if }\nu\mbox{ is a leaf of }E[s]\\\
\dot{\sum}_{\mu\sqsupset_{E[s]}\nu}\zeta_{s}(\mu)&\mbox{ otherwise
}\end{array}\right.$

Finally, let $\zeta_{s}=\zeta_{s}(\langle\rangle)$.

Claim 1: _$\zeta_{s+1} <_{\epsilon_{0}}\zeta_{s}$ for all $s\in M$._ Since
$E[s+1]\neq E[s]$, there is some leaf $\nu\in E[s]$ which is not a leaf in
$E[s+1]$. By assumption on $\Gamma_{k}$, for every
$\mu\sqsupseteq_{E[s+1]}\nu$,

$\Gamma_{k}^{\pi(\mu)\oplus
Y}(|\mu|-1)<_{\epsilon_{0}}\Gamma_{k}^{\pi(\nu)\oplus Y}(|\nu|-1)$

Hence

$\dot{\sum}_{\mu\sqsupset_{E[s+1]}\nu}\omega^{\Gamma_{k}^{\pi(\mu)\oplus
Y}(|\mu|-1)}<_{\epsilon_{0}}\omega^{\Gamma_{k}^{\pi(\nu)\oplus Y}(|\nu|-1)}$

So $\zeta_{s+1}(\nu)<_{\epsilon_{0}}\zeta_{s}(\nu)$. By $\Delta^{0}_{0}$
induction along the ancestors of $\nu$ up to the root, we obtain
$\zeta_{s+1}(\langle\rangle)<_{\epsilon_{0}}\zeta_{s}(\langle\rangle)$. This
concludes our proof of Claim 1.

Claim 2: _$\zeta_{s} <_{\epsilon_{0}}\omega^{\alpha\dottimes\omega}$ for all
$s\in M$._ For all $s\in M$,
$\zeta_{s}\leq_{\epsilon_{0}}\zeta_{0}\leq_{\epsilon_{0}}\omega^{\beta\dottimes
k}<_{\epsilon_{0}}\omega^{\alpha\dottimes\omega}$.

Then Claim 1 and Claim 2 together contradict the fact that
$\mathcal{M}\models\mathsf{WF}(\omega^{\alpha\dottimes k})$.

∎

Construction We will build a decreasing sequence $(\sigma_{s},a_{s})$ of
conditions and $G$ to be the union of the $\sigma_{s}$. We will also build an
increasing sequence $(\sigma_{s}^{\prime})$ such that $G^{\prime}$ will be the
union of the $\sigma_{s}^{\prime}$. Initially we take
$\sigma_{0}=\sigma_{0}^{\prime}=\epsilon$ and $a_{0}$ an index corresponding
to $M$, and during the construction we will ensure that we have
$|\sigma_{s}|,|\sigma^{\prime}_{s}|\leq s$ and that the index $a_{s}$ is also
less than $s$ at every stage. Each stage will be either of type $\mathcal{R}$,
of type $\mathcal{S}$ or of type $\mathcal{T}$. The stage $0$ is of type
$\mathcal{R}$.

Assume that $(\sigma_{s},a_{s})$ and $\sigma^{\prime}_{s}$ are already
defined. Let $s_{0}<s$ be the latest stage at which we switched the stage
type. We have three cases.

Case 1: $s$ is of type $\mathcal{R}$. If there exists some condition
$(\sigma,a)\leq(\sigma_{s},a_{s})$ with $|\sigma|\leq s$ and $a\leq s$ such
that $(\sigma,a)\Vdash(G\oplus
Y)^{\prime}{\upharpoonright}_{s_{0}}=\sigma^{\prime}$ for a
$\sigma^{\prime}\in 2^{s_{0}}$. Then let $\sigma_{s+1}=\sigma$, $a_{s+1}=a$,
$\sigma^{\prime}_{s+1}=\sigma^{\prime}$ and let $s+1$ be of type
$\mathcal{S}$. Otherwise, the elements are left unchanged and we go to the
next stage.

Case 2: $s$ is of type $\mathcal{S}$. If there exists some condition
$(\sigma,a)\leq(\sigma_{s},a_{s})$ with $|\sigma|\leq s$ and $a\leq s$ such
that $(\sigma,a)$ forces $\Gamma_{s_{0}}^{G\oplus Y}(m)\uparrow$ for some
$m\leq s$, then let $\sigma_{s+1}=\sigma$, $a_{s+1}=a^{\prime}$,
$\sigma_{s+1}^{\prime}=\sigma^{\prime}_{s}$ and let $s+1$ be of type
$\mathcal{T}$. Otherwise, the elements are left unchanged and we go to the
next stage.

Case 3: $s$ is of type $\mathcal{T}$. If there is some condition
$(\sigma,a)\leq(\sigma_{s},a_{s})$ with $\sigma-\sigma_{s}$ non-empty,
$|\sigma|\leq s$ and $a\leq s$, then we let $\sigma_{s+1}=\sigma$, $a_{s+1}=a$
and $\sigma_{s+1}^{\prime}=\sigma_{s}^{\prime}$. Otherwise, the elements are
left unchanged and we go to the next stage.

This completes the construction.

Verification. Since the size of $\sigma_{s},\sigma^{\prime}_{s}$ and the index
$a_{s}$ are bounded by $s$, there is a $\Delta_{1}^{0}(P\oplus
Y^{\prime})$-formula $\phi(s)$ stating that the construction can be pursued up
to stage $s$. Our construction implies that the set $\\{s|\phi(s)\\}$ is
$\Delta^{0}_{1}(P)$ and a cut, so by $\mathsf{I}\Delta^{0}_{1}(P)$, the
construction can be pursued at every stage.

Let $G=\bigcup_{s\in M}\sigma_{s}$. By Lemma 3.13, Lemma 3.14, every time we
enter a stage of type $\mathcal{R}$ or $\mathcal{S}$ we eventually leave it.
Also, for every condition $(\sigma_{s},a_{s})$, we can add an element of
$X_{a_{s}}$ to $\sigma_{s}$ and then extract an infinite minimal interval from
$X_{a_{s}}$ using $P$, so every time we enter a stage of type $\mathcal{T}$,
we eventually leave it. So, each type of stage changes $M$-infinitely often.
Thus, $\\{|\sigma^{\prime}_{s}|:s\in M\\}$ is $M$-infinite, so
$P\geq_{T}(G\oplus Y)^{\prime}$. In particular,
$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$.

Moreover, the stages $s_{0}$ where we force $\mathcal{S}_{s_{0}}$ are
infinite, so for every $\beta\in\alpha$ and $e\in M$, there is a stage that
will force $\Phi^{G\oplus Y}_{e}$ not to be an $M$-infinite
$\epsilon_{0}$-decreasing sequence of elements less than $\beta$. And thus
$\Phi^{G\oplus Y}_{e}$ will not be an $M$-infinite $\alpha$-decreasing
sequence for any $e$, so $\mathcal{M}[G]\models\mathsf{WF}(\alpha)$.

The stages of type $\mathcal{T}$ happens $M$-infinitely often, so the final
set $G$ will be $M$-infinite. This completes the proof of Proposition 3.1.

∎

######  Corollary 3.15.

Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\omega^{\alpha\dottimes\omega})$
topped by a set $Y\in S$, where $\alpha\in M$ is an ordinal
$\leq\epsilon_{0}$. Then for every infinite stable tournament $R$ in $S$,
there exists $G\subseteq M$ such that

  1. 1.

$G$ is an $M$-infinite transitive subtournament ;

  2. 2.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

###### Proof.

By Theorem 2.8, there exists a set $P\subseteq M$ such that $P\gg Y^{\prime}$
and $\mathcal{M}[P]\models\mathsf{RCA}_{0}^{*}$. The conclusion follows from
Proposition 3.1. ∎

######  Theorem 3.16.

$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})+\mathsf{SEM}$
is $\Pi_{1}^{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$.

###### Proof.

Immediate by Corollary 3.15 and Theorem 2.2. ∎

###  3.2 $\Pi^{1}_{1}$-conservation of $\mathsf{SADS}$

We now turn to the proof that
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})+\mathsf{SADS}$
is a $\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$. There
exists two main constructions of solutions to instances of $\mathsf{SADS}$: an
asymmetric one, which assumes that there is no infinite computable descending
sequence, and constructs an ascending one, as in Hirschfeldt and Shore [15,
Theorem 2.11], and a symmetric one using split pairs, as in Lerman, Solomon
and Towsner [23] or Patey [27, Theorem 26]. Our proof follows the second
construction.

######  Proposition 3.17.

Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\forall
k\mathsf{WF}(\omega^{\alpha\dottimes k})$ topped by a set $Y\in S$, where
$\alpha\in M$ is an ordinal $\leq\epsilon_{0}$. Then for every linear order
$L=(M,\leq_{L})\in S$ of order type $\omega+\omega^{*}$, there exists
$G\subseteq M$ such that

  1. 1.

$G$ is an $M$-infinite ascending or descending sequence for $\leq_{L}$;

  2. 2.

$Y^{\prime}\geq_{T}(G\oplus Y)^{\prime}$ ;

  3. 3.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

###### Proof.

Let $L=(M,\leq_{L})$ be such an order, let $U\subseteq M$ and $V\subseteq M$
be the sets of elements that have a finite amount of predecessors and
successors, respectively. By assumption, $U\sqcup V=M$, and $U$ and $V$ are
both $\Delta^{0}_{2}(Y)$.

A condition is a pair $(\sigma,\tau)$ with $\sigma$ an $M$-finite
$L$-ascending sequence included in $U$ and $\tau$ an $M$-finite $L$-descending
sequence included in $V$. We have
$(\sigma_{2},\tau_{2})\leq(\sigma_{1},\tau_{1})$ if
$\sigma_{2}\succeq\sigma_{1}$ and $\tau_{2}\succeq\tau_{1}$.

Being a condition is a $\Delta_{2}^{0}(Y)$-predicate, while the extension
relation is $\Delta_{1}^{0}$.

######  Definition 3.18.

Let $(\sigma_{0},\sigma_{1})$ be a condition, $e,x\in M$ and $i<2$, we write:

  * •

$(\sigma_{0},\sigma_{1})\Vdash_{i}\Phi_{e}^{G\oplus Y}(x)\downarrow$ if
$\Phi_{e}^{\sigma_{i}\oplus Y}(x)\downarrow$.

  * •

$(\sigma_{0},\sigma_{1})\Vdash_{i}\Phi_{e}^{G\oplus Y}(x)\uparrow$ if
$\forall\sigma^{\prime}_{i}\succeq\sigma_{i}$ such that
$(\sigma^{\prime}_{i},\sigma_{1-i})$ is a split pair,
$\Phi_{e}^{\sigma^{\prime}_{i}\oplus Y}(x)\uparrow$.

We want our construction to satisfy for some $i<2$ the following requirements
for every $k\in M$:

  * •

$\mathcal{R}^{i}_{k}$: $(G_{i}\oplus Y)^{\prime}{\upharpoonright}_{k}$ is
decided.

  * •

$\mathcal{S}^{i}_{k}$: Let $\beta<\alpha$ be the $<_{\epsilon_{0}}$-biggest
ordinal of index less than $k$, for every $e<k$, $\Phi_{e}^{G_{i}\oplus Y}$ is
not an $M$-infinite $<_{\epsilon_{0}}$-decreasing sequence of elements smaller
than $\beta$.

  * •

$\mathcal{T}^{i}_{k}$: $\operatorname{card}G_{i}\geq k$.

For this, we will use a pairing argument, and ensure that for every $k\in M$,
the following requirements are met:
$\mathcal{R}^{0}_{k}\vee\mathcal{R}^{1}_{k}$,
$\mathcal{R}^{0}_{k}\vee\mathcal{S}^{1}_{k}$,
$\mathcal{S}^{0}_{k}\vee\mathcal{R}^{1}_{k}$,
$\mathcal{S}^{0}_{k}\vee\mathcal{S}^{1}_{k}$, and
$\mathcal{T}^{0}_{k}\wedge\mathcal{T}^{1}_{k}$.

######  Definition 3.19.

Fix a condition $(\sigma,\tau)$.

A _$(\sigma,\tau)$ -tree_ is a binary tree $T$ labelled by a family of split
pairs $(\sigma_{\rho},\tau_{\rho})_{\rho\in T}$ such that for all $\rho\in T$:

  * •

$\sigma\preceq\sigma_{\rho}$ and $\tau\preceq\tau_{\rho}$ ;

  * •

For every $\mu\in T$, if $\rho\cdot 0\preceq\mu$ then
$\sigma_{\rho}\preceq\sigma_{\mu}$ and if $\rho\cdot 1\preceq\mu$ then
$\tau_{\rho}\preceq\tau_{\mu}$ ;

A node $\rho$ is said to be _valid_ if the biggest index $i$ such that
$\rho(i)=0$ satisfies $\sigma_{\rho{\upharpoonright}i}\subseteq U$ (if no such
index exists this condition is verified) and if the biggest index $j$ such
that $\rho(i)=1$ satisfies $\tau_{\rho{\upharpoonright}i}\subseteq V$ (if no
such index exists this condition is verified). Being valid is a
$\Delta_{2}^{0}(Y)$ condition.

######  Definition 3.20.

Let $T$ a $(\sigma,\tau)$-tree

  * •

A node $(\sigma_{\rho},\tau_{\rho})$ in $T$ _satisfies_ a pair of
$\Sigma^{0}_{1}(Y)$-formulas $(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$ if
$\varphi_{0}(\sigma,|\rho|-\operatorname{card}\rho-1)$ and
$\varphi_{1}(\tau,\operatorname{card}\rho-1)$ holds (where
$\operatorname{card}\rho$ is the cardinal of $\rho$ seen as a set).

  * •

$T$ _satisfies_ $(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$ if every node of
$T$ satisfies it.

######  Lemma 3.21.

For every pair $(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$ of
$\Sigma^{0}_{1}(Y)$ formulas and every condition $(\sigma,\tau)$, there is a
maximal $\Sigma^{0}_{1}$ $(\sigma,\tau)$-tree $T$ satisfying it.

###### Proof.

$T$ will be the limit of the following increasing sequence of computable
$(\sigma,\tau)$-trees $(T_{s})_{s\in M}$ that all satisfy
$(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$ (and therefore $T$ will also be
a $(\sigma,\tau)$-tree satisfying
$(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$).

At stage $0$, let $T_{0}$ be the empty tree. It vacuously satisfies
$(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$.

At stage $s+1$, if there exists a split pair $(\sigma^{\prime},\tau^{\prime})$
with $|\sigma^{\prime}|,|\tau^{\prime}|\leq s$, a $\rho\in T_{s}$ and an $i<2$
with $\rho\cdot i\notin T_{s}$ such that adding $\rho\cdot i$ to $T_{s}$ with
the index $(\sigma^{\prime},\tau^{\prime})$ still yields a
$(\sigma,\tau)$-tree satisfying $(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$,
then let $T_{s+1}$ be that tree (choose the smallest split pair possible to
enfore the maximality of $T$). If no such element is found, simply go to the
next stage. ∎

######  Lemma 3.22.

Let $(\sigma,\tau)$ be a condition,
$(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$ be a pair of $\Sigma^{0}_{1}(Y)$
formulas, and $T$ be an $M$-finite maximal $(\sigma,\tau)$-tree satisfying
$(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$. Then there is an extension
$(\hat{\sigma},\hat{\tau})\leq(\sigma,\tau)$ and some $p,q\in M$ such that the
following holds:

  * •

$(\hat{\sigma},\hat{\tau})\Vdash_{0}\varphi_{0}(G_{0},p-1)$ and
$(\hat{\sigma},\hat{\tau})\Vdash_{1}\varphi_{1}(G_{1},q-1)$

  * •

$(\hat{\sigma},\hat{\tau})\Vdash_{0}\neg\varphi_{0}(G_{1},p)$ or
$(\hat{\sigma},\hat{\tau})\Vdash_{1}\neg\varphi_{1}(G_{1},q)$.

###### Proof.

Consider a valid $\rho\in T$ having no valid descendant in $T$, this is
possible since the set of valid element of $T$ is non empty because
$\pi(\epsilon)=(\sigma,\tau)$ is a condition, so by can just take a maximal
valid element of $T$ using $\mathsf{L}\Delta^{0}_{2}$ (which we have by
$\mathsf{B}\Sigma^{0}_{2}$).

We have two cases:

Case 1: $\sigma_{\rho}\subseteq U$. In that case $\rho\cdot 0\notin T$ by
maximality of $\rho$. Then take $p=|\rho|-\operatorname{card}\rho$,
$q=\operatorname{card}\rho$ and
$(\hat{\sigma},\hat{\tau})=(\sigma_{\rho},\tau_{\rho{\upharpoonright}i_{0}})$
with $i_{0}$ the biggest index $i<|\rho|$ such that $\rho(i)=1$ (if no such
index exists we take $\tau$ instead of $\tau_{\rho{\upharpoonright}i_{0}}$),
the pair $(\hat{\sigma},\hat{\tau})$ is a condition by definition of validity
and the hypothesis $\sigma_{\rho}\subseteq U$.
$(\hat{\sigma},\hat{\tau})\Vdash_{0}\varphi_{0}(G_{0},p-1)$ and
$(\hat{\sigma},\hat{\tau})\Vdash_{1}\varphi_{1}(G_{1},q-1)$ because $T$
satisfies $(\varphi_{0}(G_{0},x),\varphi_{1}(G_{1},x))$. And
$(\hat{\sigma},\hat{\tau})\Vdash_{0}\neg\varphi_{0}(G_{0},p)$ by maximality of
$T$ (Otherwise we could add $\rho\cdot 0$ to $T$ indexed by a split pair
contradicting $(\hat{\sigma},\hat{\tau})\Vdash_{0}\neg\varphi_{0}(G_{0},p)$).

Case 2: The case $\tau_{\rho}\subseteq V$ can be treated similarly.
∎

######  Lemma 3.23.

Let $k\in M$, let $\Phi_{k}(G,x)$ be the formula: $\exists
e_{0}<e_{1}<\dots<e_{x-1}<k$ such that $\Phi_{e_{i}}^{G\oplus
Y}(e_{i})\downarrow$ for all $i<x$, let $\Psi_{k}(G,x)$ be the formula:
$\Gamma^{G\oplus Y}_{k}(x)\downarrow$ (with $\Gamma_{k}$ the functional of
Lemma 2.7 for the order $\alpha$).

For any combination
$\phi_{0}(G,x),\phi_{1}(G,x)\in\\{\Phi_{k}(G,x),\Psi_{k}(G,x)\\}$ and every
condition $(\sigma,\tau)$, there exists an extension
$(\hat{\sigma},\hat{\tau})\leq(\sigma,\tau)$ and some $p,q\in M$ such that the
following holds:

  * •

$(\hat{\sigma},\hat{\tau})\Vdash_{0}\varphi_{0}(G_{0},p-1)$ and
$(\hat{\sigma},\hat{\tau})\Vdash_{1}\varphi_{1}(G_{1},q-1)$

  * •

$(\hat{\sigma},\hat{\tau})\Vdash_{0}\neg\varphi_{0}(G_{1},p)$ or
$(\hat{\sigma},\hat{\tau})\Vdash_{1}\neg\varphi_{1}(G_{1},q)$.

###### Proof.

By Lemma 3.21 there exists a maximal $\Sigma^{0}_{1}$ $(\sigma,\tau)$-tree $T$
satisfying

$(\varphi_{0}(G,x),\varphi_{1}(G,x))$

. To apply Lemma 3.22 and conclude, we just need to prove the $M$-finiteness
of $T$.

By twisting $\Gamma_{k}$, we can assume that for every $e,n\in M$, if
$\Gamma^{\sigma\oplus Y}_{k}(n)\downarrow$, then

  * •

$\Gamma^{\sigma\oplus Y}_{k}(m)\downarrow$ for every $m<n$ ;

  * •

$\Gamma^{\sigma\oplus Y}_{k}(0),\Gamma^{\sigma\oplus
Y}_{k}(1),\dots,\Gamma^{\sigma\oplus Y}_{k}(m)$ is a strictly
$<_{\epsilon_{0}}$-decreasing sequence of elements smaller than
$\beta\dottimes k$.

Assume by contradiction that $T$ is $M$-infinite and let $(T_{s})_{s\in M}$ be
an increasing sequence of computable tree approaching $T$. Without loss of
generality we can assume that $T_{s}\neq T_{s+1}$ for all $s\in M$.

For every $s\in M$ and $\rho$ node of $T_{s}$ indexed by
$(\sigma_{\rho},\tau_{\rho})$ with set of immediate successors $S_{\rho}$
($\operatorname{card}S_{\rho}\leq 2$ since $T_{s}$ is a binary tree), define
inductively :

$\zeta_{s}(\rho)=\omega^{f_{0}(\rho)\dotplus
f_{1}(\rho)}(2-\operatorname{card}S_{\rho})\ \dotplus\dot{\sum}_{\mu\in
S_{\rho}}\zeta_{s}(\mu)$

Where $f_{0}(\rho)=\Gamma_{k}^{\sigma_{\rho}\oplus
Y}(|\rho|-\operatorname{card}\rho)$ if $\varphi_{0}(G,x)=\Psi_{k}(G,x)$ and
$f_{0}(\rho)=k-(|\rho|-\operatorname{card}\rho)$ if
$\varphi_{0}(G,x)=\Phi_{k}(G,x)$. And
$f_{1}(\rho)=\Gamma_{k}^{\tau_{\rho}\oplus Y}(\operatorname{card}\rho)$ if
$\varphi_{1}(G,x)=\Psi_{k}(G,x)$ and $f_{1}(\rho)=k-\operatorname{card}\rho$
if $\varphi_{1}(G,x)=\Phi_{k}(G,x)$.

And let $\zeta_{s}=\zeta_{s}(\epsilon)$.

Claim. _The sequence $\zeta_{s}$ is an $M$-infinitely
$<_{\epsilon_{0}}$-decreasing sequence of ordinals less than
$\omega^{\alpha}$_

Let $s\in M$, since $T_{s+1}\neq T_{s}$, there is a $\rho\in T_{s}$ an $i<2$
such that $T_{s+1}=T_{s}\cup\rho\cdot i$. Therefore:

$\zeta_{s+1}(\rho)=\zeta_{s}(\rho)\dotdiv\omega^{f_{0}(\rho)\dotplus
f_{1}(\rho)}\dotplus\omega^{f_{0}(\rho\cdot i)+f_{1}(\rho\cdot i)}\dottimes 2$

But for every possible values of $\varphi_{0}$ and $\varphi_{1}$, we have
$f_{0}(\rho)>f_{0}(\rho\cdot 0)$, $f_{0}(\rho)=f_{0}(\rho\cdot 1)$,
$f_{1}(\rho)=f_{1}(\rho\cdot 0)$ and $f_{1}(\rho)>f_{1}(\rho\cdot 1)$. So for
every possible value of $i$, we have

$\omega^{f_{0}(\rho)+f_{1}(\rho)}>\omega^{f_{0}(\rho\cdot i)+f_{1}(\rho\cdot
i)}\times 2$

and therefore $\zeta_{s+1}(\rho)<\zeta_{s}(\rho)$ which gives us
$\zeta_{s+1}<\zeta_{s}$ (as $\rho\cdot i$ is the only difference between
$T_{s}$ and $T_{s+1}$).

Therefore, for all $s\in M$,
$\zeta_{s}\leq_{\epsilon_{0}}\zeta_{0}\leq_{\epsilon_{0}}\omega^{\beta\dottimes
k}<\omega^{\alpha\dottimes\omega}$.

This contradicts $\mathsf{WF}(\omega^{\alpha\dottimes\omega})$, so $T$ is
$M$-finite and the result follows. ∎

######  Remark 3.24.

If $(\sigma,\tau)\Vdash_{i}\Phi_{k}(G_{i},p-1)$ and
$(\sigma,\tau)\Vdash_{i}\neg\Phi_{k}(G_{i},p)$, then there exists a
$\rho^{\prime}\in 2^{k}$ such that $(\sigma,\tau)\Vdash_{i}(G_{i}\oplus
Y)^{\prime}{\upharpoonright}k=\rho^{\prime}$. Such a $\rho^{\prime}$ can be
found computably in $Y$.

Moreover, if $(\sigma,\tau)\Vdash_{i}\Psi_{k}(G_{i},p-1)$ and
$(\sigma,\tau)\Vdash_{i}\neg\Psi_{k}(G_{i},p)$ then
$(\sigma,\tau)\Vdash_{i}\Gamma_{s_{0}}^{G_{i}\oplus Y}(p)\uparrow$, so
$(\sigma,\tau)$ forces $\Gamma_{s_{0}}^{G_{i}\oplus Y}$ to be partial.

######  Remark 3.25.

Because of the disjunctive requirements, preservation of
$\mathsf{WF}(\epsilon_{0})$ and first jump control must be combined. Thus, at
first sight, $\mathsf{WF}(\epsilon_{0})$ is used to control the first jump.
However, if one wants to control only the first jump, no well-foundedness
assumption is necessary. Indeed, let $U$ be the set of pairs $(p,q)\in k^{2}$
such that there is a pair $(\sigma_{1},\tau_{1})$ with
$\sigma_{1}\succeq\sigma$, $\tau_{1}\succeq\tau$ and
$\max_{\mathcal{L}}\sigma_{1}<\min_{\mathcal{L}}\tau_{1}$ satisfying
$\Psi_{k}(\sigma_{1},p)$ and $\Psi_{k}(\tau_{1},q)$. Then $U$ exists by
bounded $\Sigma^{0}_{1}$ comprehension. Using this set $U$, one can find an
extension with the desired property. Therefore, one can prove that
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{SADS}$ is a
$\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$, as already proved by Chong,
Slaman and Yang [5] using the first construction.

Construction We will build a decreasing sequence $(\sigma_{s},\tau_{s})$ of
conditions and let $G_{0}$ and $G_{1}$ to be the union of the $\sigma_{s}$ and
$\tau_{s}$. We will also build two increasing sequence $(\sigma_{s}^{\prime})$
and $(\tau_{s}^{\prime})$ such that $G_{0}^{\prime}$ and $G_{1}^{\prime}$ will
be the union of the $\sigma_{s}^{\prime}$ and $\tau_{s}^{\prime}$. Initially
we take $\sigma_{0}=\sigma_{0}^{\prime}=\tau_{s}=\tau_{s}^{\prime}=\epsilon$,
and during the construction we will ensure that we have
$|\sigma_{s}|,|\sigma^{\prime}_{s}|,|\tau_{s}|,|\tau_{s}^{\prime}|\leq s$.

Each stage of the construction will be of one of the following 5 types
corresponding to the requirements: $\mathcal{R}\vee\mathcal{R}$,
$\mathcal{S}\vee\mathcal{R}$, $\mathcal{R}\vee\mathcal{S}$,
$\mathcal{S}\vee\mathcal{S}$ or of type $\mathcal{T}\wedge\mathcal{T}$. The
stage $0$ is of type $\mathcal{R}\vee\mathcal{R}$.

Assume that $(\sigma_{s},\tau_{s})$, $\sigma^{\prime}_{s}$ and
$\tau_{s}^{\prime}$ are already defined. Let $s_{0}<s$ be the latest stage at
which we switched the stage type. We have 5 cases.

Case 1: $s$ is of type $\mathcal{R}\vee\mathcal{R}$. If there exists some
condition $(\sigma,\tau)\leq(\sigma_{s},\tau_{s})$ with $|\sigma|,|\tau|\leq
s$ such that $(\sigma,\tau)\Vdash_{0}(G_{0}\oplus
Y)^{\prime}{\upharpoonright}_{s_{0}}=\sigma^{\prime}$ for a
$\sigma^{\prime}\in 2^{s_{0}}$ or $(\sigma,\tau)\Vdash_{1}(G_{1}\oplus
Y)^{\prime}{\upharpoonright}_{s_{0}}=\tau^{\prime}$ for a $\tau^{\prime}\in
2^{s_{0}}$. Then let $\sigma_{s+1}=\sigma$, $\tau_{s+1}=\tau_{s}$, and if we
are in the first case, let $\sigma^{\prime}_{s+1}=\sigma^{\prime}$ and
$\tau^{\prime}_{s+1}=\tau^{\prime}_{s}$ and in the second case let
$\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$ and
$\tau^{\prime}_{s+1}=\tau^{\prime}$. Then let $s+1$ be of type
$\mathcal{R}\vee\mathcal{S}$. Otherwise, the elements are left unchanged and
we go to the next stage.

Case 2: $s$ is of type $\mathcal{R}\vee\mathcal{S}$. If there exists some
condition $(\sigma,\tau)\leq(\sigma_{s},\tau_{s})$ with $|\sigma|,|\tau|\leq
s$ such that $(\sigma,\tau)\Vdash_{0}(G_{0}\oplus
Y)^{\prime}{\upharpoonright}_{s_{0}}=\sigma^{\prime}$ for a
$\sigma^{\prime}\in 2^{s_{0}}$ or
$(\sigma,\tau)\Vdash_{1}\Gamma_{s_{0}}^{G_{1}\oplus Y}partial$. Then let
$\sigma_{s+1}=\sigma$, $\tau_{s+1}=\tau_{s}$, and if we are in the first case,
let $\sigma^{\prime}_{s+1}=\sigma^{\prime}$ and
$\tau^{\prime}_{s+1}=\tau^{\prime}_{s}$ and in the second case let
$\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$ and
$\tau^{\prime}_{s+1}=\tau^{\prime}_{s}$. Then let $s+1$ be of type
$\mathcal{S}\vee\mathcal{R}$. Otherwise, the elements are left unchanged and
we go to the next stage.

Case 3: $s$ is of type $\mathcal{S}\vee\mathcal{R}$. If there exists some
condition $(\sigma,\tau)\leq(\sigma_{s},\tau_{s})$ with $|\sigma|,|\tau|\leq
s$ such that $(\sigma,\tau)\Vdash_{0}\Gamma_{s_{0}}^{G_{0}\oplus Y}partial$ or
$(\sigma,\tau)\Vdash_{1}(G_{1}\oplus
Y)^{\prime}{\upharpoonright}_{s_{0}}=\tau^{\prime}$ for a $\tau^{\prime}\in
2^{s_{0}}$. Then let $\sigma_{s+1}=\sigma$, $\tau_{s+1}=\tau_{s}$, and if we
are in the first case, let $\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$ and
$\tau^{\prime}_{s+1}=\tau^{\prime}_{s}$ and in the second case let
$\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$ and
$\tau^{\prime}_{s+1}=\tau^{\prime}$. Then let $s+1$ be of type
$\mathcal{S}\vee\mathcal{S}$. Otherwise, the elements are left unchanged and
we go to the next stage.

Case 4: $s$ is of type $\mathcal{S}\vee\mathcal{S}$. If there exists some
condition $(\sigma,\tau)\leq(\sigma_{s},\tau_{s})$ with $|\sigma|,|\tau|\leq
s$ such that $(\sigma,\tau)\Vdash_{0}\Gamma_{s_{0}}^{G_{0}\oplus Y}partial$ or
$(\sigma,\tau)\Vdash_{1}\Gamma_{s_{0}}^{G_{1}\oplus Y}partial$. Then let
$\sigma_{s+1}=\sigma$, $\tau_{s+1}=\tau_{s}$, and if we are in the first case,
let $\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$ and
$\tau^{\prime}_{s+1}=\tau^{\prime}_{s}$ and in the second case let
$\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$ and
$\tau^{\prime}_{s+1}=\tau_{s}^{\prime}$. Then let $s+1$ be of type
$\mathcal{T}$. Otherwise, the elements are left unchanged and we go to the
next stage.

Case 5: $s$ is of type $\mathcal{T}$. If there exists some condition
$(\sigma,\tau)\leq(\sigma_{s},\tau_{s})$ with $\\#\sigma>\\#\sigma_{s}$ and
$\\#\tau>\\#\tau_{s}$, then let $\sigma_{s+1}=\sigma$, $\tau_{s+1}=\tau$,
$\sigma^{\prime}_{s+1}=\sigma^{\prime}_{s}$ and
$\tau^{\prime}_{s+1}=\tau^{\prime}_{s}$. Then let $s+1$ be of type
$\mathcal{R}\vee\mathcal{R}$. Otherwise, the elements are left unchanged and
we go to the next stage.

This completes the construction.

Verification. Since the size of $\sigma_{s},\tau_{s},\sigma^{\prime}_{s}$ and
$\tau_{s}$ are bounded by $s$, there is a $\Delta_{2}^{0}(Y)$-formula
$\phi(s)$ stating that the construction can be pursued up to stage $s$. Our
construction implies that the set $\\{s|\phi(s)\\}$ is a cut, so by
$\mathsf{I}\Delta^{0}_{2}(Y)$, the construction can be pursued at every stage.

Let $G_{0}=\bigcup_{s\in M}\sigma_{s}$ and $G_{1}=\bigcup_{s\in M}\tau_{s}$.
By Lemma 3.23, and the fact that $U$ and $V$ are $M$-infinite, each type of
stage changes $M$-infinitely often. Thus, for $M$-infinitely many $k$’s, the
four requirements $\mathcal{R}^{0}_{k}\vee\mathcal{R}^{1}_{k}$,
$\mathcal{S}^{0}_{k}\vee\mathcal{R}^{1}_{k}$,
$\mathcal{R}^{0}_{k}\vee\mathcal{S}^{1}_{k}$ and
$\mathcal{S}^{0}_{k}\vee\mathcal{S}^{1}_{k}$ are satisfied and $G_{0}$ and
$G_{1}$ are $M$-infinite.

So, for $M$-infinitely many $k$’s,
$(\mathcal{R}^{0}_{k}\wedge\mathcal{S}^{0}_{k})\vee(\mathcal{R}^{1}_{k}\wedge\mathcal{S}^{1}_{k})$
is satisfied which gives us an $i<2$ such that $G_{i}$ is an ascending or
descending sequence, $Y^{\prime}\geq_{T}(G_{i}\oplus Y)^{\prime}$ and
therefore $\mathcal{M}[G_{i}]\models\mathsf{B}\Sigma^{0}_{2}$ and
$\mathcal{M}[G_{i}]\models\mathsf{WF}(\alpha)$. This completes the proof of
Proposition 3.17. ∎

######  Theorem 3.26.

$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})+\mathsf{SADS}$
is $\Pi_{1}^{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$.

###### Proof.

Immediate by Proposition 3.17 and Theorem 2.2. ∎

##  4 $\Pi_{1}^{1}$-conservation of $\mathsf{RT}_{2}^{2}$

Thanks to the decomposition of Proposition 1.16, we can combine the
conservation theorems developed in Section 2 and Section 3 to prove our main
theorems. Yokoyama [33] proved the following amalgamation theorem:

######  Theorem 4.1 ([33]).

Let $T_{0},T_{1},T_{2}$ be $\Pi^{1}_{2}$ theories such that
$T_{0}\supseteq\mathsf{RCA}_{0}$ and $T_{1}$ and $T_{2}$ are both
$\Pi^{1}_{1}$-conservative extensions of $T_{0}$. Then $T_{1}+T_{2}$ is a
$\Pi^{1}_{1}$-conservative extension of $T_{0}$.

In particular, letting $T_{0}$ be
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$, one can
combine Theorem 2.15, Theorem 2.21, Theorem 3.16 and Theorem 3.26 to deduce
that
$\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}+\mathsf{WKL}+\mathsf{WF}(\epsilon_{0})$
is a $\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$. We
shall however provide a direct proof using $\omega$-extensions with the
following proposition.

######  Proposition 4.2.

Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\omega_{4}^{\alpha})$
topped by a set $Y\in S$, where $\alpha\in M$ is an ordinal
$\leq\epsilon_{0}$. Then, for every coloring $f:[M]^{2}\to 2$ in $S$ and every
set $P\gg Y^{\prime}$ such that $\mathcal{M}[P]\models\mathsf{RCA}_{0}^{*}$,
there exists $G\subseteq M$ such that

  1. 1.

$G$ is an $M$-infinite $f$-homogeneous set ;

  2. 2.

$P\geq_{T}(G\oplus Y)^{\prime}$ ;

  3. 3.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

###### Proof.

By Fiori-Carones et al [11, Lemma 3.2], there exists a $P$-computable
countable coded model of $\mathsf{WKL}_{0}^{*}$ containing $Y^{\prime}$. In
particular, there exists a set $P_{0}\subseteq M$ such that $P\gg P_{0}\gg
Y^{\prime}$. Let $\vec{R}=R_{0},R_{1},\dots$ be defined by
$R_{x}=\\{y:f(x,y)=1\\}$. By Proposition 2.9 applied to $\mathcal{M}$ and
$P_{0}$, there exists some $M$-infinite $\vec{R}$-cohesive set $G_{0}\subseteq
M$ such that $P_{0}\geq_{T}(G_{0}\oplus Y)^{\prime}$ and
$\mathcal{M}[G_{0}]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\omega_{3}^{\alpha})$.
In particular, $f:[G_{0}]^{2}\to 2$ is stable. One can see $f:[G_{0}]^{2}\to
2$ as an instance of $\mathsf{SEM}$. By Proposition 3.1 applied to
$\mathcal{M}[G_{0}]$ and $P$, there exists some $M$-infinite $f$-transitive
set $G_{1}\subseteq G_{0}$ such that $P\geq_{T}(G_{1}\oplus G_{0}\oplus
Y)^{\prime}$ and $\mathcal{M}[G_{1}\oplus
G_{0}]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\omega_{2}^{\alpha})$.
One can see $f:[G_{1}]^{2}\to 2$ as an instance of $\mathsf{SADS}$. By
Proposition 3.17 applied to $\mathcal{M}[G_{0}\oplus G_{1}]$ and $P$, there
exists some $M$-infinite $f$-homogeneous set $G\subseteq G_{1}$ such that
$P\geq_{T}(G\oplus G_{1}\oplus G_{0}\oplus Y)^{\prime}$ and
$\mathcal{M}[G\oplus G_{1}\oplus
G_{0}]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$. ∎

######  Corollary 4.3.

Fix $n\geq 2$. Let $T_{n}$ be either $\mathsf{B}\Sigma^{0}_{n}$ or
$\mathsf{I}\Sigma^{0}_{n}$. Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\omega_{4}^{\alpha})$
topped by a set $Y\in S$, where $\alpha\in M$ is an ordinal
$\leq\epsilon_{0}$. Then, for every coloring $f:[M]^{2}\to 2$ in $S$, there
exists $G\subseteq M$ such that

  1. 1.

$G$ is an $M$-infinite $f$-homogeneous set ;

  2. 2.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\alpha)$.

###### Proof.

By Harrington; Simpson–Smith; Hajek (see Belanger [1]), every countable topped
model of $\mathsf{RCA}_{0}^{*}+T_{n-1}$ can be $\omega$-extended into a model
of $\mathsf{RCA}_{0}^{*}+T_{n-1}+\mathsf{WKL}$. Since
$\mathcal{M}[Y^{\prime}]\models\mathsf{RCA}_{0}^{*}+T_{n-1}$, there is some
$P\subseteq M$ such that $P\gg Y^{\prime}$ and
$\mathcal{M}[P]\models\mathsf{RCA}_{0}^{*}+T_{n-1}$. By Proposition 4.2, there
exists $G\subseteq M$ such that

  1. 1.

$G$ is an $M$-infinite $f$-homogeneous set ;

  2. 2.

$P\geq_{T}(G\oplus Y)^{\prime}$ ;

  3. 3.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$.

Since every $\Sigma^{0}_{n}$ formula in $\mathcal{M}[G]$ is $\Sigma^{0}_{n-1}$
in $\mathcal{M}[P]$ and $\mathcal{M}[P]\models T_{n-1}$, then
$\mathcal{M}[G]\models T_{n}$. ∎

######  Main Theorem 1.6.

Fix $n\geq 2$. Let $T_{n}$ be either $\mathsf{B}\Sigma^{0}_{n}$ or
$\mathsf{I}\Sigma^{0}_{n}$.
$\mathsf{RCA}_{0}+T_{n}+\mathsf{RT}^{2}_{2}+\mathsf{WKL}+\mathsf{WF}(\epsilon_{0})$
is a $\Pi^{1}_{1}$-conservative extension of
$\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\epsilon_{0})$.

###### Proof.

From Corollary 4.3, Proposition 2.16 and Theorem 2.2, we get the
$\Pi_{1}^{1}$-conservativity of $\mathsf{WKL}+\mathsf{RT}^{2}_{2}$ over
$\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\epsilon_{0})$. ∎

###  4.1 Preserving $\bigcup_{n}\mathsf{WF}(\omega_{n})$

In their proof that $\mathsf{RT}^{2}_{2}$ does not imply
$\mathsf{I}\Sigma^{0}_{2}$ over $\mathsf{RCA}_{0}$, Chong, Slaman and Yang [6]
started with a model satisfying a slightly weaker well-foundedness axiom than
$\mathsf{WF}(\epsilon_{0})$, namely, $\bigcup_{n}\mathsf{WF}(\omega_{n})$. We
show that our assumption can also be weakened to
$\bigcup_{k}\mathsf{WF}(\omega^{\omega}_{k})$ with a little bit of extra work.

######  Theorem 4.4.

Fix $n\geq 2$. Let $T_{n}$ be either $\mathsf{B}\Sigma^{0}_{n}$ or
$\mathsf{I}\Sigma^{0}_{n}$. Let $\mathsf{P}$ be a $\Pi_{2}^{1}$ problem such
that for every countable topped model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\omega_{k}^{\alpha})$
with $\alpha\in M$ an ordinal less than $\epsilon_{0}$ and $k$ a standard
integer and every instance of $\mathsf{P}$ in $\mathcal{M}$ there exists a
solution $G\subset M$ of that instance such that
$\mathcal{M}[G]\models\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\alpha)$. Then
$\mathsf{P}$ is $\Pi_{1}^{1}$-conservative over
$\mathsf{RCA}_{0}+T_{n}+\bigcup_{k\in\omega}\mathsf{WF}(\omega^{\omega}_{k})$.

###### Proof.

Assume
$\mathsf{RCA}_{0}+T_{n}+\bigcup_{n\in\omega}\mathsf{WF}(\omega_{n})\not\vdash\forall
X\phi(X)$ for $\phi$ arithmetical.

Extend the language of second order arithmetics with a first-order constant
symbol $c$. The theory
$\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\omega_{c})+\bigcup_{k\in\omega}c>k+\exists
X\neg\phi(X)$ is finitely satisfiable by our assumption, so by compactness we
have a model
$\mathcal{M}\models\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\omega_{c})+\bigcup_{k\in\omega}c>k+\exists
X\neg\phi(X)$. Such a $c$ will therefore be non-standard.

From our assumption, for any countable topped model
$\mathcal{N}=(N,S)\models\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\omega_{d+k})$ and
instance of $\mathsf{P}$ in this model, we can find a countable topped
$\omega$-extension that will be a model of
$\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\omega_{d})$ and will contain a solution
to that instance.

So by iterating that reasoning, we can build a sequence
$\mathcal{M}_{0}=\mathcal{M}\subseteq\mathcal{M}_{1}\subseteq\dots$ of
countable topped model such that
$\mathcal{M}_{s}\models\mathsf{RCA}_{0}+T_{n}+\mathsf{WF}(\omega_{c-ks})$ and
such that every instance of $P$ appearing inside one $\mathcal{M}_{i}$ will
eventually have a solution in one $\mathcal{M}_{j}$. Since $c$ is non-standard
and every such $s$ is standard, every $\mathcal{M}_{i}$ is a model of
$\bigcup_{k\in\omega}\mathsf{WF}(\omega^{\omega}_{k})$, and the model
$\bigcup_{s\in\omega}\mathcal{M}_{s}$ will therefore be a model of
$\mathsf{RCA}_{0}+T_{n}+\bigcup_{k\in\omega}\mathsf{WF}(\omega^{\omega}_{k})+\exists
X\neg\phi(X)+\mathsf{P}$.

So
$\mathsf{RCA}_{0}+T_{n}+\bigcup_{k\in\omega}\mathsf{WF}(\omega^{\omega}_{k})+\mathsf{P}\not\vdash\forall
X\phi(X)$. ∎

######  Main Theorem 1.7.

Fix $n\geq 2$. Let $T_{n}$ be either $\mathsf{B}\Sigma^{0}_{n}$ or
$\mathsf{I}\Sigma^{0}_{n}$.
$\mathsf{RCA}_{0}+T_{n}+\bigcup_{k\in\omega}\mathsf{WF}(\omega^{\omega}_{k})+\mathsf{RT}_{2}^{2}+\mathsf{WKL}$
is $\Pi_{1}^{1}$-conservative over
$\mathsf{RCA}_{0}+T_{n}+\bigcup_{k\in\omega}\mathsf{WF}(\omega^{\omega}_{k})$.

###### Proof.

From Corollary 4.3, Proposition 2.16 and Theorem 4.4, we get the
$\Pi_{1}^{1}$-conservativity of
$\mathsf{RCA}_{0}+T_{n}+\mathsf{RT}^{2}_{2}+\mathsf{WKL}$ over
$\mathsf{RCA}_{0}+T_{n}+\bigcup_{k\in\omega}\mathsf{WF}(\omega^{\omega}_{k})$.
∎

######  Remark 4.5.

The combination of Proposition 2.9, Proposition 3.1 and Proposition 3.17
provides the $\ll_{2}$-basis theorem for $\mathsf{RT}^{2}_{2}$ while
preserving $\mathsf{WF}(\epsilon_{0})$ (see [11, Definition 4.9]). This
implies that there exists a polynomial proof transformation for the
$\Pi^{1}_{1}$-conservation for 1.6 (it will appear in the forthcoming thesis
of H. Ikari). On the other hand, it is not clear whether there exists a
polynomial proof transformation for 1.7.

###  4.2 Preserving $\mathsf{I}\Sigma^{0}_{n}$ and
$\mathsf{B}\Sigma^{0}_{n+1}$ for $n\geq 2$

One can use the previous theorems to reprove a known conservation result over
$\mathsf{I}\Sigma^{0}_{2}$.

######  Proposition 4.6.

Fix $n\geq 2$ and let $T_{n}$ be either $\mathsf{I}\Sigma^{0}_{n}$, or
$\mathsf{B}\Sigma^{0}_{n+1}$. Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+T_{n-1}$ topped by a set $Y\in S$.
Then, for every coloring $f:[M]^{2}\to 2$ in $S$ and every set $P\gg
Y^{\prime}$ such that $\mathcal{M}[P]\models\mathsf{RCA}_{0}$, there exists
$G\subseteq M$ such that

  1. 1.

$G$ is an $M$-infinite $f$-homogeneous set ;

  2. 2.

$P\geq_{T}(G\oplus Y)^{\prime}$ ;

  3. 3.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+T_{n}$.

###### Proof.

By Fiori-Carones et al [11, Lemma 3.2], there exists a $P$-computable
countable coded model of $\mathsf{WKL}_{0}^{*}$ containing $Y^{\prime}$. In
particular, there exists a set $P_{0}\subseteq M$ such that $P\gg P_{0}\gg
Y^{\prime}$. Moreover, $\mathcal{M}[P]$ and $\mathcal{M}[P_{0}]$ both satisfy
$T_{n-1}$.

Let $\vec{R}=R_{0},R_{1},\dots$ be defined by $R_{x}=\\{y:f(x,y)=1\\}$. By
Proposition 2.9 applied to $\mathcal{M}$, $P_{0}$ and $\alpha=1$, there exists
some $M$-infinite $\vec{R}$-cohesive set $G_{0}\subseteq M$ such that
$P_{0}\geq_{T}(G_{0}\oplus Y)^{\prime}$ and
$\mathcal{M}[G_{0}]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$. In
particular, $f:[G_{0}]^{2}\to 2$ is stable. Since any
$\Sigma^{0}_{n}(G_{0}\oplus Y)$ formula is $\Sigma^{0}_{n-1}(P_{0})$, and
$\mathcal{M}[P_{0}]\models T_{n-1}$, then $\mathcal{M}[G_{0}]\models T_{n}$.
In particular, since
$\mathsf{RCA}_{0}+T_{n}\vdash\mathsf{WF}(\omega^{\omega}$,
$\mathcal{M}[G_{0}]\models\mathsf{WF}(\omega^{\omega})$.

One can see $f:[G_{0}]^{2}\to 2$ as an instance of $\mathsf{SEM}$. By
Proposition 3.1 applied to $\mathcal{M}[G_{0}]$, $P$ and $\alpha=1$, there
exists some $M$-infinite $f$-transitive set $G_{1}\subseteq G_{0}$ such that
$P\geq_{T}(G_{1}\oplus G_{0}\oplus Y)^{\prime}$. Here again, since any
$\Sigma^{0}_{n}(G_{1}\oplus G_{0}\oplus Y)$ formula is $\Sigma^{0}_{n-1}(P)$
and $\mathcal{M}[P]\models T_{n-1}$, then $\mathcal{M}[G_{1}\oplus
G_{0}]\models T_{n}$.

One can see $f:[G_{1}]^{2}\to 2$ as an instance of $\mathsf{SADS}$. By
Proposition 3.17 applied to $\mathcal{M}[G_{0}\oplus G_{1}]$, $P$ and
$\alpha=0$, there exists some $M$-infinite $f$-homogeneous set $G\subseteq
G_{1}$ such that $P\geq_{T}(G\oplus G_{1}\oplus G_{0}\oplus Y)^{\prime}$ and
$\mathcal{M}[G\oplus G_{1}\oplus
G_{0}]\models\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$. Still by the same
argument, $\mathcal{M}[G\oplus G_{1}\oplus G_{0}]\models T_{n}$. ∎

######  Remark 4.7.

Contrary to Proposition 2.9 and Proposition 3.17 in which the well-foundedness
hypothesis on the ground model is only used to preserve well-foundedness, in
the proof of Proposition 3.1, one exploits $\mathsf{WF}(\omega^{\omega})$ to
preserve $\mathsf{B}\Sigma^{0}_{2}$, and one uses
$\mathsf{WF}(\omega^{\omega^{\omega}\dottimes\omega})$ to preserve
$\mathsf{WF}(\omega^{\omega})$. If one starts with a model of
$\mathsf{I}\Sigma^{0}_{2}$, the ground model is therefore also a model of
$\mathsf{WF}(\omega^{\omega})$, in which case $\mathsf{B}\Sigma^{0}_{2}$ can
be preserved. Thanks to the first-jump control, $\mathsf{I}\Sigma^{0}_{2}$ is
actually preserved, and therefore so is $\mathsf{WF}(\omega^{\omega})$.

Since $\mathsf{I}\Sigma^{0}_{2}$ and
$\mathsf{WF}(\omega^{\omega^{\omega}\dottimes\omega})$ are incomparable over
$\mathsf{RCA}_{0}$, it would be interesting to investigate the common factor
between these two statements which is sufficient to preserve
$\mathsf{WF}(\omega^{\omega})$.

######  Corollary 4.8.

Fix $n\geq 2$ and let $T_{n}$ be either $\mathsf{I}\Sigma^{0}_{n}$, or
$\mathsf{B}\Sigma^{0}_{n+1}$. Consider a countable model
$\mathcal{M}=(M,S)\models\mathsf{RCA}_{0}+T_{n}$ topped by a set $Y\in S$.
Then, for every coloring $f:[M]^{2}\to 2$ in $S$, there exists $G\subseteq M$
such that

  1. 1.

$G$ is an $M$-infinite $f$-homogeneous set ;

  2. 2.

$\mathcal{M}[G]\models\mathsf{RCA}_{0}+T_{n}$.

###### Proof.

By Harrington; Simpson–Smith; Hajek (see Belanger [1]), every countable topped
model of $\mathsf{RCA}_{0}^{*}+T_{n-1}$ can be $\omega$-extended into a model
of $\mathsf{RCA}_{0}^{*}+T_{n-1}+\mathsf{WKL}$. Since
$\mathcal{M}[Y^{\prime}]\models\mathsf{RCA}_{0}^{*}+T_{n-1}$, there is some
$P\subseteq M$ such that $P\gg Y^{\prime}$ and
$\mathcal{M}[P]\models\mathsf{RCA}_{0}^{*}+T_{n-1}$. The conclusion follows
from Proposition 4.6. ∎

######  Corollary 4.9 (Cholak, Jockusch and Slaman [3]).

Fix $n\geq 2$ and let $T_{n}$ be either $\mathsf{I}\Sigma^{0}_{n}$, or
$\mathsf{B}\Sigma^{0}_{n+1}$. $\mathsf{RCA}_{0}+T_{n}+\mathsf{RT}^{2}_{2}$ is
$\Pi^{1}_{1}$-conservative over $\mathsf{RCA}_{0}+T_{n}$.

##  5 Open questions

Many open questions remain around the first-order part of Ramsey’s theorem for
pairs and its consequences. The first and most important question being the
following:

######  Question 5.1.

Is $\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}$ $\Pi^{1}_{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$?

For every $\alpha<\epsilon_{0}$,
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)+\mathsf{WKL}+\mathsf{COH}$
is $\Pi^{1}_{1}$ conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$. The situation
seems more complex for $\mathsf{ADS}$ and $\mathsf{EM}$, which both seem to
require $\mathsf{WF}(\omega^{\alpha\dottimes\omega})$ to preserve
$\mathsf{WF}(\alpha)$.

######  Question 5.2.

For which $\alpha<\epsilon_{0}$ is
$\mathsf{RCA}_{0}+\mathsf{WF}(\alpha)+\mathsf{RT}^{2}_{2}$
$\Pi^{1}_{1}$-conservative over
$\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}+\mathsf{WF}(\alpha)$?

The proofs of Proposition 3.1 and Proposition 3.17 required the ground model
to satisfy $\mathsf{WF}(\omega^{\alpha})$ to preserve $\mathsf{WF}(\alpha)$.
It is natural to wonder whether this assumption is necessary. One way to
formalize this idea would be to prove that
$\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}\rightarrow\forall
n(\mathsf{WF}(\omega_{n})\rightarrow\mathsf{WF}(\omega_{n+1}))$, where
$\omega_{0}=1$ and $\omega_{n+1}=\omega^{\omega_{n}}$. This is not the case,
as $\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}$ is $\forall\Pi^{0}_{3}$-conservative
over $\mathsf{RCA}_{0}$, hence does not prove $\mathsf{WF}(\omega^{\omega})$.
One could also wonder whether $\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}$ proves
some weaker well-foundedness closure properties which do not already follow
from $\mathsf{RCA}_{0}+\mathsf{B}\Sigma^{0}_{2}$. Here again, the answer is
negative. Le Houérou and Levy Patey constructed a model $\mathcal{M}=(M,S)$ of
$\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}$ in which $\\{b\in
M:\mathcal{M}\models\mathsf{WF}(\omega^{b})\\}=\sup\\{a\cdot k:k\in\omega\\}$
for some $a\in M\setminus\omega$. In other words, this cut has no better
closure properties than additivity [personal communication]. This result is
tight, as $\mathsf{RCA}_{0}\vdash\forall
a(\mathsf{WF}(\omega^{a})\rightarrow\mathsf{WF}(\omega^{2a}))$. Note that one
can also show that $\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}$ does not prove
$\forall n(\mathsf{WF}(\omega^{n})\rightarrow\mathsf{WF}(\omega^{2^{n}}))$
using proof length. Indeed, by Kołodziejczyk, Wong and Yokoyama [19],
$\mathsf{RCA}_{0}+\mathsf{RT}^{2}_{2}$ does not have speedup over
$\mathsf{RCA}_{0}$ for $\forall\Pi^{0}_{3}$ consequences, but in an incoming
paper, Kołodziejczyk and Yokoyama [personal communication] proved that
$\mathsf{RCA}_{0}+\forall
n(\mathsf{WF}(\omega^{n})\rightarrow\mathsf{WF}(\omega^{2^{n}}))$ has super-
exponential speedup over $\mathsf{RCA}_{0}$ for $\forall\Pi^{0}_{3}$
consequences.

Acknowledgements

The authors are thankful to Leszek Kołodziejczyk for his careful reading and
his improvement suggestions.

## References

  * [1] David R. Bélanger.  Conservation theorems for the cohesiveness principle.  2022\.  Available at https://arxiv.org/abs/2212.13011.
  * [2] Andrey Bovykin and Andreas Weiermann.  The strength of infinitary Ramseyan principles can be accessed by their densities.  Ann. Pure Appl. Logic, 168(9):1700–1709, 2017.
  * [3] Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman.  On the strength of Ramsey’s theorem for pairs.  The Journal of Symbolic Logic, 66(1):1–55, 2001.
  * [4] C. T. Chong and K. J. Mourad.  The degree of a $\Sigma_{n}$ cut.  Ann. Pure Appl. Logic, 48(3):227–235, 1990.
  * [5] C. T. Chong, Theodore A. Slaman, and Yue Yang.  $\Pi^{1}_{1}$-conservation of combinatorial principles weaker than Ramsey’s theorem for pairs.  Adv. Math., 230(3):1060–1077, 2012.
  * [6] C. T. Chong, Theodore A. Slaman, and Yue Yang.  The inductive strength of Ramsey’s Theorem for Pairs.  Adv. Math., 308:121–141, 2017.
  * [7] Damir D. Dzhafarov and Carl Mummert.  Reverse mathematics—problems, reductions, and proofs.  Theory and Applications of Computability. Springer, Cham, [2022] ©2022.
  * [8] Benedict Eastaugh.  Slicing the truth: on the computability theoretic and reverse mathematical analysis of combinatorial principles [book review of MR3244278].  Studia Logica, 105(4):873–879, 2017.
  * [9] P. Erdős and L. Moser.  On the representation of directed graphs as unions of orderings.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:125–132, 1964\.
  * [10] António M. Fernandes, Fernando Ferreira, and Gilda Ferreira.  Analysis in weak systems.  In Logic and computation, volume 33 of Tributes, pages 231–261. Coll. Publ., [London], 2017.
  * [11] Marta Fiori-Carones, Leszek Aleksander Kołodziejczyk, Tin Lok Wong, and Keita Yokoyama.  An isomorphism theorem for models of Weak König’s Lemma without primitive recursion.  Journal of the European Mathematical Society, 2021.  To appear.
  * [12] Petr Hájek.  Interpretability and fragments of arithmetic.  In Arithmetic, proof theory, and computational complexity (Prague, 1991), volume 23 of Oxford Logic Guides, pages 185–196. Oxford Univ. Press, New York, 1993.
  * [13] Petr Hájek and Pavel Pudlák.  Metamathematics of first-order arithmetic, volume 3.  Cambridge University Press, 2017.
  * [14] Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman.  The strength of some combinatorial principles related to Ramsey’s theorem for pairs.  In Computational prospects of infinity. Part II. Presented talks, volume 15 of Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., pages 143–161. World Sci. Publ., Hackensack, NJ, 2008.
  * [15] Denis R. Hirschfeldt and Richard A. Shore.  Combinatorial principles weaker than Ramsey’s theorem for pairs.  Journal of Symbolic Logic, 72:171 – 206, 2007.
  * [16] Jeffry Lynn Hirst.  COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC.  ProQuest LLC, Ann Arbor, MI, 1987.  Thesis (Ph.D.)–The Pennsylvania State University.
  * [17] Carl Jockusch and Frank Stephan.  A cohesive set which is not high.  Math. Logic Quart., 39(4):515–530, 1993.
  * [18] Carl G. Jockusch, Jr.  Ramsey’s theorem and recursion theory.  J. Symbolic Logic, 37:268–280, 1972.
  * [19] Leszek Aleksander Kołodziejczyk, Tin Lok Wong, and Keita Yokoyama.  Ramsey’s theorem for pairs, collection, and proof size.  Journal of Mathematical Logic, page 2350007, 2023.
  * [20] Leszek Aleksander Kołodziejczyk and Keita Yokoyama.  In search of the first-order part of Ramsey’s theorem for pairs.  In Connecting with computability, volume 12813 of Lecture Notes in Comput. Sci., pages 297–307. Springer, Cham, [2021] ©2021.
  * [21] Alexander P. Kreuzer.  Primitive recursion and the chain antichain principle.  Notre Dame J. Form. Log., 53(2):245–265, 2012.
  * [22] Alexander P. Kreuzer and Keita Yokoyama.  On principles between $\Sigma_{1}$\- and $\Sigma_{2}$-induction, and monotone enumerations.  J. Math. Log., 16(1):1650004, 21, 2016.
  * [23] Manuel Lerman, Reed Solomon, and Henry Towsner.  Separating principles below Ramsey’s theorem for pairs.  J. Math. Log., 13(2):1350007, 44, 2013.
  * [24] Jiayi Liu.  RT22 does not imply WKL0.  The Journal of Symbolic Logic, 77(2):609–620, 2012.
  * [25] Joseph Roy Mileti.  Partition theorems and computability theory.  ProQuest LLC, Ann Arbor, MI, 2004.  Thesis (Ph.D.)–University of Illinois at Urbana-Champaign.
  * [26] Benoit Monin and Ludovic Patey.  $\mathsf{SRT}^{2}_{2}$ does not imply $\mathsf{RT}^{2}_{2}$ in $\omega$-models.  Adv. Math., 389:Paper No. 107903, 32, 2021.
  * [27] Ludovic Patey.  Partial orders and immunity in reverse mathematics.  Computability, 7(4):323–339, 2018.
  * [28] Ludovic Patey and Keita Yokoyama.  The proof-theoretic strength of Ramsey’s theorem for pairs and two colors.  Adv. Math., 330:1034–1070, 2018.
  * [29] David Seetapun and Theodore A. Slaman.  On the strength of Ramsey’s theorem.  volume 36, pages 570–582. 1995.  Special Issue: Models of arithmetic.
  * [30] Stephen G. Simpson.  Subsystems of Second Order Arithmetic.  Perspectives in Logic. Cambridge University Press, 2 edition, 2009.
  * [31] Stephen G. Simpson and Rick L. Smith.  Factorization of polynomials and $\Sigma^{0}_{1}$ induction.  volume 31, pages 289–306. 1986.  Special issue: second Southeast Asian logic conference (Bangkok, 1984).
  * [32] Theodore A. Slaman.  $\Sigma_{n}$-bounding and $\Delta_{n}$-induction.  Proc. Amer. Math. Soc., 132(8):2449–2456, 2004.
  * [33] Keita Yokoyama.  On conservativity for theories in second order arithmetic.  In Proceedings of the 10th Asian Logic Conference, pages 375–386. World Scientific, 2010.