The reverse mathematics of the Thin set and Erdős-Moser theorems

Abstract

The thin set theorem for $n$-tuples and $k$ colors (${\mathsf{TS}}_k^n$) 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 ${\mathsf{TS}}_k^n$, nor the free set theorem (${\mathsf{FS}}^n$) imply the Erdős-Moser theorem ($\mathsf{EM}$) whenever $k$ is sufficiently large (answering a question of Patey and giving a partial result towards a question of Cholak Giusto, Hirst and Jockusch). 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 (answering a question of Patey).

34 pages

References in corpus (2)

• Some logically weak Ramseyan theorems
• The reverse mathematics of Ramsey-type theorems