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?

  • $\begingroup$ Can you say more precisely what you mean by a computable functor? It should be accompanied by a Turing functional for the isomorphisms? $\endgroup$ – Joel David Hamkins Aug 10 '18 at 14:31
  • $\begingroup$ Yes, exactly. This Turing functional can look both at the isomorphism itself and the diagrams of the two copies. $\endgroup$ – Rachael Alvir Aug 10 '18 at 14:33
  • $\begingroup$ Since the notion of computable functor isn't broadly known I've taken the liberty of adding a bit of context; feel free to roll back if this isn't desired. Incidentally I suspect one can cook up an example by taking $A$ to be something like the Slaman-Wehner structure and $B$ to be some structure with no computable copy, since the strong reduction sort of works by magic/accident (I don't see a way an automorphism of a copy of some noncomputably-presentable structure can transfer to an automorphism of a Slaman-Wehner type structure). But I don't know this area very well, so that's just a guess. $\endgroup$ – Noah Schweber Aug 10 '18 at 17:26

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.


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.

  • $\begingroup$ This is not the sort of thing that is being asked about here. One easy way to see that is to note that every structure with a computable copy is strongly reducible to any structure whatsoever. E.g. the semiring of natural numbers is strongly reucible to the infinite pure set, as is the Harrison order $\omega_1^{CK}\cdot (1+\eta)$. $\endgroup$ – Noah Schweber Aug 11 '18 at 18:22
  • $\begingroup$ Can you then use those examples to construct one that is not effectively interpretable? If not, why not? (Also, I'm having trouble seeing the "any structure whatsoever" part of your claim.) Gerhard "Helps Me Understand The Difficulties" Paseman, 2018.08.11. $\endgroup$ – Gerhard Paseman Aug 11 '18 at 18:29
  • $\begingroup$ Nope - every computably-presentable structure is also effectively interpretable in every structure. The point is that these are really computability-theoretic, not algebraic or even model-theoretic notions. There are a few reasons for this, looking at the interpretability side: (i) the formulas involved are infinitary, not finitary, first-order; (ii) that said, we also restrict their quantifier complexity; and (iii) the domain of the interpretation isn't the structure itself but the set of all finite tuples from the structure. To see how this works in action, consider the following: (cont'd) $\endgroup$ – Noah Schweber Aug 11 '18 at 18:31
  • $\begingroup$ Let $\mathcal{S}=\{*\}$ be the one-element pure set. I claim that $\mathcal{N}=(\mathbb{N}; +,\times)$ is effectively interpretable in $\mathcal{S}$. Here's how: I'm going to interpret the unique $n$-tuple from $\mathcal{S}$ - namely, $(*,*,*,...)$ ($n$ times) - as the natural number $n$. The graphs of $+$ and $\times$ are then given by computable infinitary formulas. Meanwhile we can't effectively interpret, say, the semiring of naturals together with a predicate naming the halting problem, since if we could the halting problem would be computable. (cont'd) $\endgroup$ – Noah Schweber Aug 11 '18 at 18:34
  • $\begingroup$ So the shift from first-order definability in the structure to computable infinitary definability in the "meta-structure" of tuples from the original structure is a huge one. We lose some power (namely, the power granted to us by arbitrary quantification) and gain some other power (namely, the power granted to us by infinitely long formulas). Another example of the change in behavior is the Slaman-Wehner (or similar) structure: this is a structure with no computable copy which however is effectively interpretable in every structure with no computable copy (so it's "minimal noncomputable"). $\endgroup$ – Noah Schweber Aug 11 '18 at 18:37

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.