Strongly reducible but not effectively interpretable

Question

A countable structure A is strongly reducible to a structure B if there is a uniform turing functional which, given a copy of the atomic diagram of B, computes a copy of the atomic diagram of A.

A is said to be effectively interpretable in B if A is strongly reducible to B via a computable functor from the category of copies of B to the category of copies of A.

• See this paper of Harrison-Trainor/Melnikov/Miller/Montalban for a precise definition (and note that this isn't the starting definition; that definition is given on page $3$, and its characterization by functors is Theorem 5). Roughly speaking, let $\mathcal{A}$ and $\mathcal{B}$ be respectively the categories whose objects are copies of $A$ and $B$ and whose morphisms are isomorphisms (in the usual sense); then a computable functor reducing $\mathcal{A}$ to $\mathcal{B}$ is a functor from $\mathcal{B}$ to $\mathcal{A}$ given by a pair of Turing functionals, one sending objects in $\mathcal{B}$ to objects in $\mathcal{A}$ and the other sending morphisms in $\mathcal{B}$ to morphisms in $\mathcal{A}$. The claim that this yields a strict strengthening of strong (= Medvedev) reducibility is made without proof on page $5$ of the linked paper.

What is an example of two countable structures A,B such that A is strongly reducible to B but A is not effectively interpretable in B?

Answer 1

There are a lot of such examples (may be not so natural). The easiest example is established here https://link.springer.com/article/10.1007/s10469-009-9037-1 (instead of effective interpretability we use the terms $\Sigma$-definability and $\Sigma$-reducibility).

The idea is to consider two objects from Computability Theory: the family CF of all (graphs of) total computable functions and the family InfCE of all infinite c.e. sets. To get the desired example it is enough now to realize the members of each family as existential types in two special structures (e.g., as in the Wehner's paper).

Roughly speaking, you can effectively interpret the family InfCE of all infinite c.e. sets having the family CF of all total computable functions. If a function is injective we can produce the range of this function (which is surely an infinite c.e. set), otherwise we can dump our output to $\omega$.

But the reverse is not true. Having some infinite c.e. set $W$ we can try to produce some total computable function $\varphi_e$, assuming that $W$ consists of the minimal stages on which $\varphi_e$ converges on different initial intervals of $\omega$: $$W\subseteq\{s:(\exists n)[s=(\mu t)(\forall x<n)[\varphi_{e,t}(x)\downarrow]]\}$$ (such set is infinite iff $\varphi_e$ is total). When we see that $W$ is not such a set, we can proceed our finite portion of $\varphi_e$ by zeros, but the output depends on the enumeration of $W$, so that this process can not give an effective interpretability. Here we have only strong reducibility of CF to InfCE.

Answer 2

I do not have a precise technical answer to the question. I do have some intuition to share which might help you build the example that you seek.

There is a notion of interpretation of varieties which seems to correspond to effective interpretability. Look up works of McKenzie (I forget the coauthors, maybe Baldwin or Valeriote or Burris?) for the details, but the idea is that for every operation f in the type of the one structure there is a first-order sentence in the language of the other structure that defines how f looks in the first structure. (I believe this is the same as computing the atomic diagram, but as constants aren't added in this process to help with the interpretation, I am unsure.)

This is uniform in that, given any structure B of the other type (say a Boolean Ring), one can interpret effectively a structure A of the first type (Boolean algebra seems like a nice choice here) using the same routine given by the system of first order formulas, and the prescriptions are independent of B.

However, there are many ways to interpret A specifically, especially if A or B have many automorphisms. I can imagine a non effective twist where A is strongly reducible to B, and A' is also reducible, but A' differs from A by a noncomputable isomorphism. It may further be that A' cannot be effectively interpreted in B because there is no specific map that the varietal interpretation can produce, because this would imply computability of a certain noncomputable map.

I am unsure if this idea is at odds with computing diagrams using a uniform Turing functional, but I imagine there is such a twist occurring that separates strong reducibility from effective interpretability.

Gerhard "Reminds Me Of Kunen Exercise" Paseman, 2018.08.11.