Some logically weak Ramseyan theorems (Q2453567): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / arXiv ID
 
Property / arXiv ID: 1303.3331 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the strength of Ramsey's theorem for pairs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5711879 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The metamathematics of Stable Ramsey’s Theorem for Pairs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reverse mathematics, computability, and partitions of trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: The strength of the rainbow Ramsey Theorem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ramsey's theorem and cone avoidance / rank
 
Normal rank
Property / cites work
 
Property / cites work: Partition relations for cardinal numbers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial principles weaker than Ramsey's Theorem for pairs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ramsey's theorem and recursion theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: ∏ 0 1 Classes and Degrees of Theories / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3758821 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3329452 / rank
 
Normal rank
Property / cites work
 
Property / cites work: RT<sub>2</sub><sup>2</sup> does not imply WKL<sub>0</sub> / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the strength of Ramsey's theorem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4220572 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Rainbow Ramsey Theorem for Triples is Strictly Weaker than the Arithmetical Comprehension Axiom / rank
 
Normal rank
Property / cites work
 
Property / cites work: Cohesive sets and rainbows / rank
 
Normal rank

Latest revision as of 14:09, 8 July 2024

scientific article
Language Label Description Also known as
English
Some logically weak Ramseyan theorems
scientific article

    Statements

    Some logically weak Ramseyan theorems (English)
    0 references
    0 references
    10 June 2014
    0 references
    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.
    0 references
    reverse mathematics
    0 references
    Ramsey's theorem
    0 references
    free set
    0 references
    thin set
    0 references
    rainbow Ramsey theorem
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references