Ramsey's theorem for pairs

Ramsey's theorem as a case study beyond the Big Five: Jockusch's bounds on the complexity of homogeneous sets and the equivalence of Ramsey's theorem for triples with ACA₀, the decomposition of Ramsey's theorem for pairs into cohesiveness and stable Ramsey's theorem, and Seetapun's theorem, proved through cone avoidance for Mathias forcing and the forcing of Dzhafarov and Jockusch.

Contents

1. 1

   Ramsey's theorem in the arithmetic hierarchy

   Ramsey's theorem for n-tuples; pre-homogeneous sets and the Erdős–Radó tree; every coloring of n-tuples has a homogeneous set computable in any degree PA over its (n−1)-st jump; a computable coloring of pairs without Δ⁰₂ homogeneous set; Ramsey's theorem for triples is equivalent to ACA₀.

   1. 1.1 Statements
   2. 1.2 Pre-homogeneous sets and the upper bound
   3. 1.3 The lower bound
   4. 1.4 Coding the jump into triples
   5. 1.5 Reverse mathematics
   6. 1.6 Exercises
   7. 1.7 Notes and references
   45 min
2. 2

   Cohesiveness and stable colorings

   Cohesive sets; stable colorings of pairs and their limit sets; Ramsey's theorem for pairs decomposes into the cohesiveness principle and stable Ramsey's theorem; stable Ramsey's theorem is equivalent to the statement that every Δ⁰₂ set has an infinite subset in it or in its complement.

   1. 2.1 Cohesive sets
   2. 2.2 Stable colorings
   3. 2.3 Stable Ramsey's theorem and Δ⁰₂ sets
   4. 2.4 Exercises
   5. 2.5 Notes and references
   35 min
3. 3

   Seetapun's theorem

   Cone avoidance for cohesiveness by Mathias forcing; strong cone avoidance for the infinite pigeonhole principle by the forcing of Dzhafarov and Jockusch; Seetapun's theorem that every computable coloring of pairs has a homogeneous set not computing a given non-computable set; RT²₂ does not imply ACA₀.

   1. 3.1 Mathias forcing
   2. 3.2 Cone avoidance for cohesiveness
   3. 3.3 Strong cone avoidance for the pigeonhole principle
   4. 3.4 Seetapun's theorem
   5. 3.5 Exercises
   6. 3.6 Notes and references
   45 min