Ramsey-like theorems and immunities

Abstract

A Ramsey-like theorem is a statement of the form ``For every 2-coloring of $[\mathbb{N}{]}^2$, there exists an infinite set~$H\subseteq \mathbb{N}$ such that $[H{]}^2$ avoids some pattern''. We prove that none of these statements are computably trivial, by constructing a computable 2-coloring of $[\mathbb{N}{]}^2$ such that every infinite set avoiding any pattern computes a diagonally non-computable function relative to ${\varnothing }^{\prime }$. We also consider multiple notions of weaknesses based of variants of immunity, and characterize the Ramsey-like theorems which preserve these notions or not, based on the shape of the avoided pattern. This is part of a larger study of the reverse mathematics of Ramsey-like theorems.

39 pages