### arXiv:1501.07709v1 [math.LO] 30 Jan 2015

```Iterative forcing and hyperimmunity
in reverse mathematics
arXiv:1501.07709v1 [math.LO] 30 Jan 2015
Ludovic Patey
Laboratoire PPS, Université Paris Diderot, Paris, FRANCE
[email protected]
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.
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 RCA0 which is composed of the basic axioms of Peano arithmetic together with the ∆01 comprehension scheme and the Σ10 induction scheme. Thanks to the equivalence between ∆01 definable sets and computable sets, RCA0 can be thought as capturing “computational mathematics”. See [8] for a good introduction.
Many theorems are Π21 statements (∀X )(∃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 Π21 statements P and Q, proving an
implication Q → P over RCA0 consists in 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.
Definition 1 (Computable reducibility). Fix two Π21 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 ⊕ I computes a solution to I .
If the computable reduction between from P to Q can be formalized over RCA0 ,
then RCA0 ⊢ Q → P. However, P may not be computably reducible to Q while RCA0 ⊢
Q → 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 n colors (RT2n )
which implies RT2n+1 over RCA0 , but RT2n+1 ≤c RT2n for n ≥ 1 (see [20]).
In order to prove the non-implication between P and Q, one need 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˝
os-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 [21] 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. As well, 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 side, Wang [23] recently introduced the notion of preservation of definitions and made independent
proofs of 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 [20] for separating the free set theorem (FS)
from RT22 .
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 [23].
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, WKL0
is the weak König’s lemma, RRT22 the rainbow Ramsey theorem for pairs, Π10 G
the Π10 -genericity principle and STS2 the stable thin set theorem for pairs.
Theorem 2 (Wang [23]). Let Φ be the conjunction of COH, WKL0 , RRT22 , Π10 G,
and EM. Over RCA0 , Φ does not imply any of SADS and STS2 .
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 [20].
1.1 Notations
String, sequence. Fix an integer k ∈ ω. A string (over k) is an ordered tuple of
integers a0 , . . . , an−1 (such that ai < k for every i < n). The empty string is written ǫ.
A sequence (over k) is an infinite listing of integers a0 , a1 , . . . (such that ai < k for
every i ∈ ω). Given s ∈ ω, ks is the set of strings of length s over k. As well, k<ω is
the set of finite strings over k. Given a string σ ∈ k<ω , we denote by |σ| its length.
Given two strings σ, τ ∈ k<ω , σ is a prefix of τ (written σ
τ) if there exists
a string ρ ∈ k<ω such that σρ = τ. A binary string (resp. real) is a string (resp.
sequence) over 2. We may amalgamate a real with a set of integers by considering
that the real is its characteristic function.
Tree, path. A tree T ⊆ ω<ω is a set downward closed under prefix relation.
The tree T is finitely branching if every node σ ∈ T has finitely many immediate
successors. A binary tree is a tree T ⊆ 2<ω . A set P ⊆ ω is a path though T if
for every σ ≺ P, σ ∈ T . A string σ ∈ k<ω is a stem of a tree T if every τ ∈ T
is comparable with σ. Given a tree T and a string σ ∈ T , we denote by T [σ] the
subtree {τ ∈ T : τ σ ∨ τ σ}.
Sets. Given two sets X and Y , X ⊆∗ Y means that X is almost included into Y ,
X =∗ Y means X ⊆∗ Y ∧ Y ⊆∗ X and X ⊆fin Y means that X is a finite subset of Y .
Given some x ∈ ω, A > x denotes the formula (∀ y ∈ A)[ y > x].
2 The iteration framework
An ω-structure is a structure
= (ω, S, +, ·, <) where ω is the set of standard
integers, +, · and < are the standard operations over integers and S is a set of reals
such that
satisfies the axioms of RCA0 . Friedman [6] characterized the secondorder parts S of ω-structures as those forming a Turing ideal, that is, a set of reals
closed under Turing join and downward-closed under Turing reduction.
Fix two Π21 statements P and Q. The construction of an ω-model of P which
is not a model of Q consists in creating a Turing ideal
together with a fixed Qinstance I ∈ , such that every P-instance J ∈
has a solution in , whereas I
contains no solution in . In the first place, let’s 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:
e
: ΦXe ⊕I infinite → ΦXe ⊕I is not a solution to I
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 in constructing a Q-instance I which satisfies some fairness property. The
forcing notion I used in the construction of a solution to J is usually designed so
that
(i) There exists an I -computable set encoding (at least) every conditions in I
(ii) Given some forcing condition in I , one can uniformly find in a c.e. search a
finite set of candidate extensions such that one of them is in I (e.g. the notion
of split pair in [14], of finite cover for a tree forcing, ...).
The fairness property states the following:
For every condition in I , if for every x ∈ ω, there exists a finite Q-instance A > x
and a finite set of candidate extensions d0 , . . . , dm such that Φedi ⊕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 ∈ 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 J1 is X 0 ⊕ I -computable, but the set X 0 is not yet constructed. Hopefully, the fairness property requires a finite piece of oracle X 0 . Therefore we can
modify the fairness property which becomes
For every condition c0 ∈ I and every condition c1 ∈ c0 ⊕I , if for every x ∈ ω,
there exists a Q-instance A > x, a finite set of candidate extensions d0 , . . . , dm ∈ I
d ⊕d ⊕I
and d0,i , . . . , dni ,i ∈ di ⊕I for each i ≤ m such that Φe j,i i is not a solution to A for
each i ≤ m and j ≤ ni , then one of the A’s is a subinstance of I .
The property becoming overly complicated in the general case, Lerman, Solomon
0,I
and Towsner abstracted the notion of requirement and made it a Σ1 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
0,I
I
, if for every x ∈ ω, there
For every condition in I and every Σ1 predicate
exists a finite Q-instance A > x and a finite set of candidate extensions d0 , . . . , dm such
that I (A, di ) is satisfied for each i ≤ m, then one of the A’s is a subinstance of I .
In particular, by letting I (A, c) be the predicate “Φedi ⊕I is not a solution to A”,
the requirements 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 to modify the ground forcing. As well, 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,
0,I
0,I
given a Σ1 predicate I , the following formula is again Σ1 :
I
ϕ(U) = “there exists a finite set of candidate extensions d0 , . . . , dm of c such that
(U, di ) is satisfied for each i ≤ m”
We can therefore abstract the iteration forcing and ask the instance I to satisfy
the following property:
0,I
For every Σ1 predicate ϕ(U), if for every x ∈ ω, 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’s illustrate how this simplification works by reproving the separation of the
Erd˝
os-Moser theorem from the ascending descending sequence principle.
Definition 3 (Ascending descending sequence). A linear order is stable if it is
of order type ω + ω∗ . ADS is the statement “Every linear order admits an infinite
ascending or descending sequence”. SADS is the restriction of ADS to stable linear
orders.
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 stable linear order I with ω and ω∗ parts re0,I
spectively B0 and B1 , such that for every condition c and every Σ1 predicate I ,
if for every x ∈ ω, there exists a finite set A > x and a finite set of candidate extensions d0 , . . . , dm of c such that I (A, di ) is satisfied for each i ≤ m, then one of
the A’s will be included in B0 and another one will be included in B1 . In particular,
taking I (A, c) = Φc⊕I
∩ A = , no infinite solution to the constructed tournament
e
I -computes a solution to I . After abstraction, we obtain the following property:
0,I
For every Σ1 predicate ϕ(U), if for every x ∈ ω, there exists a finite set A > x
such that ϕ(A) is satisfied, one of the A’s is included in B0 and one of the A’s is included
in B1 .
Following the terminology of [14], we say that a formula ϕ(U) is essential if for
every x ∈ ω, there exists some finite set A > x such that ϕ(A) holds. This fairness
property coincide with the notion of hyperimmunity for B0 and B1 .
Definition 4 (Preservation of hyperimmunity).
1. Let D0 , D1 , . . . 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) ∩ B = for some i.
2. A Π21 statement P admits preservation of hyperimmunity if for each set Z, each
countable collection of Z-hyperimmune sets A0 , A1 , . . ., and each P-instance X ≤ T
Z there exists a solution Y to X such that the A’s are Y ⊕ Z-hyperimmune.
The following lemma establishes the link between the fairness property for SADS
and the notion of hyperimmunity.
0,Z
Lemma 5. Fix a set Z. A set B is Z-hyperimmune if and only if for every essential Σ1
predicate ϕ(U), ϕ(A) holds for some finite set A ⊆ B.
Hirschfeldt, Shore & Slaman constructed in [11, Theorem 4.1] a stable computable linear order 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.
A slight modification of the forcing in [14] gives preservation of hyperimmunity
of the Erd˝
os-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 7. Fix two Π21 statements P and Q. If P admits preservation of hyperimmunity and Q does not, then P does not imply Q over RCA0 .
Before starting an analysis of preservations of hyperimmunity for basic statements, we state another negative preservation result which enables to reprove that
the Erd˝
os-Moser theorem does not imply the stable thin set theorem for pairs [15].
Definition 8 (Thin set theorem). Let k ∈ ω and f : [ω]k → ω. A set A is f -thin
if f ([A]n ) = ω, that is, if the set A “avoids” at least one color. TSk is the statement
“every function f : [ω]k → ω has an infinite f -thin set”. STSk is the restriction of
TSk to stable functions.
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 [24], Rice [22] and the author [18,20]. The author constructed
in [17] an infinite computable stable function f : [ω]2 → ω such that the sets Bi =
{n ∈ ω : lims f (n, s) = 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 9. STS2 does not admit preservation of hyperimmunity.
4 Basic preservation of hyperimmunitys
When defining a notion, it is usually convenient to see how they relate with typical
sets. There are two kinds of typicalities: genericity and randomness. Both notions
Theorem 10. Fix some set Z and a countable collection of Z-hyperimmune sets B0 , B1 , . . .
1. If G is sufficiently Cohen generic relative to Z, the B’s are G ⊕ Z-hyperimmune.
2. If R is sufficiently random relative to Z, the B’s are R ⊕ Z-hyperimmune.
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), Π10 -genericity (Π10 G) and the rainbow Ramsey theorem for
pairs (RRT22 ) are direct consequences of genericity and randomness [11,4]. We can
deduce from Theorem 10 that they all admit preservation of hyperimmunity.
Cohesiveness is a very useful statement in the analysis of Ramsey-type theorems
as it enables to transform an arbitrary instance into a stable one [3]. A set C is
cohesive for a sequence of sets R0 , R1 , . . . if C ⊆∗ R i or C ⊆∗ R i for each i.
Theorem 11. 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.
0,Z
Lemma 12. For every set Z, every Z-computable Mathias condition (F, X ), every Σ1
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 ⊆ B.
Proof. Define
ψ(U) = (∃G ⊇ F )[G ⊆ F ∪ X ∧ ϕ(G, U)]
0,Z
The formula ψ(U) is Σ1 . By hyperimmunity of B, either ψ(U) is not essential,
or ψ(A) holds for some finite set A ⊆ B. In the first case, the condition (F, X )
already satisfies the desired property. In the second case, let A ⊆fin 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, ma x(E)]. The condition (E, Y ) is a valid
extension.
⊔
⊓
The weak König’s lemma (WKL0 ) states that every infinite, binary tree admits
an infinite path.
Theorem 13. WKL0 admits preservation of hyperimmunity.
Wei Wang [personal communication] observed that WKL0 preserves hyperimmunity in a much stronger sense than COH, since cohesive sets are of hyperimmune degree [12], whereas by the hyperimmune-free basis theorem [13], WKL0
can preserve hyperimmunities of every hyperimmune set simultaneously and not
only countably many.
5 The Erd˝
os-Moser theorem and preservation of hyperimmunity
The Erd˝
os-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 14 (Erd˝
os-Moser theorem). A tournament T is an irreflexive binary relation such that for all x, y ∈ ω with x = 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˝
os-Moser theorem has been introduced in reverse mathematics by Bovykin
& Weiermann [1] and then studied by Lerman, Solomon & Towsner [14] and the
author [19,18,16]. In this section, we give a simple proof of the following theorem.
Theorem 15. EM admits preservation of hyperimmunity.
The proof of Theorem 15 exploits the modularity of the framework by using
preservation of hyperimmunity of WKL0 . Together with previous preservations results, this theorem is sufficient to reprove Theorem 2. We must first introduce some
terminology.
Definition 16 (Minimal interval). Let T be an infinite tournament and a, b ∈ T be
such that T (a, b) holds. The interval (a, b) is the set of all x ∈ T such that T (a, x)
and T (x, b) hold. Let F ⊆ T be a finite transitive subtournament of T . For a, b ∈ F
such that T (a, b) holds, we say that (a, b) is a minimal interval of F if there is no
c ∈ F ∩ (a, b), i.e. no c ∈ F such that T (a, c) and T (c, b) both hold.
Definition 17. An Erd˝
os Moser condition (EM condition) for an infinite tournament T is a Mathias condition (F, X ) where
(a) F ∪ {x} is T -transitive for each x ∈ X
(b) 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 [19].
Fix a set Z and some countable collection of Z-hyperimmune sets B0 , B1 , . . . Our
forcing notion is the partial order of Erd˝
os Moser conditions (F, X ) such that the B’s
are X ⊕ Z-hyperimmune. Our initial condition is ( , ω). By Lemma 5.9 in [19],
EM conditions are extensible, so we can force the transitive subtournament to be
infinite. Therefore it suffices to prove the following lemma to deduce Theorem 15.
0,Z
Lemma 18. Fix a condition (F, X ), some X ⊕ Z-hyperimmune set Bi and some Σ1
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 ⊆ Bi .
Proof. Let ψ(U) be the formula “For every partition X 0 ∪ X 1 = X , there exists
˜
some j < 2, a T -transitive set G ⊆ X j and a set A˜ ⊆ U such that ϕ(F ∪ G, A)
0,X ⊕Z
holds.” By compactness, ψ(U) is a Σ1
formula. By X ⊕ Z-hyperimmunity of Bi ,
we have two cases:
– Case 1: ψ(A) holds for some finite set A ⊆ Bi . By compactness, there exists a
finite set H ⊂ X such that for every partition H0 ∪ H1 = H, there exists some j <
˜ holds. Given
2, a T -transitive set G ⊆ H j and a set A˜ ⊆ A such that ϕ(F ∪ G, A)
two sets U and V , we denote by U → T V the formula (∀x ∈ U)(∀ y ∈ V )T (x, y).
Each element y ∈ X induces a partition H0 ∪ H1 = H such that H0 → T { y} → T
H1 . There exists finitely many such partitions, so by the infinite pigeonhole
principle, there exists an X -computable infinite set Y ⊂ X and a partition H0 ∪
H1 = H such that H0 → T Y → T H1 . Let j < 2 and G ⊆ H j be the T -transitive
˜ holds for some A˜ ⊆ A ⊆ Bi . By Lemma 5.9 in [19],
set such that ϕ(F ∪ G, A)
(F ∪ G, Y ) is a valid extension.
0,X ⊕Z
– Case 2: ψ(U) is not essential with some witness x. Then the Π1
class
of sets X 0 ⊕ X 1 such that X 0 ∪ X 1 = X and for every j < 2, every T -transitive
˜ does not hold
set G ⊆ X j and every finite set A˜ > x, the formula ϕ(F ∪ G, A)
is not empty. By preservation of hyperimmunity of WKL0 , there exists some
partition X 0 ⊕ X 1 ∈
such that the B’s are X 0 ⊕ X 1 ⊕ 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 STS2 witness their
failure of preservation of hyperimmunity. In the case of SADS, we construct two
hyperimmune sets whereas in the case of STS2 , a countable collection of hyperimmune sets is used. This difference can be exploited to obtain further separation
results.
Definition 19 (Preservation of n hyperimmunities). A Π21 statement P admits
preservation of n hyperimmunities if for each set Z, each Z-hyperimmune sets A0 , . . . ,
An−1 , and each P-instance X ≤ T Z there exists a solution Y to X such that the A’s are
Y ⊕ Z-hyperimmune.
Theorem 6 shows that SADS does not admit preservation of 2 hyperimmunities.
On the other side, we shall see that STS2 admits preservation of n hyperimmunities
for every n ∈ ω. Consider the following variants of the thin set theorem.
Definition 20 (Thin set theorem). Given a function f : [ω]k → n, an infinite set H
is f -thin if | f ([H]k )| ≤ n − 1 (i.e. f avoids one color over H). For every k ≥ 1
and n ≥ 2, TSkn is the statement “Every function f : [ω]k → n has an infinite f -thin
set”. STSkn is the restriction of TSkn to stable colorings.
Note that TS22 is Ramsey’s theorem for pairs. The following theorem is sufficient
to separate TS2 from Ramsey’s theorem for pairs as TS2 ≤c TS2n for every n ≥ 2.
The proof of preservation is rather technical and is therefore proven in appendix.
Theorem 21. For every n ≥ 1, TS2n+1 admits preservation of n but not n + 1 hyperimmunities.
In the case n = 1, noticing that the arithmetical comprehension scheme (ACA0 )
does not preserve 1 hyperimmunities as witnessed by taking any ∆02 hyperimmune set, we re-obtain the separation of Ramsey’s theorem for pairs from ACA0 .
Hirschfeldt & Jockusch [9] asked whether TS2n+1 implies TS2n over RCA0 . The author answered negatively in [20]. Preservation of n hyperimmunities gives the same
separation.
Theorem 22 (Patey [20]). For every n ≥ 2, let Φ be the conjunction of COH, WKL0 ,
RRT22 , Π10 G, EM, TS2n+1 . Over RCA0 , Φ does not imply any of SADS and STS2n .
Acknowledgements. The author is thankful to Wei Wang for useful comments and
discussions.
References
1. Andrey Bovykin and Andreas Weiermann. The strength of infinitary ramseyan principles
can be accessed by their densities. Annals of Pure and Applied Logic, page 4, 2005.
2. Peter A. Cholak, Mariagnese Giusto, Jeffry L. Hirst, and Carl G. Jockusch Jr. Free sets
and reverse mathematics. Reverse mathematics, 21:104–119, 2001.
3. Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman. On the strength of Ramsey’s
theorem for pairs. Journal of Symbolic Logic, pages 1–55, 2001.
4. Barbara F Csima and Joseph R Mileti. The strength of the rainbow Ramsey theorem.
Journal of Symbolic Logic, 74(04):1310–1324, 2009.
5. Stephen Flood and Henry Towsner. Separating principles below WKL0 , 2014. in preparation.
6. Harvey Friedman. Some systems of second order arithmetic and their use. In Proceedings
of the International Congress of Mathematicians, Vancouver, volume 1, pages 235–242,
1974.
7. Harvey M. Friedman. Fom:53:free sets and reverse math and fom:54:recursion theory
and dynamics. Available at http://www.math.psu.edu/simpson/fom/.
8. Denis R Hirschfeldt. Slicing the truth. preprint, 2013.
9. Denis R Hirschfeldt and Carl G Jockusch Jr. On notions of computability theoretic reduction between Π21 principles. To appear.
10. Denis R. Hirschfeldt and Richard A. Shore. Combinatorial principles weaker than Ramsey’s theorem for pairs. Journal of Symbolic Logic, 72(1):171–206, 2007.
11. Denis R. Hirschfeldt, Richard A. Shore, and Theodore A. Slaman. The atomic
model theorem and type omitting. Transactions of the American Mathematical Society,
361(11):5805–5837, 2009.
12. Carl Jockusch and Frank Stephan. A cohesive set which is not high. Mathematical Logic
Quarterly, 39(1):515–530, 1993.
13. Carl G Jockusch and Robert I Soare. Π10 classes and degrees of theories. Transactions of
the American Mathematical Society, 173:33–56, 1972.
14. Manuel Lerman, Reed Solomon, and Henry Towsner. Separating principles below Ramsey’s theorem for pairs. Journal of Mathematical Logic, 13(02):1350007, 2013.
15. Ludovic Patey. A note on "Separating principles below Ramsey’s theorem for pairs".
Unpublished, 2013.
16. Ludovic Patey. Controlling iterated jumps of solutions to combinatorial problems. In
preparation, 2014.
17. Ludovic Patey. Somewhere over the rainbow Ramsey theorem for pairs. In preparation,
2014.
18. Ludovic Patey. Combinatorial weaknesses of ramseyan principles. In preparation, 2015.
19. Ludovic Patey. Degrees bounding principles and universal instances in reverse mathematics. Submitted, 2015.
20. Ludovic Patey. Dissent within cohesiveness in reverse mathematics. In preparation,
2015.
21. Ludovic Patey. Ramsey-type graph coloring and diagonal non-computability. Submitted,
2015.
22. Brian Rice. Thin set for pairs implies DNR. Notre Dame J. Formal Logic. To appear.
23. Wei Wang. The definability strength of combinatorial principles, 2014.
24. Wei Wang. Some logically weak ramseyan theorems. Advances in Mathematics, 261:1–
25, 2014.
A
Preservation of hyperimmunity
Proof (Lemma 5). Let D0 , D1 , . . . be a computable list of all finite sets.
0,Z
– Fix some set Z and some Z-hyperimmune set B. For every essential Σ1 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. weak array, so by Zhyperimmunity, D f (i) ∩ B = for some i, hence D f (i) ⊆ B and ϕ(D f (i) ) holds.
– Fix some set Z and some set B such that the fairness property of Lemma 5
0,Z
holds. For every Z-c.e. weak array {D f (i) }i≥0 , define the Σ1 formula ϕ(U) =
(∃i)[U = D f (i) ]. The formula ϕ(U) is essential, so there exists some finite
set A ⊆ B such that ϕ(A) holds. In particular, there exists some i such that D f (i) ⊆
B.
⊔
⊓
Proof (Lemma 7). Fix a set X 0 , a countable collection of X 0 -hyperimmune sets B0 , B1 , . . .
and an X 0 -computable Q-instance J such that for every solution Y to J , one of
the B’s is not Y ⊕ X 0 -hyperimmune. By preservation of hyperimmunity of P and
carefully choosing a sequence of P-instances I0 , I1 , . . ., we can define an infinite
sequence of sets X 1 , X 2 , . . . such that for each n ∈ ω
(a) X n+1 is a solution to the P-instance I nX 0 ⊕...⊕X n
(b) The B’s are X 0 ⊕ . . . ⊕ X n -hyperimmune
(c) For every X 0 ⊕ . . . ⊕ X n -computable P-instance I , there exists some m such
that I = I mX 0 ⊕...⊕X m .
Let
be the ω-structure whose second order part is the Turing ideal
= {Y : (∃n)[Y ≤ T X 0 ⊕ . . . ⊕ X n ]}
In particular, the Q-instance J is in , but he B’s are Y -hyperimmune for every Y ∈ , so J has no solution Y ∈
and
|= Q. By construction of , every
P-instance I ∈ has a solution X n ∈ , so by Friedman [6],
|= RCA0 ∧ P.
⊔
⊓
B
Basic preservation proofs
The proofs in this appendix are inspired by Wang’s work in [23].
0,Z
Proof (Item 1 of Theorem 10). It suffices to prove that for every Σ1 formula ϕ(G, U)
and every i ∈ ω, the set of conditions σ forcing ϕ(G, U) not to be essential or such
that ϕ(σ, A) holds for some finite set A ⊂ Bi is dense. Fix any string σ ∈ 2<ω . Define
ψ(U) = (∃τ
0,Z
σ)ϕ(τ, U)
The formula ψ(U) is Σ1 , so by Z-hyperimmunity of Bi , either ψ(U) is not essential, or ψ(A) holds for some finite set A ⊆ Bi . If ψ(U) is not essential with witness
x ∈ ω, then σ forces ϕ(G, U) not to be essential with the same witness. If ψ(U) is
essential, then there exists some finite set A ⊂ Bi such that ψ(A) holds. Unfolding
the definition of ψ(A), there exists some τ σ such that ϕ(τ, A) holds. The condi⊔
⊓
tion τ is an extension such that ϕ(τ, A) holds for some A ⊂ Bi .
0,Z
Proof (Item 2 of Theorem 10). It suffices to prove that for every Σ1
and every i ∈ ω, the following class is Lebesgue null.
formula ϕ(G, U)
= {X : [ϕ(X , U) is essential ] ∧ (∀A ⊆fin ω)ϕ(X , A) → A ⊆ Bi }
Suppose it is not the case. There exists σ ∈ 2<ω such that
µ(X ∈
: σ ≺ X ) > 2−|σ|−1
Define
˜ > 2−|σ|−1 ]
ψ(U) = [µ(X : (∃A˜ ⊆ U)ϕ(X , A))
0,Z
The formula ψ(U) is Σ1 and by compactness, ψ(U) is essential. By Z-hyperimmunity
of Bi , there exists some finite set A ⊆ Bi such that ψ(A) holds. For every set A such
˜ holds.
that ψ(A) holds, there exists some X ∈
and some A˜ ⊆ A such that ϕ(X , A)
⊔
⊓
By definition of X ∈ , A˜ ⊆ Bi and therefore A ⊆ Bi . Contradiction.
Proof (Theorem 13). Fix some set Z, some countable collection of Z-hyperimmune
sets B0 , B1 , . . . and some Z-computable tree T ⊆ 2<ω . Our forcing conditions are (σ, R)
where σ is a stem of the infinite, Z-computable tree R ⊆ T . A condition (τ, S) extends (σ, R) if σ τ and S ⊆ R. The result is a direct consequence of the following
lemma.
0,Z
Lemma 23. For every condition c = (σ, R), every Σ1 formula ϕ(G, U) and every i ∈
ω, there exists an extension d = (τ, S) such that ϕ(P, U) is not essential for every
path P ∈ [S], or ϕ(τ, A) holds for some A ⊆ Bi .
Proof. Define
˜
ψ(U) = (∃s)(∀τ ∈ R ∩ 2s )(∃A˜ ⊆fin U)ϕ(τ, A)
0,Z
The formula ψ(U) is Σ1
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:
S = {τ ∈ R : (∀A > x)¬ϕ(τ, A)}
The condition d = (σ, S) is an extension such that ϕ(P, U) is not essential for
every P ∈ [S].
– Case 2: ψ(U) is essential. By Z-hyperimmunity of Bi , there exists some finite
set A ⊆ Bi such that ψ(A) holds. Unfolding the definition of ψ(A), there exists
˜ holds for some A˜ ⊆ A ⊆ Bi . The
some τ ∈ R such that R[τ] is infinite and ϕ(τ, A)
[τ]
˜ holds for some finite
condition d = (τ, R ) is an extension such that ϕ(τ, A)
˜
set A ⊆ Bi .
Using Lemma 23, define an infinite descending sequence of conditions c0 =
(ε, T ) ≥ c1 ≥ . . . such that for each s ∈ ω
(i) |σs | ≥ s
(ii) ϕ(P, U) is not essential for every path P ∈ [Rs+1 ], or ϕ(σs+1 , A) holds for some
finite set A ⊆ Bi if s = ϕ, i
where cs = (σs , Rs ).
⊔
⊓
C
Thin set for pairs and preservation of hyperimmunity
All the proofs in this section are very similar to [20]. We reprove everything in the
context of preservation of hyperimmunities for the sake of completeness.
Definition 24 (Strong preservation of n hyperimmunities). A Π21 statement P
admits strong preservation of n hyperimmunities if for each set Z, each Z-hyperimmune
sets B0 , . . . , Bn−1 and each (arbitrary) P-instance X , there exists a solution Y to X such
that the B’s are Y ⊕ Z-hyperimmune.
The following lemma has been proven by the author in its full generality in [18].
We reprove it in the context of preservation of n hyperimmunities.
Lemma 25. For every k, n ≥ 1 and m ≥ 2, if TSkm admits strong preservation of n
hyperimmunities, then TSkm+1 admits preservation of n hyperimmunities.
Proof. Fix any set Z, some Z-hyperimmune sets B0 , . . . , Bn−1 and any Z-computable
coloring f : [ω]k+1 → m. Consider the uniformly Z-computable sequence of sets Rσ,i
defined for each σ ∈ [ω]k and i < m by
Rσ,i = {s ∈ ω : f (σ, s) = i}
As COH admits preservation of n hyperimmunities, there exists some R-cohesive
set G such that the B’s are G ⊕ Z-hyperimmune. The cohesive set induces a (G ⊕ Z)′ computable coloring f˜ : [ω]k → m defined by:
(∀σ ∈ [ω]k ) f˜(σ) = lim f (σ, s)
s∈G
As TSkm admits strong preservation of n hyperimmunities, there exists an infinite
f˜-thin set H such that the B’s are H ⊕ G ⊕ Z-hyperimmune. H ⊕ G ⊕ Z computes an
infinite f -thin set.
Thanks to Lemma 25, it suffices to prove the following theorem to deduce Theorem 21.
Theorem 26. For every n ≥ 1, TS1n+1 admits preservation of n hyperimmunities.
The remainder of this section is devoted to the proof of Theorem 26. Fix some
set Z, some Z-hyperimmune sets B0 , . . . , Bn−1 and some (n + 1)-partition A0 ∪ . . . ∪
An = ω. We will construct an infinite set G such that G ∩ Ai is infinite for each i ≤ n
and the B’s are (G ∩ Ai ) ⊕ Z-hyperimmune for some i ≤ n. Our forcing conditions
are Mathias conditions (F, X ) such that the B’s are X ⊕ Z-hyperimmune.
C.1 Forcing limitlessness
We want to satisfy the following scheme of requirements to ensure that G ∩ Ai is
infinite for each i ≤ n.
p
: (∃m0 , . . . , mn > p)[m0 ∈ G ∩ A0 ∧ . . . ∧ mn ∈ G ∩ An ]
We say that an (n+1)-partition A0 ∪. . .∪An−1 = ω is non-trivial if there exists no
infinite f -thin set H such that the B’s are H ⊕ Z-hyperimmune. A condition (F, X )
forces p if there exists m0 , . . . , mn > p such that mi ∈ F ∩ Ai for each i ≤ n.
Therefore, if G satisfies c and c forces p , then G satisfies the requirement p . We
now prove that the set of conditions forcing p is dense for each p ∈ ω. Therefore,
every sufficiently generic filter will induce n + 1 infinite sets G ∩ A0 , . . . , G ∩ An .
Lemma 27. For every condition c and every p ∈ ω, there is a condition d extending c
such that d forces p .
Proof. Fix some p ∈ ω. It is sufficient to show that for a condition c = (F, X ) and
some i ≤ n, there exists an extension d0 = (H, Y ) and some integer mi > p that mi ∈
H ∩ Ai . By iterating the process for each i ≤ n, we obtain the desired extension d.
Suppose for the sake of contradiction that X ∩ Ai is finite. Then one can X -compute
an infinite set H thin for the A’s with witness j for any j = i, contradicting nontriviality of f . Therefore, there exists an mi ∈ X ∩ Ai , mi > p. The condition d0 =
⊔
⊓
(F ∪ {mi }, X [0, mi ]) is the desired extension.
C.2 Forcing non-preservation
0,Z
Fix an enumeration ϕ0 (G, U), ϕ1 (G, U), . . . of all Σ1 formulas. The second scheme
of requirements consists in ensuring that the sets B0 , . . . , Bn−1 are all G∩Ai -hyperimmune
for some i ≤ n. The requirements are of the following form for each e.
e
A0 ,B j
e0
:
j<n
where
Ai ,B j
e
An ,B j
en
∨ ... ∨
j<n
: ϕe (G ∩ Ai , U) essential ⇒ (∃A ⊆fin B j )ϕe (G ∩ Ai , A)
A condition forces
requirement e .
e
if every set G satisfying this condition also satisfies the
Lemma 28. For every condition c = (F, X ), every i0 < i1 ≤ n, every j < n and every
indices e, there exists an extension d such that for some i ∈ {i0 , i1 }, d forces ϕei (G ∩
Ai , U) not to be essential or forces ϕei (G ∩ Ai , A) for some finite set A ⊆ B j .
Proof. Let ψ(U) be the formula which holds if for every 2-partition X i0 ∪ X i1 = X ,
˜ holds
there is some i ∈ {i0 , i1 } and some set Gi ⊆ X i such that ϕei ((F ∩ Ai ) ∪ Gi , A)
0,X
⊕Z
for some A˜ ⊆ U. By compactness, the formula ψ(U) is Σ1
. We have two cases:
– Case 1: ψ(U) is essential. As B j is X ⊕ Z-hyperimmune, there exists some finite set A ⊆ B j such that ψ(A) holds. In particular, taking X i = X ∩ Ai for
each i ∈ {i0 , i1 }, there exists some i ∈ {i0 , i1 } and some finite set Gi ⊆ X i such
˜ holds for some A˜ ⊆ A. The condition d = (F ∪ Gi , X
that ϕei ((F ∩ Ai ) ∪ Gi , A)
[0, ma x(Gi )]) is an extension forcing ϕei (G ∩ Ai , A) for some finite set A ⊆ B j
0,X ⊕Z
– Case 2: ψ(U) is not essential, say with witness x. By compactness, the Π1
class
of sets X i0 ⊕ X i1 such that X i0 ∪ X i1 = X and for every A > x, every i ∈
{i0 , i1 } and every set Gi ⊆ X i , ϕei ((F ∩ Ai ) ∪ Gi , A) does not hold is not empty. By
preservation of hyperimmunity of WKL0 , there exists some X i0 ⊕ X i1 ∈
such
that the B’s are X i0 ⊕ X i1 ⊕ Z-hyperimmune. Let i ∈ {i0 , i1 } be such that X i is
infinite. The condition d = (F, X i ) is an extension of c forcing ϕei (G ∩ Ai , U) not
to be essential.
⊔
⊓
Lemma 29. For every condition c, and every indices e, there exists an extension d
forcing e .
Proof. Fix a condition c, and apply iteratively Lemma 28 to obtain an extension d
such that for each j < n, d forces ϕei (G ∩ Ai , U) not to be essential or forces ϕei (G ∩
Ai , A) for some finite set A ⊆ B j for n different i’s. By the pigeonhole principle, there
exists some i ≤ n such that d forces ϕei (G ∩ Ai , U) not to be essential or forces
⊔
ϕei (G ∩ Ai , A) for some finite set A ⊆ B j for each j < n. Therefore, d forces e . ⊓
C.3 Construction
Thanks to Lemma 29 and Lemma 27, define an infinite descending sequence of
conditions c0 = ( , ω) ≥ c1 ≥ . . . such that for each s ∈ ω,
(a) cs+1 forces
(b) cs+1 forces
e
if s = 〈e〉
s
where cs = (Fs , X s ). Let G = s Fs . The sets G ∩ A0 , . . . , G ∩ An are all infinite and
the B’s are (G ∩ Ai ) ⊕ Z-hyperimune for some i ≤ n. This finishes the proof.
```