3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Next time, your structure is $I$, then you have $CS(I)$. $\endgroup$
    – Asaf Karagila ♦
    Commented Oct 11, 2019 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
    Commented Oct 11, 2019 at 20:01

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Perfect, thanks! $\endgroup$
    – Noah Schweber
    Commented Oct 12, 2019 at 5:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .