The weakness of the Erdős-Moser theorem under arithmetic reductions

Abstract

The Erdős-Moser theorem $(\mathsf{EM})$ says that every infinite tournament admits an infinite transitive subtournament. We study the computational behavior of the Erdős-Moser theorem with respect to the arithmetic hierarchy, and prove that ${\Delta }_n^0$ instances of $\mathsf{EM}$ admit low${}_{n+1}$ solutions for every $n\ge 1$, and that if a set $B$ is not arithmetical, then every instance of $\mathsf{EM}$ admits a solution relative to which $B$ is still not arithmetical. We also provide a level-wise refinement of this theorem. These results are part of a larger program of computational study of combinatorial theorems in Reverse Mathematics.