# The weakness of the Erdős-Moser theorem
under arithmetic reductions

Ludovic Levy Patey  CNRS, IMJ-PRG
Université Paris Cité
Paris, France  Ahmed Mimouni  Univ Paris Est Creteil, LACL, F-94010 Creteil,
France

###### Abstract

The Erdős-Moser theorem ($\mathsf{EM}$) says that every infinite tournament
admits an infinite transitive subtournament. We study the computational
behavior of the Erdős-Moser theorem with respect to the arithmetic hierarchy,
and prove that $\Delta^{0}_{n}$ instances of $\mathsf{EM}$ admit lown+1
solutions for every $n\geq 1$, and that if a set $B$ is not arithmetical, then
every instance of $\mathsf{EM}$ admits a solution relative to which $B$ is
still not arithmetical. We also provide a level-wise refinement of this
theorem. These results are part of a larger program of computational study of
combinatorial theorems in Reverse Mathematics.

##  1 Introduction

We conduct a computational study of the Erdős-Moser theorem, an infinitary
statement from graph theory. A _tournament_ on a domain $D\subseteq\mathbb{N}$
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$ is the restriction of $R$ to a
subdomain $H\subseteq D^{2}$. We identify subtournaments with their domains.
The following statement is known as the Erdős-Moser theorem, and is an
infinitary version of some theorem by Erdős and Moser [6].

######  Statement 1.1 (Erdős-Moser theorem).

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

The Erdős-Moser theorem easily follows from the celebrated Ramsey theorem for
pairs. 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.2 (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”.

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$.”
Since any $f$-homogeneous set is $f$-transitive, the Erdős-Moser theorem can
be considered as a particular case of Ramsey’s theorem for pairs.

###  1.1 $\mathsf{EM}$ and $\mathsf{RT}^{2}_{2}$ in Reverse Mathematics

Both the Erdős-Moser theorem and Ramsey’s theorem for pairs have been
extensively studied in Reverse Mathematics, both from a computational and a
proof-theoretic viewpoint. See Hirschfeldt [5] for an introduction to the
reverse mathematics of combinatorial principles.

From many perspectives, $\mathsf{EM}$ is very close to $\mathsf{RT}^{2}_{2}$.
The combinatorics are very similar, and the Erdős-Mőser theorem can be
considered as a disjunction-free version of Ramsey’s theorem for pairs. These
similarities in combinatorics have many consequences in Reverse Mathematics.
Jockusch [9] proved that every computable instance of $\mathsf{RT}^{2}_{2}$
admits a $\Pi^{0}_{2}$ solution, while there exists a computable instance of
$\mathsf{RT}^{2}_{2}$ with no $\Sigma^{0}_{2}$ solution. These bounds are the
same for the Erdős-Moser theorem. On the proof-theoretic side, the first-order
part of Ramsey’s theorem for pairs and the Erdős-Moser theorem are known to
coincide [2]. More generally, most of the known statements implied by
$\mathsf{RT}^{2}_{2}$ are already known to follow from $\mathsf{EM}$ over
$\mathsf{RCA}_{0}$, the base theory of Reverse Mathematics. Whether
$\mathsf{EM}$ implies $\mathsf{RT}^{2}_{2}$ was open for a long time, before
Lerman, Solomon and Towsner [11] answered it negatively.

When considering non-computable instances, the behaviors of
$\mathsf{RT}^{2}_{2}$ and $\mathsf{EM}$ turn out to be very dramatically
different. For every function $g:\mathbb{N}\to\mathbb{N}$, there exists a
coloring $f:[\mathbb{N}]^{2}\to 2$ such that every infinite $f$-homogeneous
set computes a function $h$ dominating $g$, that is, $\forall x(h(x)\geq
g(x))$. Indeed, simply take $f(x,y)=1$ iff $g(x)<y$. Thus, by a theorem of
Slaman and Groszek [7], there exists a (non-computable) instance of
$\mathsf{RT}^{2}_{2}$ such that every solution computes every hyperarithmetic
(or equivalently $\Delta^{1}_{1}$) set. On the other hand, Patey and Wang
(both unpublished) independently proved that for every non-computable set $B$
and every instance of $\mathsf{EM}$, there exists a solution which does not
compute $B$. This property of $\mathsf{EM}$ is shared with the infinite
pigeonhole principle ($\mathsf{RT}^{1}_{2}$). Indeed, Dzhafarov and Jockusch
[4] proved that for every non-computable set $B$ and every set $A$, there is
an infinite subset $H$ of $A$ or $\overline{A}$ which does not compute $B$.

###  1.2 $\mathsf{EM}$ and $\mathsf{RT}^{1}_{2}$ under stronger reductions

As mentioned above, when considering non-computable instances, the Erdős-Moser
theorem seems to have closer behavior to the pigeonhole principle than to
Ramsey’s theorem for pairs. In a series of papers, Monin and Patey [12, 15,
13] developed a framework to control iterated jumps of solutions to the
pigeonhole principle. They proved in particular the following three facts (see
[15]):

  * •

If $B$ is not arithmetic (resp. hyperarithmetic), then for every set $A$,
there is an infinite subset $H$ of $A$ or $\overline{A}$ such that $B$ is not
$A$-arithmetic (resp. $A$-hyperarithmetic).

  * •

If $B$ is not $\Sigma^{0}_{n}$ (resp. $\Delta^{0}_{n})$, then for every set
$A$, there is an infinite subset $H$ of $A$ or $\overline{A}$ such that $B$ is
not $\Sigma^{0}_{n}(A)$ (resp. $\Delta^{0}_{n}(A)$).

  * •

For every $\Delta^{0}_{n}$ set $A$, there is an infinite subset $H$ of $A$ or
$\overline{A}$ of lown degree.

In this article, we prove the following three theorems:

######  Main Theorem 1.3.

If $B$ is not arithmetic, then for every tournament $T$, there is an infinite
transitive subtournament $H$ such that $B$ is not $H$-arithmetic.

The generalization to the hyperarithmetic hierarchy is not proven, but the
authors believe that it holds with the same proof _mutatis mutandis_. Like for
the pigeonhole principle, a layerwise version of the previous theorem holds:

######  Main Theorem 1.4.

Fix $n\geq 1$. If $B$ is not $\Sigma^{0}_{n}$, then for every tournament $T$,
there is an infinite transitive subtournament $H$ such that $B$ is not
$\Sigma^{0}_{n}(H)$.

The case $n=1$ was already proven independently by the first author and Wang
(unpublished). The statement where $\Sigma^{0}_{n}$ is replaced by
$\Delta^{0}_{n}$ directly follows from 1.4 and Post’s theorem. Indeed, if $B$
is not $\Delta^{0}_{n}$, then by Post’s theorem, either it or its complement
is not $\Sigma^{0}_{n}$. Then apply 1.4 to conclude.

######  Main Theorem 1.5.

Fix $n\geq 1$. Every $\Delta^{0}_{n}$ tournament $T$ has an infinite
transitive subtournament of lown+1 degree.

The case $n=1$ follows from the same statement for Ramsey’s theorem for pairs,
proven by Cholak, Jockusch and Slaman [1]. On the other hand, as explained,
the statement for Ramsey’s theorem for pairs fails for $n>1$, since there
exists a $\Delta^{0}_{2}$ instance of $\mathsf{RT}^{2}_{2}$ such that every
solution computes $\emptyset^{\prime}$.

Besides the intrinsic interest of these theorems, they are also motivated by
the more general program of development of good iterated jump control of
combinatorial theorems, and in particular by the goal to prove the strictness
of the free set, thin set and rainbow ramsey hierarchies. See Monin and Patey
[15, Section 1.2] for a discussion on the subject. The Erdős-Moser is the
first statement about colorings of pairs which is known to admit a good
iterated jump control.

###  1.3 Definition and notation

A _binary string_ is an ordered tuple of bits
$a_{0},\dots,a_{n-1}\in\\{0,1\\}$. The empty string is written $\epsilon$. A
_binary sequence_ (or a _real_) is an infinite listing of bits
$a_{0},a_{1},\dots$. Given $s\in\omega$, $2^{s}$ is the set of binary strings
of length $s$ and $2^{<s}$ is the set of binary strings of length $<s$.
Accordingly, $2^{<\omega}$ is the set of binary strings and $2^{\omega}$ is
the set of binary sequences. Given a string $\sigma\in 2^{<\omega}$, we use
$|\sigma|$ to denote its length. Given two strings $\sigma,\tau\in
2^{<\omega}$, $\sigma$ is a _prefix_ of $\tau$ (written $\sigma\preceq\tau$)
if there exists a string $\rho\in 2^{<\omega}$ such that
$\sigma^{\frown}\rho=\tau$. Given a sequence $X$, we write $\sigma\prec X$ if
$\sigma=X\upharpoonright n$ for some $n\in\omega$. A binary string $\sigma$
can be interpreted as a finite set $F_{\sigma}=\\{x<|\sigma|:\sigma(x)=1\\}$.
We write $\sigma\subseteq\tau$ for $F_{\sigma}\subseteq F_{\tau}$. We write
$\\#\sigma$ for the size of $F_{\sigma}$. Given two strings $\sigma$ and
$\tau$, we let $\sigma\cup\tau$ be the unique string $\rho$ of length
$\max(|\sigma|,|\tau|)$ such that $F_{\rho}=F_{\sigma}\cup F_{\tau}$.

A _binary tree_ is a set of binary strings $T\subseteq 2^{<\omega}$ which is
closed downward under the prefix relation. A _path_ through $T$ is a binary
sequence $P\in 2^{\omega}$ such that every initial segment belongs to $T$.

A _Turing ideal_ $\mathcal{I}$ is a collection of sets which is closed
downward under the Turing reduction and closed under the effective join, that
is, $(\forall X\in\mathcal{I})(\forall Y\leq_{T}X)Y\in\mathcal{I}$ and
$(\forall X,Y\in\mathcal{I})X\oplus Y\in\mathcal{I}$, where $X\oplus
Y=\\{2n:n\in X\\}\cup\\{2n+1:n\in Y\\}$. A _Scott set_ is a Turing ideal
$\mathcal{I}$ such that every infinite binary tree $T\in\mathcal{I}$ has a
path in $\mathcal{I}$. In other words, a Scott set is the second-order part of
an $\omega$-model of $\mathsf{RCA}_{0}+\mathsf{WKL}$. A Turing ideal
$\mathcal{M}$ is _countable coded_ by a set $X$ if
$\mathcal{M}=\\{X_{n}:n\in\omega\\}$ with $X=\bigoplus_{n\in\omega}X_{n}$.
Given $n\geq 1$, a formula is $\Sigma^{0}_{n}(\mathcal{M})$ (resp.
$\Pi^{0}_{n}(\mathcal{M})$) if it is $\Sigma^{0}_{n}(X)$ (resp.
$\Pi^{0}_{n}(X)$) for some $X\in\mathcal{M}$.

Given two sets $A$ and $B$, we denote by $A<B$ the formula $(\forall x\in
A)(\forall y\in B)[x<y]$. We write $A\subseteq^{*}B$ to mean that $A-B$ is
finite, that is, $(\exists n)(\forall a\in A)(a\not\in B\rightarrow a<n)$. A
_$k$ -cover_ of a set $X$ is a sequence of sets $Y_{0},\dots,Y_{k-1}$ such
that $X\subseteq Y_{0}\cup\dots\cup Y_{k-1}$.

###  1.4 Organization of this paper

In Section 2, we try to give an overview of the forcing construction, by
explaining in Section 2.1 the importance of the so-called “forcing question”,
then diving in Section 2.2 into the combinatorics of $\mathsf{EM}$, especially
explaining the role of the infinite pigeonhole principle as a warrant of
extendibility for the Erdős-Moser theorem, and then explaining in Section 2.3
the issues raised when trying to control iterated jumps of solutions with
variants of Mathias forcing.

In Section 3, we restate the main properties of partition regular and large
classes, studied in Monin and Patey [12, 15]. In particular, we define the
notions of cohesive and minimal classes in Section 3.2, which play an
essential role to maintain the compatibility of large classes between
different levels of the iterated jump control. Last, we restate in Section 3.3
the existence of a hierarchy of Scott sets and of cohesive classes, which play
the role of a spine for the main notion of forcing.

Section 4 is dedicated to the development of the main forcing framework, by
defining its conditions, the forcing relation, and a forcing question. This
framework is applied in various contexts, to prove strong cone avoidance of
$\mathsf{EM}$ for arithmetic reductions in Section 5, a layerwise version of
this strong cone avoidance for $\Sigma^{0}_{n}$ operators in Section 6, and
prove the existence of lown solutions through an effectivization of the
construction in Section 7.

##  2 The big picture

The techniques used in this article are rather sophisticated with many
technical subtleties, and it may be quite hard to have the big picture. In
this section, we describe the general forcing argument used to prove our main
theorems, and highlight a few technical difficulties justifying the design
choice of our notion of forcing.

###  2.1 Forcing question

The three main theorems are related, in that they involve very similar
techniques of iterated jump control. Indeed, in each case, it consists of
constructing a solution whose $\Sigma^{0}_{n}$ properties resemble the ones of
the ground model. For this, one tries to translate $\Sigma^{0}_{n}(G)$
formulas relative to the generic object constructed $G$ into absolute
$\Sigma^{0}_{n}$ formulas. In set-theoretic forcing, this is achieved through
the forcing relation, whose definition must be sufficiently simple (in terms
of definitional complexity) to make the new model inherit properties of the
ground model. In computability theory, the situation is slightly different,
and the simplicity of the forcing relation is less important than the one of
the so-called _forcing question_.

In what follows, a _notion of forcing_ is a partial order $(\mathbb{P},\leq)$
such that every sufficiently generic filter $\mathcal{F}\subseteq\mathbb{P}$
induces a set $G_{\mathcal{F}}\subseteq\mathbb{N}$. Every notion of forcing is
equipped with a forcing relation, written $\Vdash$, between the set of
conditions $\mathbb{P}$ and the set of arithmetic formulas $\text{Form}[G]$
with a set parameter $G$ denoting the generic object constructed.

######  Definition 2.1.

Fix a notion of forcing $(\mathbb{P},\leq)$. A _forcing question_ is a
relation $\operatorname{{?}{\vdash}}$ over $\mathbb{P}\times\text{Form}[G]$
such that, for every $c\in\mathbb{P}$ and $\varphi(G)\in\text{Form}[G]$,

  1. (1)

If $c\operatorname{{?}{\vdash}}\varphi(G)$, then there is an extension $d\leq
c$ such that $d\Vdash\varphi(G)$;

  2. (2)

If $c\operatorname{{?}{\nvdash}}\varphi(G)$, then there is an extension $d\leq
c$ such that $d\Vdash\neg\varphi(G)$;

The notion of forcing question is not canonical, and a single notion of
forcing might have many candidate forcing questions. On the other hand, many
computational properties of the generic object $G$ might be directly derived
from the existence of a forcing question with sufficiently nice definitional
properties. Consider for example the following property:

######  Definition 2.2.

Fix a notion of forcing $(\mathbb{P},\leq)$ and some $n\in\mathbb{N}$. A
forcing question $\operatorname{{?}{\vdash}}$ is _uniformly
$\Sigma^{0}_{n}$-preserving_ if for every $c\in\mathbb{P}$ and every uniform
sequence of $\Sigma^{0}_{n}$ formulas $\varphi_{0}(G),\varphi_{1}(G),\dots$,
the sequence
$c\operatorname{{?}{\vdash}}\varphi_{0}(G),c\operatorname{{?}{\vdash}}\varphi_{1}(G),\dots$
is uniformly $\Sigma^{0}_{n}$.

The following proposition is at the heart of our forcing construction. It was
used by Wang [19, Proposition 3.1, Proposition 3.4, Theorem 3.6], where the
author showed for each notion of forcing the existence of a uniformly
$\Sigma^{0}_{n}$-preserving forcing question, without naming explicitly this
concept.

######  Proposition 2.3.

Let $(\mathbb{P},\leq)$ be a notion of forcing with a uniformly
$\Sigma^{0}_{n}$-preserving forcing question. Then for every
non-$\Sigma^{0}_{n}$ set $C$ and every sufficiently generic set $G$ for this
notion of forcing, $C$ is not $\Sigma^{0}_{n}(G)$.

###### Proof.

Fix a $\Sigma^{0}_{n}$ formula $\varphi(G,x)$ with one free first-order
variable $x$. Let $D_{\varphi}\subseteq\mathbb{P}$ be the set of conditions
$c$ such that either $c\Vdash\varphi(G,a)$ for some $a\not\in C$, or
$c\Vdash\neg\varphi(G,a)$ for some $a\in C$. Let us show that $D_{\varphi}$ is
dense. Given a condition $c\in\mathbb{P}$, let
$W=\\{a\in\mathbb{N}:c\operatorname{{?}{\vdash}}\varphi(G,a)\\}$. Since the
forcing question is uniformly $\Sigma^{0}_{n}$-preserving, then the set $W$ is
$\Sigma^{0}_{n}$, hence $C\neq W$. Let $a\in C\Delta W$, the symmetric
difference of $C$ and $W$.

  * •

If $a\in W\setminus C$, then by definition,
$c\operatorname{{?}{\vdash}}\varphi(G,a)$, so by property (1) of the forcing
question, there is an extension $d\leq c$ such that $d\Vdash\varphi(G,a)$.

  * •

If $a\in C\setminus W$, then by definition,
$c\operatorname{{?}{\nvdash}}\varphi(G,a)$. By property (2) of the forcing
question, $c\operatorname{{?}{\vdash}}\neg\varphi(G,a)$, and by property (1),
there is an extension $d\leq c$ such that $d\Vdash\neg\varphi(G,a)$.

In both cases, $d\in D_{\varphi}$, so $D_{\varphi}$ is dense. If $\mathcal{F}$
is a sufficiently generic filter, it will intersect $D_{\varphi}$ for every
$\Sigma^{0}_{n}$ formula $\varphi(G,x)$, hence, letting $G$ be the set induced
by $\mathcal{F}$, $C$ will not be $\Sigma^{0}_{n}(G)$. ∎

The construction of lown solutions are often effectivizations of the forcing
argument, either by constructing a $\emptyset^{(n)}$-computable filter
sufficiently generic for deciding $\Sigma^{0}_{n}(G)$ formulas, or by
constructing, with any PA degree $P$ over $\emptyset^{(n-1)}$, a
$P$-computable filter $G_{\mathcal{F}}$ sufficiently generic for deciding
$\Sigma^{0}_{n-1}(G)$ formulas. In the latter case, using the low basis
theorem relativized to $\emptyset^{(n-1)}$, there exists such a PA degree $P$
over $\emptyset^{(n-1)}$ such that $P^{\prime}\leq_{T}\emptyset^{(n)}$, thus
$\Sigma^{0}_{n}$ properties of $G_{\mathcal{F}}$ can be decided thanks to
$\emptyset^{(n)}$.

###  2.2 Combinatorics of $\mathsf{EM}$

In order to understand the design of the notion of forcing for this article,
it is important to get familiar with the combinatorics of the Erdős-Moser
theorem. Lerman, Solomon and Towsner [11] analyzed the basic combinatorial
ideas essential to the computable study of the theorem.

A transitive tournament $T$ over a domain $A$ can be seen as a linear order
$(A,\leq_{T})$ defined by $a\leq_{T}b$ iff $a=b$ or $T(a,b)$. This
interpretation should be kept in mind throughout the article. For convenience,
we shall always consider that the tournament contains two end-points $-\infty$
and $+\infty$, that is, such that $T(-\infty,x)$ and $T(x,+\infty)$ holds for
every $x$.

######  Definition 2.4 ([11]).

Fix a tournament $T$ over a domain $A$.

  * (1)

The _interval_ $(a,b)$ between $a,b\in A\cup\\{-\infty,+\infty\\}$ is the set
of points $x\in A$ such that $T(a,x)$ and $T(x,b)$ holds.

  * (2)

Given a finite $T$-transitive subset $F\subseteq A$ and $a,b\in
F\cup\\{-\infty,+\infty\\}$, the interval $(a,b)$ is _minimal_ in $F$ if
$(a,b)\cap F=\emptyset$.

Fix a tournament $T$ over $\omega$. Any finite $T$-transitive set $F$ is not
necessarily extendible into an infinite solution. Indeed, maybe there exist
some $a,b\in F$ such that $T(a,b)$ holds, but $T(b,x)$ and $T(x,a)$ both hold
for cofinitely many $x$. We shall therefore work with Mathias conditions
$(\sigma,X)$ where $\sigma$ is a $T$-transitive finite set, with some extra
structure which will guarantee that $\sigma$ is extendible into an infinite
solution. This yields the following definition (due to Patey [17, Definition
5.7]).

######  Definition 2.5 ([17]).

An _$\mathsf{EM}$ -condition_ for $T$ is a Mathias condition $(\sigma,X)$ such
that

  1. 1.

for all $y\in X$, $\sigma\cup\\{y\\}$ is $T$-transitive

  2. 2.

$X$ is included in a minimal $T$-interval of $\sigma$

Actually, the second property can be obtained from the first one by a simple
application of the infinite pigeonhole principle. Indeed, there are only
finitely many minimal $T$-intervals in $\sigma$, and each element of $X$
belongs to exactly one of them. The notion of condition extension is the usual
Mathias extension.

To simplify notation, given two disjoint sets $F$ and $E$, we write
$F\to_{T}E$ if for every $a\in F$ and $b\in E$, $T(a,b)$ holds. One essential
feature in the understanding of the computational content of a theorem is to
understand the combinatorics necessary to extend a partial solution with an
arbitrarily large number of elements in one block. In the case of the Erdős-
Moser theorem, the following lemma contains its core combinatorics.

######  Lemma 2.6 ([17]).

Fix an $\mathsf{EM}$-condition $c=(\sigma,X)$ for a tournament $T$, an
infinite subset $Y\subseteq X$ and a finite $T$-transitive set $\rho\subseteq
X$ such that $\max\rho<\min Y$ and $[\rho\to_{T}Y\vee Y\to_{T}\rho]$. Then
$(\sigma\cup\rho,Y)$ is a valid extension of $c$.

Suppose one wants to design a good forcing question for deciding
$\Sigma^{0}_{1}$ formulas with this notion of forcing. To simplify the
situation, assume first that the tournament $T$ is _stable_ , that if, for
every $a$, either $(\forall^{\infty}b)T(a,b)$ holds, or
$(\forall^{\infty}b)T(b,a)$ holds. In other words, each element admits a limit
behavior with respect to $T$. Let $f:\omega\to 2$ be the limit behavior of
$T$, that is, $f(a)=0$ iff $\forall^{\infty}bT(a,b)$ and $f(a)=1$ otherwise.
The following naive definition does not satisfy the desired definitional
properties:

######  Definition 2.7.

Let $c=(\sigma,X)$ be an EM-condition, $n$ be an integer, and $e$ be a Turing
index. Let $c\operatorname{{?}{\vdash}}\Phi_{e}^{G}(n)\downarrow$ hold if
there exists a finite $f$-homogeneous $T$-transitive set $\tau\subseteq X$
such that $\Phi_{e}^{\sigma\cup\tau}(n)\downarrow$.

By Lemma 2.6, this is a valid forcing condition, in that if it holds, then
there exists an extension forcing $\Phi_{e}^{G}(n)\downarrow$, and otherwise,
there exists an extension forcing $\Phi_{e}^{G}(n)\uparrow$. From a
definitional viewpoint, the previous relation is $\Sigma^{0}_{1}(X\oplus
T\oplus f)$. However, the tournament $T$ and its limit behavior $f$ are
strongly non-computable, and may even compute the set $B$ that we want to
avoid. The solution to get rid of these parameters is to make an over-
approximation:

######  Definition 2.8.

Let $c=(\sigma,X)$ be an EM-condition, $n$ be an integer, and $e$ be a Turing
index. Let $c\operatorname{{?}{\vdash}}\Phi_{e}^{G}(n)\downarrow$ hold if for
every tournament $R$ and every function $g:\mathbb{N}\to 2$, there is a finite
$g$-homogeneous $R$-transitive set $\tau\subseteq X$ such that
$\Phi_{e}^{\sigma\cup\tau}(n)\downarrow$.

At first sight, an overapproximation yields a forcing question with even worse
definitional properties since it contains a universal second-order
quantification. However, thanks to compactness, the forcing question is
actually $\Sigma^{0}_{1}(X)$, as it is equivalent to the following definition:

> $c\operatorname{{?}{\vdash}}\Phi_{e}^{G}(n)\downarrow$ if there exists some
> threshold $t$ such that for every tournament $R$ over $\\{0,\dots,t\\}$ and
> every function $g:\\{0,\dots,t\\}\to 2$, there is a finite $g$-homogeneous
> $R$-transitive set $\tau\subseteq X$ such that
> $\Phi_{e}^{\sigma\cup\tau}(n)\downarrow$.

If the forcing question holds, then by letting $R=T$ and $g=f$, it is clear
that there exists an extension forcing $\Phi_{e}^{G}(n)\downarrow$. On the
other hand, if the forcing question does not hold, then the witness of failure
might be some tournaments $R$ and some colorings $f$ which are unrelated to
$T$ and $g$. This is where the combinatorics of Ramsey theory comes into play.

######  Lemma 2.9.

Let $c=(\sigma,X)$ be an $\mathsf{EM}$-condition, $n$ be an integer and $e$ be
a Turing index.

  * (1)

If $c\operatorname{{?}{\vdash}}\Phi_{e}^{G}(n)\downarrow$, then there exists
$d\leq c$ such that $d\Vdash\Phi_{e}^{G}(n)\downarrow$.

  * (2)

Else, if $c\operatorname{{?}{\nvdash}}\Phi_{e}^{G}(n)\downarrow$, then there
exists $d\leq c$ such that $d\Vdash\Phi_{e}^{G}(n)\uparrow$.

###### Proof in the stable case.

We prove each point :

  * (1)

If $c\operatorname{{?}{\vdash}}\Phi_{e}^{G}(n)\downarrow$, letting $R=T$ and
$g=f$, there exists a finite $f$-homogeneous $T$-transitive set $\tau\subseteq
X$ such that $\Phi_{e}^{\sigma\cup\tau}(n)\downarrow$. By choice of $f$, there
exists some $t\in\omega$ such that $\tau\to_{T}X\setminus\\{0,\dots,t\\}$ or
$X\setminus\\{0,\dots,t\\}\to_{T}\tau$. Thus, by Lemma 2.6, the pair
$d:=(\sigma\cup\tau,X\setminus\\{0,\dots,t\\})$ is an EM-condition. Note that
$d\leq c$ and that $d\Vdash\Phi_{e}^{G}(n)\downarrow$.

  * (2)

If $c\operatorname{{?}{\nvdash}}\Phi_{e}^{G}(n)\downarrow$, then there exists
a coloring $h:\mathbb{N}\to 2$ and a tournament $R$ such that for all finite
$h$-homogeneous and $R$-transitive set $\tau\subseteq X$,
$\Phi_{e}^{\sigma\cup\tau}(n)\uparrow$. By the pigeonhole principle and the
Erdős-Moser theorem restricted to $X$, there exists an infinite subset
$Y\subseteq X$ which is both $h$-homogeneous and $R$-transitive. The pair
$d:=(\sigma,Y)$ is a valid EM-condition such that
$d\Vdash\Phi_{e}^{G}(e)\uparrow$.

∎

Whenever the tournament is not stable, the situation seems more complicated as
there is no clear choice of $f$. Surprisingly, the previous forcing question
still holds, but with a more subtle proof in the first case. The idea is the
following: in the first case, by compactness, the finite extension candidate
is bounded by a threshold. One can then restrict the reservoir, so that every
element below the threshold has a limit behavior with respect to the new
reservoir, and then act like in the stable case.

###### Proof in the general case.

We only prove the first case, as the second case did not involve stability of
the tournament.

  * (1)

If $c\operatorname{{?}{\vdash}}\Phi_{e}^{G}(n)\downarrow$, by compactness,
there exists some threshold $t$ such that for every tournament $R$ over
$\\{0,\dots,t\\}$ and every function $g:\\{0,\dots,t\\}\to 2$, there is a
finite $g$-homogeneous $R$-transitive set $\tau\subseteq X$ such that
$\Phi_{e}^{\sigma\cup\tau}(n)\downarrow$.

For every element $y\in X\setminus\\{0,\dots,t\\}$, one can associate a
function $g_{y}:\\{0,\dots,t\\}\to 2$ defined by $g_{y}(x)=1$ iff $T(x,y)=1$.
Since there are $2^{t}$ many such functions, then the function $y\mapsto
g_{y}$ is a finite coloring of the reservoir, so by the infinite pigeonhole
principle, there exists an infinite subset $Y\subseteq
X\setminus\\{0,\dots,t\\}$ which is homogeneous for some color
$g:\\{0,\dots,t\\}\to 2$. In other words, for every $g$-homogeneous set
$\tau\subseteq\\{0,\dots,t\\}$, either $\tau\to_{T}Y$, or $Y\to_{T}\tau$.

Letting $R=T$, there is a finite $g$-homogeneous $T$-transitive set
$\tau\subseteq X\cap\\{0,\dots,t\\}$ such that
$\Phi_{e}^{\sigma\cup\tau}(n)\downarrow$. Thus, by Lemma 2.6, the pair
$d:=(\sigma\cup\tau,Y)$ is an EM-condition. Note that $d\leq c$ and that
$d\Vdash\Phi_{e}^{G}(n)\downarrow$.

∎

Together with the general discussion of Section 2.1 about forcing questions,
this section constitutes a proof that $\mathsf{EM}$ admits strong cone
avoidance.

######  Remark 2.10.

The bottom line of this section is the following: The combinatorics of the
Erdős-Moser theorem involve the pigeonhole principle, in that in order to
ensure the extendibility of a finite $T$-transitive set, one needs to ensure
that it is homogeneous for the appropriate instance of $\mathsf{RT}^{1}_{2}$.
This 2-coloring represents the limit behavior of the tournament. Whenever the
tournament is not stable, the choice of the 2-coloring is not clear ahead of
time, and the colorings must be universally quantified.

Last, note that the use of $\mathsf{RT}^{1}_{2}$ in the proof of $\mathsf{EM}$
is not overkill, in that given a 2-coloring $f:\mathbb{N}\to 2$, one can
define a tournament $T$ by $T(x,y)$ iff $[x<y\leftrightarrow f(x)=f(y)]$. Then
any infinite transitive subtournament is, up to finite changes,
$f$-homogeneous.

###  2.3 Iterated jump control of EM forcing

In computability-theoretic forcing, one usually forces a
$\Sigma^{0}_{1}/\Pi^{0}_{1}$ property in a strong sense: if
$c\Vdash\varphi(G)$ for $\varphi\in\\{\Sigma^{0}_{1},\Pi^{0}_{1}\\}$, then
$\varphi(G_{\mathcal{F}})$ actually holds for every filter $\mathcal{F}$
containing $c$. The situation becomes significantly more complicated when
considering $\Sigma^{0}_{2}/\Pi^{0}_{2}$ formulas.

A $\Pi^{0}_{2}$ formula $(\forall x)(\exists y)\varphi(G,x,y)$ can be
considered as a countable collection of $\Sigma^{0}_{1}$ formulas $\\{(\exists
y)\varphi(G,n,y):n\in\mathbb{N}\\}$. Such a formula cannot usually be forced
in a strong sense. The relation $c\Vdash(\forall x)(\exists y)\varphi(G,x,y)$
holds iff for every $x\in\mathbb{N}$, the set of conditions forcing $(\exists
y)\varphi(G,x,y)$ is dense below $c$. This way, every sufficiently generic
filter containing $c$ will also contain a condition forcing $(\exists
y)\varphi(G,x,y)$ for each $x\in\mathbb{N}$, thus the property $(\forall
x)(\exists y)\varphi(G_{\mathcal{F}},x,y)$ holds for every sufficiently
generic filter containing $c$.

Stating the density of a collection of conditions can be a definitionally
complex statement, depending on the complexity of the notion of forcing. In
some simple cases, such as Cohen forcing, the forcing relation for
$\Pi^{0}_{2}(G)$ formulas is $\Pi^{0}_{2}$, yielding a good forcing question.

Variants of Mathias forcing do not behave that well. Indeed, the statement of
density requires universal and existential quantification on the conditions,
hence on the reservoirs, which are second-order objects. Actually, the
approach of Mathias forcing provably fails:

######  Lemma 2.11 (Folklore).

The set $\emptyset^{\prime\prime}$ is $\Pi^{0}_{2}(G_{\mathcal{F}})$ for every
sufficiently generic filter $\mathcal{F}$ for Mathias forcing with computable
reservoirs.

###### Proof.

By Martin’s domination theorem, a set is of high degree iff it computes a
function eventually dominating every total computable function. Given a
computable function $f$ and a computable Mathias condition $(\sigma,X)$, there
exists a computable Mathias extension $(\sigma,Y)$ such that the principal
function of $Y$ (the function which to $n$ associates the $n$th element of
$Y$) dominates $f$. Thus, for every sufficiently generic filter $\mathcal{F}$,
the principal function of $G_{\mathcal{F}}$ will eventually dominate every
total computable function, hence be of high degree. ∎

The same argument holds for computable EM forcing. Intuitively, the reason of
failure of Mathias forcing and its variants, is because of the sparsity of its
reservoirs. One way to circumvent the problem is to restrict the class
possible reservoirs with a third-order object, which will play the role of a
“reservoir of reservoirs”: this meta-reservoir is a class of infinite sets
$\mathcal{L}$ which cannot contain arbitrarily sparse objects. Our goal is to
work with EM conditions $(\sigma,X)$ such that $X\in\mathcal{L}$. One however
requires the class $\mathcal{L}$ to be closed under certain operations which
are needed for using the combinatorics of Section 2.2. Analyzing the
operations made over the reservoirs, they are of three kinds:

  1. 1.

truncation of a reservoir from a finite number of elements (case 1 of the
forcing question)

  2. 2.

splitting of a reservoir based on an instance of $\mathsf{RT}^{1}_{2}$ (case 2
of the forcing question)

  3. 3.

choice of an $R$-transitive subtournament for an instance $R$ of $\mathsf{EM}$
(case 2 of the forcing question)

Assuming $\mathcal{L}$ contains only infinite sets, the truncation operation
is a consequence of finitely many applications of $\mathsf{RT}^{1}_{2}$.
Unfortunately, contrary to the pigeonhole principle, the classes which are
closed under applications of $\mathsf{EM}$ do not have nice combinatorial
properties. Therefore, in Case 2 of Lemma 2.9, instead of applying the Erdős-
Moser theorem restricted to $X$ to obtain an infinite $R$-transitive
subtournament $Y\subseteq X$, we shall simply add $R$ to the list of
tournaments we commit to be transitive for. The benefit of it is that the only
remaining operation done on our reservoirs is the application of
$\mathsf{RT}^{1}_{2}$. The counterpart of postponing our application of
$\mathsf{EM}$ is that our forcing conditions will now be made of triples
$(\vec{R},\sigma,X)$, where $\vec{R}$ is a finite sequence of tournaments, and
such that $(\sigma,X)$ is an EM condition for every $R\in\vec{R}$. This list
$\vec{R}$ can grow with condition extension.

The reservoir $X$ will therefore belong to a class $\mathcal{L}$ which is
closed under applications of $\mathsf{RT}^{1}_{2}$. This notion of closure is
called _partition regularity_. We shall introduce this concept and its main
properties in Section 3. The restriction of the reservoirs to those which
belong to a partition regular class dramatically decreases the definitional
complexity of the forcing question, as instead of asking whether for every
infinite set $Y\subseteq X$, there is an infinite set $Z\subseteq Y$
satisfying some property, one can ask whether the collection of all $Z$
satisfying the property is partition regular. Based on the complexity of the
property, the question will not be definitionally too complex.

##  3 Partition regularity and largeness

The notion of partition regularity comes from combinatorics and is widely used
in Ramsey theory. It therefore naturally occurred in the computability-
theoretic analysis of combinatorial theorems.

######  Definition 3.1.

A class $\mathcal{L}\subseteq 2^{\omega}$ is partition regular if :

  * •

$\mathcal{L}$ is non-empty,

  * •

for all $X\in\mathcal{L}$, if $X\subseteq Y$, then $Y\in\mathcal{L}$,

  * •

for every integer $k$, for every $X\in\mathcal{L}$, for every $k$-cover
$Y_{1},Y_{2},\dots Y_{k}$ of $X$, there exists $i\leq k$ such that
$Y_{i}\in\mathcal{L}.$

Dorais [3] was the first to use variants of Mathias forcing in which the
reservoirs belong to partition regular classes, to produce generic sets of
non-high degree. Since then, Monin and Patey [12, 14, 15, 16] successfully
used this variant to control iterated jump of solutions to the infinite
pigeonhole principle. Monin and Patey [15, Section 2] contains all the
computability-theoretic analysis of partition regularity used in this article.
In this section, we therefore simply state the relevant definitions and
theorems for the sake of completeness.

Partition regularity enjoys nice closure properties, but is not a notion of
largeness per se, in that a superclass of a partition regular class is not
necessarily partition regular itself. Throughout the article, given a property
$\varphi(X)$, we will ask whether the class $\\{X:\varphi(X)\\}$ is large, in
the sense that it contains a partition regular subclass. This yields the
following definition, which is often more convenient to manipulate than
partition regularity.

######  Definition 3.2.

A class $\mathcal{L}\subseteq 2^{\omega}$ is large if :

  * •

for all $X\in\mathcal{L}$, if $X\subseteq Y$, then $Y\in\mathcal{L}$,

  * •

for every integer $k$, for every $k$-cover $Y_{1},Y_{2},\dots Y_{k}$ of
$\omega$, there exists $i\leq k$ such that $Y\in\mathcal{L}.$

The large classes are exactly those which contain a partition regular
subclass. To avoid degenerate behaviors, in this article, we shall restrict
ourselves to large classes which contain only infinite sets.

######  Definition 3.3.

A large class is non-trivial if it contains only infinite sets.

In particular, if a partition regular class $\mathcal{P}$ is non-trivial, then
it is closed under finite changes. Indeed, if $X\in\mathcal{P}$ and $Y=^{*}X$
as witnessed by a finite set $F$, then $Y,F$ form a 2-cover of $X$, so either
$Y$ or $F$ must belong to $\mathcal{P}$, and by non-triviality,
$F\not\in\mathcal{P}$.

One of the core properties of large classes is the following lemma, which
plays an essential role in the computability-theoretic analysis of large
classes. For example, by contraposition, if an $F_{\sigma}$ class is not
large, then it is included into a non-large open class.

######  Lemma 3.4 ([15]).

Let $(\mathcal{P}_{n})_{n\in\omega}$ be a decreasing sequence of large
classes. Their intersection $\bigcap_{n\in\omega}\mathcal{P}_{n}$ is again
large.

The above lemma also holds if one replaces largeness by partition regularity.
Moreover, a union of partition regular classes is still partition regular.
Therefore, every large class contains a largest (for inclusion) partition
regular subclass, which justifies the following definition.

######  Definition 3.5.

For every large class $\mathcal{P}$, let $\mathcal{L}(\mathcal{P})$ denote the
largest partition regular subclass of $\mathcal{P}$.

By the infinite pigeonhole principle, the class of all infinite sets is
partition regular. This naturally generalizes to a whole family of partition
regular classes:

######  Definition 3.6.

For every set $X\subseteq\omega$, let
$\mathcal{L}_{X}:=\\{E\subseteq\omega:|E\cap X|=\infty\\}$.

For every infinite set $X$, the class $\mathcal{L}_{X}$ is partition regular.
This class plays an essential role in ensuring that a set belongs to all
partition regular subclasses. Indeed, if $\mathcal{P}$ is a partition regular
subclass of $\mathcal{L}_{X}$, then $X\in\mathcal{P}$, as otherwise, since
$X,\overline{X}$ forms a 2-cover of $\omega$, we would have
$\overline{X}\in\mathcal{P}\subseteq\mathcal{L}_{X}$, contradiction.

###  3.1 $\Pi^{0}_{2}$ large classes

By Monin and Patey [16, Proposition 2.15], there are no non-trivial
$\mathbf{\Sigma^{0}_{2}}$ large classes. The first interesting example of such
classes are $\Pi^{0}_{2}$. Along this article, we will only be interested in
$F_{\sigma}$ classes, and more precisely intersections of
$\Sigma^{0}_{1}(\mathcal{M})$ classes, for some Scott set $\mathcal{M}$
(recall that a formula is $\Sigma^{0}_{1}(\mathcal{M})$ if it is
$\Sigma^{0}_{1}(P)$ for some $P\in\mathcal{M}$). Fix a Scott set $\mathcal{M}$
encoded by a set $M\subseteq\omega$, i.e., $M=\bigoplus_{n\in\omega}X_{n}$ and
$\mathcal{M}=\\{X_{n}:n\in\omega\\}$. One can code such classes by sets
$C\subseteq\omega^{2}$ as follows:

######  Definition 3.7.

Fix a set $P$. For every $e\in\omega$, let $\mathcal{U}^{P}_{e}=\\{Z\in
2^{\omega}:\exists\sigma\in W^{P}_{e}:\sigma\subseteq Z\\}$. For every
$C\subseteq\omega^{2}$, let $\mathcal{U}^{\mathcal{M}}_{C}=\bigcap_{(e,i)\in
C}\mathcal{U}^{X_{i}}_{e}$.

The following lemma is a core lemma in the analysis of the definitional
complexity of the statement “$\mathcal{U}^{\mathcal{M}}_{C}$ is large”, thanks
to Lemma 3.4.

######  Lemma 3.8 ([15]).

Let $\mathcal{A}$ be a $\Sigma_{1}^{0}$ class. The sentence “$\mathcal{A}$ is
large” is $\Pi_{2}^{0}$.

By Lemma 3.4, a class $\mathcal{U}^{\mathcal{M}}_{C}$ is large iff
$\mathcal{U}^{\mathcal{M}}_{F}$ is large for every finite set $F\subseteq C$.
The class $\mathcal{U}^{\mathcal{M}}_{F}$ is $\Sigma^{0}_{1}(\mathcal{M})$
uniformly in $F$, hence by a relativization of Lemma 3.8, the statement
“$\mathcal{U}^{\mathcal{M}}_{F}$ is large” is $\Pi^{0}_{2}(\mathcal{M})$
uniformly in $F$. The overall statement “$\mathcal{U}^{\mathcal{M}}_{C}$ is
large” is therefore $\Pi^{0}_{1}(C\oplus M^{\prime})$, where $M$ is the set
coding $\mathcal{M}$.

The following lemma shows that instead of working with large classes of the
form $\mathcal{U}^{\mathcal{M}}_{C}$, one can work with partition regular
classes without extra definitional complexity.

######  Lemma 3.9 ([15]).

For every set $C\subseteq\omega^{2}$, there exists $D\leq_{T}C$ such that
$\mathcal{U}^{\mathcal{M}}_{D}=\mathcal{L}(\mathcal{U}^{\mathcal{M}}_{C})$.

###  3.2 $\mathcal{M}$-minimal and $\mathcal{M}$-cohesive classes

When two classes $\mathcal{P}$ and $\mathcal{Q}$ are large, their intersection
$\mathcal{P}\cap\mathcal{Q}$ is not necessarily large. For example, letting
$X$ be a bi-infinite set, both the classes $\mathcal{L}_{X}$ and
$\mathcal{L}_{\overline{X}}$ are large, but their intersection is not, as
witnessed by the 2-cover $X,\overline{X}$ of $\omega$. During the forcing
construction, one will consider multiple properties to be forced, and
therefore will need to ensure that not only the corresponding classes are
large, but so are their intersection. One natural approach consists in
creating a large class which will be minimal for inclusion, in the following
sense:

######  Definition 3.10.

A class $\mathcal{A}$ is _$\mathcal{M}$ -minimal_ if for every
$X\in\mathcal{M}$ and $e\in\omega$, either
$\mathcal{A}\subseteq\mathcal{U}_{e}^{X}$ or
$\mathcal{A}\cap\mathcal{U}_{e}^{X}$ is not large.

Then, in order to decide whether two $\Sigma^{0}_{1}(\mathcal{M})$ properties
$\mathcal{P}$ and $\mathcal{Q}$ are large, one can ask independently whether
$\mathcal{A}\cap\mathcal{P}$ and $\mathcal{A}\cap\mathcal{Q}$ are large. If
both are, then by $\mathcal{M}$-minimality of $\mathcal{A}$,
$\mathcal{A}\subseteq\mathcal{P}$ and $\mathcal{A}\subseteq\mathcal{Q}$, hence
$\mathcal{P}\cap\mathcal{Q}$ is large as well. Eventhough the notion of
minimality was defined for largeness, partition regularity comes for free for
an $\mathcal{M}$-minimal large class.

######  Lemma 3.11 ([15]).

Every $\mathcal{M}$-minimal large class $\mathcal{U}_{C}^{\mathcal{M}}$ is
partition regular.

There exists $\mathcal{M}$-minimal large classes of the form
$\mathcal{U}^{\mathcal{M}}_{C}$. However, the index set $C$ is computationally
too complex, as it is only $M^{\prime\prime}$-computable. Indeed, in order to
create the set $C$ by finite approximations $C_{0}\subseteq
C_{1}\subseteq\dots$, one needs to successively ask whether
$\mathcal{U}^{\mathcal{M}}_{C_{s}}\cap\mathcal{U}_{e}^{X}$ is large, which is
a $\Pi^{0}_{2}(\mathcal{M})$ question. Thankfully, one can consider a weaker
notion with better computational properties, which still satisfies the
compatibility requirements.

######  Definition 3.12.

A class $\mathcal{A}$ is _$\mathcal{M}$ -cohesive_ if for every
$X\in\mathcal{M}$, either $\mathcal{A}\subseteq\mathcal{L}_{X}$ or
$\mathcal{A}\subseteq\mathcal{L}_{\overline{X}}$.

Every $\mathcal{M}$-minimal class is $\mathcal{M}$-cohesive. Moreover, one can
compute the index set $C$ of an $\mathcal{M}$-cohesive class
$\mathcal{U}^{\mathcal{M}}_{C}$ in any PA degree over $M^{\prime}$. Indeed,
instead of deciding whether
$\mathcal{U}^{\mathcal{M}}_{C_{s}}\cap\mathcal{L}_{X}$ is large or not, one
needs to pick a true statement among
“$\mathcal{U}^{\mathcal{M}}_{C_{s}}\cap\mathcal{L}_{X}$ is large” and
“$\mathcal{U}^{\mathcal{M}}_{C_{s}}\cap\mathcal{L}_{\overline{X}}$ is large”.
Choosing a true $\Pi^{0}_{2}(M)$ sentence among two such sentences, known that
one of them is true, can be computed by any PA degree over $M^{\prime}$ (see
Cholak, Jockusch and Slaman [1, Lemma 4.2] for a proof).

######  Lemma 3.13 ([15]).

Let $\mathcal{U}_{C}^{\mathcal{M}}$ be an $\mathcal{M}$-cohesive class. Let
$\mathcal{U}_{D}^{\mathcal{M}}$ and $\mathcal{U}_{E}^{\mathcal{M}}$ be such
that $\mathcal{U}_{C}^{\mathcal{M}}\cap\mathcal{U}_{D}^{\mathcal{M}}$ and
$\mathcal{U}_{C}^{\mathcal{M}}\cap\mathcal{U}_{E}^{\mathcal{M}}$ are both
large. Then so is
$\mathcal{U}_{C}^{\mathcal{M}}\cap\mathcal{U}_{D}^{\mathcal{M}}\cap\mathcal{U}_{E}^{\mathcal{M}}$.

In general, given a large class $\mathcal{U}^{\mathcal{M}}_{C}$, the index set
$C$ can be completed into an index set $D\supseteq C$ in multiple ways to form
an $\mathcal{M}$-minimal large subclass $\mathcal{U}^{\mathcal{M}}_{D}$,
depending on the order in which the questions are asked. However, whenever
$\mathcal{U}_{C}^{\mathcal{M}}$ is $\mathcal{M}$-cohesive, then by Lemma 3.13,
the order of the questions does not matter, thus it contains a unique
$\mathcal{M}$-minimal subclass, which can be explicitly defined as follows:

######  Lemma 3.14.

Given an $\mathcal{M}$-cohesive large class $\mathcal{U}_{C}^{\mathcal{M}}$,
the collection of sets

$\langle\mathcal{U}_{C}^{\mathcal{M}}\rangle:=\bigcap_{e\in\omega,X\in\mathcal{M}}\\{\mathcal{U}_{e}^{X}:\mathcal{U}_{C}^{\mathcal{M}}\cap\mathcal{U}_{e}^{X}\text{
is a large }\\}$

is an $\mathcal{M}$-minimal large class contained in
$\mathcal{U}_{C}^{\mathcal{M}}$.

###  3.3 The $(\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}})_{n\in\omega}$ sequence

Monin and Patey [15, Section 2.5] defined an infinite hierarchy of Scott sets
together with a decreasing sequence of minimal classes for these Scott sets,
playing a central role in the definition of the notion of forcing. The $n$th
level of this hierarchy is responsible for having a good $(n+1)$st jump
control.

The following first proposition is an easy consequence of the uniform low
basis theorem for $\Pi^{0}_{1}$ classes, due to Lawton (see Hirschfeldt and
al. [8, Theorem 4.1]):

######  Proposition 3.15 ([15]).

There exists a sequence of sets $({M}_{n})_{n\in\omega}$ such that :

  * •

$M_{n}$ codes for a countable Scott set $\mathcal{M}_{n}$,

  * •

$\emptyset^{(n)}$ is uniformly coded by an element of $\mathcal{M}_{n}$,

  * •

Each $M_{n}^{\prime}$ is uniformly computable in $\emptyset^{(n+1)}$.

Then, the next proposition follows from our remark on the complexity of the
construction of an $\mathcal{M}$-cohesive large class. Indeed, since
$\mathcal{M}_{n+1}$ contains $M^{\prime}_{n}$ and $\mathcal{M}_{n+1}$ is a
Scott set, then it contains a PA degre over $M^{\prime}_{n}$. Moreover, this
construction is uniform.

######  Proposition 3.16 ([15]).

There exists a sequence of sets $({C}_{n})_{n\in\omega}$ such that :

  * •

$\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$ is an $\mathcal{M}_{n}$-cohesive large
class,

  * •

$\mathcal{U}_{C_{n+1}}^{\mathcal{M}_{n+1}}\subseteq\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle$,

  * •

Each $C_{n}$ is coded by an element of $\mathcal{M}_{n+1}$ uniformly in $n$
and $M_{n+1}$.

##  4 Forcing framework

We now develop the general framework for iterated jump control of solutions to
the Erdős-Moser theorem through forcing. This framework will be applied in
sections 5, 6 and 7 to prove our three main theorems.

###  4.1 Forcing conditions

In order to obtain a layerwise version of strong cone avoidance of
$\mathsf{EM}$ for $\Sigma^{0}_{n}$ operators, our notion of forcing will be
parameterized by a partition regular class $\mathcal{P}$. Assuming
$\mathcal{P}\subseteq\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle$,
this notion of forcing will have a good $(n+1)$st jump control. All along
Section 4, one should think of $\mathcal{P}$ as the partition regular class
$\bigcap_{n\in\omega}\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle$.

######  Definition 4.1.

Given a partition regular class $\mathcal{P}\subseteq 2^{\omega}$, let
$\mathbb{P}_{\mathcal{P}}$ denote the set of all 3-tuples $(\vec{R},\sigma,X)$
such that

  1. 1.

$\vec{R}$ is a finite sequence of tournaments,

  2. 2.

$X\cap\\{0,\dots,|\sigma|\\}=\emptyset$,

  3. 3.

$X\in\mathcal{P}$.

  4. 4.

for all $y\in X$, $\sigma\cup\\{y\\}$ is $\vec{R}$-transitive.

  5. 5.

$X$ is included in a minimal $\vec{R}$-interval of $\sigma$

In other words, $\mathbb{P}_{\mathcal{P}}$ is the set of all 3-tuples
$(\vec{R},\sigma,X)$ such that $(\sigma,X)$ forms an EM condition for each
tournament $R\in\vec{R}$, and such that $X\in\mathcal{P}$. Note that no
effectiveness restriction is given on the reservoir $X$. Given a tournament
$T$, in order to produce an infinite $T$-transitive subset, one will work with
sufficiently generic filters containing the condition $(T,\emptyset,\omega)$.
From now on, fix a partition regular class $\mathcal{P}$.

######  Definition 4.2.

We define the partial order over $\mathbb{P}_{\mathcal{P}}$ as following : we
say that $(\tau,Y,\vec{S})\leq(\sigma,X,\vec{R})$ if
$\sigma\preceq\tau,Y\subseteq X$, $\tau\setminus\sigma\subseteq X$, and
$\vec{R}\subseteq\vec{S}$.

Here again, the extension relation $(\tau,Y,\vec{S})\leq(\sigma,X,\vec{R})$ is
the usual Mathias extension $(\tau,Y)\leq(\sigma,X)$, but in addition, one
commits to be transitive for more and more tournaments simultaneously. Given a
collection $\mathcal{F}\subseteq\mathbb{P}_{\mathcal{P}}$, we let
$G_{\mathcal{F}}:=\bigcup_{(\vec{R},\sigma,X)\in\mathcal{F}}\sigma$.

######  Lemma 4.3.

Let $\mathcal{F}$ be a $\mathbb{P}_{\mathcal{P}}$-filter. For all
$c:=(\vec{R},\sigma,X)$, the set $G_{\mathcal{F}}$ is $\vec{R}$-transitive.

###### Proof.

Suppose otherwise. Then, there exists $x<y<z\in G_{\mathcal{F}}$ a
$\vec{R}$-cycle. By definition of $G_{\mathcal{F}}$, there exists
$d:=(\vec{R}\vec{S},\tau,Y)\in\mathcal{F}$, such that $d\leq c$ and
$\\{x,y,z\\}\subseteq\tau$. Since $\tau$ is $\vec{R}\vec{S}$-transitive, and
thus $\vec{R}$-transitive, $(x,y,z)$ cannot be a $\vec{R}$-cycle. ∎

###  4.2 Forcing question

In this section, we design a forcing question as explained in Section 2.1. The
general idea is the following: given a $\Sigma^{0}_{1}$ formula $(\exists
x)\varphi(G,x)$ and a condition $(\vec{R},\sigma,X)$, one would like to ask
whether there exists some $x\in\omega$ and a finite set $\tau\subseteq X$
satisfying some good combinatorial properties, such that
$\varphi(\sigma\cup\tau,x)$ holds. This naive question is
$\Sigma^{0}_{1}(\vec{R}\oplus X)$. As explained in Section 2.2, one can get
rid of the parameter $\vec{R}$ by universally quantifying over all $m$-tuples
of tournaments, where $m=|\vec{R}|$. By compactness, the question becomes
$\Sigma^{0}_{1}(X)$, which is not enough, since $X$ can be computationally
very complex. The same overapproximation trick cannot be applied for $X$,
since the class of all infinite sets is closed, but not compact. One must
therefore use a second trick: consider the class $\mathcal{L}$ of all
reservoirs $Y$ such that this property holds, that is, of all $Y$ such that
there exists some $x\in\omega$ and a finite set $\tau\subseteq X$ satisfying
some good combinatorial properties, such that $\varphi(\sigma\cup\tau,x)$
holds. Then, ask whether
$\mathcal{L}\cap\mathcal{U}^{\mathcal{M}_{0}}_{C_{0}}$ is large. If it does,
then by $\mathcal{M}_{0}$-minimality of $\mathcal{P}$,
$\mathcal{P}\subseteq\mathcal{L}$, and since $X\in\mathcal{P}$, the property
holds for $X$ in particular.

Before giving the actual definition of the forcing question, let us introduce
a very convenient piece of notation. As explained, given a condition
$(\vec{R},\sigma,X)$, since no effectiveness constraint is imposed on
$\vec{R}$, one will often resort to an over-approximation of $\vec{R}$. This
over-approximation $\mathcal{C}$ has two essential properties: (1) it must
contain $\vec{R}$, and (2) it must be $X$-effectively compact. One can exploit
the $\Pi^{0}_{1}$ constraints in the definition of a condition to obtain a
finer over-approximation: $X$ is included in a minimal interval of $\sigma$
and $\sigma\cup\\{y\\}$ is $\vec{R}$-transitive for every $y\in X$. This
yields the following definition:

######  Definition 4.4.

Let $(\sigma,X)$ be a Mathias condition. For every $m\in\omega$,
$\mathcal{C}_{m}(\sigma,X)$ is the class of all $m$-tuples $\vec{R}$ of
tournaments such that for all $y\in X$, $\sigma\cup\\{y\\}$ is
$\vec{R}$-transitive, and such that $X$ is included in a minimal
$\vec{R}$-interval of $\sigma$.

In particular, for every condition $(\vec{R},\sigma,X)$, letting
$m=|\vec{R}|$, $\vec{R}\in\mathcal{C}_{m}(\sigma,X)$. Thus, the class
$\mathcal{C}_{m}(\sigma,X)$ is an over-approximation of $\vec{R}$. On the
other direction, if $(\sigma,X)$ is a Mathias condition such that
$X\in\mathcal{P}$, then for all $m\in\omega$ and for all
$\vec{R}\in\mathcal{C}_{m}(\sigma,X)$, the 3-tuple $(\vec{R},\sigma,X)$ is a
condition in $\mathbb{P}_{\mathcal{P}}$. The following lemma shows that the
over-approximation $\mathcal{C}_{m}(\sigma,X)$ is $X$-effectively compact, as
desired.

######  Lemma 4.5.

For every Mathias condition $(\sigma,X)$ and every $m\in\omega$,
$\mathcal{C}_{m}(\sigma,X)$ is $\Pi^{0}_{1}(X)$.

###### Proof.

Immediate. Both properties are $\Pi^{0}_{1}$ formulas in $X$. ∎

The following combinatorial lemma is essentially a reformulation of Lemma 2.6.
If one furthermore assumes that $Y\in\mathcal{P}$, then
$(\vec{R},\sigma\cup\tau,Y)$ is a valid $\mathbb{P}_{\mathcal{P}}$-condition.

######  Lemma 4.6.

Let $(\vec{R},\sigma,X)$ be a condition, $\tau\subseteq X$ be a finite
$\vec{R}$-transitive set and $Y\subseteq X$ be an infinite set such that for
every $R\in\vec{R}$, $\tau\to_{R}Y$ or $Y\to_{R}\tau$. Then,
$\vec{R}\in\mathcal{C}_{|\vec{R}|}(\sigma\cup\tau,Y)$.

###### Proof.

Since $(\vec{R},\sigma,X)$ is a condition, $X$ is included in a minimal
interval of $\sigma$ for all $R\in\vec{R}$. Furthermore, since $\tau\cup
Y\subseteq X$, and $\tau\to_{R}Y$ or $Y\to_{R}\tau$, then $Y$ is included in a
minimal interval of $\sigma\cup\tau$ for all $R\in\vec{R}$.

Let $y\in Y$. Suppose for the contradiction that there exists a 3-cycle
$x<y<z$ in $\sigma\cup\tau\cup\\{y\\}$.

  * •

If $x,y\in\sigma$ then since $(\vec{R},\sigma,X)$ is a condition,
$\sigma\cup\\{z\\}$ is $R$-transitive, so $\\{x,y,z\\}$ is not a 3-cycle.

  * •

If $x\in\sigma$ and $y,z\in\tau\cup\\{a\\}$, then since $X$ is included in a
minimal interval of $\sigma$, $x\to_{R}\\{y,z\\}$ or $\\{y,z\\}\to_{R}x$,
hence $\\{x,y,z\\}$ is not a 3-cycle.

  * •

If $x,y,z\in\tau$, then $\\{x,y,z\\}$ is not a 3-cycle by $R$-transitivity of
$\tau$

  * •

If $x,y\in\tau$ and $z=a$, then since $\tau\to_{R}Y$ or $Y\to_{R}\tau$, then
$\\{x,y,z\\}$ is not a 3-cycle.

∎

We are now ready to define the forcing question. Since $\vec{R}$ is only
accessed through an over-approximation, and $X$ through largeness, the forcing
question is parameterized only by the initial segment $\sigma$ and the number
$m$ of tournaments, rather than by the condition $(\vec{R},\sigma,X)$.

######  Definition 4.7.

Let $c:=(\vec{R},\sigma,X)\in\mathbb{P}_{\mathcal{P}}$ be a condition and
$m\geq|\vec{R}|$. Consider $(\exists x)\psi_{e}(G,x)$ a $\Sigma_{1}^{0}$
formula. We define the $\operatorname{{?}{\vdash}}$ relation as follows:

$\sigma\operatorname{{?}{\vdash}}_{m}(\exists x)\leavevmode\nobreak\
\psi_{e}(G,x)$

holds if the class of all $Y\in\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}$ such
that for every $m$-tuple of 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{Y}$
and every $\vec{S}\in\mathcal{C}_{m}(\sigma,Y)$, there is a finite
$\tau\subseteq Y\setminus\\{0,\dots,|\sigma|\\}$ which is $\vec{S}$-transitive
and $\vec{h}$-homogeneous, and some $x\in\omega$ such that
$\psi_{e}(\sigma\cup\tau,x)$ is large.

Inductively, for $n\geq 1$, consider $(\exists x)\psi_{e}(G,x)$ a
$\Sigma_{n+1}^{0}$ formula. We define the $\operatorname{{?}{\vdash}}$
relation as follows:

$\sigma\operatorname{{?}{\vdash}}_{m}(\exists x)\leavevmode\nobreak\
\psi_{e}(G,x)$

holds if the class of all $Y\in\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$ such
that for every $m$-tuple of 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{Y}$
and every $\vec{S}\in\mathcal{C}_{m}(\sigma,Y)$, there is a finite
$\tau\subseteq Y\setminus\\{0,\dots,|\sigma|\\}$ which is $\vec{S}$-transitive
and $\vec{h}$-homogeneous, some $x\in\omega$ and $\ell\geq m$ such that
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$ is large.

The over-approximation of $\vec{R}$ comes at no extra cost from a definitional
complexity viewpoint. On the other hand, over-approximating the reservoir $X$
by a large class yields a $\Pi_{1}^{0}(\mathcal{M}_{n+1})$ forcing question
for $\Sigma^{0}_{n+1}$ formulas, which is sufficient for arithmetic
reductions, but not a layerwise cone avoidance.

######  Lemma 4.8.

Let $n\in\omega$ and $c:=(\vec{R},\sigma,X)\in\mathbb{P}_{\mathcal{P}}$.
Consider $(\exists x)\psi_{e}(G,x)$ a $\Sigma_{n+1}^{0}$ formula. The formula
$(\sigma\operatorname{{?}{\vdash}}_{m}(\exists x)\psi_{e}(G,x))$ is
$\Pi_{1}^{0}(\mathcal{M}_{n+1})$, for all $m\in\omega$.

###### Proof.

We prove this result inductively over $n$. The sentence is of the form
“$\mathcal{L}\cap\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$ is large”, where
$\mathcal{L}$ is the class of all $Y$ such that for every $m$-tuple of
2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{Y}$ and every
$\vec{S}\in\mathcal{C}_{m}(\sigma,Y)$, there is a finite $\tau\subseteq
Y\setminus\\{0,\dots,|\sigma|\\}$ which is $\vec{S}$-transitive and
$\vec{h}$-homogeneous, and some $x\in\omega$ such that

  * •

for $n=0$, $\psi_{e}(\sigma\cup\tau,x)$.

  * •

for $n>0$, there is some $\ell\geq m$ such that
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$.

By a compactness argument, $\mathcal{L}$ is also the class of all $Y$ such
that there exists $t\in\omega$ such that for every $m$-tuple of 2-colorings
$\vec{h}=h_{0},\dots,h_{m-1}\in 2^{t}$ and every $m$-tuple $\vec{S}$ of
tournaments over $\\{0,\dots t\\}$ such that for all $y\in\\{0,\dots,t\\}\cap
Y,\sigma\cup\\{y\\}$ is $\vec{S}$-transitive, there is a finite
$\tau\subseteq\\{0,\dots,t\\}\cap Y\setminus\\{0,\dots,|\sigma|\\}$ which is
$\vec{S}$-transitive and $\vec{h}$-homogeneous, and some $x\in\omega$ such
that

  * •

for $n=0$, $\psi_{e}(\sigma\cup\tau,x)$.

  * •

for $n>0$, there is some $\ell\geq m$ such that
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$.

The first item is $\Sigma^{0}_{1}$, and by induction hypothesis, the second
item $\sigma\cup\tau\operatorname{{?}{\nvdash}}\neg\psi_{e}(G,x)$ is
$\Sigma_{1}^{0}(\mathcal{M}_{n})$, hence $\mathcal{L}$ is a
$\Sigma^{0}_{1}(\mathcal{M}_{n})$ class.

By Lemma 3.4, the class $\mathcal{L}\cap\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$
is large if and only if for all finite set $F\subseteq C_{n}$,
$\mathcal{L}\cap\mathcal{U}_{F}^{\mathcal{M}_{n}}$ is also large. Since
$\mathcal{L}\cap\mathcal{U}_{F}^{\mathcal{M}_{n}}$ is $\Sigma^{0}_{1}(M_{n})$
uniformly in $F$, then by a relativized Lemma 3.8, the sentence
“$\mathcal{L}\cap\mathcal{U}_{F}^{\mathcal{M}_{n}}$ is large” is
$\Pi_{2}^{0}(M_{n})$ uniformly in $F$, hence a $\Pi_{1}^{0}(M_{n}^{\prime})$
sentence uniformly in $F$, and thus, by Proposition 3.15, a
$\Pi_{1}^{0}(\emptyset^{(n+1)})$ sentence. This makes
$\mathcal{L}\cap\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$ largeness a
$\Pi_{1}^{0}(C_{n}\oplus\emptyset^{(n+1)})$ sentence, Moreover, by Proposition
3.16 and Proposition 3.15,
$(C_{n}\oplus\emptyset^{(n+1)})\in\mathcal{M}_{n+1}$, hence, the sentence
“$\mathcal{L}\cap\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$ is large” is a
$\Pi_{1}^{0}(\mathcal{M}_{n+1})$ sentence.

∎

We now define the forcing relation for arithmetic formulas. The base cases for
$\Sigma^{0}_{1}$ and $\Pi^{0}_{1}$ formulas, as well as the $\Sigma^{0}_{n+1}$
case, are quite straightforward. The interesting case is for $\Pi^{0}_{n+1}$
formulas $(\forall x)\neg\psi_{e}(G,x)$: it asserts that for every
$x\in\omega$ and extension $d=(\vec{R}\vec{S},\sigma\cup\tau,Y)$ of $c$, the
forcing question
$\sigma\cup\tau\operatorname{{?}{\vdash}}_{|\vec{R}\vec{S}|}\neg\psi_{e}(G,x)$
will hold. Assuming that the forcing question meets its specifications, that
is, if the forcing question holds for a formula, then there exists an
extension forcing this formula, then the forcing relation for $\Pi^{0}_{n+1}$
formulas is a density statement: it asserts that for every $x\in\omega$, the
set of conditions forcing $\neg\psi_{e}(G,x)$ is dense below $c$. Thus, for
every sufficiently generic filter $\mathcal{F}$ containing $c$ and every
$x\in\omega$, there will be a condition $d_{x}\in\mathcal{F}$ forcing
$\neg\psi_{e}(G,x)$.

######  Definition 4.9.

Let $c:=(\vec{R},\sigma,X)\in\mathbb{P}_{\mathcal{P}}$. Consider $(\exists
x)\psi_{e}(G,x)$ a $\Sigma_{1}^{0}$ formula. We define the $\Vdash$ relation
as follows:

  * •

$c\Vdash(\exists x)\psi_{e}(G,x)$ if $(\exists x)\psi_{e}(\sigma,x)$.

  * •

$c\Vdash(\forall x)\neg\psi_{e}(G,x)$ if $(\forall\tau\subseteq X)(\forall
x)(\tau$ is $\vec{R}$-transitive $\implies\neg\psi_{e}(\sigma\cup\tau,x))$.

Then, inductively, for $n\geq 1$, let $(\exists x)\psi_{e}(G,x)$ be a
$\Sigma_{n+1}^{0}$ formula. Then,

  * •

$c\Vdash(\exists x)\psi_{e}(G,x)$ if $(\exists x)(c\Vdash\psi_{e}(G,x))$.

  * •

$c\Vdash(\forall x)\neg\psi_{e}(G,x)$ if $(\forall\tau\subseteq X)(\forall
x)(\forall\ell\geq|\vec{R}|)(\tau$ is
$\vec{R}$-transitive$\implies\sigma\cup\tau\operatorname{{?}{\vdash}}_{\ell}\neg\psi_{e}(G,x))$.

######  Remark 4.10.

Every $\Sigma^{0}_{1}(G)$ formula $\psi(G)$ can be expressed without loss of
generality of the form $\Phi^{G}_{e}(0)\downarrow$. By the use property, the
notion of Turing functional can be extended to finite length oracles, which
induces an extension of the formula $\psi(G)$ to finite strings, such that
$\psi(G)$ holds iff $\psi(G\upharpoonright_{k})$ holds for some $k\in\omega$.
Moreover, the formula $\psi(\sigma)$ can be chosen so that if $\psi(\sigma)$
holds, then so does $\psi(\tau)$ for every $\tau\succeq\sigma$. Throughout
this article, we will always assume that $\Sigma^{0}_{1}$ formulas are in this
normal form.

The following lemma shows that the forcing relation is stable under condition
extension.

######  Lemma 4.11.

Fix $n\geq 0$. Let $d,c\in\mathbb{P}_{\mathcal{P}}$ be such that $d\leq c$,
and let $(\exists x)\psi_{e}(G,x)$ be a $\Sigma_{n+1}^{0}$ formula.

  * (1)

If $c\Vdash(\exists x)\psi_{e}(G,x)$ then $d\Vdash(\exists x)\psi_{e}(G,x)$.

  * (2)

If $c\Vdash(\forall x)\neg\psi_{e}(G,x)$ then $d\Vdash(\forall
x)\neg\psi_{e}(G,x)$.

###### Proof.

Let $c:=(\vec{R},\sigma,X)$ and $d:=(\vec{R}\vec{S},\sigma\cup\tau,Y)$.
Suppose $n=0$.

  * •

If $c\Vdash(\exists x)\psi_{e}(G,x)$, then $(\exists x)\psi_{e}(\sigma,x)$.
Moreover, $\sigma\cup\tau\succeq\sigma$, so by monotonicity of $\psi_{e}$ (see
Remark 4.10), $(\exists x)\psi_{e}(\sigma\cup\tau,x)$, hence $d\Vdash(\exists
x)\psi_{e}(G,x)$.

  * •

If $c\Vdash(\forall x)\neg\psi_{e}(G,x)$, then $(\forall\rho\subseteq
X)(\forall x)(\rho$ is $\vec{R}$-transitive
$\implies\neg\psi_{e}(\sigma\cup\rho,x))$. Then, pick $x\in\omega$ and
$\rho\subseteq Y$. Then, $\tau\cup\rho\subseteq\tau\cup Y\subseteq X$.
Moreover, since $d$ is a condition, if $\rho$ is $\vec{R}\vec{S}$-transitive,
$\sigma\cup\tau\cup\rho$ is $\vec{R}\vec{S}$-transitive, and in particular,
$\tau\cup\rho$ is $\vec{R}$-transitive, hence
$\neg\psi_{e}(\sigma\cup\tau\cup\rho,x)$. This yields that
$(\forall\rho\subseteq Y)(\forall x)(\rho$ is
$\vec{R}\vec{S}$-transitive$\implies\neg\psi_{e}(\sigma\cup\tau\cup\rho,x))$,
i.e., $d\Vdash(\forall x)\neg\psi_{e}(G,x)$.

Inductively, suppose $n>0$.

  * •

If $c\Vdash(\exists x)\psi_{e}(G,x)$, then $(\exists
x)c\Vdash\psi_{e}(\sigma,x)$, hence, by induction hypothesis, $(\exists
x)d\Vdash\psi_{e}(\sigma,x)$, i.e., $d\Vdash(\exists x)\psi_{e}(G,x)$.

  * •

If $c\Vdash(\forall x)\neg\psi_{e}(G,x)$, then $(\forall\rho\subseteq
X)(\forall x)(\forall\ell\geq|\vec{R}|)(\rho$ is
$\vec{R}$-transitive$\implies\sigma\cup\rho\operatorname{{?}{\vdash}}_{\ell}\neg\psi_{e}(G,x))$.
Then, pick $x\in\omega$, $\rho\subseteq Y$ and $\ell\geq|\vec{R}\vec{S}|$.
Then, $\tau\cup\rho\subseteq\tau\cup Y\subseteq X$. Moreover, since $d$ is a
condition, if $\rho$ is $\vec{R}\vec{S}$-transitive, $\sigma\cup\tau\cup\rho$
is $\vec{R}\vec{S}$-transitive, and in particular, $\tau\cup\rho$ is
$\vec{R}$-transitive, thus, since $\ell\geq|\vec{R}|$,
$\sigma\cup\rho\operatorname{{?}{\vdash}}_{\ell}\neg\psi_{e}(G,x)$ holds. This
yields that $(\forall\rho\subseteq Y)(\forall
x)(\forall\ell\geq\vec{R}\vec{S})(\rho$ is $\vec{R}\vec{S}$-transitive
$\implies\sigma\cup\tau\cup\rho\operatorname{{?}{\vdash}}_{\ell}\neg\psi_{e}(G,x))$,
i.e., $d\Vdash(\forall x)\neg\psi_{e}(G,x)$.

∎

We now prove the core lemma for this notion of forcing: the forcing question
meets its specifications. It implies in particular the density of the set of
conditions forcing a property or its complement. Until now, the only
hypothesis on the class $\mathcal{P}$ was its partition regularity. Here,
since we over-approximate the reservoir $X$ by a class $\mathcal{L}$ such that
$\mathcal{L}\cap\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$ is large, one needs to
assert some compatibility between $\mathcal{P}$ and $\mathcal{L}$ to deduce
that $X\in\mathcal{L}$. Since $\mathcal{L}$ will be an intersection of
$\Sigma^{0}_{1}(\mathcal{M}_{n})$ classes, assuming
$\mathcal{M}_{n}$-minimality of $\mathcal{P}$, that is,
$\mathcal{P}\subseteq\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle$, we
will have $X\in\mathcal{P}\subseteq\mathcal{L}$.

######  Lemma 4.12.

Let $n\in\omega$ and $c:=(\vec{R},\sigma,X)\in\mathbb{P}_{\mathcal{P}}$ such
that
$\mathcal{P}\subseteq\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle$.
Consider $(\exists x)\psi_{e}(G,x)$ a $\Sigma_{n+1}^{0}$ formula. Let
$m\geq|\vec{R}|$.

  * •

If $\sigma\operatorname{{?}{\vdash}}_{m}(\exists x)\psi_{e}(G,x)$ then
$\exists d\leq c$ such that $d\Vdash(\exists x)\psi_{e}(G,x)$.

  * •

If $\sigma\operatorname{{?}{\nvdash}}_{m}(\exists x)\psi_{e}(G,x)$ then
$\exists d\leq c$ such that $d\Vdash(\forall x)\neg\psi_{e}(G,x)$.

###### Proof.

First, suppose $n=0$.

  * •

Suppose $\sigma\operatorname{{?}{\vdash}}_{m}(\exists x)\psi_{e}(G,x)$. Let
$\mathcal{L}$ denote the class of all $Y$ such that for every $m$-tuple of
2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{Y}$ and every
$\vec{S}\in\mathcal{C}_{m}(\sigma,Y)$, there is a finite $\tau\subseteq
Y\setminus\\{0,\dots,|\sigma|\\}$ which is $\vec{S}$-transitive and
$\vec{h}$-homogeneous, and some $x\in\omega$ such that
$\psi_{e}(\sigma\cup\tau,x)$. Then,
$\mathcal{L}\cap\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}$ is large. Since
$\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}$ is $\mathcal{M}_{0}$-cohesive,
$\langle\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}\rangle$ is
$\mathcal{M}_{0}$-minimal. This yields that
$\langle\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}\rangle\subseteq\mathcal{L}$.
Moreover,
$X\in\mathcal{P}\subseteq\langle\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}\rangle\subseteq\mathcal{L}$.
By a compactness argument, this yields that there exists $t\in\omega$ such
that for every 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{t}$, there is a
finite $\tau\subseteq X\cap\\{0,\dots,t\\}$ which is $\vec{R}$-transitive and
$\vec{h}$-homogeneous and some $x\in\omega$ such that
$\psi_{e}(\sigma\cup\tau,x)$. Let us build a specific $\vec{h}$ such that the
$\tau$ we get gives us the extension of $c$ we look for. For every $i<m$,
$a\leq t$, and $y\in X$, $y>t$, let $g_{i,a}(y):=1$ if $aR_{i}y$, and 0
otherwise (if $m>i\geq|\vec{R}|$, then let $R_{i}$ be a fixed dummy
tournament). Since $\mathcal{P}$ is partition regular, then there is some
$\vec{g}$-homogeneous set $H\subseteq X$ in $\mathcal{P}$. For every $i<m$ and
$a\leq t$, let $h_{i}(a)=1$ if $\\{a\\}\to_{R_{i}}H$, and $0$ otherwise. Since
$X\in\mathcal{L}$, there exists a finite $\tau\subseteq X\cap\\{0,\dots,t\\}$
which is $\vec{R}$-transitive and $\vec{h}$-homogeneous and some $x\in\omega$
such that $\psi_{e}(\sigma\cup\tau,x)$ holds. Moreover, by Lemma 4.6,
$\vec{R}\in\mathcal{C}_{|\vec{R}|}(\sigma\cup\tau,H)$. This makes
$d:=(\vec{R},\sigma\cup\tau,H)$ a valid condition such that $d\Vdash(\exists
x)\psi_{e}(G,x)$.

  * •

Suppose $\sigma\operatorname{{?}{\nvdash}}_{m}(\exists x)\psi_{e}(G,x)$. Then,
there exists $s\in\omega$ and $Y_{0},\dots Y_{s}$ a partition of $\omega$ such
that for all $i\leq s$, $(\dagger)$ either
$Y_{i}\not\in\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}$ or there exists an
$m$-tuple of 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{Y_{i}}$ and an
$\vec{S}\in\mathcal{C}_{m}(\sigma,Y_{i})$, such that for all $\tau\subseteq
Y_{i}\setminus\\{0,\dots,|\sigma|\\}$ which is $\vec{S}$-transitive and
$\vec{h}$-homogeneous, and for all $x\in\omega$,
$\neg\psi_{e}(\sigma\cup\tau,x)$.

Since $\mathcal{P}$ is partition regular, then there is some $i\leq s$ such
that $X\cap Y_{i}\in\mathcal{P}$. In particular, $X\cap
Y_{i}\in\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}$, so by upward-closure of
partition regularity, $Y_{i}\in\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}$. Let
$\vec{h}$ and $\vec{S}\in\mathcal{C}_{m}(\sigma,Y)$ be witnesses of
$(\dagger)$. By partition regularity of $\mathcal{P}$, there is a
$\vec{h}$-homogeneous subset $H\subseteq X\cap Y_{i}$ in $\mathcal{P}$. The
condition $d:=(\vec{R}\vec{S},\sigma,H)$ is a valid extension of $c$ such that
$d\Vdash(\forall x)\neg\psi_{e}(G,x)$.

Now, inductively, suppose $n>0$.

  * •

Suppose $\sigma\operatorname{{?}{\vdash}}_{m}(\exists x)\psi_{e}(G,x)$. Let
$\mathcal{L}$ denote the class of all $Y$ such that for every $m$-tuple of
2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{Y}$ and every
$\vec{S}\in\mathcal{C}_{m}(\sigma,Y)$, there is a finite $\tau\subseteq
Y\setminus\\{0,\dots,|\sigma|\\}$ which is $\vec{S}$-transitive and
$\vec{h}$-homogeneous, and some $x,\ell\in\omega$ such that
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$. Then,
$\mathcal{L}\cap\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$ is large. Since
$\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$ is $\mathcal{M}_{n}$-cohesive,
$\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle$ is
$\mathcal{M}_{n}$-minimal. This yields that
$\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle\subseteq\mathcal{L}$.
Moreover,
$X\in\mathcal{P}\subseteq\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle\subseteq\mathcal{L}$.
By a compactness argument, this yields that there exists $t\in\omega$ such
that for every $m$-tuple of 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in
2^{t}$, there is a finite $\tau\subseteq X\cap\\{0,\dots,t\\}$ which is
$\vec{R}$-transitive and $\vec{h}$-homogeneous and some $x,\ell\in\omega$ such
that $\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$. Let
us build a specific $\vec{h}$ such that the $\tau$ we get gives us the
extension of $c$ we look for.

For every $i<m$, $a\leq t$, and $y\in X$, $y>t$, let $g_{i,a}(y):=1$ if
$aR_{i}y$, and 0 otherwise.

By partition regularity of $\mathcal{P}$, there is some $\vec{g}$-homogeneous
set $H\subseteq X$ in $\mathcal{P}$.

For every $i<m$ and $a\leq t$, let $h_{i}(a)=1$ if $\\{a\\}\to_{R_{i}}H$, and
$0$ otherwise. Now, there exists a finite $\tau\subseteq X\cap\\{0,\dots,t\\}$
which is $\vec{R}$-transitive and $\vec{h}$-homogeneous and some
$x,\ell\in\omega$ such that
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$. Moreover,
by Lemma 4.6, $\vec{R}\in\mathcal{C}_{m}(\sigma\cup\tau,H)$. This makes
$d:=(\vec{R},\sigma\cup\tau,H)$ a valid condition such that for some $\ell\geq
m$, $\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$,
hence, by induction hypothesis, there exists $p\leq d\leq c$ such that
$p\Vdash\psi_{e}(G,x)$, hence, $p\Vdash(\exists x)\psi_{e}(G,x)$.

  * •

Suppose $\sigma\operatorname{{?}{\nvdash}}_{m}(\exists x)\psi_{e}(G,x)$. Then,
there exists $s\in\omega$ and $Y_{0},\dots Y_{s}$ a partition of $\omega$ such
that for all $i\leq s$, $(\dagger)$ either
$Y_{i}\not\in\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$ or there exists an
$m$-tuple of 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{Y_{i}}$ and an
$\vec{S}\in\mathcal{C}_{m}(\sigma,Y_{i})$, such that for all $\tau\subseteq
Y_{i}\setminus\\{0,\dots,|\sigma|\\}$ which is $\vec{S}$-transitive and
$\vec{h}$-homogeneous, and for all $x\in\omega$ and $\ell\geq m$,
$\sigma\cup\tau\operatorname{{?}{\vdash}}_{\ell}\neg\psi_{e}(G,x)$.

By partition regularity of $\mathcal{P}$, there is some $i\leq s$ such that
$X\cap Y_{i}\in\mathcal{P}$. In particular, $X\cap
Y_{i}\in\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$, so by upward-closure of
partition regularity, $Y_{i}\in\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}$. Let
$\vec{h}$ and $\vec{S}\in\mathcal{C}_{m}(\sigma,Y)$ be witnesses of
$(\dagger)$. By partition regularity of $\mathcal{P}$, there is a
$\vec{h}$-homogeneous subset $H\subseteq X\cap Y_{i}$ in $\mathcal{P}$. The
condition $d:=(\vec{RS},\sigma,H)$ is a valid extension of $c$ such that
$d\Vdash(\forall x)\neg\psi_{e}(G,x)$.

∎

######  Definition 4.13.

Let $n\in\omega$, and $\mathcal{F}\subseteq\mathbb{P}_{\mathcal{P}}$ be a
filter. The set $\mathcal{F}$ is said _$n$ -generic_ if for all $k<n$, and
every $\Sigma_{k+1}^{0}$ formula $(\exists x)\psi_{e}(G,x)$, there exists a
condition $c\in\mathcal{F}$ such that $c\Vdash(\exists x)\psi_{e}(G,x)$ or
$c\Vdash(\forall x)\neg\psi_{e}(G,x)$

######  Lemma 4.14.

Fix $n\in\omega$, and let $\mathcal{F}$ be a sufficiently generic
$\mathbb{P}_{\mathcal{P}}$-filter, where
$\mathcal{P}\subseteq\langle\mathcal{U}^{\mathcal{M}_{n}}_{\mathcal{C}_{n}}\rangle$.
Then $\mathcal{F}$ is $n$-generic.

###### Proof.

Let $k<n$, and let $(\exists x)\psi_{e}(G,x)$ be a $\Sigma_{k+1}$ formula. Let
$\mathcal{D}$ be the collection of all conditions deciding $(\exists
x)\psi_{e}(G,x)$. We claim that $\mathcal{D}$ is dense. Let
$c:=(\vec{R},\sigma,X)\in\mathcal{F}$, and $m:=|\vec{R}|$. Suppose
$\sigma\operatorname{{?}{\vdash}}_{m}(\exists x)(\psi_{e}(G,x)$. Then, by
Lemma 4.12 there exists $d\leq c$ such that $d\Vdash(\exists
x)(\psi_{e}(G,x)$. Otherwise, $\sigma\operatorname{{?}{\nvdash}}_{m}(\exists
x)(\psi_{e}(G,x)$. Then, by Lemma 4.12 there exists $d\leq c$ such that
$d\Vdash(\forall x)\neg(\psi_{e}(G,x)$. Either way, there is some $d\leq c$ in
$\mathcal{D}$, so $\mathcal{D}$ is dense. Since $\mathcal{F}$ is sufficiently
generic, $\mathcal{F}\cap\mathcal{D}\neq\emptyset$. ∎

######  Lemma 4.15.

Let $n\in\omega$, and let $c:=(\vec{R},\sigma,X)\in\mathbb{P}_{\mathcal{P}}$
such that if $n>0$ then
$\mathcal{P}\subseteq\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$.
Consider $(\exists x)\psi_{e}(G,x)$ a $\Sigma_{n+1}^{0}$ formula. Then,
$(c\Vdash(\exists x)\psi_{e}(G,x))\land(c\Vdash(\forall x)\neg\psi_{e}(G,x))$
never holds.

###### Proof.

We prove this inductively. Suppose otherwise.

  * •

First, suppose $n=0$. Then, $(\exists x)\psi_{e}(\sigma,x)$ holds, and
$(\forall\tau\subseteq X)(\forall y)(\tau$ is $\vec{R}$-transitive
$\implies\neg\psi_{e}(\sigma\cup\tau,y))$. In particular, for
$\tau=\emptyset$, $\tau$ is $\vec{R}$-transitive, hence,
$\neg\psi_{e}(\sigma,x)$ holds, yielding a contradiction.

  * •

Now, suppose $n>0$. Then, $(\exists x)(c\Vdash\psi_{e}(G,x))$, and
$(\forall\tau\subseteq X)(\forall y)(\forall\ell\geq|\vec{R}|)(\tau$ is
$\vec{R}$-transitive$\implies\sigma\cup\tau\operatorname{{?}{\vdash}}_{\ell}\neg\psi_{e}(G,y))$.
In particular, for $\tau=\emptyset$, and $\ell=\vec{R}$, $\tau$ is
$\vec{R}$-transitive, hence,
$\sigma\operatorname{{?}{\vdash}}_{\ell}\neg\psi_{e}(G,x))$. Since
$\mathcal{P}\subseteq\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$,
this yields by Lemma 4.12 that there exists $d\leq c$ such that
$d\Vdash\neg\psi_{e}(G,x)$. However, by Lemma 4.11, $d\Vdash\psi_{e}(G,x)$.
This contradicts induction hypothesis.

∎

The following lemma is known as the “forcing implies truth” lemma: if a
condition forces a formula, then for every sufficiently generic filter
containing this condition, the formula will hold.

######  Lemma 4.16.

Let $n\in\omega$, and $\mathcal{F}\subseteq\mathbb{P}_{\mathcal{P}}$ be a
filter such that if $n>0$ then $\mathcal{F}$ is $(n-1)$-generic and
$\mathcal{P}\subseteq\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$.
Let $(\exists x)\psi_{e}(G,x)$ be a $\Sigma_{n+1}^{0}$ formula. Let
$c\in\mathcal{F}$.

  * •

If $c\Vdash(\exists x)\psi_{e}(G,x)$, then $(\exists
x)\psi_{e}(G_{\mathcal{F}},x)$ holds.

  * •

If $c\Vdash(\forall x)\neg\psi_{e}(G,x)$, then $(\forall
x)\neg\psi_{e}(G_{\mathcal{F}},x)$ holds.

###### Proof.

Suppose $n=0$.

  * •

If $c\Vdash(\exists x)\psi_{e}(G,x)$, then $(\exists x)\psi_{e}(\sigma,X)$,
and since $G_{\mathcal{F}}\succeq\sigma$, $(\exists
x)\psi_{e}(G_{\mathcal{F}},X)$.

  * •

If $c\Vdash(\forall x)\neg\psi_{e}(G,x)$, then $(\forall\tau\subseteq
X)(\forall x)(\tau$ is $\vec{R}$-transitive
$\implies\neg\psi_{e}(\sigma\cup\tau,x))$. Suppose for the contradiction that
$(\exists x)\psi_{e}(G_{\mathcal{F}},x)$. Then, by Remark 4.10, there exists
$\tau\subseteq G_{\mathcal{F}}\subseteq X$ such that
$\psi_{e}(\sigma\cup\tau,x)$. However, by Lemma 4.3, $G_{\mathcal{F}}$ is
$\vec{R}$-transitive, hence $\tau$ is $\vec{R}$-transitive, contradicting
hypothesis.

Inductively, suppose $n>0$.

  * •

If $c\Vdash(\exists x)\psi_{e}(G,x)$, then $c\Vdash\psi_{e}(\sigma,x)$ for
some $x\in\omega$. By induction hypothesis, $(\exists
x)\psi_{e}(G_{\mathcal{F}},x)$.

  * •

If $c\Vdash(\forall x)\neg\psi_{e}(G,x)$, then $(\forall\tau\subseteq
X)(\forall x)(\forall\ell\geq|\vec{R}|)(\tau$ is
$\vec{R}$-transitive$\implies\sigma\cup\tau\operatorname{{?}{\vdash}}_{\ell}\neg\psi_{e}(G,x))$.
Fix some $x\in\omega$. By $(n-1)$-genericity of $\mathcal{F}$, there exists
some $d\in\mathcal{F}$ such that $d\Vdash\psi_{e}(G,x)$ or
$d\Vdash\neg\psi_{e}(G,x)$. By compatibility of the conditions in a filter,
and by Lemma 4.11, we can suppose without loss of generality that $d\leq c$.
In particular, $d:=(\vec{R}\vec{S},\sigma\cup\tau,Y)$. Since $\tau\subseteq X$
and is $\vec{R}$-transitive and since $|\vec{R}\vec{S}|\geq|\vec{R}|$,
$\sigma\cup\tau\operatorname{{?}{\vdash}}_{|\vec{R}\vec{S}|}\neg\psi_{e}(G,x))$.

By Lemma 4.12, there is some $p\leq d$ such that $p\Vdash\neg\psi_{e}(G,x))$.
Since $p\leq d$ and
$\mathcal{P}\subseteq\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$,
then by Lemma 4.15, $d\Vdash\neg\psi_{e}(G,x)$. By induction hypothesis,
$\psi_{e}(G_{\mathcal{F}},x)$ holds, and this, for every $x$, so $(\forall
x)\psi_{e}(G_{\mathcal{F}},x)$.

∎

######  Lemma 4.17.

Let $\mathcal{F}\subseteq\mathbb{P}_{\mathcal{P}}$ be a 1-generic filter. Then
$G_{\mathcal{F}}$ is infinite.

###### Proof.

By 1-genericity of $\mathcal{F}$, for all $x$, there exists
$c:=(\vec{R},\sigma,X)\in\mathcal{F}$ such that $c\Vdash(\exists y>x)(y\in G)$
or $c\Vdash(\forall y>x)(y\not\in G)$. Suppose the latter holds for some $x$.

Unfolding the definition of the forcing relation for $\Pi^{0}_{1}$ formulas,
$(\forall\tau\subseteq X)(\forall y)(\tau\mbox{ is
}\vec{R}\mbox{-transitive}\implies y\leq x\vee y\not\in\sigma\cup\tau)$. Since
$X$ is infinite, there is some $y\in X$ such that $y>x$. Letting
$\tau=\\{y\\}$, $\tau$ is $\vec{R}$-transitive, $y>x$ and
$y\in\sigma\cup\\{y\\}$. Contradiction. ∎

##  5 Strong cone avoidance for arithmetic reductions

We now use the framework developed in Section 4 to prove that $\mathsf{EM}$
admits strong cone avoidance for arithmetic reductions. In other words, the
goal of this section is to prove our first main theorem:

######  Main Theorem 1.3.

If $B$ is not arithmetic, then for every tournament $T$, there is an infinite
transitive subtournament $H$ such that $B$ is not $H$-arithmetic.

Recall that in Section 3.3, we stated the existence of an infinite sequence of
Scott sets $\mathcal{M}_{0}\subseteq\mathcal{M}_{1}\subseteq\dots$
respectively coded by some sets $M_{0},M_{1},\dots$, together with a sequence
of sets $C_{0},C_{1},\dots$ such that $\emptyset^{(n+1)}\oplus
C_{n}\in\mathcal{M}_{n+1}$, $M^{\prime}_{n}\leq_{T}\emptyset^{(n+1)}$ and

$\langle\mathcal{U}_{C_{0}}^{\mathcal{M}_{0}}\rangle\supseteq\langle\mathcal{U}_{C_{1}}^{\mathcal{M}_{1}}\rangle\supseteq\dots$

are partition regular classes. By Lemma 3.4, the class
$\mathcal{P}_{\omega}=\bigcap_{n}\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle$
is again partition regular.

######  Definition 5.1.

Let $\mathbb{P}_{\omega}=\mathbb{P}_{\mathcal{P}_{\omega}}$.

Since
$\mathcal{P}_{\omega}=\bigcap_{n}\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle$,
then all the hypothesis of the form
$\mathcal{P}\subseteq\langle\mathcal{U}_{C_{n}}^{\mathcal{M}_{n}}\rangle$ hold
in Section 4. By Lemma 4.8, the forcing question to decide $\Sigma^{0}_{n}(G)$
formulas is $\Pi^{0}_{1}(\mathcal{M}_{n})$, hence the definitional complexity
of the forcing question is not at the same level in the hierarchy as the
formula we force. Thankfully, in the case of arithmetic reductions, this
difference is not relevant. Indeed, all the sets in $\mathcal{M}_{n}$ are
arithmetic, so if a set $B$ is not arithmetic, it is in particular not
$\Pi^{0}_{2}(\mathcal{M}_{n})$ for any $n$.

######  Lemma 5.2.

Suppose $B$ is not arithmetic. Let $\mathcal{F}$ be a sufficiently generic
$\mathbb{P}_{\omega}$-filter. Then for every $n\in\omega$ and every
$\Sigma^{0}_{n}$ formula $\varphi(G,x)$, there exists $d\in\mathcal{F}$ such
that

$(\exists x\notin B)(d\Vdash\varphi(G,x))\ \lor\ (\exists x\in
B)(d\Vdash\neg\varphi(G,x)).$

###### Proof.

Fix some $c=(\vec{R},\sigma,X)\in\mathcal{F}$, and let $\varphi(G,x)$ be a
$\Sigma^{0}_{n}$ formula for some $n>0$. Say $m=|\vec{R}|$. Let
$W=\\{x:\sigma\operatorname{{?}{\vdash}}_{m}\varphi(G,x)\\}$. By Lemma 4.8,
the set $W$ is $\Pi^{0}_{n}(\mathcal{M}_{n})$. Since $B$ is not arithmetic,
$W\neq B$. Let $x\in W\Delta B=(W\setminus B)\cup(B\setminus W)$. One of the
two cases holds:

  * •

$x\in W\setminus B$, then, by Lemma 4.12, there exists a condition $d\leq c$
such that $d\Vdash\varphi(G,x)$.

  * •

$x\in B\setminus W$, then, by Lemma 4.12, there exists a condition $d\leq c$
such that $d\Vdash\neg\varphi(G,x)$.

In both cases, by genericity of $\mathcal{F}$, there is such a $d$ in
$\mathcal{F}$. ∎

We are now ready to prove our first main theorem.

###### Proof of 1.3.

Fix a non-arithmetic set $B$, a tournament $T$, and let $\mathcal{F}$ be a
sufficiently generic $\mathbb{P}_{\omega}$-filter containing the condition
$(T,\emptyset,\omega)$. By Lemma 4.14, $\mathcal{F}$ is $n$-generic for every
$n\in\omega$. By Lemma 4.3, $G_{\mathcal{F}}$ is $T$-transitive, and by Lemma
4.17, $G_{\mathcal{F}}$ is infinite.

We claim that $B$ is not $G_{\mathcal{F}}$-arithmetic: Fix a $\Sigma^{0}_{n}$
formula $\varphi(G,x)$. By Lemma 5.2, there exists some $c\in\mathcal{F}$ such
that

$(\exists x\notin B)(c\Vdash\varphi(G,x))\ \lor\ (\exists x\in
B)(c\Vdash\neg\varphi(G,x)).$

By Lemma 4.16, $(\exists x\notin B)\varphi(G_{\mathcal{F}},x)\lor(\exists x\in
B)\neg\varphi(G_{\mathcal{F}},x)$, hence $B$ is not
$G_{\mathcal{F}}$-arithmetic. ∎

##  6 Layerwise strong cone avoidance

In this section, we are going to twist the previous notion of forcing to
obtain a layerwise version of 1.3. More precisely, the goal of this section is
to prove the following theorem:

######  Main Theorem 1.4.

Fix $n\geq 1$. If $B$ is not $\Sigma^{0}_{n}$, then for every tournament $T$,
there is an infinite transitive subtournament $H$ such that $B$ is not
$\Sigma^{0}_{n}(H)$.

As explained in Section 2.1, the proof of such theorems is closely related to
the existence of a uniformly $\Sigma^{0}_{n}$-preserving forcing question,
that is, a forcing question for $\Sigma^{0}_{n}(G)$ formulas which is
$\Sigma^{0}_{n}$ uniformly in its parameters.

Unfortunately, by Lemma 4.8, forcing a $\Sigma^{0}_{n}(G)$ formula is
$\Pi^{0}_{1}(\mathcal{M}_{n})$, which is not the desired definitional
complexity. We are going to use the same trick as Monin and Patey [15] and
define a twisted notion of forcing “on the top”, that is, leaving the lower
levels unchanged, we are going to replace the Scott set $\mathcal{M}_{n}$ by
another Scott set $\mathcal{N}_{n}$ with more suited properties, and define a
different forcing question on the top level.

Intuitively, the bad complexity of the forcing question comes from the fact
that, since there is no effectiveness restriction on the reservoir $X$, the
only way to decide properties is to check whether the class of sets satisfying
this property is large. Largeness of a $\Sigma^{0}_{n}$ property is
$\Pi^{0}_{n+1}$. Therefore, at the top level, the forcing question will have
to directly involve the reservoir. The counterpart is that the forcing
conditions will need to impose effectiveness restrictions on the reservoirs,
which will raise a few technical difficulties.

###  6.1 Top Scott set

Suppose $B$ is a non-$\Sigma^{0}_{n+1}$ set. The forcing question on the top
for $\Sigma^{0}_{n+1}$ formulas will be $\Sigma^{0}_{1}(\mathcal{M}_{n})$, so
for Proposition 2.3 about diagonalization to work, one needs $B$ not to be
$\Sigma^{0}_{1}(\mathcal{M}_{n})$. We will therefore replace the Scott set
$\mathcal{M}_{n}$ with another Scott set $\mathcal{N}_{n}$ coded by a set
$N_{n}$ with the following two properties:

  * •

$\emptyset^{(n)}$ is coded by an element of $\mathcal{N}_{n}$ ;

  * •

$B$ is not $\Sigma^{0}_{1}(\mathcal{N}_{n})$

The second fact replaces the previous assumption that $N_{n}^{\prime}$ is
computable in $\emptyset^{(n+1)}$. The existence of such a Scott set follows
from the following proposition by Wang [19, Theorem 3.6]:

######  Proposition 6.1 (Wang [19]).

Let $Z,B$ such that $B$ is not $\Sigma^{0}_{1}(Z)$. For every $Z$-computable
tree $T\subseteq 2^{<\mathbb{N}}$, there exists an infinite path $P\in[T]$
such that $B$ is not $\Sigma^{0}_{1}(Z\oplus P)$.

However, the two properties above are not sufficient to define
$\mathcal{N}_{n}$. Indeed, there are still no effectiveness restrictions on
the initial tournament $T$, and in particular, $T$ cannot be assumed to be in
$\mathcal{N}_{n}$, but in the proof of Lemma 4.12, one needs to split the
reservoir $X$ based on a $Z\oplus T$-computable finite partition, for some
$Z\in\mathcal{N}_{n}$. The resulting reservoir must still belong to
$\mathcal{N}_{n}$ and to the partition regular class $\mathcal{P}$. The Scott
set $\mathcal{N}_{n}$ must therefore enjoy the following property:

  * •

For every $X\in\mathcal{N}_{n}\cap\mathcal{P}$, every $Z\in\mathcal{N}_{n}$
and every $T\oplus Z$-computable set $A$, there exists an infinite set
$Y\subseteq X\cap A$ or $Y\subseteq X\cap\overline{A}$ such that
$Y\in\mathcal{N}_{n}\cap\mathcal{P}$.

For this, we will prove the following proposition, which is an adaptation of
an alternative proof by Hirschfeldt [5, Lemma 6.63] of a theorem by Dzhafarov
and Jockusch [4]. The statement of the proposition can be found in Monin and
Patey [16, Theorem 5.1] and [15, Theorem 4.11], but without the assumption
that $H\in\mathcal{U}^{Z}_{C}$. We therefore give a direct proof of it for the
sake of simplicity.

######  Proposition 6.2.

Let $Z,B$ such that $B$ is not $\Sigma^{0}_{1}(Z)$. Let $\mathcal{U}^{Z}_{C}$
be a partition regular class. For every set $A$, there exists an infinite
subset $H\subseteq A$ or $H\subseteq\overline{A}$ such that $B$ is not
$\Sigma^{0}_{1}(Z\oplus H)$ and $H\in\mathcal{U}^{Z}_{C}$.

Fix $Z,B,\mathcal{U}^{Z}_{C}$ and $A$. Say $A_{0}=A$ and $A_{1}=\overline{A}$.
We are going to build two sets $G_{0},G_{1}$ by a variant of Mathias forcing
whose conditions are tuples of the form $(\sigma_{0},\sigma_{1},X)$, where

  * •

$(\sigma_{i},X)$ is a Mathias condition with $\sigma_{i}\subseteq A_{i}$

  * •

$X\in\mathcal{U}^{Z}_{C}$ and $B$ is not $\Sigma^{0}_{1}(X\oplus Z)$

Consider the following two kind of requirements, for every $e\in\omega$ and
$k\in C$:

$\mathcal{R}^{G}_{e}\mbox{: }W_{e}^{G\oplus Z}\neq B\hskip
20.0pt\mathcal{S}^{G}_{k}\mbox{: }G\in\mathcal{U}^{Z}_{k}$

We are going to construct $G_{0},G_{1}$ such that they satisfy the following
requirements for every $e_{0},e_{1}\in\omega$ and $k_{0},k_{1}\in C$:

$\mathcal{R}^{G_{0}}_{e_{0}}\vee\mathcal{R}^{G_{1}}_{e_{1}}\mbox{ ;
}\mathcal{S}^{G_{0}}_{k_{0}}\vee\mathcal{S}^{G_{1}}_{k_{1}}\mbox{ ;
}\mathcal{R}^{G_{0}}_{e_{0}}\vee\mathcal{S}^{G_{1}}_{k_{1}}\mbox{ ;
}\mathcal{S}^{G_{0}}_{k_{0}}\vee\mathcal{R}^{G_{1}}_{e_{1}}$

By a pairing argument, then there is some $i<2$ such that
$G_{i}\in\mathcal{U}^{Z}_{C}$ and $B$ is not $\Sigma^{0}_{1}(G_{i}\oplus Z)$.
We will need the following three lemmas. The fourth case follows by symmetry.

######  Lemma 6.3.

Let $c$ be a condition and $e_{0},e_{1}\in\omega$. There is an extension
forcing $\mathcal{R}^{G_{0}}_{e_{0}}\vee\mathcal{R}^{G_{1}}_{e_{1}}$.

###### Proof.

Say $c=(\sigma_{0},\sigma_{1},X)$. Let $W$ be the $\Sigma^{0}_{1}(X\oplus Z)$
set of all $x\in\omega$ such that for every 2-partition $R_{0}\sqcup R_{1}=X$,
there is some $i<2$ and some $\rho\subseteq R_{i}$ such that $x\in
W_{e_{i}}^{(\sigma_{i}\cup\rho)\oplus Z}$. Since $W$ is
$\Sigma^{0}_{1}(X\oplus Z)$ while $B$ is not, there is some $x\in W\Delta
B=(W\setminus B)\cup(B\setminus W)$.

  * •

If $x\in W\setminus B$, then, letting $R_{i}=X\cap A_{i}$, there is some $i<2$
and some $\rho\subseteq X\cap A_{i}$ such that $x\in
W_{e_{i}}^{(\sigma_{i}\cup\rho)\oplus Z}$. The condition
$(\sigma_{i}\cup\rho,\sigma_{1-i},X\setminus\\{0,\dots,\max\rho\\})$ is an
extension of $c$ forcing $\mathcal{R}^{G_{i}}_{e_{i}}$.

  * •

If $x\in B\setminus W$, then, let $\mathcal{C}$ be the $\Pi^{0}_{1}(X\oplus
Z)$ class of all $R_{0}\oplus R_{1}$ such that $R_{0}\sqcup R_{1}=X$, for
every $i<2$ and every $\rho\subseteq R_{i}$, $x\not\in
W_{e_{i}}^{(\sigma_{i}\cup\rho)\oplus Z}$. The class $\mathcal{C}$ is non-
empty, so by Proposition 6.1, there is some $R_{0}\oplus R_{1}\in\mathcal{C}$
such that $B$ is not $\Sigma^{0}_{1}(R_{0}\oplus R_{1}\oplus X\oplus Z)$. By
partition regularity of $\mathcal{U}^{Z}_{C}$, there is some $i<2$ such that
$R_{i}\in\mathcal{U}^{Z}_{C}$. The condition $(\sigma_{0},\sigma_{1},R_{i})$
is an extension of $c$ forcing $\mathcal{R}^{G_{i}}_{e_{i}}$.

∎

######  Lemma 6.4.

Let $c$ be a condition and $k_{0},k_{1}\in C$. There is an extension forcing
$\mathcal{S}^{G_{0}}_{k_{0}}\vee\mathcal{S}^{G_{1}}_{k_{1}}$.

###### Proof.

Say $c=(\sigma_{0},\sigma_{1},X)$. Since $\mathcal{U}^{Z}_{C}$ is partition
regular and $X\in\mathcal{U}^{Z}_{C}$, there is some $i<2$ such that $X\cap
A_{i}\in\mathcal{U}^{Z}_{C}$. In particular, $X\cap
A_{i}\in\mathcal{U}^{Z}_{k_{i}}$. Let $\rho\subseteq X\cap A_{i}$ be such that
$\rho\in\mathcal{U}^{Z}_{k_{i}}$. Then the condition
$(\sigma_{i}\cup\rho,\sigma_{1-i},X\setminus\\{0,\dots,\max\rho\\})$ is an
extension of $c$ forcing $\mathcal{S}^{G_{i}}_{k_{i}}$. ∎

######  Lemma 6.5.

Let $c$ be a condition, $e_{0}\in\omega$ and $k_{1}\in C$. There is an
extension forcing
$\mathcal{R}^{G_{0}}_{e_{0}}\vee\mathcal{S}^{G_{1}}_{k_{1}}$.

###### Proof.

Say $c=(\sigma_{0},\sigma_{1},X)$. Let $W$ be the $\Sigma^{0}_{1}(X\oplus Z)$
set of all $x\in\omega$ such that for every 2-partition $R_{0}\sqcup R_{1}=X$,
either there is some $\rho\subseteq R_{0}$ such that $x\in
W_{e_{0}}^{(\sigma_{0}\cup\rho)\oplus Z}$, or there is some $\rho\subseteq
R_{1}$ such that $\rho\in\mathcal{U}^{Z}_{k_{1}}$. Since $W$ is
$\Sigma^{0}_{1}(X\oplus Z)$ while $B$ is not, there is some $x\in W\Delta
B=(W\setminus B)\cup(B\setminus W)$.

  * •

If $x\in W\setminus B$, then, letting $R_{i}=X\cap A_{i}$, either there is
some $\rho\subseteq X\cap A_{0}$ such that $x\in
W_{e_{0}}^{(\sigma_{0}\cup\rho)\oplus Z}$, or some $\rho\subseteq X\cap A_{1}$
such that $\rho\in\mathcal{U}^{Z}_{k_{1}}$. The condition
$(\sigma_{i}\cup\rho,\sigma_{1-i},X\setminus\\{0,\dots,\max\rho\\})$ is an
extension of $c$ forcing $\mathcal{R}^{G_{0}}_{e_{0}}$ in the first case, and
$\mathcal{S}^{G_{1}}_{k_{1}}$ in the second case.

  * •

If $x\in B\setminus W$, then, let $\mathcal{C}$ be the $\Pi^{0}_{1}(X\oplus
Z)$ class of all $R_{0}\oplus R_{1}$ such that for every $\rho\subseteq
R_{0}$, $x\not\in W_{e_{0}}^{(\sigma_{i}\cup\rho)\oplus Z}$, and
$R_{1}\not\in\mathcal{U}^{Z}_{k_{1}}$. The class $\mathcal{C}$ is non-empty,
so by Proposition 6.1, there is some $R_{0}\oplus R_{1}\in\mathcal{C}$ such
that $B$ is not $\Sigma^{0}_{1}(R_{0}\oplus R_{1}\oplus X\oplus Z)$. By
partition regularity of $\mathcal{U}^{Z}_{C}$, there is some $i<2$ such that
$R_{i}\in\mathcal{U}^{Z}_{C}$, and by choice of $\mathcal{C}$, $i=0$. The
condition $(\sigma_{0},\sigma_{1},R_{0})$ is an extension of $c$ forcing
$\mathcal{R}^{G_{0}}_{e_{0}}$.

∎

We are now ready to prove Proposition 6.2.

###### Proof of Proposition 6.2.

Fix $Z,B,\mathcal{U}^{Z}_{C}$ and $A$. Say $A_{0}=A$ and $A_{1}=\overline{A}$.
Let $\mathcal{F}$ be a sufficiently generic filter for this notion of forcing.
For every $i<2$, let
$G_{i}=\bigcup_{(\sigma_{0},\sigma_{1},X)\in\mathcal{F}}\sigma_{i}$. By
definition of a condition, $G_{0}\subseteq A$ and
$G_{1}\subseteq\overline{A}$. By Lemma 6.3, Lemma 6.4, Lemma 6.5 and its
symmetric version, there is some $i<2$ such that $G_{i}\in\mathcal{U}^{Z}_{C}$
and $B$ is not $\Sigma^{0}_{1}(G_{i}\oplus Z)$. In particular, assuming
$\mathcal{U}^{Z}_{C}$ contains only infinite sets, $G_{i}$ is infinite. This
completes the proof of Proposition 6.2. ∎

Thanks to Proposition 6.1 and Proposition 6.2, one can prove the existence of
a Scott set $\mathcal{N}_{n}$ satisfying the properties mentioned above:

######  Proposition 6.6.

Fix $n>0$. Let $B$ be a non-$\Sigma^{0}_{n+1}$ set and $T$ be a tournament.
There exists a Scott set $\mathcal{N}_{n}$ such that

  * •

$\emptyset^{(n)}\in\mathcal{N}_{n}$ ; $B$ is not
$\Sigma^{0}_{1}(\mathcal{N}_{n})$ ;

  * •

for every
$X\in\mathcal{N}_{n}\cap\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$,
every $Z\in\mathcal{N}_{n}$ and every $T\oplus Z$-computable set $A$, there
exists an infinite set $Y\subseteq X\cap A$ or $Y\subseteq X\cap\overline{A}$
such that
$Y\in\mathcal{N}_{n}\cap\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$.

###### Proof.

By Proposition 6.1 and Proposition 6.2, there exists an infinite sequence
$Z_{0},Z_{1},\dots$ such that $Z_{0}=\emptyset^{(n)}$, and for every
$s\in\omega$:

  * (1)

For every $Z_{0}\oplus\dots\oplus Z_{s}$-computable infinite binary tree $T$,
there is some $t$ such that $Z_{t}\in[T]$ ;

  * (2)

For every $Z_{0}\oplus\dots\oplus Z_{s}$-computable infinite set
$X\in\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$ and every
$T\oplus Z_{0}\oplus\dots\oplus Z_{s}$-computable set $A$, there exists some
$t$ such that $Z_{t}\subseteq X\cap A$ or $Z_{t}\subseteq X\cap\overline{A}$
and
$Z_{t}\in\mathcal{N}_{n}\cap\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$.

  * (3)

$B$ is not $\Sigma^{0}_{1}(Z_{0}\oplus\dots\oplus Z_{s})$

Let $\mathcal{N}_{n}=\\{X:(\exists s)X\leq_{T}Z_{0}\oplus\dots\oplus
Z_{s}\\}$. By construction, $\mathcal{N}_{n}$ is a Turing ideal containing
$\emptyset^{(n)}$. Moreover, by (1), $\mathcal{N}_{n}\models\mathsf{WKL}$, by
(2), $\mathcal{N}_{n}$ satisfies the second item of the lemma, and by (3), $B$
is not $\Sigma^{0}_{1}(\mathcal{N}_{n})$. ∎

As explained in Section 3.2, given a Scott set $\mathcal{M}$ coded by a set
$M$, one can compute the index set $C$ of an $\mathcal{M}$-cohesive class
$\mathcal{U}^{\mathcal{M}}_{C}$ in any PA degree over $M^{\prime}$ (see Monin
and Patey [15, Lemma 2.17] for a full proof). Since
$M_{n-1}^{\prime}\leq_{T}\emptyset^{(n)}$ and
$\emptyset^{(n)}\in\mathcal{N}_{n}$ which is a Scott set, then one can find
the index set $C_{n-1}$ of an $\mathcal{M}_{n-1}$-cohesive large class
$\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$ in $\mathcal{N}_{n}$.

###  6.2 Top forcing conditions

The notion of forcing for layerwise cone avoidance resembles the previous
notion of forcing, with a few distinctive features.

  * •

First, since one needs to control only $\Sigma^{0}_{n+1}(G)$ properties, the
partition generic class $\mathcal{P}$ will only need to be included in a
minimal class of a finite level of the hierarchy of Scott sets. We will
actually choose
$\mathcal{P}=\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$.

  * •

Second, since the forcing question on the top will depend on the reservoir
$X$, one must require that $X\in\mathcal{N}_{n}$, in order to obtain a
$\Sigma^{0}_{1}(\mathcal{N}_{n})$ forcing question. Since $B$ is not
$\Sigma^{0}_{1}(\mathcal{N}_{n})$, the diagonalization lemma will hold.

  * •

Last, as explained above, since the proof of Lemma 4.12 splits the reservoir
based on 2-partitions computable in the tournaments, one must require that
$\mathcal{N}_{n}$ is closed under this operation. By construction of
$\mathcal{N}_{n}$, the closure is ensured for the original tournament $T$.
However, in the proof of Lemma 4.12, new tournaments will be added to the
condition. Thankfully, all the new tournaments can be chosen as members of
$\Pi^{0}_{1}(\mathcal{N}_{n})$ classes, and since $\mathcal{N}_{n}$ is a Scott
set, one can require that $\vec{R}\in\mathcal{N}_{n}$. The new notion of
condition will therefore distinguish between the original tournament $T$ which
can be of arbitrary strength, and the new tournaments $\vec{R}$ added along
the construction of a generic filter, and which will belong to
$\mathcal{N}_{n}$.

######  Definition 6.7.

Fix a tournament $T$. Let $n>0$. Let $\mathbb{P}_{n}$ denote the set of all
3-tuples $(\vec{R},\sigma,X)$ such that

  1. 1.

$\vec{R}$ is a finite sequence of tournaments,

  2. 2.

$X\cap\\{0,\dots,|\sigma|\\}=\emptyset$,

  3. 3.

$X\in\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$,

  4. 4.

$\vec{R},X\in\mathcal{N}_{n}$,

  5. 5.

for all $y\in X$, $\sigma\cup\\{y\\}$ is $\vec{R}$-transitive and
$T$-transitive,

  6. 6.

$X$ is included in a minimal $\vec{R}$-interval and $T$-interval of $\sigma$.

In other words, $\mathbb{P}_{n}$ is the set of all
$\mathbb{P}_{\mathcal{P}}$-conditions $((T,\vec{R}),\sigma,X)$ for
$\mathcal{P}=\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$ such
that $\vec{R},X\in\mathcal{N}_{n}$.

######  Remark 6.8.

As an element of $\mathbb{P}_{\mathcal{P}}$, a $\mathbb{P}_{n}$ condition
inherits the definitions of the forcing relation and the forcing question. The
Scott set $\mathcal{N}_{n}$ has been designed so that the proof of Lemma 4.12
still holds while ensuring that $\vec{R}$ and $X$ belong to $\mathcal{N}_{n}$.

###  6.3 Top forcing question

We now define a forcing question which is very similar to Definition 2.8.

######  Definition 6.9.

Fix $n>0$. Let $c=(\vec{R},\sigma,X)\in\mathbb{P}_{n}$ and let $(\exists
x)\psi_{e}(G,x)$ be a $\Sigma^{0}_{n+1}$ formula. Say $m:=|\vec{R}|+1$. Define
the relation $c\operatorname{{?}{\vdash}}(\exists x)\psi_{e}(G,x)$ to hold if
for every $m$-tuple of 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{X}$ and
every $\vec{S}\in\mathcal{C}_{m}(\sigma,X)$, there is an $\vec{h}$-homogeneous
and $\vec{S}$-transitive $\tau\subseteq X$ and some $x\in\omega$ such that
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{m}\neg\psi_{e}(G,x)$.

######  Lemma 6.10.

Fix $n>0$. Let $c=(\vec{R},\sigma,X)\in\mathbb{P}_{n}$ and let $(\exists
x)\psi_{e}(G,x)$ be a $\Sigma^{0}_{n+1}$ formula. The sentence
$(c\operatorname{{?}{\vdash}}(\exists x)\psi_{e}(G,x))$ is
$\Sigma^{0}_{1}(\mathcal{N}_{n})$.

###### Proof.

Let $m:=|\vec{R}|+1$. By a compactness argument,
$(c\operatorname{{?}{\vdash}}(\exists x)\psi_{e}(G,x))$ holds if there exists
$t\in\omega$ such that for every $m$-tuple of 2-colorings
$\vec{h}=h_{0},\dots,h_{m-1}\in 2^{t}$ and every every $m$-tuple of
tournaments $\vec{S}$ over $\\{0,\dots,t\\}$ such that
$\vec{S}\in\mathcal{C}_{m}(\sigma,X\cap\\{0,\dots,t\\})$, there is an
$\vec{h}$-homogeneous and $\vec{S}$-transitive $\tau\subseteq
X\cap\\{0,\dots,t\\}$ and some $x\in\omega$ such that
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{m}\neg\psi_{e}(G,x)$. The formula
$\neg\psi_{e}(G,x)$ is $\Sigma^{0}_{n}$, so by Lemma 4.8, the formula
$(\sigma\cup\tau\operatorname{{?}{\vdash}}_{m}\neg\psi_{e}(G,x))$ is
$\Pi^{0}_{1}(C_{n-1}\oplus\emptyset^{(n)})$ uniformly in its parameters, hence
$(\sigma\cup\tau\operatorname{{?}{\nvdash}}_{m}\neg\psi_{e}(G,x))$ is
$\Sigma^{0}_{1}(\mathcal{M}_{n})$. This yields the expected result since
$\mathcal{M}_{n}\subseteq\mathcal{N}_{n}$.

∎

The following lemma states that the forcing question on the top meets its
specifications, that is, based on its answer, there is an extension forcing
the property or its complement.

######  Lemma 6.11.

Let $n\in\omega$ and $c:=(\vec{R},\sigma,X)\in\mathbb{P}_{n}$. Consider
$(\exists x)\psi_{e}(G,x)$ a $\Sigma_{n+1}^{0}$ formula.

  * •

If $c\operatorname{{?}{\vdash}}(\exists x)\psi_{e}(G,x)$ then $\exists d\leq
c$ such that $d\Vdash(\exists x)\psi_{e}(G,x)$.

  * •

If $c\operatorname{{?}{\nvdash}}(\exists x)\psi_{e}(G,x)$ then $\exists d\leq
c$ such that $d\Vdash(\forall x)\neg\psi_{e}(G,x)$.

###### Proof.

Let $m=|\vec{R}|+1$. For simplicity of notation, let $R_{m-1}=T$.

First, suppose $c\operatorname{{?}{\vdash}}(\exists x)\psi_{e}(G,x)$. Then, in
particular, for every $m$-tuple of 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in
2^{X}$, there exists an $\vec{h}$-homogeneous, $\vec{R}$-transitive and
$T$-transitive $\tau\subseteq X$ and some $x\in\omega$ such that
$\sigma\cup\tau\operatorname{{?}{\nvdash}}\neg\psi_{e}(G,x)$. By a compactness
argument, there exists $t\in\omega$ such that we can restrict the considered
set of $m$-tuples of $2$-colorings of $X$ to 2-colorings of $\\{0,\dots,t\\}$.
We again build the same $m$-tuple of 2-colorings as follows: for every $i<m$,
$a\leq t$, and $y\in X$, $y>t$, let $g_{i,a}(y):=1$ if $R_{i}(a,y)$ holds, and
0 otherwise. Note that $\vec{g}$ is $T\oplus\vec{R}\oplus X$-computable, hence
$T\oplus Z$-computable for some $Z\in\mathcal{N}_{n}$ (since $R_{m-1}=T$).

By choice of $\mathcal{N}_{n}$, with
$\mathcal{P}=\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$, by
Proposition 6.6, there exists $H\subseteq X$ a $\vec{g}$-homogeneous set in
$\mathcal{N}_{n}\cap\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$.

For every $i<m$ and $a\leq t$, let $h_{i}(a)=1$ if $\\{a\\}\to_{R_{i}}H$, and
$0$ otherwise. Now, there exists a finite $\tau\subseteq X\cap\\{0,\dots,t\\}$
which is $\vec{R}$-transitive, $T$-transitive and $\vec{h}$-homogeneous and
some $x\in\omega$ such that
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{m}\neg\psi_{e}(G,x)$. Moreover, by
Lemma 4.6, $(\vec{R},T)\in\mathcal{C}_{m}(\sigma\cup\tau,H)$. This makes
$d:=(\vec{R},\sigma\cup\tau,H)$ a valid $\mathbb{P}_{n}$ condition under $c$
such that $d\operatorname{{?}{\nvdash}}_{m}\neg\psi_{e}(G,x)$, hence, by Lemma
4.12, there exists $p\leq d\leq c$ such that $p\Vdash\psi_{e}(G,x)$.

Now, suppose $c\operatorname{{?}{\nvdash}}(\exists x)\psi_{e}(G,x)$. Then,
there exists an $m$-tuple of 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in
2^{X}$ and an $m$-tuple of tournaments $\vec{S}\in\mathcal{C}_{m}(\sigma,X)$
such that for every $\vec{h}$-homogeneous and $\vec{S}$-transitive finite
chain $\sigma\subseteq X$ and every $x\in\omega$,
$\sigma\cup\tau\operatorname{{?}{\vdash}}_{m}\neg\psi_{e}(G,x)$. Let
$\mathcal{L}$ be the class of such $m$-tuples of 2 colorings $\vec{h}$ and
$m$-tuples of $\vec{S}\in\mathcal{C}_{m}(\sigma,X)$. By Lemma 4.5,
$\mathcal{C}_{m}(\sigma,X)$ is $\Pi^{0}_{1}(X)$. Since $X\in\mathcal{N}_{n}$,
the class $\mathcal{L}$ is $\Pi_{1}^{0}(\mathcal{N}_{n})$, hence, since
$\mathcal{N}_{n}\models\mathsf{WKL}$, there exists
$(\vec{h},\vec{S})\in\mathcal{N}_{n}\cap\mathcal{L}$. By partition regularity
of $\mathcal{P}=\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$,
there is a $\vec{h}\oplus X$-computable $\vec{h}$-homogeneous set $Y\subseteq
X$ in $\mathcal{P}$. The 3-tuple $d:=(\vec{R}\vec{S},\sigma,Y)$ is a valid
$\mathsf{EM}$-condition such that $d\Vdash(\forall x)\neg\psi_{e}(G,x)$.

∎

The following diagonalization lemma is a specialization of Proposition 2.3 to
this notion of forcing.

######  Lemma 6.12.

Fix $n>0$. Let $\mathcal{F}$ be a sufficiently generic
$\mathbb{P}_{n}$-filter. Then, for every $\Sigma_{n+1}^{0}$ formula
$\varphi(G,x)$, there exists $d\in\mathcal{F}$ such that

$(\exists x\notin B)(d\Vdash\varphi(G,x))\ \lor\ (\exists x\in
B)(d\Vdash\neg\varphi(G,x)).$

###### Proof.

Fix some $c=(\vec{R},\sigma,X)\in\mathcal{F}$, and let $\varphi(G,x)$ be a
$\Sigma^{0}_{n+1}$ formula. Let
$W=\\{x:c\operatorname{{?}{\vdash}}(\varphi(G,x)\\}$. By Lemma 6.10, the set
$W$ is $\Sigma^{0}_{1}(\mathcal{N}_{n})$. By construction of $\mathcal{N}_{n}$
in Proposition 6.6, $B$ is not $\Sigma_{1}^{0}(\mathcal{N}_{n})$, hence,
$W\neq B$. Let $x\in W\Delta B=(W\setminus B)\cup(B\setminus W)$. One of the
two cases holds:

  * •

$x\in W\setminus B$, then, by Lemma 6.11, there exists a condition $d\leq c$
such that $d\Vdash\varphi(G,x)$.

  * •

$x\in B\setminus W$, then, by Lemma 6.11, there exists a condition $d\leq c$
such that $d\Vdash\neg\varphi(G,x)$.

In both cases, by genericity of $\mathcal{F}$, there is such a $d$ in
$\mathcal{F}$. ∎

We are now ready to prove 1.4.

###### Proof of 1.4.

The case $n=0$ is proven independently by the first author and Wang
(unpublished) and is a consequence of Section 2.2. Fix $n>0$, and fix a
non-$\Sigma_{n+1}^{0}$ set $B$, a tournament $T$, and let $\mathcal{F}$ be a
sufficiently generic $\mathbb{P}_{n}$-filter containing the condition
$(\emptyset,\emptyset,\omega)$ (recall that $T$ is a parameter of the notion
of forcing). By Lemma 4.14, $\mathcal{F}$ is $(n-1)$-generic. By Lemma 4.3,
$G_{\mathcal{F}}$ is $T$-transitive, and by Lemma 4.17, $G_{\mathcal{F}}$ is
infinite.

We claim that $B$ is not $\Sigma^{0}_{n+1}(G_{\mathcal{F}})$: fix a
$\Sigma^{0}_{n+1}$ formula $\varphi(G,x)$. By Lemma 6.12, there exists some
$c\in\mathcal{F}$ such that

$(\exists x\notin B)(c\Vdash\varphi(G,x))\ \lor\ (\exists x\in
B)(c\Vdash\neg\varphi(G,x)).$

By Lemma 4.16, since $\mathcal{F}$ is $(n-1)$-generic, $(\exists x\notin
B)\varphi(G_{\mathcal{F}},x)\lor(\exists x\in
B)\neg\varphi(G_{\mathcal{F}},x)$, hence $B$ is not
$\Sigma^{0}_{n}(G_{\mathcal{F}})$. ∎

##  7 Effective constructions and lowness

This last section of our article is devoted to the proof of the third main
theorem:

######  Main Theorem 1.5.

Fix $n\geq 1$. Every $\Delta^{0}_{n}$ tournament $T$ has an infinite
transitive subtournament of lown+1 degree.

First of all, notice that this bound is tight, in that there exists a
computable tournament with no infinite $\Sigma^{0}_{2}$ transitive
subtournament (see Patey [18]). By relativizing the argument, for every $n\geq
1$, there is a $\Delta^{0}_{n}$ tournament with no infinite $\Sigma^{0}_{n+1}$
transitive subtournament, hence no infinite lown transitive subtournament. We
will actually prove the following stronger theorem:

######  Theorem 7.1.

Fix $n\geq 1$. For every set $P$ of PA degree over $\emptyset^{(n)}$, every
$\Delta^{0}_{n}$ tournament $T$ has an infinite transitive subtournament $H$
such that $H^{(n)}\leq_{T}P$.

1.5 follows from Theorem 7.1 using the low basis theorem:

###### Proof of 1.5.

Fix $n\geq 1$ and a $\Delta^{0}_{n}$ tournament $T$. By the low basis theorem
relative to $\emptyset^{(n)}$ (see Jockusch and Soare [10]), there is a set
$P$ of PA degree over $\emptyset^{(n)}$ such that
$P^{\prime}\leq_{T}\emptyset^{(n+1)}$. By Theorem 7.1, there is an infinite
$T$-transitive subtournament $H$ such that $H^{(n)}\leq_{T}P$. In particular,
$H^{(n+1)}\leq_{T}P^{\prime}\leq_{T}\emptyset^{(n+1)}$, hence $H$ is of lown+1
degree. ∎

The rest of this section is therefore devoted to the proof of Theorem 7.1. The
goal will be to construct, given a $\Delta^{0}_{n}$ tournament $T$ and a set
$P$ of PA degree over $\emptyset^{(n)}$, an infinite decreasing sequence of
conditions $c_{0}=(T,\emptyset,\omega)\geq c_{1}\geq\dots$ such that the
induced filter $\mathcal{F}=\\{d:(\exists n)c_{n}\leq d\\}$ is $n$-generic.
Then, the set $G_{\mathcal{F}}$ be will be an infinite $T$-transitive
subtournament such that $G_{\mathcal{F}}^{(n)}\leq_{T}P$.

We will work with a notion of forcing $\mathbb{Q}_{n}$ which is very similar
to $\mathbb{P}_{n}$, with the same distinction between the forcing question of
the top and the ones at the lower levels. The main difference between
$\mathbb{Q}_{n}$ and $\mathbb{P}_{n}$ comes from two facts:

  * •

The tournament $T$ is $\Delta^{0}_{n}$, hence belongs to $\mathcal{M}_{n}$.
There is therefore no need to distinguish the original tournament $T$ from the
sequence of tournaments $\vec{R}$ obtained with the question of forcing.

  * •

The resulting filter will be $n$-generic, but there will be no diagonalization
against a fixed non-$\Sigma^{0}_{n+1}$ set $B$. We therefore does not require
that a set $B$ is not $\Sigma^{0}_{1}(\mathcal{M}_{n})$.

Because of these differences, there is no need to use a different Scott set at
the level $n$. We will therefore keep $\mathcal{M}_{n}$ instead of replacing
it with $\mathcal{N}_{n}$. Note that any PA degree over $\emptyset^{(n)}$ can
compute a sequence of sets $M_{0},M_{1},\dots,M_{n}$ satisfying the properties
of Proposition 3.15, except that the last set $M_{n}$ is not required to
satisfy the last item, but simply to be $P$-computable.

######  Definition 7.2.

Let $n>0$. Let $\mathbb{Q}_{n}$ denote the set of all
$\mathbb{P}_{\mathcal{P}}$-conditions $(\vec{R},\sigma,X)$ for
$\mathcal{P}=\langle\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}\rangle$ such
that $\vec{R},X\in\mathcal{M}_{n}$.

In order to analyze the computational power needed to construct an $n$-generic
decreasing sequence of conditions, one must fix a coding of the conditions
into finite objects. Since $\mathcal{M}_{n}=\\{Z_{e}:e\in\mathbb{N}\\}$ is
countably coded by the set $M_{n}=\bigoplus_{e\in\omega}Z_{e}$, every element
$X\in\mathcal{M}_{n}$ can be represented by an integer $e$ such that
$X=Z_{e}$. We call such an $e$ an _$M_{n}$ -index_ of $X$. Note that any set
$X\in\mathcal{M}_{n}$ can be represented by infinitely many $M_{n}$-indices.

######  Definition 7.3.

Let $c:=(\vec{R},\sigma,X)$. A _$\mathbb{Q}_{n}$ -index_ of $c$ is a 3-tuple
$\langle e_{R},\sigma,e_{X}\rangle$ such that $Z_{e_{X}}=X$, i.e. $e_{X}$ is
an $M_{n}$-index of $X$, and such that
$\Phi_{e_{R}}^{\emptyset^{(n)}}(i,a,b)=R_{i}(a,b)$.

In what follows, fix some $n\geq 1$ and a set $P$ of PA degree over
$\emptyset^{(n)}$ computing $M_{n}$.

######  Lemma 7.4.

The statement “$X\in\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$” is
$\Pi^{0}_{1}(C_{n-1}\oplus(X\oplus M_{n-1})^{\prime})$ uniformly in $X$. In
particular, if $X\in\mathcal{M}_{n-1}$, then it is $\Pi^{0}_{1}(C_{n-1}\oplus
M_{n-1}^{\prime})$ uniformly in an $M_{n}$-index of $X$.

###### Proof.

The sentence “$X\in\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}$” is equivalent
to the formula $(\forall(e,i)\in C_{n-1})(X\in\mathcal{U}_{e}^{Z_{i}})$, where
$M_{n-1}=\bigoplus_{i\in\omega}Z_{i}$. In other words, the sentence
“$X\in\mathcal{U}_{C_{n-1}}^{\mathcal{M}_{n-1}}$” is equivalent to

$\forall e\forall i,\ (e,i)\not\in C_{n-1}\vee(\exists\rho\subseteq X)\rho\in
W^{Z_{i}}_{e}$

The left-hand side of the disjunction is $\Delta^{0}_{0}(C_{n-1})$, and the
right-hand side is $\Sigma^{0}_{1}(X\oplus M_{n-1})$, hence
$\Delta^{0}_{0}((X\oplus M_{n-1})^{\prime})$. The whole sentence is therefore
$\Pi_{1}^{0}(C_{n-1}\oplus(X\oplus M_{n-1})^{\prime})$ uniformly in $X$. ∎

Fix a set $Z$ and a sequence of pairs of $\Pi^{0}_{1}(Z)$ formulas
$(\varphi_{s},\psi_{s})_{s\in\mathbb{N}}$ such that for every $s$, at least
one of $\varphi_{s}$ and $\psi_{s}$ is true. It is well-known that any set $P$
of PA degree relative to $Z$ computes a set $H$ such that for every $s$, if
$s\in H$ then $\varphi_{s}$ is true, and if $s\not\in H$ then $\psi_{s}$ is
true. Combining this fact with Lemma 7.4, we obtain the following lemma:

######  Lemma 7.5.

Let $X\in\mathcal{M}_{n}\cap\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$ and
$f:X\to 2$ be a 2-coloring in $\mathcal{M}_{n}$. Then there is some
$f$-homogeneous set $Y\subseteq X$ such that
$Y\in\mathcal{M}_{n}\cap\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$. Moreover,
an $M_{n}$-index of $Y$ can be $P$-uniformly from $M_{n}$-indices of $X$ and
and $f$.

###### Proof.

Let $\mathcal{P}_{X}$ be the class of all $H$ such that for every $i$, if
$i\in H$ then $X\cap Z_{i}\in\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$, and
if $i\not\in H$, then $X\setminus
Z_{i}\in\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$. By partition regularity of
$\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$ and since
$X\in\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$, then $\mathcal{P}_{X}$ is
non-empty. Moreover, by Lemma 7.4, the class $\mathcal{P}_{X}$ is
$\Pi^{0}_{1}(C_{n-1}\oplus M_{n-1}^{\prime})$ uniformly in an $M_{n}$-index of
$X$, hence is $\Pi^{0}_{1}(\mathcal{M}_{n})$. Thus, given an $M_{n}$-index of
$X$, one can find an $M_{n}$-index of a tree $T_{X}$ such that
$[T_{X}]=\mathcal{P}_{X}$, and of a member $H\in[T_{X}]$, and given an
$M_{n}$-index $i_{f}$ of $f$, one can $H$-decide whether $X\cap f^{-1}(0)$ or
$X\cap f^{-1}(1)$ belongs to $\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$ and
thus compute an $M_{n}$-index of the corresponding set.

Note that almost all the operations are manipulations of codes, hence do not
use the oracle $P$. The only place it is used is when deciding whether $X\cap
f^{-1}(0)$ or $X\cap f^{-1}(1)$ belongs to
$\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$. Indeed, it requires to “evaluate”
the $M_{n}$-index of $H$ into its actual set, thanks to the oracle $M_{n}$
which is $P$-computable. ∎

The following two lemmas analyze the uniformity of the forcing questions at
the lower levels and at the top level.

######  Lemma 7.6.

In Lemma 4.12, a $\mathbb{Q}_{n}$-index of an extension $d$ can be found
$P$-uniformly from a $\mathbb{Q}_{n}$-index of $c$ and the $\Sigma^{0}_{k+1}$
formula $(\exists x)\psi_{e}(G,x)$ for $k<n$.

###### Proof.

Let $c:=(\vec{R},\sigma,X)$ with $\mathbb{Q}_{n}$-index $\langle
e_{R},\sigma,e_{X}\rangle$.

  * •

Suppose $\sigma\operatorname{{?}{\vdash}}_{m}(\exists x)\psi_{e}(G,x)$. As in
the proof of Lemma 4.12, by a compactness argument, there exists $t\in\omega$
such that for every 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{t}$, there
is a finite $\tau\subseteq X\cap\\{0,\dots,t\\}$ which is $\vec{R}$-transitive
and $\vec{h}$-homogeneous and some $x\in\omega$ such that

    * –

if $k=0$, $\psi_{e}(\sigma\cup\tau,x)$,

    * –

if $k>0$, $\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$
for some $\ell\geq m.$

$M_{n}$-indices of the colorings $\vec{g}$ defined in Lemma 4.12 are uniformly
$P$-computable in $\langle e_{R},\sigma,e_{X}\rangle$. By Lemma 7.5, one can
$P$-compute uniformly in $M_{n}$-indices of $\vec{g}$ and $e_{X}$ an
$M_{n}$-index of a $\vec{g}$-homogeneous set $H\subseteq X$ in
$\mathcal{M}_{n}\cap\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$.

The colorings $\vec{h}$ are defined uniformly from the colors of
$\vec{g}$-homogeneity of $H$. Thus, the finite $\vec{R}$-transitive and
$\vec{h}$-homogeneous set $\tau\subseteq X\cap\\{0,\dots,t\\}$ is found
$P$-uniformly in $\langle e_{R},\sigma,e_{X}\rangle$. One can therefore
$P$-compute a $\mathbb{Q}_{n}$-index of $d:=(\vec{R},\sigma\cup\tau,H)$
uniformly from a $\mathbb{Q}_{n}$-index of $c$.

If $k=0$, $d$ is the desired extension. If $k>0$, since
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$, then by
induction hypothesis, one can $P$-computably find a $\mathbb{Q}_{n}$-index of
an extension $p\leq d$ such that $p\Vdash\psi_{e}(G,x)$, uniformly in a
$\mathbb{Q}_{n}$-index of $d$, hence in a $\mathbb{Q}_{n}$-index of $c$.

  * •

Suppose $\sigma\operatorname{{?}{\nvdash}}_{m}(\exists x)\psi_{e}(G,x)$. For
every set $Y$, let $\mathcal{P}_{Y}$ be the class of all $m$-tuple of
2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in 2^{Y}$ and
$\vec{S}\in\mathcal{C}_{m}(\sigma,Y)$, such that for all $\tau\subseteq
Y\setminus\\{0,\dots,|\sigma|\\}$ which is $\vec{S}$-transitive and
$\vec{h}$-homogeneous, and for all $x\in\omega$,

    * –

if $k=0$, $\neg\psi_{e}(\sigma\cup\tau,x)$,

    * –

if $k>0$, $\sigma\cup\tau\operatorname{{?}{\vdash}}_{\ell}\neg\psi_{e}(G,x)$
for all $\ell\geq m$.

Note that the class $\mathcal{P}_{Y}$ is $\Pi^{0}_{1}(M_{k}\oplus Y)$
uniformly in $Y$.

Since $\sigma\operatorname{{?}{\nvdash}}_{m}(\exists x)\psi_{e}(G,x)$, there
exists $s\in\omega$ and $Y_{0},\dots Y_{s}$ a partition of $\omega$ such that
for all $i\leq s$, $(\dagger)$ either
$Y_{i}\not\in\mathcal{U}_{C_{k}}^{\mathcal{M}_{k}}$ or
$\mathcal{P}_{Y_{i}}\neq\emptyset$. Let $\mathcal{L}$ be the class of all such
$s$-partitions of $\omega$. Since the statement
“$Y_{i}\not\in\mathcal{U}_{C_{k}}^{\mathcal{M}_{k}}$” is
$\Pi^{0}_{1}(C_{k}\oplus M_{k}^{\prime})$ and the statement
“$\mathcal{P}_{Y_{i}}\neq\emptyset$” is $\Pi^{0}_{1}(M_{k}\oplus Y_{i})$
uniformly in $Y_{i}$, the class $\mathcal{L}$ is $\Pi^{0}_{1}(C_{k}\oplus
M_{k}^{\prime})$ and in particular is $\Pi^{0}_{1}(\mathcal{M}_{n})$ since
$k<n$. One can $P$-compute uniformly in an index of $\mathcal{L}$ an
$M_{n}$-index of some $(Y_{0},\dots,Y_{s})\in\mathcal{L}$. By Lemma 7.5, one
can $P$-compute uniformly in an $M_{n}$-index of $(Y_{0},\dots,Y_{s})$ and an
$M_{n}$-index of $X$ some $i\leq s$ and an $M_{n}$-index of some set
$H_{0}\subseteq X\cap Y_{i}$ in
$\mathcal{M}_{n}\cap\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$. In particular,
$Y_{i}\in\mathcal{U}_{C_{k}}^{\mathcal{M}_{k}}$, thus
$\mathcal{P}_{X_{i}}\neq\emptyset$ and one can $P$-computably find an
$M_{n}$-index of an $m$-tuple $\vec{h}$ and
$\vec{S}\in\mathcal{C}_{m}(\sigma,Y)$ in $\mathcal{P}_{X_{i}}$.

By Lemma 7.5, one can $P$-compute the $M_{n}$-index of a $\vec{h}$-homogeneous
subset $H\subseteq H_{0}$ in
$\mathcal{M}_{n}\cap\mathcal{U}^{\mathcal{M}_{n-1}}_{C_{n-1}}$ uniformly in
$\langle e_{R},\sigma,e_{X}\rangle$. Thus, a $\mathbb{Q}_{n}$-index of the
condition $d:=(\vec{R}\vec{S},\sigma,H)$ can be $P$-computed uniformly in a
$\mathbb{Q}_{n}$-index of $c$ and the formula $(\exists x)\psi_{e}(G,x)$.

∎

######  Lemma 7.7.

In Lemma 6.11, a $\mathbb{Q}_{n}$-index of an extension $d$ can be found
$P$-uniformly from a $\mathbb{Q}_{n}$-index of $c$ and the $\Sigma^{0}_{n+1}$
formula $(\exists x)\psi_{e}(G,x)$.

###### Proof.

Let $m=|\vec{R}|+1$.

  * •

First, suppose $c\operatorname{{?}{\vdash}}(\exists x)\psi_{e}(G,x)$. The
proof is essentially the same as the first case of Lemma 7.6: One define
colorings $\vec{g}$ and $\vec{h}$ similarly, and refine the reservoir into a
$\vec{g}$-homogeneous subset thanks to Lemma 7.5. One therefore obtains a
$\mathbb{Q}_{n}$-index of $d:=(\vec{R},\sigma\cup\tau,H)$ uniformly from a
$\mathbb{Q}_{n}$-index of $c$, where
$\sigma\cup\tau\operatorname{{?}{\nvdash}}_{\ell}\neg\psi_{e}(G,x)$.

Then, by Lemma 7.6, one can $P$-computably find a $\mathbb{Q}_{n}$-index of an
extension $p\leq d$ such that $p\Vdash\psi_{e}(G,x)$, uniformly in a
$\mathbb{Q}_{n}$-index of $d$, hence in a $\mathbb{Q}_{n}$-index of $c$.

  * •

Now, suppose $c\operatorname{{?}{\nvdash}}(\exists x)\psi_{e}(G,x)$. Then,
there exists an $m$-tuple of 2-colorings $\vec{h}=h_{0},\dots,h_{m-1}\in
2^{X}$ and an $m$-tuple of tournaments $\vec{S}\in\mathcal{C}_{m}(\sigma,X)$
such that for every $\vec{h}$-homogeneous and $\vec{S}$-transitive finite
chain $\sigma\subseteq X$ and every $x\in\omega$,
$\sigma\cup\tau\operatorname{{?}{\vdash}}_{m}\neg\psi_{e}(G,x)$. Let
$\mathcal{L}$ be the class of such $m$-tuples of 2 colorings $\vec{h}$ and
$m$-tuples of $\vec{S}\in\mathcal{C}_{m}(\sigma,X)$. By Lemma 4.5,
$\mathcal{C}_{m}(\sigma,X)$ is $\Pi^{0}_{1}(X)$. Since $X\in\mathcal{M}_{n}$,
the class $\mathcal{L}$ is $\Pi_{1}^{0}(\mathcal{M}_{n})$, hence, since
$P\geq_{T}M_{n}$, one can $P$-compute $M_{n}$-indices of a pair
$(\vec{h},\vec{S})\in\mathcal{M}_{n}\cap\mathcal{L}$. By Lemma 7.5, one can
$P$-compute a $\mathbb{Q}_{n}$-index of a $\vec{h}$-homogeneous set
$Y\subseteq X$ in $\mathcal{P}$ uniformly in $\mathcal{M}_{n}$-indices of $X$
and $\vec{h}$. The 3-tuple $d:=(\vec{R}\vec{S},\sigma,Y)$ is a valid
$\mathsf{EM}$-condition such that $d\Vdash(\forall x)\neg\psi_{e}(G,x)$.

∎

We are now ready to prove Theorem 7.1.

###### Proof of Theorem 7.1.

Let $n\geq 1$. Let $P$ be a set of PA degree over $\emptyset^{(n)}$. Let
$(\psi_{s}(G))_{s>0}$ be an enumeration of all $\Sigma_{k+1}^{0}$ formulas for
all $k\leq n$.

Let us begin with a condition $c_{0}:=(T,\emptyset,\omega)$. By induction,
suppose $c_{s-1}$ built, with $i_{s-1}$ a $\mathbb{Q}_{n}$-index of $c_{s-1}$,
Consider the $\Sigma^{0}_{k+1}$ formula $\psi_{s}(G)$ , for $k\leq n$. By
Lemma 7.6 if $k<n$ and by Lemma 7.7 if $k=n$, there exists an extension $d\leq
c_{s-1}$ such that $d\Vdash\psi_{s}(G)$ or $d\Vdash\neg\psi_{s}(G)$. Moreover,
a $\mathbb{Q}_{n}$-index $i_{d}$ of $d$ is $P$-computable uniformly from
$i_{s-1}$ and $s$. Let $c_{s}:=d$, and $i_{s}:=i_{d}$. The
$(c_{s})_{s\in\omega}$ sequence is a decreasing sequence of conditions such
that $\mathcal{F}:=\\{d\in\mathbb{Q}_{n}:(\exists s)c_{s}\leq d\\}$ is
n-generic. By Lemma 4.17 and Lemma 4.3, $G_{\mathcal{F}}$ is infinite and
$T$-transitive, and by Lemma 4.16, $G_{\mathcal{F}}^{(n)}\leq_{T}P$. ∎

## References

  * [1] 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.
  * [2] 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.
  * [3] François G. Dorais.  A variant of Mathias forcing that preserves $\mathsf{ACA}_{0}$.  Arch. Math. Logic, 51(7-8):751–780, 2012.
  * [4] Damir D. Dzhafarov and Carl G. Jockusch, Jr.  Ramsey’s theorem and cone avoidance.  J. Symbolic Logic, 74(2):557–578, 2009.
  * [5] 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.
  * [6] 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\.
  * [7] Marcia J. Groszek and Theodore A. Slaman.  Moduli of computation.  Lecture delivered at ”Logic, Computability and Randomness, 2007.
  * [8] 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.
  * [9] Carl G. Jockusch, Jr.  Ramsey’s theorem and recursion theory.  J. Symbolic Logic, 37:268–280, 1972.
  * [10] Carl G. Jockusch, Jr. and Robert I. Soare.  $\Pi^{0}_{1}$ classes and degrees of theories.  Trans. Amer. Math. Soc., 173:33–56, 1972.
  * [11] Manuel Lerman, Reed Solomon, and Henry Towsner.  Separating principles below Ramsey’s theorem for pairs.  J. Math. Log., 13(2):1350007, 44, 2013.
  * [12] Benoit Monin and Ludovic Patey.  Pigeons do not jump high.  Adv. Math., 352:1066–1095, 2019.
  * [13] 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.
  * [14] 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.
  * [15] Benoit Monin and Ludovic Patey.  The weakness of the pigeonhole principle under hyperarithmetical reductions.  J. Math. Log., 21(3):Paper No. 2150013, 41, 2021.
  * [16] Benoit Monin and Ludovic Patey.  Partition genericity and pigeonhole basis theorems.  The Journal of Symbolic Logic, pages 1–29, 2022.
  * [17] Ludovic Patey.  Degrees bounding principles and universal instances in reverse mathematics.  Ann. Pure Appl. Logic, 166(11):1165–1185, 2015.
  * [18] Ludovic Patey.  Somewhere over the rainbow ramsey theorem for pairs, 2015.
  * [19] Wei Wang.  The definability strength of combinatorial principles.  J. Symb. Log., 81(4):1531–1554, 2016.