文摘
In Ramsey’s Theorem and Recursion Theory, Theorem 4.2, Jockusch proved that for any computable k-coloring of pairs of integers, there is an infinite \(\Pi ^0_2\) homogeneous set. The proof used a countable collection of \(\Pi ^0_2\) sets as potential infinite homogeneous sets. In a remark preceding the proof, Jockusch stated without proof that it can be shown that there is no computable way to prove this result with a finite number of \(\Pi ^0_2\) sets. We provide a proof of this claim, showing that there is no computable way to take an index for an arbitrary computable coloring and produce a finite number of indices of \(\Pi ^0_2\) sets with the property that one of those sets will be homogeneous for that coloring. While proving this result, we introduce n-trains as objects with useful combinatorial properties which can be used as approximations to infinite \(\Pi ^0_2\) sets.
