pith. sign in

arxiv: 1507.03256 · v1 · pith:RHKUKU7Tnew · submitted 2015-07-12 · 🧮 math.LO

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

classification 🧮 math.LO
keywords proofsetscomputablehomogeneousinfinitejockuschpairstheorem
0
0 comments X
read the original abstract

In \cite{J}, Theorem 4.2, Jockusch proves that for any computable k-coloring of pairs of integers, there is an infinite $\Pi^0_2$ homogeneous set. The proof uses a countable collection of $\Pi^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 $\Pi^0_2$ sets. We provide a proof of this latter fact.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.