The definability strength of combinatorial principles

DOI10.1017/JSL.2016.10zbMATH Open1436.03099arXiv1408.1465OpenAlexW2467976395MaRDI QIDQ2976345FDOQ2976345

Authors: Wei Wang 

Publication date: 28 April 2017

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

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.

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

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

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)

Cites Work

• Algorithmic randomness and complexity.
• Subsystems of second order arithmetic
• Separating principles below Ramsey's theorem for pairs
• Title not available (Why is that?)
• The atomic model theorem and type omitting
• On the strength of Ramsey's theorem
• Cohesive sets and rainbows
• Some logically weak Ramseyan theorems
• Turing degrees of certain isomorphic images of computable relations

Cited In (12)

• Combinatorial versus decision-theoretic components of impossibility theorems
• A combinatorial version of the Svenonius theorem on definability
• Dominating the Erdős-Moser theorem in reverse mathematics
• Degrees bounding principles and universal instances in reverse mathematics
• Extracting randomness within a subset is hard
• Erdős-Moser and \(I \Sigma_2\)
• Definable combinatorics at the first uncountable cardinal
• Pigeons do not jump high
• 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)