April 5
Peter Cholak,
University of Notre Dame
Computability-Theoretic Aspects of Ramsey's Theorem
Ramsey's Theorem for pairs and 2 colors says that for every 2-coloring, $C$, of pairs of natural numbers, there is an infinite set $H$, such that all pairs from $H$ have the same constant color. $H$ is called a homogeneous set for $C$. We will also consider Ramsey's Theorem in other settings. For example, we can be given countably many $1$-colorings of natural numbers, $\{c_i\}$, and ask for a set $C$ such that, for each $i$, all but finitely many elements of $C$ have the same color with respect to $c_i$. Call $C$ a cohesive set for $\{c_i\}$. Among the questions we will explore here is what can be computed from homogeneous sets. For example, given countably many $1$-colorings $\{c_i\}$, is there a 2-coloring $C$, such that every homogeneous set for $C$ computes a cohesive set for $\{c_i\}$?