Iterative forcing and hyperimmunity in reverse mathematics

Abstract

The separation between two theorems in reverse mathematics is usually done by constructing a Turing ideal satisfying a theorem P and avoiding the solutions to a fixed instance of a theorem Q. Lerman, Solomon and Towsner introduced a forcing technique for iterating a computable non-reducibility in order to separate theorems over omega-models. In this paper, we present a modularized version of their framework in terms of preservation of hyperimmunity and show that it is powerful enough to obtain the same separations results as Wang did with his notion of preservation of definitions. More than the actual separations, we provide a systematic method to design a computability-theoretic property which enables one to distinguish two statements, based on an analysis of their combinatorics.

Keywords

Iterative forcing hyperimmunity reverse mathematics

1. Introduction

Reverse mathematics is a mathematical program which aims to capture the provability content of ordinary (i.e. non set-theoretic) theorems. It uses the framework of subsystems of second-order arithmetic, with a base theory ${RCA}_{0}$ which is composed of the basic axioms of Peano arithmetic together with the $Δ_{1}^{0}$ comprehension scheme and the $Σ_{1}^{0}$ induction scheme. Thanks to the equivalence between $Δ_{1}^{0}$ -definable sets and computable sets, ${RCA}_{0}$ can be thought as capturing “computational mathematics”. See [8] for a good introduction.

Many theorems are $Π_{2}^{1}$ statements $(\forall X) (\exists Y) Φ (X, Y)$ and come with a natural class of instances X. The sets Y such that $Φ (X, Y)$ holds are solutions to X. For example, König’s lemma ( $KL$ ) states that every infinite, finitely branching tree has an infinite path. An instance of $KL$ is an infinite, finitely branching tree T. A solution to T is an infinite path through T. Given two $Π_{2}^{1}$ statements $P$ and $Q$ , proving an implication $Q \to P$ over ${RCA}_{0}$ consists of taking a $P$ -instance X and constructing a solution to X through a computational process involving several applications of the $Q$ statement. Empirically, many proofs of implications are in fact computable reductions [9].

Definition 1.1 (Computable reducibility).

Fix two $Π_{2}^{1}$ statements $P$ and $Q$ . We say that $P$ is computably reducible to $Q$ (written $P ⩽_{c} Q$ ) if every $P$ -instance I computes a $Q$ -instance J such that for every solution X to J, $X \oplus I$ computes a solution to I.

If the computable reduction between from $P$ to $Q$ can be formalized over ${RCA}_{0}$ , then ${RCA}_{0} ⊢ Q \to P$ . However, $P$ may not be computably reducible to $Q$ while ${RCA}_{0} ⊢ Q \to P$ . Indeed, one may need more than one application of $Q$ to solve the instance of $P$ . This is for example the case of Ramsey’s theorem for pairs with k colors ( ${RT}_{k}^{2}$ ) which implies ${RT}_{k + 1}^{2}$ over ${RCA}_{0}$ , but ${RT}_{k + 1}^{2} ≰_{c} {RT}_{k}^{2}$ for $k ⩾ 1$ (see [21]).

In order to prove the non-implication between $P$ and $Q$ , one needs to iterate the computable non-reducibility in order to build a model of $Q$ which is not a model of $P$ . This is the purpose of the framework developed by Lerman, Solomon and Towsner in [14]. They successfully used their framework for separating the Erdős–Moser theorem ( $EM$ ) from the stable ascending descending sequence principle ( $SADS$ ) and separating the ascending descending sequence ( $ADS$ ) from the stable chain antichain principle ( $SCAC$ ). Their approach has been reused by Flood & Towsner [5] and the author [17] on diagonal non-computability statements.

However, their framework suffers some drawbacks. In particular the forcing notions involved are heavy and the deep combinatorics witnessing the non-implications are hidden by the complexity of the proof. Moreover, the $P$ -instance chosen in the ground forcing depends on the forcing notion used in the iteration forcing and therefore the overall construction is not modular. On the other hand, Wang [24] recently introduced the notion of preservation of definitions and made independent proofs of preservations for various statements included $EM$ . Then he deduced that the conjunction of those statements does not imply $SADS$ , therefore strengthening the result of Lerman, Solomon & Towsner in a modular way. Variants of this notion have been reused by the author [21] for separating the free set theorem ( $FS$ ) from ${RT}_{2}^{2}$ .

In this paper, we present a modularized version of the framework of Lerman, Solomon & Towsner and use it to reprove the separation results obtained by Wang [24]. We thereby show that this framework is a viable alternative to the notion introduced by Wang for separating statements in reverse mathematics. In particular, we reprove the following theorem, in which $COH$ is the cohesiveness principle, ${WKL}_{0}$ is weak König’s lemma, ${RRT}_{2}^{2}$ the rainbow Ramsey theorem for pairs, $Π_{1}^{0} G$ the $Π_{1}^{0}$ -genericity principle and ${STS}^{2}$ the stable thin set theorem for pairs.1

¹
This paper is an extended version of a conference paper of the same name published in CiE 2015.

Theorem 1.2 (Wang [24]).

Let Φ be the conjunction of $COH$ , ${WKL}_{0}$ , ${RRT}_{2}^{2}$ , $Π_{1}^{0} G$ , and $EM$ . Over ${RCA}_{0}$ , Φ does not imply any of $SADS$ and ${STS}^{2}$ .

One may object that those separations were already known and that the preservation notion used to separate the two classes of theorems is pretty similar to Wang’s. There is however a fundamental difference between the two approaches.

The approach of Wang [24] with his notion of preservation of non-c.e. definition is mainly explorative. Wang studied various notions of preservation and wondered how the statements in reverse mathematics compare with respect to these notions.

With our technique, we start with two statements that we would like to separate, study the features of their forcing notions and design a computability-theoretic notion which will distinguish them. The resulting process benefits both from the systematic nature of the framework of Lerman, Solomon and Towsner, and the simplicity of Wang’s notion of preservation. Moreover, the resulting computability-theoretic notions are more informative, in that they express the fundamental difference between the combinatorics of the two studied statements. The technique has been already successfully reused by the author to separate Ramsey’s theorem for pairs from the tree theorem for pairs [19].

In Section 2, we introduce the framework of Lerman, Solomon & Towsner in its original form and detail its drawbacks. Then, in Section 3, we develop a modularized version of their framework. In Section 4, we establish basic preservation results, before reproving in Section 5 Wang’s theorem. Last, we reprove in Section 6 the separation obtained by the author in [21].

1.1. Notation

String, sequence. Fix an integer $k \in ω$ . A string (over k) is an ordered tuple of integers $a_{0}, \dots, a_{n - 1}$ (such that $a_{i} < k$ for every $i < n$ ). The empty string is written ε. A sequence (over k) is an infinite listing of integers $a_{0}, a_{1}, \dots$ (such that $a_{i} < k$ for every $i \in ω$ ). Given $s \in ω$ , $k^{s}$ is the set of strings of length s over k and $k^{< ω}$ is the set of finite strings over k. Given a string $σ \in k^{< ω}$ , we denote by $| σ |$ its length. Given two strings $σ, τ \in k^{< ω}$ , σ is a prefix of τ (written $σ ⪯ τ$ ) if there exists a string $ρ \in k^{< ω}$ such that $σ ρ = τ$ . A binary string (resp. real) is a string (resp. sequence) over 2. We may equate a real with a set of integers by considering that the real is its characteristic function.

Tree, path. A tree $T \subseteq ω^{< ω}$ is a set downward-closed under the prefix relation. The tree T is finitely branching if every node $σ \in T$ has finitely many immediate successors. A binary tree is a tree $T \subseteq 2^{< ω}$ . A set $P \subseteq ω$ is a path though T if for every $σ ≺ P$ , $σ \in T$ . A string $σ \in k^{< ω}$ is a stem of a tree T if every $τ \in T$ is comparable with σ. Given a tree T and a string $σ \in T$ , we denote by $T^{[σ]}$ the subtree ${τ \in T : τ ⪯ σ \lor τ ⪰ σ}$ .

Sets. Given two sets X and Y, $X \subseteq^{*} Y$ means that X is almost included into Y, $X =^{*} Y$ means $X \subseteq^{*} Y \land Y \subseteq^{*} X$ and $X \subseteq_{fin} Y$ means that X is a finite subset of Y. Given some $x \in ω$ , $A > x$ denotes the formula $(\forall y \in A) [y > x]$ .

Computation. We fix a computable enumeration $Φ_{0}^{X}, Φ_{1}^{X}, \dots$ of all Turing functionals with oracle X. We write $W_{e}^{X}$ for $dom (Φ_{e}^{X})$ . A set X is Y-computable if there is a Turing index e such that $X = Φ_{e}^{Y}$ .

2. The iteration framework

An ω-structure is a structure $M = (ω, S, +, \cdot, <)$ where ω is the set of standard integers, +, · and < are the standard operations over integers and S is a set of reals such that $M$ satisfies the axioms of ${RCA}_{0}$ . Friedman [6] characterized the second-order parts S of ω-structures as those forming a Turing ideal, that is, a set of reals closed under Turing join and downward-closed under the Turing reduction.

Fix two $Π_{2}^{1}$ statements $P$ and $Q$ . The construction of an ω-model of $P$ which is not a model of $Q$ consists of creating a Turing ideal $I$ together with a fixed $Q$ -instance $I \in I$ , such that every $P$ -instance $J \in I$ has a solution in $I$ , whereas I contains no solution in $I$ . In the first place, let us just focus on the one-step case, that is, a proof that $Q ≰_{c} P$ . To do so, one has to choose carefully some $Q$ -instance I such that every I-computable $P$ -instance has a solution X which does not I-compute a solution to I. The construction of a solution X to some I-computable $P$ -instance J will have to satisfy the following scheme of requirements for each index e: $\begin{matrix} R_{e} : Φ_{e}^{X \oplus I} infinite \to Φ_{e}^{X \oplus I} is not a solution to I . \end{matrix}$ Such requirements may not be satisfiable for an arbitrary $Q$ -instance I. The choice of the instance and the satisfaction of the requirement is strongly dependent on the combinatorics of the statement $Q$ and the forcing notion used for constructing a solution to J. A recurrent approach in the framework of Lerman, Solomon & Towsner consists of constructing a $Q$ -instance I which satisfies some fairness property. The forcing notion $P^{I}$ used in the construction of a solution to J is usually designed so that:

There exists an I-computable set encoding (at least) every condition in $P^{I}$ .

Given some forcing condition in $P^{I}$ , one can uniformly find in a c.e. search a finite set of candidate extensions such that one of them is in $P^{I}$ (e.g. the notion of split pair in [14], the compactness argument for a tree forcing, …).

The fairness property states the following:

“For every condition in $P^{I}$ , if for every $x \in ω$ , there exists a finite $Q$ -instance $A > x$ and a finite set of candidate extensions $d_{0}, \dots, d_{m}$ such that $Φ_{e}^{d_{i} \oplus I}$ is not a solution to A for each $i ⩽ m$ , then one of the A’s is a subinstance of I.”

This property is designed so that we can satisfy it by taking each condition $c \in P^{I}$ one at a time, find some finite $Q$ -instance A on which I is not yet defined, and define I over A. One can think of the instance I as a fair adversary who, if we have infinitely often the occasion to beat him, will be actually beaten at some time.

Suppose now we want to extend this computable non-reducibility into a separation over ω-structures. One may naturally try to make the instance I satisfy the fairness property at every level of the iteration forcing. At the first iteration with an I-computable $P$ -instance J, the property is unchanged. At the second iteration, the $P$ -instance $J_{1}$ is $X_{0} \oplus I$ -computable, but the set $X_{0}$ is not yet constructed. Thankfully, the fairness property requires a finite piece of oracle $X_{0}$ . Therefore we can modify the fairness property which becomes

“For every condition $c_{0} \in P^{I}$ and every condition $c_{1} \in P^{c_{0} \oplus I}$ , if for every $x \in ω$ , there exists a $Q$ -instance $A > x$ , a finite set of candidate extensions $d_{0}, \dots, d_{m} \in P^{I}$ and $d_{0, i}, \dots, d_{n_{i}, i} \in P^{d_{i} \oplus I}$ for each $i ⩽ m$ such that $Φ_{e}^{d_{j, i} \oplus d_{i} \oplus I}$ is not a solution to A for each $i ⩽ m$ and $j ⩽ n_{i}$ , then one of the A’s is a subinstance of I.”

Since this property becomes overly complicated in the general case, Lerman, Solomon and Towsner abstracted the notion of requirement and made it a $Σ_{1}^{0, I}$ black box which takes as parameters a condition and a finite $Q$ -instance. Instead of making the instance I in charge of satisfying the fairness property at every level of the iteration forcing, the instance I satisfies the property only at the first level. Then, by encoding a requirement at the next level into a requirement at the current level, the iteration forcing ensures the propagation of this fairness property from the first level to every level. The property in its abstracted form is then

“For every condition in $P^{I}$ and every $Σ_{1}^{0, I}$ predicate $K^{I}$ , if for every $x \in ω$ , there is a finite $Q$ -instance $A > x$ and a finite set of candidate extensions $d_{0}, \dots, d_{m}$ such that $K^{I} (A, d_{i})$ is satisfied for each $i ⩽ m$ , then one of the A’s is a subinstance of I.”

In particular, by letting $K^{I} (A, c)$ be the predicate “ $Φ_{e}^{d_{i} \oplus I}$ is not a solution to A”, the requirements $R_{e}$ will be satisfied.

The problem of such an approach is that the construction of the $Q$ -instance strongly depends on the forcing notion used in the iteration forcing. A slight modification of the latter requires a change in the ground forcing. Moreover, if someone wants to prove that the conjunction of two statements does not imply a third one, we need to construct an instance I which will satisfy the fairness property for the two statements, and in each iteration forcing, we will need to ensure that both properties are propagated to the next iteration. The size of the overall construction explodes when trying to make a separation of the conjunction of several statements at the same time.

3. Preservation of hyperimmunity

In this section, we propose a general simplification of the framework of Lerman, Solomon & Towsner [14] and illustrate it in the case of the separation of $EM$ from $SADS$ . The corresponding fairness property happens to coincide with the notion of hyperimmunity. The underlying idea ruling this simplification is the following: since each condition in the iteration forcing can be given an index and since the finite set of candidate extensions of a condition c, can be found in a c.e. search, given a $Σ_{1}^{0, I}$ predicate $K^{I}$ , the following formula is again $Σ_{1}^{0, I}$ :

$φ (U)$ = “there exists a finite set of candidate extensions $d_{0}, \dots, d_{m}$ of c such that $K^{I} (U, d_{i})$ is satisfied for each $i ⩽ m$ ”.

We can therefore abstract the iteration forcing and ask the instance I to satisfy the following property:

“For every $Σ_{1}^{0, I}$ predicate $φ (U)$ , if for every $x \in ω$ , there exists a finite $Q$ -instance $A > x$ such that $φ (A)$ is satisfied, then one of the A’s is a subinstance of I.”

Let us illustrate how this simplification works by reproving the separation of the Erdős–Moser theorem from the ascending descending sequence principle.

Definition 3.1 (Ascending descending sequence).

$ADS$ is the statement “Every linear order admits an infinite ascending or descending sequence”. $SADS$ is the restriction of $ADS$ to linear orders of type $ω + ω^{*}$ .

The ascending descending sequence principle has been studied within the framework of reverse mathematics by Hirschfeldt & Shore [10]. Lerman, Solomon & Towsner [14] constructed an infinite linear order I of order type $ω + ω^{*}$ with ω and $ω^{*}$ parts respectively $B_{0}$ and $B_{1}$ , such that for every condition c and every $Σ_{1}^{0, I}$ predicate $K^{I}$ , if for every $x \in ω$ , there exists a finite set $A > x$ and a finite set of candidate extensions $d_{0}, \dots, d_{m}$ of c such that $K^{I} (A, d_{i})$ is satisfied for each $i ⩽ m$ , then one of the A’s will be included in $B_{0}$ and another one will be included in $B_{1}$ . In particular, taking $K^{I} (A, c) = Φ_{e}^{c \oplus I} \cap A \neq \emptyset$ , no infinite solution to the constructed tournament I-computes a solution to I. After abstraction, we obtain the following property:

“For every $Σ_{1}^{0, I}$ predicate $φ (U)$ , if for every $x \in ω$ , there exists a finite set $A > x$ such that $φ (A)$ is satisfied, one of the A’s is included in $B_{0}$ and one of the A’s is included in $B_{1}$ .”

Following the terminology of [14], we say that a formula $φ (U)$ is essential if for every $x \in ω$ , there exists some finite set $A > x$ such that $φ (A)$ holds. This fairness property coincides with the notion of hyperimmunity for ${\overline{B}}_{0}$ and ${\overline{B}}_{1}$ .

Definition 3.2 (Preservation of hyperimmunity).

Let $D_{0}, D_{1}, \dots$ be a computable list of all finite sets and let f be computable. A c.e. array ${D_{f (i)}}_{i ⩾ 0}$ is a c.e. set of mutually disjoint finite sets $D_{f (i)}$ . A set B is hyperimmune if for every c.e. array ${D_{f (i)}}_{i ⩾ 0}$ , $D_{f (i)} \cap B = \emptyset$ for some i.

A $Π_{2}^{1}$ statement $P$ admits preservation of hyperimmunity if for each set Z, each countable collection of Z-hyperimmune sets $A_{0}, A_{1}, \dots$ , and each $P$ -instance $X ⩽_{T} Z$ there exists a solution Y to X such that the A’s are $Y \oplus Z$ -hyperimmune.

The following lemma establishes the link between the fairness property for $SADS$ and the notion of hyperimmunity.

Lemma 3.3.
Fix a set Z. A set B is Z-hyperimmune if and only if for every essential $Σ_{1}^{0, Z}$ predicate $φ (U)$ , $φ (A)$ holds for some finite set $A \subseteq \overline{B}$ .
Proof.
Let $D_{0}, D_{1}, \dots$ be a computable list of all finite sets.
Fix some set Z and some Z-hyperimmune set B. For every essential $Σ_{1}^{0, Z}$ formula $φ (U)$ , define the Z-computable function f inductively so that $φ (D_{f (0)})$ holds and for every i, $D_{f (i + 1)} > D_{f (i)}$ and $φ (D_{f (i + 1)})$ holds. Because $φ (U)$ is essential, the function f is total. ${D_{f (i)}}_{i ⩾ 0}$ is a Z-c.e. array, so by Z-hyperimmunity, $D_{f (i)} \cap B = \emptyset$ for some i, hence $D_{f (i)} \subseteq \overline{B}$ and $φ (D_{f (i)})$ holds.

Fix some set Z and some set B such that the fairness property of Lemma 3.3 holds. For every Z-c.e. array ${D_{f (i)}}_{i ⩾ 0}$ , define the $Σ_{1}^{0, Z}$ formula $φ (U) = (\exists i) [U = D_{f (i)}]$ . The formula $φ (U)$ is essential, so there exists some finite set $A \subseteq \overline{B}$ such that $φ (A)$ holds. In particular, there exists some i such that $D_{f (i)} \subseteq \overline{B}$ . □

Hirschfeldt, Shore & Slaman constructed in [11, Theorem 4.1] a computable linear order of type $ω + ω^{}$ such that both the ω and the $ω^{}$ part are hyperimmune. As every ascending (resp. descending) sequence is an infinite subset of the ω (resp. $ω^{}$ ) part of the linear order, we deduce the following theorem.
Theorem 3.4.
$SADS$ does not admit preservation of hyperimmunity.*

A slight modification of the forcing in [14] gives preservation of hyperimmunity of the Erdős–Moser theorem. We will however reprove it in a later section with a simpler forcing notion. As expected, the notion of preservation of hyperimmunity can be used to separate statements in reverse mathematics.
Lemma 3.5.
Fix two $Π_{2}^{1}$ statements $P$ and $Q$ . If $P$ admits preservation of hyperimmunity and $Q$ does not, then $P$ does not imply $Q$ over ${RCA}_{0}$ .
Proof.
Fix a set $X_{0}$ , a countable collection of $X_{0}$ -hyperimmune sets $B_{0}, B_{1}, \dots$ and an $X_{0}$ -computable $Q$ -instance J such that for every solution Y to J, one of the B’s is not $Y \oplus X_{0}$ -hyperimmune. By preservation of hyperimmunity of $P$ and carefully choosing a sequence of $P$ -instance functionals $I_{0}, I_{1}, \dots$ , we can define an infinite sequence of sets $X_{1}, X_{2}, \dots$ such that for each $n \in ω$ .
$X_{n + 1}$ is a solution to the $P$ -instance $I_{n}^{X_{0} \oplus \dots \oplus X_{n}}$ .

The B’s are $X_{0} \oplus \dots \oplus X_{n}$ -hyperimmune.

For every $X_{0} \oplus \dots \oplus X_{n}$ -computable $P$ -instance I, there exists some m such that $I = I_{m}^{X_{0} \oplus \dots \oplus X_{m}}$ .
Let $M$ be the ω-structure whose second-order part is the Turing ideal $\begin{matrix} I = {Y : (\exists n) [Y ⩽_{T} X_{0} \oplus \dots \oplus X_{n}]} . \end{matrix}$ In particular, the $Q$ -instance J is in $I$ , but the B’s are Y-hyperimmune for every $Y \in I$ , so J has no solution $Y \in I$ and $M ⊭ Q$ . By construction of $I$ , every $P$ -instance $I \in I$ has a solution $X_{n} \in I$ , so by Friedman [6], $M ⊧ {RCA}_{0} \land P$ . □

Before starting an analysis of preservations of hyperimmunity for basic statements, we state another negative preservation result which enables to reprove that the Erdős–Moser theorem does not imply the stable thin set theorem for pairs [22].
Definition 3.6 (Thin set theorem).

A coloring $f : {[ω]}^{2} \to ω$ is stable if for every x, ${lim}_{y} f (x, y)$ exists. Let $n \in ω$ and $f : {[ω]}^{n} \to ω$ . A set A is f-thin if $f ({[A]}^{n}) \neq ω$ , that is, if the set A “avoids” at least one color. ${TS}^{n}$ is the statement “every function $f : {[ω]}^{n} \to ω$ has an infinite f-thin set”. ${STS}^{2}$ is the restriction of ${TS}^{2}$ to stable colorings.

Introduced by Friedman in [7], the basic reverse mathematics of the thin set theorem has been settled by Cholak, Hirst & Jockusch in [2]. Its study has been continued by Wang [25], Rice [23] and the author [15,21]. The author constructed in [18] an infinite computable stable coloring $f : {[ω]}^{2} \to ω$ such that the sets $B_{i} = {n \in ω : {lim}_{s} f (n, s) \neq i}$ are all hyperimmune. Every infinite f-thin set being an infinite subset of one of the B’s, we deduce the following theorem.

Theorem 3.7.
${STS}^{2}$ does not admit preservation of hyperimmunity.

4. Basic preservations of hyperimmunity

When defining a notion, it is usually convenient to see how it relates with typical sets. There are two kinds of typicalities: genericity and randomness. Both notions admit preservation of hyperimmunity.

Theorem 4.1.
Fix some set Z and a countable collection of Z-hyperimmune sets $B_{0}, B_{1}, \dots$ . If G is sufficiently Cohen generic relative to Z, the B’s are $G \oplus Z$ -hyperimmune.
Proof.
It suffices to prove that for every $Σ_{1}^{0, Z}$ formula $φ (G, U)$ and every $i \in ω$ , the set of conditions σ forcing $φ (G, U)$ not to be essential or such that $φ (σ, A)$ holds for some finite set $A \subset {\overline{B}}_{i}$ is dense. Fix any string $σ \in 2^{< ω}$ . Define $\begin{matrix} ψ (U) = (\exists τ ⪰ σ) φ (τ, U) . \end{matrix}$ The formula $ψ (U)$ is $Σ_{1}^{0, Z}$ , so by Z-hyperimmunity of $B_{i}$ , either $ψ (U)$ is not essential, or $ψ (A)$ holds for some finite set $A \subseteq {\overline{B}}_{i}$ . If $ψ (U)$ is not essential with witness $x \in ω$ , then σ forces $φ (G, U)$ not to be essential with the same witness. If $ψ (U)$ is essential, then there exists some finite set $A \subset {\overline{B}}_{i}$ such that $ψ (A)$ holds. Unfolding the definition of $ψ (A)$ , there exists some $τ ⪰ σ$ such that $φ (τ, A)$ holds. The condition τ is an extension such that $φ (τ, A)$ holds for some $A \subset {\overline{B}}_{i}$ . □
Theorem 4.2.
Fix some set Z and a countable collection of Z-hyperimmune sets $B_{0}, B_{1}, \dots$ . If R is sufficiently random relative to Z, the B’s are $R \oplus Z$ -hyperimmune.
Proof.
It suffices to prove that for every $Σ_{1}^{0, Z}$ formula $φ (G, U)$ and every $i \in ω$ , the following class is Lebesgue null. $\begin{matrix} S = {X : [φ (X, U) is essential] \land (\forall A \subseteq_{fin} ω) φ (X, A) \to A ⊈ {\overline{B}}_{i}} . \end{matrix}$ Suppose it is not the case. There exists $σ \in 2^{< ω}$ such that $\begin{matrix} μ (X \in S : σ ≺ X) > 2^{- | σ | - 1} . \end{matrix}$ Define $\begin{matrix} ψ (U) = [μ (X : (\exists \tilde{A} \subseteq U) φ (X, \tilde{A})) > 2^{- | σ | - 1}] . \end{matrix}$ The formula $ψ (U)$ is $Σ_{1}^{0, Z}$ and by compactness, $ψ (U)$ is essential. By Z-hyperimmunity of $B_{i}$ , there exists some finite set $A \subseteq {\overline{B}}_{i}$ such that $ψ (A)$ holds. For every set A such that $ψ (A)$ holds, there exists some $X \in S$ and some $\tilde{A} \subseteq A$ such that $φ (X, \tilde{A})$ holds. By definition of $X \in S$ , $\tilde{A} ⊈ {\overline{B}}_{i}$ and therefore $A ⊈ {\overline{B}}_{i}$ . Contradiction. □

Note that this does not mean that the sets G and R are hyperimmune-free relative to Z. In fact, the converse holds: if G is sufficiently generic and R sufficiently random, then both are Z-hyperimmune. Some statements like the atomic model theorem ( $AMT$ ), $Π_{1}^{0}$ -genericity ( $Π_{1}^{0} G$ ) and the rainbow Ramsey theorem for pairs ( ${RRT}_{2}^{2}$ ) are direct consequences of genericity and randomness [4,11]. We can deduce from Theorem 4.1 and Theorem 4.2 that they all admit preservation of hyperimmunity.

Cohesiveness is a very useful statement in the analysis of Ramsey-type theorems as it enables one to transform an arbitrary instance into a stable one [3]. A set C is cohesive for a sequence of sets $R_{0}, R_{1}, \dots$ if $C \subseteq^{} R_{i}$ or $C \subseteq^{} {\overline{R}}_{i}$ for each i.
Theorem 4.3.
$COH$ admits preservation of hyperimmunity.

The proof is done by the usual construction of a cohesive set with Mathias forcing, combined with the following lemma.
Lemma 4.4.
For every set Z, every Z-computable Mathias condition $(F, X)$ , every $Σ_{1}^{0, Z}$ formula $φ (G, U)$ and every Z-hyperimmune set B, there exists an extension $(E, Y)$ such that $X =^{} Y$ and either* $φ (G, U)$ is not essential for every set G satisfying $(E, Y)$ , or $φ (E, A)$ holds for some finite set $A \subseteq \overline{B}$ .
Proof.
Define $\begin{matrix} ψ (U) = (\exists G \supseteq F) [G \subseteq F \cup X \land φ (G, U)] . \end{matrix}$ The formula $ψ (U)$ is $Σ_{1}^{0, Z}$ . By hyperimmunity of B, either $ψ (U)$ is not essential, or $ψ (A)$ holds for some finite set $A \subseteq \overline{B}$ . In the first case, the condition $(F, X)$ already satisfies the desired property. In the second case, let $A \subseteq_{fin} \overline{B}$ be such that $ψ (A)$ holds. By the use property, there exists a finite set E satisfying $(F, X)$ such that $φ (E, A)$ holds. Let $Y = X \ [0, max (E)]$ . The condition $(E, Y)$ is a valid extension. □

Weak König’s lemma ( ${WKL}_{0}$ ) states that every infinite, binary tree admits an infinite path.
Theorem 4.5.
${WKL}_{0}$ admits preservation of hyperimmunity.
Proof.
Fix some set Z, some countable collection of Z-hyperimmune sets $B_{0}, B_{1}, \dots$ and some Z-computable tree $T \subseteq 2^{< ω}$ . Our forcing conditions are $(σ, R)$ where σ is a stem of the infinite, Z-computable tree $R \subseteq T$ . A condition $(τ, S)$ extends $(σ, R)$ if $σ ⪯ τ$ and $S \subseteq R$ . The result is a direct consequence of the following lemma. Lemma 4.6.
For every condition $c = (σ, R)$ , every $Σ_{1}^{0, Z}$ formula $φ (G, U)$ and every $i \in ω$ , there exists an extension $d = (τ, S)$ such that $φ (P, U)$ is not essential for every path $P \in [S]$ , or $φ (τ, A)$ holds for some $A \subseteq {\overline{B}}_{i}$ .
Proof.
Define $\begin{matrix} ψ (U) = (\exists s) (\forall τ \in R \cap 2^{s}) (\exists \tilde{A} \subseteq_{fin} U) φ (τ, \tilde{A}) . \end{matrix}$ The formula $ψ (U)$ is $Σ_{1}^{0, Z}$ so we have two cases:
Case 1: $ψ (U)$ is not essential with some witness x. By compactness, the following set is an infinite Z-computable subtree of R: $\begin{matrix} S = {τ \in R : (\forall A > x) \neg φ (τ, A)} . \end{matrix}$ The condition $d = (σ, S)$ is an extension such that $φ (P, U)$ is not essential for every $P \in [S]$ .

Case 2: $ψ (U)$ is essential. By Z-hyperimmunity of $B_{i}$ , there exists some finite set $A \subseteq {\overline{B}}_{i}$ such that $ψ (A)$ holds. Unfolding the definition of $ψ (A)$ , there exists some $τ \in R$ such that $R^{[τ]}$ is infinite and $φ (τ, \tilde{A})$ holds for some $\tilde{A} \subseteq A \subseteq {\overline{B}}_{i}$ . The condition $d = (τ, R^{[τ]})$ is an extension such that $φ (τ, \tilde{A})$ holds for some finite set $\tilde{A} \subseteq {\overline{B}}_{i}$ . □

Using Lemma 4.6, define an infinite descending sequence of conditions $c_{0} = (ϵ, T) ⩾ c_{1} ⩾ \dots$ such that for each $s \in ω$
$| σ_{s} | ⩾ s$ ,

$φ (P, U)$ is not essential for every path $P \in [R_{s + 1}]$ , or $φ (σ_{s + 1}, A)$ holds for some finite set $A \subseteq {\overline{B}}_{i}$ if $s = ⟨ φ, i ⟩$ ,
where $c_{s} = (σ_{s}, R_{s})$ . □

Wei Wang [personal communication] observed that ${WKL}_{0}$ preserves hyperimmunity in a much stronger sense than $COH$ , since cohesive sets are of hyperimmune degree [13], whereas by the hyperimmune-free basis theorem [12], ${WKL}_{0}$ can preserve hyperimmunities of every hyperimmune set simultaneously and not only countably many.
5. The Erdős–Moser theorem and preservation of hyperimmunity

The Erdős–Moser theorem is a statement from graph theory which received a particular interest from reverse mathematical community as it provides, together with the ascending descending sequence principle, an alternative proof of Ramsey’s theorem for pairs.

Definition 5.1 (Erdős–Moser theorem).

A tournament T is an irreflexive binary relation such that for all $x, y \in ω$ with $x \neq y$ , exactly one of $T (x, y)$ or $T (y, x)$ holds. A tournament T is transitive if the corresponding relation T is transitive in the usual sense. $EM$ is the statement “Every infinite tournament T has an infinite transitive subtournament.”

The Erdős–Moser theorem was introduced in reverse mathematics by Bovykin & Weiermann [1] and then studied by Lerman, Solomon & Towsner [14] and the author [15,16,20]. In this section, we give a simple proof of the following theorem.

Theorem 5.2.
$EM$ admits preservation of hyperimmunity.

The proof of Theorem 5.2 exploits the modularity of the framework by using preservation of hyperimmunity of ${WKL}_{0}$ . Together with the previous preservations results, this theorem is sufficient to reprove Theorem 1.2. We must first introduce some terminology.
Definition 5.3 (Minimal interval).

Let T be an infinite tournament and $a, b \in T$ be such that $T (a, b)$ holds. The interval $(a, b)$ is the set of all $x \in T$ such that $T (a, x)$ and $T (x, b)$ hold. Let $F \subseteq T$ be a finite transitive subtournament of T. For $a, b \in F$ such that $T (a, b)$ holds, we say that $(a, b)$ is a minimal interval of F if there is no $c \in F \cap (a, b)$ , i.e., no $c \in F$ such that $T (a, c)$ and $T (c, b)$ both hold.

Definition 5.4.
An Erdős Moser condition (EM condition) for an infinite tournament T is a Mathias condition $(F, X)$ where
$F \cup {x}$ is T-transitive for each $x \in X$ ,

X is included in a minimal T-interval of F.

EM extension is Mathias extension. A set G satisfies an EM condition $(F, X)$ if it is T-transitive and satisfies the Mathias extension $(F, X)$ . Basic properties of EM conditions have been stated and proven in [16].

Fix a set Z and some countable collection of Z-hyperimmune sets $B_{0}, B_{1}, \dots$ . Our forcing notion is the partial order of Erdős Moser conditions $(F, X)$ such that the B’s are $X \oplus Z$ -hyperimmune. Our initial condition is $(\emptyset, ω)$ . By Lemma 5.9 in [16], EM conditions are extendable, so we can force the transitive subtournament to be infinite. Therefore it suffices to prove the following lemma to deduce Theorem 5.2. Lemma 5.5.
Fix a condition $(F, X)$ , some $i \in ω$ and some $Σ_{1}^{0, Z}$ formula $φ (G, U)$ . There exists an extension $(E, Y)$ such that either $φ (G, U)$ is not essential for every set G satisfying $(E, Y)$ , or $φ (E, A)$ holds for some finite set $A \subseteq {\overline{B}}_{i}$ .
Proof.
Let $ψ (U)$ be the formula “For every partition $X_{0} \cup X_{1} = X$ , there exists some $j < 2$ , a T-transitive set $G \subseteq X_{j}$ and a set $\tilde{A} \subseteq U$ such that $φ (F \cup G, \tilde{A})$ holds.” By compactness, $ψ (U)$ is a $Σ_{1}^{0, X \oplus Z}$ formula. By $X \oplus Z$ -hyperimmunity of $B_{i}$ , we have two cases:
Case 1: $ψ (A)$ holds for some finite set $A \subseteq {\overline{B}}_{i}$ . By compactness, there exists a finite set $H \subset X$ such that for every partition $H_{0} \cup H_{1} = H$ , there exists some $j < 2$ , a T-transitive set $G \subseteq H_{j}$ and a set $\tilde{A} \subseteq A$ such that $φ (F \cup G, \tilde{A})$ holds. Given two sets U and V, we denote by $U \to_{T} V$ the formula $(\forall x \in U) (\forall y \in V) T (x, y)$ . Each element $y \in X$ induces a partition $H_{0} \cup H_{1} = H$ such that $H_{0} \to_{T} {y} \to_{T} H_{1}$ . There exists finitely many such partitions, so by the infinite pigeonhole principle, there exists an X-computable infinite set $Y \subset X$ and a partition $H_{0} \cup H_{1} = H$ such that $H_{0} \to_{T} Y \to_{T} H_{1}$ . Let $j < 2$ and $G \subseteq H_{j}$ be the T-transitive set such that $φ (F \cup G, \tilde{A})$ holds for some $\tilde{A} \subseteq A \subseteq {\overline{B}}_{i}$ . By Lemma 5.9 in [16], $(F \cup G, Y)$ is a valid extension.

Case 2: $ψ (U)$ is not essential with some witness x. Then the $Π_{1}^{0, X \oplus Z}$ class $C$ of sets $X_{0} \oplus X_{1}$ such that $X_{0} \cup X_{1} = X$ and for every $j < 2$ , every T-transitive set $G \subseteq X_{j}$ and every finite set $\tilde{A} > x$ , the formula $φ (F \cup G, \tilde{A})$ does not hold is not empty. By preservation of hyperimmunity of ${WKL}_{0}$ , there exists some partition $X_{0} \oplus X_{1} \in C$ such that the B’s are $X_{0} \oplus X_{1} \oplus Z$ -hyperimmune. The set $X_{j}$ is infinite for some $j < 2$ and the condition $(F, X_{i})$ is the desired EM extension. □

6. Thin set theorem and preservation of hyperimmunity

There exists a fundamental difference in the way $SADS$ and ${STS}^{2}$ witness their failure of preservation of hyperimmunity. In the case of $SADS$ , we construct two hyperimmune sets whereas in the case of ${STS}^{2}$ , a countable collection of hyperimmune sets is used. This difference can be exploited to obtain further separation results.

Definition 6.1 (Preservation of k hyperimmunities).

A $Π_{2}^{1}$ statement $P$ admits preservation of k hyperimmunities if for each set Z, each Z-hyperimmune sets $A_{0}, \dots, A_{k - 1}$ , and each $P$ -instance $X ⩽_{T} Z$ there exists a solution Y to X such that the A’s are $Y \oplus Z$ -hyperimmune.

Theorem 3.4 shows that $SADS$ does not admit preservation of 2 hyperimmunities. On the other hand, we shall see that ${STS}^{2}$ admits preservation of k hyperimmunities for every $k \in ω$ . Consider the following variants of the thin set theorem.

Definition 6.2 (Thin set theorem).

Given a function $f : {[ω]}^{n} \to k$ , an infinite set H is f-thin if $| f ({[H]}^{n}) | ⩽ k - 1$ (i.e. f avoids one color over H). For every $n ⩾ 1$ and $k ⩾ 2$ , ${TS}_{k}^{n}$ is the statement “Every function $f : {[ω]}^{n} \to k$ has an infinite f-thin set”. ${STS}_{k}^{2}$ is the restriction of ${TS}_{k}^{2}$ to stable colorings.

Note that ${TS}_{2}^{2}$ is Ramsey’s theorem for pairs. The following theorem is sufficient to separate ${TS}^{2}$ from Ramsey’s theorem for pairs as ${TS}^{2} ⩽_{c} {TS}_{k}^{2}$ for every $k ⩾ 2$ .

Theorem 6.3.
For every $k ⩾ 1$ , ${TS}_{k + 1}^{2}$ admits preservation of k but not $k + 1$ hyperimmunities.

Before proving Theorem 6.3, we establish a few consequences. In the case $k = 1$ , noticing that the arithmetical comprehension scheme ( ${ACA}_{0}$ ) does not preserve 1 hyperimmunities as witnessed by taking any $Δ_{2}^{0}$ hyperimmune set, we re-obtain the separation of Ramsey’s theorem for pairs from ${ACA}_{0}$ . Hirschfeldt & Jockusch [9] asked whether ${TS}_{k + 1}^{2}$ implies ${TS}_{k}^{2}$ over ${RCA}_{0}$ . The author answered negatively in [21]. Preservation of k hyperimmunities gives the same separation.
Theorem 6.4 (Patey [21]).

For every $k ⩾ 2$ , let Φ be the conjunction of $COH$ , ${WKL}_{0}$ , ${RRT}_{2}^{2}$ , $Π_{1}^{0} G$ , $EM$ , ${TS}_{k + 1}^{2}$ . Over ${RCA}_{0}$ , Φ does not imply any of $SADS$ and ${STS}_{k}^{2}$ .

We now prove Theorem 6.3. All the proofs in this section are very similar to [21]. We reprove everything in the context of preservation of hyperimmunities for the sake of completeness. The negative part of Theorem 6.3 is obtained by a simple finite injury priority construction (see [18]).

Lemma 6.5.
For every $k ⩾ 2$ , ${TS}_{k}^{2}$ does not admit preservation of k hyperimmunities.
Proof.
By [18], there is an infinite computable stable coloring $f : {[ω]}^{2} \to ω$ such that the sets $B_{i} = {n \in ω : {lim}_{s} f (n, s) \neq i}$ are all hyperimmune. The coloring $g : {[ω]}^{2} \to k$ defined by $g (x, y) = max (f (x, y), k - 1)$ witnesses that ${TS}_{k}^{2}$ does not admit preservation of k hyperimmunities. □
Definition 6.6 (Strong preservation of k hyperimmunities).

A $Π_{2}^{1}$ statement $P$ admits strong preservation of k hyperimmunities if for each set Z, each Z-hyperimmune sets $B_{0}, \dots, B_{k - 1}$ and each (arbitrary) $P$ -instance X, there exists a solution Y to X such that the B’s are $Y \oplus Z$ -hyperimmune.

The following lemma has been proven by the author in its full generality in [15]. We reprove it in the context of preservation of k hyperimmunities.

Lemma 6.7.
For every $k, n ⩾ 1$ and $ℓ ⩾ 2$ , if ${TS}_{ℓ}^{n}$ admits strong preservation of k hyperimmunities, then ${TS}_{ℓ}^{n + 1}$ admits preservation of k hyperimmunities.
Proof.
Fix any set Z, some Z-hyperimmune sets $B_{0}, \dots, B_{k - 1}$ and any Z-computable coloring $f : {[ω]}^{n + 1} \to ℓ$ . Consider the uniformly Z-computable sequence of sets $R_{σ, i}$ defined for each $σ \in {[ω]}^{n}$ and $i < ℓ$ by $\begin{matrix} R_{σ, i} = {s \in ω : f (σ, s) = i} . \end{matrix}$ As $COH$ admits preservation of k hyperimmunities, there exists some $\vec{R}$ -cohesive set G such that the B’s are $G \oplus Z$ -hyperimmune. The cohesive set induces a ${(G \oplus Z)}^{'}$ -computable coloring $\tilde{f} : {[ω]}^{n} \to ℓ$ defined by: $\begin{matrix} (\forall σ \in {[ω]}^{n}) \tilde{f} (σ) = lim_{s \in G} f (σ, s) . \end{matrix}$ As ${TS}_{ℓ}^{n}$ admits strong preservation of k hyperimmunities, there exists an infinite $\tilde{f}$ -thin set H such that the B’s are $H \oplus G \oplus Z$ -hyperimmune. $H \oplus G \oplus Z$ computes an infinite f-thin set. □

Thanks to Lemma 6.7, it suffices to prove the following theorem to deduce the positive part of Theorem 6.3.
Theorem 6.8.
For every $k ⩾ 1$ , ${TS}_{k + 1}^{1}$ admits strong preservation of k hyperimmunities.

The remainder of this section is devoted to the proof of Theorem 6.8. Fix some set Z, some Z-hyperimmune sets $B_{0}, \dots, B_{k - 1}$ and some $(k + 1)$ -partition $A_{0} \cup \dots \cup A_{k} = ω$ . We will construct an infinite set G such that $G \cap {\overline{A}}_{i}$ is infinite for each $i ⩽ k$ and the B’s are $(G \cap {\overline{A}}_{i}) \oplus Z$ -hyperimmune for some $i ⩽ k$ . Our forcing conditions are Mathias conditions $(F, X)$ such that the B’s are $X \oplus Z$ -hyperimmune.
6.1. Forcing limitlessness

We want to satisfy the following scheme of requirements to ensure that $G \cap {\overline{A}}_{i}$ is infinite for each $i ⩽ k$ . $\begin{matrix} Q_{p} : (\exists m_{0}, \dots, m_{k} > p) [m_{0} \in G \cap {\overline{A}}_{0} \land \dots \land m_{k} \in G \cap {\overline{A}}_{k}] . \end{matrix}$

We say that an $(k + 1)$ -partition $A_{0} \cup \dots \cup A_{k - 1} = ω$ is non-trivial if there exists no infinite set $H \subseteq {\overline{A}}_{i}$ for some $i < k$ such that the B’s are $H \oplus Z$ -hyperimmune. A condition $(F, X)$ forces $Q_{p}$ if there exists $m_{0}, \dots, m_{k} > p$ such that $m_{i} \in F \cap {\overline{A}}_{i}$ for each $i ⩽ k$ . Therefore, if G satisfies c and c forces $Q_{p}$ , then G satisfies the requirement $Q_{p}$ . We now prove that the set of conditions forcing $Q_{p}$ is dense for each $p \in ω$ . Therefore, every sufficiently generic filter will induce $k + 1$ infinite sets $G \cap {\overline{A}}_{0}, \dots, G \cap {\overline{A}}_{k}$ .

Lemma 6.9.
For every condition c and every $p \in ω$ , there is a condition d extending c such that d forces $Q_{p}$ .
Proof.
Fix some $p \in ω$ . It is sufficient to show that for a condition $c = (F, X)$ and some $i ⩽ k$ , there exists an extension $d_{0} = (H, Y)$ and some integer $m_{i} > p$ that $m_{i} \in H \cap {\overline{A}}_{i}$ . By iterating the process for each $i ⩽ k$ , we obtain the desired extension d. Suppose for the sake of contradiction that $X \cap {\overline{A}}_{i}$ is finite. Then one can X-compute an infinite set H thin for the A’s with witness j for any $j \neq i$ , contradicting non-triviality of f. Therefore, there exists an $m_{i} \in X \cap {\overline{A}}_{i}$ , $m_{i} > p$ . The condition $d_{0} = (F \cup {m_{i}}, X \ [0, m_{i}])$ is the desired extension. □

6.2. Forcing non-preservation

Fix an enumeration $φ_{0} (G, U), φ_{1} (G, U), \dots$ of all $Σ_{1}^{0, Z}$ formulas. The second scheme of requirements consists in ensuring that the sets $B_{0}, \dots, B_{k - 1}$ are all $G \cap {\overline{A}}_{i}$ -hyperimmune for some $i ⩽ k$ . The requirements are of the following form for each $\vec{e}$ . $\begin{matrix} R_{\vec{e}} : \underset{j < k}{⋀} R_{e_{0}}^{A_{0}, B_{j}} \lor \dots \lor \underset{j < k}{⋀} R_{e_{k}}^{A_{k}, B_{j}} \end{matrix}$ where $\begin{matrix} R_{e}^{A_{i}, B_{j}} : φ_{e} (G \cap {\overline{A}}_{i}, U) essential \Rightarrow (\exists A \subseteq_{fin} {\overline{B}}_{j}) φ_{e} (G \cap {\overline{A}}_{i}, A) . \end{matrix}$

A condition forces $R_{\vec{e}}$ if every set G satisfying this condition also satisfies the requirement $R_{\vec{e}}$ .

Lemma 6.10.
For every condition $c = (F, X)$ , every $i_{0} < i_{1} ⩽ k$ , every $j < k$ and every indices $\vec{e}$ , there exists an extension d such that for some $i \in {i_{0}, i_{1}}$ , d forces $φ_{e_{i}} (G \cap {\overline{A}}_{i}, U)$ not to be essential or forces $φ_{e_{i}} (G \cap {\overline{A}}_{i}, A)$ for some finite set $A \subseteq {\overline{B}}_{j}$ .
Proof.
Let $ψ (U)$ be the formula which holds if for every 2-partition $X_{i_{0}} \cup X_{i_{1}} = X$ , there is some $i \in {i_{0}, i_{1}}$ and some set $G_{i} \subseteq X_{i}$ such that $φ_{e_{i}} ((F \cap {\overline{A}}_{i}) \cup G_{i}, \tilde{A})$ holds for some $\tilde{A} \subseteq U$ . By compactness, the formula $ψ (U)$ is $Σ_{1}^{0, X \oplus Z}$ . We have two cases:
Case 1: $ψ (U)$ is essential. As $B_{j}$ is $X \oplus Z$ -hyperimmune, there exists some finite set $A \subseteq {\overline{B}}_{j}$ such that $ψ (A)$ holds. In particular, taking $X_{i} = X \cap {\overline{A}}_{i}$ for each $i \in {i_{0}, i_{1}}$ , there exists some $i \in {i_{0}, i_{1}}$ and some finite set $G_{i} \subseteq X_{i}$ such that $φ_{e_{i}} ((F \cap {\overline{A}}_{i}) \cup G_{i}, \tilde{A})$ holds for some $\tilde{A} \subseteq A$ . The condition $d = (F \cup G_{i}, X \ [0, max (G_{i})])$ is an extension forcing $φ_{e_{i}} (G \cap {\overline{A}}_{i}, A)$ for some finite set $A \subseteq {\overline{B}}_{j}$ .

Case 2: $ψ (U)$ is not essential, say with witness x. By compactness, the $Π_{1}^{0, X \oplus Z}$ class $C$ of sets $X_{i_{0}} \oplus X_{i_{1}}$ such that $X_{i_{0}} \cup X_{i_{1}} = X$ and for every $A > x$ , every $i \in {i_{0}, i_{1}}$ and every set $G_{i} \subseteq X_{i}$ , $φ_{e_{i}} ((F \cap {\overline{A}}_{i}) \cup G_{i}, A)$ does not hold is not empty. By preservation of hyperimmunity of ${WKL}_{0}$ , there exists some $X_{i_{0}} \oplus X_{i_{1}} \in C$ such that the B’s are $X_{i_{0}} \oplus X_{i_{1}} \oplus Z$ -hyperimmune. Let $i \in {i_{0}, i_{1}}$ be such that $X_{i}$ is infinite. The condition $d = (F, X_{i})$ is an extension of c forcing $φ_{e_{i}} (G \cap {\overline{A}}_{i}, U)$ not to be essential. □

Lemma 6.11.
For every condition c, and every indices $\vec{e}$ , there exists an extension d forcing $R_{\vec{e}}$ .
Proof.
Fix a condition c, and apply iteratively Lemma 6.10 to obtain an extension d such that for each $j < k$ , d forces $φ_{e_{i}} (G \cap {\overline{A}}_{i}, U)$ not to be essential or forces $φ_{e_{i}} (G \cap {\overline{A}}_{i}, A)$ for some finite set $A \subseteq {\overline{B}}_{j}$ for k different i’s. By the pigeonhole principle, there exists some $i ⩽ k$ such that d forces $φ_{e_{i}} (G \cap {\overline{A}}_{i}, U)$ not to be essential or forces $φ_{e_{i}} (G \cap {\overline{A}}_{i}, A)$ for some finite set $A \subseteq {\overline{B}}_{j}$ for each $j < k$ . Therefore, d forces $R_{\vec{e}}$ . □

6.3. Construction

Thanks to Lemma 6.11 and Lemma 6.9, define an infinite descending sequence of conditions $c_{0} = (\emptyset, ω) ⩾ c_{1} ⩾ \dots$ such that for each $s \in ω$ ,

$c_{s + 1}$ forces $R_{\vec{e}}$ if $s = ⟨ \vec{e} ⟩$ ,

$c_{s + 1}$ forces $Q_{s}$ ,

where

c_{s} = (F_{s}, X_{s})

. Let

G = ⋃_{s} F_{s}

. The sets

G \cap {\overline{A}}_{0}, \dots, G \cap {\overline{A}}_{k}

are all infinite and the B’s are

(G \cap {\overline{A}}_{i}) \oplus Z

-hyperimmune for some

i ⩽ k

. This finishes the proof.

Footnotes

Acknowledgements

The author is thankful to Wei Wang for useful comments and discussions. The author is funded by the John Templeton Foundation (‘Structure and Randomness in the Theory of Computation’ project). The opinions expressed in this publication are those of the author(s) and do not necessarily reflect the views of the John Templeton Foundation.

References

Bovykin and

Weiermann, The strength of infinitary Ramseyan principles can be accessed by their densities, Annals of Pure and Applied Logic (2005), to appear, p. 4.

P.A.

Cholak,

Giusto,

J.L.

Hirst and

C.G.

JockuschJr., Free sets and reverse mathematics, Reverse Mathematics 21 (2001), 104–119.

P.A.

Cholak,

C.G.

Jockusch and

T.A.

Slaman, On the strength of Ramsey’s theorem for pairs, Journal of Symbolic Logic 66(01) (2001), 1–55. doi:10.2307/2694910.

B.F.

Csima and

J.R.

Mileti, The strength of the rainbow Ramsey theorem, Journal of Symbolic Logic 74(04) (2009), 1310–1324. doi:10.2178/jsl/1254748693.

Flood and

Towsner, Separating principles below WKL₀ (2014), submitted, available at: http://arxiv.org/abs/1410.4068.

H.M.

Friedman, Some systems of second order arithmetic and their use, in: Proceedings of the International Congress of Mathematicians, Vancouver, Vol. 1, Canadian Mathematical Society, Montreal, Quebec, 1974, pp. 235–242.

H.M.

Friedman, Fom:53:free sets and reverse math and fom:54:recursion theory and dynamics, http://www.math.psu.edu/simpson/fom/, available at: https://www.cs.nyu.edu/pipermail/fom/.

D.R.

Hirschfeldt, Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles,

Chong,

Feng,

T.A.

Slaman,

W.H.

Woodin and

Yang, eds, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 28, World Scientific Publishing Co. Pte. Ltd, Hackensack, NJ, 2015.

D.R.

Hirschfeldt and

C.G.

Jockusch, On notions of computability theoretic reduction between

Π_{2}^{1}

principles, Journal of Mathematical Logic 16(1) (2016), 1650002. doi:10.1142/S0219061316500021.

10.

D.R.

Hirschfeldt and

R.A.

Shore, Combinatorial principles weaker than Ramsey’s theorem for pairs, Journal of Symbolic Logic 72(1) (2007), 171–206. doi:10.2178/jsl/1174668391.

11.

D.R.

Hirschfeldt,

R.A.

Shore and

T.A.

Slaman, The atomic model theorem and type omitting, Transactions of the American Mathematical Society 361(11) (2009), 5805–5837. doi:10.1090/S0002-9947-09-04847-8.

12.

C.G.

Jockusch and

R.I.

Soare,

Π_{1}^{0}

classes and degrees of theories, Transactions of the American Mathematical Society 173 (1972), 33–56.

13.

C.G.

Jockusch and

Stephan, A cohesive set which is not high, Mathematical Logic Quarterly 39(1) (1993), 515–530. doi:10.1002/malq.19930390153.

14.

Lerman,

Solomon and

Towsner, Separating principles below Ramsey’s theorem for pairs, Journal of Mathematical Logic 13(02) (2013), 1350007. doi:10.1142/S0219061313500074.

15.

Patey, Combinatorial weaknesses of Ramseyan principles (2015), in preparation, available at: http://ludovicpatey.com/media/research/combinatorial-weaknesses-draft.pdf.

16.

Patey, Degrees bounding principles and universal instances in reverse mathematics, Annals of Pure and Applied Logic 166(11) (2015), 1165–1185. doi:10.1016/j.apal.2015.07.003.

17.

Patey, Ramsey-type graph coloring and diagonal non-computability, Archive for Mathematical Logic 54(7–8) (2015), 899–914. doi:10.1007/s00153-015-0448-5.

18.

Patey, Somewhere over the rainbow Ramsey theorem for pairs (2015), submitted, available at: http://arxiv.org/abs/1501.07424.

19.

Patey, The strength of the tree theorem for pairs in reverse mathematics, Journal of Symbolic Logic (2015), to appear, available at: http://arxiv.org/abs/1505.01057.

20.

Patey, Controlling iterated jumps of solutions to combinatorial problems, Computability (2016), to appear, available at: http://arxiv.org/abs/1509.05340.

21.

Patey, The weakness of being cohesive, thin or free in reverse mathematics, Israel Journal of Mathematics (2016), to appear, available at: http://arxiv.org/abs/1502.03709.

22.

Patey, A note on “Separating principles below Ramsey’s theorem for pairs” (2013), unpublished, available at: http://ludovicpatey.com/media/research/note-em-sts.pdf.

23.

Rice, Thin set for pairs implies DNR, Notre Dame J. Formal Logic, to appear.

24.

Wang, The definability strength of combinatorial principles (2014), to appear, available at: http://arxiv.org/abs/1408.1465.

25.

Wang, Some logically weak Ramseyan theorems, Advances in Mathematics 261 (2014), 1–25. doi:10.1016/j.aim.2014.05.003.

Iterative forcing and hyperimmunity in reverse mathematics

Abstract

Keywords

1. Introduction

Definition 1.1 (Computable reducibility).

1 This paper is an extended version of a conference paper of the same name published in CiE 2015.

1.1. Notation

2. The iteration framework

3. Preservation of hyperimmunity

Definition 3.1 (Ascending descending sequence).

Definition 3.2 (Preservation of hyperimmunity).

Theorem 3.7. STS 2 does not admit preservation of hyperimmunity. 4. Basic preservations of hyperimmunity

Definition 5.1 (Erdős–Moser theorem).

Definition 6.1 (Preservation of k hyperimmunities).

Definition 6.2 (Thin set theorem).

Footnotes

Acknowledgements

References

¹
This paper is an extended version of a conference paper of the same name published in CiE 2015.

Theorem 3.7.
${STS}^{2}$ does not admit preservation of hyperimmunity.

4. Basic preservations of hyperimmunity