$\vec{x}\in\omega^{n}$, $\theta^{(n)}(\vec{x})$ is undefined. Consequently,
$\theta^{(n)}_{q(i)}\in\textsc{Anf}^{(n)}_{A}$ and
$\mathrm{graph}(\theta^{(n)}_{q(i)})\subseteq graph(r)$. By our assumption
this means that $\theta^{(n)}_{q(i)}\notin X$, that is $q(i)\notin
I_{\theta^{(n)}}(X)$.

For the construction of $q$ we again apply Lemma 4.2 and Condition (QGN II),
as we did already many times. We only state predicate $Q$ and function $f$
needed in the construction:

$\displaystyle Q(i,\langle b,c\rangle,z)\Leftrightarrow f_{A}(b)\leq
c\wedge(\forall c^{\prime}\leq c)\,h(c^{\prime})\neq
i\wedge\bigwedge_{\nu=1}^{n}\pi^{(n)}_{\nu}(\arg(z))<f_{A}(b),$ $\displaystyle
f(i,\langle b,c\rangle,z)\overset{\mathrm{Def}}{=}r(\arg(z))+1.$

  * Claim 2  $(\forall s,r\in\mathcal{S}^{(n)}_{A})\,[[s\in X\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)]\Rightarrow r\in X]$.

Again we assume to the contrary that there are $s,r\in\mathcal{S}^{(n)}_{A}$
so that $s\in X$, $\mathrm{graph}(s)\subseteq\mathrm{graph}(r)$, but $r\notin
X$. Let $j$ be a $\theta^{(n)}$-index of $s$. Then we construct a function
$p\in\mathcal{R}^{(1)}$ so that

$\theta^{(n)}_{p(i)}(\vec{x})=\begin{cases}s(\vec{x})&\text{if in a
simultaneous search in the extended graph of $\theta^{(n)}$ and $K^{A}$, }\\\
&\text{respectively, $\langle\langle j,\vec{x}\rangle,s(\vec{x})+1\rangle$
will not be found later than $i$},\\\ r(\vec{x})&\text{if $i$ will be found
earlier},\\\ \text{undefined}&\text{otherwise}.\end{cases}$

Note that since $\mathrm{graph}(s)\subseteq\mathrm{graph}(r)$, in case that
$i\in K^{A}$ we always have that $\theta^{(n)}_{p(i)}=r$, independently when
$\langle\langle j,\vec{x}\rangle,s(\vec{x})+1\rangle$ will be found. By our
assumption $r\notin X$. Thus it follows for $i\in K^{A}$ that $p(i)\notin
I_{\theta^{(n)}}(X)$. On the other hand, if $i\in\omega\setminus K^{A}$, then
$\theta^{(n)}_{p(i)}=s$. Because $s\in X$, we have in this case that $p(i)\in
I_{\theta^{(n)}}(X)$. This shows that $\omega\setminus
K^{A}\leq_{m}I_{\theta^{(n)}}(X)$, which is impossible as we have seen.

It remains to construct the function $p$. Let to this end $j^{\prime}$ be a
$\theta^{(n)}$-index of $r$ and $h^{\prime}\in\mathcal{R}^{(1)}$ be an
enumeration of the extended graph of the universal function of numbering
$\theta^{(n)}$. The existence of $h^{\prime}$ follows from Condition (QGN I).
Define

$\displaystyle\widehat{Q}_{1}(a,b,z)\Leftrightarrow\pi^{(2)}_{2}(h^{\prime}(b))>0\wedge\pi^{(2)}_{1}(h^{\prime}(b))=\langle
a\rangle\ast\arg(z),$
$\displaystyle\widehat{Q}_{2}(i,b,z)\Leftrightarrow\mbox{}$
$\displaystyle\qquad\quad[\widehat{Q}_{1}(j,b,z)\wedge(\forall c<b)\,h(c)\neq
i]\vee\mbox{}$ $\displaystyle\hskip
85.35826pt[\widehat{Q}_{1}(j^{\prime},b,z)\wedge(\exists b^{\prime}\leq
b)\,[h(b^{\prime})=i\wedge\neg(\exists c\leq
b^{\prime})\,\widehat{Q}_{1}(j,c,z)]],$ $\displaystyle
Q(i,t,z)\Leftrightarrow(\exists b\leq t)\,\widehat{Q}_{2}(i,b,z),$
$\displaystyle f(i,t,z)\overset{\mathrm{Def}}{=}\pi^{(2)}_{2}(h^{\prime}(\mu
b\leq t.\ \widehat{Q}_{2}(i,b,z))),$

and construct function $k\in\mathcal{R}^{(2)}$ as in Lemma 4.2. Then $\lambda
t.\ k(i,t)$ enumerates the extended graph of function $d$ with

$d(\vec{x})=\begin{cases}s(\vec{x})&\text{$(\exists
b)\,\pi^{(2)}_{2}(h^{\prime}(b))>0\wedge\pi^{(2)}_{1}(h^{\prime}(b)=\langle
j,\vec{x}\rangle\wedge(\forall c<b)\,h(c)\neq i]$},\\\
r(\vec{x})&\text{$(\exists b)\,h(b)=i\wedge\neg(\exists c\leq
b)\,[\pi^{(2)}_{2}(h^{\prime}(c))>0\wedge\pi^{(2)}_{1}(h^{\prime}(c))=\langle
j,\vec{x}\rangle]]$},\\\ \text{undefined}&\text{otherwise}.\end{cases}$

As follows from the definition, $d\in\mathcal{S}^{(n)}_{A}$. By Condition (QGN
II) there is then a $p\in\mathcal{R}^{(1)}$ with $\theta^{(n)}_{p(i)}=d$.
Consequently, $p$ has the properties mentioned above.

  * Claim 3  $X=\\{\,r\in\mathcal{S}^{(n)}_{A}\mid(\exists i\in C)\,\mathrm{graph}(\alpha^{(n)}_{i})\subseteq\mathrm{graph}(r)\,\\}$.

Let $g\in\mathcal{R}^{(1)}$ with $\alpha^{(n)}=\theta^{(n)}\circ g$ and
$C=g^{-1}[I_{\theta*(n)}(X)]$. Then $CF$ is c.e. By Claim 6 we have for
$r\in\mathcal{S}^{(n)}_{A}$ that

$\displaystyle r\in X$ $\displaystyle\Rightarrow(\exists s\in
X\cap\textsc{Anf}^{(n)}_{A})\,\mathrm{graph}(s)\subseteq\mathrm{graph}(r)$
$\displaystyle\Rightarrow(\exists i)\,[\alpha^{(n)}_{i}\in
X\wedge\mathrm{graph}(\alpha^{(n)}_{i})\subseteq\mathrm{graph}(r)]$
$\displaystyle\Rightarrow(\exists i\in
C)\,\mathrm{graph}(\alpha^{(n)}_{i})\subseteq\mathrm{graph}(r).$

Conversely, we have with Claim 6 that

$\displaystyle(\exists i\in
C)\,\mathrm{graph}(\alpha^{(n)}_{i})\subseteq\mathrm{graph}(r)$
$\displaystyle\Rightarrow(\exists s\in
X)\,\mathrm{graph}(s)\subseteq\mathrm{graph}(r)$ $\displaystyle\Rightarrow
r\in X.\qed$

Next, we will study different kinds of computable operators on
$\widehat{\mathcal{S}}^{(n)}_{A}$ ands their relationship.

######  Definition 6.3 (cf. [36]).

An operator
$\widehat{G}\colon\widehat{\mathcal{S}}^{(n)}_{A}\to\widehat{\mathcal{S}}^{(m)}_{A}$
is _computable_ , if there is a c.e. set $C\subseteq\omega$ so that for
$r\in\widehat{\mathcal{S}}^{(n)}_{A}$,

$\mathrm{graph}(\widehat{G}(r))=\\{\,\langle\langle\vec{y}\rangle,z\rangle\mid(\exists
a)\,[\langle\langle\langle\vec{y}\rangle,z\rangle,a\rangle\in C\wedge(\forall
c\leq\mathrm{lth}(a))\,(a)_{c}\in\mathrm{graph}(r)\,\\}].$

We say that $C$ _defines_ the operator $\widehat{G}$.

As follows from the definition, $\mathrm{graph}(\widehat{G}(r))$ is c.e., if
$\mathrm{graph}(r)$ is c.e. Thus, we have for computable operators
$\widehat{G}\colon\widehat{\mathcal{S}}^{(n)}_{A}\to\widehat{\mathcal{S}}^{(m)}_{A}$
that $\widehat{G}[\mathcal{S}^{(n)}_{A}]\subseteq\mathcal{S}^{(m)}_{A}$. If
one assigns to the zero-ary tuple a code number $\langle\hskip 5.0pt\rangle$
the above definition and the subsequent results for $m=0$ also include the
case of the recursive functionals. However, it should be noted here that
$\widehat{\mathcal{S}}^{(0)}_{A}$ and $\mathcal{S}^{(0)}_{A}$ contain the
zero-digit constant functions, each of which we identify with the respective
constant, as well as the zero-ary nowhere defined function.

######  Theorem 6.4.

Let
$\widehat{G}\colon\widehat{\mathcal{S}}^{(n)}_{A}\to\widehat{\mathcal{S}}^{(m)}_{A}$
and $G$ be its restriction to $\mathcal{S}^{(n)}_{A}$. Then $\widehat{G}$ is
computable if, and only if the following three conditions are satisfied:

  1. 1.

For all $s,s^{\prime}\in\textsc{Anf}^{(n)}_{A}$,

$\mathrm{graph}(s)\subseteq\mathrm{graph}(s^{\prime})\Rightarrow\mathrm{graph}(G(s))\subseteq\mathrm{graph}(G(s^{\prime})).$

  2. 2.

For all $r\in\widehat{\mathcal{S}}^{(n)}_{A}$,

$\mathrm{graph}(\widehat{G}(r))=\bigcup\\{\,\mathrm{graph}(G(s))\mid
s\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\,\\}.$

  3. 3.

$\\{\,\langle
i,j\rangle\mid\mathrm{graph}(\alpha^{(m)}_{j})\subseteq\mathrm{graph}(G(\alpha^{(n)}_{i}))\,\\}$
is c.e.

###### Proof.

Assume that $\widehat{G}$ is computable. Then it follows from the definition
that for $s\in\textsc{Anf}^{(n)}_{A}$ and $r\in\widehat{G}^{(n)}_{A}$ with
$\mathrm{graph}(s)\subseteq\mathrm{graph}(r)$,
$\mathrm{graph}(G(s))\subseteq\mathrm{graph}(\widehat{G}(r))$. Thus, (1)
holds. Moreover,

$\bigcup\\{\,\mathrm{graph}(G(s))\mid
s\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\,\\}\subseteq\mathrm{graph}(\widehat{G}(r)).$

For the converse inclusion note that $\mathrm{graph}(\widehat{G}(r))$ is the
union of all $\mathrm{graph}(q)$, where $q\in\textsc{Anf}^{(m)}_{A}$ with
$\mathrm{graph}(q)\subseteq\mathrm{graph}(\widehat{G}(r))$. Therefore, let $q$
be such an initial segment function. In the enumeration of
$\mathrm{graph}(\widehat{G}(r))$ each element of $\mathrm{graph}(q)$
corresponds to a finite number of questions to $\mathrm{graph}(r)$. Since
$\mathrm{graph}(q)$ is finite, there is thus some $s\in\textsc{Anf}^{(n)}_{A}$
with $\mathrm{graph}(s)\subseteq\mathrm{graph}(r)$ and
$\mathrm{graph}(q)\subseteq\mathrm{graph}(G(s))$, which shows that also
Condition 2 holds.

For Condition (3) observe that

$\mathrm{graph}(\alpha^{(m)}_{j})\subseteq\mathrm{graph}(G(\alpha^{(n)}_{i}))\Leftrightarrow\mbox{}\\\
\hskip 10.00002pt(\forall\vec{y}<(\lg(j))^{m})(\exists z)(\exists
a)\,\langle\langle
j,\vec{y}\rangle,z+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda b,\vec{x}.\
\alpha^{(m)}_{b}(\vec{x}))\wedge\langle\langle\vec{y},z\rangle,a\rangle\in
C\wedge\mbox{}\\\ (\forall c<\mathrm{lth}(a))\,\langle\langle
i\rangle\ast\pi^{(2)}_{1}((a)_{c}),1+\pi^{(2)}_{2}((a)_{c})\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda
b,\vec{x}.\ \alpha^{(n)}_{b}(\vec{x})).$

Recall that the unbounded existential quantifiers in the right-hand side can
be brought in front of the expression by using an effective sequence encoding.
Moreover, the extended graphs in the expression are c.e. With the projection
lemma we hence obtain (3).

Now, conversely, suppose that
$\widehat{G}\colon\widehat{\mathcal{S}}^{(n)}_{A}\to\widehat{\mathcal{S}}^{(m)}_{A}$
satisfies Conditions (1)-(3). With (2) we have for
$r\in\widehat{\mathcal{S}}^{(n)}_{A}$ that

$\displaystyle\mathrm{graph}(\widehat{G}(r))$
$\displaystyle\qquad=\bigcup\\{\,\mathrm{graph}(G(s))\mid
s\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\,\\}$
$\displaystyle\qquad=\bigcup\\{\,\mathrm{graph}(q)\mid
q\in\textsc{Anf}^{(m)}_{A}\wedge(\exists
s\in\textsc{Anf}^{(n)}_{A})\,\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\wedge\mbox{}$
$\displaystyle\hskip
170.71652pt\mathrm{graph}(q)\subseteq\mathrm{graph}(G(s))\,\\}$
$\displaystyle\qquad=\bigcup\\{\,\mathrm{graph}(\alpha^{(m)}_{j})\mid(\exists
i)\,\mathrm{graph}(\alpha^{(n)}_{i})\subseteq\mathrm{graph}(r)\wedge\mbox{}$
$\displaystyle\hskip
170.71652pt\mathrm{graph}(\alpha^{(m)}_{j})\subseteq\mathrm{graph}(G(\alpha^{(n)}_{i}))\,\\}$

Let the graph encdoding $[\\![\alpha^{(n)}_{b}]\\!]$ be as in the proof of
Lemma 6.1. Then it follows

$\displaystyle\langle\langle\vec{y}\rangle,$ $\displaystyle
z\rangle\in\mathrm{graph}(\widehat{G}(r))$
$\displaystyle\Leftrightarrow\mbox{}$ $\displaystyle(\exists j)(\exists
i)\,\langle\langle\vec{y}\rangle,z\rangle\in\mathrm{graph}(\alpha^{(m)}_{j})\wedge\mbox{}$
$\displaystyle\qquad\qquad\mathrm{graph}(\alpha^{(m)}_{j})\subseteq\mathrm{graph}(G(\alpha^{(n)}_{i}))\wedge\mathrm{graph}(\alpha^{(n)}_{i})\subseteq\mathrm{graph}(r)$
$\displaystyle\Leftrightarrow\mbox{}$ $\displaystyle(\exists a)\,[(\exists
j)(\exists i)\,\langle\langle
j,\vec{y}\rangle,z+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda b,\vec{x}.\
\alpha^{(m)}_{b}(\vec{x}))\wedge a=[\\![\alpha^{(n)}_{i}]\\!]\wedge\mbox{}$
$\displaystyle\qquad\qquad\mathrm{graph}(\alpha^{(m)}_{j})\subseteq\mathrm{graph}(G(\alpha^{(n)}_{i}))]\wedge(\forall
c<\mathrm{lth}(a))\,(a)_{c}\in\mathrm{graph}(r).$

Set

$C\overset{\mathrm{Def}}{=}\\{\,\langle\langle\langle\vec{y}\rangle,z\rangle,a\rangle\mid(\exists
j)(\exists i)\,\langle\langle
j,\vec{y}\rangle,z+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda b,\vec{x}.\
\alpha^{(m)}_{b}(\vec{x}))\wedge\mbox{}\\\
\mathrm{graph}(\alpha^{(m)}_{j})\subseteq\mathrm{graph}(G(\alpha^{(n)}_{i}))\wedge
a=[\\![\alpha^{(n)}_{i}]\\!]\,\\}.$

Then $C$ defines $\widehat{G}$. Since $[\\![\alpha^{(n)}_{i}]\\!]$ can be
computed form $i$ and because of Lemma 6.1(2) and Condition (3), we further
have that $C$ is c.e. Thus, $\widehat{G}$ is computable. ∎

The second type of operator we are going to consider is at the basis of the
Russian school of constructive mathematics. Contrary to computable operators
these operators are only defined for functions in $\mathcal{S}^{(n)}_{A}$.

######  Definition 6.5.

An operator $G\colon\mathcal{S}^{(n)}_{A}\to\mathcal{S}^{(m)}_{A}$ is called
_Markov-computable_ if there is a function $g\in\mathcal{R}^{(1)}$ so that

$G(\theta^{(n)}_{i})=\theta^{(m)}_{g(i)}.$

We say that $g$ _realises_ the operator $G$.

Our aim is to derive an analogue of the Myhill/Shepherdson theorem [31] for
the function classes considered here. We break the proof down in several
steps.

######  Lemma 6.6.

The restriction of a computable operator
$\widehat{G}\colon\widehat{\mathcal{S}}^{(n)}_{A}\to\widehat{\mathcal{S}}^{(m)}_{A}$
to $\mathcal{S}^{(n)}_{A}$ is Markov-computable.

###### Proof.

We use Lemma 4.2 to construct a function $k^{\prime}\in\mathcal{R}^{(2)}$ such
that $\lambda t.\ k^{\prime}(i,t)$ enumerates the extended graph of the
function $G(\theta^{(n)}_{i})$, where $G$ is the restriction of $\widehat{G}$
to $\mathcal{S}^{(n)}_{A}$. The existence of a function realising $G$ is then
a consequence of Condition (QGN II). Let $k\in\mathcal{R}^{(2)}$ be as
inTheorem 4.4. Then $\lambda t.\ k(i,t)$ enumerates the graph of
$\theta^{(n)}_{i}$. Moreover, let the c.e. set $C$ define $\widehat{G}$. Set

$\displaystyle\widehat{Q}(i,\langle\langle\langle\vec{y}\rangle,x\rangle,a\rangle,t,z)\Leftrightarrow\mbox{}$
$\displaystyle\qquad\vec{y}=\arg(z)\wedge(\forall
c\leq\mathrm{lth}(a))\,(\exists t^{\prime}\leq
t)\,k(i,t^{\prime})=\langle\pi^{(2)}_{1}((a)_{c}),1+\pi^{(2)}_{2}((a)_{c})\rangle,$
$\displaystyle
Q(i,t,z)\Leftrightarrow(\exists\langle\langle\langle\vec{y}\rangle,x\rangle,a\rangle\in
C_{t})\,\widehat{Q}(i,\langle\langle\langle\vec{y}\rangle,x\rangle,a\rangle,t,z),$
$\displaystyle
f(i,t,z)\overset{\mathrm{Def}}{=}\pi^{(2)}_{2}(\pi^{(2)}_{1}(\mu\langle\langle\langle\vec{y}\rangle,x\rangle,a\rangle\in
C_{t}.\ Q(i,\langle\langle\langle\vec{y}\rangle,x\rangle,a\rangle,t,z))).$

By comparing this definition with the condition that $C$ defines $\widehat{G}$
one sees that the function $k^{\prime}\in\mathcal{R}^{(2)}$ constructed as in
Lemma 4.2 has the required property. ∎

######  Lemma 6.7.

Every Markov-computable operator
$G\colon\mathcal{S}^{(n)}_{A}\to\mathcal{S}^{(m)}_{A}$ is monotone. That is,
for $r,s\in\mathcal{S}^{(n)}_{A}$,

$\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\Rightarrow\mathrm{graph}(G(s))\subseteq\mathrm{graph}(G(r)).$

###### Proof.

Assume to the contrary that there are $r,s\in\mathcal{S}^{(n)}_{A}$ s that
$\mathrm{graph}(s)\subseteq\mathrm{graph}(r)$, but
$\mathrm{graph}(G(s))\not\subseteq\mathrm{graph}(G(r))$. Since for every
$q\in\mathcal{S}^{(n)}_{A}$,

$\mathrm{graph}(q)=\bigcup\\{\,\mathrm{graph}(p)\mid
p\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}{p}\subseteq\mathrm{graph}(q)\,\\}.$

Therefore, there is some $p\in\textsc{Anf}^{(n)}_{A}$ with

$\mathrm{graph}(p)\subseteq\mathrm{graph}(G(s))\quad\text{and}\quad\mathrm{graph}(p)\not\subseteq\mathrm{graph}(G(r)).$

Let us suppose for the moment that a function $\hat{k}\in\mathcal{R}^{(2)}$
can be constructed so that $\lambda t.\ \hat{k}(i,t)$ enumerates the extended
graph of $s$, if $i\in\omega\setminus K_{A}$, and the extended graph of $r$,
otherwise. Then it follows for the function $v\in\mathcal{R}^{(1)}$ existing
for this $k$ by (QGN II) that

$\theta^{(n)}_{v(i)}=\begin{cases}s&\text{if $i\in\omega\setminus K^{A}$},\\\
r&\text{otherwise.}\end{cases}$

If $G$ is realised by $g\in\mathcal{R}^{(1)}$, we obtain

$\mathrm{graph}(p)\subseteq\mathrm{graph}(\theta^{(n)}_{g(v()i)})\Leftrightarrow\theta^{(n)}_{v(i)}=s\Leftrightarrow
i\in\omega\setminus K^{A}.$

By Lemma 6.1(5) the set
$\\{\,i\mid\mathrm{graph}(p)\subseteq\mathrm{graph}(\theta^{(n)}_{g(v(i))})\,\\}$
is c.e. and hence $\omega\setminus K^{A}$ is c.e. as well, which is false.
Thus we have a contradiction.

It remains to show that a function $\hat{k}$ as above can indeed be
constructed. Let again $k\in\mathcal{R}^{(1)}$ be as in Lemma 4.4. Then
$\lambda t.\ k(i,t)$ enumerates the extended graph of $\theta^{(n)}_{i}$.
Moreover, let $j,j^{\prime}$, respectively, be $\theta^{(n)}$-indices of $s$
and $r$, and let $h\in\mathcal{R}^{(1)}$ enumerate $K^{A}$. Then define
$\hat{k}$ by

$\hat{k}(i,t)\overset{\mathrm{Def}}{=}\begin{cases}k(j,t)&\text{if
$h(t^{\prime})\neq i$, for all $t^{\prime}\leq t$},\\\
k(j^{\prime},t)&\text{otherwise.}\end{cases}$

Then $\hat{k}$ is as wanted. ∎

######  Lemma 6.8.

Let $G\colon\mathcal{S}^{(n)}_{A}\to\mathcal{S}^{(m)}_{A}$ be Markov-
computable. Then, for every $r\in\mathcal{S}^{(n)}_{A}$,

$\mathrm{graph}(G(r))=\bigcup\\{\,\mathrm{graph}(G(s))\mid
s\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\,\\}.$

###### Proof.

By the previous lemma the set $\\{\,\mathrm{graph}(G(s))\mid
s\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\,\\}$
is a chain with respect to inclusion. For $r\in\textsc{Anf}^{(n)}_{A}$,
$\mathrm{graph}(r)$ is contained in this set. Hence, the statement holds
trivially. It remains to consider the case that $r\in\mathcal{R}^{(n)}$.
Because of Lemma 6.7 it suffices to show that

$\mathrm{graph}(G(r))\subseteq\bigcup\\{\,\mathrm{graph}(G(s))\mid
s\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\,\\}.$

Assume to the contrary that this inclusion is wrong for some
$r\in\mathcal{R}^{(n)}$. Then there exists $q\in\textsc{Anf}^{(m)}_{A}$ so
that $\mathrm{graph}(q)\subseteq\mathrm{graph}(G(r))$, but

$\mathrm{graph}(q)\not\subseteq\bigcup\\{\,\mathrm{graph}(G(s))\mid
s\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\,\\}.$
(4)

Statement (4) holds exactly if for all $s\in\textsc{Anf}^{(n)}_{A}$ with
$\mathrm{graph}(s)\subseteq\mathrm{graph}(r)$,
$\mathrm{graph}(q)\not\subseteq\mathrm{graph}(G(s))$.

Assume for the moment that there is some $v\in\mathcal{R}^{(1)}$ with
$\theta^{(n)}_{v(i)}\in\textsc{Anf}^{(n)}_{A}$ and

$\mathrm{graph}(\theta^{(n)}_{v(i)})\subseteq\mathrm{graph}(r),$

if $i\in K^{A}$, and $\theta^{(n)}_{v(i)}=r$, if $i\notin K^{A}$. Let
$g\in\mathcal{R}^{(1)}$ realise $G$. Then we obtain

$\mathrm{graph}(q)\subseteq\mathrm{graph}(\theta^{(m)}_{g(v(i))})\Leftrightarrow\theta^{(n)}_{v(i)}=r\Leftrightarrow
i\in\omega\setminus K^{A}.$

As seen in the last proof, this is impossible. So, the assumption made at the
beginning is wrong.

We will now consider the construction of function $v$. Let to this end
$h,f_{A}\in\mathcal{R}^{(1)}$, respectively, be enumerations of $K^{A}$ and
$A$. Moreover, let $\hat{k},k\in\mathcal{R}^{(2)}$ be defined by

$\displaystyle\hat{k}(i,t)\overset{\mathrm{Def}}{=}\begin{cases}\hat{k}(i,t-1)&\text{if
for $t^{\prime}<t$ and $t^{\prime\prime}\leq t$, $h(t^{\prime})=i$ and
$t=f_{A}(t^{\prime\prime})^{n}$},\\\
\langle\langle\kappa(t)\rangle,r(\kappa(t))+1\rangle&\text{otherwise},\end{cases}$
$\displaystyle k(i,2t)\overset{\mathrm{Def}}{=}\langle t,0\rangle,$
$\displaystyle k(i,2t+1)\overset{\mathrm{Def}}{=}\hat{k}(i,t).$

If $i\notin K^{A}$, $\lambda t.\ k(i,t)$ enumerates the extended graph of $r$;
otherwise, $\lambda t.\ \hat{k}(i,t)$ step by step lists

$\langle\langle\kappa(0)\rangle,r(\kappa(0))+1\rangle,\langle\langle\kappa(1)\rangle,r(\kappa(1))+1\rangle,\ldots$

until $i$ has been found in $K^{A}$. If so, it continues this enumeration
until an initial segment of $\omega^{n}$ with an edge length in $A$ has been
enumerated by $\kappa(0),\ldots,\kappa(t)$. Therefore, in this case, $\lambda
t.\ k(i,t)$ enumerates the extended graph of a function
$s\in\textsc{Anf}^{(n)}_{A}$ with
$\mathrm{graph}(s)\subseteq\mathrm{graph}(r)$. It follows that the function
$v\in\mathcal{R}^{(1)}$ existing for this $k$ by Condition (QGN II) has the
appropriate properties. ∎

If $\alpha^{(n)}=\theta^{(n)}\circ f$, for some $f\in\mathcal{R}^{(n)}$ and
the Markov-computable operator
$G\colon\mathcal{S}^{(n)}_{A}\to\mathcal{S}^{(m)}_{A}$ is realised by
$g\in\mathcal{R}^{(n)}$, then $G(\alpha^{(n)}_{i})=\theta^{(n)}_{g(f(i))}$.
With Lemma 6.1(5) we also obtain that $\\{\,\langle
i,j\rangle\mid\mathrm{graph}(\alpha^{(m)}_{i})\subseteq\mathrm{graph}(G(\alpha^{(n)}_{j}))\,\\}$
is c.e. We have now completed all the necessary steps to derive the result we
were aiming for.

######  Theorem 6.9 (Myhill, Shepherdson).

  1. 1.

The restriction of every computable operator
$\widehat{G}\colon\widehat{\mathcal{S}}^{(n)}_{A}\to\widehat{\mathcal{S}}^{(m)}_{A}$
to $\mathcal{S}^{(n)}_{A}$ is Markov-computable.

  2. 2.

Every Markov-computable operator
$G\colon\mathcal{S}^{(n)}_{A}\to\mathcal{S}^{(m)}_{A}$ is the restriction to
$\mathcal{S}^{(n)}_{A}$ of a computable operator
$\widehat{G}\colon\widehat{\mathcal{S}}^{(n)}_{A}\to\widehat{\mathcal{S}}^{(m)}_{A}$.

###### Proof.

(1) has been shown in Lemma 6.6.

(2) By Lemma 6.7 the set $\\{\,\mathrm{graph}(G(s))\mid
s\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\,\\}$
with $r\in\mathcal{S}^{(n)}_{A}$ is a chain with respect to set inclusion.
Thus, the union over this chain is single-valued, that is, the graph of an
$m$-ary function. Let $\widehat{G}(r)$ be this function. Then we have

$\mathrm{graph}(\widehat{G}(r))=\bigcup\\{\,\mathrm{graph}(G(s))\mid
s\in\textsc{Anf}^{(n)}_{A}\wedge\mathrm{graph}(s)\subseteq\mathrm{graph}(r)\,\\}.$

The chain is either finite or infinite. In the first case
$\mathrm{graph}(\widehat{G}(r))$ is its maximal element. Since for all
$s\in\textsc{Anf}^{(n)}_{A}$, $G(s)\in\mathcal{S}^{(m)}_{A}$, it follows that
also $\widehat{G}(r)\in\mathcal{S}^{(m)}_{A}$. In the other case, every
element of the chain is the graph of a function in $\mathcal{S}^{(m)}_{A}$.
The domains of this functions in the chain therefore form an increasing chain
of subsets of $\omega^{m}$. it follows that $\widehat{G}(r)$ is total in this
case. Hence, in both cases,
$\widehat{G}(r)\in\widehat{\mathcal{S}}^{(m)}_{A}$. With Lemma 6.7 and the
remark preceding this theorem it follows that $\widehat{G}$ satisfies
Conditions (1)-(3) in Theorem 6.4. Hence, $\widehat{G}$ is computable. In case
that $r\in\mathcal{S}^{(n)}_{A}$ it moreover follows with Lemma 6.8 that
$\widehat{G}(r)=G(r)$. That is, $G$ is the restriction of $\widehat{G}$ to
$\mathcal{S}^{(n)}_{A}$. ∎

##  7 Quasi-Gödel numberings and the Rogers semi-lattice of computable
numberings

In this section we examine quasi-Gödel numberings under numbering-theoretical
aspects and sort out the relationship of the numbered sets
$(\mathcal{S}^{(1)}_{A},\theta)$ to the numbered set
$(\mathcal{P}^{(1)},\varphi)$. Here, $\theta$ is again a quasi-Gödel and
$\varphi$ a Gödel numbering. We limit ourselves to unary functions, since
every $n$-ary function $f\in\mathcal{S}^{(n)}_{A}$ converts into the unary
function $r\circ\kappa\in\mathcal{S}^{(1)}_{A^{\prime}}$ with
$A^{\prime}=\\{\,a^{n}\mid a\in A\,\\}$ by means of a one-to-one and initial
segment-wise enumeration $\kappa$ of $\omega^{n}$.

######  Proposition 7.1.

Let $\eta,\gamma$ be numberings of $\mathcal{S}^{(1)}_{A}$. Then the following
three statements hold;

  1. 1.

If $\gamma$ is a quasi-Gödel numbering and $\eta\leq_{m}\gamma$, then $\eta$
satisfies Condition (QGN I).

  2. 2.

If $\eta$ is a quasi-Gödel numbering and $\eta\leq_{m}\gamma$, then $\gamma$
satisfies Condition (QGN II).

  3. 3.

If $\eta,\gamma$, respectively, satisfy (QGN I) and (QGN II), then
$\eta\leq_{m}\gamma$.

###### Proof.

(1) Since $\eta\leq_{m}\gamma$, there is some $g\in\mathcal{R}^{(1)}$ with
$\eta=\gamma\circ g$. By assumption

$\mathrm{graph}_{\mathrm{e}}(\lambda i,x.\ \gamma_{i}(x))$

is c.e. Hence this is also true for $\mathrm{graph}_{\mathrm{e}}(\lambda i,x.\
\gamma_{g(i)}(x))$.

(2) Let $g\in\mathcal{R}^{(1)}$ with $\eta=\gamma\circ g$. Moreover, let
$k\in\mathcal{R}^{(2)}$ and $r\in\mathcal{S}^{(1)}_{A}$ so that $\lambda t.\
k(i,t)$ enumerates the extended graph of $r$. Since $\eta$ satisfies (QGN II),
there is some $v\in\mathcal{R}^{(1)}$ with $r=\eta_{v(i)}$. Set
$v^{\prime}\overset{\mathrm{Def}}{=}g\circ v$. Then
$r=\gamma_{v^{\prime}(i)}$. Whence also $\gamma$ satisfies (QGN II).

(3) Let $k\in\mathcal{R}^{(2)}$ be as in Theorem 4.4. Then $\lambda t.\
k(i,t)$ enumerates the extended graph of function $\eta_{i}$. Since $\gamma$
satisfies (QGN II) there is some $v\in\mathcal{R}^{(1)}$ with
$\eta_{i}\gamma_{v(i)}$. Thus, $\eta\leq_{m}\gamma$. ∎

It follows that, if $\gamma$ is a quasi Gödel numbering of
$\mathcal{S}^{(1)}_{A}$, then $\eta$ is also a quasi-Gödel numbering of
$\mathcal{S}^{(1)}_{A}$, exactly if $\eta\equiv_{m}\gamma$. In particular, all
quasi-Gödel numberings of $\mathcal{S}^{(1)}_{A}$ are $m$-equivalent. As we
will see next, they are maximal among all numberings of
$\mathcal{S}^{(1)}_{A}$ satisfying (QGN I), and minimal among those satisfying
(QGN II).

######  Theorem 7.2.

Let $\eta$ be a numbering of $\mathcal{S}^{(1)}_{A}$. Then the following three
statements are equivalent:

  1. 1.

$\eta$ is a quasi-Gödel numbering.

  2. 2.

$\eta$ satifies (QGN I) and for all numberings $\gamma$ of
$\mathcal{S}^{(1)}_{A}$, if $\gamma$ satisfies (QGN I) then
$\gamma\leq_{m}\eta$.

  3. 3.

$\eta$ satifies (QGN II) and for all numberings $\gamma$ of
$\mathcal{S}^{(1)}_{A}$, if $\gamma$ satisfies (QGN II) then
$\eta\leq_{m}\gamma$.

###### Proof.

Assume (1). Then (2) follows with Proposition 7.1(3). Conversely, suppose (2)
and let $\leftidx{{}^{A}}\psi$ be a quasi-Gödel numbering as in Theorem 3.2.
Then $\leftidx{{}^{A}}\psi\leq_{m}\eta$, by our assumption. With Proposition
7.1(2) it follows that $\eta$ satisfies (QGN II). Since it also satisfies (QGN
I), $\eta$ is a quasi-Gödel numbering.

In a similar way it follows that (1) and (2) are equivalent. ∎

At the end of Section 4 we pointed out that quasi-Gödel numberings are pre-
complete. This will be strengthened next.

######  Theorem 7.3.

Let $\theta$ be a quasi-Gödel numbering of $\mathcal{S}^{(1)}_{A}$. Then the
following two statements hold:

  1. 1.

$\theta$ is complete with the nowhere defined function as distinguished
element. This means that for any $p\in\mathcal{P}^{(1)}$ there exists
$g\in\mathcal{R}^{(1)}$ such that

$\theta_{g(i)}(x)=\begin{cases}\theta_{p(i)}(x)&\text{if
$i\in\mathrm{dom}(p)$},\\\ \text{undefined}&\text{otherwise}.\end{cases}$

  2. 2.

$\theta$ is cylindrical, that is, $\theta\equiv\theta^{c}$, where
$\theta^{c}_{\langle i,j\rangle}=\theta_{j}$.

###### Proof.

(1) Let $k\in\mathcal{R}^{(2)}$ be as in Theorem 4.4. Then $\lambda t.\
k(i,t)$ enumerates the extended graph of $\theta_{i}$. Moreover, let
$k^{\prime}\in\mathcal{R}^{(2)}$ be defined by

$\displaystyle k^{\prime}(i,2t)\overset{\mathrm{Def}}{=}\langle t,0\rangle,$
$\displaystyle
k^{\prime}(i,2t+1)\overset{\mathrm{Def}}{=}\begin{cases}k(i,t\mathbin{\mathchoice{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\displaystyle.$}\cr$\displaystyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\textstyle.$}\cr$\textstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptstyle.$}\cr$\scriptstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptscriptstyle.$}\cr$\scriptscriptstyle-$\cr}}}}\mu
t^{\prime}.\ p(i)\mathclose{\downarrow}_{t^{\prime}})&\text{if for some
$t^{\prime}<t$, $p(i)\mathclose{\downarrow}_{t^{\prime}}$},\\\ \langle
t,0\rangle&\text{otherwise}.\end{cases}$

Then $\lambda t.\ k^{\prime}(i,t)$ enumerates the extended graph of
$\theta_{i}$, if $i\in\mathrm{dom}(p)$. Otherwise, $\lambda t.\
k^{\prime}(i,t)$ enumerates the extended graph of the nowhere defined
function. Let $g\in\mathcal{R}(1)$ be the function existing by (QGN II). Then
we have for $i\in\mathrm{dom}{p}$ that $\theta_{g(i)}=\theta_{p(i)}$. In the
other case, $\theta_{g(i)}$ is nowhere defined.

(2) Let $\theta^{c}$ with $\theta^{c}_{\langle i,j\rangle}=\theta_{j}$ be the
cylinder of $\theta$. Then $\theta\leq_{1}\theta^{c}$. Since by the Ershov-
Myhill isomorphism theorem [7, p. 295] 1-equivalence coincides with computable
isomorphism, it remains to show that also $\theta^{c}\leq_{1}\theta$. Let to
this end $p\in\mathcal{R}^{(2)}$ be the padding function existing by Theorem
4.13. Then

$\theta^{c}_{\langle i,j\rangle}=\theta_{j}=\theta_{p(i,j)}.$

Thus, $\theta^{c}=\theta\circ g$ with $g(\langle i,j\rangle)=p(j,i)$. That is,
$\theta^{c}\leq_{1}\theta$. ∎

As we have seen above, all quasi-Gödel numberings are $m$-equivalent. Since
such numberings possess padding functions, they are even 1-equivalent. With
the Ershov-Myhill isomorphism theorem we thus obtain an extension of Rogers’
isomorphism theorem [35] for Gödel numberings to quasi-Gödel numberings.

######  Theorem 7.4 (Isomorphism Theorem).

All quasi-Gödel numberings are computably isomorphic.

It follows that a numbering of $\mathcal{S}^{(1)}_{A}$ is a quasi-Gödel
numbering, if it is computably isomorphic to a quasi-Gödel numbering.

In Section 2 we fixed a Gödel numbering $\varphi$ to construct a special
$\varphi$-standard numbering of $\mathcal{S}^{(1)}_{A}$ which then turned out
to be a quasi-Gödel numbering. Thus, every quasi-Gödel numbering of
$\mathcal{S}^{(1)}_{A}$ is computable isomorphic to a special
$\varphi$-standard numbering of $\mathcal{S}^{(1)}_{A}$. This result can be
strengthened again.

######  Theorem 7.5.

For every quasi-Gödel numbering $\theta$ there is a Gödel numbering $\xi$ so
that $\theta$ is a special $\xi$-standard numbering.

###### Proof.

Let $\leftidx{{}^{A}}\varphi$ be the special standard numbering von
$\mathcal{S}^{(1)}_{A}$ used in Section 2. Then
$\leftidx{{}^{A}}\varphi=\varphi\circ f$, for some $f\in\mathcal{R}^{(1)}$.
Moreover, there is a one-to-one and onto function $g\in\mathcal{R}^{(1)}$ with
$\theta=\leftidx{{}^{A}}\varphi\circ g$. Set
$\xi\overset{\mathrm{Def}}{=}\varphi\circ g$. Then $\xi$ is a Gödel numbering,
and as is readily verified, $\xi\circ(g^{-1}\circ f\circ g)$ is a special
$\xi$-standard numbering of $\mathcal{S}^{(1)}_{A}$. Moreover,
$\theta=\xi\circ(g^{-1}\circ f\circ g)$. ∎

It follows that the construction of a quasi-Gödel numbering of
$\mathcal{S}^{(1)}_{A}$ in Section 2 has universal character: every quasi-
Gödel numbering is obtained in this way.

In a next step we will examine which other properties the quasi-Gödel numbered
set $(\mathcal{S}^{(1)}_{A},\theta)$ has as a subobject of
$(\mathcal{P}^{(1)},\varphi)$. Here, a subset $Z\subseteq\mathcal{P}^{(1)}$
with a numbering $\zeta$ is called _subobject_ of
$(\mathcal{P}^{(1)},\varphi)$ if $\zeta\leq_{m}\varphi$ (cf. [7, 8]).

$(Z,\zeta)$ is an _sn-subobject_ of $(\mathcal{P}^{(1)},\varphi)$ if, in
addition, there is some $g\in\mathcal{R}^{(1)}$ so that $\zeta\circ g$ is a
special $\varphi$-standard n numbering of $Z$.

$(Z,\zeta)$ is called _r-subobject_ or _retract_ of
$(\mathcal{P}^{(1)},\varphi)$ if, in addition, there is an idempotent onto
function $H\colon\mathcal{P}^{(1)}\to Z$ and some $h\in\mathcal{R}^{(1)}$ such
that $H(\varphi_{i})=\zeta_{h(i)}$.

$(Z,\zeta)$ is an _n-subobject_ of $(\mathcal{P}^{(1)},\varphi)$ if, in
addition, there exist $f\in\mathcal{R}^{(1)}$ such that for all $i\in
I_{\varphi}(Z)$, $\varphi_{i}=\zeta_{f(i)}$. In this case the numbering $zeta$
is called _$\varphi$ -normal_ (cf. [28]).

$(Z,\zeta)$ is called _principal subobject_ of $(\mathcal{P}^{(1)},\varphi)$
and $\zeta$ _$\varphi$ -principal numbering_, if for every numbering $\eta$ of
$Z$ with $\eta\leq_{m}\varphi$ one has that $\eta\leq_{m}\zeta$.

As seen above, the quasi-Gödel numbering $\theta$ is computably isomorphic to
a special $\varphi$-standard numbering of $\mathcal{S}^{(1)}_{A}$. This shows

######  Corollary 7.6.

$(\mathcal{S}^{(1)}_{A},\theta)$ is an sn-subobject of
$(\mathcal{P}^{(1)},\varphi)$,

In Section 3 we have considered a Turing program $M^{(1)}_{A}$ that calls
arbitrary Turing programs $P$ so that $M^{(1)}_{A}(P)$ is a program that
computes the functions in $\mathcal{S}^{(1)}_{A}$. By considering the
semantics of the programs we obtain an idempotent onto map
$M_{A}\colon\mathcal{P}^{(1)}\to\mathcal{S}^{(1)}_{A}$ such that
$M_{A}(\varphi_{i})=\leftidx{{}^{A}}\varphi_{i}$. As we have seen above,
$\theta$ is computably isomorphic to $\leftidx{{}^{A}}\varphi_{i}$.

######  Theorem 7.7.

$(\mathcal{S}^{(1)}_{A},\theta)$ is a retract of
$(\mathcal{P}^{(1)},\varphi)$.

As is shown by Ershov [7, $\S 4$], every retract of
$(\mathcal{P}^{(1)},\varphi)$ is an n-subobject and each n-subobject is a
principal subobject of $(\mathcal{P}^{(1)},\varphi)$. Thus, every quasi-Gödel
numbering $\theta$ of $\mathcal{S}^{(1)}_{A}$ is $\varphi$-normal and a
$\varphi$-principal numbering. Since every numbering of
$\mathcal{S}^{(1)}_{A}$ that satisfies (QGN I) is $m$-reducible to $\varphi$,
it follows with Theorem 7.2 that each $\varphi$-principal numbering of
$\mathcal{S}^{(1)}_{A}$ is a quasi-Gödel numbering is. As a consequence, every
$\varphi$-normal numbering of $\mathcal{S}^{(1)}_{A}$ is a quasi-Gödel
numbering.

######  Theorem 7.8.

Let $\mathrm{HPT}^{\varphi}_{A}$, $\mathrm{NOR}^{\varphi}_{A}$ and
$\mathrm{QGN}^{\varphi}_{A}$, respectively, be the set of $\varphi$-principal,
$\varphi$-normal and quasi-Gödel numberings of $\mathcal{S}^{(1)}_{A}$. Then

$\mathrm{HPT}^{\varphi}_{A}=\mathrm{NOR}^{\varphi}_{A}=\mathrm{QGN}^{\varphi}_{A}.$

If $B$ is a c.e. superset of $A$ and $\gamma$ a quasi-Gödel numbering of
$\mathcal{S}^{(1)}_{B}$, then the above results remain true if $\varphi$ is
replaced by $\gamma$ and $(\mathcal{P}^{(1)},\varphi)$ by
$(\mathcal{S}^{(1)}_{B},\gamma)$. In particular we obtain an analogue of
Theorem 7.7.

######  Theorem 7.9.

$(\mathcal{S}^{(1)}_{A},\theta)$ is a retract of
$(\mathcal{S}^{(1)}_{B},\gamma)$.

So far in this work it was shown that the function classes
$\mathcal{S}^{(n)}_{A}$ have a quasi-G”odel numbering $\theta^{(n)}$ for every
infinite c.e. set $A$ and that for this a sufficiently rich computability
theory can be developed in which the same results apply as in the
computability theory for all partial computable functions. If there are
classes of functions that include the total computable functions but do not
contain all partial computable functions and for which a satisfactory
computability theory can be developed, one naturally wonders whether there are
$\subset^{*}$-minimal classes of this kind. Here, $X\subset^{*}Y$, if
$X\subset Y$ and $Y\setminus X$ is infinite. We do not want to treat this
problem in full generality, but want to examine whether the family
$\mathrm{BB}$ of sets contains $\subset^{*}$-minimal elements, where

$\mathrm{BB}\overset{\mathrm{Def}}{=}\\{\,\mathcal{R}^{(1)}\cup
T\mid\text{$T\subseteq\textsc{Anf}^{(1)}_{\omega}$ and $\mathcal{R}^{(1)}\cup
T$ has a quasi-G\"{o}del numbering}\,\\}$

Set $h(0,j)\overset{\mathrm{Def}}{=}j$ and
$h(i+1,j)\overset{\mathrm{Def}}{=}2^{h(i,j)}$. Then each set
$A_{i}\overset{\mathrm{Def}}{=}\\{\,h(i,j)\mid j\in\omega\,\\}$ with
$i\in\omega$ is computable and infinite. Since $A_{i+1}\subset^{*}A_{i}$, we
obtain that $\mathrm{BB}$ contains infinite descending chains with respect to
$\subset^{*}$.

If every function class in $\mathrm{BB}$ were of the form
$\mathcal{R}^{(1)}\cup\textsc{Anf}^{(1)}_{A}$ with an infinite c.e. set $A$,
we would of course know that $\mathrm{BB}$ contains no $\subset^{*}$-minimal
elements, since from any infinite c.e. set one can remove infinitely many
elements without destroying the property of being both infinite and c.e.
However, we do not know whether there are other sets
$T\subseteq\textsc{Anf}^{(1)}_{\omega}$ for which $\mathcal{R}^{(1)}\cup T$
has a quasi-Gödel numbering. Menzel and Sperschneider [29] show that the
family of sets

$\\{\,\mathcal{R}^{(1)}\cup T\mid\text{$T\subseteq\textsc{Anf}^{(1)}_{\omega}$
and $\mathcal{R}^{(1)}\cup T$ enumerable in $\varphi$}\,\\}$

does not contain $\subset^{*}$-minimal elements. Here, for a set $X$ with
numbering $\delta$, $Y\subseteq X$ is _enumerable in $\delta$_ if
$Y=\delta[E]$, for some c.e. set $E\subseteq\omega$. If $\mathcal{R}^{(1)}\cup
T$ now has a quasi-Gödel numbering, then this is $m$-reducible to $\varphi$.
So $\mathcal{R}^{(1)}\cup T$ is also enumerable in $\varphi$. This leads us to
the following result:

######  Theorem 7.10.

$\mathrm{BB}$ has no $\subset^{*}$-minimal elements.

.

Let $\mathrm{BN}_{A}$ be the set of numberings of $\mathcal{S}^{(1)}_{A}$ that
satisfy Condition (QGN I). As was shown at the beginning of this section, the
quasi-Gödel numberings of $\mathcal{S}^{(1)}_{A}$ are just those numberings in
$\mathrm{BN}_{A}$ that are maximal with respect to $\leq_{m}$. The numberings
in $\mathrm{BN}_{A}$ are exactly those numberings of $\mathcal{S}^{(1)}_{A}$
that have a computable universal function (which is however in
$\mathcal{P}^{(2)}\setminus\mathcal{S}^{(2)}_{A}$). Therefore, these
numberings are called _computable_.

For two numberings $\eta$ and $\gamma$ of $\mathcal{S}^{(1)}_{A}$,
$\eta\oplus\gamma$ defined by

$(\eta\oplus\gamma)(2i)\overset{\mathrm{Def}}{=}\eta(i)\quad\text{and}\quad(\eta\oplus\gamma)(2i+1)\overset{\mathrm{Def}}{=}\gamma(i)$

is the direct sum of $\eta$ and $\gamma$. Let $[\eta]$ be the equivalence
class of all numberings of $\mathcal{S}^{(1)}_{A}$ that are $m$-equivalent
with $\eta$. As is well known, the $m$-reducibility relation can be lifted to
the equivalence classes yielding a partial order on the set of these classes
denoted by $\leq$. As shown in [7], the collection of all equivalence classes
is an upper semi-lattice, usually called _Rogers semi-lattice_ , with respect
to this order with $[\eta\oplus\gamma]$ as least upper bound of $[\eta]$ and
$[\gamma]$. Because the direct sum of two computable numberings is computable
again, we obtain for the set
$[\mathrm{BN}_{A}]\overset{\mathrm{Def}}{=}\mathrm{BN}_{A}/{\leq_{m}}$:

######  Proposition 7.11.

  1. 1.

$([\mathrm{BN}_{A}],\leq)$ is a Rogers sub-semi-lattice of the Rogers semi-
lattice of all numberings of $\mathcal{S}^{(1)}_{A}$.

  2. 2.

$\mathrm{QGN}_{A}$ is the greatest element in $([\mathrm{BN}_{A}],\leq)$.

As we will see later in this section, $([\mathrm{BN}_{A}],\leq)$ is not a
lattice. The next result is an analogue of a theorem by Goetze [9, 10] for the
Rogers semi-lattice of the computable numberings of $\mathcal{P}^{(1)}$.

######  Theorem 7.12.

Every countable partially ordered set can be isomorphically embedded into the
Rogers semi-lattice of computable numberings of $\mathcal{S}^{(1)}_{A}$.

We derive this result in several steps. Let to this end $\theta$ be a quasi-
Gödel numbering of $\mathcal{S}^{(1)}_{A}$, $a$ be the least positive element
of $A$ and $\mathrm{CS}$ be the set of all computable subsets of $\omega$.
Then $(\mathrm{CS},\subseteq)$ is a lattice with the empty set as least
element. For every $C\in\mathrm{CS}$ let the numbering $\theta^{C}$ be defined
by

$\theta^{C}_{i}(x)\overset{\mathrm{Def}}{=}\begin{cases}\pi^{(a+1)}_{1}(i)\mathbin{\mathchoice{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\displaystyle.$}\cr$\displaystyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\textstyle.$}\cr$\textstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptstyle.$}\cr$\scriptstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptscriptstyle.$}\cr$\scriptscriptstyle-$\cr}}}}1&\text{if
$x=0$ and $\pi^{(a+1)}_{1}(i)\in C+1$},\\\ \vdots\\\
\pi^{(a+1)}_{a}(i)\mathbin{\mathchoice{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\displaystyle.$}\cr$\displaystyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\textstyle.$}\cr$\textstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptstyle.$}\cr$\scriptstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptscriptstyle.$}\cr$\scriptscriptstyle-$\cr}}}}1&\text{if
$x=a-1$ and $\pi^{(a+1)}_{1}(i)\in C+1$},\\\
\theta_{\pi^{(a+1)}_{a+1}(i)}(x)&\text{if $x\geq a$ and $\pi^{(a+1)}_{1}(i)\in
C+1$, or $\pi^{(a+1)}_{1}(i)\notin C+1$ and}\\\ &\text{
$\theta_{\pi^{(a+1)}_{a+1}(i)}(0)\notin C$},\\\
\text{undefined}&\text{otherwise}.\end{cases}$

Here, $C+1\overset{\mathrm{Def}}{=}\\{\,b+1\mid b\in C\,\\}$. Note that by the
choice of $a$ for all $j$ with $0\in\mathrm{dom}(\theta_{j})$, $\theta_{j}$ is
defined at least on an initial segment of $\omega$ of length $a$. Therefore,
$\theta^{C}_{i}\in\mathcal{S}^{(1)}_{A}$.

######  Lemma 7.13.

For all $C\in\mathrm{CS}$, $\theta^{C}\in\mathrm{BN}_{A}$.

###### Proof.

Since $\theta$ satisfies (QGN I) there is an enumeration
$h\in\mathcal{R}^{(1)}$ of the extended graph of the universal function of
$\theta$. Then we have

$\displaystyle\langle\langle i,x\rangle,z\rangle\in\mbox{}$
$\displaystyle\mathrm{graph}_{\mathrm{e}}(\lambda i,x.\
\theta^{C}_{i}(x))\Leftrightarrow\mbox{}$ $\displaystyle
z=0\vee\bigvee_{\nu=1}^{n}[x=\nu-1\wedge\pi^{(a+1)}_{1}(i)\in C+1\wedge
z=\pi^{(a+1)}_{\nu}(i)]\vee\mbox{}$ $\displaystyle[(\exists
t)\,h(t)=\langle\langle\pi^{(a+1)}_{a+1}(i),x\rangle,z\rangle\wedge[[x\geq
a\wedge\pi^{(a+1)}_{1}(i)\in C+1]\vee\mbox{}$
$\displaystyle[\pi^{(a+1)}_{1}(i)\notin C+1\wedge(\exists
t^{\prime})\,[\pi^{(2)}_{1}(h(t^{\prime}))=\langle\pi^{(a+1)}_{a+1}(i),0\rangle\wedge\mbox{}$
$\displaystyle\pi^{(2)}_{2}(h(t^{\prime}))>0\wedge\pi^{(2)}_{2}(h(t^{\prime}))\notin
C+1]]]].$

It follows that $\mathrm{graph}_{\mathrm{e}}(\lambda i,x.\ \theta^{C}_{i}(x))$
is c.e. it remains to show that
$\mathrm{range}(\theta^{C})=\mathcal{S}^{(1)}_{A}$. Let to this end
$r\in\mathcal{S}^{(1)}_{A}$ with $r=\theta_{j}$. Then

$i\overset{\mathrm{Def}}{=}\begin{cases}\langle
r(0)+1,\ldots,r(a)+1,j\rangle&\text{if $\mathrm{dom}(r)$ is not empty},\\\
\langle 0,\ldots,0,j\rangle&\text{otherwise}\end{cases}$

is a $\theta^{C}$-index of $r$. ∎

Note that by Theorem 7.2(3), $\theta^{\emptyset}\leq_{m}\theta$. On the other
hand, $\theta_{i}=\theta^{\emptyset}_{\langle 0,\ldots,0,i\rangle}$. Thus,
$\theta\equiv_{m}\theta^{\emptyset}$.

######  Lemma 7.14.

$(\\{\,[\theta^{C}]\mid C\in\mathrm{CS}\,\\},\leq)$ is a lattice that is
dually isomorphic zu $(\mathrm{CS},\subseteq)$. The mapping
$J(C)\overset{\mathrm{Def}}{=}[\theta^{C}]$ is a dual isomorphism.

###### Proof.

Let $C,E\in\mathrm{CS}$. First, we show that $\theta^{E}\leq_{m}\theta^{C}$,
if $E\subseteq C$. Consider the following algorithm:

_Input:_ $i$

  1. 1.

If $\pi^{(a+1)}_{1}(i)\in C+1$ then set $\hat{i}:=i$ and go to Step (4)

  2. 2.

If $\pi^{(a+1)}_{1}(i)\in E+1\setminus C+1$ then find $j$ so that

$\theta_{j}(x)=\begin{cases}\pi^{(a+1)}_{1}(i)\mathbin{\mathchoice{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\displaystyle.$}\cr$\displaystyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\textstyle.$}\cr$\textstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptstyle.$}\cr$\scriptstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptscriptstyle.$}\cr$\scriptscriptstyle-$\cr}}}}1&\text{if
$x=0$},\\\ \vdots\\\
\pi^{(a+1)}_{a}(i)\mathbin{\mathchoice{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\displaystyle.$}\cr$\displaystyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\textstyle.$}\cr$\textstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptstyle.$}\cr$\scriptstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptscriptstyle.$}\cr$\scriptscriptstyle-$\cr}}}}1&\text{if
$x=a-1$},\\\ \theta_{\pi^{(a+1)}_{a+1}(i)}(x)&\text{if $x\geq a$}\end{cases}$

and set
$\hat{i}:=\langle\pi^{(a+1)}_{1}(i),\ldots,\pi^{(a+1)}_{a}(i),j\rangle$ and go
to Step (4).

  3. 3.

(After the procedure has finished with this step, we know that
$\pi^{(a+1)}_{1}(i)\notin E+1$.)
Find $j^{\prime}$ with

$\theta_{j^{\prime}}(x)=\begin{cases}\theta_{\pi^{(a+1)}_{a+1}(i)}(x)&\text{if
$\theta_{\pi^{(a+1}_{a+1}(i)}(0)\notin E$},\\\
\text{undefined}&\text{otherwise}\end{cases}$

and set
$\hat{i}:=\langle\pi^{(a+1)}_{1}(i),\ldots,\pi^{(a+1)}_{a}(i),j^{\prime}\rangle$.

  4. 4.

STOP

_Output:_ $\hat{i}$.

As we will see in the next step, the indices $j$ and $j^{\prime}$ in Steps (2)
and (3), respectively, can be computed from $i$. Therefore, the above is
really an algorithm. Let $q\in\mathcal{R}^{(1)}$ be the function it computes.
Then $\theta^{E}=\theta^{C}\circ q$, that is $\theta^{E}\leq_{m}\theta^{C}$.

By Theorem 4.4 there is function $k\in\mathcal{R}^{(2)}$ such that for every
$i\in\omega$, $\lambda i,t.\ k(i,t)$ enumerates the extended graph of
$\theta_{i}$. Let

$\displaystyle k^{\prime}(i,t)\overset{\mathrm{Def}}{=}\begin{cases}\langle
t,\pi^{(a+1)}_{1}(i)\rangle&\text{if $t=0$},\\\ \vdots\\\ \langle
t,\pi^{(a+1)}_{a}(i)\rangle&\text{if $t=a-1$},\\\
k(\pi^{(a+1)}_{a+1}(i),t\mathbin{\mathchoice{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\displaystyle.$}\cr$\displaystyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\textstyle.$}\cr$\textstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptstyle.$}\cr$\scriptstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptscriptstyle.$}\cr$\scriptscriptstyle-$\cr}}}}a)&\text{if
$t\geq a$, and
$\pi^{(2)}_{2}(k(\pi^{(a+1)}_{a+1}(i),t\mathbin{\mathchoice{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\displaystyle.$}\cr$\displaystyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\textstyle.$}\cr$\textstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptstyle.$}\cr$\scriptstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptscriptstyle.$}\cr$\scriptscriptstyle-$\cr}}}}a))=0$
or}\\\
&\text{$\pi^{(2)}_{1}(k(\pi^{(a+1)}_{a+1}(i),t\mathbin{\mathchoice{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\displaystyle.$}\cr$\displaystyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\textstyle.$}\cr$\textstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptstyle.$}\cr$\scriptstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptscriptstyle.$}\cr$\scriptscriptstyle-$\cr}}}}a))\geq
a$},\\\ \langle 0,0\rangle&\text{otherwise},\end{cases}$ $\displaystyle
Q(i,t)\Leftrightarrow\pi^{(2)}_{1}(k(\pi^{(a+1)}_{a+1}(i),t))=0\wedge\pi^{(2)}_{2}(k(\pi^{(a+1}_{a+1}(i),t))\notin
E+1,$ $\displaystyle
k^{\prime\prime}(i,t)\overset{\mathrm{Def}}{=}\begin{cases}k(\pi^{(a+1)}_{a+1}(i),t\mathbin{\mathchoice{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\displaystyle.$}\cr$\displaystyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\textstyle.$}\cr$\textstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptstyle.$}\cr$\scriptstyle-$\cr}}}{\vbox{\offinterlineskip\halign{#\cr\raisebox{-1.5pt}[0.0pt][0.0pt]{$\scriptscriptstyle.$}\cr$\scriptscriptstyle-$\cr}}}}\mu
t^{\prime}\leq t.\ Q(i,t^{\prime}))&\text{if for some $t^{\prime}\leq t$,
$Q(i,t^{\prime})$},\\\ \langle t,0\rangle&\text{otherwise}.\end{cases}$

Then $\lambda t.\ k^{\prime}(i,t)$ enumerates the extended graph of the
function $\theta_{j}$ defined in Step (2) of the above algorithm and $\lambda
i,t.\ k^{\prime\prime}(i,t)$ the extended graph of the function
$\theta_{j^{\prime}}$ defined in Step (3). Let
$v^{\prime},v^{\prime\prime}\in\mathcal{R}^{(1)}$ be the functions now
existing by Condition (QGN II). Then $\theta_{j}=\theta_{v^{\prime}(i)}$ and
$\theta_{j^{\prime}}=\theta_{v^{\prime\prime}(i)}$. Thus, we can effectively
find indices $j$ and $j^{\prime}$ from given $i$ with the required properties.

Next, we show that also conversely, $\theta^{E}\leq_{m}\theta^{C}$ implies
$C\subseteq E$. To this end we need the following result:

Let $B$ be a computable set. Then the set $\\{\,i\mid\theta^{B}(0)=y\,\\}$ is
computable, exactly if $y\in B$. (5)

which we will prove in a later step.

Assume that $\theta^{E}\leq_{m}\theta^{C}$ and suppose that $y\in C$. Then we
ned to show that $y\in E$. Since $y\in C$, it follows with (5) that the set
$\\{\,i\mid\theta^{C}(0)=y\,\\}$ is computable. Because
$\theta^{E}\leq_{m}\theta^{C}$, it follows that
$\\{\,i\mid\theta^{E}(0)=y\,\\}$ is computable as well. Hence $y\in E$, again
by (5).

Thus, we have shown that $J$ is a dual isomorphism. Since
$(\mathrm{CS},\subseteq)$ is a lattice, the same holds for
$(\\{\,[\theta^{C}]\mid C\in\mathrm{CS}\,\\},\leq)$.

Finally, we derive the statement in (5). If $y\in B$ then
$\theta^{B}_{i}(0)=y$, exactly if $\pi^{(a+1)}_{1}(i)=y+1$. Therefore, the set
$\\{\,i\mid\theta^{B}_{i}(0)=y\,\\}$ is computable. If $y\notin B$, then we
have that

$\theta^{B}_{i}(0)=y\Leftrightarrow\pi^{(a+1)}_{1}(i)\notin
B+1\wedge\theta_{\pi^{(a+1)}_{a+1}(i)}(0)=y.$

By Rice’s theorem the set $\\{\,j\mid\theta_{j}(0)=y\,\\}$ is not computable,
for every $y\in\omega$. As $B$ is computable it follows that the set
$\\{\,i\mid\theta^{B}_{i}(0)=y\,\\}$ cannot be computable. ∎

Goetze [10] has shown that every countable partially ordered set can be
isomorphically embedded in the lattice of all computable set. By Lemma 7.14 it
therefore follows that every such set can be isomorphically embedded in the
Rogers semi-lattice of computable numberings of $\mathcal{S}^{(1)}_{A}$. This
concludes the proof of Theorem 7.12

In the next section we will show that $\mathcal{S}^{(1)}$ is an effectively
given domain with properties as considered in [41, Theorem 3.1]. As a
consequence we obtain that the Rogers semi-lattice of computable numberings of
$\mathcal{S}^{(1)}_{A}$ contains a Friedberg numbering, that is a one-to-one
computable numbering. As in Khutoretskiĭ [24, Corollary 2] one even obtains
that there are infinitely many Friedberg numberings of $\mathcal{S}^{(1)}_{A}$
which are pairwise incomparable with respect to $m$-reducibiility. Pour-El
[32] shows that the equivalence class $[\gamma]$ generated by a Friedberg
numbering of $\mathcal{S}^{(1)}_{A}$ is minimal in $(\mathrm{BN}_{A},\leq)$.

######  Theorem 7.15.

$(\mathrm{BN}_{A},\leq)$ is not a lattice.

$(\mathrm{BN}_{A},\leq)$ also contains minimal elements that are not generated
by Friedberg numberings, A numbering $\eta$ of $\mathcal{S}^{(1)}_{A}$ is
called _positive_ , if $\\{\,\langle i,j\rangle\mid\eta_{i}=\eta_{j}\,\\}$ is
c.e. Ershov [7, p. 303] shows that the equivalence class generated by a
positive numbering is minimal in the Rogers semi-lattice of numberings of a
given set.

######  Theorem 7.16.

$\mathcal{S}^{(1)}_{A}$ has a positive computable numbering to which no
Friedberg numbering can be reduced.

###### Proof.

The general construction is given by Khutoretskiĭ [24, Example 1]. Here we
verify the assumptions made. Let $f\in\mathcal{R}^{(1)}$. The we have to show
that the sets

$\\{\,g\in\mathcal{S}^{(1)}_{A}\mid\mathrm{graph}(g)\subseteq\mathrm{graph}(f)\,\\}\quad\text{and}\quad\\{\,g\in\mathcal{S}^{(1)}_{A}\mid\mathrm{graph}(g)\not\subseteq\mathrm{graph}(f)\,\\}$

can be numbered in a one-to-one way so that the universal functions of these
numberings have a c.e. graph. This, however, is a consequence of Mal’cev [27,
Theorem 5], if the classes can be enumerated in a quasi-Gödel numbering
$\theta$ of $\mathcal{S}^{(1)}_{A}$ and the sets

$\\{\,i\mid\mathrm{graph}(\alpha^{(1)}_{i})\subset\mathrm{graph}(f)\,\\}\quad\text{and}\quad\\{\,i\mid\mathrm{graph}(\alpha^{(1)}_{i})\not\subset\mathrm{graph}(f)\,\\}$

are c.e. Note that

$\mathrm{graph}(\alpha^{(1)}_{i}\subset\mathrm{graph}(f)\Leftrightarrow(\forall
x<\lg(i))\,\alpha^{(1)}_{i}(x)=f(x).$

Since $f\in\mathcal{R}^{(1)}$ it follows that both sets are even computable.

Let
$C=\\{\,i\mid\mathrm{graph}(\alpha^{(1)}_{i})\subset\mathrm{graph}(f)\,\\}$
and $g\in\mathcal{R}^{(1)}$ with $\alpha^{(1)}=\theta\circ g$. Moreover, let
$j$ be a $\theta$-index of $f$. Then

$\\{\,g\in\mathcal{S}^{(1)}_{A}\mid\mathrm{graph}(g)\subseteq\mathrm{graph}(f)\,\\}=\theta[\\{j\\}\cup
g[C]].$

Thus,
$\\{\,g\in\mathcal{S}^{(1)}_{A}\mid\mathrm{graph}(g)\subseteq\mathrm{graph}(f)\,\\}$
is enumerable in $\theta$.

Because of Condition (QGN I) there is some $h\in\mathcal{R}^{(1)}$ that
enumerates the extended graph of the universal function of $\theta$. Then we
have that

$\mathrm{graph}(\theta_{i})\not\subseteq\mathrm{graph}(f)\Leftrightarrow(\exists
x)(\exists t)\,\pi^{(2)}_{1}(h(t))=\langle
i,x\rangle\wedge\pi^{(2)}_{2}(h(t))>0\wedge\pi^{(2)}_{2}(h(t))\neq f(x)+1.$

Thus,
$\\{\,i\mid\mathrm{graph}(\theta_{i})\not\subseteq\mathrm{graph}(f)\,\\}$ is
c.e. and hence
$\\{\,g\in\mathcal{S}^{(1)}_{A}\mid\mathrm{graph}(g)\not\subseteq\mathrm{graph}(f)\,\\}$
enumerable in $\theta$. ∎

##  8 $\widehat{\mathcal{S}}^{(1)}_{A}$ as effectively given domain

Let $(D,\sqsubseteq)$ be a poset. $D$ is _pointed_ if it contains a least
element $\bot$. A subset $L$ of $D$ is _directed_ , if it is non-empty and
every pair of elements in $L$ has an upper bound in $L$. $D$ is a _directed-
complete partial order(dcpo)_ , if every directed subset $L$ of $D$ has a
least upper bound $\bigsqcup L$ in $D$.

Let $(D,\sqsubseteq)$ and $(D^{\prime},\sqsubseteq^{\prime})$ be posets. Then
a map $G\colon D\to D^{\prime}$ is _Scott-continuous_ , if it is monotone and
for any directed subset $L$ of $D$ with existing least upper bound,
$G(\bigsqcup L)=\bigsqcup^{\prime}G[L]$.

Assume that $x,y$ are elements of a poset $D$. Then $x$ is said to
_approximate_ $y$, written $x\ll y$, if for any directed subset $L$ of $D$ the
least upper bound of which exists in $D$, the relation $y\sqsubseteq\bigsqcup
L$ always implies the existence of some $u\in L$ with $x\sqsubseteq u$.
Moreover, $x$ is _compact_ if $x\ll x$. A subset $B$ of $D$ is a _basis_ of
$D$, if for each $x\in D$ the set $B_{x}=\\{\,u\in B\mid u\ll x\,\\}$ contains
a directed subset with least upper bound $x$. Note that the set of all compact
elements of $D$ is included in every basis of $D$. A directed-complete pointed
partial order $D$ is said to be _continuous_ (or a _domain_) if it has a basis
and it is called _algebraic_ (or an _algebraic domain_) if its compact
elements form a basis. Note we here assume that a domain is always pointed
which is not usually the case in the literature. Standard references for
domain theory and its applications are [47, 13, 2, 42, 3, 12].

######  Lemma 8.1.

Let $D$ and $D^{\prime}$ be domains. Then the following statements hold:

  1. 1.

The approximation relation $\ll$ is transitive.

  2. 2.

$x\ll y\Rightarrow x\sqsubseteq y$.

  3. 3.

$u\sqsubseteq x\ll y\sqsubseteq z\Rightarrow x\ll z$.

  4. 4.

$\bot\ll x$.

  5. 5.

$B_{x}$ is directed with respect to $\ll$.

  6. 6.

$G\colon D\to D^{\prime}$ is Scott-continuous, exactly if for all $x\in D$,
$G(x)=\bigsqcup^{\prime}G[B_{x}]$.

Note that by Property (3) we have that $x\ll y$ exactly if $x\sqsubseteq y$,
in case that $x$ or $y$ is compact.

######  Definition 8.2.

Let $D$ be a continuous domain with countable basis $B$ and a numbering
$\beta\colon\omega\to B$. Then $D$ is said to be _effectively given_ if the
set $\\{\,\langle i,j\rangle\mid\beta_{i}\ll\beta_{j}\,\\}$ is c.e.

If $D$ is effectively given, then an element $x$ is _computable_ if
$\beta^{-1}[B_{x}]$ is c.e. Let $D_{c}$ be the set of all computable elements
of $D$. If $D^{\prime}$ is another domain, say with basis $B^{\prime}$ and
numbering $\beta^{\prime}$ so that $D^{\prime}$ is effectively given, then a
map $G\colon D\to D^{\prime}$ is _computable_ , of $G$ is Scott-continuous and
$\\{\,\langle i,j\rangle\mid\beta^{\prime}_{j}\ll G(\beta_{i})\,\\}$ is c.e.
Note that for computable maps $G$, $G[D_{c}]\subseteq D^{\prime}_{c}$.

######  Definition 8.3.

Let $D$ be an effectively given domain. Then a numbering $\eta\colon\omega\to
D_{c}$ of the computable elements of $D$ is called _admissible_ if it
satisfies the following two requirements:

(A I)

$\\{\,\langle i,j\rangle\mid\beta_{i}\ll\eta_{j}\,\\}$ is c.e.

(A II)

There is a function $d\in\mathcal{R}^{(1)}$ such that for all $i\in\omega$, if
$\beta[W_{i}]$ is directed then $\eta_{d(i)}=\bigsqcup\beta[W_{i}]$.

Weihrauch and Deil [45] have shown that for every effectively given domain an
admissible numbering can be constructed.

######  Proposition 8.4 (Weihrauch, Deil, 1980).

Let $D$ be an effectively given domain and let $\eta$ be an admissible and
$\gamma$ an arbitrary numbering of its computable elements. Then the following
statements hold:

  1. 1.

$\eta$ is complete with special element $\bot$.

  2. 2.

$\gamma\text{ satisfies (A~{}I)}\Leftrightarrow\gamma\leq_{m}\eta$.

  3. 3.

$\gamma\text{ satisfies (A~{}II)}\Leftrightarrow\eta\leq_{m}\gamma$.

  4. 4.

$\gamma\text{ is
admissible}\Leftrightarrow\eta\equiv_{m}\gamma\Leftrightarrow\eta\equiv\gamma$.

Since $\eta$ is complete, it follows with a result of Ershov [7, p. 332] that
$\eta$ is cylindrical. As follows from the definition of an effectively given
domain, all basic elements are computable. Moreover, if $\gamma$ is any
numbering of $D_{c}$ satisfying (A II) then $\beta\leq_{m}\gamma$.

######  Lemma 8.5.

Let $D$ be an effectively given domain with basis $B$ and numbering $\beta$ of
the basis elements. Moreover, let $\eta$ be a numbering of $D_{c}$ that
satisfies (A I). Then there is a function $r\in\mathcal{R}^{(2)}$ such that
for all $i,j\in\omega$ with $\beta_{i}\ll\eta_{j}$ the following statements
hold:

  1. 1.

$\varphi_{r(i,j)}\in\mathcal{R}^{(1)}$,

  2. 2.

$\beta(i)\ll\beta(\varphi_{r(i,j)}(0))$,

  3. 3.

$\beta(\varphi_{r(i,j)}(a))\ll\beta(\varphi_{r(i,j)}(a+1))$ $(a\in\omega)$,

  4. 4.

$\eta(j)=\bigsqcup_{a}\beta(\varphi_{r(i,j)}(a))$.

###### Proof.

Let
$E_{ij}\overset{\mathrm{Def}}{=}\\{\,a\mid\beta(i)\ll\beta(a)\ll\eta(j)\,\\}$.
Then $E_{ij}$ is c.e. Thus, there is some function $q\in\mathcal{R}^{(2)}$ so
that $E_{ij}=W_{q(i,j)}$. Since $B_{\eta(j)}$ is directed with respect to
$\ll$, the same holds for $\beta[E_{ij}]$. It follows that
$\bigsqcup\beta[E_{ij}]$ exists. Moreover,
$\bigsqcup\beta[E_{ij}]\sqsubseteq\eta(j)$. Let $i,j$ be such that
$\beta(i)\ll\eta(j)$. Since $B_{\eta(j)}$ is directed with respect to $\ll$,
we have that for any $u\in B_{\eta(j)}$ there is some
$u^{\prime}\in\beta[E_{ij}]$ with $u\ll u^{\prime}$. Thus $E_{ij}$ is non-
empty and in addition, $\eta(j)\sqsubseteq\bigsqcup\beta[E_{ij}]$. Hence,
$\eta(j)=\bigsqcup\beta[E_{ij}]$.

In the sequel let $s\in\mathcal{R}^{(1)}$ such that $\varphi_{s(a)}$ is a
total function enumerating $W_{a}$, if $W_{a}$ is non-empty. Moreover, let
$k\in\mathcal{R}^{(2)}$ with $W_{k(a,c)}=W_{a}\cap W_{c}$, Then define
$g\in\mathcal{R}^{(3)}$ by

$\displaystyle g(i,j,0)\overset{\mathrm{Def}}{=}\varphi_{s(q(i,j))}(0),$
$\displaystyle
g(i,j,a+1)\overset{\mathrm{Def}}{=}\varphi_{s(k(q(g(i,j,a),j),q(\varphi_{s(q(i,j))}(a+1),j)))}(0).$

Then $g(i,ja+1)\in E_{g(i,j,a)j}\cap E_{\bar{\imath}j}$, where $\bar{\imath}$
is the $(a+1)$-st element of $E_{ij}$ in the enumeration
$\varphi_{s(q(i,j))}$. Because $\beta[E_{ij}]$ is directed with respect to
$\ll$, we have that $E_{g(i,j,a)j}\cap E_{\bar{\imath}j}$ is non-empty.
Therefore, $g(i,j,a+1)$ is defined. Furthermore, for all $a$,
$\beta(i)\ll\beta(g(i,j,a+1))$, from which we obtain that
$\bigsqcup\beta[E_{ij}]\sqsubseteq\bigsqcup_{a}\beta(g(i,j,a))$. Conversely,
since for all $a$, $g(i,j,a)\in E_{ij}$, we also have that
$\bigsqcup_{a}\beta(g(i,j,a))\sqsubseteq\bigsqcup\beta[E_{ij}]$. Thus,
$\bigsqcup_{a}\beta(g(i,j,a))=\bigsqcup\beta[E_{ij}]=\eta(j)$. Now, let
$r\in\mathcal{R}_{(2)}$ with $\varphi_{r(i,j)}(a)=g(i,j,a)$. Then $r$ is as
required. ∎

For the next consequence choose $i$ such that $\beta(i)=\bot$.

######  Corollary 8.6.

For every $x\in D_{c}$, there is a function $p\in\mathcal{R}^{(1)}$ so that

  1. 1.

$\beta(p(a))\ll\beta(p(a+1))\quad(a\in\omega$),

  2. 2.

$x=\bigsqcup_{a}\beta(p(a))$.

After these more technical results which we will need later, we now start
investigating the relationship of the function classes
$\widehat{\mathcal{S}}^{(n)}_{A}$ with domains. Again we will restrict
ourselves to considering only the classes $\widehat{\mathcal{S}}^{(1)}_{A}$.

######  Theorem 8.7.

Let $A\subseteq\omega$ be a c.e. infinite set and for
$f,g\in\widehat{\mathcal{S}}^{(1)}_{A}$ set

$f\sqsubseteq g\Leftrightarrow\mathrm{graph}(f)\subseteq\mathrm{graph}(g).$

Then $(\widehat{\mathcal{S}}^{(1)}_{A},\sqsubseteq)$ is an effectively given
algebraic domain such that:

  1. 1.

The nowhere defined function is the least element.

  2. 2.

The initial segment functions in $\textsc{Anf}^{(1)}_{A}$ are exactly the
compact elements.

  3. 3.

The functions in $\mathcal{S}^{(1)}_{A}$ are the computable elements.

  4. 4.

For numberings of $\mathcal{S}^{(1)}_{A}$, Conditions (QGN I) and (A I) as
well as (QGN II) and (A II) are equivalent. In particular, the quasi-Gödel
numberings are exactly the admissible numberings.

  5. 5.

The computability notions for operators
$G\colon\widehat{\mathcal{S}}^{(1)}_{A}\to\widehat{\mathcal{S}}^{(1)}_{A}$ in
Definition 6.3 and in this section coincide.

###### Proof.

If $L\subseteq\widehat{\mathcal{S}}^{(1)}_{A}$ is directed with respect to
$\sqsubseteq$, then $L$ has to be a chain. Thus the union of the graphs of the
functions in $L$ is again the graph of a function. This function must be in
$\widehat{\mathcal{S}}^{(1)}_{A}$. It is the least upper bound of $L$ with
respect to $\sqsubseteq$. Thus, $\widehat{\mathcal{S}}^{(1)}_{A}$ is directed-
complete. Obviously the nowhere defined function is the least element. Every
function in $\widehat{\mathcal{S}}^{(1)}_{A}$ is the least upper bound of its
restrictions to initial segments of $\omega$ with length in $A$. So, the
functions in $\textsc{Anf}^{(1)}_{A}$ form a basis.

(2) All functions in $\textsc{Anf}^{(1)}_{A}$ are compact. To see this let
$p\in\textsc{Anf}^{(1)}_{A}$ and $L$ be a directed subset of
$\widehat{\mathcal{S}}^{(1)}_{A}$ with $p\sqsubseteq\bigsqcup L$. Then
$\mathrm{graph}(p)\subseteq\bigcup\\{\,\mathrm{graph}(q)\mid q\in L\,\\}$.
Since $\mathrm{graph}(p)$ is finite, it is covered by the union of the graphs
of finitely many functions in $L$. Because this union is again contained in
the graph of some function $r\in L$, as $L$ is directed, we have that
$p\sqsubseteq r$. Conversely, if $f\in\widehat{\mathcal{S}}^{(1)}_{A}$ is
compact, then consider the directed set $L$ of all functions
$s\in\textsc{Anf}^{(1)}_{A}$ with $s\sqsubseteq f$. Then
$f\sqsubseteq\bigsqcup L$. By compactness there is some $s\in L$ with
$f\sqsubseteq s$. Since $s\in\textsc{Anf}^{(1)}_{A}$, the same must hold for
$f$. Thus, the domain $\widehat{\mathcal{S}}^{(1)}_{A}$ is algebraic.

With Lemma 6.1(4) and Statement (4) we obtain that $\\{\,\langle
i,j\rangle\mid\alpha^{(1)}_{i}\sqsubseteq\alpha^{(1)}_{j}\,\\}$ is c.e. Thus,
the domain $\widehat{\mathcal{S}}^{(1)}_{A}$ is effectively given with respect
to the numbering $\alpha^{(1)}$ of the basis.

(3) Let $f\in\mathcal{S}^{(1)}_{A}$. Then it follows with Lemma 6.1(5) that
$\\{\,i\mid\alpha^{(1)}_{i}\sqsubseteq f\,\\}$ is c.e. Hence,
$f\in(\widehat{\mathcal{S}}^{(1)}_{A})_{c}$. Conversely, if
$f\in(\widehat{\mathcal{S}}^{(1)}_{A})_{c}$ then
$\\{\,i\mid\alpha^{(1)}_{i}\sqsubseteq f\,\\}$. Since
$\mathrm{graph}(f)=\bigcup\\{\,\mathrm{graph}(s)\mid
s\in\textsc{Anf}^{(1)}_{A}\wedge s\sqsubseteq f\,\\}$ we have,

$\langle x,y\rangle\in\mathrm{graph}(f)\Leftrightarrow(\exists
i)\,\alpha^{(1)}_{A}\sqsubseteq f\wedge\lg(i)>x\wedge\langle\langle
i,x\rangle,y+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda a,z.\
\alpha^{(1)}_{a}(z)).$

Because the extended graph of the universal function of $\alpha^{(1)}$ is
computable, by Lemma 6.1(2), it follows that $\mathrm{graph}(f)$ is c.e. With
Lemma 5.2(2) we therefore have that $f\in\mathcal{S}^{(1)}_{A}$.

(4) As in the proof of Lemma 6.1(5) it is only required that $\theta$
satisfies Condition (QGN I), it follows that every numbering of
$\mathcal{S}^{(1)}_{A}$ with Property (QGN I) satisfies Condition (A I).
Conversely, assume that $\theta$ is a numbering of $\mathcal{S}^{(1)}_{A}$
satisfying Condition (A I). Then it follows as in the proof of Statement (3)
that $\mathrm{graph}_{\mathrm{e}}(\lambda j,x.\ \theta_{j}(x))$ is c.e. Thus,
$\theta$ meets Requirement (QGN I).

Next assume that $\theta$ has Property (QGN II) and let $\alpha^{(1)}[W_{i}]$
be directed. Then there exists some $r\in\widehat{\mathcal{S}}^{(1)}_{A}$ with
$r=\bigsqcup\alpha^{(1)}[W_{i}]$. Hence,

$\mathrm{graph}(r)=\\{\,\langle x,y\rangle\mid(\exists j)\,j\in
W_{i}\wedge\langle\langle
j,x\rangle,y+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda a,z.\
\alpha^{(1)}_{a}(z))\,\\},$

which implies that $r\in\mathcal{S}^{(1)}_{A}$. As we moreover see,
$\mathrm{graph}_{\mathrm{e}}(r)$ can be uniformly enumerated in $i$.
Therefore, by Condition (QGN II), there is a function $v\in\mathcal{R}^{(1)}$
so that $\theta_{v(i)}=r=\bigsqcup\alpha^{(1)}[W_{i}]$. Thus, $\theta$ fulfils
Requirement (A II). Since, for any $k\in\mathcal{R}^{(2)}$, the set
$\\{\,j\mid\mathrm{graph}_{\mathrm{e}}(\alpha^{(1)})\subseteq\mathrm{range}(\lambda
t.\ k(i,t))\,\\}$ is c.e., uniformly in $i$, it conversely follows that
$\theta$ has Property (QGN II), once it satisfies Requirement (A II).

(5) Let $C\subset\omega$ be a c.e. set that defines $G$. Then

$\displaystyle\mathrm{graph}($
$\displaystyle\alpha^{(1)}_{i})\subseteq\mathrm{graph}(G(\alpha^{(1)}_{j}))$
$\displaystyle\Leftrightarrow\mbox{}$ $\displaystyle(\forall x<\lg(i))(\exists
a)\,\langle\langle\langle x\rangle,\alpha^{(1)}_{i}(x)\rangle,a\rangle\in
C\wedge(\forall
c\leq\mathrm{lth}(a))\,(a)_{c}\in\mathrm{graph}(\alpha^{(1)}_{j})$
$\displaystyle\Leftrightarrow\mbox{}$ $\displaystyle(\forall x<\lg(i))(\exists
y)(\exists a)\,\langle\langle
i,x\rangle,y+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda b,z.\
\alpha^{(1)}_{b}(z))\wedge\langle\langle\langle x\rangle,y\rangle,a\rangle\in
C\wedge\mbox{}$ $\displaystyle(\forall c\leq\mathrm{lth}(a))\,\langle\langle
j,\pi^{(2)}_{1}((a)_{c})\rangle,\pi^{(2)}_{2}((a)_{c})+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda
b,z.\ \alpha^{(1)}_{b}(z)).$

By Lemma 6.1(2) $\mathrm{graph}_{\mathrm{e}}(\lambda a,z.\
\alpha^{(1)}_{a}(z))$ is c.e. With the Tarski-Kuratowski algorithm [36] we can
now bring this expression in a $\Sigma_{1}$-form from which we see that
$\\{\,\langle
i,j\rangle\mid\mathrm{graph}(\alpha^{(1)}_{i})\subseteq\mathrm{graph}(G(\alpha^{(1)}_{j}))\,\\}$
is c.e.

Conversely assume that $V\overset{\mathrm{Def}}{=}\\{\,\langle
i,j\rangle\mid\mathrm{graph}(\alpha^{(1)}_{i})\subseteq\mathrm{graph}(G(\alpha^{(1)}_{j}))\,\\}$
is c.e. Moreover, Let $r\in\widehat{\mathcal{S}}^{(1)}_{A}$. By the continuity
of $G$ have that

$\displaystyle\langle\langle x\rangle,z\rangle\in\mbox{}$
$\displaystyle\mathrm{graph}(G(r))$ $\displaystyle\Leftrightarrow\mbox{}$
$\displaystyle(\exists i)(\exists a)\,\alpha^{(1)}_{i}\sqsubseteq
G(\alpha^{(1)}_{a})\wedge\langle
x,z\rangle\in\mathrm{graph}(\alpha^{(1)}_{i})\wedge\alpha^{(1)}_{a}\sqsubseteq
r$ $\displaystyle\Leftrightarrow\mbox{}$
$\displaystyle(\exists\bar{a})(\exists a)(\exists i)\langle\langle
i,x\rangle,z+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda b,u.\
\alpha^{(1)}_{b}(u))\wedge\langle i,a\rangle\in V\wedge\mbox{}$
$\displaystyle\mathrm{lth}(\bar{a})=\lg(a)\wedge(\forall
c\leq\lg(a))\,\pi^{(2)}_{1}((\bar{a})_{c})=c\wedge\mbox{}$
$\displaystyle\langle\langle
a,c\rangle,\pi^{(2)}_{2}((\bar{a})_{c})+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda
b,u.\ \alpha^{(1)}_{b}(u))\wedge(\bar{a})_{c}\in\mathrm{graph}(r).$

Therefore by setting

$C\overset{\mathrm{Def}}{=}\\{\,\langle\langle\langle
x\rangle,z\rangle,\bar{a}\rangle\mid(\exists a)(\exists i)\langle\langle
i,x\rangle,z\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda b,u.\
\alpha^{(1)}_{b}(u))\wedge\langle i,a\rangle\in V\wedge\mbox{}\\\
\mathrm{lth}(\bar{a})=\lg(a)\wedge\pi^{(2)}_{1}((\bar{a})_{c})=c\wedge\langle\langle
a,c\rangle,\pi^{(2)}_{2}((\bar{a})_{c})+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda
b,u.\ \alpha^{(1)}_{b}(u))\,\\},$

we obtain that $C$ is c.e. and defines $G$. ∎

The next result shows that each of the algebraic domains
$\widehat{\mathcal{S}}^{(1)}_{A}$ can be computably mapped onto any other
effectively given domain. For the proof we need an extension of a result by
Weihrauch and Schäfer [46].

######  Proposition 8.8.

Let $D$ be an effectively given domain with basis $B$ and numbering $\beta$ of
the base elements. Then there is a computable operator
$D\colon\widehat{\mathcal{S}}^{(1)}_{\omega}\to\widehat{\mathcal{S}}^{(1)}_{\omega}$
such that the following statements hold for
$f,g\in\widehat{\mathcal{S}}^{(1)}_{\omega}$,

  1. 1.

If $f\in\mathcal{R}^{(1)}$ then also $G(f)\in\mathcal{R}^{(1)}$.

  2. 2.

If $f\in\textsc{Anf}^{(1)}_{\omega}$ then also
$G(f)\in\textsc{Anf}^{(1)}_{\omega}$.

  3. 3.

For all $a\in\mathrm{dom}(G(f))$, $\beta(G(f)(a))\ll\beta(G(f)(a+1))$.

  4. 4.

If $\beta[\mathrm{range}(f)]$ is directed then
$\bigsqcup_{a}\beta(G(f)(a))\sqsubseteq\bigsqcup\beta[\mathrm{range}(f)]$.

  5. 5.

If $f\in\mathcal{R}^{(1)}$ and $\beta[\mathrm{range}(f)]$ is directed then
$\bigsqcup_{a}\beta(G(f)(a))=\bigsqcup\beta[\mathrm{range}(f)]$.

  6. 6.

If $f\sqsubseteq g$ then
$\bigsqcup_{a}\beta(G(f)(a))\sqsubseteq\bigsqcup_{a}\beta(G(g)(a))$.

  7. 7.

For $f\in\textsc{Anf}^{(1)}_{\omega}$, $\bigsqcup_{a}\beta(G(f)(a))\in B$.

###### Proof.

Since $\\{\,\langle i,j\rangle\mid\beta_{i}\ll\beta_{j}\,\\}$ is c.e., there
are functions $k\in\mathcal{R}^{(2)}$ and $h\in\mathcal{R}^{(1)}$ so that
$\lambda t.\ k(t,j)$ enumerates $\\{\,i\mid\beta_{i}\ll\beta_{j}\,\\}$ and $h$
enumerates $\\{\,\langle i,j\rangle\mid\beta_{i}\ll\beta_{j}\,\\}$. Now, we
define functions $q,p,r\in\mathcal{R}^{(1)}$:

If $\mathrm{lth}(a)\leq 1$, we set

$p(a)\overset{\mathrm{Def}}{=}q(a)\overset{\mathrm{Def}}{=}i_{\bot}\quad\text{and}\quad
r(a)\overset{\mathrm{Def}}{=}1.$

Here, $i_{\bot}$ is a $\beta$-index of $\bot$.

In case that $a=[\\![a_{0},\ldots,a_{m+1}]\\!]$ and $q(a^{\prime})$ as well as
$p(a^{\prime})$ and $r(a^{\prime})$ are already defined for
$a^{\prime}=[\\![a_{0},\ldots,a_{m}]\\!]$, say $r(a^{\prime})=\langle
t,c\rangle$, then we define $q(a)$, $p(a)$ and $r(a)$ as follows: if there is
$\langle i,j\rangle\leq m+1$ with

$\\{\langle k(c,a_{t}),k(j,a_{i})\rangle,\langle
p(a^{\prime}),k(j,a_{i})\rangle\\}\subset\\{h(0),\ldots,h(m+1)\\},$

then set

$\displaystyle q(a)\overset{\mathrm{Def}}{=}p(a^{\prime}),$
$p(a)\overset{\mathrm{Def}}{=}k(j,a_{i})$, for the smallest number $\langle
i,j\rangle$ with this property, $\displaystyle
r(a)\overset{\mathrm{Def}}{=}r(a^{\prime})+1.$

If there is no such number $\langle i,j\rangle$, then set

$\displaystyle q(a)\overset{\mathrm{Def}}{=}\pi^{(2)}_{1}(\mu\langle
b,a\rangle.\ \\{\langle q(a^{\prime}),b\rangle,\langle
b,p(a^{\prime})\rangle\\}\subseteq\\{h(0),\ldots,h(n)\\}),$ $\displaystyle
p(a)\overset{\mathrm{Def}}{=}p(a^{\prime}),$ $\displaystyle
r(a)\overset{\mathrm{Def}}{=}r(a^{\prime}).$

As follows form the definition,
$\beta_{q(a^{\prime})}\ll\beta_{p(a^{\prime})}$. By Lemma 8.1(5) there is thus
always a number $\langle b,n\rangle$ with the above property. Hence, $q(a)$ is
defined also in this case.

In addition to the above let $v\in\mathcal{R}^{(1)}$ with

$\displaystyle v([\\![\text{empty
sequence}]\\!])\overset{\mathrm{Def}}{=}[\\![\text{empty sequence}]\\!],$
$\displaystyle
v([\\![a_{0},\ldots,a_{m}]\\!])\overset{\mathrm{Def}}{=}[\\![\langle
0,a_{0}\rangle,\ldots,\langle m,a_{m}\rangle]\\!].$

Moreover, let

$C\overset{\mathrm{Def}}{=}\\{\,\langle\langle\mathrm{lth}(a),q(a)\rangle,v(a)\rangle\mid
a\in\omega\,\\}.$

Then $C$ is c.e. As is readily seen, $C$ defines a computable operator $G$ on
$\widehat{\mathcal{S}}^{(1)}_{\omega}$. For
$f\in\widehat{\mathcal{S}}^{(1)}_{\omega}$ with non-empty domain it follows
that $\mathrm{dom}(f)=\mathrm{dom}(G(f))$. $G$ maps the nowhere defined
function onto the function that for $0$ has value $i_{\bot}$, and is
undefined, otherwise. This implies Statements (1) and (2).

Let $\overline{f}(m)\overset{\mathrm{Def}}{=}[\\![f(0),\ldots,f(m)]\\!]$. Then
we obtain from the definition of $G$ that for $a^{\prime}=\overline{f}(m)$ and
$a=\overline{f}(m+1)$, $G(f)(m)=q(a^{\prime})$ and $G(F)(m+1)=q(a)$. Since
$\beta_{q(a^{\prime})}\ll\beta_{q(a)}$, this proves Statement (3). In
particular, we have that $\bigsqcup_{a}\beta(G(f)(a))$ exists. Moreover,
Statements (6) and (7) follow, because $G$ is monotone by Theorem 6.4 and by
Statement (2), $\mathrm{dom}(G(f))$ is finite, for functions
$f\in\textsc{Anf}^{(1)}_{\omega}$.

For Statements (4) and (5), finally, let $f\in\mathcal{R}^{(1)}$ so that
$\beta[\mathrm{range}(f)]$ is directed. First, we show that the sequnce
$(r(\overline{f}(m)))_{m\in\omega}$ is unbounded. Assume that
$r(\overline{f}(m))=\langle t,c\rangle$. Since the set $\\{\,u\in B\mid
u\ll\bigsqcup\beta[\mathrm{range}(f)]\,\\}$ is directed with respect to $\ll$
by Lemma 8.1(5), there is some $m^{\prime}\geq m$ and a number $\langle
i,j\rangle\leq m+1$ so that

$\\{\langle k(c,f(t)),k(j,f(i))\rangle,\langle
p(\overline{f}(m)),k(j,f(i))\rangle\\}\subseteq\\{h(0),\ldots,h(m^{\prime}+1)\\}.$
(6)

Suppose that $u\in B$ with $u\ll\beta(f(t))$. The there is some $c$ with
$\beta(k(c,f(t))=u$. Moreover, because the sequence
$(r(\overline{f}(m)))_{m\in\omega}$ is unbounded, there is some $m^{\prime}$
with $r(\overline{f}(m^{\prime}))=\langle t,c\rangle$ as well as some smallest
number $\langle i,j\rangle\leq m^{\prime}+1$ so that the inclusion in (6)
holds. Thus, $u\ll\beta(k(j,f(i)))$. Consequently, since
$k(j,f(i))=G(f)(\widehat{m})$, for some $\widehat{m}\geq m^{\prime}+1$, it
follows that
$\bigsqcup\beta[\mathrm{range}(f)]\sqsubseteq\bigsqcup_{m}\beta(G(f)(m))$.

As follows from the above definitions, we have for
$g\in\widehat{\mathcal{S}}^{(1)}_{\omega}$ that for every $m$ there is some
$i$ with $\beta(G(g)(m))\ll\beta(g(i))$. Therefore,
$\bigsqcup_{m}\beta(G(g)(m))\sqsubseteq\bigsqcup\beta[\mathrm{range}(G)]$, if
$\beta[\mathrm{range}(G)]$ is directed. This shows Statement (4) and, with
what we derived before, also Statement (5). ∎

######  Theorem 8.9.

Let $A\subseteq\omega$ be a c.e. infinite set and $D$ be an effectively given
domain with basis $B$ and numbering $\beta$ of the base elements. Then there
is a computable onto map $\Gamma\colon\widehat{\mathcal{S}}^{(1)}_{A}\to D$ so
that for $f,g\in\widehat{\mathcal{S}}^{(1)}_{A}$,

  1. 1.

If $f\in\textsc{Anf}^{(1)}_{A}$ then $\Gamma(f)\in B$.

  2. 2.

If $\beta[\mathrm{range}(f)]$ is directed then
$\Gamma(f)\sqsubseteq\bigsqcup\beta[\mathrm{range}(f)]$.

  3. 3.

If $f\in\mathcal{R}^{(1)}$ and $\beta[\mathrm{range}(f)]$ is directed then
$\Gamma(f)=\bigsqcup\beta[\mathrm{range}(f)]$.

###### Proof.

Let
$G\colon\widehat{\mathcal{S}}^{(1)}_{\omega}\to\widehat{\mathcal{S}}^{(1)}_{\omega}$
be the computable operator constructed in the preceding Lemma. Then we define
for $f\in\widehat{\mathcal{S}}^{(1)}_{A}$,

$\Gamma(f)\overset{\mathrm{Def}}{=}\bigsqcup_{a}\beta(G(f)(a)).$

Since the basis $B$ is countable, every domain element is the least upper
bound of a sequence that is monotonically increasing with respect to $\ll$.
Because of Property (5) of the preceding lemma it therefore follows that
$\Gamma$ is onto. We will show that $\Gamma$ is continuous. Let to this end
$u\in B$. Since $G$ is continuous by Theorem 6.4, we have

$\displaystyle u\ll\Gamma(f)$ $\displaystyle\Leftrightarrow
u\ll\bigsqcup_{a}\beta(G(f)(a))$ $\displaystyle\Leftrightarrow(\exists
a)\,u\ll\beta(G(f)(a))$ $\displaystyle\Leftrightarrow(\exists
a)\,u\ll\beta((\bigsqcup\\{\,G(s)\mid s\in\textsc{Anf}^{(1)}_{A}\wedge
s\sqsubseteq f\,\\})(a))$ $\displaystyle\Leftrightarrow(\exists a)(\exists
s\in\textsc{Anf}^{(1)}_{A})\,s\sqsubseteq f\wedge a\in\mathrm{dom}(G(s))\wedge
u\ll\beta(G(s)(a)).$

In the same way we obtain that

$u\ll\bigsqcup\\{\,\Gamma(s)\mid s\in\textsc{Anf}^{(1)}_{A}\wedge s\sqsubseteq
f\,\\}\Leftrightarrow\mbox{}\\\ (\exists a)(\exists
s\in\textsc{Anf}^{(1)}_{A})\,s\sqsubseteq f\wedge a\in\mathrm{dom}(G(s))\wedge
u\ll\beta(G(s)(a)).$

Since every domain element $x$ is uniquely determined by the set $B_{x}$, it
follows that $\Gamma$ is continuous. It remains to show that $\\{\,\langle
i,j\rangle\mid\beta_{j}\ll\Gamma(\alpha^{(1)}_{i})\,\\}$ is c.e. We have that

$\displaystyle\beta_{j}$ $\displaystyle\ll\Gamma(\alpha^{(1)}_{i})$
$\displaystyle\Leftrightarrow\mbox{}$ $\displaystyle(\exists
a)\,\beta_{j}\ll\beta(G(\alpha^{(1)}_{i})(a))$
$\displaystyle\Leftrightarrow\mbox{}$ $\displaystyle(\exists a)(\exists
b)\,\beta_{j}\ll\beta_{b}\wedge b=G(\alpha^{(1)}_{i})(a)$
$\displaystyle\Leftrightarrow\mbox{}$ $\displaystyle(\exists a)(\exists
b)(\exists c)(\exists m)\,\beta_{j}\ll\beta_{b}\wedge
b=\alpha^{(1)}_{m}(c)\wedge\mathrm{graph}(\alpha^{(1)}_{m})\subseteq\mathrm{graph}(G(\alpha^{(1)}_{i}))$
$\displaystyle\Leftrightarrow\mbox{}$ $\displaystyle(\exists a)(\exists
b)(\exists c)(\exists m)\,\beta_{j}\ll\beta_{b}\wedge\langle\langle
m,c\rangle,b+1\rangle\in\mathrm{graph}_{\mathrm{e}}(\lambda\hat{\imath},n.\
\alpha^{(1)}_{\hat{\imath}}(n))\wedge\mbox{}$
$\displaystyle\mathrm{graph}(\alpha^{(1)}_{m})\subseteq\mathrm{graph}(G(\alpha^{(1)}_{i})).$

Since the set of all $\langle i,m\rangle$ with
$\mathrm{graph}(\alpha^{(1)}_{m})\subseteq\mathrm{graph}(G(\alpha^{(1)}_{i}))$
is c.e. by Theorem 6.4 and
$\mathrm{graph}_{\mathrm{e}}(\lambda\hat{\imath},n.\
\alpha^{(1)}_{\hat{\imath}}(n))$ is c.e. by Lemma 6.1, the set of all $\langle
i,j\rangle$ with $\beta_{j}\ll\Gamma(\alpha^{(1)}_{i})$ is c.e. as well.
Therefore, $\Gamma$ is computable. Properties (1)-(3) are a consequence of the
corresponding properties of $G$, ∎

Assume that the domain $D$ in the previous result is also algebraic. Then we
have for $u\in B$ and $x\in D$ that $u\ll x$ exactly if $u\sqsubseteq x$. As
is readily seen, in this case for every base element $u$ of the domain one can
find an initial segment function in $\textsc{Anf}^{(1)}_{A}$ that is mapped
onto $u$ under $\Gamma$. This initial segment map can be chosen in such a way
that it has only $\beta$-indices of $\bot$ and $u$ as values. This makes the
idea of extending representations as they are used in computable analysis e.g.
(cf. [48]) to maps from $\widehat{\mathcal{S}}^{(1)}_{A}$ to domains precise
that was mentioned at the beginning of this paper: initial segment functions
are used as names for approximating base elements, or the Scott-open sets they
determine, and total functions are names for the limit elements they
approximate. By the monotoniciy of $\Gamma$ the relation of approximation
between the functions in $\widehat{\mathcal{S}}^{(1)}_{A}$, that is the names,
is transferred to the domain.

Next, we will show that via the mapping $\Gamma$ numberings of $D_{c}$ can be
generated from numberings of $\mathcal{S}^{(1)}_{A}$.

######  Theorem 8.10.

Let $A\subseteq\omega$ be a c.e. infinite set and $D$ be an effectively given
domain. Moreover, let $\theta$ be a numbering of $\mathcal{S}^{(1)}_{A}$.
Define

$\eta_{i}\overset{\mathrm{Def}}{=}\Gamma(\theta_{i})\quad(i\in\omega).$

Then $\eta$ is a numbering of the computable elements of $D$ such that:

  1. 1.

If $\theta$ satisfies (QGN I) then $\eta$ meets Condition (A I).

  2. 2.

If $\theta$ satisfies (QGN II) then $\eta$ meets Condition (A II).

  3. 3.

If $\theta$ is quasi-Gödel numbering then $\eta$ is admissible.

###### Proof.

By Corollary 8.6, $\Gamma$ maps $\mathcal{R}^{(1)}$ onto $D_{c}$. Therefore,
the mapping $\eta$ defined above is a numbering of $D_{c}$.

(1) Because of the continuity of $\Gamma$ we have that

$\displaystyle\beta_{i}\ll\eta_{j}$
$\displaystyle\Leftrightarrow\beta_{i}\ll\Gamma(\theta_{j})$
$\displaystyle\Leftrightarrow\beta_{i}\ll\Gamma(\bigsqcup\\{\,\alpha^{(1)}_{n}\mid\alpha^{(1)}_{n}\sqsubseteq\theta_{j}\,\\})$
$\displaystyle\Leftrightarrow\beta_{i}\ll\bigsqcup\\{\,\Gamma(\alpha^{(1)}_{n})\mid\alpha^{(1)}_{n}\sqsubseteq\theta_{j}\,\\})$
$\displaystyle\Leftrightarrow(\exists
n)\,\beta_{i}\ll\Gamma(\alpha^{(1)}_{n})\wedge\alpha^{(1)}_{n}\sqsubseteq\theta_{j}.$

Since $\Gamma$ is computable, the set $\\{\,\langle
i,j\rangle\mid\beta_{i}\ll\Gamma(\alpha^{(1)}_{n})\,\\}$ is c.e. By Lemma 6.1
the same is true for $\\{\,\langle
n,j\rangle\mid\alpha^{(1)}_{n}\sqsubseteq\theta_{j}\,\\}$, if $\theta$
satisfies (QGN I). Thus, also $\\{\,\langle
i,j\rangle\mid\beta_{i}\ll\eta_{j}\,\\}$ is c.e. in this case. That is, $\eta$
meets the (A I) requirement.

(3) Let $\theta$ be a quasi-Gödel numbering. We need to construct a function
$v\in\mathcal{R}^{(1)}$ so that $\theta_{v(i)}$ enumerates $W^{A}_{i}$ in such
a way that $\theta_{v(i)}\in\mathcal{R}^{(1)}$, if $W^{A}_{i}$ is not empty.
By (QGN I) there is a function $h\in\mathcal{R}^{(1)}$ enumerating the
universal function of $\theta$. Define

$\displaystyle\widehat{Q}(i,a,z)\Leftrightarrow\pi^{(2)}_{1}(h(a))=\langle
i,\pi^{(2)}_{1}((z)_{\mathrm{lth}(z)})\rangle\wedge\pi^{(2)}_{2}(h(a))>0,$
$\displaystyle Q(i,t,z)\Leftrightarrow(\exists a\leq t)\,\widehat{Q}(i,a,z),$
$\displaystyle f(i,t,z)\overset{\mathrm{Def}}{=}\pi^{(2)}_{2}(h(\mu a\leq t.\
\widehat{Q}(i,a,z))).$

Now, construct $k\in\mathcal{R}^{(2)}$ according to Lemma 4.2 so that $\lambda
t.\ k(i,t)$ enumerates the extended graph of a function
$g\in\mathcal{R}^{(1)}$ that enumerates $W^{A}_{i}$, if $W^{A}_{i}$ is not
ermpty, and the extended graph of the nowhere defined function, otherwise. By
Condition (QGN II) there is then a function $v\in\mathcal{R}^{(1)}$ that has
the properties we were looking for.

Assume that $\beta[W_{i}]$ is directed. Then $W_{i}$ is not empty. As we have
seen, $W$ and $W^{A}$ are computably isomorphic. Thus, there is some
$s\in\mathcal{R}^{(1)}$ so that $W_{i}=W^{A}_{s(i)}$. Set
$d\overset{\mathrm{Def}}{=}v\circ s$. Then it follows wth Theorem 8.9(3) that

$\eta_{d(i)}=\Gamma(\theta_{d(i)})=\bigsqcup\beta[\mathrm{range}(\theta_{d(i)})]=\bigsqcup\beta[W^{A}_{s(i)}]=\bigsqcup\beta[W_{i}].$

Hence, $\eta$ satisfies Requirement (A II). As seen in Step (3), $\eta$ also
satisfies (A I). Therefore, $\eta$ is admissible.

(2) Let $\psi$ be a quasi-Gödel numbering of $\mathcal{S}^{(1)}_{A}$, and let
$\theta$ satisfy (QGN II). By Theorem 7.2 there is some
$g\in\mathcal{R}^{(1)}$ with $\psi=\theta\circ g$. Let $\gamma$ be the
numbering of $D_{c}$ defined by
$\gamma_{i}\overset{\mathrm{Def}}{=}\Gamma(\psi_{i})$. Then we have that
$\gamma\leq_{m}\eta$. Since $\gamma$ is admissible by what was shown in the
previous step, it follows with Proposition 8.4 that $\eta$ satisfies (A II). ∎

As we see, via the mapping $\Gamma$ numberings of $D_{c}$ with Properties (A
I) and\or (A II) can be obtained from numberings of $\mathcal{S}^{(1)}_{A}$. A
natural question now is whether all numberings of $D_{c}$ with these
properties can be obtained in this way.

Set

$\widehat{\Gamma}(\theta)_{i}\overset{\mathrm{Def}}{=}\Gamma(\theta_{i}).$

Then $\widehat{\Gamma}$ is a mapping from the set of all numberings of
$\mathcal{S}^{(1)}_{A}$ into the set of all numberings of $D_{c}$. As follows
from the definition, $\widehat{\Gamma}$ is monotone with respect to
$\leq_{m}$.

######  Theorem 8.11.

Let $A\subseteq\omega$ be a c.e. infinite set and $D$ be an effectively given
domain. Then the following statements hold:

  1. 1.

For every admissible numbering $\eta$ of $D_{c}$ there is a quasi-Gödel
numbering $\theta$ of $\mathcal{S}^{(1)}_{A}$ with
$\eta=\widehat{\Gamma}(\theta)$.

  2. 2.

For every numbering $\eta$ of $D_{c}$ satisfying (A I) there is a numbering
$\theta$ of $\mathcal{S}^{(1)}_{A}$ satisfying (QGN I) with
$\eta=\widehat{\Gamma}(\theta)$.

###### Proof.

(1) Let $\psi$ be a quasi-Gödel numbering of $\mathcal{S}^{(1)}_{A}$ and
$\eta$ an admissible numbering of $D_{c}$. By the previous theorem,
$\widehat{\Gamma}(\psi)$ is a admissible numbering as well. Hence, $\eta$ and
$\widehat{\Gamma}(\psi)$ are computably isomorphic, by Proposition 8.4. Thus,
there is a computable permutation $g\in\mathcal{R}^{(1)}$ with
$\eta=\widehat{\Gamma}(\psi)\circ g$, that is, $\eta_{i}=\Gamma(\psi_{g(i)})$.
Let $\theta\overset{\mathrm{Def}}{=}\psi\circ g$. Then also $\theta$ is a
quasi-Gödel numbering. Moreover, $\eta=\widehat{\Gamma}(\theta)$.

(2) As has already been mentioned, $D_{c}$ has an admissible numbering, say
$\gamma$. Let $\psi$ be the quasi-Gödel numbering with
$\gamma=\widehat{\Gamma}(\psi)$, existing by Statement (1). If $\eta$ is a
numbering of $D_{c}$ satisfying (A I), then $\eta\leq_{m}\gamma$, by
Proposition 8.4. Therefore, there is some $g\in\mathcal{R}^{(1)}$ with
$\eta=\gamma\circ g$. Define $\theta\overset{\mathrm{Def}}{=}\psi\circ g$.
Then it follows with Proposition 7.1 that $\theta$ satisfies Condition (QGN
I). Moreover, $\widehat{\Gamma}(\theta)=\eta$. ∎

The question whether an analogue of Statement (2) is true for numberings of
$D_{c}$ that satisfy Requirement (A II) remains open.

We call numberings of $D_{c}$ that satisfy (A I) _computable_. As in the case
of the numberings of $\mathcal{S}^{(1)}_{A}$ the $m$-equivalence classes of
the numberings of $D_{c}$ form a Rogers semi-lattice in which the
$m$-equivalence classes of the computable numberings form a Rogers sub-semi-
lattice with the class of admissible numberings as greatest element. Let again
$\eta\oplus\gamma$ be the direct sum of the numberings $\eta$ and $\gamma$ of
$D_{c}$. Then it follows for numberings $\psi$ and $\theta$ of
$\mathcal{S}^{(1)}_{A}$ that

$\widehat{\Gamma}(\psi\oplus\theta)=\widehat{\Gamma}(\psi)\oplus\widehat{\Gamma}(\theta).$

Moreover, let $\widehat{\Gamma}_{\equiv}$ be the quotient map, that is,
$\widehat{\Gamma}_{\equiv}([\psi])=[\widehat{\Gamma}(\psi)]$.

######  Corollary 8.12.

$\widehat{\Gamma}_{\equiv}$ is a homomorphism of the Rogers semi-lattice of
the numberings of $\mathcal{S}^{(1)}_{A}$ in the Rogers semi-lattice of the
numberings of $D_{c}$ which maps the Rogers sub-semi-lattice of computable
numberings of $\mathcal{S}^{(1)}_{A}$ onto the Rogers sub-semi-lattice of
computable numberings of $D_{c}$.

.

##  9 Conclusion

Non-termination is a typical phenomenon of algorithms. It cannot be read of
the program text whether and in which case it will happen. Approaches to avoid
it have been studied and require advanced methods. The question we dealt with
in this paper was whether there is a class of algorithms that compute the
total (computable) functions—in which one is actually only interested in—, and
if non-termination occurs then the area of such inputs has a well-defined
structure.

We presented such a class. The typical algorithm we had in mind when starting
this research was list searching or the computation of approximations of
infinite objects like the real numbers. The algorithms in this class are such
that their domain of definition is either the set of all natural numbers, or a
finite initial segment of this set of a length in a given set of possible
lengths. It is shown that even though besides the total functions there are
now only finite partial functions, a rich computability theory can be
developed in which the same important results hold as in the classical theory
dealing with all possible algorithms. In particular, the theory of computably
enumerable set remains unchanged, except that the domain characterisation of
these set is no longer useful. What is presented is a development of
computability theory based on the notion of enumeration. The main ingredient
in the new approach is the notion of a quasi-Gödel numbering which takes on
the role of Gödel numberings in the classical approach. Every Gödel numbering
is also a quasi-Gödel numbering.

Besides developing computability theory on the basis of quasi-Gödel
numberings, meta-investigations have been carried out: the new quasi-Gödel
numbered function classes are a retract of the Gödel numbered class of all
partial computable functions. Moreover, it is the class of computable elements
of an effectively given algebraic domain (in the sense of Scott-Ershov) that
can be computably mapped onto any other effectively given domain so that the
finite functions in the function classes considered here are mapped to base
elements. This extends the use of representations in computable analysis in
such a way that now also the basic open sets used for approximations obtain a
finite function as name. Via the mapping every quasi-Gödel numbering induces
an admissible numbering of the computable domain elements. It was shown that
every admissible numbering can obtained in this way.

## References

  * [1] O. Aberth. _Computable Analysis_. McGraw-Hill, New York, 1980.
  * [2] S. Abramsky and A. Jung. Domain theory. In S. Abramsky et al., editors, _Handbook of Logic in Computer Science, vol. 3, Semantic Structures_ , Clarendon Press, Oxford, 1994, pages1–168.
  * [3] R. M. Amadio and P.-L. Curien. _Domains and Lambda-Calculi_ , Cambridge University Press, Cambridge, 1998.
  * [4] M. Davis. _Computability and Unsolvability_. Mc-Graw-Hill, New York, 1958.
  * [5] T. Deil. _Darstellungen und Berechenbarkeit reeller Zahlen_. Ph.D. thesis. Fernuniversität Hagen, 1983.
  * [6] Yu. L. Ershov. Computable functionals of finite types. _Algebra i Logika_ , 11: 367–437, 1972; English translation, _Algebra and Logic_ , 11: 203–242, 1973.
  * [7] Yu. L. Ershov. Theorie der Numerierungen I. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ , 19: 289–388, 1973.
  * [8] Yu. L. Ershov. Theorie der Numerierungen II. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ , 21: 473–584, 1975.
  * [9] B. Goetze. Die Struktur des Halbverbandes der effektiven Numerierungen. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ , 20, 183–188, 1974.
  * [10] B. Goetze. The structure of the lattice of recursive sets. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ , 22, 187–191, 1976.
  * [11] D. Gordon and E. Shamir. Computation of recursive functionals using minimal initial segments. _Theoretical Computer Science_ , 23: 305–315, 1983.
  * [12] G. Gierz, K. H. Hoffmann, K. Keimel, J. D. Lawson, M. W. Mislove and D. S. Scott, _Continuous Lattices and Domains_ , Cambridge University Press, Cambridge, 2003.
  * [13] C. A. Gunter and D. S. Scott. Semantic domains. In J. van Leeuwen, editor, _Handbook of Theoretical Computer Science, vol. B, Formal Models and Semantics_ , Elsevier, Amsterdam, 1990, pages 633–674.
  * [14] J. Hauck. Zur Präzisierung des Begriffs berechenbare reelle Funktion. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ ,17: 295–300. 1971.
  * [15] J. Hauck. Berechenbare reelle Funktionen. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ , 19:121–140, 1973.
  * [16] J. Hauck. Berechenbare reelle Funktionenfolgen. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ , 22: 265–282, 1976.
  * [17] J. Hauck. Konstruktive Darstellungen reeller Zahlen und Funktionen. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ , 24: 365–374, 1978.
  * [18] P. G. Hinman. Finitely approximable sets. In M. M. Richter et al., editors, _Computation and Proof Theory_ , Springer, Berlin, 1984. pages 233–258.
  * [19] J. M. E. Hyland. Filter spaces and continuous functionals. _Annals of Mathematical Logic_ , 16: 101–143, 1979.
  * [20] T. Kamimura and A. Tang. Effectively given spaces. In J. Diaz, editor, _Automata, Languages and Programming_ , Springer, Berlin, 1983, pages 385–396.
  * [21] W. H. Kersjes. _Rekursionstheorie auf Teilmengen von P_. Diplomarbeit. RWTH Aachen, 1982.
  * [22] S. C. Kleene. General recursive functions of natural numbers. _Mathematische Annalen_ , 112: 727–742, 1936.
  * [23] S. C. Kleene. _Introduction to Metamathematics_. Van Nostrand, Princeton, N.J., 1952.
  * [24] A. B. Khutoretskiĭ. On the reducibility of computable numerations. _Algebra i Logika_ , 8: 251–264, 1969; English translation, _Algebra and Logic_ , 8: 145–151, 1970.
  * [25] C. Kreitz and K. Weihrauch. Theory of representation. _Theoretical Computer Science_. 38: 35–53, 1985.
  * [26] A. H. Lachlan. Standard classes of recursively enumerable sets. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ , 10: 23–42, 1964.
  * [27] A. I. Mal’cev. _Algorithms and Recursive Functions_. Wolters-Noordhoff, Groningen, 1970.
  * [28] A. I. Mal’cev. _The Metamathematics of Algebraic Structures. Collected Papers: 1936 - 1967_. B. F. Wells III, editor. North-Holland, Amsterdam, 1971.
  * [29] W. Menzel and V. Sperschneider. Recursively enumerable extensions of $R_{1}$ by finite functions. In E. Börger et al., editors, _Logic and Machines: Decision Problems and Complexity_ , Springer, Berlin,1984, pages 62–76.
  * [30] Y. N. Moschovakis. _Recursive Analysis_. Ph.D. thesis. University of Wisconsin, Madison, Wis., 1963.
  * [31] J, Myhill and J. C. Shepherdson. Effective operations on partial recursive functions. _Zeitschrift für mathematische Logik und Grundlagen der Mathematik_ , 1: 310–317, 1955.
  * [32] M. B. Pour-El. Gödel numberings versus Friedberg numberings. _Proceedings of the American Mathematical Society_ , 15: 252–256, 1964.
  * [33] M. B. Pour-El and J. I. Richards. _Computability in Analysis and Physics_. Springer, Berlin, 1989.
  * [34] H. G. Rice. Classes of recursively enumerable sets and their decision problems. _Transactions of the American Mathematical Society_ , 74: 358–366, 1953.
  * [35] H. Rogers, Jr. Gödel numberings of partial recursive functions. _Journal of Symbolic Logic_ , 23: 331–341, 1958.
  * [36] H. Rogers, Jr. _Theory of Recursive Functions and Effective Computability_. McGraw-Hill, New York, 1967.
  * [37] D. Scott, _Outline of a Mathematical Theory of Computation_. Technical Monograph PRG-2. Oxford University Computing Laboratory, 1970.
  * [38] D. Scott. _Lectures on a Mathematical Theory of Computation_. Technical Monograph PRG-19. Oxford University Computing Laboratory, 1981.
  * [39] D. Scott. Domains for denotational semantics. In M. Nielsen and E. M. Schmidt, editors, _Automata, Languages and Programming_ , Springer, Berlin, 1982, pages 577–613.
  * [40] D. Spreen. _Rekursionstheorie auf Teilmengen partieller Funktionen_. Habilitation thesis. RWTH Aachen, 1985.
  * [41] D. Spreen. Computable one-to-one enumerations of effective domains. _Information and Computation_ , 84(1): 26-45, 1990.
  * [42] V. Stoltenberg-Hansen, I. Lindström and E. R. Griffor. _Mathematical Theory of Domains_. Cambridge University Press. Cambridge, 1994.
  * [43] A, Turing. On computable numbers, with an application to the Entscheidungsproblem. _Proceedings of the London Mathematical Society_ , s2-42(1): 230–265, 1936/37
  * [44] A. Turing. A correction. _Proceedings of the London Mathematical Society_ , s2-43: 544–546, 1937.
  * [45] K. Weihrauch and T. Deil. _Berchenbarkeit auf cpo-s_. Schriften zur Angewandten Mathematik und Informatik Nr. 63. RWTH Aachen, 1980.
  * [46] K. Weihrauch and G. Schäfer. Admissible representations of effective cpo-s. _Theoretical Computer Science_ , 26: 131-141, 1983.
  * [47] K. Weihrauch. _Computability_. Springer, Berlin, 1987.
  * [48] K. Weihrauch. _Computable Analysis_. Springer, Berlin, 2000.