Computable Ramsey's Theorem for Pairs Needs Infinitely Many Pi-0-2 Sets Article Swipe

PDF

Related Concepts

Countable set Mathematics Homogeneous Pi Discrete mathematics Ramsey theory Combinatorics Ramsey's theorem Set (abstract data type) Computer science Programming language Geometry Graph

Gregory Igusa , Henry Towsner ·

YOU? · · 2015 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1507.03256 · OA: W1846297281

In \cite{J}, Theorem 4.2, Jockusch proves that for any computable k-coloring of pairs of integers, there is an infinite $Π^0_2$ homogeneous set. The proof uses a countable collection of $Π^0_2$ sets as potential infinite homogeneous sets. In a remark preceding the proof, Jockusch states without proof that it can be shown that there is no computable way to prove this result with a finite number of $Π^0_2$ sets. We provide a proof of this latter fact.