SOMEWHERE OVER THE RAINBOW RAMSEY THEOREM FOR PAIRS LUDOVIC PATEY Abstract. TherainbowRamseytheoremstatesthateverycoloringoftupleswhereeachcolor isusedaboundednumberoftimeshasaninfinitesubdomainonwhichnocolorappearstwice. The restriction of the statement to colorings over pairs (RRT2) admits several characteriza- 2 tions: it is equivalent to finding an infinite subset of a 2-random, to diagonalizing against Turing machines with the halting set as oracle... In this paper we study principles that are closely related to the rainbow Ramsey theorem, the Erdo˝s Moser theorem and the thin set theoremwithintheframeworkofreversemathematics. Weprovethatthethinsettheoremfor pairs implies RRT2, and that the stable thin set theorem for pairs implies the atomic model 2 5 theorem over RCA . We define different notions of stability for the rainbow Ramsey theorem 0 1 and establish characterizations in terms of Ramsey-type Ko¨nig’s lemma, relativized Schnorr 0 randomness or diagonalization of ∆0 functions. 2 2 n a J 1. Introduction 0 3 Reverse mathematics is a vast mathematical program whose goal is to find the provability content of theorems. Empirically, many “ordinary” (i.e. non set-theoretic) theorems happen to ] O require very weak axioms, and furthermore to be equivalent to one of five main subsystems of L second order arithmetic. However, among theorems studied in reverse mathematics, Ramseyan . principles are known to contradict this observation. Their computational complexities are diffi- h t cult to tackle and the introduction to a new Ramseyan principle often leads to a new subsystem a of second order arithmetics. m The Ramsey theorem for pairs (RT2) states that for every coloring of pairs into two colors, [ 2 there exists an infinite restriction of the domain on which the coloring is monochromatic. This 2 principle benefited of a particular attention from the scientific community [6, 8, 9, 26, 33, 45]. v The questions of its relations with WKL – K¨onig’s lemma restricted to binary trees – and SRT2 4 0 2 2 – the restriction of RT2 to stable colorings – have been opened for decades and went recently 2 4 solved. Liu [34] proved that RT2 does not imply for WKL over RCA , and Chong et Slaman [9] 7 2 0 0 proved that SRT2 does not imply RT2, using non-standard models. It remains open whether 0 2 2 . every ω-model of SRT2 is also model of RT2. 1 2 2 0 5 1.1. The rainbow Ramsey theorem 1 : Among the consequences of Ramsey’s theorem, the rainbow Ramsey theorem intuitively v i states the existence of an infinite injective restriction of any function which is already close to X being injective. We now provide its formal definition. r a Definition 1.1 (Rainbow Ramsey theorem). Fix n,k ∈ N. A coloring function f : [N]n → N is k-bounded if for every y ∈ N, (cid:12)(cid:12)f−1(y)(cid:12)(cid:12) ≤ k. A set R is a rainbow for f (or an f-rainbow) if f is injective over [R]n. RRTn is the statement “Every k-bounded function f : [N]n → N has an k infinite f-rainbow”. RRT is the statement: (∀n)(∀k)RRTn. k A proof of the rainbow Ramsey theorem is due to Galvin who noticed that it follows easily from Ramsey’s theorem. Hence every computable 2-bounded coloring function f over n-tuples has an infinite Π0 rainbow. Csima and Mileti proved in [13] that every 2-random bounds an ω- n model of RRT2 and deduced that RRT2 implies neither SADS nor WKL over ω-models. Conidis 2 2 0 & Slaman adapted in [11] the argument from Cisma and Mileti to obtain RCA (cid:96) 2-RAN → 0 RRT2. 2 Received by the editors February 2, 2015. 1 2 LUDOVICPATEY Wang proved in [47, 48] that RCA +RRT3 (cid:48) ACA and RRT2 is Π1-conservative over 0 2 0 2 1 RCA +BΣ0. He refined his result in [49], proving that RRT3 implies neither WKL nor RRT4 0 2 2 0 2 over ω-models. CsimaandMiletiprovedin[13]thatforeveryn ∈ N,thereexistsacomputable2-boundedcol- oringover[N]n withnoinfiniteΣ0 rainbow. Conidis&Slamanprovedin[11]thatRCA +RRT2 n 0 2 proves CΣ0. Later, Slaman proved in [46] that RRT2 – in fact even 2-RAN – does not imply 2 2 BΣ0 over RCA . 2 0 In a computational perspective, Miller [36] proved that RRT2 is equivalent to DNR[∅’] where 2 DNR[∅(n)] is the statement “for every set X, there exists a function f such that f(e) (cid:54)= ΦX(n)(e) e foreverye”. DNR[∅’]isknowntobeequivalenttotheabilitytoescapefiniteΣ0 setsofuniformly 2 bounded size, to diagonalize against partial ∅(cid:48)-computable functions, to find an infinite subset of a 2-random, or an infinite subset of a path in a ∆0 tree of positive measure. 2 Having so many simple characterizations speak in favor of the naturality of the rainbow Ramsey theorem for pairs. Its characterizations are formally stated in sections 5.2 and 5.3 and are adapted to obtain characterizations of stable versions of the rainbow Ramsey theorem. 1.2. Somewhere over RRT2 2 There exist several proofs of the rainbow Ramsey theorem, partly due to the variety of its characterizations. Among them are statements about graph theory and thin set theorem. The Erd˝os-Moser theorem (EM) states that every infinite tournament (see below) has an infinite transitive subtournament. It can be seen as the ability to find an infinite subdomain of an arbitrary 2-coloring of pairs on which the coloring behaves like a linear order. It is why EM, together with the ascending descending sequence principle (ADS), proves RT2 over RCA . 2 0 Definition 1.2 (Erd˝oss-Moser theorem). A tournament T on a domain D ⊆ N is an irreflexive binary relation on D such that for all x,y ∈ D with x (cid:54)= 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. A tournament T is stable if (∀x ∈ D)[(∀∞s)T(x,s)∨(∀∞s)T(s,x)]. EM is the statement “Every infinite tournament T has an infinite transitive subtournament.” SEM is the restriction of EM to stable tournaments. BovykinandWeiermannprovedin[6]thatEM+ADSisequivalenttoRT2 overRCA ,andthe 2 0 same equivalence holds between the stable versions. Lerman & al. [32] proved over RCA +BΣ0 0 2 that EM implies OPT and that there is an ω-model of EM not model of SRT2. Kreuzer proved 2 in [31] that SEM implies BΣ0 over RCA . Bienvenu et al. [4] and Flood & Towsner [18] proved 2 0 independently that RCA (cid:96) SEM → RWKL, hence there is an ω-model of RRT2 not model 0 2 of SEM. We prove that that EM implies RRT2 over RCA using both a direct proof and the 2 0 equivalence between RRT2 and DNR[∅’]. We also prove that RCA (cid:96) EM → [STS(2)∨COH]. 2 0 Thethin set theorem (TS)statesthateverycoloringoftupleshasarestrictionoveraninfinite domain on which it avoids a color. It is often studied together with the free set theorem FS. Its study has been initiated by Friedman in the FOM mailing list [19, 20]. Definition 1.3 (Freesettheorem). Letk ∈ Nandf : [N]k → N. AsetAisfree for f (orf-free) if for every x < ··· < x ∈ A, if f(x ,...,x ) ∈ A then f(x ,...,x ) ∈ {x ,...,x }. FS(k) 1 k 1 k 1 k 1 k is the statement “every function f : [N]k → N has an infinite set free for f”. A function f : [N]k+1 → N is stable if for every σ ∈ [N]k, lim f(σ,s) exists. SFS(k) is the restriction of FS(k) s to stable functions. FS is the statement (∀k)FS(k) Definition 1.4 (Thin set theorem). Let k ∈ N and f : [N]k → N. A set A is thin for f (or f- thin)iff([A]n) (cid:54)= N. TS(k)isthestatement“everyfunctionf : [N]k → Nhasaninfinitesetthin for f”. STS(k) is the restriction of TS(k) to stable functions. TS is the statement (∀k)TS(k). Cholak & al. studied extensively free set and thin set principles in [7], proving that FS(1) holds in RCA while FS(2) does not, FS(k +1) (resp. TS(k +1)) implies FS(k) (resp. TS(k)) 0 over RCA . They proved that FS implies TS over RCA , and the more finely-grained result that 0 0 FS(k) implies TS(k) and SFS(k) implies STS(k) over RCA for every k. 0 SOMEWHERE OVER THE RAINBOW RAMSEY THEOREM FOR PAIRS 3 Some of the results where already stated by Friedman [19] without proof, notably there is an ω-model of WKL which is not a model of TS(2), and ACA does not imply TS. Cholak & al. 0 0 also proved that RCA +RTk implies FS(k) for every k hence ACA proves FS(k). Wang showed 0 2 0 in [50] that neither FS nor TS implies ACA . He proved that RCA (cid:96) FS(k) → RRTk. Rice [43] 0 0 2 proved that STS(2) implies DNR over RCA . 0 We prove, using the equivalence between RRT2 and DNR[∅’], that RCA (cid:96) TS(2) → RRT2 2 0 2 and more generally RCA (cid:96) TS(k +1) → DNR[∅(k)]. We also prove that STS(2) implies AMT 0 over RCA . 0 1.3. Stable versions of the rainbow Ramsey theorem Consider a 2-bounded coloring f of pairs as the history of interactions between people in an infinite population. f(x,s) = f(y,s) means that x and y interact at time s. In this world, x and y get married if f(x,s) = f(y,s) for cofinitely many s, whereas a person x becomes a monk if f(x,s) is a fresh color for cofinitely many s. Finally, a person x is wise if for each y, either x and y get married or x and y eventually break up forever, i.e., (∀y)[(∀∞s)f(x,s) = f(y,s)∨(∀∞s)f(x,s) (cid:54)= f(y,s)]. In particular married people and monks are wise. Note that 2-boundedness implies that a person x can get married to at most one y. RRT2 states that given an world, we can find infinitely many instants where people behave 2 like monks. However we can weaken our requirement, leading to new principles. Definition 1.5 (Stable rainbow Ramsey theorem). A coloring f : [N]2 → N is rainbow-stable if for every x, one of the following holds: (a) There is a y (cid:54)= x such that (∀∞s)f(x,s) = f(y,s) (b) (∀∞s)|{y (cid:54)= x : f(x,s) = f(y,s)}| = 0 SRRT2 is the statement “every rainbow-stable 2-bounded coloring f : [N]2 → N has a rainbow.” 2 Hence in the restricted world of SRRT2, everybody either gets married or becomes a monk. 2 SRRT2 is a particular case of RRT2. It is proven to have ω-models with only low sets, hence 2 2 is strictly weaker than RRT2. Characterizations of RRT2 extend to SRRT2 which is equivalent 2 2 2 to diagonalizing against any ∅(cid:48)-computable total function, finding an infinite subset of a path in a ∆0 tree of positive ∅(cid:48)-computable measure, or being the subset of an infinite set passing a 2 Schnorr test relativized to ∅(cid:48). SRRT2happenstobeusefulasafactorizationprinciple: Itisstrongenoughtoimplyprinciples 2 like DNR or OPT and weak enough to be consequence of many stable principles, like SRT2, 2 STS(2) or SEM. It thus provides a factorization of the proofs that TS(2) or EM both imply OPT and DNR over ω-models, which were proven independently in [13, 43] for TS(2) and [32] for EM. Wang used in [49] another version of stability for rainbow Ramsey theorems to prove various results, like the existence of non-PA solution to any instance of RRT3. This notion leads to a 2 principle between RRT2 and SRRT2. 2 2 Definition 1.6 (Weakly stable rainbow Ramsey theorem). A coloring f : [N]2 → N is weakly rainbow-stable if (∀x)(∀y)[(∀∞s)f(x,s) = f(y,s)∨(∀∞s)f(x,s) (cid:54)= f(y,s)] WSRRT2 is the statement “every weakly rainbow-stable 2-bounded coloring f : [N]2 → N has 2 an infinite rainbow.” Weak rainbow-stability can be considered as the “right” notion of stability for 2-bounded colorings as one can extract an infinite weakly rainbow-stable restriction of any 2-bounded coloring using cohesiveness. However the exact strength of WSRRT2 is harder to tackle. A characterization candidate 2 would be computing an infinite subset of a path in a ∅(cid:48)-computably graded ∆0 tree where the 2 notion of computable gradation is taken from the restriction of Martin-L¨of tests to capture computable random reals. We prove that it is enough be able to escape finite ∆0 sets to prove 2 4 LUDOVICPATEY WSRRT2. We also separate WSRRT2 from RRT2 by proving that WSRRT2 contains an ω-model 2 2 2 2 with only low sets. The question of exact characterizations of WSRRT2 remains open. 2 Due to the lack of characterizations of WSRRT2, only SFS(2) is proven to be strong enough 2 to imply WSRRT2 among SFS(2), STS(2) and SEM. 2 1.4. Notation The set of finite binary strings is denoted by 2<N. We write (cid:15) for the empty string. The length of σ ∈ 2<N is denoted |σ|. For i ∈ N, and σ ∈ 2<N, σ(i) is the (i+1)-th bit of σ. For σ,τ ∈ 2<N, we say that σ is a prefix of τ (written σ (cid:22) τ) if |σ| ≤ |τ| and σ(i) = τ(i) for all i < |σ|. Given a finite string σ, Γ = {τ ∈ 2<N : σ (cid:22) τ}. σ N N We denote by 2 the space of infinite binary sequences. We also refer to the elements of 2 as sets (of integers), as any X ⊆ N can be identified with its characteristic sequence, which is N N an element of 2 . For a string σ, σ is the set of X ∈ 2 whom σ is a prefix of. A binary tree T is a subset of (cid:74)2<(cid:75)N downward closed under prefix relation. Unless specified otherwise we will consider only binary trees. A sequence P is a path of T if any initial segment of P is in T. We denote by [T] the Π0 class of paths through T. 1 GivenasetX andanelementa, wewritea < X tostatethataisstrictlybeloweachmember of X. We denote by Γi the set {τ ∈ 2<N : (∀s < |τ|)s ∈ X → τ(s) = i}. Γ = Γ0 ∪Γ1 . X X X X Whenever X = {n}, we shall write Γi for Γi . n {n} 2. Rainbow Ramsey theorem The computational strength of the rainbow Ramsey theorem for pairs is well understood, thanks to its remarkable connections with algorithmic randomness, and more precisely the notion of diagonal non-computability. Definition 2.1 (Diagonal non-computability). A function f : N → N is diagonally non- computable relative to X if (∀e)f(e) (cid:54)= ΦX(e). A function f : N → N is fixpoint-free relative to e X if (∀e)W (cid:54)= W . DNR (resp. FPF) is the statement “For every X, there exists a function e f(e) d.n.c. (resp. f.p.f.) relative to X”. For every n ∈ N, DNR[0(n)] is the statement “For every X, there exists a function d.n.c. relative to X(n)”. It is well-known that fixpoint-free degrees are precisely d.n.c. degrees, and that this equiva- lence holds over RCA . Hence RCA (cid:96) DNR ↔ FPF. Miller [36] gave a characterization of d.n.c. 0 0 degrees relative to ∅(cid:48): Theorem 2.2 (Miller [36]). RCA (cid:96) RRT2 ↔ DNR[∅’] 0 2 A first consequence of Theorem 2.2 is another proof of RCA +2-RAN (cid:96) RRT2. Moreover 0 2 it will enable us to prove a lot of implications from other principles to RRT2 – Theorem 3.10, 2 Theorem 4.8 –. The author, together with Bienvenu and Shafer defined in [5] a property over ω-structures, the No Randomized Algorithm property, and classified a wide range of principles depending on whether their ω-models have this property. They proved that for any principle P having this property, there exists an ω-model of RCA +2-RAN which is not a model of P. In 0 particular, there exists an ω-model of RCA +RRT2 which is not a model of P. 0 2 A careful look at the proof of Theorem 2.2 gives the following relativized version: Theorem 2.3 (Miller [36], RCA ). Fix a set X. 0 − There is an X-computable 2-bounded coloring f : [N]2 → N such that every infinite f-rainbow computes (not relative to X) a function d.n.c. relative to X(cid:48). − For every X-computable 2-bounded coloring f : [N]2 → N and every function g d.n.c. relative to X(cid:48), there exists a g⊕X-computable infinite f-thin set. Theorem 2.3 can be generalized by a straightforward adaptation of [13, Theorem 2.5]. We first state a technical lemma. SOMEWHERE OVER THE RAINBOW RAMSEY THEOREM FOR PAIRS 5 Lemma 2.4 (RCA ). Fix a standard n ≥ 1 and X ⊆ N. For every X(cid:48)-computable 2-bounded 0 coloring f : [N]n → N there exists an X-computable 2-bounded coloring g : [N]n+1 → N such that every rainbow for g is a rainbow for f. Proof. Using the Limit Lemma, there exists an X-computable approximation function h : [N]n+1 → N such that lim h((cid:126)x,s) = f((cid:126)x) for every (cid:126)x ∈ [N]n. s Let (cid:104)...(cid:105) be a standard coding of the lists of integers into N and ≺N be a standard total order over N<N. We define an X-computable 2-bounded coloring g : [N]n+1 as follows. (cid:26) (cid:104)h((cid:126)x,s),s,0(cid:105) if there is at most one (cid:126)y ≺N (cid:126)x s.t. h((cid:126)y,s) = h((cid:126)x,s) g((cid:126)x,s) = (cid:104)rank ((cid:126)x),s,1(cid:105) otherwise ≺N (where rank≺N((cid:126)x) is the position of (cid:126)x for any well-order ≺N over tuples). By construction g is 2-bounded and X-computable. We claim that every infinite rainbow for g is a rainbow for f. Let A be an infinite rainbow for g. Assume for the sake of contradiction that (cid:126)x,(cid:126)y ∈ [A]n are such that (cid:126)y ≺N (cid:126)x and f((cid:126)y) = f((cid:126)x). Fix t ∈ N such that h((cid:126)z,s) = f((cid:126)z) whenever (cid:126)z (cid:22)N (cid:126)x and s ≥ t. Fix s such that s ∈ A, s ≥ t and s > max((cid:126)x). Notice that since f is 2-bounded and h((cid:126)z,s) = f((cid:126)z) for every (cid:126)z (cid:22)N (cid:126)x, we have g((cid:126)z,s) = (cid:104)h((cid:126)z,s),s,0(cid:105) = (cid:104)f((cid:126)z),s,0(cid:105) for every (cid:126)z (cid:22)N (cid:126)x. Hence g((cid:126)x,s) = (cid:104)f((cid:126)x),s,0(cid:105) = (cid:104)f((cid:126)y),s,0(cid:105) = g((cid:126)y,s) contradicting the fact that A is a rainbow for g. (cid:3) We can now deduce several relativizations of some existing results. Theorem 2.5 (RCA ). For every standard n ≥ 1 and X ⊆ N, there is an X-computable 2- 0 bounded coloring function f : [N]n+1 → N such that every infinite rainbow for c computes (not relative to X) a function d.n.c. relative to X(n). Proof. By induction over n. Case n = 1 is exactly the statement of Theorem 2.3. Assume it holds for some n ∈ N. Fix an X(cid:48)-computable 2-bounded coloring g : [N]n → N such that every infinite rainbow for g computes a function d.n.c. relative to (X(n−1))(cid:48) = Xn. By Lemma 2.4 there exists an X-computable coloring f : [N]n+1 → N such that every infinite rainbow for f is a rainbow for g. (cid:3) Corollary 2.6. For every standard k ≥ 1, RCA (cid:96) RRT(k+1) → DNR[∅(k)]. 0 2 The other direction does not hold. In fact, for every standard k, there exists an ω-model of DNR[∅(k)] not model of RRT3 as we will see later (Remark 5.28). 2 Definition 2.7 (Hyperimmunity). A function h : N → N dominates a function g : N → N if h(n) > g(n) for all but finitely many n ∈ N. The principal function p of a set A = {x < x < A 0 1 ...} is defined by p (n) = x for every n ∈ N. Given a set X, a set A is hyperimmune relative A n to X if its principal function p is not dominated by any X-computable function. HYP is the A statement “For every set X, there exists a set Y hyperimmune relative to X”. Theorem 2.8 (RCA ). For every standard n ≥ 1 and X ⊆ N, there is an X-computable 0 2-bounded coloring function f : [N]n+2 → N such that every infinite rainbow for f is a set hyperimmune relative to X(n). Proof. As usual, by induction over n. Case n = 1 is exactly the statement of Theorem 4.1 of [13]. Assumeitholdsforsomen ∈ N. FixanX(cid:48)-computable2-boundedcoloringg : [N]n+1 → N such that every infinite rainbow for g is a set hyperimmune relative to (X(n−1))(cid:48) = Xn. By Lemma 2.4 there there exists an X-computable coloring f : [N]n+2 → N such that every infinite rainbow for f is a rainbow for g. This concludes the proof. (cid:3) A simple consequence is that any ω-model of RRT3 is a model of AMT. We will see later by 2 a more careful analysis that RCA (cid:96) RRT3 → STS(2) and RCA (cid:96) STS(2) → AMT. Bienvenu 0 2 0 et al. proved in [5] the existence of an ω-model of RRT2 not model of AMT. 2 6 LUDOVICPATEY Remark 2.9. This theorem is optimal in the sense that every computable 2-bounded coloring c : [N]n+1 → Nhasaninfiniterainbowofhyperimmune-freedegreerelativeto0(n) bycombining atheoremfromJockusch[26]andtherelativizedversionofthehyperimmune-freebasistheorem. As SRT2 and RRT2 are both consequences of RT2 over RCA , one might wonder how they do 2 2 2 0 relate each other. The answer is that they are incomparable as states Corollary 2.12 and Csima & Mileti in [13]. ThefirstdirectionisaconsequenceofaverytrickyproofofseparationofRT2 andSRT2 using 2 2 non-standard models. This separation question was a long-standing open question, recently positively answered by Chong et al. in [9]. Theorem 2.10 (Chong et al. [9]). There is a model of RCA +BΣ0+¬IΣ0+SRT2 having only 0 2 2 2 ∆0 (in fact low) sets. 2 Theorem 2.11. There is no model of RCA +RRT2 having only ∆0 sets. 0 2 2 Proof. Using the characterization of RRT2 by DNR[∅’] proven by Joe Miller – Theorem 2.2 –, 2 let f be a diagonally non-computable function relative to ∅(cid:48). If f were ∆0, then letting e be a 2 Turing index such that Φ∅(cid:48) = f, we would have f(e) (cid:54)= Φ∅(cid:48)(e), contradiction. (cid:3) e e Corollary 2.12. RCA +SRT2 (cid:54)(cid:96) RRT2 0 2 2 The question of separating RT2 and SRT2 in ω-models is still an open question. A related 2 2 question whose positive answer would give a separation of RT2 from SRT2 is the following: 2 2 Question 2.13. Is there an ω-model of RCA +SRT2 which not a model of RRT2 ? 0 2 2 Evenifthequestionisstronger,thisapproachcouldbesimplerasRRT2 coincidewithDNR[∅’] 2 which admits a set complete for the corresponding Muchnik degree, ie any set d.n.c. relative to ∅(cid:48). Csima&Miletiprovedin[13]thatthereexistsacomputable2-boundedcoloringc : [N]2 → N such that every infinite set thin for c computes a set of hyperimmune degree. We now give an alternative proof of the same statement using Π0-genericity. 1 Definition 2.14. A set X is Π0-generic if for all Σ0 classes G, either X is in G or there is a 1 2 Π0 class F disjoint from G such that X is in F. 1 Theorem 2.15 (Monin in [37]). A set X is Π0-generic iff it is of hyperimmune-free degree. 1 Theorem 2.16. No Π0-generic set computes a function d.n.c. relative to ∅(cid:48). 1 Proof. Fix any functional Ψ. Consider the Σ0 class 2 (cid:110) (cid:111) U = X ∈ 2N : (∃e)[ΨX(e) ↑ ∨ΨX(e) = Φ∅(cid:48)(e)] e Consider any Π0-generic X such that ΨX is total. Either X ∈ U, in which case ΨX(e) = 1 Φ∅(cid:48)(e) hence ΨX is not d.n.c. relative to ∅(cid:48). Or there exists a Π0 class F disjoint from U and e 1 containing X. Any member of F computes a function d.n.c. relative to ∅(cid:48). In particular any ∆0 set of PA degree computes such a function, contradiction. (cid:3) 2 Corollary 2.17. Every function d.n.c. relative to ∅(cid:48) is of hyperimmune degree. Proof. Thanks to Theorem 2.15 we can restate Theorem 2.16 as no hyperimmune-free set com- putes a function d.n.c. relative to ∅(cid:48), hence every such function is of hyperimmune degree. (cid:3) 3. The Erdo˝s-Moser theorem BovykinandWeiermann[6]decomposedRT2intoEMandADSasfollows: Givenacoloringf : 2 [N]2 → 2, we can see f as a tournament T such that whenever x <N y, T(x,y) holds if and only if f(x,y) = 1. Any transitive subtournament H can be seen as a linear order (H,≺) such that whenever x <N y, x ≺ y if and only if f(x,y) = 1. Any infinite ascending or descending SOMEWHERE OVER THE RAINBOW RAMSEY THEOREM FOR PAIRS 7 sequence is f-homogeneous. This decomposition also holds for the stable versions and enables us to make SEM inherit from several properties of SRT2. 2 Many principles in reverse mathematics are Π1 statements (∀X)(∃Y)Φ(X,Y), where Φ is 2 an arithmetic formula. They usually come with a natural collection of instances X. A set Y such that Φ(X,Y) holds is a solution to X. For example, in Ramsey’s theorem for pairs, and instance is a coloring f : [N]2 → 2 and a solution to f is an infinite f-homogeneous set. Many proofs of implications Q → P over RCA happen to be computable reductions from P to Q. 0 Definition 3.1 (Computable reducibility). Fix two Π1 statements P and Q. We say that P is 2 computably reducible to Q (written P ≤ Q) if every P-instance I computes a Q-instance J such c that for every solution X to J, X ⊕I computes a solution to I. A computable reducibility P ≤ Q can be seen as a degenerate case of an implication Q → P c over ω-models, in which the principle Q is applied at most once. In order to prove that P (cid:54)≤ Q, c it suffices to construct one P-instance I such that for every I-computable Q-instance J, there exists some solution X to J such that X ⊕I does not compute a solution to I. We need the following stronger notion of avoidance which implies in particular computable non-reducibility. Definition 3.2 (Avoidance). Let P and Q be Π1 statements. P is Q-avoiding if for any set X 2 and any X-computable instance I of Q having no X-computable solution, any X-computable instance of P has a solution S such that I has no X ⊕S-computable solution. Example 3.3. Hirschfeldt and Shore proved in [23] that if some set X does not compute an infinite d.n.c. function, every X-computable linear order has an infinite ascending or descending sequenceY suchthatX⊕Y doesnotcomputeaninfinited.n.c.function. ThereforeADSisDNR- avoiding. On the other side, the author [39] showed the existence of an infinite computable binary tree T ⊆ 2<N with no infinite, computable path, together with a computable coloring f : [N]2 → 2 such that every infinite f-homogeneous set computes an infinite path through T. Therefore RT2 2 is not WKL -avoiding. 0 Theorem 3.4. If P ≤ SRT2 and SADS is P-avoiding, then P ≤ SEM. c 2 c Proof. Let I be any instance of P. As P ≤ SRT2, there exists an I-computable stable coloring c 2 f : [N]2 → 2 such that for any infinite f-homogeneous set H, I ⊕H computes a solution to I. The coloring f can be seen as a tournament T where for each x < y, T(x,y) holds iff f(x,y) = 1. If T has an infinite sub-tournament U such that I⊕H does not compute a solution to I, consider H as an I ⊕H-computable stable linear order. Then by P-avoidance of SADS, there exists a solution S to H such that I ⊕H ⊕S does not compute a solution to I. But S is an infinite f-homogeneous set, contradicting our choice of f. (cid:3) Corollary 3.5 (Kreuzer [31]). There exists a transitive computable tournament having no low infinite subtournament. Proof. Consider the principle Low stating “∀X∃Y(Y ⊕ X)(cid:48) (cid:54)≤ X(cid:48)”. Downey et al. proved T in [14] that for every set X, there exists an X-computable instance of SRT2 with no solution 2 low over X. In other words, Low ≤ SRT2. On the other side, Hirschfeldt et al. [23] proved c 2 that every linear order L of order type ω+ω∗ has an infinite ascending or descending sequence which is low over L. Therefore SADS is Low-avoiding. By Theorem 3.4, Low ≤ SEM. (cid:3) c Corollary 3.6. Any ω-model of SEM is a model of DNR. Proof. Hirschfeldtetal.provedin[22]thatDNR ≤ SRT2 andin[23]thatADSisDNR-avoiding. c 2 By Theorem 3.4, DNR ≤ SEM. (cid:3) c Corollary 3.7. There exists an ω-model of CAC which is not a model of SEM. Proof. Hirschfeldtetal.constructedin[23]anω-modelofCACwhichisnotamodelofDNR. (cid:3) Corollary 3.8. COH ≤ SRT2 if and only if COH ≤ SEM c 2 c 8 LUDOVICPATEY Proof. The author associated in [41] a Π0,∅(cid:48) class C(R(cid:126)) to any sequence of sets R , R , ..., 1 0 1 so that a degree bounds an R(cid:126)-cohesive set if and only if its jump bounds a member of C(R(cid:126)). Hirschfeldt et al. [23] proved that every X-computable instance I of SADS has a solution Y low over X. Therefore, if X does not compute an R(cid:126)-cohesive set, then X(cid:48) does not compute a member of C(R(cid:126)). As (Y ⊕X)(cid:48) ≤ X(cid:48), (Y ⊕X)(cid:48) does not compute a member of C(R(cid:126)), Y ⊕X does not compute an R(cid:126)-cohesive set. In other words, SADS is COH-avoiding. Conclude by Theorem 3.4. (cid:3) Definition 3.9. LetT beatournamentonadomainD ⊆ N. An-cycleisatuple{x ,...,x } ∈ 1 n Dn such that for every 0 < i < n, T(x ,x ) holds and T(x ,x ) holds. i i+1 n 1 Kang [27] attributed to Wang a direct proof of RCA (cid:96) EM → RRT2. We provide an 0 2 alternative proof using the characterization of RRT2 by DNR[∅’] from Miller. 2 Theorem 3.10. RCA (cid:96) EM → DNR[∅’] 0 Proof. Let X be a set. Let g(.,.) be a total X-computable function such that ΦX(cid:48)(e) = e lim g(e,s) if the limit exists, and ΦX(cid:48)(e) ↑ if the limit does not exist. Interpret g(e,s) as s e the code of a finite set D of size 3e+1. We define the tournament T by Σ -induction as fol- e,s 1 lows. Set T = ∅. At stage s+1, do the following. Start with T = T . Then, for each e < s, 0 s+1 s take the first pair {x,y} ∈ D (cid:114)(cid:83) D (notice that such a pair exists by cardinality as- e,s k<e k,s sumptions on the D ), and if T (s,x) and T (s,y) are not already assigned, assign them in e,s s+1 s+1 a way that {x,y,s} forms a 3-cycle in T . Finally, for any z < s such that T (s,z) remains s+1 s+1 undefined, assign any truth value to it in a predefined way (e.g., for any such pair {x,y}, set T (x,y) to be true if x < y, and false otherwise). This finishes the construction of T . Set s+1 s+1 (cid:83) T = T , which must exist as a set by Σ -induction. s s 1 First of all, notice that T is a tournament of domain [N]2, as at the end of stage s+1 of the construction T(x,y) is assigned a truth value for (at least) all pairs {x,y} with x < s and y < s. By EM, let T(cid:48) be a transitive subtournament of T of infinite domain A. Let f(e) be the code of thefinitesetA consistingofthefirst3e+1 elementsofT(cid:48). Weclaimthatf(e) (cid:54)= ΦX(cid:48)(e)foralle, e e which would prove DNR[∅’]. Suppose otherwise, i.e., suppose that ΦX(cid:48)(e) = f(e) for some e. e Then there is a stage s such that f(e) = g(e,s) for all s ≥ s or equivalently D = A for 0 0 e,s e (cid:83) all s ≥ s . Let N = max(A ). We claim that for any s be bigger than both max( D ) 0 e e e,s<Ne e,s and s , the restriction of T to A ∪{s} is not a transitive subtournament, which contradicts the 0 e fact that the restriction T(cid:48) of T to the infinite set A containing A is transitive. e To see this, let s be such a stage. At that stage s of the construction of T, a pair {x,y} ∈ D (cid:114)(cid:83) D is selected, and since D = A , this pair is contained in A . Furthermore, e,s k<e k,s e,s e e we claim that T(s,x) and T(s,y) become assigned at that precise stage, i.e., were not assigned before. This is because, by construction of T, when the value of some T(a,b) is assigned at a stage t, either a ≤ t or b ≤ t. Thus, if T(s,x) was already assigned at the beginning of stage s, it would have in fact been assigned during or before stage x. However, x ∈ A , so x < N , e e and at stage N the number s, by definition of N , has not appeared in the construction yet. e e In particular T(s,x) is not assigned at the end of stage x. This proves our claim, therefore T(s,x) and T(s,y) do become assigned exactly at stage s, in a way – still by construction – that {x,y,s} form a 3-cycle for T. Therefore the restriction of T to A ∪{s} is not a transitive e subtournament, which is what we needed to prove. (cid:3) Corollary 3.11 (Wang in [27]). RCA (cid:96) EM → RRT2 0 2 Proof. Immediate by Theorem 3.10 and Theorem 2.2. (cid:3) Corollary 3.12. SEM does not imply EM over RCA . 0 Proof. Immediate by Theorem 3.10, Theorem 2.2 and Corollary 2.12 (cid:3) We have seen (see Corollary 3.6) that every ω-model of SEM is a model of DNR. We now give a direct proof of it and show that it holds over RCA . 0 SOMEWHERE OVER THE RAINBOW RAMSEY THEOREM FOR PAIRS 9 Theorem 3.13. RCA (cid:96) SEM → DNR 0 Proof. This is obtained by small variation of the proof of Theorem 3.10. Fix a set X. Let g(.,.) be a total X-computable function such that ΦX(e) = lim g(e,s) if ΦX(e) ↓ and lim g(e,s) = 0 e s e s otherwise. Interpret g(e,s) as a code of a finite set D of size 3e+1 such that min(D ) ≥ e e,s e,s and construct the infinite tournament T accordingly. The argument for constructing a function d.n.c. relative to X given an infinite transitive subtournament is similar. We will only prove that the tournament T is stable. Fix some u ∈ N. By BΣ0, which is provable from SEM over RCA (see [31]), there exists some 2 0 stage s after which D remains constant for every e ≤ u. If u is part of a pair {x,y} ⊂ D 0 e,s e,s for some s ≥ s and e, then e ≤ u because min(D ) ≥ e. As the D ’s remain constant for 0 e,s e,s each e ≤ u, the pair {x,y} will be chosen at every stage s ≥ s and therefore T(u,s) will be 0 assigned the same value for every s ≥ s . If u is not part of a pair {x,y}, it will always be 0 assignedthedefaultvalueateverystages ≥ s . Inbothcases, T(u,s)stabilizesatstages . (cid:3) 0 0 4. Free set and thin set theorems Some priority or forcing constructions involving SRT2 split their requirements by color and 2 do not exploit the fact that there exists only two colors. For example the absence of universal instance for principles between RT2 and SRT2 proven by Mileti in [35, Theorem 5.4.2] has been 2 2 generalized by the author to principles between RT2 and STS(2) in [40]. The separation of EM 2 from SRT2 by Lerman et al. [32] has been adapted to a separation of EM from STS(2) as well 2 (see [38]). Question 4.1. Does FS(2) imply EM (or even SEM) over RCA ? 0 The following question is still open: Question 4.2. Is there any k such that RCA (cid:96) TS(k) → FS(k) ? 0 Cholak et al. conjectured that it is never the case. Lemma 4.3. RCA (cid:96) SRT2 → SFS(2) 0 2 Proof. We adapt the proof of [7, Theorem 5.2]. Let f : [N]2 → N be a stable coloring function over pairs. For w(cid:126) an ordered k-tuple and 1 ≤ j ≤ k we write (w(cid:126)) for the jth component of w(cid:126). j Define S = (cid:8)(x,y) ∈ N2 : f(x,y) < y∧f(x,y) (cid:54)∈ {x,y}(cid:9) Given some (cid:126)x ∈ S, let i((cid:126)x) be the least j such that f((cid:126)x) < ((cid:126)x) . Such a j exists because (cid:126)x ∈ S. j Let h((cid:126)x) be the increasing ordered pair obtained from (cid:126)x by replacing ((cid:126)x) by f((cid:126)x). Note i((cid:126)x) that h((cid:126)x) is lexicographically smaller than (cid:126)x. Let c((cid:126)x) be the least j ∈ N such that h(j)((cid:126)x) (cid:54)∈ S or i(h(j)((cid:126)x)) (cid:54)= i((cid:126)x) where h(j) is the jth iteration of h. The function c is well-defined because the lexicographic order is a well-order. Define a function g : [N]2 → 6 as follows for each x < y:  0 if f(x,y) ∈ {x,y}  g(x,y) = 1 if f(x,y) > y  2i(x,y)+j if (x,y) ∈ S,j ≤ 1 and c(x,y) ≡ j mod 2 Fix an x. Because f is stable there is a y such that for every y ≥ y f(x,y) = f(x,y ). 0 0 0 Case 1: If there is a y such that f(x,y ) ∈ {x,y } then for every y,w > max(y ,y ), 1 1 1 0 1 f(x,y) ∈ {x,y} iff f(x,w) ∈ {x,w} and hence after a threshold first condition will either be always fulfilled or will never be. Case 2: For every y ≥ max(y ,f(x,y )), f(x,y) = f(x,y ) ≤ y. Hence second condition will 0 0 0 be fulfilled for finitely many y. Case 3: It suffices to check that i and c are stable when f is. If f(x,y ) < x then i(x,y) = 1 0 for every y ≥ y . If x ≤ f(x,y ) < y then x ≤ f(x,y) < y ≤ y for every y ≥ y . Hence i is 0 0 0 0 0 stable. It remains to check stability of c(x,y). By induction over x: 10 LUDOVICPATEY − If f(x,y ) < x then h(x,y) = (f(x,y ),y) for every y ≥ y . By stability of f, 0 0 0 there is a y such that f(f(x,y ),y) = f(f(x,y ),y ) for every y ≥ y . For y > 1 0 0 1 1 max(y ,f(f(x,y ),y )), f(f(x,y ),y) = f(f(x,y ),y ) < y. If f(f(x,y ),y ) = f(x,y ) 1 0 1 0 0 1 0 1 0 then (f(x,y ),y ) = h(x,y) (cid:54)∈ S hence j = 1 for every y > max(y ,f(f(x,y ),y )). 0 1 1 0 1 Otherwise h(x,y) ∈ S. If f(h(x,y)) = f(f(x,y ),y) = f(f(x,y ),y ) > f(x,y ) 0 0 1 0 then i(h(x,y)) (cid:54)= i(x,y) and j = 1 for every y > max(y ,f(f(x,y ),y )). Oth- 1 0 1 erwise h(x,y) ∈ S and i(h(x,y) = i(x,y) so j = 1 + i where i is the least inte- ger such that h(i)(f(x,y ),y) ∈ S or i(h(i)(f(x,y ),y) (cid:54)= i(x,y) = i(h(x,y). Hence 0 0 j = 1 + c(f(x,y ),y). By induction hypothesis, there is a y such that for every 0 2 y ≥ y , c(f(x,y ),y) = c(f(x,y ),y ). So for every y,w > max(y ,y ,f(f(x,y ),y )) 2 0 0 2 1 2 0 1 c(x,y) = c(x,w). − If x ≤ f(x,y ) < y then for every y ≥ y , h(x,y) = (x,f(x,y )) and hence c(x,y) = 0 0 0 0 c(x,y ). 0 (cid:3) Corollary 4.4. RCA (cid:96) SRT2 → STS(2) 0 2 Proof. Apply Lemma 4.3 using the restriction of Theorem 3.2 to stable functions in [7]. (cid:3) Theorem 4.5. RCA (cid:96) (∀n)[RRTn+1 → TS(n)] 0 2 Proof. Fix some n ∈ N and let f : [N]n → N be a coloring. We build a ∆0,f 2-bounded coloring 1 g : [N]n+1 → N such that every infinite rainbow for g is, up to finite changes, thin for f. For every y ∈ N and (cid:126)z ∈ [N]n, if f((cid:126)z) = (cid:104)x,y(cid:105) with x < y < min((cid:126)z), then set g(y,(cid:126)z) = g(x,(cid:126)z). Otherwise assign g(y,(cid:126)z) a fresh color. The function g is clearly 2-bounded. Let H be an infinite rainbow for g and let x,y ∈ H be such that x < y. Set H = H (cid:114)[0,y]. We claim that H 1 1 is f-thin with color (cid:104)x,y(cid:105). Indeed, for every (cid:126)z ∈ [H ]n, if f((cid:126)z) = (cid:104)x,y(cid:105) then x < y < min((cid:126)z), 1 so g(x,(cid:126)z) = g(y,(cid:126)z). This contradicts the fact that H is a g-rainbow. (cid:3) Theorem 4.6. For every standard n, RCA (cid:96) RRT2n+1 → FS(n) 0 2 Proof. Let (cid:104)·,·(cid:105) be a bijective coding from {(x,y) ∈ N2 : x < y} to N, such that (cid:104)x,y(cid:105) < (cid:104)u,v(cid:105) whenever x < u and y < v. We shall refer to this property as (P1). We say that a function f : [N]n → N is t-trapped for some t ≤ n if for every (cid:126)z ∈ [N]n, z ≤ f((cid:126)z) < z , where z = −∞ t−1 t −1 and z = +∞. Wang proved in [50, Lemma 4.3] that we can restrict without loss of generality n to trapped functions when n is a standard integer. Let f : [N]n → N be a t-trapped coloring for some t ≤ n. We build a ∆0,f 2-bounded coloring 1 g : [N]2n+1 → N such that every infinite rainbow for g computes an infinite set thin for f. Given some (cid:126)z ∈ [N]n, we write (cid:126)z (cid:46)(cid:47) u to denote the (2n+1)-uple t x ,y ,...,x ,y ,u,x ,y ,...,x ,y 0 0 t−1 t−1 t t n−1 n−1 where z = (cid:104)x ,y (cid:105) for each i < n. We say that (cid:126)z (cid:46)(cid:47) u is well-formed if the sequence above is a i i 1 t strictly increasing. For every y ∈ N and (cid:126)z ∈ [N]n such that (cid:126)z (cid:46)(cid:47) y is well-formed, if f((cid:126)z) = (cid:104)x,y(cid:105) for some x such t that (cid:126)z (cid:46)(cid:47) x is well-formed, then set g((cid:126)z (cid:46)(cid:47) y) = g((cid:126)z (cid:46)(cid:47) x). Otherwise assign g((cid:126)z (cid:46)(cid:47) y) a fresh t t t t color. The function g is total and 2-bounded. Let H = {x < y < x < y < ...} be an infinite rainbow for g and let H = {(cid:104)x ,y (cid:105) : 0 0 1 1 1 i i i ∈ N}. We claim that H is f-free. Let (cid:126)z ∈ [H ]n be such that f((cid:126)z) ∈ H . In particular, 1 1 1 f((cid:126)z) = (cid:104)x ,y (cid:105) for some i ∈ N. By t-trapeness of f and by (P1), if f((cid:126)z) (cid:54)= z then (cid:126)z (cid:46)(cid:47) x i i t−1 t i and (cid:126)z (cid:46)(cid:47) y are both well-formed. Hence g((cid:126)z (cid:46)(cid:47) x ) = g((cid:126)z (cid:46)(cid:47) y ). Because H is a g-rainbow, t i t i s i either x or y is not in H, contradicting (cid:104)x ,y (cid:105) ∈ H . Therefore f((cid:126)z) = z . (cid:3) i i i i 1 t−1 Corollary 4.7. RRT and FS coincide over ω-models. We now strengthen Wang’s result by proving that TS(2) → RRT2 using Miller’s character- 2 ization (Theorem 2.2). We will see in Corollary 4.21 that the implication is strict by showing that n-WWKL does not imply STS(2) over RCA for every n. 0