# set theory – What logic characterizes relative intrinsic complexity in set recursion?

Short version: Is there an analogue of the Ash-Knight-Manasse-Slaman/Chisholm theorem for $$E$$-recursion?

Long version: I’m interested in “$$E$$-recursive structure theory,” but it’s not immediately clear to me what exactly that is; my question is an attempt to tease out one aspect of this.

One of the most basic results in classical computable structure theory is the AKMSC theorem, a particular case of which is the following:

Suppose $$mathfrak{A}$$ is a countably infinite structure in a finite language, and $$Usubseteqmathfrak{A}$$ is an automorphically fixed (=$$mathcal{L}_{infty,infty}$$-definable) set. Then the following are equivalent:

• Both $$U$$ and $$neg U$$ are definable in $$mathfrak{A}$$ by a computable infinitary $$Sigma_1$$ formula (with parameters).

• Whenever $$mathfrak{B}$$ is a copy of $$mathfrak{A}$$ with domain $$omega$$, $$U^mathfrak{B}$$ is computable relative to (the atomic diagram of) $$mathfrak{B}$$.

So we have a connection between relatively intrinsic c.e.-ness and definability in a certain logic. Carson/Johnson/Knight/Lange/McCoy/Wallbaum lifted this theorem to the setting of $$omega_1$$-recursion, and in fact the argument generalizes to all infinite regular cardinals (I suspect that the result holds for singular cardinals as well, but I’m leery of claiming that).

However, I don’t immediately see an analogous result for $$E$$-recursion. Specifically:

Is there a “definability-based” characterization, in terms of already-introduced logic(s), of when an automorphically fixed $$Usubseteqmathfrak{A}$$ has the property that for every $$mathfrak{B}congmathfrak{A}$$ we have $$U^mathfrak{B}le_Etc({mathfrak{B}}), overline{x}$$ for some finite tuple $$overline{x}in tc({mathfrak{B})$$?

(Call such a $$U$$ “relatively intrinsically $$E$$-recursive on $$mathfrak{A}$$.”)

• There is an easy upper bound, at least assuming that $$mathfrak{A}$$ has a constructible copy whose cardinality is a regular cardinal in the sense of $$L$$: for such a $$mathfrak{A}$$, if $$U$$ is relatively intrinsically $$E$$-recursive on $$mathfrak{A}$$ then both $$U$$ and $$neg U$$ are definable in $$mathfrak{A}$$ by $$Sigma_1$$ formulas in the sense of $$mathcal{L}_{vertmathfrak{A}vert^+,vertmathfrak{A}vert}$$. This follows from building a copy of $$mathfrak{A}$$ with domain $$L_{vertmathfrak{A}vert}$$ and applying the CJKLMW lifting of the AKMSC argument. However, the gap between $$alpha$$– and $$E$$-recursion is in general quite large, so this upper bound is probably terrible.
• If we try to run the usual forcing argument, things break down almost immediately. Conditions should be “simple” partial maps from transitive sets to the structure. In $$kappa$$-recursion theory for $$kappa$$ infinite and regular (including $$kappa=omega$$), it’s enough to just look at $$kappa$$-finite maps. Diving into the details what we really want is for the poset of such maps to be appropriately recursive in the structure itself. However, we now run into a major issue: in order to build a sufficiently generic copy of the structure in question in reality (as opposed to some generic extension of the universe) we need these simple maps to “cover” the structure in an appropriate sense, and – while this is trivial for $$kappa$$-recursion – there seems to be no reason for this to hold in the $$E$$-setting, even for reasonably natural structures.