The reverse mathematics of the thin set and erdős–moser theorems

Journal of Symbolic Logic 87 (1):313-346 (2022)
  Copy   BIBTEX

Abstract

The thin set theorem for n-tuples and k colors states that every k-coloring of $[\mathbb {N}]^n$ admits an infinite set of integers H such that $[H]^n$ avoids at least one color. In this paper, we study the combinatorial weakness of the thin set theorem in reverse mathematics by proving neither $\operatorname {\mathrm {\sf {TS}}}^n_k$, nor the free set theorem imply the Erdős–Moser theorem whenever k is sufficiently large. Given a problem $\mathsf {P}$, a computable instance of $\mathsf {P}$ is universal iff its solution computes a solution of any other computable $\mathsf {P}$ -instance. It has been established that most of Ramsey-type problems do not have a universal instance, but the case of Erdős–Moser theorem remained open so far. We prove that Erdős–Moser theorem does not admit a universal instance.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,261

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Dominating the Erdős–Moser theorem in reverse mathematics.Ludovic Patey - 2017 - Annals of Pure and Applied Logic 168 (6):1172-1209.
The Thin Set Theorem for Pairs Implies DNR.Brian Rice - 2015 - Notre Dame Journal of Formal Logic 56 (4):595-601.
Reverse Mathematics and Completeness Theorems for Intuitionistic Logic.Takeshi Yamazaki - 2001 - Notre Dame Journal of Formal Logic 42 (3):143-148.
Refining the Taming of the Reverse Mathematics Zoo.Sam Sanders - 2018 - Notre Dame Journal of Formal Logic 59 (4):579-597.
Reverse mathematics: the playground of logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
Reverse mathematics and initial intervals.Emanuele Frittaion & Alberto Marcone - 2014 - Annals of Pure and Applied Logic 165 (3):858-879.
Splittings and Disjunctions in Reverse Mathematics.Sam Sanders - 2020 - Notre Dame Journal of Formal Logic 61 (1):51-74.
The Dirac delta function in two settings of Reverse Mathematics.Sam Sanders & Keita Yokoyama - 2012 - Archive for Mathematical Logic 51 (1-2):99-121.
omnibus Review. [REVIEW]James Baumgartner - 1995 - Journal of Symbolic Logic 60 (2):698-701.
[Omnibus Review].James E. Baumgartner - 1985 - Journal of Symbolic Logic 50 (1):239-240.
The modal logic of Reverse Mathematics.Carl Mummert, Alaeddine Saadaoui & Sean Sovine - 2015 - Archive for Mathematical Logic 54 (3-4):425-437.

Analytics

Added to PP
2022-04-08

Downloads
7 (#1,392,075)

6 months
3 (#984,770)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Lu Liu
Central South University

Citations of this work

No citations found.

Add more citations

References found in this work

On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
Open questions in reverse mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
Degrees bounding principles and universal instances in reverse mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.

Add more references