Below, by "structure" I mean "computable structure in a finite language with domain $\omega$," and by "sentence" I mean "finitary first-order sentence containing no instances of negation applied to non-atomic formulas."
Let $\mathcal{A}$ be a structure, $\varphi$ a sentence in the language of $\mathcal{A}$ with parameters (which are just natural numbers), $e\in\omega$, and $f\in \omega^\omega$. We define the relation $e$ realizes that $\mathcal{A}$ satisfies $\varphi$ with oracle $f$, or $\mathcal{A}\models_e^f\varphi$, as follows:
If $\varphi$ is atomic or negated atomic, then $\mathcal{A}\models_e^f\varphi$ iff $\mathcal{A}\models\varphi$ in the usual sense.
If $\varphi\equiv\psi\wedge\theta$ then $\mathcal{A}\models_e^f\varphi$ iff $e=\langle a,b\rangle$ with $\mathcal{A}\models_a^f\psi$ and $\mathcal{A}\models_b^f\theta$.
If $\varphi\equiv\psi_1\vee\psi_2$ then $\mathcal{A}\models_e^f\varphi$ iff $e=\langle i,b\rangle$ with $i\in\{1,2\}$ and $\mathcal{A}\models^f_b\psi_i$.
If $\varphi\equiv \exists x\psi(x)$ then $\mathcal{A}\models_e^f\varphi$ iff $e=\langle a,b\rangle$ with $\mathcal{A}\models_a^f\psi(b)$.
If $\varphi\equiv\forall x\psi(x)$ then $\mathcal{A}\models_e^f\varphi$ iff $e$ is an index for a partial Turing functional $\Phi_e$ such that $(i)$ $\Phi_e^f$ is total and $(ii)$ for each $a$ we have $\mathcal{A}\models^f_{\Phi_e^f(a)}\varphi(a)$.
I'll reserve "$\models$" for its usual (classical) meaning, and write "$\mathcal{A}\models_\star^f\varphi$" for "$\exists e(\mathcal{A}\models_e^f\varphi)$".
I'm interested in the following notion of relative complexity of structures: given structures $\mathcal{A},\mathcal{B}$ in possibily different languages, write $\mathcal{A}\le_{SK}\mathcal{B}$ iff there is a partial computable functional $\Theta$ and a partial computable function $p$ such that the following hold for every $e,f$:
If $\mathcal{A}\models\varphi$ then $p(\varphi)\downarrow$ and $\mathcal{B}\models p(\varphi)$.
If $\mathcal{A}\models\varphi$ and $\mathcal{B}\models_e^fp(\varphi)$ then $\mathcal{A}\models^f_{\Theta^f(e)}\varphi$.
Basically, $\mathcal{A}\le_{SK}\mathcal{B}$ means that oracle-effective truth in $\mathcal{A}$ can be computably reduced to oracle-effective truth in $\mathcal{B}$ uniformly in the oracle used. For example, $(\omega;<)$ is $\le_{SK}$-minimal since $\models$ and $\models_\star^\emptyset$ coincide for it; on the other hand, $(\omega;+,\times)$ is $\le_{SK}$-maximal since it can appropriately implement every computable structure.
I'm generally interested in the overall nature of the resulting degree structure $\mathfrak{SK}$, but to keep things concrete here are two test questions:
Question 1: Is $\mathfrak{SK}$ linear?
Question 2: Does $\mathfrak{SK}$ have finitely many classes?
I strongly suspect that the answer to each question is negative, but I don't see how to prove that. I'm also interested in the oracle-free version of the above, but I suspect that's trickier so I'm starting with the oracular version.
