For a countable structure $\mathcal{S}$, let the cospectrum of $\mathcal{S}$ be the set $CS(\mathcal{S})$ of reals (non-uniformly) computable in every copy of $\mathcal{S}$ (we can also make sense of cospectra for uncountable structures, via forcing).

The cospectrum is clearly an invariant with respect to Muchnik reducibility (where the mass problem corresponding to a countable structure is the set of copies of the structure). Richter showed that in many cases the cospectrum is a silly invariant; for example, any two linear orders have the same cospectra (namely the set of computable reals). However, "higher-order" cospectra turn out to have more content. Namely, say that a structure $\mathcal{S}$ is:

  • self-escaping if for every copy $S$ of $\mathcal{S}$ there is some $f\le_TS$ such that $f$ escapes every $g\in CS(\mathcal{S}$.

  • self-dominating if for every copy $S$ of $\mathcal{S}$ there is some $f\le_TS$ such that $f$ dominates every $g\in CS(\mathcal{S}$.

It looks plausible that self-sufficiency considerations could be used to provide interesting separations with respect to Muchnik reducibility (and variants of self-sufficiency could be useful for other reducibilities); see e.g. Downey/Greenberg/Miller. However, I believe there is still very little known about this. In particular, I can't seem to separate the two kinds of "self-sufficiency" above (which seems a good test problem: if it's truly hard, then this is probably a silly notion to consider).

Question: Is there a structure which is self-$\mathfrak{E}$-sufficient but not self-$\mathfrak{D}$-sufficient?

  • $\begingroup$ Next time, your structure is $I$, then you have $CS(I)$. $\endgroup$ – Asaf Karagila Oct 11 '19 at 19:11
  • $\begingroup$ In particular it is now known - work of Andrews/Miller/S./Soskova, unpublished - that the non-self-dominating structure from DGM is also non-self-escaping. By way of motivation, this question grew out of considerations of cardinal characteristics of the continuum and their effective analogues; since "$\mathfrak{b}$ vs. $\mathfrak{d}$" is basically the easiest CCC question to resolve in both contexts, it seems a good one to start with here, even leaving aside the fact that it's already arisen implicitly in DGM. $\endgroup$ – Noah Schweber Oct 11 '19 at 20:01

Diamondstone, Greenberg and I showed that there is a structure with spectrum precisely the array non-computable degrees. Since this contains a minimal pair, its cospectrum is just the computable reals. Every A.N.C. computes an escaping function, but they do not all compute dominating functions, so this structure is self-escaping but not self-dominating.

Edit: Prior to that, Csima and Kalimullin showed that there's a structure with spectrum precisely the hyperimmune degrees, which will also do.

  • $\begingroup$ Perfect, thanks! $\endgroup$ – Noah Schweber Oct 12 '19 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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