Some logically weak Ramseyan theorems

DOI10.1016/J.AIM.2014.05.003MaRDI QIDQ2453567zbMATH OpenOpenAlexFDO

Publication date 10 June 2014

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.3331

free set rainbow Ramsey theorem Ramsey's theorem reverse mathematics thin set

Foundations of classical theories (including reverse mathematics) (03B30) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35) Ramsey theory (05D10)

Abstract: We study four families of consequences of Ramsey's Theorem from the viewpoint of reverse mathematics. The first, which we call the Achromatic Ramsey Theorem, is from a partition relation introduced by ErdH{o}s, Hajnal and Rado:

o m e g a o [o m e g a]_{c, l e q d}^{r}

, which asserts that for every

f : [o m e g a]^{r} o c

there exists an infinite

H

with

| f ([H]^{r}) | l e q d

. The second and third are the Free Set Theorem and the Thin Set Theorem, which were introduced by Harvey Friedman. And the last is the Rainbow Ramsey Theorem. We show that, most theorems from these families are quite weak, i.e., they are strictly weaker than

o p e r a t o r n a m e {A C A}_{0}

over

o p e r a t o r n a m e {R C A}_{0}

. Interestingly, these families turn out to be closely related. We establish the so-called strong cone avoidance property of most instances of the Achromatic Ramsey Theorem by an induction of exponents, then apply this and a similar induction to obtain the strong cone avoidance property of the Free Set Theorem. From the strong cone avoidance property of the Achromatic Ramsey Theorem and the Free Set Theorem, we derive the strong cone property of the Thin Set Theorem and the Rainbow Ramsey Theorem. It follws easily that a theorem with the strong cone avoidance property does not imply

o p e r a t o r n a m e {A C A}_{0}

over

o p e r a t o r n a m e {R C A}_{0}

.

Review text

The main aim of the paper is to show that some Ramsey-like theorems are weak in the sense that (unlike the usual Ramsey theorem) they do not imply \(\mathrm{ACA}_0\) even if they are stated for arbitrarily large fixed exponents. The theorems studied include: -- the achromatic Ramsey theorem for exponent \(r\) and bound \(d\), \(\mathrm{ART}^r_{<\infty, d}\): for every colouring \(f\) of \([\omega]^r\) by finitely many colours, there exists an infinite \(H\) such that \(f([H]^r)\) has fewer than \(d\) elements, -- Friedman's thin set theorem and free set theorem for exponent \(r\), \(\mathrm{TS}^r\) and \(\mathrm{FS}^r\): for every \(f : [\omega]^r \to \omega\), there exists an infinite set \(S\) such that \(f([S]^r) \neq \omega\) and an infinite set \(H\) such that for all \(\bar x \in [H]^r\), \(f(\bar x) \notin H \setminus \{\bar x\}\), respectively, -- the rainbow Ramsey theorem for exponent \(r\) and bound \(b\), \(\mathrm{RRT}^r_b\): for every colouring \(f : [\omega]^r \to \omega\), if not more than \(b\) tuples are mapped to any single colour, then there is an infinite set \(H\) such that \(f\) is injective on \([H]^r\). The author proves that none of \(\mathrm{TS}^r\), \(\mathrm{FS}^r\) and \(\mathrm{RRT}^r_2\) imply \(\mathrm{ACA}_0\) over \(\mathrm{RCA}_0\), and neither does \(\mathrm{ART}^r_{<\infty,d_r}\) for a sufficiently large number \(d_r\) which depends on \(r\) but can be effectively bounded in \(r\). This is a significant strengthening of earlier results by the author such as the unprovability of \(\mathrm{ACA}_0\) from \(\mathrm{RCA}_0 + \mathrm{RRT}^3_2\) [J. Symb. Log. 78, No. 3, 824--836 (2013; Zbl 1300.03013)]. To prove the weakness of the above theorems, the author shows that the computational problems associated with the theorems have the strong cone avoidance property. Here, a problem associated with a statement \(\forall X \exists Y \varphi(X,Y)\) has strong cone avoidance if for any set \(A\), any \(B\) that does not compute \(A\), and any \(X\) (regardless of the complexity of \(X\)) there exists a solution \(Y\) to \(\varphi(X,Y)\) such that \(B \oplus Y\) still does not compute \(A\). Strong cone avoidance for \(\mathrm{ART}^r_{<\infty,d_r}\) and \(\mathrm{FS}^r\) is established by induction on \(r\); the inductive steps are relatively involved arguments employing, among other things, standard tools in this area such as cohesive-stable decomposition and Mathias forcing. Strong cone avoidance for \(\mathrm{TS}^r\) and \(\mathrm{RRT}^r_2\) follows easily.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: Some logically weak Ramseyan theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453567)