Timeline for Strongly reducible but not effectively interpretable
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2018 at 8:31 | comment | added | Iskander Kalimullin | This is not true: " this is a structure with no computable copy which however is effectively interpretable in every structure with no computable copy". Moreover, this gives a difference between the strong reducibility and the effective interpretability. The Slaman-Wehner structure shows that the relation "$A$ is strongly reducible to $B$" is not $\Sigma^1_1$ as a class of reals, while the relation "$A$ is effectively interpretable in $B$" is $\Sigma^1_1$. | |
| Aug 16, 2018 at 1:12 | comment | added | Gerhard Paseman | @Noah, it expands my perspective somewhat. This is the first time (in my recollection) I have heard of Slaman-Wehner. I still think there is some resemblance between varietal interpretation and the effective interpretability of the post, but I am not claiming that the two notions of interpretation are alike. Even if effective interpretability is a more powerful (or general, or different) notion, the task remains to distinguish it from strong reducibility. If a non computable automorphism doesn't help, what will? Gerhard "Willing To Hear New Ideas" Paseman, 2018.08.15. | |
| Aug 15, 2018 at 17:31 | comment | added | Noah Schweber | Did those examples help? | |
| Aug 11, 2018 at 18:39 | comment | added | Noah Schweber | And yet another example of the model theory/computable structure theory divergence: effective interpretability exists on the level of structures, not theories. E.g. if $\mathcal{N}^*$ is any nonstandard model of true arithmetic, then (by Tennenbaum's theorem) $\mathcal{N}^*$ is not effectively interpretable in the $\mathcal{S}$ above even though it is elementarily equivalent to something which is. | |
| Aug 11, 2018 at 18:37 | comment | added | Noah Schweber | 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"). | |
| Aug 11, 2018 at 18:34 | comment | added | Noah Schweber | 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) | |
| Aug 11, 2018 at 18:31 | comment | added | Noah Schweber | 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) | |
| Aug 11, 2018 at 18:29 | comment | added | Gerhard Paseman | 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. | |
| Aug 11, 2018 at 18:22 | comment | added | Noah Schweber | 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)$. | |
| Aug 11, 2018 at 15:48 | history | answered | Gerhard Paseman | CC BY-SA 4.0 |