The definability strength of combinatorial principles

DOI10.1017/JSL.2016.10MaRDI QIDQ2976345zbMATH OpenOpenAlexFDO

Authors Wei Wang

Publication date 28 April 2017

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

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

zbMATH Keywords

reverse mathematicsRamsey's theoremthin setfree setrainbow Ramsey theorydefinability strength

Mathematics Subject Classification ID

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

Abstract: We introduce the definability strength of combinatorial principles. In terms of definability strength, a combinatorial principle is strong if solving a corresponding combinatorial problem could help in simplifying the definition of a definable set. We prove that some consequences of Ramsey's Theorem for colorings of pairs could help in simplifying the definitions of some $Delt{a}_2^0$ sets, while some others could not. We also investigate some consequences of Ramsey's Theorem for colorings of longer tuples. These results of definability strength have some interesting consequences in reverse mathematics, including strengthening of known theorems in a more uniform way and also new theorems.

Recommendations

• \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
• scientific article; zbMATH DE number 7377981
• Combinatorial principles between \(\text{RRT}_2^2\) and \(\text{RT}_2^2\)
• Strong reductions between combinatorial principles
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs

Cites work

• scientific article; zbMATH DE number 2236640 (Why is no real title available?)
• Algorithmic randomness and complexity.
• Cohesive sets and rainbows
• On the strength of Ramsey's theorem
• Separating principles below Ramsey's theorem for pairs
• Some logically weak Ramseyan theorems
• Subsystems of second order arithmetic
• The atomic model theorem and type omitting
• Turing degrees of certain isomorphic images of computable relations

Cited in

(12)

• Combinatorial versus decision-theoretic components of impossibility theorems
• Dominating the Erdős-Moser theorem in reverse mathematics
• A combinatorial version of the Svenonius theorem on definability
• Degrees bounding principles and universal instances in reverse mathematics
• Extracting randomness within a subset is hard
• Erdős-Moser and \(I \Sigma_2\)
• Pigeons do not jump high
• Definable combinatorics at the first uncountable cardinal
• A combinatorial result related to the consistency of New Foundations
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• Open questions about Ramsey-type statements in reverse mathematics
• Strong combinatorial principles and level by level equivalence

This page was built for publication: The definability strength of combinatorial principles

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