Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom

DOI10.2178/JSL.7803070zbMATH Open1300.03013arXiv1303.3327OpenAlexW2592247263WikidataQ114005164 ScholiaQ114005164MaRDI QIDQ2869903FDOQ2869903

Authors: Wei Wang 

Publication date: 7 January 2014

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: We prove that $RCA+RR{T}_2^{3}otvdashACA$ where $RR{T}_2^3$ is the Rainbow Ramsey Theorem for 2-bounded colorings of triples. This reverse mathematical result is based on a cone avoidance theorem, that every 2-bounded coloring of pairs admits a cone-avoiding infinite rainbow, regardless of the complexity of the given coloring. We also apply the proof of the cone avoidance theorem to the question whether $RCA+RR{T}_2^{4}vdashACA$ and obtain some partial answer.

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

Recommendations

• The strength of the rainbow Ramsey Theorem
• A rainbow Ramsey analogue of Rado's theorem
• Some logically weak Ramseyan theorems
• scientific article; zbMATH DE number 512985
• Some remarks on uncountable rainbow Ramsey theory
• More on monochromatic-rainbow Ramsey type theorems
• Random reals, the rainbow Ramsey theorem, and arithmetic conservation
• scientific article
• Rainbow Arithmetic Progressions and Anti-Ramsey Results
• Combinatorial principles weaker than Ramsey's Theorem for pairs

zbMATH Keywords

ACAreverse mathematicscohesive setrainbow Ramsey theoremarithmetical comprehensioncone avoidance

Mathematics Subject Classification ID

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

Cites Work

• On the strength of Ramsey's theorem for pairs
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Title not available (Why is that?)
• On the strength of Ramsey's theorem
• Class groups of integral group rings

Cited In (8)

• Pathwise-randomness and models of second-order arithmetic
• Some logically weak Ramseyan theorems
• On uniform relationships between combinatorial problems
• Combinatorial principles between \(\text{RRT}_2^2\) and \(\text{RT}_2^2\)
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• The strength of the rainbow Ramsey Theorem
• Pigeons do not jump high
• Cohesive sets and rainbows

This page was built for publication: Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom

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