View Related Documents

Abstract

Ramsey's Theorem deals with colorings of the k-element subsets of a fixed infinite set. The Dual Ramsey Theorem deals with colorings of the k-element partitions of a fixed infinite set. We review the statement of the Dual Ramsey Theorem and of its generalization to A-partitions. Here A is a finite alphabet. We discuss the problem of optimal recursion-theoretic bounds for the Dual Ramsey Theorem. We point out applications of the Dual Ramsey Theorem to initial segment constructions in degree theory. We state a result of Brackin concerning partitions which have no coarsenings of higher Turing degree. In an appendix we summarize the known results (and present two new results) concerning "nearly recursive" (i.e. bi-immune free) Turing degrees.
This paper is in final form. The results which are proved here will not be published elsewhere.
Research partially supported by NSF grant MCS 8107867.

Fulltext Preview

Image of the first page of the fulltext document