MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Thanks! Should be $\Sigma^0_1$ – Jing Zhang Feb 16 '13 at 14:01
up vote 2 down vote accepted

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].

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.