Abstract

We study some generalized notions of cohesiveness which arise naturally in connection with effective versions of Ramsey's Theorem. An infinite set A of natural numbers is n-cohesive if A is almost homogeneous for every computably enumerable 2-coloring of the n-element sets of natural numbers. We consider the degrees of unsolvability and arithmetical definability levels of n-cohesive and n-r-cohesive sets. For example, we show that for all $n \geq 2$, there exists a $\Delta^0_{n+1}$ n-cohesive set. We improve this result for n = 2 by showing that there is a $\Pi^0_2$ 2-cohesive set. We show that the n-cohesive and n-r-cohesive degrees together form a linear, non-collapsing hierarchy of degrees for $n \geq 2$. In addition, for $n \geq 2$ we characterize the jumps of n-cohesive degrees as exactly the degrees $\geq 0^{}$ and also characterize the jumps of the n-r-cohesive degrees.