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

Lu Liu, Ludovic Patey

Published 2021-03-14Version 1

The thin set theorem for $n$-tuples and $k$ colors ($\mathsf{TS}^n_k$) 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}^n_k$, nor the free set theorem ($\mathsf{FS}^n$) imply the Erd\H{o}s-Moser theorem ($\mathsf{EM}$) 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. We prove that Erd\H{o}s-Moser theorem does not admit a universal instance.