# Relations enumerable from positive information

Barbara F. Csima  Department of Pure Mathematics, University of Waterloo
<EMAIL_ADDRESS>,  Luke MacLean  Department of Pure Mathematics, University
of Waterloo<EMAIL_ADDRESS>and  Dino Rossegger  Department of
Mathematics, University of California, Berkeley and Institute of Discrete
Mathematics and Geometry, Technische Universität Wien<EMAIL_ADDRESS>
###### Abstract.

We study countable structures from the viewpoint of enumeration reducibility.
Since enumeration reducibility is based on only positive information, in this
setting it is natural to consider structures given by their positive atomic
diagram – the computable join of all relations of the structure. Fixing a
structure ${\mathcal{A}}$, a natural class of relations in this setting are
the relations $R$ such that $R^{\hat{\mathcal{A}}}$ is enumeration reducible
to the positive atomic diagram of $\hat{\mathcal{A}}$ for every
$\hat{\mathcal{A}}\cong{\mathcal{A}}$ – the _relatively intrinsically
positively enumerable (r.i.p.e.)_ relations. We show that the r.i.p.e.
relations are exactly the relations that are definable by $\Sigma^{p}_{1}$
formulas, a subclass of the infinitary $\Sigma^{0}_{1}$ formulas. We then
introduce a new natural notion of the jump of a structure and study its
interaction with other notions of jumps. At last we show that positively
enumerable functors, a notion studied by Csima, Rossegger, and Yu, are
equivalent to a notion of interpretability using $\Sigma^{p}_{1}$ formulas.

###### Key words and phrases:

enumeration reducibility, ripe relations, positive definability

###### 1991 Mathematics Subject Classification:

03C75, 03D45

The first author is supported by an NSERC Discovery grant. The work of the
third author was supported by the European Union’s Horizon 2020 Research and
Innovation Programme under the Marie Skłodowska-Curie grant agreement No.
101026834 — ACOSE. This project received support from the Austrian Agency for
International Cooperation in Education and Research under grant WTZ-BG11/2019.

While in computable structure theory countable structures are classically
studied up to Turing reducibility, researchers have successfully used
enumeration reducibility to both contribute to the classical study and develop
a beautiful theory on its own. One example of a contribution to classical
theory is Soskov’s work on degree spectra and co-spectra [15] which allowed
him to show that there is a degree spectrum of a structure such that the set
of degrees whose $\omega$-jump is in this spectrum is not the spectrum of a
structure [14]. Another example is Kalimullin’s study of reducibilities
between classes of structures [8] where he studied enumeration reducibility
versions of Muchnik and Medvedev reducibility between classes of structures.
This topic has also been studied by Knight, Miller, and Vanden Boom [9] and
Calvert, Cummins, Knight, and Miller [2]. There appears to be a rich theory on
these notions with interesting questions on the relationship between the
enumeration reducibility and the classical versions. In this article we
develop a novel approach to study relations that are enumeration reducible to
every copy of a given structure.

More formally, say that given a countable relational structure
${\mathcal{A}}$, a relation $R$ is _relatively intrinsically positively
enumerable_ (_r.i.p.e._) in ${\mathcal{A}}$ if for every copy ${\mathcal{B}}$
of ${\mathcal{A}}$ and every enumeration of the basic relations on
${\mathcal{B}}$, we can compute an enumeration of $R^{\mathcal{B}}$. We obtain
a syntactic classification of the r.i.p.e. relations using the infinitary
logic $L_{\omega_{1}\omega}$. 1.6 shows that the r.i.p.e. relations on a
structure are precisely those that are definable by computable infinitary
$\Sigma_{1}^{0}$ formulas in which neither negations nor implications occur.

This classification is motivated by a related classification of the r.i.c.e.
relations. A relation $R$ on a structure ${\mathcal{A}}$ is relatively
intrinsically computably enumerable (r.i.c.e.) if for every
${\mathcal{B}}\cong{\mathcal{A}}$, $R^{\mathcal{B}}$ is c.e. relative to the
atomic diagram of ${\mathcal{B}}$. The following classification of r.i.c.e.
relations is a special case of a theorem by Ash, Knight, Manasse and Slaman
[1] and, independently, Chisholm [3]: A relation is r.i.c.e. in a structure
${\mathcal{A}}$ if and only if it is definable in ${\mathcal{A}}$ by a
computable $\Sigma^{0}_{1}$ formula in the logic $L_{\omega_{1}\omega}$.

Since this result there has been much work on r.i.c.e. relations and related
concepts. For a summary, see Fokina, Harizanov, and Melnikov [6]. One
particularly interesting generalization of r.i.c.e. relations is due to
Montalbán [12]. He extended the definition of r.i.c.e. relations from
relations on $\omega^{n}$ to $\omega^{<\omega}$ and to sequences of relations,
obtaining a classification similar to the one given in [1, 3]. This extension
allows the development of a rich theory such as an intuitive definition of the
jump of a structure, and an effective version of interpretability with a
category theoretic analogue: A structure ${\mathcal{A}}$ is effectively
interpretable in a structure ${\mathcal{B}}$ if and only if there is a
computable functor from ${\mathcal{B}}$ to ${\mathcal{A}}$ as given in
Harrison-Trainor, Melnikov, Miller, and Montalbán [7]. For a complete
development of this theory see Montalbán [11]. The main goal of this article
to develop a similar theory for r.i.p.e. relations.

Let ${\mathcal{A}}$ be a countable structure in relational language $L$. We
might assume that the universe of ${\mathcal{A}}$ is $\omega$, and in order to
measure its computational complexity, identify it with the set
$=^{\mathcal{A}}\oplus\neq^{\mathcal{A}}\oplus\bigoplus_{R_{i}\in
L}R_{i}^{\mathcal{A}}$ which we call $P({\mathcal{A}})$, the _positive diagram
of ${\mathcal{A}}$_. It is Turing equivalent to the standard definition of the
atomic diagram of a structure, which can be viewed as the set
$=^{\mathcal{A}}\oplus\neq^{\mathcal{A}}\oplus\bigoplus_{R_{i}\in
L}R_{i}^{\mathcal{A}}\oplus\overline{R_{i}}^{\mathcal{A}}$. Now, a relation
$R\subseteq\omega^{<\omega}$ is r.i.c.e. if for every copy
${\mathcal{B}}\cong{\mathcal{A}}$, $R^{\mathcal{B}}$ is c.e. in
$P({\mathcal{B}})$. The r.i.p.e. relations are the natural analogue to the
r.i.c.e. relations for enumeration reducibility. Recall that a set of natural
numbers $A$ is enumeration reducible to $B$, $A\leq_{e}B$ if there exists a
c.e. set $\Psi$ consisting of pairs $\langle D,x\rangle$ where $D$ is a finite
set under some fixed coding such that

$A=\Psi^{B}=\\{x:D\subseteq B\land\langle D,x\rangle\in\Psi\\}.$

Enumeration reducibility allows us to formally define the notion of a r.i.p.e.
relation.

######  Definition 0.1.

Let ${\mathcal{A}}$ be a structure. A relation $R\subseteq A^{<\omega}$ is
_relatively intrinsically positively enumerable_ in ${\mathcal{A}}$, short
r.i.p.e., if, for every copy $({\mathcal{B}},R^{\mathcal{B}})$, of
$({\mathcal{A}},R)$, $R^{\mathcal{B}}\leq_{e}P({\mathcal{B}})$. The relation
is uniformly relatively intrinsically positively enumerable in
${\mathcal{A}}$, if the above enumeration reducibility is uniform in the
copies of ${\mathcal{A}}$, that is, if there is a fixed enumeration operator
$\Psi$ such that $R^{\mathcal{B}}=\Psi^{P({\mathcal{B}})}$ for every copy
${\mathcal{B}}$ of ${\mathcal{A}}$.

The study of the computability theoretic properties of structures with respect
to enumeration reducibility is an active research topic; see Soskova and
Soskova [16] for a summary of results in this area.

###  0.1. Structure of the paper

In Section 1 we show that a relation is r.i.p.e. in a structure
${\mathcal{A}}$ if and only if it is definable by a $\Sigma_{1}^{p}$ formula
in the language of ${\mathcal{A}}$, that is, a computable infinitary
$\Sigma_{1}^{0}$ formula in which neither negations nor implications occur. We
continue by defining a notion of reducibility between r.i.p.e. relations and
exhibiting a complete relation. Towards the end of Section 1 we study sets of
natural numbers r.i.p.e. in a given structure and show that these are
precisely those sets whose degrees lie in the structures co-spectrum, the set
of enumeration degrees below every copy of the structure.

Section 2 is devoted to the study of the positive jump of a structure. We
define the positive jump and study its degree theoretic properties. The main
result of this section is that the enumeration degree spectrum of the positive
jump of a structure is the set of jumps of enumeration degrees of the
structure. The main tool to prove this result are r.i.p.e. generic
enumerations which are studied at the beginning of the section. To finish the
section we compare the enumeration degree spectra obtained by applying various
operations on structures such as the positive jump, the classical jump and the
totalization.

In Section 3 we define an effective version of interpretability using
$\Sigma^{p}_{1}$ formulas, positive interpretability. We show that a structure
${\mathcal{A}}$ is positively interpretable in a structure ${\mathcal{B}}$ if
and only if there is a positive enumerable functor from the isomorphism class
of ${\mathcal{B}}$ to the isomorphism class of ${\mathcal{A}}$. Positive
enumerable functors and related effectivizations of functors were studied by
Csima, Rossegger and Yu [5]. Positive interpretability allows for a useful
strengthening that preserves most properties of a structure, positive bi-
interpretability. We show that two structures ${\mathcal{A}}$ and
${\mathcal{B}}$ are positive bi-interpretable if and only if their isomorphism
classes are enumeration adjoint, that is there is an adjoint equivalence
between $Iso({\mathcal{A}})$ and $Iso({\mathcal{B}})$ witnessed by enumeration
operators.

##  1\. First results on r.i.p.e. relations

In our proofs we will often build structures in stages by copying increasing
pieces of finite substructures of a given structure ${\mathcal{A}}$. The
following definitions will be useful for this.

######  Definition 1.1.

Given an $\mathcal{L}$-structure ${\mathcal{A}}$ and $\overline{a}\in
A^{<\omega}$, let $P({\mathcal{A}})\restriction\overline{a}$ denote the
positive diagram of the substructure of ${\mathcal{A}}$ with universe
$\overline{a}$ in the restriction of $\mathcal{L}$ to the first
$|\overline{a}|$ relation symbols.

######  Definition 1.2.

Let ${\mathcal{A}}$ be an $\mathcal{L}$-structure and $\overline{a}=\langle
a_{0},\dots,a_{s}\rangle\in A^{s}$. The set $P_{{\mathcal{A}}}(\overline{a})$
is the pullback of $P({\mathcal{A}})\restriction\overline{a}$ along the index
function of $\overline{a}$, i.e.,

$\langle i,n_{0},\dots,n_{r_{i}}\rangle\in
P_{{\mathcal{A}}}(\overline{a})\Leftrightarrow\langle i,a_{n_{0}},\dots
a_{n_{r_{i}}}\rangle\in P({\mathcal{A}})\restriction\overline{a}.$

The main feature of 1.2 is that if we approximate the positive diagram of a
structure ${\mathcal{A}}$ in stages by considering larger and larger tuples,
i.e.,
$\lim_{s\in\omega}P({\mathcal{A}})\restriction\overline{a}_{s}=P({\mathcal{A}})$,
then the limit of $P_{{\mathcal{A}}}(\overline{a}_{s})$ gives a structure
isomorphic to ${\mathcal{A}}$. We will use this fact to obtain generic copies
of a given structure.

We denote by $\Psi_{e}$ the $e^{th}$ enumeration operator in a fixed
computable enumeration of all enumeration operators and by $\Psi_{e,s}$ its
stage $s$ approximation. Without loss of generality we make the common
assumption that $\Psi_{e,s}$ is finite and does not contain pairs $\langle
n,D\rangle>s$. Notice that $\Psi_{e,s}$ itself is an enumeration operator. In
our proofs we also frequently argue that a set $A$ is enumeration reducible to
a set $B$ by using a characterization of enumeration reducibility due to
Selman [13].

######  Theorem 1.3 (Selman [13]).

For any $A,B\subseteq\omega$

$A\leq_{e}B\quad\text{ iff }\quad\forall X[B\text{ is c.e. in }X\Rightarrow
A\text{ is c.e. in }X]$

We refer the reader to Cooper [4] for a proof of this result and further
background on enumeration reducibility and enumeration degrees.

Notice that by 0.1 $({\mathcal{A}},R)$ is technically not a first order
structure as $R\subseteq\omega^{<\omega}$. We may however still think of it as
a first order structure in the language expanded by relation symbols
$(Q_{i})_{i\in\omega}$, each $Q_{i}$ of arity $i$, where
$Q_{i}^{\mathcal{A}}=\\{\overline{a}\in A^{n}:\overline{a}\in
R^{\mathcal{A}}\\}$. The positive diagrams $P({\mathcal{A}},R^{\mathcal{A}})$
and $P({\mathcal{A}},(Q_{i}^{\mathcal{A}})_{i\in\omega})$ are enumeration
equivalent.

###  1.1. A syntactic characterization

The main purpose of this section is to show that being r.i.p.e. in a structure
${\mathcal{A}}$ is equivalent to being definable by infinitary formulas in
${\mathcal{A}}$ of the following type.

######  Definition 1.4.

A _positive computable infinitary $\Sigma_{1}^{p}$ formula_ is a formula of
the infinitary logic $L_{\omega_{1}\omega}$ of the form

$\varphi(\overline{x})\equiv\operatorname*{\bigvee\mkern-15.0mu\bigvee}_{i\in
I}\exists\overline{y}_{i}\varphi_{i}(\overline{x},\overline{y}_{i})$

where each $\varphi_{i}$ is a finite conjunct of atomic formulas, and the
index set $I$ is c.e..

Notice that the above definition includes all c.e. disjunctions of finitary
$\Sigma^{0}_{1}$ formulas without negation and implication symbols, as every
such formula is equivalent to a finite disjunction of conjunctions with each
existential quantifier occurring in front of the conjunctions.

######  Definition 1.5.

A relation $R\subseteq\omega^{<\omega}$ is _$\Sigma^{p}_{1}$ -definable with
parameters $\overline{c}$_ in a structure ${\mathcal{A}}$ if there exists a
uniformly computable sequence of $\Sigma^{p}_{1}$ formulas
$(\varphi_{i}(x_{1},\dots,x_{i},y_{1},\dots,y_{|c|}))_{i\in\omega}$ such that
for all $\overline{a}\in\omega^{<\omega}$

$\overline{a}\in
R\Leftrightarrow{\mathcal{A}}\models\varphi_{|\overline{a}|}(\overline{a},\overline{c}).$

######  Theorem 1.6.

Let ${\mathcal{A}}$ be a structure and $R\subseteq A^{<\omega}$ a relation on
it. Then the following are equivalent:

  1. (i)

$R$ is relatively intrinsically positively enumerable in ${\mathcal{A}}$,

  2. (ii)

$R$ is $\Sigma^{p}_{1}$-definable in ${\mathcal{A}}$ with parameters.

###### Proof.

Assuming (ii), there is a uniformly computable sequence
$(\varphi_{i}(\overline{x},\overline{z}))_{i\in\omega}$ of $\Sigma_{1}^{p}$
formulas where each $\varphi_{i}$ is of the form
$\operatorname*{\bigvee\mkern-15.0mu\bigvee}_{j\in\omega}\exists\overline{y}_{i,j}\psi_{i,j}(\overline{x},\overline{y}_{i,j},\overline{z})$
with the property that for every ${\mathcal{B}}\cong{\mathcal{A}}$ there is a
tuple $\overline{c}\in\omega^{|\overline{z}|}$ such that for all $i\in\omega$
and $\overline{a}\in\omega^{i}$,
${\mathcal{B}}\models\varphi_{i}(\overline{a},\overline{c})$ if and only if
$\overline{a}\in R^{{\mathcal{B}}}$. Recall that each $\psi_{i,j}$ is a finite
conjunction of atomic formulas, i.e.,
$\psi_{i,j}=\theta_{1}(\overline{x},\overline{y}_{i,j},\overline{z})\land\dots\land\theta_{n}(\overline{x},\overline{y}_{i,j},\overline{z})$
for some $n\in\omega$. For $\theta(\overline{x})$ an atomic formula, let
$\ulcorner\theta(\overline{a})\urcorner$ be the function mapping
$\theta(\overline{a})$ to its code in the positive diagram of a structure. For
example, if $\theta(\overline{x})=R_{i}(x_{3},x_{5})$, then
$\ulcorner\theta(\overline{a})\urcorner=\langle i+2,\langle
a_{3},a_{5}\rangle\rangle$ for $\overline{a}\in\omega^{<\omega}$. Consider the
set
$X^{\overline{a},\overline{b},\overline{c}}_{i,j}=\\{\ulcorner\theta_{k}(\overline{a},\overline{b},\overline{c})\urcorner:k<n\\}$.
Clearly, $X^{\overline{a},\overline{b},\overline{c}}_{i,j}\subseteq
P({\mathcal{A}})$ if and only if
${\mathcal{A}}\models\psi_{i,j}(\overline{a},\overline{b},\overline{c})$ for
any $L$-structure ${\mathcal{A}}$. We define an enumeration operator $\Psi$ by
enumerating all pairs
$\langle\overline{a},X_{i,j}^{\overline{a},\overline{b},\overline{c}}\rangle$
into $\Psi$. We have that

$\displaystyle\overline{a}\in\Psi^{P({\mathcal{B}})}$
$\displaystyle\Leftrightarrow\exists\langle\overline{a},X_{|\overline{a}|,j}^{\overline{a},\overline{b},\overline{c}}\rangle\in\Psi\land
X_{|\overline{a}|,j}^{\overline{a},\overline{b}\overline{c}}\subseteq
P({\mathcal{B}})$
$\displaystyle\Leftrightarrow{\mathcal{B}}\models\exists\overline{y}_{|\overline{a}|,j}\psi_{|\overline{a}|,j}(\overline{a},\overline{y}_{|\overline{a}|,j},\overline{c})$
$\displaystyle\Leftrightarrow{\mathcal{B}}\models\varphi_{|\overline{a}|}(\overline{a},\overline{c})$

and thus $R$ is r.i.p.e.

To show that (i) implies (ii) we build an enumeration
$g:\omega\rightarrow{\mathcal{A}}$ by constructing a nested sequence of tuples
$\\{\overline{p}_{s}\\}_{s\in\omega}\subseteq A^{<\omega}$ and letting
$g=\bigcup_{s}\overline{p}_{s}$. We then define
${\mathcal{B}}=g^{-1}({\mathcal{A}})$. Our goal is to produce a
$\Sigma^{p}_{1}$ definition of $R^{\mathcal{B}}$. To obtain it we try to force
during the construction that
$R^{\mathcal{B}}=g^{-1}(R)\neq\Psi_{e}^{P({\mathcal{B}})}$. As $R$ is r.i.p.e.
this will fail for some $e$ and we will use the failure to get the syntactic
definition.

To construct ${\mathcal{B}}$ we do the following. Let $p_{0}$ be the empty
sequence. At stage $s+1=2e+1$ if the $e$-th element of $A$ is not already in
$\overline{p}_{s}$ then we let
$\overline{p}_{s+1}=\overline{p}_{s}^{\frown}e$. Otherwise let
$\overline{p}_{s+1}=\overline{p}_{s}$. This guarantees that $g$ is onto. At
stage $s+1=2e$ we try to force $\Psi_{e}^{P({\mathcal{B}})}\not\subseteq
g^{-1}(R)$ for which we need a tuple $\langle
j_{1},\dots,j_{l}\rangle\in\Psi_{e}^{P({\mathcal{B}})}$ with $\langle
g(j_{1}),\dots,g(j_{l})\rangle\not\in R$. To do this we ask if there is an
extension $\overline{q}$ of $\overline{p}_{s}$ in the set

$Q_{e}=\\{\overline{q}\in A^{<\omega}:\exists l,j_{1},\dots
j_{l}<|\overline{q}|\,[\langle
j_{1},\dots,j_{l}\rangle\in\Psi_{e}^{P_{\mathcal{A}}(\overline{q})}\text{ and
}\langle q_{j_{1}},\dots,q_{j_{l}}\rangle\not\in R]\\}$

If there is one let $\overline{p}_{s+1}=\overline{q}$, otherwise let
$\overline{p}_{s+1}=\overline{p}_{s}$. This concludes the construction.

If at any stage $s+1=2e$ we succeed in defining
$\overline{p}_{s+1}=\overline{q}$ for some $\overline{q}\in Q_{e}$ then we
will have made $\Psi_{e}^{P({\mathcal{B}})}\neq g^{-1}(R)$. But by our
assumption this must fail for some $e\in\omega$. For this $e$, at stage
$s+1=2e$ we will not have been able to find an extension of $\overline{p}_{s}$
in $Q_{e}$. We will use this to give a $\Sigma^{p}_{1}$ definition of $R$ with
parameters $\overline{p}_{s}$.

Notice that if there is some $\overline{q}\supseteq\overline{p}_{s}$ and sub-
tuple $\langle q_{j_{1}},\dots,q_{j_{l}}\rangle$ such that $\langle
j_{1},\dots,j_{l}\rangle\in\Psi_{e}^{P_{\mathcal{A}}(\overline{q})}$ then we
must have $\langle q_{j_{1}},\dots,q_{j_{l}}\rangle\in R$ or else we will have
that $\overline{q}\in Q_{e}$. We now show that $R$ is equal to the set

$\displaystyle S=\\{\langle q_{j_{1}},\dots,q_{j_{l}}\rangle\in
A^{<\omega}:\text{ for some }\overline{q}\in A^{<\omega}\text{ and
}l,j_{1},\dots,j_{l}<|\overline{q}|\text{ satisfying
}\overline{q}\supseteq\overline{p}_{s}$ $\displaystyle\text{ and }\langle
j_{1},\dots,j_{l}\rangle\in\Psi_{e}^{P_{\mathcal{A}}(\overline{q})}\\}$

By the previous paragraph $S\subseteq R$. If $\overline{a}\in R$ then there
are indices $j_{1},\dots,j_{|\overline{a}|}$ such that $\overline{a}=\langle
g(j_{1}),\dots g(j_{|\overline{a}|})\rangle$ and so if we take a long enough
initial segment of $g$ it will witness the fact that $\overline{a}\in S$. Fix
an enumeration $(\varphi_{i}^{at})_{i\in\omega}$ of all atomic formulas where
without loss of generality the free variables of $\varphi_{i}^{at}$ are a
subset of $\\{x_{0},\dots,x_{i}\\}$. The following is a $\Sigma^{p}_{1}$
definition of $S$

$\operatorname*{\bigvee\mkern-15.0mu\bigvee}_{C\subset_{\text{fin}}\omega}\bigvee_{\langle
j_{1},\dots,j_{|\overline{a}|}\rangle\in
W_{e}^{C}}\exists\,\overline{q}\supseteq\overline{p}_{s}\,[\langle
q_{j_{1}},\dots,q_{j_{|\overline{a}|}}\rangle=\overline{a}\,\wedge\,\bigwedge_{i\in
C}[\varphi^{at}_{i}]\frac{q_{0}}{x_{0}}\cdots\frac{q_{|\overline{q}|}}{x_{|\overline{q}|}}]$

where the latter half of the formula is simply saying that $C\subseteq
P_{\mathcal{A}}(\overline{q})$. ∎

######  Corollary 1.7.

Let ${\mathcal{A}}$ be a structure and $R\subseteq A^{<\omega}$ be a relation
on it. Then the following are equivalent:

  1. (i)

$R$ is uniformly relatively intrinsically positively enumerable in
${\mathcal{A}}$,

  2. (ii)

$R$ is $\Sigma_{1}^{p}$-definable in ${\mathcal{A}}$ without parameters.

###### Proof.

For $(i)\Rightarrow(ii)$ we mimic the proof of Theorem 1.6. Let $\Psi_{e}$ be
the fixed enumeration operator such that
$R^{{\mathcal{B}}}=\Psi_{e}^{P({\mathcal{B}})}$ and $Q_{e}$ as above. Note
that no $\overline{q}$ can be in $Q_{e}$ and so we mimic the construction of
our set $S$ with $\overline{p}_{s}$ being the empty tuple.

For $(ii)\Rightarrow(i)$ we again mimic the same direction in 1.6 excluding
the parametrizing tuple $\overline{c}$ to make the process uniform. ∎

###  1.2. R.i.p.e. completeness

Similar to the study of computably enumerable sets we want to investigate
notions of completeness for r.i.p.e. relations on a given structure. Before we
obtain a natural example of a r.i.p.e. complete relation we have to define a
suitable notion of reduction.

######  Definition 1.8.

Given a structure ${\mathcal{A}}$ and two relations $P,R\subseteq
A^{<\omega}$, we say that $P$ is _positively intrinsically one reducible_ to
$R$, and write $P\operatorname{\leq_{p1}}R$, if for all
${\mathcal{B}}\cong{\mathcal{A}}$ $P({\mathcal{B}})\oplus
P^{\mathcal{B}}\leq_{1}P({\mathcal{B}})\oplus R^{\mathcal{B}}$.

######  Proposition 1.9.

Positive intrinsic one reducibility ($\operatorname{\leq_{p1}}$) is a
reducibility.

###### Proof.

Let ${\mathcal{A}}$ be a structure with relations $P,Q,R\subseteq
A^{<\omega}$. It is easy to see that $\operatorname{\leq_{p1}}$ is reflexive,
since for any structure ${\mathcal{B}}\cong{\mathcal{A}}$ we have that
$P({\mathcal{B}})\oplus P^{\mathcal{B}}\leq_{1}P({\mathcal{B}})\oplus
P^{\mathcal{B}}$, which means $P\operatorname{\leq_{p1}}P$. To see that it is
transitive assume that $P\operatorname{\leq_{p1}}R$ and
$R\operatorname{\leq_{p1}}Q$ and let ${\mathcal{B}}\cong{\mathcal{A}}$. By
assumption $P({\mathcal{B}})\oplus
P^{\mathcal{B}}\leq_{1}P({\mathcal{B}})\oplus
R^{\mathcal{B}}\leq_{1}P({\mathcal{B}})\oplus Q^{\mathcal{B}}$ and so
$P\operatorname{\leq_{p1}}Q$. ∎

######  Definition 1.10.

Fix a structure ${\mathcal{A}}$. A relation $R\subseteq A^{<\omega}$ is
_r.i.p.e. complete_ if $R$ is r.i.p.e. and for every r.i.p.e. relation $P$ on
${\mathcal{A}}$, $P\operatorname{\leq_{p1}}R$.

The most natural way to obtain a complete set is to follow the construction of
the Kleene set in taking the computable join of all r.i.p.e. sets. The result
is a relation $R\subseteq\omega\times A^{<\omega}$ which can be seen as a
uniform sequence of r.i.p.e. relations in the sense that there is a
enumeration operator $\Psi$ such that ${\Psi^{{\mathcal{A}}}}^{[i]}=R_{i}$.
The issue is that this does not behave well under isomorphism. However, this
can be easily overcome using the following coding. Given a relation
$R\subseteq\omega\times A^{<\omega}$, we can identify it with a subset
$R^{\prime}\subseteq A^{<\omega}$ as follows. For any two elements $b,c\in A$
let

$\overbrace{b\dots b}^{i\times}c\overline{a}\in R^{\prime}\iff\langle
i,\overline{a}\rangle\in R.$

One can now easily see that $R$ is a uniform sequence of r.i.p.e. relations if
and only if the so obtained relation $R^{\prime}$ is uniformly r.i.p.e.

We can now give a natural candidate for a r.i.p.e. complete relation.

######  Definition 1.11.

Let $\varphi_{i,j}^{\Sigma^{p}_{1}}$ be the $i$th formula with free variables
$x_{1},\dots,x_{j}$ in a computable enumeration of all $\Sigma^{p}_{1}$
formulas. The _positive Kleene predicate_ relative to ${\mathcal{A}}$ is
$\vec{K}^{\mathcal{A}}_{p}=\left(K^{\mathcal{A}}_{i}\right)_{i\in\omega}$,
where

$K^{{\mathcal{A}}}_{i}=\bigcup_{j\in\omega}\\{\overline{a}\in
A^{j}:{\mathcal{A}}\models\varphi^{\Sigma_{1}^{p}}_{i,j}(\overline{a})\\}.$

Notice that we defined the positive Kleene predicate as a sequence of
relations instead of a single relation. It is slightly more convenient as we
do not have to deal with coding. Another alternative definition would be to
break down the sequence even further and let the Kleene predicate be the
sequence

$(\\{\overline{a}:{\mathcal{A}}\models\varphi_{i,j}^{\Sigma_{1}^{p}}(\overline{a})\\})_{\langle
i,j\rangle\in\omega}$

so that $({\mathcal{A}},\vec{K}_{p}^{\mathcal{A}})$ is a first order
structure. However, as all of these definitions are computationally equivalent
these distinctions are irrelevant for our purpose.

######  Proposition 1.12.

The positive Kleene predicate $\vec{K}_{p}^{\mathcal{A}}$ is uniformly
r.i.p.e., and r.i.p.e. complete.

###### Proof.

Since $\vec{K}^{\mathcal{A}}_{p}$ is defined in a $\Sigma_{1}^{p}$ way without
parameters we can use Corollary 1.7 to see that it is uniformly relatively
intrinsically positively enumerable. Let $R$ be any relation on
${\mathcal{A}}$ of arity $a_{R}$. Notice that $R^{\mathcal{B}}$ is trivially
$\Sigma_{1}^{p}$ definable, and so there is a formula
$\varphi_{i,a_{R}}^{\Sigma_{1}^{P}}$ such that $\overline{a}\in
R^{\mathcal{B}}\Leftrightarrow{\mathcal{B}}\models\varphi_{i,a_{R}}^{\Sigma_{1}^{p}}(\overline{a})$.
This shows that $P({\mathcal{B}})\oplus
R^{\mathcal{B}}\leq_{1}P({\mathcal{B}})\oplus\vec{K}_{p}^{\mathcal{B}}$. ∎

###  1.3. R.i.p.e. sets of natural numbers

Our above discussion of sequences of r.i.p.e. relations allows us to code sets
of natural numbers as r.i.p.e. relations.

######  Definition 1.13.

A set $X\subseteq\omega$ is _r.i.p.e. in a structure ${\mathcal{A}}$_ if the
relation $R_{X}=X\times\emptyset$ is a r.i.p.e. relation, i.e., if the
following relation is r.i.p.e.:

$\\{\overbrace{b\dots b}^{i\times}c:i\in X,b,c\in A\\}$

A natural question is which sets of natural numbers are r.i.p.e. in a given
structure. One characterization can be derived directly from the definitions:
The sets $X$ such that $X\leq_{e}P({\mathcal{B}})$ for all
${\mathcal{B}}\cong{\mathcal{A}}$. Another one can be given using co-spectra,
a notion defined by Soskov [15]. Intuitively, the co-spectrum of a structure
${\mathcal{A}}$ is the maximal ideal in the enumeration degrees such that
every member of it is below every copy of ${\mathcal{A}}$. More formally.

######  Definition 1.14.

The _co-spectrum_ of a structure ${\mathcal{A}}$ is

$Co({\mathcal{A}})=\bigcap_{{\mathcal{B}}\cong{\mathcal{A}}}\\{\mathbf{d}:\mathbf{d}\leq
deg_{e}(P({\mathcal{B}}))\\}.$

Let us point out that Soskov’s definition of co-spectra appears to be
different from ours. We will prove in Section 2 that the two definitions are
equivalent. Given a tuple $\overline{a}$ in some structure ${\mathcal{A}}$ let
$\Sigma_{1}^{p}\text{-}tp_{\mathcal{A}}(\overline{a})$ be the set of positive
finitary $\Sigma_{1}^{0}$ formulas true of ${\mathcal{A}}$. The equivalence of
Item 1 and Item 3 in 1.15 is the analogue to a well-known theorem of Knight
[10] for total structures.

######  Theorem 1.15.

The following are equivalent for every structure ${\mathcal{A}}$ and
$X\subseteq\omega$.

  1. (1)

$X$ is r.i.p.e. in ${\mathcal{A}}$

  2. (2)

$deg_{e}(X)\in Co({\mathcal{A}})$

  3. (3)

$X$ is enumeration reducible to
$\Sigma_{1}^{p}\text{-}tp_{\mathcal{A}}(\overline{a})$ for some tuple
$\overline{a}\in A^{<\omega}$.

###### Proof.

If $deg_{e}(X)\in Co({\mathcal{A}})$, then for all
${\mathcal{B}}\cong{\mathcal{A}}$, $X\leq_{e}P({\mathcal{B}})$. Given an
enumeration of $X$, enumerate $b^{n}c$ into $R_{X}$ for all elements $b,c\in
B$ whenever you see $n$ enter $X$. The relation $R_{X}$ clearly witnesses that
$X$ is r.i.p.e. in ${\mathcal{A}}$. This shows that Item 2 implies Item 1. On
the other hand if $X$ is r.i.p.e. in ${\mathcal{A}}$, then given any
$B\cong{\mathcal{A}}$ and an enumeration of $R_{X}^{\mathcal{B}}$ build a set
$S$ by enumerating $n$ into $S$ whenever you see $b^{n}c$ enumerated into
$R_{X}^{\mathcal{B}}$ for any two elements $b,c\in B$. Clearly $n\in S$ if and
only if $n\in X$ and thus Item 1 implies Item 2.

To see that Item 3 implies Item 2 assume that $X$ is enumeration reducible to
the positive $\Sigma_{1}$ type of a tuple $\overline{b}$ in any copy
${\mathcal{B}}$ of ${\mathcal{A}}$. As the
$\Sigma_{1}^{p}\text{-}tp_{\mathcal{B}}(\overline{b})$ is enumeration
reducible to $P({\mathcal{B}})$, by transitivity $X\leq_{e}P({\mathcal{B}})$
for every ${\mathcal{B}}\cong{\mathcal{A}}$ and thus $deg_{e}(X)\in
Co({\mathcal{A}})$. At last, we show that Item 1 implies Item 3. Assume that
$X$ is r.i.p.e. in ${\mathcal{A}}$. Then there is a computable enumeration of
$\Sigma^{p}_{1}$ formulas $\psi_{n}$ with parameters $\overline{p}$ such that
for some $\overline{a}\in A^{<\omega}$, $n\in
X\Leftrightarrow{\mathcal{A}}\models\psi_{n}(\overline{a})$. Simultaneously
enumerate $\Sigma^{p}_{1}\text{-}tp_{\mathcal{A}}(\overline{a})$ and the
disjuncts in the formulas $\psi_{n}$. Whenever you see a disjunct of
$\psi_{n}$ that is also in
$\Sigma^{p}_{1}\text{-}tp_{\mathcal{A}}(\overline{a})$ enumerate $n$. This
gives an enumeration of $X$ given an enumeration of
$\Sigma^{p}_{1}\text{-}tp_{\mathcal{A}}(\overline{a})$ and thus
$X\leq_{e}\Sigma^{p}_{1}\text{-}tp_{\mathcal{A}}(\overline{a})$ as required. ∎

##  2\. The positive jump and degree spectra

In this section we compare various definitions of the jump of a structure with
respect to their enumeration degree spectra, a notion first studied by Soskov
[15]. Before we introduce it, let us recall the definition of the jump of an
enumeration degree.

######  Definition 2.1.

Let $K_{A}=\\{x\,|\,x\in\Psi^{A}_{x}\\}$. The _enumeration jump_ of a set $A$
is $J_{e}(A):=A\oplus\overline{K}_{A}$. The jump of an $e$-degree
$\mathbf{a}=\text{deg}_{e}(A)=\\{X:X\equiv_{e}A\\}$ is
$\mathbf{a}^{\prime}=\text{deg}_{e}(J_{e}(A))$.

######  Definition 2.2.

The _positive jump_ of a structure ${\mathcal{A}}$ is the structure

$PJ({\mathcal{A}})=({\mathcal{A}},\overline{\vec{K}^{{\mathcal{A}}}_{p}})=({\mathcal{A}},(\overline{K^{{\mathcal{A}}}_{i}})_{i\in\omega}).$

We are interested in the degrees of enumerations of $P({\mathcal{A}})$ and
$P(PJ({\mathcal{A}}))$. To be precise, let $f$ be an enumeration of $\omega$,
that is, a surjective mapping $\omega\rightarrow\omega$, and for
$X\subseteq\omega^{<\omega}$ let

$f^{-1}(X)=\\{\langle x_{1},\dots\rangle:(f(x_{1}),\dots,)\in X\\}.$

Then, given a structure ${\mathcal{A}}$ let
$f^{-1}({\mathcal{A}})=(\omega,f^{-1}(=),f^{-1}(\neq),f^{-1}(R_{1}^{\mathcal{A}}),f^{-1}(R_{2}^{\mathcal{A}}),\dots)$.
This definition differs from the definition given in Soskov [15] where
$f^{-1}({\mathcal{A}})$ means what we will denote as
$P(f^{-1}({\mathcal{A}}))$, i.e.,

$=\oplus\neq\oplus f^{-1}(=)\oplus
f^{-1}(\neq)\oplus\bigoplus_{i\in\omega}f^{-1}(R_{i}^{\mathcal{A}}).$

Using this notation we can see that for any structure ${\mathcal{A}}$, and any
enumeration $f$ of $\omega$ we have that $PJ(f^{-1}({\mathcal{A}}))$ is the
structure
$(f^{-1}({\mathcal{A}}),\overline{\vec{K}_{p}^{f^{-1}({\mathcal{A}})}})$. Thus

$P(PJ(f^{-1}({\mathcal{A}})))=f^{-1}(=)\oplus
f^{-1}(\neq)\oplus\bigoplus_{j\in\omega}\overline{K_{j}^{f^{-1}({\mathcal{A}})}}\oplus\bigoplus_{i\in\omega}R^{f^{-1}({\mathcal{A}})}_{i}.$

If we instead apply the enumeration to $PJ({\mathcal{A}})$ we will get the
structure $f^{-1}(PJ({\mathcal{A}}))$. Now, for every relation $R$ on
${\mathcal{A}}$, $R^{f^{-1}({\mathcal{A}})}=f^{-1}(R^{\mathcal{A}})$ and thus
$\overline{K_{j}^{f^{-1}({\mathcal{A}})}}=f^{-1}\left(\overline{K_{j}^{{\mathcal{A}}}}\right)$.
So $P(f^{-1}(PJ({\mathcal{A}})))=P(PJ(f^{-1}({\mathcal{A}})))$.

###  2.1. R.i.p.e. generic presentations

######  Definition 2.3.

Let $A^{*}=\\{\sigma\in A^{<\omega}:(\forall i\neq
j<|\sigma|)[\sigma(i)\neq\sigma(j)]\\}$. We say that $\gamma\in A^{*}$
_decides_ an upwards closed subset $R\subseteq A$ if $\gamma\in R$ or
$\sigma\not\in R$ for all $\sigma\supseteq\gamma$. A $1{-}1$ function
$g:\omega\rightarrow{\mathcal{A}}$ is a _r.i.p.e.-generic enumeration_ , if
for every r.i.p.e. subset $R\subseteq A^{*}$ there is an initial segment of
$g$ that decides $R$. ${\mathcal{B}}$ is a _r.i.p.e.-generic presentation_ of
${\mathcal{A}}$ if it is the pull-back along a r.i.p.e.-generic enumeration of
$P({\mathcal{A}})$.

The following lemma is an analogue of the well-known result that there is a
$\Delta^{0}_{2}$ 1-generic.

######  Lemma 2.4.

Every structure ${\mathcal{A}}$ has a r.i.p.e.-generic enumeration $g$ such
that $Graph(g)\leq_{e}P(PJ({\mathcal{A}}))$. In particular,
$P(g^{-1}(PJ({\mathcal{A}})))\leq_{e}P(PJ({\mathcal{A}}))$.

###### Proof.

Fix a $P({\mathcal{A}})$-computable enumeration $(S_{i})_{i\in\omega}$ of all
r.i.p.e. subsets of ${\mathcal{A}}$. We define our enumeration $g$ to be the
limit of an increasing sequence of strings $\\{\overline{p}_{s}\in
A^{*}:s\in\omega\\}$. The strings $\overline{p}_{s}$ are defined as follows:

  1. (1)

$\overline{p}_{-1}=\operatorname{\langle\rangle}$

  2. (2)

To define $\overline{p}_{s+1}$, check if there is a $\overline{q}\in S_{s+1}$
such that $\overline{q}\supset\overline{p}_{s}$. If there is let
$\overline{p}_{s+1}$ be the least such tuple, otherwise define
$\overline{p}_{s+1}=\overline{p}_{s}$.

Notice that $g=\bigcup_{s\in\omega}\overline{p}_{s}$ is onto as for every
$n\in\omega$, $D_{n}=\\{\overline{a}\in A^{*}:\exists j<|\overline{a}|\
\overline{a}(j)=n\\}$ is a dense r.i.p.e. subset of $A^{*}$. Thus there is an
$e$ such that $S_{e}=D_{n}$ and $\overline{p}_{e}$ forces into $D_{n}$. Thus,
$g$ is a $1{-}1$ r.i.p.e.-generic enumeration of ${\mathcal{A}}$.

The set
$\\{\overline{p}:\exists\overline{q}\supset\overline{p}\,,\overline{q}\in
S_{e}\\}$ is $\Sigma_{1}^{p}$-definable in ${\mathcal{A}}$ and so enumerable
from $P(PJ({\mathcal{A}}))$, which contains $P({\mathcal{A}})$. The coset
$\\{\overline{p}:\forall\overline{q}\supset\overline{p},\overline{q}\not\in
S_{e}\\}$ is co-r.i.p.e. and so enumerable from
$\overline{\vec{K}^{\mathcal{A}}_{p}}$. Hence $P(PJ({\mathcal{A}}))$ will be
able to decide when a tuple $\overline{p}_{s}$ belongs to the upward closure
of $S_{e}$. Thus $Graph(g)\leq_{e}P(PJ({\mathcal{A}}))$.

If we can enumerate the graph of $g$ and also $PJ({\mathcal{A}})$, then to
enumerate $g^{-1}(PJ({\mathcal{A}}))$, we wait for something of the form
$(x,g(x))\in Graph(g)$ to appear with $g(x)\in PJ({\mathcal{A}})$ and
enumerate $x$ into the corresponding slice of $g^{-1}(PJ({\mathcal{A}}))$. ∎

R.i.p.e. generic presentations have many useful properties. One of them is
that they are minimal in the sense that the only sets enumeration below a
r.i.p.e. generic presentation are the r.i.p.e. sets.

######  Lemma 2.5.

If ${\mathcal{B}}$ is a r.i.p.e.-generic presentation of ${\mathcal{A}}$, then
$X\subseteq\omega$ is r.i.p.e. in ${\mathcal{B}}$ if and only if
$X\leq_{e}P({\mathcal{B}})$.

###### Proof.

If $X$ r.i.p.e. then it is enumerable from $P({\mathcal{B}})$ by definition.
Assume $X$ is enumerable from $P({\mathcal{B}})$. Then
$X=\Psi^{P({\mathcal{B}})}_{e}$ for some $e$. Recall the set $Q_{e}$ from 1.6
which we know to be r.i.p.e. because we gave a $\Sigma_{1}^{p}$ description of
it.

$Q_{e}=\\{\overline{q}\in A^{<\omega}:\exists l,j_{1},\dots
j_{l}<|\overline{q}|\,[\langle
j_{1},\dots,j_{l}\rangle\in\Psi_{e}^{P_{\mathcal{B}}(\overline{q})}\text{ and
}\langle q_{j_{1}},\dots,q_{j_{l}}\rangle\not\in X]\\}.$

Now because ${\mathcal{B}}$ is r.i.p.e.-generic, there is some tuple $\langle
0,\dots,k-1\rangle$ that decides $Q_{e}$. $\langle 0,\dots,k-1\rangle\not\in
Q_{e}$ or we would contradict the fact that $X=\Psi^{P({\mathcal{B}})}_{e}$
and so $\langle 0,\dots,k-1\rangle$ forms the parameterizing tuple
$\overline{p}_{s}$ from the set $S$ in 1.6. ∎

Another useful property is that the degree of the positive jump of a r.i.p.e.
generic agrees with the enumeration jump of the degree of their positive
diagram.

######  Proposition 2.6.

Let ${\mathcal{A}}$ be a structure. For an arbitrary enumeration $f$ of
${\mathcal{A}}$, let ${\mathcal{B}}=f^{-1}({\mathcal{A}})$. Then
$P(PJ({\mathcal{B}}))\leq_{e}J_{e}(P({\mathcal{B}}))$. Furthermore, if
${\mathcal{B}}$ is a r.i.p.e.-generic presentation then
$P(PJ({\mathcal{B}}))\equiv_{e}J_{e}(P({\mathcal{B}}))$.

###### Proof.

Recall that
$PJ({\mathcal{B}})=({\mathcal{B}},\overline{\vec{K}_{p}^{{\mathcal{B}}}})$ and
$J_{e}(P({\mathcal{B}}))=P({\mathcal{B}})\oplus\overline{K}_{P({\mathcal{B}})}$,
so to show that $P(PJ({\mathcal{B}}))\leq_{e}J_{e}(P({\mathcal{B}}))$ it is
sufficient to show that
$\overline{\vec{K}_{p}^{{\mathcal{B}}}}\leq_{e}\overline{K}_{P({\mathcal{B}})}$.
As $\vec{K}_{p}^{{\mathcal{B}}}$ is r.i.p.e.,
$\vec{K}_{p}^{{\mathcal{B}}}=\Psi^{P({\mathcal{B}})}_{e}$ for some $e$. Thus
$\overline{\vec{K}_{p}^{{\mathcal{B}}}}$ appears as a slice of $\\{\langle
x,i\rangle:x\not\in\Psi^{P({\mathcal{B}})}_{i}\\}$ and hence
$\overline{\vec{K}_{p}^{{\mathcal{B}}}}\leq_{e}\\{\langle
x,i\rangle:x\not\in\Psi^{P({\mathcal{B}})}_{i}\\}$. The latter set is
$m$-equivalent to $\overline{K}_{P({\mathcal{B}})}$ and thus
$\overline{\vec{K}_{p}^{{\mathcal{B}}}}\leq_{e}\overline{K}_{P({\mathcal{B}})}$.

It remains to show that $J_{e}(P({\mathcal{B}}))\leq_{e}P(PJ({\mathcal{B}}))$
if ${\mathcal{B}}$ is r.i.p.e.-generic. For every $e$ consider the set

$R_{e}=\\{\overline{q}\in
B^{*}:e\in\Psi_{e}^{P_{\mathcal{B}}(\overline{q})}\\}.$

Note that the $R_{e}$ are closed upwards as subsets of $B^{*}$ and r.i.p.e..
So since ${\mathcal{B}}$ is r.i.p.e.-generic, for every $e$ there is an
initial segment of $B^{*}$ that either is in $R_{e}$ or such that no extension
of it is in $R_{e}$. The set $Q_{e}=\\{\overline{p}\in
B^{*}:\forall(\overline{q}\supseteq\overline{p})(\overline{q}\not\in
R_{e})\\}$ of elements in $B^{*}$ that are non-extendible in $R_{e}$ is
co-r.i.p.e. Also note that these sets are uniform in $e$, that is, given $e$
we can compute the indices of $R_{e}$ and $Q_{e}$ as r.i.p.e., respectively,
co-r.i.p.e. subsets of ${\mathcal{B}}$. Thus, given an enumeration of
$P(PJ({\mathcal{B}}))$ we can enumerate $P({\mathcal{B}})$ and the sets
$Q_{e}$ and $R_{e}$. By genericity for all $e\in\omega$ there is an initial
segment of $\overline{b}$ of $B$ such that either $\overline{b}\in Q_{e}$ or
$\overline{b}\in R_{e}$. So whenever we see such a $\overline{b}$ in $Q_{e}$
we enumerate $e$ and thus obtain an enumeration
$\overline{K}_{P({\mathcal{B}})}$. ∎

The above properties of r.i.p.e. generics are very useful to study how the
enumeration degree spectra of structures and their positive jumps relate.

######  Definition 2.7 ([15]).

Given a structure ${\mathcal{A}}$, define the set of enumerations of a
structure
$Enum({\mathcal{A}})=\\{P({\mathcal{B}}):{\mathcal{B}}=f^{-1}({\mathcal{A}})\text{
for }f\text{ an enumeration of }\omega\\}$. Further, let the _enumeration
degree spectrum_ of ${\mathcal{A}}$ be the set

$eSp({\mathcal{A}})=\\{d_{e}(P({\mathcal{B}})):P({\mathcal{B}})\in
Enum({\mathcal{A}})\\}$

If $\mathbf{a}$ is the least element of $eSp({\mathcal{A}})$, then
$\mathbf{a}$ is called the _enumeration degree_ of ${\mathcal{A}}$.

As mentioned after 1.14, Soskov’s definition of the co spectrum of a structure
was slightly different [15]. He defined the co-spectrum of a structure
${\mathcal{A}}$ as the set

$\\{\mathbf{d}:\forall(\mathbf{a}\in
eSp({\mathcal{A}}))\,\mathbf{d}\leq\mathbf{a}\\}.$

We now show that the two definitions are equivalent.

######  Proposition 2.8.

For every structure ${\mathcal{A}}$,
$Co({\mathcal{A}})=\\{\mathbf{d}:\forall(\mathbf{a}\in
eSp({\mathcal{A}}))\mathbf{d}\leq_{e}\mathbf{a}\\}$.

###### Proof.

First note that
$\\{\mathbf{d}:\forall(\mathcal{C}\cong{\mathcal{A}})\mathbf{d}\leq
deg_{e}(P(\mathcal{C}))\\}\supseteq\\{\mathbf{d}:\forall(\mathbf{a}\in
eSp({\mathcal{A}}))\mathbf{d}\leq\mathbf{a}\\}$ as every $P(\mathcal{C})$ is
the pullback of ${\mathcal{A}}$ along an injective enumeration.

On the other hand for any enumeration $f:\omega\to\omega$,
$f^{-1}({\mathcal{A}})/f^{-1}(=)\cong{\mathcal{A}}$. Consider the substructure
${\mathcal{B}}$ of $f^{-1}({\mathcal{A}})$ consisting of the least element in
every $f^{-1}(=)$ equivalence class. Since
$f^{-1}({\mathcal{A}})/f^{-1}(=)\cong{\mathcal{A}}$, we get that
${\mathcal{B}}\cong{\mathcal{A}}$. As $P(f^{-1}({\mathcal{A}}))$ contains both
$f^{-1}(=)$ and $f^{-1}(\neq)$ we can compute an enumeration of
$B\oplus\overline{B}$ from any enumeration of $P(f^{-1}({\mathcal{A}}))$ and
thus also the graph of its principal function $p_{B}$. Let
$\mathcal{C}=p_{B}^{-1}({\mathcal{B}})$. Then $\mathcal{C}\cong{\mathcal{A}}$,
and $P(\mathcal{C})\leq_{e}P(f^{-1}({\mathcal{A}}))$. Thus,

$\\{\mathbf{d}:\forall(\mathbf{a}\in
eSp({\mathcal{A}}))\mathbf{d}\leq\mathbf{a}\\}=\\{\mathbf{d}:\forall(\mathcal{C}\cong{\mathcal{A}})\mathbf{d}\leq
deg_{e}(P(\mathcal{C}))\\}=Co({\mathcal{A}}).$

∎

A set $A$ is said to be _total_ if $A\equiv_{e}A\oplus\overline{A}$. An
enumeration degree is said to be total if it contains a total set, and a
structure ${\mathcal{A}}$ is total if $P(f^{-1}({\mathcal{A}}))$ is a total
set for every enumeration $f$.

######  Proposition 2.9.

For every structure ${\mathcal{A}}$, $PJ({\mathcal{A}})$ is a total structure.

###### Proof.

First, note that we have the following equality for arbitrary relations $R$
and enumerations $f$.

$x\in f^{-1}(\overline{R})\Leftrightarrow f(x)\in\overline{R}\Leftrightarrow
f(x)\not\in R\Leftrightarrow x\not\in f^{-1}(R)\Leftrightarrow
x\in\overline{f^{-1}(R)}$

Recall that for every $R_{i}$ in the language of ${\mathcal{A}}$,
$R_{i}^{\mathcal{A}}$ is r.i.p.e. and that

$P(f^{-1}(PJ({\mathcal{A}})))=f^{-1}(=)\oplus f^{-1}(\neq)\oplus
f^{-1}(\overline{\vec{K}^{{\mathcal{A}}}_{p}})\oplus
f^{-1}(R^{\mathcal{A}}_{1})\oplus\cdots$

and we observe that all $R_{i}^{\mathcal{A}}$ are trivially r.i.p.e.,
uniformly in $i$, so in particular
$\overline{f^{-1}(R_{i}^{\mathcal{A}})}\leq_{e}\overline{f^{-1}(\vec{K}^{\mathcal{A}}_{p})}=f^{-1}(\overline{\vec{K}^{\mathcal{A}}_{p}})$.
Also,
$f^{-1}(\vec{K}^{\mathcal{A}}_{p})\leq_{e}P(f^{-1}({\mathcal{A}}))\leq_{e}P(f^{-1}(PJ({\mathcal{A}}))$.
∎

We will now see that the positive jump of a structure jumps, in the sense that
the enumeration degree spectrum of the positive jump is indeed the set of
jumps of the degrees in the enumeration degree spectrum of the structure. The
following version of a Theorem by Soskova and Soskov [17] is essential to our
proof.

######  Theorem 2.10 ([17, Theorem 1.2]).

Let $B$ be an arbitrary set of natural numbers. There exists a total set $F$
such that

$B\leq_{e}F\quad\text{and}\quad J_{e}(B)\equiv_{e}J_{e}(F).$

######  Theorem 2.11.

For any structure ${\mathcal{A}}$,

$eSp(PJ({\mathcal{A}}))=\\{\mathbf{a^{\prime}}:\mathbf{a}\in
eSp({\mathcal{A}})\\}$

###### Proof.

To show that $\\{\mathbf{a^{\prime}}:\mathbf{a}\in
eSp({\mathcal{A}})\\}\subseteq eSp(PJ({\mathcal{A}}))$, consider an arbitrary
enumeration $f$ of $\omega$ and let ${\mathcal{B}}=f^{-1}({\mathcal{A}})$.
Then from Proposition 2.6 we know that
$P(PJ({\mathcal{B}}))\leq_{e}J_{e}(P({\mathcal{B}}))$. Note that
$P(PJ({\mathcal{B}}))=P(PJ(f^{-1}({\mathcal{A}})))=P(f^{-1}(PJ({\mathcal{A}})))$,
and $d_{e}(P(f^{-1}(PJ({\mathcal{A}})))\in eSp(PJ({\mathcal{A}}))$. Since the
enumeration jump is always total and enumeration degree spectra are closed
upwards with respect to total degrees, $d_{e}(J_{e}(P({\mathcal{B}})))\in
eSp(PJ({\mathcal{B}}))$.

To show $eSp(PJ({\mathcal{A}}))\subseteq\\{\mathbf{a^{\prime}}:\mathbf{a}\in
eSp({\mathcal{A}})\\}$, let us look at $P(f^{-1}(PJ({\mathcal{A}})))$ for some
enumeration $f$ of $\omega$, and again write
${\mathcal{B}}=f^{-1}({\mathcal{A}})$ so that
$P(f^{-1}(PJ({\mathcal{A}})))=P(PJ({\mathcal{B}}))$. Since $PJ({\mathcal{A}})$
is a total structure, we know that $P(PJ({\mathcal{B}}))$ is total. By 2.4 we
can use $P(PJ({\mathcal{B}}))$ to enumerate a r.i.p.e.-generic enumeration $g$
of ${\mathcal{B}}$ such that
$P(g^{-1}(PJ({\mathcal{B}})))\leq_{e}P(PJ({\mathcal{B}}))$. Then, letting
$\mathcal{C}=g^{-1}({\mathcal{B}})$ and using the latter part of Proposition
2.6 we know that $J_{e}(P(\mathcal{C}))\equiv_{e}P(PJ(\mathcal{C}))$ which
makes $J_{e}(P(\mathcal{C}))\leq_{e}P(PJ({\mathcal{B}}))$. Using 2.10 there is
a total set $F$ such that $P(\mathcal{C})\leq_{e}F$ and
$J_{e}(F)\equiv_{e}J_{e}(P(\mathcal{C}))\leq_{e}P(PJ({\mathcal{B}}))$. As $F$
and $P(PJ({\mathcal{B}}))$ are total, we have that
$F^{\prime}\leq_{T}P(PJ({\mathcal{B}}))$.

We can now apply the relativized jump inversion theorem for the Turing degrees
to get a set $Z\geq_{T}F$ such that
$Z^{\prime}\equiv_{T}P(PJ({\mathcal{B}}))$. For this $Z$, we have that
$\iota(deg(Z^{\prime}))=d_{e}(J_{e}(\chi_{Z}))=d_{e}(P(PJ(({\mathcal{B}})))\in
eSp(PJ({\mathcal{A}}))$ and $d_{e}(P({\mathcal{B}}))\leq d_{e}(F)\leq
d_{e}(\chi_{Z})$. Since $\chi_{Z}$ is total and enumeration degree spectra are
upwards closed in the total degrees, this means $d_{e}(\chi_{Z})\in
eSp({\mathcal{B}})\subseteq eSp({\mathcal{A}})$. So in particular,
$d_{e}(J_{e}(\chi_{Z}))=d_{e}(P(PJ({\mathcal{B}})))\in\\{\mathbf{a}^{\prime}:\mathbf{a}\in
eSp({\mathcal{A}})\\}$. ∎

We now compare the enumeration degree spectrum of the positive jump of a
structure ${\mathcal{A}}$ with the spectrum of the original structure and the
spectrum of its traditional jump. The latter is the spectrum of the structure
obtained by adding the sequence of relations

$\vec{K}^{{\mathcal{A}}}=(\bigcup_{j\in\omega}\\{\overline{a}\in\omega^{j}:{\mathcal{A}}\models\varphi_{i,j}^{\Sigma_{1}^{c}}(\overline{a})\\})_{i\in\omega}$

where $\varphi_{i,j}^{\Sigma_{1}^{c}}(\overline{x})$ is the $i^{th}$ formula
with $j$ free variables in a fixed computable enumeration of all computable
infinitary $\Sigma_{1}^{0}$ formulas. Let
$J({\mathcal{A}})=({\mathcal{A}},\vec{K}^{{\mathcal{A}}})$ denote the
traditional jump of ${\mathcal{A}}$. This notion of a jump was defined by
Montalbán [12] and is similar to several other notions of jumps of structures
that arose independently such as Soskova’s notion using Marker extensions [17]
or Stukachev’s version using $\Sigma$-definability [18].

We will also consider the structure ${\mathcal{A}}^{+}$, the totalization of
${\mathcal{A}}$ given by

${\mathcal{A}}^{+}=(A,(R_{i}^{\mathcal{A}},\overline{R_{i}^{\mathcal{A}}})_{i\in\omega}).$

We will not compare the enumeration degree spectra directly but instead the
sets of enumerations. This gives more insight than comparing the degree
spectra as we can make use of the following analogues to Muchnik and Medvedev
reducibility for enumeration degrees. Given
$\mathfrak{A},\mathfrak{B}\subseteq P(\omega)$ we say that
$\mathfrak{A}\leq_{we}\mathfrak{B}$, $\mathfrak{A}$ is _weakly enumeration
reducible_ to $\mathfrak{B}$, if for every $B\in\mathfrak{B}$ there is
$A\in\mathfrak{A}$ such that $A\leq_{e}B$. We say that
$\mathfrak{A}\leq_{se}\mathfrak{B}$, $\mathfrak{A}$ is _strongly enumeration
reducible_ to $\mathfrak{B}$, if there is an enumeration operator $\Psi$ such
that for every $B\in\mathfrak{B}$, $\Psi^{B}\in\mathfrak{A}$.

It is not hard to see that given an enumeration of ${\mathcal{A}}^{+}$ one can
enumerate an enumeration of $J({\mathcal{A}})$ and the converse holds
trivially. We thus have the following.

######  Proposition 2.12.

For every structure ${\mathcal{A}}$,
$deg_{e}(J({\mathcal{A}}))=deg_{e}({\mathcal{A}}^{+})$. In particular
$Enum(J({\mathcal{A}}))\equiv_{se}Enum({\mathcal{A}}^{+})$.

###### Proof.

By replacing every subformula of the form $\neg R_{i}(x_{1},\dots,x_{m})$ by
the formula $\overline{R}_{i}(x_{1},\dots,x_{m})$ we get a $\Sigma^{p}_{1}$
formula in the language of ${\mathcal{A}}^{+}$. Similarly, given a
$\Sigma^{p}_{1}$ formula in the language of ${\mathcal{A}}^{+}$ we can obtain
a $\Sigma^{c}_{1}$ formula in the language of ${\mathcal{A}}$ by substituting
subformulas of the form $\overline{R}_{i}(x_{1},\dots,x_{m})$ with $\neg
R_{i}(x_{1},\dots,x_{m})$. Indeed we get a computable bijection between the
$\Sigma^{p}_{1}$ formulas in the language of ${\mathcal{A}}^{+}$ and the
$\Sigma^{c}_{1}$ formulas of ${\mathcal{A}}$. Thus
$J({\mathcal{A}})\equiv_{e}({\mathcal{A}}^{+},\vec{K}_{p}^{{\mathcal{A}}^{+}})$,
but
${\mathcal{A}}^{+}\equiv_{e}({\mathcal{A}}^{+},\vec{K}_{p}^{{\mathcal{A}}^{+}})$
given the first equivalence. All of these equivalence are witnessed by fixed
enumeration operators and thus
$Enum(J({\mathcal{A}}))\equiv_{se}Enum({\mathcal{A}}^{+})$. ∎

Proposition 2.12 is not very surprising, as adding a r.i.c.e. set such as
$\vec{K}^{\mathcal{A}}$ to the totalization of ${\mathcal{A}}$ won’t change
its enumeration degree. We will thus consider a slightly different notion of
jump by adding the coset of $\vec{K}^{\mathcal{A}}$:

$T({\mathcal{A}})=({\mathcal{A}},\overline{\vec{K}^{{\mathcal{A}}}})$

Clearly $T({\mathcal{A}})\equiv_{T}J({\mathcal{A}})$; however, the two sets
are not necessarily enumeration equivalent as the following two propositions
show.

######  Proposition 2.13.

Let ${\mathcal{A}}$ be a structure. For every presentation $\hat{\mathcal{A}}$
of ${\mathcal{A}}$,
$P(\hat{\mathcal{A}})\leq_{e}D(\hat{\mathcal{A}})=P(\hat{\mathcal{A}}^{+})\leq_{e}PJ(\hat{\mathcal{A}})\leq_{e}T(\hat{\mathcal{A}})$.
In particular

$Enum({\mathcal{A}})\leq_{se}Enum({\mathcal{A}}^{+})\leq_{se}Enum(PJ({\mathcal{A}}))\leq_{se}Enum(T({\mathcal{A}})).$

###### Proof.

Straightforward from the definitions. ∎

######  Proposition 2.14.

There is a structure ${\mathcal{A}}$ such that

$Enum({\mathcal{A}})\not\geq_{we}Enum({\mathcal{A}}^{+})\not\geq_{we}Enum(PJ({\mathcal{A}}))\not\geq_{we}Enum(T({\mathcal{A}})).$

###### Proof.

Sacks showed that there is an incomplete c.e. set $X$ of high Turing degree.
Thus, $X$ has enumeration degree $deg_{e}(X)=\mathbf{0}_{e}$ and
$deg_{T}(X^{\prime})=\mathbf{0}^{\prime\prime}$. Let ${\mathcal{A}}$ be the
graph coding $X$ as follows. ${\mathcal{A}}$ contains a single element $a$
with a loop, i.e. $aE^{{\mathcal{A}}}a$ and one circle of length $n+1$ for
every $n\in\omega$. Let $y$ be the least element in ${\mathcal{A}}$ that is
part of the cycle of length $n+1$. If $n\in X$, then connect $a$ to $y$, i.e.,
$aE^{\mathcal{A}}y$. This finishes the construction.

As $X$ is c.e., ${\mathcal{A}}$ has enumeration degree $\mathbf{0}_{e}$.
However, $\mathbf{0}_{e}\not\in eSp({\mathcal{A}}^{+})$, as
${\mathcal{A}}^{+}$ has enumeration degree
$deg_{e}(X\oplus\overline{X})>\mathbf{0}_{e}$. So, in particular
$Enum({\mathcal{A}})\not\geq_{we}Enum({\mathcal{A}}^{+})$. By 2.11 the
enumeration degree of $PJ({\mathcal{A}})$ is $\mathbf{0}^{\prime}_{e}$ and
$\mathbf{0}^{\prime}_{e}\ni\emptyset^{\prime}\oplus\overline{\emptyset^{\prime}}>_{e}X\oplus\overline{X}$,
so $Enum({\mathcal{A}}^{+})\not\geq_{we}Enum(PJ({\mathcal{A}}))$. For the last
inequality notice that both $T({\mathcal{A}})$ and $PJ({\mathcal{A}})$ are
total structures and that by the analogue of 2.11 for the traditional jumps of
structures we have that the enumeration degree of $T({\mathcal{A}})$ is
$deg_{e}(\emptyset^{\prime\prime}\oplus\overline{\emptyset^{\prime\prime}})$.
As mentioned above the enumeration degree of $PJ({\mathcal{A}})$ is
$\mathbf{0}^{\prime}_{e}$,
$\emptyset^{\prime}\oplus\overline{\emptyset^{\prime}}\in\mathbf{0}^{\prime}_{e}$,
and
$\emptyset^{\prime}\oplus\overline{\emptyset^{\prime}}<_{e}\emptyset^{\prime\prime}\oplus\overline{\emptyset^{\prime\prime}}$.
So, in particular,
$Enum(PJ({\mathcal{A}}))\not\geq_{we}Enum(T({\mathcal{A}}))$. ∎

For total structures the traditional notion of the jump and the positive jump
coincide.

######  Proposition 2.15.

Let ${\mathcal{A}}$ be a structure, then
$Enum(PJ({\mathcal{A}}^{+}))\equiv_{se}Enum(T({\mathcal{A}}))$ and
$eSp(PJ({\mathcal{A}}^{+}))=eSp(T({\mathcal{A}}))$.

###### Proof.

This proof is similar to the proof of Proposition 2.12. Mutatis mutandis. ∎

##  3\. Functors

When comparing structures with respect to their enumerations it is natural to
want to use only positive information. Csima, Rossegger, and Yu [5] introduced
the notion of a positive enumerable functor which uses only the positive
diagrams of structures. Reductions based on this notion preserve desired
properties such as enumeration degree spectra of structures.

Recall that a functor $F$ from a class of structures $\mathfrak{C}$ to a class
$\mathfrak{D}$ maps structures in $\mathfrak{C}$ to structures in
$\mathfrak{D}$ and isomorphisms $f:{\mathcal{A}}\to{\mathcal{B}}$ to
isomorphisms $F(f):F({\mathcal{A}})\to F({\mathcal{B}})$ with the property
that $F(id_{\mathcal{A}})=id_{F({\mathcal{A}})}$ and $F(f\circ g)=F(f)\circ
F(g)$ for all isomorphisms $f$ and $g$ and structures
${\mathcal{A}}\in\mathfrak{C}$.

######  Definition 3.1.

A functor $F:\mathfrak{C}\to\mathfrak{D}$ is _positive enumerable_ if there is
a pair $(\Psi,\Psi_{*})$ where $\Psi$ and $\Psi_{*}$ are enumeration operators
such that for all ${\mathcal{A}},{\mathcal{B}}\in\mathfrak{C}$

  1. (1)

$\Psi^{P({\mathcal{A}})}=P(F({\mathcal{A}}))$,

  2. (2)

for all $f\in Hom({\mathcal{A}},{\mathcal{B}})$,
$\Psi_{*}^{P({\mathcal{A}})\oplus Graph(f)\oplus
P({\mathcal{B}})}=Graph(F(f))$.

For ease of notation, when a graph of a function occurs in an oracle, we will
simply write the name of the function to represent it.

An alternative and purely syntactical method of comparing classes of
structures is through the model-theoretic notion of interpretability. Since we
are restricting ourselves to positive information, we introduce a new notion
of interpretability that uses $\Sigma^{p}_{1}$ formulas.

######  Definition 3.2.

A structure ${\mathcal{A}}=(A,P_{0}^{\mathcal{A}},\dots)$ is _positively
interpretable_ in a structure ${\mathcal{B}}$ if there exists a
$\Sigma^{p}_{1}$ definable sequence of relations
$(Dom_{\mathcal{A}}^{\mathcal{B}},\overline{Dom_{\mathcal{A}}^{\mathcal{B}}},\sim,\not\sim,R_{0},\dots)$
in the language of ${\mathcal{B}}$ such that

  1. (1)

$Dom_{\mathcal{A}}^{\mathcal{B}}\subseteq B^{<\omega}$,
$\overline{Dom_{\mathcal{A}}^{\mathcal{B}}}=B^{<\omega}\setminus
Dom_{\mathcal{A}}^{\mathcal{B}}$,

  2. (2)

$\sim$ is an equivalence relation on $Dom_{\mathcal{A}}^{\mathcal{B}}$ and
$\not\sim$ its corelation,

  3. (3)

$R_{i}\subseteq(B^{<\omega})^{a_{P_{i}}}$111$a_{P_{i}}$ is the arity of
$P_{i}$ is closed under $\sim$ on $Dom_{\mathcal{A}}^{\mathcal{B}}$,

and there exists a function
$f_{\mathcal{B}}^{\mathcal{A}}:Dom_{\mathcal{A}}^{\mathcal{B}}\to{\mathcal{A}}$,
the _interpretation of ${\mathcal{A}}$ in ${\mathcal{B}}$_, which induces an
isomorphism:

$(Dom_{\mathcal{A}}^{\mathcal{B}},R_{0},\dots)/{\sim}\cong(A,P_{0}^{\mathcal{A}},\dots)$

We seek to provide enumeration analogues to the results proven in [7],
starting with the following.

######  Theorem 3.3.

There is a positive enumerable functor $F:Iso({\mathcal{B}})\to
Iso({\mathcal{A}})$ if and only if ${\mathcal{A}}$ is positively interpretable
in ${\mathcal{B}}$.

###### Proof.

Suppose that ${\mathcal{A}}$ is positively interpretable in ${\mathcal{B}}$
using
$(Dom_{\mathcal{A}}^{\mathcal{B}},\overline{Dom_{\mathcal{A}}^{\mathcal{B}}}\sim,\not\sim,R^{\mathcal{B}}_{0},\dots)$.
We want to construct a functor $F:Iso({\mathcal{B}})\rightarrow
Iso({\mathcal{A}})$, so let $\tilde{{\mathcal{B}}}\in Iso({\mathcal{B}})$.
Since the relations are all $\Sigma_{1}^{p}$ definable they are uniformly
r.i.p.e. and so uniformly enumerable from $P(\tilde{{\mathcal{B}}})$ by
Corollary 1.7. Fix an enumeration of $\omega^{<\omega}$. Using the fact that
both $Dom_{\mathcal{A}}^{\tilde{\mathcal{B}}},\sim$, and their complements are
uniformly enumerable from $P(\tilde{\mathcal{B}})$ we can uniformly enumerate
a map $\tilde{\tau}:\omega\to Dom_{\mathcal{A}}^{\tilde{\mathcal{B}}}/\sim$
sending elements of $\omega$ to $\sim$ equivalence classes in
$Dom_{\mathcal{A}}^{\tilde{{\mathcal{B}}}}$. We define
$F(\tilde{{\mathcal{B}}})$ to be the pullback along $\tilde{\tau}$ of the
structure
$(Dom_{\mathcal{A}}^{\tilde{{\mathcal{B}}}}/\sim,\overline{Dom_{\mathcal{A}}^{\tilde{{\mathcal{B}}}}}/\sim,R^{\tilde{{\mathcal{B}}}}_{0}/\sim,\dots)$.
Since our relations are all uniformly enumerable from $P(\tilde{B})$, we have
that $P(F(\tilde{\mathcal{B}}))$ is enumerable from $P({\mathcal{B}})$.

Now to define our functor on isomorphisms, if we have
$f:\tilde{{\mathcal{B}}}\rightarrow\hat{{\mathcal{B}}}$ then letting
$\tilde{\tau}:\omega\rightarrow
Dom^{\tilde{{\mathcal{B}}}}_{\mathcal{A}}{/}{\sim}$ and
$\hat{\tau}:\omega\rightarrow
Dom^{\hat{{\mathcal{B}}}}_{\mathcal{A}}{/}{\sim}$ be defined as above, and
extending $f$ to $\tilde{{\mathcal{B}}}^{<\omega}$ in the natural way, we let

$F(f)=\hat{\tau}^{-1}\circ
f\circ\tilde{\tau}:\tilde{{\mathcal{A}}}\rightarrow\hat{{\mathcal{A}}}$

Since $\tilde{\tau}$ and $\hat{\tau}$ are uniformly enumerable from
$\tilde{\mathcal{B}}$ and $\hat{\mathcal{B}}$ respectively, we have that this
set $Graph(F(f))$ is uniformly enumerable from $P(\tilde{\mathcal{B}})\oplus
Graph(f)\oplus P(\hat{\mathcal{B}})$.

Now suppose that there is a positive enumerable functor $F=(\Psi,\Psi_{*})$
from $Iso({\mathcal{B}})$ to $Iso({\mathcal{A}})$. We want to produce the
$\Sigma_{1}^{p}$ sequence of relations providing the positive interpretation
of ${\mathcal{B}}$ in ${\mathcal{A}}$.

In what follows, we will often write $P(\overline{b})$ instead of
$P_{{\mathcal{B}}}(\overline{b})$ when it is clear from context which
structure ${\mathcal{B}}$ is meant.

We can view any finite disjoint tuple $\overline{b}$ as a map $i\mapsto b_{i}$
for $i<|\overline{b}|$. Note that viewing $\overline{b}$ as such a map, if $f$
is any permutation of $\omega$ extending $\overline{b}$, then
$P_{\mathcal{B}}(\overline{b})\subseteq P({\mathcal{B}}_{f})$ where
${\mathcal{B}}_{f}=f^{-1}({\mathcal{B}})$.

Let $Dom_{\mathcal{A}}^{\mathcal{B}}$ be the set of pairs
$(\overline{b},i)\in{\mathcal{B}}^{<\omega}\times\omega$ such that

$(i,i)\in\Psi_{*,|\overline{b}|}^{P(\overline{b})\oplus\lambda\restriction|\overline{b}|\oplus
P(\overline{b})}$

where $\lambda$ is the identity function. Both
$Dom_{\mathcal{A}}^{\mathcal{B}}$ and its corelation
$\overline{Dom_{\mathcal{A}}^{\mathcal{B}}}$ are clearly uniformly r.i.p.e.

For $(\overline{b},i),(\overline{c},j)\in Dom_{\mathcal{A}}^{\mathcal{B}}$ we
let $(\overline{b},i)\sim(\overline{c},j)$ exactly if there exists a finite
tuple $\overline{d}$ which does not mention elements from $\overline{b}$ or
$\overline{c}$, such that if $\overline{b}^{\prime}$ lists the elements that
occur in $\overline{b}$ but not $\overline{c}$ and $\overline{c}^{\prime}$
lists the elements in $\overline{c}$ but not in $\overline{b}$, and if
$\sigma=(\overline{c}\overline{b}^{\prime}\overline{d})^{-1}\circ\overline{b}\overline{c}^{\prime}\overline{d}$
then

$(i,j)\in\Psi_{*,|\overline{b}\overline{c}\overline{d}|}^{P(\overline{b}\overline{c}^{\prime}\overline{d})\oplus\sigma\oplus
P(\overline{c}\overline{b}^{\prime}\overline{d})}\quad\text{and}\quad(j,i)\in\Psi_{*,|\overline{b}\overline{c}\overline{d}|}^{P(\overline{c}\overline{b}^{\prime}\overline{d})\oplus\sigma^{-1}\oplus
P(\overline{b}\overline{c}^{\prime}\overline{d})}.$

It is easy to see that $\sim$ is uniformely r.i.p.e.. Rather than showing
immediately that the complement of $\sim$ is uniformly r.i.p.e., we define a
clearly uniformly r.i.p.e. relation $\not\sim$, and then show that it is
indeed the complement of $\sim$.

For $(\overline{b},i),(\overline{c},j)\in Dom_{\mathcal{A}}^{\mathcal{B}}$ we
say $(\overline{b},i)\not\sim(\overline{c},j)$ if there exist $k\neq j,l\neq
i$, and a finite tuple $\overline{d}$ which does not mention elements from
$\overline{b}$ or $\overline{c}$, such that if $\overline{b}^{\prime}$ lists
the elements that occur in $\overline{b}$ but not $\overline{c}$ and
$\overline{c}^{\prime}$ lists the elements in $\overline{c}$ but not in
$\overline{b}$, and if
$\sigma=(\overline{c}\overline{b}^{\prime}\overline{d})^{-1}\circ\overline{b}\overline{c}^{\prime}\overline{d}$
then

$(i,k)\in\Psi^{P(\overline{b}\overline{c}^{\prime}\overline{d})\oplus\sigma\oplus
P(\overline{c}\overline{b}^{\prime}\overline{d})}_{*,|\overline{b}\overline{c}\overline{d}|}\quad\text{or}\quad(j,l)\in\Psi_{*,|\overline{b}\overline{c}\overline{d}|}^{P(\overline{c}\overline{b}^{\prime}\overline{d})\oplus\sigma^{-1}\oplus
P(\overline{b}\overline{c}^{\prime}\overline{d})}.$

######  Claim 3.3.1.

$\not\sim$ is the complement of $\sim$

###### Proof.

We want to show that, for any tuples $(\overline{b},i),(\overline{c},j)\in
Dom_{\mathcal{A}}^{\mathcal{B}}$, exactly one of
$(\overline{b},i)\sim(\overline{c},j)$,
$(\overline{b},i)\not\sim(\overline{c},j)$ hold. Let $\overline{b}^{\prime}$
list the elements in $\overline{b}$ but not $\overline{c}$, and let
$\overline{c}^{\prime}$ list the elements in $\overline{c}$ but not
$\overline{b}$. Let
$\sigma=(\overline{c}\overline{b}^{\prime})^{-1}\circ\overline{b}\overline{c}^{\prime}$.
Let $f,g:\omega\rightarrow{\mathcal{A}}$ be bijections extending
$\overline{b}\overline{c}^{\prime},\overline{c}\overline{b}^{\prime}$
respectively which agree on all inputs
$i>|\overline{b}\overline{c}^{\prime}|=|\overline{c}\overline{b}^{\prime}|$.
We can then pull back $f$ and $g$ to get structures
${\mathcal{B}}_{f},{\mathcal{B}}_{g}$. Then $h=g^{-1}\circ f$ is an
isomorphism extending $\sigma$ which is constant on all $i>|\sigma|$. Hence

$(i,h(i))\in\Psi_{*}^{P({\mathcal{B}}_{f})\oplus h\oplus
P({\mathcal{B}}_{g})}\quad\text{and}\quad(j,h(j))\in\Psi_{*}^{P({\mathcal{B}}_{f})\oplus
h\oplus P({\mathcal{B}}_{g})}$

If $h(i)=j$ and $h(j)=i$, then taking a long enough initial segment of $h$
witnesses $(\overline{b},i)\sim(\overline{c},j)$. If however $h(i)\not=j$ or
$h(j)\not=i$, then a long enough initial segment of $h$ witnesses
$(\overline{b},i)\not\sim(\overline{c},j)$.

We now assume towards a contradiction that both
$(\overline{b},i)\sim(\overline{c},j)$, and
$(\overline{b},i)\not\sim(\overline{c},j)$ and that their equivalence is
witnessed by $\overline{d}_{1},\sigma$ and their inequivalence is witnessed by
$k,l$,$\overline{d}_{2}$ and $\tau$. Without loss of generality assume that
$(i,k)\in\Psi_{*}^{P(\overline{b}\overline{c}^{\prime}\overline{d}_{2})\oplus\tau\oplus
P(\overline{c}\overline{b}^{\prime}\overline{d}_{2})}$. We also have
$(i,j)\in\Psi_{*}^{P(\overline{b}\overline{c}^{\prime}\overline{d}_{1})\oplus\sigma\oplus
P(\overline{c}\overline{b}^{\prime}\overline{d}_{1})}$. Let

$f_{1}\supset\overline{b}\overline{c}^{\prime}\overline{d}_{1}\quad
g_{1}\supset\overline{c}\overline{b}^{\prime}\overline{d}_{1}\quad
f_{2}\supset\overline{b}\overline{c}^{\prime}\overline{d}_{2}\quad
g_{2}\supset\overline{c}\overline{b}^{\prime}\overline{d}_{2}$

Then we have isomorphisms as shown below.

${\mathcal{B}}$${\mathcal{B}_{f_{2}}}$${\mathcal{B}_{f_{1}}}$${\mathcal{B}_{g_{1}}}$${\mathcal{B}_{g_{2}}}$$\scriptstyle{f_{1}^{-1}\circ
f_{2}}$$\scriptstyle{g_{2}^{-1}\circ
f_{2}}$$\scriptstyle{f_{2}}$$\scriptstyle{g_{1}^{-1}\circ
f_{1}}$$\scriptstyle{f_{1}}$$\scriptstyle{g_{2}^{-1}\circ
g_{1}}$$\scriptstyle{g_{1}}$$\scriptstyle{g_{2}}$

Since $F$ is a functor,

$F(g_{2}^{-1}\circ f_{2})=F(g^{-1}_{2}\circ g_{1})\circ F(g_{1}^{-1}\circ
f_{1})\circ F(f^{-1}_{1}\circ f_{2}).$

Since $(\overline{b},i)\in Dom_{\mathcal{A}}^{\mathcal{B}}$ we know that
$(i,i)\in\Psi_{*}^{P(\overline{b})\oplus\lambda\restriction|\overline{b}|\oplus
P(\overline{b})}$. Notice that $f_{1}^{-1}\circ
f_{2}\supset\lambda\restriction|\overline{b}\overline{c}^{\prime}|$ and
$P({\mathcal{B}}_{f_{1}})\supset
P(\overline{b}),P({\mathcal{B}}_{f_{2}})\supset P(\overline{b})$. Thus

$(i,i)\in\Psi_{*}^{P({\mathcal{B}}_{f_{2}})\oplus(f_{1}^{-1}\circ f_{2})\oplus
P({\mathcal{B}}_{f_{1}})}=Graph(F(f_{1}^{-1}\circ f_{2}))\Rightarrow
F(f_{1}^{-1}\circ f_{2})(i)=i.$

Similarly, since $(\overline{c},j)\in Dom_{\mathcal{A}}^{\mathcal{B}}$,

$(j,j)\in\Psi_{*}^{P(\overline{c})\oplus\lambda\restriction|\overline{c}|\oplus
P(\overline{c})}\Rightarrow(j,j)\in\Psi_{*}^{P({\mathcal{B}}_{g_{1}})\oplus(g_{2}^{-1}\circ
g_{1})\oplus P({\mathcal{B}}_{g_{2}})}=Graph(F(g_{2}^{-1}\circ g_{1})).$

Following from our choices for $f_{1},g_{1},f_{2},g_{2}$ we have that
$g_{1}^{-1}\circ f_{1}\supset\sigma$ and $g_{2}^{-1}\circ f_{2}\supset\tau$,
so

$(i,j)\in\Psi_{*}^{P(\overline{b}\overline{c}^{\prime}\overline{d}_{1})\oplus\sigma\oplus
P(\overline{c}\overline{b}^{\prime}\overline{d}_{1})}\Rightarrow(i,j)\in\Psi_{*}^{P({\mathcal{B}}_{f_{1}})\oplus(g_{1}^{-1}\circ
f_{1})\oplus P({\mathcal{B}}_{g_{1}})}=Graph(F(g_{1}^{-1}\circ f_{1}))$
$(i,k)\in\Psi_{*}^{P(\overline{b}\overline{c}^{\prime}\overline{d}_{2})\oplus\tau\oplus
P(\overline{c}\overline{b}^{\prime}\overline{d}_{2})}\Rightarrow(i,k)\in\Psi_{*}^{P({\mathcal{B}}_{f_{2}})\oplus(g_{2}^{-1}\circ
f_{2})\oplus P({\mathcal{B}}_{g_{2}})}=Graph(F(g_{2}^{-1}\circ f_{2})).$

The first three equations tell us that

$F(g^{-1}_{2}\circ g_{1})\circ F(g_{1}^{-1}\circ f_{1})\circ F(f^{-1}_{1}\circ
f_{2})(i)=F(g^{-1}_{2}\circ g_{1})\circ F(g_{1}^{-1}\circ
f_{1})(i)=F(g^{-1}_{2}\circ g_{1})(j)=j$

whereas the fourth equation tells us that $F(g_{2}^{-1}\circ f_{2})(i)=k$.
This contradicts our earlier statement of $F$ being a functor, and so only one
of $\sim,\not\sim$ can hold at once. ∎

######  Claim 3.3.2.

The relation $\sim$ is an equivalence relation on
$Dom_{\mathcal{A}}^{\mathcal{B}}$.

###### Proof.

Let $(\overline{a},i),(\overline{b},j),(\overline{c},k)\in
Dom_{\mathcal{A}}^{\mathcal{B}}$. It is reflexive, since $(\overline{a},i)\in
Dom_{\mathcal{A}}^{\mathcal{B}}$ means that
$(i,i)\in\Psi_{*}^{P(\overline{a})\oplus\lambda\restriction|\overline{a}|\oplus
P(\overline{a})}$, and so the equivalence is witnessed by the empty tuple and
$\lambda\restriction|\overline{a}|$. If $(\overline{a},i)\sim(\overline{b},j)$
via $\overline{d},\sigma$, then $(\overline{b},j)\sim(\overline{a},i)$ via
$\overline{d},\sigma^{-1}$. Now assume that
$(\overline{a},i)\sim(\overline{b},j)$ and it is witnessed by
$\overline{a}^{\prime},\overline{b}^{\prime}\overline{d}^{\prime},\sigma$ and
$(\overline{b},j)\sim(\overline{c},k)$ via
$\overline{b}^{\prime\prime},\overline{c}^{\prime\prime},\overline{d}^{\prime\prime},\tau$.
Let $\overline{a}^{\prime\prime\prime}$ and
$\overline{c}^{\prime\prime\prime}$ list the elements of
$\overline{a}\setminus\overline{c}$ and $\overline{c}\setminus\overline{a}$
respectively. Choose bijections as follows

$\displaystyle
f_{1}\supset\overline{a}\overline{b}^{\prime}\overline{d}^{\prime}\quad
g_{1}\supset\overline{b}\overline{c}^{\prime\prime}\overline{d}^{\prime\prime}\quad
h_{1}\supset\overline{a}\overline{c}^{\prime\prime\prime}$ $\displaystyle
f_{2}\supset\overline{b}\overline{a}^{\prime}\overline{d}^{\prime}\quad
g_{2}\supset\overline{c}\overline{b}^{\prime\prime}\overline{d}^{\prime\prime}\quad
h_{2}\supset\overline{c}\overline{a}^{\prime\prime\prime}$

such that $h_{1}$ and $h_{2}$ agree outside an initial segment of length
$|\overline{a}|+|\overline{c}^{\prime\prime\prime}|$.

${\mathcal{B}}$${\mathcal{B}_{h_{1}}}$${\mathcal{B}_{f_{1}}}$${\mathcal{B}_{f_{2}}}$${\mathcal{B}_{g_{1}}}$${\mathcal{B}_{g_{2}}}$${\mathcal{B}_{h_{2}}}$${\overline{a}\overline{c}^{\prime\prime\prime}}$${\overline{a}\overline{b}^{\prime}\overline{d}^{\prime}}$${\overline{b}\overline{a}^{\prime}\overline{d}^{\prime}}$${\overline{b}\overline{c}^{\prime\prime}\overline{d}^{\prime\prime}}$${\overline{c}\overline{b}^{\prime\prime}\overline{d}^{\prime\prime}}$${\overline{c}\overline{a}^{\prime\prime\prime}}$$\scriptstyle{h_{2}^{-1}\circ
h_{1}}$$\scriptstyle{f_{1}^{-1}\circ
h_{1}}$$\scriptstyle{h_{1}}$$\scriptstyle{f_{2}^{-1}\circ
f_{1}}$$\scriptstyle{f_{1}}$$\scriptstyle{g_{1}^{-1}\circ
f_{2}}$$\scriptstyle{f_{2}}$$\scriptstyle{g_{2}^{-1}\circ
g_{1}}$$\scriptstyle{g_{1}}$$\scriptstyle{g_{2}}$$\scriptstyle{h_{2}^{-1}\circ
g_{2}}$$\scriptstyle{h_{2}}$$\scriptstyle{(\cdot)_{\rho}}$$\scriptstyle{(\cdot)_{\sigma}}$$\scriptstyle{(\cdot)_{\tau}}$

Since $F$ is a functor we have

$F(h_{2}^{-1}\circ h_{1})=F(h_{2}^{-1}\circ g_{2})\circ F(g_{2}^{-1}\circ
g_{1})\circ F(g_{1}^{-1}\circ f_{2})\circ F(f_{2}^{-1}\circ f_{1})\circ
F(f_{1}^{-1}\circ h_{1}).$

Since $(\overline{a},i)\in Dom_{\mathcal{A}}^{\mathcal{B}}$, and
$f_{1}^{-1}\circ h_{1}\supset\lambda\restriction|\overline{a}|$ we can show as
we did in Claim 3.3.1 that $F(f_{1}^{-1}\circ h_{1})(i)=i$. Similarly,
$F(g_{1}^{-1}\circ f_{2})(j)=j,F(h_{2}^{-1}\circ g_{2})(k)=k$. By assumption
$F(f_{2}^{-1}\circ f_{1})(i)=j$ and $F(g_{2}^{-1}\circ g_{1})(j)=k$. Thus

$(i,k)\in Graph(F(h_{2}^{-1}\circ
h_{1}))=\Psi_{*}^{P({\mathcal{B}}_{h_{1}})\oplus(h_{2}^{-1}\circ h_{1})\oplus
P({\mathcal{B}}_{h_{2}})}$

Similarly one can show that
$(k,i)\in\Psi_{*}^{P({\mathcal{B}}_{h_{2}})\oplus(h_{1}^{-1}\circ h_{2})\oplus
P({\mathcal{B}}_{h_{1}})}$. Since $h_{1}$ and $h_{2}$ agree outside of the
initial segment of length $|\overline{a}|+|\overline{c}^{\prime\prime\prime}|$
if we take a long enough $\overline{d}^{\prime\prime\prime}$ and let
$\rho\subset h_{2}^{-1}\circ h_{1}$ be the permutation sending
$\overline{a}\overline{c}^{\prime\prime\prime}\overline{d}^{\prime\prime\prime}$
to
$\overline{c}\overline{a}^{\prime\prime\prime}\overline{d}^{\prime\prime\prime}$
we witness that $(\overline{a},i)\sim(\overline{c},k)$. ∎

######  Claim 3.3.3.

For all $i\in\omega$, there is some $n\in\omega$ such that for
$\overline{c}={\mathcal{B}}\restriction n$, we have $(\overline{c},i)\in
Dom_{\mathcal{A}}^{\mathcal{B}}$.

###### Proof.

Let $\lambda$ be the identity function. Since functors map the identity to the
identity, $(i,i)\in
Graph(\lambda)=\Psi_{*}^{P({\mathcal{B}})\oplus\lambda\oplus
P({\mathcal{B}})}$, so by the use principle there is a sufficiently long
initial segment of ${\mathcal{B}}$ will have $(\overline{c},i)\in
Dom_{\mathcal{A}}^{\mathcal{B}}$. ∎

######  Claim 3.3.4.

For $(\overline{b},i)\in Dom_{\mathcal{A}}^{\mathcal{B}}$, there is an initial
segment $\overline{c}={\mathcal{B}}\restriction n$ of ${\mathcal{B}}$ and
$j\in\omega$ such that $(\overline{b},i)\sim(\overline{c},j)$.

###### Proof.

Let $m$ be greater than the maximum number in the tuple $\overline{b}$, and
let $\overline{c}^{\prime}$ list the numbers less than or equal to $m$ not
occuring in $\overline{b}$. Let $\overline{c}={\mathcal{B}}\restriction m$,
and let $f\supset\overline{c}^{-1}\circ\overline{b}\overline{c}^{\prime}$ be
defined by $f(n)=n$ for all $n\geq m$. Then $(i,j)\in
Graph(F(f))=\Psi_{*}^{P({\mathcal{B}}_{f})\oplus f\oplus P({\mathcal{B}})}$
for some $j$. So by the use principle, there exists $\overline{d}$ such that
$(i,j)\in\Psi_{*,|\overline{c}\overline{d}|}^{P(\overline{b}\overline{c}^{\prime}\overline{d})\oplus\sigma\oplus
P(\overline{c}\overline{d})}$ where
$\sigma=(\overline{c}\overline{d})^{-1}\circ\overline{b}\overline{c}^{\prime}\overline{d}$,
witnessing that $(\overline{b},i)\sim(\overline{c},j)$. ∎

######  Claim 3.3.5.

If $(\overline{b},i),(\overline{c},j)\in Dom_{\mathcal{A}}^{\mathcal{B}}$ and
$\overline{b}\subseteq\overline{c}$ then
$(\overline{b},i)\sim(\overline{c},j)$ iff $i=j$.

###### Proof.

To see this we note that since $(\overline{b},i)\in
Dom_{\mathcal{A}}^{\mathcal{B}}$, we have
$(i,i)\in\Psi_{*}^{P(\overline{b})\oplus\lambda\restriction|\overline{b}|\oplus
P(\overline{b})}$. So since $\overline{b}\subseteq\overline{c}$, by the use
principle
$(i,i)\in\Psi_{*}^{P(\overline{c})\oplus\lambda\restriction|\overline{c}|\oplus
P(\overline{c})}$, so $(\overline{b},i)\sim(\overline{c},i).$ Now let
$\overline{d},\sigma$ witness that $(\overline{b},i)\sim(\overline{c},j)$.
Then $\sigma\supseteq\lambda\restriction|\overline{b}|$ and the oracle
$P(\overline{b}\overline{c}^{\prime}\overline{d})\oplus\sigma\oplus
P(\overline{c}\overline{d})$ extends
$P(\overline{b})\oplus\lambda\restriction|\overline{b}|\oplus
P(\overline{b})$. So by the use principle
$(i,i)\in\Psi_{*}^{P(\overline{b}\overline{c}^{\prime}\overline{d})\oplus\sigma\oplus
P(\overline{c}\overline{d})}$. As
$\Psi_{*}^{P(\overline{b}\overline{c}^{\prime}\overline{d})\oplus\sigma\oplus
P(\overline{c}\overline{d})}$ must extend to the graph of a function, this
shows that $j=i$. ∎

We now define relations $R_{i}$ on $Dom_{\mathcal{A}}^{\mathcal{B}}$. For each
relation $P_{i}$ of arity $p(i)$ we let
$(\overline{b}_{1},k_{1}),\dots,(\overline{b}_{p(i)},k_{p(i)})$ be in $R_{i}$
if there is an initial segment $\overline{c}={\mathcal{B}}\restriction n$ of
${\mathcal{B}}$ and $j_{1},\dots,j_{p(i)}\in\omega$ such that
$(\overline{b}_{l},k_{l})\sim(\overline{c},j_{l})$ for all $l$ and
$P_{i}(j_{1},\dots,j_{p(i)})\in\Psi^{P(\overline{c})}$. Note that by 3.3.5, it
does not matter which initial segment is chosen.

We are now in position to define the isomorphism

$\mathfrak{F}:({\mathcal{A}},P_{0},P_{1}\dots)\rightarrow(Dom_{\mathcal{A}}^{\mathcal{B}}{/}{\sim},R_{0}{/}{\sim},R_{1}{/}{\sim},\dots)$

by $\mathfrak{F}(i)=(\overline{c},i)$ where
$\overline{c}={\mathcal{B}}\restriction n$ for the least $n$ such that
$(\overline{c},i)\in Dom_{\mathcal{A}}^{\mathcal{B}}$. Note that such
$(\overline{c},i)$ exists by 3.3.3. It then follows from 3.3.4 and 3.3.5 that
$\mathfrak{F}$ is a bijection. The bijection respects the relations by
definition, and so $\mathfrak{F}$ is an isomorphism. ∎

In the above theorem we not only show the existence of an interpretation given
a functor, but provide a method for transforming a functor $F$ into an
interpretation. Using the other direction of the proof we can turn this
interpretation back into a new functor. We shall call this new induced functor
$I^{F}$. We would like $I^{F}$ to agree with our original functor $F$ in some
fashion, and so we introduce the following definitions.

######  Definition 3.4.

A functor $F:\mathfrak{C}\to\mathfrak{D}$ is _enumeration isomorphic_ to a
functor $G:\mathfrak{C}\to\mathfrak{D}$ if there is an enumeration operator
$\Lambda$ such that for any $\mathcal{A}\in\mathfrak{C}$,
$\Lambda^{P(\mathcal{A})}:F(\mathcal{A})\to G(\mathcal{A})$ is an isomorphism.
Moreover, for any morphism $h\in Hom(\mathcal{A},\mathcal{B})$ in
$\mathfrak{C}$ when viewing $\Lambda^{P({\mathcal{A}})}$,
$\Lambda^{P({\mathcal{B}})}$ as isomorphisms, $\Lambda^{P(\mathcal{B})}\circ
F(h)=G(h)\circ\Lambda^{P(\mathcal{A})}$. That is, the diagram below commutes.

$F(\mathcal{A})$$F(\mathcal{B})$$G(\mathcal{A})$$G(\mathcal{B})$$\Lambda^{P(\mathcal{A})}$$\Lambda^{P(\mathcal{B})}$$F(h)$$G(h)$

######  Proposition 3.5.

Let $F:Iso({\mathcal{B}})\to Iso({\mathcal{A}})$ be positive enumerable and
$I^{F}:Iso({\mathcal{B}})\to Iso({\mathcal{A}})$ be the functor obtained from
Theorem 3.3. Then $F$ and $I^{F}$ are enumeration isomorphic.

###### Proof.

Given a presentation ${\mathcal{B}}\in Iso({\mathcal{B}})$ let
$\mathfrak{F}^{\mathcal{B}}:{\mathcal{B}}\rightarrow
Dom_{\mathcal{A}}^{\mathcal{B}}$ be the map obtained in Theorem 3.3 and let
$\tau^{\mathcal{B}}:\omega\rightarrow Dom_{\mathcal{A}}^{\mathcal{B}}/\sim$ be
the bijection obtained in the other direction of the same proof.
$\tau^{\mathcal{B}}$ gives rise to an isomorphism
$\mathcal{I}^{F}({\mathcal{B}})\rightarrow Dom_{\mathcal{A}}^{\mathcal{B}}$.
We know that both can be enumerated uniformly from a given presentation of
${\mathcal{B}}$ and so
$(\tau^{\mathcal{B}})^{-1}\circ\mathfrak{F}^{\mathcal{B}}$ is also uniformly
enumerable from ${\mathcal{B}}$. Thus there is some enumeration operator
$\Lambda$ such that for any presentation ${\mathcal{B}}$

$\Lambda^{P({\mathcal{B}})}=(\tau^{\mathcal{B}})^{-1}\circ\mathfrak{F}^{\mathcal{B}}:F({\mathcal{B}})\rightarrow\mathcal{I}^{F}({\mathcal{B}})$

To show $\Lambda$ is an enumeration isomorphism we want to show the following
diagram commutes for all $\tilde{\mathcal{B}},\hat{\mathcal{B}}\in
Iso({\mathcal{B}})$ and all morphisms
$h:\tilde{\mathcal{B}}\rightarrow\hat{\mathcal{B}}$. We extend $h$ to a map
$\tilde{\mathcal{B}}^{<\omega}\rightarrow\hat{\mathcal{B}}^{<\omega}$ and then
restrict to $Dom_{\mathcal{A}}^{\tilde{\mathcal{B}}}\rightarrow
Dom_{\mathcal{A}}^{\hat{\mathcal{B}}}$.

${F(\tilde{\mathcal{B}})}$${Dom_{\mathcal{A}}^{\tilde{{\mathcal{B}}}}}$${\mathcal{I}^{F}(\tilde{\mathcal{B}})}$${F(\hat{\mathcal{B}})}$${Dom_{\mathcal{A}}^{\hat{\mathcal{B}}}}$${\mathcal{I}^{F}(\hat{\mathcal{B}})}$$\scriptstyle{\mathfrak{F}^{\tilde{\mathcal{B}}}}$$\scriptstyle{F(h)}$$\scriptstyle{\Lambda^{P(\tilde{\mathcal{B}})}}$$\scriptstyle{h}$$\scriptstyle{\tau^{\tilde{\mathcal{B}}}}$$\scriptstyle{\mathcal{I}^{F}(h)}$$\scriptstyle{\mathfrak{F}^{\hat{\mathcal{B}}}}$$\scriptstyle{\Lambda^{P(\hat{\mathcal{B}})}}$$\scriptstyle{\tau^{\hat{\mathcal{B}}}}$

The right hand square commutes since $I^{F}(h)$ is defined to be
$\tau^{\tilde{{\mathcal{B}}}}\circ h\circ(\tau^{\hat{\mathcal{B}}})^{-1}$. To
see that the left square commutes take $i\in F(\tilde{\mathcal{B}})$. Then
$F(h)(i)=j$ for some $j\in F(\hat{\mathcal{B}})$ and
$\mathfrak{F}^{\tilde{\mathcal{B}}}(i)=(\overline{a},i)$,
$\mathfrak{F}^{\hat{\mathcal{B}}}(j)=(\overline{b},j)$ where $\overline{a}$
and $\overline{b}$ are initial segments of $\omega$. We want to show that
$h(\overline{a},i)=(h(\overline{a}),i)\sim^{\hat{\mathcal{B}}}(\overline{b},j)$.

Since $(i,j)\in\Psi_{*}^{P(\tilde{\mathcal{B}})\oplus h\oplus
P(\hat{\mathcal{B}})}$ we can get
$(i,j)\in\Psi_{*,|\overline{a}||\overline{b}|}^{P_{\tilde{\mathcal{B}}}(\overline{a})\oplus
h\restriction|\overline{a}|\oplus P_{\hat{\mathcal{B}}}(\overline{b})}$ by
extending $\overline{a}$ and $\overline{b}$. Note that
$P_{\tilde{{\mathcal{B}}}}(\overline{a})=P_{\hat{{\mathcal{B}}}}(h(\overline{a}))$
and assume without loss of generality that $\overline{b}$ contains both
$\overline{a}$ and $h(\overline{a})$. Since $\overline{b}$ is an initial
segment, the map associated to it is the identity. So the map
$\sigma=\overline{b}^{-1}\circ h(\overline{a})\overline{b}^{\prime}$ is an
initial segment of $h\restriction|\overline{a}|$. Hence

$(i,j)\in\Psi_{*,|\overline{a}\overline{b}|}^{P_{\hat{\mathcal{B}}}(h(\overline{a}))\oplus\sigma\oplus
P_{\hat{\mathcal{B}}}(\overline{b})}\quad\text{and}\quad(j,i)\in\Psi_{*,|\overline{a}\overline{b}|}^{P_{\hat{\mathcal{B}}}(\overline{b})\oplus(\sigma)^{-1}\oplus
P_{\hat{\mathcal{B}}}(h(\overline{a}))}$

∎

Clearly if we have a functor $F:Iso({\mathcal{A}})\to Iso({\mathcal{B}})$,
then every enumeration of ${\mathcal{A}}$ computes an enumeration of
${\mathcal{B}}$. In order to preserve enumeration degree spectra of structures
we need the relationship between the two isomorphism classes to be even
stronger. In [5] positive enumerable bi-transformability was introduced and it
was shown that two positive enumerable bi-transformable structures have the
same enumeration degree spectra. The next definition is the same as positive
enumerable bi-transformability. We chose to rename it, as we learned that the
notion is not new, but rather an effectivization of the highly influential
notion of an adjoint equivalence of categories in category theory.

######  Definition 3.6.

An _enumeration adjoint equivalence_ of categories $\mathfrak{C}$ and
$\mathfrak{D}$ consists of a tuple
$(F,G,\Lambda_{\mathfrak{C}},\Lambda_{\mathfrak{D}}))$ where
$F:\mathfrak{C}\to\mathfrak{D}$ and $G:\mathfrak{D}\to\mathfrak{C}$ are
positive enumerable functors, $\Lambda_{\mathfrak{C}}$ and
$\Lambda_{\mathfrak{D}}$ witness enumeration isomorphisms between the
compositions of $G\circ F$ and $Id_{\mathfrak{C}}$, respectively $F\circ G$
and $Id_{\mathfrak{D}}$, and the two isomorphisms are mapped to each other.
I.e.,

$F(\Lambda_{\mathfrak{C}}^{P({\mathcal{A}})})=\Lambda_{\mathfrak{D}}^{P(F({\mathcal{A}}))}\text{
and
}G(\Lambda_{\mathfrak{D}}^{P({\mathcal{B}})})=\Lambda_{\mathfrak{C}}^{P(G({\mathcal{B}}))}$

for all ${\mathcal{A}}\in\mathfrak{C}$ and ${\mathcal{B}}\in\mathfrak{D}$. If
there is an enumeration adjoint equivalence between $Iso({\mathcal{A}})$ and
$Iso({\mathcal{B}})$ then we say that ${\mathcal{A}}$ and ${\mathcal{B}}$ are
_enumeration adjoint_.

We will show that the following notion based on positive interpretability is
equivalent to enumeration adjointness.

######  Definition 3.7.

Two structures $\mathcal{A}$ and $\mathcal{B}$ are _positively bi-
interpretable_ if there are effective interpretations of one in the other such
that the compositions

$f_{\mathcal{B}}^{\mathcal{A}}\circ\hat{f}^{\mathcal{B}}_{\mathcal{A}}:Dom_{\mathcal{B}}^{Dom^{\mathcal{B}}_{\mathcal{A}}}\to\mathcal{B}\quad\mbox{and}\quad
f_{\mathcal{A}}^{\mathcal{B}}\circ\hat{f}_{\mathcal{B}}^{\mathcal{A}}:Dom_{\mathcal{A}}^{Dom^{\mathcal{A}}_{\mathcal{B}}}\to\mathcal{A}$

are uniformly ripe in $\mathcal{B}$ and $\mathcal{A}$ respectively. (Here the
function
$\hat{f^{\mathcal{B}}_{\mathcal{A}}}:(Dom_{\mathcal{A}}^{\mathcal{B}})^{<\omega}\to\mathcal{A}^{<\omega}$
is the canonical extension of
$f_{\mathcal{A}}^{\mathcal{B}}:Dom^{\mathcal{B}}_{\mathcal{A}}\to\mathcal{A}$
mapping $Dom^{Dom^{\mathcal{B}}_{\mathcal{A}}}_{\mathcal{B}}$ to
$Dom^{\mathcal{A}}_{\mathcal{B}}$)

######  Theorem 3.8.

${\mathcal{A}}$ and ${\mathcal{B}}$ are positively bi-interpretable if and
only if they are enumeration adjoint.

Since the proof of Theorem 3.3 works in the enumeration setting, this proof
will go through exactly as in [7] mutatis mutandis.

##  4\. Conclusion

When we restrict ourselves to only the positive information of a structure,
the notion of a r.i.p.e. relation is a natural analogue to r.i.c.e. relations.
Whence Theorem 1.6 shows that $\Sigma_{1}^{p}$ relations are the correct
notion of formula to consider in the enumeration setting. We see further
evidence for this in Section 2 when r.i.p.e. formulas are used to define the
positive jump of a structure. Theorem 2.11 supports the claim that the
positive jump is the proper enumeration jump for structures as it behaves well
with the regular enumeration jump of sets.

The authors in [5] showed that when comparing classes of structures with
respect to enumeration reducibility, positive enumerable functors are the
correct effectivization of functors to consider as they preserve enumeration
degree spectra. The equivalence given by Theorem 3.8 between enumeration
adjointness and positive bi-interpretability thus justifies the choice of
positive bi-interpretability as the enumeration analogue to bi-
interpretability.

We strongly believe that r.i.p.e. relations are a valuable addition to the
field of computable structure theory. Developing the idea of definability by
positive formulas further a Lopez-Escobar theorem for positive infinitary
formulas is proven in upcoming work by Bazhenov, Fokina, Rossegger, Soskova,
Soskova and Vatev: The sets of structures definable by $\Sigma^{p}_{\alpha}$
formulas are precisely the $\boldsymbol{\Sigma}^{0}_{\alpha}$ sets in the
Scott topology on the space of structures. This result as well as the results
in this article show promising signs of being useful to answer questions in
other areas, such as for instance algorithmic learning theory.

## References

  * [1] Chris Ash, Julia Knight, Mark Manasse and Theodore Slaman  “Generic Copies of Countable Structures”  In _Annals of Pure and Applied Logic_ 42.3, 1989, pp. 195–205  DOI: 10.1016/0168-0072(89)90015-8
  * [2] Wesley Calvert, Desmond Cummins, Julia Knight and Sara Miller  “Comparing Classes of Finite Structures”  In _Algebra and Logic_ 43.6, 2004, pp. 374–392  DOI: 10.1023/B:ALLO.0000048827.30718.2c
  * [3] John Chisholm  “Effective Model Theory vs. Recursive Model Theory”  In _The Journal of Symbolic Logic_ 55.03, 1990, pp. 1168–1191  DOI: 10.2307/2274481
  * [4] S. Cooper  “Computability Theory”  CRC Press, 2003  URL: https://books.google.at/books?hl=en&lr=&id=SJvt8ELnMakC&oi=fnd&pg=PA3&dq=cooper+computability+theory&ots=HRyW144BwW&sig=AxxZ9_a9IarhFeqXI37luP0AEBE
  * [5] Barbara F. Csima, Dino Rossegger and Daniel Yu  “Positive Enumerable Functors”  In _Connecting with Computability - 17th Conference on Computability in Europe, CiE 2021, Virtual Event, Ghent, July 5-9, 2021, Proceedings_ 12813, Lecture Notes in Computer Science  Springer, 2021, pp. 385–394  Springer  DOI: 10.1007/978-3-030-80049-9˙38
  * [6] Ekaterina Fokina, Valentina Harizanov and Alexander Melnikov  “Computable Model Theory”  In _Turing’s Legacy: Developments from Turing’s Ideas in Logic_ 42, 2014, pp. 124–191  DOI: 10.1017/cbo9781107338579.001
  * [7] Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller and Antonio Montalbán  “Computable functors and effective interpretability”, 2015  arXiv:1506.02737 [math.LO]
  * [8] Iskander Kalimullin  “Algorithmic Reducibilities of Algebraic Structures.”  In _Journal of Logic & Computation_ 22.4, 2012
  * [9] Julia Knight, Sara Miller and Michael Vanden Boom  “Turing Computable Embeddings”  In _The Journal of Symbolic Logic_ 72.3, 2007, pp. 901–918
  * [10] Julia F. Knight  “Degrees Coded in Jumps of Orderings”  In _The Journal of Symbolic Logic_ 51.04, 1986, pp. 1034–1042  DOI: 10.2307/2273915
  * [11] Antonio Montalbán  “Computable Structure Theory: Within the Arithmetic”, Perspectives in Logic  Cambridge: Cambridge University Press, 2021  DOI: 10.1017/9781108525749
  * [12] Antonio Montalbán  “Rice Sequences of Relations”  In _Philosophical Transactions of the Royal Society of London A_ 370.1971, 2012, pp. 3464–3487  URL: http://rsta.royalsocietypublishing.org/content/370/1971/3464.short
  * [13] Alan L. Selman  “Arithmetical Reducibilities I”  In _Zeitschrift fur mathematische Logik und Grundlagen der Mathematik_ 17.1 Carnegie Mellon University, 1971
  * [14] Ivan N. Soskov  “A note on $\omega$-jump inversion of degree spectra of structures”  In _Conference on Computability in Europe_ Springer, 2013, pp. 365–370
  * [15] Ivan N. Soskov  “Degree Spectra and Co-Spectra of Structures”  In _Ann. Univ. Sofia_ 96, 2004, pp. 45–68  URL: http://www.fmi.uni-sofia.bg/fmi/logic/soskov/dspect.pdf
  * [16] Alexandra Soskova and Mariya Soskova  “Enumeration Reducibility and Computable Structure Theory”  In _Computability and Complexity_ Springer, 2017, pp. 271–301  URL: http://link.springer.com/chapter/10.1007/978-3-319-50062-1_19
  * [17] Alexandra A. Soskova and Ivan N. Soskov  “A Jump Inversion Theorem for the Degree Spectra”  In _Journal of Logic and Computation_ 19.1, 2009, pp. 199–215  DOI: 10.1093/logcom/exn024
  * [18] Aleksei Stukachev  “Degrees of Presentability of Structures. I”  In _Algebra and Logic_ 46.6, 2007, pp. 419–432  URL: http://link.springer.com/article/10.1007/s10469-007-0041-z