${\mathsf{RT}}_2^2$ does not imply ${\mathsf{WKL}}_0$

Abstract

We prove that ${\mathsf{RCA}}_0+{\mathsf{RT}}_2^2\nrightarrow {\mathsf{WKL}}_0$ by showing that for any set $C$ not of PA-degree and any set $A$, there exists an infinite subset $G$ of $A$ or $\bar{A}$, such that $G\oplus C$ is also not of PA-degree.

12 pages