A Survey of Recursive Combinatorics
William I. Gasarch · 2007
4 Ramsey’s Theorem 12 4.1 Definitions and Classical Version . . . . . . . . . . . . . . . . 13 4.2 Recursive Analogue is False . . . . . . . . . . . . . . . . . . . 15 4.3 How Hard is it to Tell if a Homogeneous set is Recursive? . . . 16 4.4 Recursion-Theoretic Modifications . . . . . . . . . . . . . . . . 19 4.5 Connections to Proof Theory . . . . . . . . . . . . . . . . . . 23 4.6 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.6.1 2-colorings of [N] . . . . . . . . . . . . . . . . . . . . . 27 ∗Supported in part by NSF grants CCR-84-05079, CCR-88-03641, and CCR-90-20079.