# $\Sigma_1^0-COH$?

In reverse mathematics, $COH$ is a statement that there is a cohesive set for any uniform array of sets. Here uniform array of sets means that there exists a set $B$ such that $x\in B_e \leftrightarrow (e,x)\in B$, while a set $A$ is cohesive for $\lbrace B_e: e\in \omega\rbrace$ if and only if $A\subset^* B_e$ or $A\subset^*\bar B_e$ for any $e\in \omega$.

I am thinking of a stronger version of $COH:$ replace the uniform family of sets by $\Sigma^0_1$ family, namely there exists a set $B$ such that $x\in B_e \leftrightarrow \exists z (e,x,z)\in B$ and a cohesive for $\lbrace B_e: e\in \omega\rbrace$ exists. I am searching for literatures that studied this principle previously but so far have not found anything interesting. Does anyone know what has been done regarding this principle?

-
Thanks! Should be $\Sigma^0_1$ – Jing Zhang Feb 16 '13 at 14:01

I also don't recall this principle being directly adressed in the reverse math literature. However, known results can be pieced together to paint a decent picture for $\Sigma^0_1$-COH. I will add to this answer if I find something more.

The results of Jockusch and Stephan, A cohesive set which is not high [Math. Logic Quart. 39 (1993), 515–530; doi:10.1002/malq.19930390153, MR1270396] (that survive the later corrections [Math. Logic Quart. 43 (1997), 569; doi:10.1002/malq.19970430412, MR1477624]) are very relevant, at least in the context of $\omega$-models. In particular, it follows from these results that $\Sigma^0_1$-COH does not imply arithmetic comprehension. (Actually, it follows from some of my results in A variant of Mathias forcing that preserves $\text{ACA}_0$ [Arch. Math. Logic 51 (2012), 751–780; doi:10.1007/s00153-012-0297-4, arXiv:1110.6559, MR2975428] that $\Gamma$-COH does not imply arithmetic comprehension for any class of formulas $\Gamma$.)

The analysis of Jockush and Stephan actually allows us to characterize $\Sigma^0_1$-COH more precisely. Namely, $\Sigma^0_1$-COH is equivalent to the statement that:

• For every set $A$, there is a set $C$ such that either $C \subseteq^* X$ or $C \subseteq^* \bar{X}$ for every $A$-computable set $X$.

Further thought shows that $\Sigma^0_1$-COH is equivalent to the conjunction of COH with:

• For every set $A$, there are an infinite set $D$ and a sequence $\langle R_k \rangle$ of subsets of $D$ such that if $X$ is $A$-computable then there is a $k$ such that $X \cap D = R_k$

Or with the slight strengthening:

• For every set $A$, there are an infinite set $D$ and a sequence $\langle R_k \rangle$ of subsets of $D$ such that for all $i,j$, if $W^A_i \cap W^A_j \cap D = \varnothing$, then there is a $k$ such that $W^A_i \cap D \subseteq R_k$ and $W^A_j \cap D \subseteq \bar{R}_k$.

Note that if we require $D = \omega$, this statement last is equivalent to the Weak König Lemma. Therefore COH and $\Sigma^0_1$-COH are equivalent modulo $\text{WKL}_0$ (or even $\text{RCA}_0+\text{DNR}$).

I don't know whether COH and $\Sigma^0_1$-COH are equivalent over $\text{RCA}_0$, which boils down to asking whether COH proves the bulleted statements above. There is some evidence that suggests that COH might not imply $\Sigma^0_1$-COH over $\text{RCA}_0$. Namely, COH does not imply the uniform version of the last bulleted statement (where $k$ can be effectively computed from $i,j$) by a conservation result of Hirschfeldt and Shore from Combinatorial principles weaker than Ramsey's theorem for pairs [J. Symbolic Logic 72 (2007), 171–206; doi:10.2178/jsl/1174668391, MR2298478].

-
Thanks for the information. I've been thinking about the relation between $Σ_1^0-COH$ and $RT_2^2$ since $Σ_1^0-COH$ is stronger than $COH$. Would $RT_2^2$ also imply $Σ_1^0-COH$? – Jing Zhang Feb 18 '13 at 2:53
That's also unclear. Since $\mathrm{SRT}^2_2$ is rather orthogonal to cohesiveness, my guess is that $\mathrm{RT}^2_2$ implies $\Sigma^0_1$-COH only if COH implies $\Sigma^0_1$-COH (modulo some induction). – François G. Dorais Feb 18 '13 at 3:01
I guess I did not fully see the last two characterizations. What would the cohesive set be like? Thanks! – Jing Zhang Feb 19 '13 at 13:24
The last two bulleted statements are bridges that get a sequence of subsets $\langle R_k \rangle$ of a set $D$ to which we can apply COH and the resulting cohesive set is actually cohesive for all $A$-computable sets. The problem is that there is no $A$-computable listing of all $A$-computable sets, so we need something to gather these together so that we can apply COH; this is precisely what the next to last bulleted statement does. The last bulleted statement is to clarify the relationship with WKL. – François G. Dorais Feb 19 '13 at 14:11
You need to apply COH inside $D$, equivalently apply COH to the sets $R_k' = \lbrace i : d_i \in R_k \rbrace$ where $\langle d_i \rangle$ is the increasing enumeration of $D$. The analysis by Jockush and Stephan shows that $\Sigma^0_1$-COH is equivalent to the first bulleted statement. The equivalence is not obvious at all. – François G. Dorais Feb 19 '13 at 15:53