| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

4. Reducibility on a cone


    1. Add remark

      Problem 4.1.

      For each $X\in \omega^\omega$, we have $\Phi = \Phi_X$ is an equivalence relation on $\omega$, such that whenever $x \equiv_T y$ then $\Phi(x)$ is computably equivalent to $\Phi(y)$. Given $\Phi$ and $\Psi$ as above, define $\Phi \le^\triangledown \Psi$ if there exists $ c$ such that for every $y \ge_T c$, $\Phi(y)$ is computably reducible to $\Psi(y)$. What can we say about $\le^\triangledown$?


        • Add remark

          Problem 4.2.

          Given $A$ and $B$ classes of structures, define $A\le_{\text{eff}}^\triangledown B$ if there is a $c$ such that for every $y\ge_T c$, there is a computable $\Phi$ such that for all $i,j$, if $w_i^y, w_j^y$ are structures in $A$, then $\Phi^y(i), \Phi^y(j)\in B$ and $w_i^y \equiv w_j^y$ iff $\Phi^y(i) \equiv \Phi^y(j)$.

          Statement: every $A$ that is given by an $L_{\omega_1,\omega}$-sentence either has a bound on Scott rank, or universal under this reducibility.

          Is this statement equivalent to Vaught’s conjecture? (It is known that the statement implies Vaught’s conjecture.)

              Cite this as: AimPL: Invariant descriptive computability theory, available at http://aimpl.org/invdesccomp.