Computable Ramsey's theorem for pairs needs infinitely many \(\Pi ^0_2\) sets

DOI10.1007/S00153-016-0519-2zbMATH Open1386.03056arXiv1507.03256OpenAlexW2962726502MaRDI QIDQ512143

Henry Towsner, Gregory Igusa

Publication date: 24 February 2017

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1507.03256

zbMATH Keywords

Ramsey's theoremrecursion theory\(\Pi_2^0\) setseffective combinatoricstheory of computability

Mathematics Subject Classification ID

Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Recursively (computably) enumerable sets and degrees (03D25)

Cites Work

• Ramsey's theorem and recursion theory

This page was built for publication: Computable Ramsey's theorem for pairs needs infinitely many \(\Pi ^0_2\) sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512143)