\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
%
%\usepackage[utf8]{inputenc}
\usepackage{t1enc,color,array,rotating,graphicx,mathtools}
\usepackage{soul}
\usepackage{latexsym,amssymb,amsmath,amsfonts,stmaryrd,algorithm,algpseudocode}
\usepackage[english]{babel}
\usepackage{hyperref}
\numberwithin{equation}{section}
\usepackage{graphicx,nicefrac,wrapfig}
\usepackage[textsize=footnotesize]{todonotes}

\usepackage{cleveref,multirow,tikz,xspace,comment,enumitem}
\newcommand{\MK}[2][]{\todo[color=purple!20,#1]{MK: #2}}
%

\def\udcs{510.5} %Here the author places classificators of the paper according to Russian classification system
\def\mscs{03D45, 03D80, 68Q15} %Here the author places  classificators according to the AMS classification list.
\setcounter{page}{1}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
% my def
\newcommand{\Reqast}{{${ \rm \bf Req}^\ast $}}
\newcommand{\Req}{{\rm \bf Req }}
\newcommand{\R}{\mathbb{R}}
\newcommand{\K}{K}
\newcommand{\KRast}{K^\ast}
\newcommand{\KR}{\widetilde{K}}
\newcommand{\RC}{\mathbb{R}_c}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\im}{{\rm im}}
\newcommand{\dom}{{\rm dom}}
\newcommand{\Dyad}{{\rm Dyad}}
\newcommand{\Pt}{{\rm P}}
\newcommand{\SPt}{{\rm S}\Pt}
\newcommand{\AC}{{\rm AC}}
\newcommand{\Tot}{{\rm Tot}}
\newcommand \dotmm {\,{-}\hspace*{-6pt}\parbox{3pt}{\vspace*{-6pt}.}\hspace*{3pt}\,}
\newcommand{\dotminus}{\dotmm}
\newcommand{\BF}{{\rm BF}}
\newcommand{\Sp}{{\rm Sp}}
\newcommand{\str}{{\rm str}}
%
%\newcommand{\dotminus}{-^{.}}
%
\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]  %Headings in Russian
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том {\rm xxx}, стр. {\rm xxx} (2023) \hspace{65mm}{\rm\small УДК \udcs}} %Volume, pages in Russian,
                                                                                    %filled by Editorial board
     \newline
         {\rm\small DOI~10.17377/semi.2023.xxx.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaa}{\rm\small MSC
         \mscs
           }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\proofname}{Proof.}
\thispagestyle{empty}

\title[On the Computability of Ordered Fields]{On the Computability of Ordered Fields}

\author{{M.V.Korovina and O.V.Kudinov}}%
\address{Margarita Vladimirovna Korovina
\newline\hphantom{iii} A.P. Ershov Institute of Informatics Systems,
\newline\hphantom{iii} pr. Acad. Lavrentjev, 6,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{rita.korovina@gmail.com}%
\address{Oleg Victorovich Kudinov
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyug, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{kud@math.nsc.ru}%

\thanks{\sc Korovina, M.V., Kudinov, O.V.,
On the Computability of Ordered Fields}
\thanks{\copyright \ 2023 Korovina M.V., Kudinov O.V}
\thanks{\rm M.V.~Korovina's  research was  carried out within the framework  of the state contract
of the A.P. Ershov Institute  of Informatics Systems (project no.
 FWNU-2021-0003). O.V.~Kudinov's research was  carried out within the framework  of the state contract
of the Sobolev Institute of Mathematics (project no.
 FWNF-2022-0011).
 }
\thanks{\it Received   2020, published    XXX}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. }
%\medskip
In this paper we develop  general techniques  for structures
of computable real numbers generated by  classes of total computable (recursive) functions with special requirements on basic operations in order to investigate the following problems:
whether a generated structure is a real closed field and whether there exists a computable copy of  a generated structure.
We prove a series of theorems that lead to the result that there are no  computable copies
for $\mathcal{E}^n$-computable real numbers, where $\mathcal{E}^n$ is a level  in  Grzegorczyk hierarchy, $n\geq 3$.
We also  propose a criterion of computable presentability of an archimedean ordered field.

\medskip

\noindent{\bf Keywords:} computable analysis,  computability, index set, computable model theory, complexity.
 \end{quote}
}


\section{Introduction}
%historical remarks+ problem statements

 \noindent In the framework of computable model theory originated in \cite{Malcev,Rabin,Ersh_PRCM} there have been investigated
 condi\-tions on the existence of computable copies
  for countable homogeneous boolean algebras \cite{Alaev,Morozov}, for superatomic boolean algebras \cite{Gonch1}, for ordered abelian groups \cite{Khisamiev} among others and established several negative  results for archimedean ordered fields \cite{Miller,KK_spectr}.
%
 Nevertheless,  till now there where no natural criteria on the existence of computable presentations of ordered fields even in an  archimedean case. In this paper we try to fill this gap.


 \noindent We  are also going dipper to revile  relations between a class of computable (recursive) functions $\K$ and  structures $\KR$ and $\KRast$ of
computable real numbers generated by $\K$ corresponding Cauchy approximations and sign-digit expansions.
 We propose natural restrictions on  a class $\K$ under which the structures $\KR$ and $\KRast$ coincide.
 %In this case an element of the structure we call a $\K$-number.
We also revile requirements on $K$ when $\KRast$  is a real closed field.

 %It is worth noting duality: for any computable  archimedean ordered field $(F,+,\cdot,\leq)$
%  one can create the corresponding class $K$ such that $F=\KR$.
% since the diadic numbers is computable defined in $F$

% As an motivating example we can consider the dyadic numbers $\Dyad$. In this case $(\Dyad,+,\cdot,\leq)$ is a computable structure,  the corresponding $\K$ is the set of  computable almost constant functions and  $\Dyad=\KR$.

 Further we investigate a natural problem whether there exist  computable copies of   generated structures for
 popular classes of computable functions such as the
Grzegorczyk classes  $\mathcal{E}^n,\, n\geq 3$.
  We establish that the corresponding real closed fields do not have computable copies.
%
 In order to do that we develop  techniques of index sets and multiple $m$-complete\-ness.
%
   On this way we have to   establish
  a criterion of $m$-completeness for tuples of c.e. sets and $\Sigma^0_2$-sets. From our point of view this criterion is
an interesting result   itself and can be used for different purposes.

%\MK{Trivial ex: comp functions almost zero --- operation - addition should be equivalent to prestburger arithmetic and has  computable presentation}


%\subsection{plan}
%\begin{enumerate}
%\item  Conditions on $K$ when $\KR$ is real closed field Cshegorchik klassii
%\item If $\KR$ has
%\end{enumerate}

%In this paper we address natural problems related to bla-bla

%We give positive answers to these questions.

%
The paper is organised as follows:
 Section~\ref{prelim_sec}  contains preliminaries and  basic background.
%
  In Section~\ref{KR_KRast}  we propose the notions of $\KR$ and $\KRast$ generated structures. We
  show under which requirements on $\K$ the corresponding generated structures $\KR$ and $\KRast$ coincide
  and under which requirements on $\K$ the corresponding generated structure  $\KRast$ is a real closed field. Further we  prove a criterion of the computable presentability of an archimedean ordered field.
%
 \noindent In Section~\ref{index_sets_constructivisiruemih_kr}  we define 3-tuple of index sets $(A_0,A_1,A_2)$ depending on $\K$ such that
$A_i\in\Sigma^0_2$  with the following  embedding property $A_0\subseteq A_1\subseteq A_2$.
In the Theorem~\ref{sigma02construct} we show that if the corresponding $\KR$ as a structure, in particular as  an abelian group, has a computable copy
then $A_0\cup (A_2\setminus A_1)\in \Sigma^0_2$.
%
 In Sections~\ref{m-universality}, \ref{index_sets} and \ref{without_constr} we develop techniques to  establish that   under natural assumptions on a class $K$   the 3-tuple $(A_0,A_1,A_2)$ is $m$-complete in the class of 3-tuples of $\Sigma^0_2$-sets with the embedding property.
It is well-known that in this case $A_0\cup (A_2\setminus A_1)\not\in \Sigma^0_2$ and therefore for the corresponding
$\KR$ there is no a computable copy.
It is worth noting than these classes contain  computable real numbers generated by Grzegorczyk classes, in  particular $\mathcal{E}^3$ and beyond.

%Kasalos bi chem menshe K tem bolshe veroiatnost chto K konstr no eto ne tak ...




%





\section{Preliminaries}\label{prelim_sec}

We refer the reader to \cite{Rogers,Soarehbook} for  basic definitions and fundamental concepts of recursion theory, \cite{Ko,Weihrauchbook} for computable analysis, \cite{ErshGonch} for computable model theory, \cite{Grzegorczyk,Ritchie} for
Grzegorczyk classes $\mathcal{E}^n$, $n\geq 2$, of computable (recursive) functions.
 %and \cite{ALR} for complexity classes.
We recall that, in particular, $\varphi_e$ denotes the partial  computable (recursive) function with  an index $e$ in the Kleene numbering. For simplicity of descriptions  we identify a function with its graph. We also use notations $W_e=\rm {dom}(\varphi_e)$, $ \overline{W_e}=\omega\setminus W_e$,  $\pi_e=\rm {im}(\varphi_e)$,
 $c:\omega^2\to\omega$
 for Cantor  numbering of pairs   and $l:\omega\to\omega$, $r:\omega\to\omega$ for the corresponding functions such that $n= c(l(n),r(n))$.
   We fix the set $\BF$ of standard  basic functions $\lambda x.0,\,s(x)$ and
 $I^n_m$, where $I^n_m(x_1,\dots,x_n)=x_m$ for $1\leq m\leq n$ and denote the total  computable numerical functions as $\mathbb{T}$ and $\Tot=\{n\mid \varphi_n\in \mathbb{T}\}$.
We fix the following computable numbering $q:\omega\to \mathbb{Q}$  of the rational numbers:
\begin{align*}
& \mbox{for }m\geq 0, k>0:\\
&q(2c(m,k))=+\frac{m}{k},\\
&q(2c(m,k)+1)=-\frac{m}{k},\\
&q(c(m,0))= q(c(m,1))=m \mbox{ and}\\
&q(l)=1 \mbox{ for the rest arguments $l$}.
\end{align*}
When it is clear from a context we use  the notation $q_n$ for $q(n)$.
We denote $I=\{2c(m,k)\mid m\in\omega,\, k\in\omega \mbox{ and $\frac{m}{k}$ is irriducible} \}
\cup \{2c(m,k)+1\mid m\in\omega,\, k\in\omega \mbox{ and $\frac{m}{k}$ is irriducible} \}
\cup \{c(m,0)\mid m\in\omega\}$.
For tuples $z_1\dots,z_k$ of numbers or functions  we use the notation $\bar{z}$ when
 it is clear from a context.
 For the positive rational numbers we use the notation
  $\mathbb{Q}^{+}=\{q\in\mathbb{Q}\mid q>0\}$, for the dyadic numbers we use the notation $Dyad=\{\frac{m}{2^{i+1}}\mid m\in \mathbb{Z},\,i\geq 0\}$
  and $B(\alpha,r)=\{x\in\R\mid |x-\alpha|<r\}$,  for an open ball with the center $\alpha\in\mathbb{R}$ and the radius $r\in \mathbb{R}^{+}$.
\subsection{ Computable Presentations}

 We say that a structure ${\mathcal A}=\left <A,\sigma\right >$  with a finite language $\sigma$ admits a  computable presentation  (copy) if there is a numbering $\nu:\omega\to A$ such that  the relations and operations  from $\sigma$ including equality
 are computable  with respect to the numbering $\nu$. The pair $({\mathcal A},\nu)$ is called a computable structure and the numbering $\nu$ is called its computable presentation.

If only operations are computable with respect to the numbering $\nu$, a structure  $({\mathcal A},\nu)$  is called a~numbered (effective) algebra.
\subsection{Grzegorczyk classes}
In this paper we use the following properties of $\mathcal{E}^n$ for $n\geq 2$:
\begin{enumerate}
\item  Every class contains $\BF$ and the functions $+,\,\cdot,\,c(x,y),\,l(x),\,r(x)$.
\item Every class is closed under composition and the standard bounded recursion scheme.
\item Ritchie's characterisation  of $\mathcal{E}^2$ \cite{Ritchie}:
$f\in \mathcal{E}^2$ if and only if an computation on some TM of $f(x_1,\dots,x_m)$ requires the number of cells bounded from above by
$c_f\cdot \sum_{i=1}^m\Big( L(x_i)+1\Big)$, where $L(x)$ is  the
word length in binary notation
 of the number $x$.

\end{enumerate}


\section{Generated Computable Reals}\label{KR_KRast}
\subsection{Definitions}Let $\K$ be a class of total
 %computable
  numerical functions.
% closed under composition.
 We associate with $\K$ the classes
\[\K^{\{0,1,2\}}=\{f\in \K\mid{\rm im}(f)\subseteq \{0,1,2\} \mbox{ and $f$ is a unary function}\}\] and
\[K_1=\{f\mid f\in K \mbox{ and $f$ is a unary function}\}.
\]

Let us define  a subset $K^\ast$  of the computable real numbers as follows:
\begin{align*}
x\in \K^\ast\leftrightarrow (\exists \phi\in \K_1)(\forall n\in\omega)|q_{\phi(n)}-x|<\frac{1}{2^n}.
\end{align*}


 We proceed with the definition of  the corresponding subset $\KR$ of the computable real numbers.
For $f\in\K^{\{0,1,2\}}$ let us denote
\[
 \bar{f}=\sum_{i=0}^\infty\frac{f(i)-1}{2^{i+1}}.
\]

\noindent Then we define   \[\KR=\{m+\bar{f}\mid m\in\mathbb{Z},\, f\in K^{\{0,1,2\}}\}.\]
%
One of the trivial examples, where $\K$ is the set of  the almost constant functions illustrates that in general $\KRast\neq \KR$. Indeed, in this case the generated
class $\KRast$ coincides with $\mathbb{Q}$ while $\KR$ coincides with $\Dyad$.
Below we will show under which requirements on $\K$ we have $\KRast= \KR$.



\noindent In this paper we use requirements \Req on $K$:

\begin{itemize}
\item[Req 1] it   contains the basic functions $\BF$,  and  $\lambda x.2x$,
\item[Req 2] it is closed under composition and
%
$=^\ast$, i.e., if $f\in\K_1$ and $g=^\ast f$ then $g\in\K_1$, where
\[g=^\ast f \leftrightarrow (\exists n\in\omega)(\forall m\geq n)\, g(m)=f(m),\]
\item[Req 3] it   contains computable functions
${\rm Add}:\omega\times \omega\to\omega$, ${\rm Mult}:\omega\times \omega\to\omega$ and ${\rm Inv}:\omega\to\omega$ such that
\begin{align*}
&\forall n\,\forall m\, q_n+ q_m=q_{{\rm Add}(n,m)},\\
&\forall n\,\forall m\, q_n\cdot q_m=q_{{\rm Mult}(n,m)},\\
&\forall n \,(q_n)^{-1}=q_{{\rm Inv}(n)} \mbox{ if } q_n\neq 0.
\end{align*}
%

\end{itemize}
Assume $\K$ satisfies $\rm\bf Req$,   for all $n,\,m\in \omega$, ${\rm Add}(n,m),\, {\rm Mult}(n,m), {\rm Inv}(n)\in I$, where the~set $I$ is defined in Preliminaries and
\begin{itemize}
\item[Req 4] it is closed under
 the following  bounded primitive  recursion scheme:

\noindent if $\alpha\,\,g,\psi\in K$ and $f$ is defined by

  \begin{eqnarray*}
f(\bar{x},y)=\left \{
\begin{array}{lll}
\alpha(\bar{x})&\mbox{ if }& y=0\\
\psi(\bar{x},y,f(\bar{x},y-1)) &\mbox{ if }& y\geq 1
\end{array}
\right.
\end{eqnarray*}
 and
\begin{align*}
f(\bar{x},y)\leq g(\bar{x},y)
\end{align*}
then $f\in K$.
\end{itemize}

 \noindent Then we tell that $\K$ satisfies the requirements  \Reqast.

\begin{lemma}\label{propK}
Let $K$ satisfy the requirements \Reqast and  contain $+,\,\cdot,\,\lambda x.2^x$ then
\begin{itemize}
\item all constant functions are in $K$.
\item $c(x,y),\,l(x),\,r(x)\in K$.

\item Let
  \begin{eqnarray*}
g(n,m)=\left \{
\begin{array}{lll}
2&\mbox{ if }& q_n<q_m\\
1 &\mbox{ if }& q_n=q_m\\
0&\mbox{ if }& q_n>q_m.
\end{array}
\right.
\end{eqnarray*}
Then $g\in K$.
\end{itemize}

\end{lemma}
\begin{lemma}\label{propKRast}

Let $K$ satisfy the requirements \Req and $\phi^\prime\in K_1$ such that, for a real number $x$,
$(\exists N\in\omega)(\forall n\geq N)|q_{\phi^\prime(n)}-x|<\frac{1}{2^n}.$
Then there exists $\phi\in \K_1$ such that $(\forall n\in\omega)|q_{\phi(n)}-x|<\frac{1}{2^n}$,
in other words, $x\in \KRast$.

\end{lemma}
\subsection{  When $\KR=\KRast$}
\begin{proposition}\label{kr_krast}
Let $K$ satisfy the requirements \Reqast and  contain $+,\,\cdot,\,\lambda x.2^x$ then $\KR=\KRast$.
\end{proposition}

\begin{proof} First we show that $\KR\subseteq\KRast$. W.l.o.g. we  assume $f\in K^{\{0,1,2\}}$ and   $x=\bar{f}$.
It is clear that a required function $\phi\in K$ can be  defined by

\[
 q_{\phi(n)}=\sum_{i=0}^n\frac{f(i)-1}{2^{i+1}}.
\]
The numerator of this fraction is bounded by above by $2^{n+1}-1$ and the denominator is  $2^{n+1}$.
It is worth noting that the number of a rational  $q$, where $|q|=\frac{i}{j}$ is bounded from above by $2c(i,j)+1$.
% Therefore
%\begin{align*}
%\Phi(n)\leq
%2c(2^{n+1}-1,2^{n+1})+1\leq 2c(2^{n+2}-1,0)+1
%\end{align*}
%since $c(i,j)<c(i+j+1,0)$ by the definition of Cantor numbering.
By definition  $\lambda x.2^x\in K$ and  $K$ is closed under composition so  by Lemma~\ref{propK} $\phi(n)$ is bounded from above by
some function from $K$. We have that $\phi\in K$ and $x\in\KRast$.


\noindent To show that $\KR\supseteq\KRast$  w.l.o.g we assume that $x\in [-1,1]\cap \KRast$ and
$\phi$  is given.
We are going to  construct simultaneously  $f\in K^{\{0,1,2\}}$ such that $\bar{f}=x$ and a supporting function $\psi\in K_1$ satisfying the equation $q_{\psi(n)}=\sum^{n}_{i=0}\frac{f(i)-1}{2^{i+1}}$.
 For that using bounded primitive  recursion scheme we construct a function $h\in K$  that satisfies $h(i)=c(f(i),\psi(i))$ and finally permits  us to define $f\in K^{\{0,1,2\}}$
such as $ f(i)=l(h(i)) $.
 Denote $J_n=[q_{\phi(n)}-\frac{1}{2^{n}},q_{\phi(n)}+\frac{1}{2^{n}}]$. In our construction  we want to meet
the following properties:


\begin{itemize}
\item $q_{\psi(n)}=\sum^{n}_{i=0}\frac{f(i)-1}{2^{i+1}}$,
\item $q_{\psi(n+1)}= q_{\psi(n)}+\frac{f(n+1)-1}{2^{n+2}}$ and
\item in the case study:
\begin{itemize}
\item if $q_{\psi(n)}> J_{n+3}$ then $f(n+1)=0$,
\item if $q_{\psi(n)}\in J_{n+3}$ then $f(n+1)=1$,
\item if $q_{\psi(n)}< J_{n+3}$ then $f(n+1)=2$.

\end{itemize}
\end{itemize}


 We define $f(0)$ and $\psi(0)$ as follows:

\begin{itemize}
\item if $0> J_{2}$ then $f(0)=0,\, q_{\psi(0)}=-\frac{1}{2}$,
\item if $0\in J_{2}$ then $f(0)=1,\, q_{\psi(0)}= 0$,
\item if $0< J_{2}$ then $f(0)=2,\, q_{\psi(0)}=\frac{1}{2}$.
\end{itemize}

Before formality let us note that the properties above guarantee  $\bar{f}=x$.
Indeed, by induction we show that   $(\forall n\in\omega) |x-q_{\psi(n)}|\leq\frac{1}{2^{n+1}}$.

\noindent For $n=0$ it follows from the definition of $f(0)$, $\psi(0)$ and the assumption that $x\in[0,1]$.
\noindent For the inductive transition $n\to n+1$ we consider three cases:
\begin{itemize}
\item If $q_{\psi(n)}> J_{n+3}$ then $q_{\psi(n+1)}= q_{\psi(n)}-\frac{1}{2^{n+2}}$. By induction assumption,
$|x-q_{\psi(n)}|\leq\frac{1}{2^{n+1}}$, therefore $|x-q_{\psi(n+1)}|\leq\frac{1}{2^{n+2}}$.

\item If $q_{\psi(n)}< J_{n+3}$ the $q_{\psi(n+1)}= q_{\psi(n)}+\frac{1}{2^{n+2}}$. By induction assumption,
$|x-q_{\psi(n)}|\leq\frac{1}{2^{n+1}}$, therefore $|x-q_{\psi(n+1)}|\leq\frac{1}{2^{n+2}}$.

\item If $q_{\psi(n)}\in J_{n+3}$ then $q_{\psi(n+1)}= q_{\psi(n)}$. In this case the length of $J_{n+3}$ is equal to $\frac{1}{2^{n+2}}$. We have $x\mbox{ and  } q_{\psi(n+1)}\in J_{n+3}$, so $|x-q_{\psi(n+1)}|\leq\frac{1}{2^{n+2}}$.
 \end{itemize}
 Therefore  $\bar{f}=x$.

We define $h$ as follows:
First $h(0)=c(f(0),\psi(0))$. Assume $h(n)$ is already constructed. First we find $e\in\{0,1,2\}$ by the following rules:

\begin{itemize}
\item if $q_{r(h(n))}> J_{n+3}$ then $e=0$,
\item if $q_{r(h(n))}\in J_{n+3}$ then $e=1$,
\item if $q_{r(h(n))}< J_{n+3}$ then $e=2$.
\end{itemize}
Then we find $d_0,\,d_1,\,d_2\in K$  according the following rules:
$\frac{e-1}{2^{n+1}}=q_{d_e(n)}$.
%, i.e., $-\frac{1}{2^{n+1}}=q_{d_0(n)}$, $0=q_{d_1(n)}$ and $\frac{1}{2^{n+1}}=q_{d_2(n)}$.
After that we have the scheme $l(h(n+1))=e$, $r(h(n+1))={\rm Add}(r(h(n)),d_e(n))$.
 Finally,
$h(n+1)=c(e,{\rm Add}(r(h(n)),d_e(n)))$ and $f(n)=l(h(n))$.
It is clear that the defined function $f$ meets the required  properties.
The same as in the proof of the inclusion $\KR\subseteq\KRast$ it is easy to see that $\psi$ is bounded from above
by a function from $K$. The function $f$ is  bounded from above by $\lambda x.2$. So  by Lemma~\ref{propK}  $h$ is  bounded from above by
a function from $K$. Finally, $f\in K$.
\end{proof}
 We propose to use the phrase '$x$ is a  $K$-number'
 when $\KR=\KRast$ and $x\in\KRast$ since in this case different intuitive approaches such as Cauchy approximations and sign-digit expansions give exactly the same set of computable reals.
In particular, below we mention $\mathcal{E}^n$-numbers in some results.
\subsection{When $\KRast$ is a real closed field}

\begin{remark}
If $K$ satisfies the requirements {\bf Req} then $\mathbb{Q}\subseteq \KRast$. As an example:
let $-1=q_\alpha$ for some $\alpha$ then the constant function $\lambda x.\alpha\in\K$ so $-1\in K^\ast$.
The same holds for any $q\in\Q$.
\end{remark}
Let $f:\omega\to\omega$ be a computable function. The sequence $ \{q_{f(n)}\}_{n\in\omega}$ is called fast Cauchy if $|q_{f(n+1)}-q_{f(n)}|\leq\frac{1}{2^n}$   for $n>0$.

\begin{lemma}\label{l_fast_cauchy}
If $\K$ satisfies the requirements {\bf Req} and $x\in \K^\ast$ then there is a  function $f\in \K_1$ such that $\{q_{f(n)}\}_{n\in\omega}$ is a fast Cauchy sequence converging to $x$ such that $|x-q_{f(n)}|<\frac{1}{2^{2n}}$ for all $n\in\omega$.
\end{lemma}
\begin{proof}
Indeed, since $x\in\KRast$ there exists $f^\ast\in\K_1$ such that $|x-q_{f^\ast(n)}|<\frac{1}{2^{n}}$. Then put $f(n)=f^\ast(2n)$.
%
The sequence $\{q_{f(n)}\}_{n\in\omega}$ is  fast  Cauchy one since

   \begin{align*}
   |q_{f(n+1)}-q_{f(n)}|<\frac{1}{2^{2n}}+\frac{1}{2^{2(n+1)}}< \frac{1}{2^{n}}
   \end{align*}

   for $n>0$.
  % \MK{pochemu ne $n\geq 0$}
\end{proof}
\begin{proposition}\label{field}
Let $K$ satisfy the requirements {\bf Req}. Then $(\KRast,+,\,\cdot,\leq)$ is a field.
\end{proposition}
\begin{proof}
Let $|x|<A$ and $|y|<A$ for $x,\, y\in \KRast$ and $|x-q_{f(n)}|<\frac{1}{2^{2n}}$,
$|y-q_{g(n)}|<\frac{1}{2^{2n}}$ for $f,\, g\in\K_1$ that exist by Lemma~\ref{l_fast_cauchy}.
 %
 We show that  $\KRast$ contains their product.
Indeed, $|x\cdot y-q_{f(n)}\cdot q_{g(n)}|<A\cdot\frac{1}{2^{2n}}+ (A+\frac{1}{2^{2n}})\cdot\frac{1}{2^{2n}}<\frac{1}{2^n}$ where $n>N$ for some large $N$.
By definition,  $q_{f(n)}\cdot q_{g(n)}=q_{{\rm Mult}(f(n),g(n))}$.
Since $x\cdot y$ is a real number there exists a sequence $\{q_{i_s}\}_{s\leq N}$ such that $|x\cdot y-q_{i_s}|<\frac{1}{2^s}$ for $s\leq N$.
Then we define a new function as follows:

   \begin{eqnarray*}
\chi(n)=\left \{
\begin{array}{lll}
{\rm Mult}(f(n),g(n))&\mbox{ if }& n>N\\
i_s &\mbox{ if }& n\leq N.
\end{array}
\right.
\end{eqnarray*}

By definition for all $n\in\omega$ we have $|x\cdot y-q_{\chi(n)}|<\frac{1}{2^n}$ and
$\chi=^\ast {\rm Mult}(f,g)$. So $\chi\in \K_1$  and defines $x\cdot y$.

For addition it is even easier:
 since $|x+ y-(q_{f(n)}+ q_{g(n)})|<\frac{1}{2^{2n}}+ \frac{1}{2^{2n}} \leq\frac{1}{2^n}$
for $n>0$ the function $\eta={\rm Add}(f,g)$ defines $x+ y$ and belongs to $\K_1$.
For inverses elements:
$-x=-1\cdot x$.
Then let $x\neq 0$, $x\in \KRast$ and  $|x-q_{f(n)}|<\frac{1}{2^{2n}}$  for $f\in\K_1$ that exists by Lemma~\ref{l_fast_cauchy}.
Since there is  $B\in\mathbb{Q}^+$ such that $|x|>B>0$ without loss of generality we can assume that $q_{f(n)}\neq 0$ for all $n\in\omega$ or use the construction as for product.
We have
\begin{align*}
|x^{-1}-(q_{f(n)})^{-1}|
=\frac{|x-q_{f(n)}|}{|x|\cdot|q_{f(n)}|}
<\frac{1}{2^{2n}}\cdot B^{-1}\cdot(B+\frac{1}{2^{2n}})^{-1}<\frac{1}{2^n}
\end{align*}
 for $n>M$ for some large $M$.
 And now we use a  construction as for product.

\end{proof}
\begin{proposition}\label{rcfield}
Let $K$ satisfy the requirements \Reqast and contains $\lambda x.2^x$. Then $(\KRast,+,\,\cdot,\leq)$ is a real closed field.
\end{proposition}
\begin{proof}
The claim that $\KRast$ is a field follows from Proposition~\ref{field}.
To complete the proof, we  show that the  real roots of unitary polynomials
with coefficients in $\KRast$ are also in  $\KRast$.
Assume contrary that there exists a unitary polynomial  $p(x)= \sum^n_{i=0}a_i x^i\in\KRast[x]$ of a minimal degree which has a root $x_0$ in $\R$ but not in $\KRast$. The polynomial $p$ does not have multiple roots since in opposite case it is possible to compute $g={\rm G.C.D.}(p(x),p^\prime(x))$ and $h=\frac{p}{q}$ which are in $\KRast[x]$.
The polynomial  $h$ has exactly the same roots as $p$ and ${\rm deg}(h)\leq {\rm deg}(p)$
 however $h$ does not have multiple roots.
 %
Therefore since $a_n=1$ the coefficients $\bar{a}=(a_0,\dots,a_{n-1})$ of $p$ satisfy the following formula:
\[
\Psi(\bar{a})=\Psi_1(\bar{a})\vee \Psi_2(\bar{a}),
\]
where
\small{
\[
\Psi_1(\bar{a})\leftrightharpoons
\exists A\,\exists B\,\exists c>0\exists\epsilon>0
\Big(
A<B\wedge p(A)<-\epsilon\wedge\, p(B)>\epsilon\wedge \forall x\in [A,B]\, c>p^\prime(x)>\epsilon
\Big)
\]
}
and
{\small
\[
\Psi_2(\bar{a})\leftrightharpoons
\exists A\,\exists B\,\exists c<0\exists\epsilon<0
\Big(
A<B\wedge p(A)>-\epsilon\wedge\, p(B)<\epsilon\wedge \forall x\in [A,B]\, c<p^\prime(x)<\epsilon
\Big).
\]
}
It is clear that the sets defined by  $\Psi_1(\bar{a})$ and $\Psi_2(\bar{a})$ are not overlapping.
 W.l.o.g. we assume $\R\models\Psi_1(\bar{a})$.
 By continuity arguments, we can chose some $A,\,B,\,\epsilon>0$, $c>0$ and balls $B(a_i,r_i)$, $i=1,\dots,n-1$, such that
$|B-A|< 1$ and  for all $\bar{b}\in \prod_{i=0}^{n-1}B(a_i,r_i)$, where $\bar{b}=(b_0,\dots,b_{n-1})$ and $b_n=1$, we have
 \begin{align*}
 \sum_{i=0}^n b_iA^i<-\epsilon\wedge
  \sum_{i=0}^n  b_iB^i>\epsilon \wedge
 (\forall x\in [A,B] )\, c>\sum_{i=1}^n i\cdot b_i\cdot x^{i-1}>\epsilon.
  \end{align*}
Now we are going to show that $x_0$ being a unique root in $[A,B]$ belongs to $\KRast$.
For that we fix $m$ and the precision $\frac{1}{2^m}$  assuming that $m$ is quite large. Our goal is  to construct
 a function $\psi\in K_1$ such that $y_m=q_{\psi(m)}$ and $|x_0-y_m|<\frac{1}{2^m}$ for $m\gg 1$.
 Since $a_i\in\KRast$ there exists $\phi_i\in \K_1 $ such that for all $s\in\omega$, $|a_i-q_{\phi_i(s)}|<\frac{1}{2^s}$.
 Put $s=3m$ and $b_i=q_{\phi_i(3m)}$. Then $b_i\in B(a_i,r_i)\cap \mathbb{Q}$, $i\leq n-1$, for $m\gg 1$ and for all $m\in\omega$, $|b_i-a_i|\leq \frac{1}{2^{3m}}$.
 %
% \MK{nush no li  $|x_0-y_m|<\frac{1}{2^m}$????}
Let $\widetilde{p}(x)=\sum_{i=0}^n b_ix^i$.
Since $\bar{b}$ satisfies the formula $\Psi_1$, the polynomial  $\widetilde{p}(x)$ has   a unique root $z$ in $[A,B]$. We show that $z\in \KRast$, i.e., we construct  a function $\phi\in K$ such that
for all $k\in\omega $, $|z-q_{\phi(m,k)}|<\frac{1}{2^k}$.
%
We describe the standard bisection method for finding  the root $z$ of $\widetilde{p}$ on $[A,B]$.
Let
\[
q_{\phi(m,0)}=\frac{A+B}{2}.
\]
%
Assume $\phi(m,k)$ is already constructed. Then we define $\phi(m,k+1)$ by the following rules:

\begin{itemize}
\item if $\widetilde{p}(q_{\phi(m,k)})=0$ then $\phi(m,k+1)=\phi(m,k)$,
\item if $\widetilde{p}(q_{\phi(m,k)})>0$ then $\phi(m,k+1)=\phi(m,k)-\frac{B-A}{2^{k+2}}$,
\item if $\widetilde{p}(q_{\phi(m,k)})<0$ then $\phi(m,k+1)=\phi(m,k)+\frac{B-A}{2^{k+2}}$.
\end{itemize}
By induction it is straightforward that for all $k\in\omega$, $|z-q_{\phi(m,k)}|<\frac{|B-A|}{2^{k+1}}$.
The function $\phi(m,k)$ is constructed by   the recursive scheme. Let us show that $\phi(m,k)$ is bounded.
It is clear that the endpoints of the interval with the center $q_{\phi(m,k)}$ and the radius $\frac{B-A}{2^{k+1}}$,
where $A=\frac{d_1}{l}$ and  $B=\frac{d_2}{l}$, have a form
\[
\frac{2^k d_1+ (d_2-d_1)\cdot i\cdot l}{2^k\cdot l}
\]
for appropriate $i\leq 2^k$.
Therefore $q_{\phi(m,k)}$ has a form
\[
\frac{2^{k+1} d_1+ (d_2-d_1)\cdot (2i+1)\cdot l}{2^{k+1}\cdot l}
\]
 and it is clear that
 $
 \phi(m,k)
$ is bounded by some function from $\K$ and
 therefore $\phi\in K$.
Let us define $\psi(m)=\phi(m,4m)$.
Since for all $x\in [A,B]$ we have $|\widetilde{p}^\prime(x)|>\epsilon>0$, by
the mean value  theorem $\widetilde{p}(q)-\widetilde{p}(z)=\widetilde{p}^\prime(\theta)(q-z)$
for some $\theta\in[A,B]$. Put $y_m=q_{\psi(m)}$. Then
\[
\mid \widetilde{p}(y_m)\mid=\mid \widetilde{p}(q_{\psi(m)})\mid\leq \frac{c}{2^{4m}}<\frac{1}{2^{3m}}
\]
for $m\gg 1$. We show that $y_m=q_{\psi(m)}$ is  required.
%
Let $M\in\Q^+$ be a bound on $a_i$,  $A$, $B$ and $\epsilon$, i.e., $|a_i|<M$ for $0\leq i\leq n$, $|A|< M$,\,$|B|<M$
and $\frac{1}{\epsilon}<M$.
%
One can assume that $m$ is sufficiently big , i.e.,
$2^m> M^n+\dots+1=\sum_{i=0}^{n}M^i$. It is worth noting that
%
$2^m\cdot\epsilon>1$ and
we already establish above $\mid b_i-a_i \mid<\frac{1}{2^{3m}}$. So for all $x,\, y\in [A,B]$
we have $\mid p(y)- \widetilde{p}(y) \mid<(1+\dots + M_n)\cdot\frac{1}{2^{3m}}$.
As a corollary for $y=y_m$ taking into account $\widetilde{p}(y_m)<\frac{1}{2^{3m}}$ we get
%
\[\mid p(y_m)\mid\leq \frac{1}{2^{3m}}\cdot(1+\dots|y|^n)\leq \frac{1}{2^{3m}}\cdot 2^m=\frac{1}{2^{2m}}.\]
By the mean value  theorem,  for all $x,\, y\in [A,B]$ there exists $\theta\in [A,B]$
such that $p(x)-p(y)=(x-y)\cdot p^\prime(\theta)$.
If $x_0$ is the root of $p$ in the interval $[A,B]$ and $y_m=q_{\psi(m)}$ then
\[
|x_0-y_m|\leq \frac{|p(y)|}{\epsilon}<\frac{1}{2^{2m}}\cdot2^m\leq\frac{1}{2^m} \mbox{ for $m\gg 1$}.
\]

 \noindent So $y_m\in \mathbb{Q}$ is an approximation of  the root $x_0$ with the precision $\frac{1}{2^m}$ for $m\gg 1$.
%
By Lemma~\ref{propKRast}, $x_0\in\KRast$, a contradiction.
\end{proof}

\begin{corollary}\label{K-numb_rcfield}
Let $K$ satisfy the requirements \Reqast and contain $\lambda x.2^x$. Then the set of $\K$-numbers forms a real closed field.
\end{corollary}
\begin{corollary}\label{E-numb_rcfield}
 For $n\geq 3$ the set of $\mathcal{E}^n$--numbers forms a real closed field.
\end{corollary}
\begin{remark}
 It is worth noting that Proposition~\ref{rcfield} is closely related to well-known K.~ Ko's  Theorem on real closedness of the polynomial time computable real numbers however this result is not particular case of  our proposition. At the same time the particular case when $K$ is the set of all primitive recursive functions has been considered by P. Hertling (handwritten notes) and it has been proven by him that the primitive recursive real numbers
 is a real closed field.
\end{remark}
\subsection{Criterion of Computable Presentability of Archimedean Ordered Fields}\label{criterion_aof}


Let $L=(L,\leq)$ be linearly ordered and $\mathbb{Q}\subseteq L$.  Assume $\mu:\omega\to L$ is a numbering.
 %such that $\mu\geq q$, i.e., $q_n=\mu(h(n))$
%for a computable function $h:\omega\to\omega$.
%
With $L$ we associate 2 families of non-strict Dedekind cuts:
\begin{align*}
&A_k=\{ n\mid q_n\leq \mu(k)\}\\
&B_k=\{ n\mid q_n\geq \mu(k)\}
\end{align*}
and naturally define $S_k=A_k\oplus B_k=\{2n\mid n\in A_k\}\cup \{2n+1\mid n\in B_k\}$ and $S_L=\{S_k\mid k\in\omega\}$.
The family $S_L$ is endowed with the standard numbering $\beta(k)=S_k$.
%
The following proposition provides  a criterion of computable presentability of  an archimedean ordered field.

\begin{proposition}\label{criterion_comp_copy}
Let $F=(F,+,\cdot,\leq)$ be an archimedean ordered field, $\mu:\omega\to F$ be its numbering such that
$(F,\mu)$ is an effective  algebra.
Then $(F,\mu)$ is a computable copy  if and only if  the family $(S_F,\beta)$ is computable.
\end{proposition}
\begin{proof}

\noindent The claim  $\rightarrow$ follows from the observation that  if the numbering $\mu$ is

 \noindent a computable presentation of an ordered field
 $F$  then $\mu\geq q$, i.e., $q_n=\mu(h(n))$
for a computable function $h:\omega\to\omega$ and  the family $(S_F,\beta)$ is computable.


\noindent  For the claim  $\leftarrow$ we assume that $(S_F,\beta)$ is computable.
Let $0=q_i$ and $-1=\mu(a)$ for some $a\in\omega$.  So the substraction is defined as  $\mu(n)-\mu(m)=\mu(n)+\mu(a)\cdot\mu(m)$. It is clear that $\mu(n)=\mu(m)$ iff $\mu(n)-\mu(m)=\mu(k)\wedge 2i\in S_k\,\wedge\, 2i+1\in S_k $ and
$x\neq 0$ iff $(\exists y)\, y\cdot x=1$.
%
Therefore equality is computable.
%
 It is easy to see that  order is also computable. Indeed,
 \begin{align*}
 &\mu(n)<\mu(m)\mbox{ iff }
(\exists k)(\exists l)\, \mu(n)\leq q_k<q_l\leq\mu(m),\\
&\mu(n)\leq \mu(m)\mbox{ iff } \mu(n)<\mu(m)\vee \mu(n)=\mu(m),\\
&\mu(n)\not\leq \mu(m)\mbox{ iff }\mu(m)<\mu(n).
 \end{align*}
\end{proof}
\begin{corollary}
Let $K$ satisfy the requirements \Req and $\mu:\omega\to \KRast$ be its numbering such that
$(\KRast,\mu)$ is an effective  algebra.
Then $(\KRast,\mu)$ is a computable copy  if and only if  the family $(S_{\KRast},\beta)$ is computable.
\end{corollary}

\section{  Index sets vs. Computable Presentability}\label{index_sets_constructivisiruemih_kr}
In this section we assume
  $\AC$  denotes the almost  constant  functions, i.e.,
%
  $\AC=\{f:\omega\to\omega\mid (\exists c\in \omega)(\exists x\in \omega)(\forall y>x) f(y)= c\,\} $
  and $\AC\subseteq K$.
%

\begin{definition}\label{str}
Suppose $\K$ is a class of total computable numerical functions, $\KR$ is the set of reals generated by $K$.
Then we associate with $\K$  a structure  $(\KR,\sigma_\str)=(\KR,0,Q^3_{+},Q^3_{-},\leq)$, where
\begin{align*}
&\KR\models Q^3_{+}(x,y,z)\leftrightarrow x+y\leq z\\
&\KR\models Q^3_{-}(x,y,z)\leftrightarrow x+y\geq z.
\end{align*}
\end{definition}
It is easy to see that, since the graph of addition is computable, if  a structure $\KR$ has a computable copy $(\KR,\mu)$ then the set $\mu^{-1}(\Dyad)$  is computably enumerable:
\begin{align*}
% \mu(n)\in \mathbb{Q} \leftrightarrow (\exists k\in\omega)(\exists l\in\mathbb{Z})\, k\cdot \mu(n)+l=0,\\
  \mu(n)\in \Dyad \leftrightarrow (\exists k\in\omega)(\exists l\in\mathbb{Z})\, 2^k\cdot \mu(n)+l=0.
\end{align*}
To proceed    further we define index sets:
\begin{align*}
&A_0=\{n\mid \pi_n\subseteq \{0,1,2\}\wedge n\not\in \Tot\},\\
&A_1=\{n\mid \pi_n\subseteq \{0,1,2\}\wedge ( n\not\in \Tot\vee \varphi_n\in\AC)\},\\
&A_2=\{n\mid  \pi_n\subseteq \{0,1,2\}\wedge (n\not\in \Tot\vee\varphi_n\in\K^\prime)\}=\\
&\{n\mid  \pi_n\subseteq \{0,1,2\}\wedge (n\not\in \Tot\vee\overline{\varphi_n}\in\KR)\}
\end{align*}
where  $\K^\prime=\{\varphi_n\mid \overline{\varphi_n}\in \KR\cap [-1,1] \}$.
\begin{theorem}\label{sigma02construct}
Suppose $\K$ is a class of total computable numerical functions. If  the structure $(\KR,\sigma_\str)$ generated by $K$ has a computable presentation then
$A_0\cup (A_2\setminus A_1)\in \Sigma^0_2$.
\end{theorem}
\begin{proof}

Let $\mu:\omega\to\KR$ be a computable presentation.
%
 Since the set $E=\{n\mid -1\leq\mu(n)\leq 1\}$ is computable, there exists a computable function $h$  such that
 ${\rm im}(h)=E$ and $\tilde{\mu}=\mu\circ h$ is  a computable numbering of $\KR\cap [-1,1]$.
Assume $x=\tilde{\mu}(n)$. Now we construct a map $\nu:\omega\to \mathbb{T}$ by induction:
\begin{align*}
& \nu(n)(0)=1\\
& \nu(n)(s+1)=\left \{
\begin{array}{lll}
0 & \mbox{ if }&  x<x_s\\
1 &\mbox{ if }&  x=x_s\\
2 &\mbox{ if }&  x>x_s,
\end{array}
\right.
\end{align*}
 where $x_s=\sum_{i\leq s}\frac{\nu(n)(i)-1}{2^i}$.
 Since $|x_s-x|\leq \frac{1}{2^s}$, $|x_{s+1}-x|\leq \frac{1}{2^{s+1}}$. From $\AC\subseteq K$ it follows that
 $x_s\in\KR$.
%
 We have the following properties:
 %
 $\nu(n)$ is total,  $\nu(n)\in \mathbb{T}$ and $\nu(n)$ provides  a sign-digit representation of $x$.
%
%From properties of $\mu$ it follows that $\nu(n)\in\AC$
%  is a $\Sigma^0_1$--condition since $\nu(n)\in\AC\leftrightarrow \mu(n)\in\Dyad$ and
%$\mu(n)\in \Dyad\leftrightarrow (\exists k\in\omega)(\exists l \in\mathbb{Z})\, 2^k\cdot\mu(n)+l=0$.
%
It is worth noting that $\Dyad$ is $\Sigma^0_1$--relation on $\KR$ and for any $f:\omega\to\{0,1,2\}$
it holds that $f\in \AC \leftrightarrow \bar{f}\in\Dyad$ (see c.f. \cite{Ko}).
As  a corollary,  $Y=\{n\mid\nu(n)\in AC\}$ is computably enumerable.
Now we show that $A_0\cup A_2\setminus A_1\in \Sigma^0_2$. Let us note that
%
\begin{align*}
& n \in A_0\cup (A_2\setminus A_1)\leftrightarrow\\
&
n\in A_0\vee
\Big(n\in A_2\wedge \Big( (\exists m\in \omega\setminus Y)\, \overline{\nu(m)}=\overline{\varphi_n}
\vee n\not\in\Tot\Big)\Big).
\end{align*}

We have the following:
\begin{itemize}
\item The relation $n\not\in Y$ is $\Pi^0_1$.

\item The relation $\overline{\nu(m)}=\overline{\varphi_n}$ is $\Pi^0_1$.
It follows from the following observations.
Let

\begin{align*}
\Phi(f,g) \leftrightharpoons
(\exists s>0)\,
%
  \Big|\sum^{s}_{k=0}\frac{f(k)-1}{2^{k+1}}- \sum^{s}_{k=0}\frac{g(k)-1}{2^{k+1}}\big|>\frac{1}{2^{s-1}}
.
\end{align*}
Then for $f,\, g\in \mathbb{T}^{\{0,1,2\}}$, $\overline{f}\neq \overline{g}\leftrightarrow \Phi(f,g)$. So, $\overline{\nu(m)}=\overline{\varphi_n}\leftrightarrow \neg\Phi(\nu(m),\varphi_n)$.

 \item The relation $n\in A_2$ is $\Sigma^0_2$ since
\begin{align*}
n\in A_2\leftrightarrow n\not\in\Tot\vee (\exists m\in\omega)\neg \Phi(\nu(m),\varphi_n)
.
\end{align*}
\item The relation $n\not\in Tot$ is $\Sigma^0_2$.
\end{itemize}

Therefore $A_0\cup (A_2\setminus A_1)\in \Sigma^0_2$.
\end{proof}
\noindent It is worth noting that the same proof is valid when one consider just a computable presentation $\mu$ of  a linear ordered $(\KR,\leq)$ with the requirement that $\mu\geq q$.


\subsection{Criterion of $m$-completeness for  tuples of $\Sigma^0_1$ and $\Sigma^0_2$ sets }\label{m-universality}
In this section for $s\geq 1$ we consider  $s$-tuples    $(A_0,\dots,A_{s-1})$, where either all $A_i$ are  $\Sigma^0_1$-sets or
all $A_i$ are $\Sigma^0_2$--sets.

For uniformity of  a presentation we introduce a symbol $l$ where   $l\in\{1,2\}$, a  relation $\sim_l$ on sets and an oracle $z_l$ that have the following interpretation.
If $l=1$ then $ A\sim_l B$ means that  $A$ and $B$ are equal and the oracle $z_l=\emptyset$. If $l=2$ then $ A\sim_l B$ means that $(A\setminus B)\cup (B\setminus A)$ is finite, i.e.,  $A$ and $B$ are almost equal, denoted $A=^* B$. The oracle $z_l=Kw$,
where $Kw=\{n\mid \varphi_n(n)\downarrow\}$ or could be any creative set.
We generalise ideas of the criterion of $m$-completeness of $\Sigma^0_1$-sets and $\Sigma^0_2$-sets in
\cite{Arslanov_0} to fit  $m$-completeness of  $s$-tuples of $\Sigma^0_1$-sets and $\Sigma^0_2$-sets that requires modifications of  concepts and definitions.

\begin{definition}

 Let $(A_0,\dots,A_{s-1})$  and $(B_0,\dots,B_{s-1})$ be  $s$-tuples of subsets of $\omega$.
We say that $(A_0,\dots,A_{s-1})$ is $m$-reducible to $(B_0,\dots,B_{s-1})$
($(A_0,\dots,A_{s-1})\leq_m (B_0,\dots,B_{s-1})$) if there exists a computable function $f$ such that
$f^{-1}(B_i)=A_i$ for all $0\leq i< s$.

\end{definition}
\begin{definition}
 Let $A$    belong to a class $L$, where
 $L\subseteq (\Sigma_n^0[\omega])^s$.
We say that $A$ is $m$-complete in the class $L$ if  any element from this class
is $m$-reducible to it.
\end{definition}
\begin{remark}\label{rmalmosteq}
It is well known (see c.f. \cite{Arslanov})  that  given any (partial) $\Sigma^0_2$-function $f$
one can effectively construct  a total computable function $F$ such that
$(\forall x\in \dom(f))\, W_{f(x)}=^\ast W_{F(x)}$, moreover $\varphi_{f(x)}=^\ast \varphi_{F(x)}$.
\end{remark}


\begin{definition}
Let  $(F_0,\dots,F_{s-1})$ be an $s$-tuple of  functions, where $F_i:\omega^s\to\omega$, $0\leq i\leq s-1$
and $(A_0,\dots,A_{s-1})$ be an $s$-tuple of $\Sigma^0_l$-sets.
We say that $(F_0,\dots,F_{s-1})$ is $m$-reducible to $(A_0,\dots,A_{s-1})$, denoted as  $(F_0,\dots,F_{s-1})\leq_m (A_0,\dots,A_{s-1})$,
if there exist computable functions $h:\omega^s\to\omega$, $a_i:\omega^s\to\omega$, $b_i:\omega^s\to\omega$,  $0\leq i\leq s-1$,   such that

 \begin{eqnarray*}
F_i(\bar{x})=\left \{
\begin{array}{lll}
a_i(\bar{x}) & \mbox{ if }&  h(\bar{x})\in A_i\\
b_i(\bar{x}) &\mbox{ if }&  h(\bar{x})\not\in A_i.
\end{array}
\right.
\end{eqnarray*}

\end{definition}

 \noindent It is easy to see that this definition is a  generalisation of the corresponding definition from \cite{Arslanov}.
\begin{lemma}\label{lem_m_reduc}
 For  s-tuples $X$ and $A$ of $\Sigma^0_l$-sets if $(F_0,\dots,F_{s-1})\leq_m (X_0,\dots,X_{s-1})$ and $(X_0,\dots,X_{s-1})\leq_m (A_0,\dots,A_{s-1})$ then
$(F_0,\dots,F_{s-1})\leq_m (A_0,\dots,A_{s-1})$.
\end{lemma}

\begin{proposition}(Smullyan's Fixed Point Theorem)\cite{Smullyan}\label{Smullyan}
Let $\lambda_0,\dots,\lambda_{s-1}$ be partial computable functions of  arity $n+s$. Then there exist
computable functions
\[h_0,\dots,h_{s-1}\]
 of  arity $n$ such that the following equality simultaneously holds
\[\varphi_{\lambda_i(\bar{z},\bar{h}(\bar{z}))}=\varphi_{h_i(\bar{z})}\]
for all $0\leq i\leq s-1$ and for all $\bar{z}$ under the standard agreement:
if the index in the left part of the equality is undefined then the function on the right is undefined anywere.
\end{proposition}
\begin{proposition}\label{criteria_m_compl}
Let  $(A_0,\dots,A_{s-1})$ be a $s$-tuple of $\Sigma^0_l$-sets.
The following claims are equivalent.
\begin{enumerate}
\item $(A_0,\dots,A_{s-1})$ is $m$-complete in the class of  $s$-tuples of $\Sigma^0_l$-set.
\item  There exists  a computable function (its productive function) $H:\omega^s\to\omega$ such that for all $x_0,\dots\,x_{s-1}\in\omega$
\[
H(x_0,\dots\,x_{s-1})\in \bigcap_{i=0}^{s-1}
\Big( (A_i\cap W^{z_l}_{x_i})\cup (\overline{A_i}\cap \overline{W}^{z_l}_{x_i})
\Big).
\]
\item There exists a $s$-tuple of  functions $(F_0,\dots,F_{s-1})$, where $F_i:\omega^s\to\omega$, $0\leq i<s$, such that
   \begin{enumerate}
   \item $(F_0,\dots,F_{s-1})\leq_m (A_0,\dots,A_{s-1})$,
   \item $W_{F_i(\bar{x})}\not\sim_l W_{x_i}$ for all $0\leq i<s$ and for all $\bar{x}$.
   \end{enumerate}
   \item There exists a $s$-tuple of  functions $(F_0,\dots,F_{s-1})$, where $F_i:\omega^s\to\omega$, $0\leq i<s$, such that
   \begin{enumerate}
   \item $(F_0,\dots,F_{s-1})\leq_m (A_0,\dots,A_{s-1})$,
   \item $\varphi_{F_i(\bar{x})}\not\sim_l \varphi_{x_i}$ for all $0\leq i<s$ and for all $\bar{x}$.
   \end{enumerate}
\end{enumerate}
\end{proposition}
\begin{proof}
\noindent $1)\leftrightarrow 2)$. For $l=1$ the equivalents of  the statements can be found in \cite{Ersh_TH}.
The existence  of $m$-complete $s$-tuple of computably enumerable  sets has been also established there.
For $l=2$ we only need  a relativisation to the oracle $z_2$ which also could be found in \cite{Ersh_TH}.

\noindent $1)\to3)$.
Without loss of generality we assume $s=3$.

\noindent \textbf{Case 1:  l=1.}
First we
take the following $m$-complete 3-tuple:
 \begin{align*}
& X_0=\{n\mid \varphi_n(0)\downarrow\},\\
 &X_1=\{n\mid \varphi_n(1)\downarrow\},\\
 &X_2=\{n\mid \varphi_n(2)\downarrow\}.\\
  \end{align*}
Further on by By Lemma~\ref{lem_m_reduc}  the considerations below will hold for any $m$-complete 3-tuple.
  By Graph theorem \cite{Rogers} we construct a computable sequence
   \[B=\{B_{x_0x_1x_2}\}_{x_0x_1x_2\in\omega}\]
    of partial  computable functions such that
   \begin{align*}
  & B_{x_0x_1x_2}(i)=\varphi_{x_i}(i) \mbox{ if } i=0,1,2\\
  & B_{x_0x_1x_2}(k)\uparrow \mbox{ if } k>2.
     \end{align*}
 Then there exists  a computable function $h:\omega^3\to\omega$ such that
   \[B_{x_0x_1x_2}=\varphi_{h(x_0,x_1,x_2)}.\]
 By definition of $B$ we have    $h(x_0,x_1,x_2)\in X_i\leftrightarrow x_i\in X_i$ for $i\leq 2$.
  To finish  the construction of $F_i$ we take $a_i$ and $b_i $   for $i\leq 2$ as follows.


 \begin{align*}
& a_0=a_1=a_2 \mbox{ is an index of } \bot, \\
& b_0 \mbox{ is an index of  the function } \{<0,0>\}, \\
%& a_1 \mbox{ is an index of } \bot, \\
& b_1 \mbox{ is an index of the function}  \{<1,0>\}, \\
%& a_2 \mbox{ is an index of } \bot, \\
&  b_2 \mbox{ is an index of the function}  \{<2,0>\},
 \end{align*}

 We define  for $i\leq 2$
  \begin{eqnarray*}
F_i(\bar{x})=\left \{
\begin{array}{lll}
a_i & \mbox{ if }&  h(\bar{x})\in X_i\\
b_i &\mbox{ if }&  h(\bar{x})\not\in X_i.
\end{array}
\right.
\end{eqnarray*}
 By construction $(F_0,F_1,F_2)$ is $m$-reducible to $(X_0,X_1,X_{2})$. Let us show that
  \[W_{F_i(\bar{x})}\neq W_{x_i}.\]    Fix $i$ and consider two cases:
   \begin{itemize}
\item   Assume $h(\bar{x})\in X_i$. Since $F_i(\bar{x})=a_i$, $W_{F_i(\bar{x})}=\emptyset$.
  At the same time $W_{x_i}\neq \emptyset$ since $x_i\in X_i$ and $\varphi_{x_i}(i)\downarrow$.
\item  Assume $h(\bar{x})\not\in X_i$. Since $F_i(\bar{x})=b_i$, $\varphi_{b_i}(i)\downarrow$  and $i\in W_{F_i(\bar{x})}\neq\emptyset$.
  At the same time $\varphi_{x_i}(i)\uparrow$, i.e., $i\not\in W_{x_i}$.
\end{itemize}
  Therefore $(F_0,F_1,F_2)$ is a required $3$-tuple.

\noindent \textbf{Case 2: l=2.}
First we
take the following  3-tuple:
 \begin{align*}
& Z_0=\{n\mid W_n\cap 3\omega \mbox{ is finite}\},\\
 &Z_1=\{n\mid W_n\cap (3\omega+1) \mbox{ is finite}\},\\
 &Z_2=\{n\mid W_n\cap (3\omega+2) \mbox{ is finite}\}.\\
  \end{align*}
By analogy to the case 1 we chose $h:\omega^3\to\omega$ such that for all $\bar{x}=(x_0,x_1,x_2)$ and every $k\in\omega$
 we have $\varphi_{h(\bar{x})}(3k+i)=\varphi_{x_i}(3k+i)$ for $i\leq 2$.
  To finish  the construction of $F_i$ we take $a_i$ and $b_i $   for $i\leq 2$ as follows.

 \begin{align*}
& a_0=a_1=a_2 \mbox{ is an index of constant zero function}, \\
& b_0=b_1=b_2 \mbox{ is an index of } \bot. \\
\end{align*}

 We define  for $i\leq 2$
  \begin{eqnarray*}
F_i(\bar{x})=\left \{
\begin{array}{lll}
a_i & \mbox{ if }&  h(\bar{x})\in Z_i\\
b_i &\mbox{ if }&  h(\bar{x})\not\in Z_i.
\end{array}
\right.
\end{eqnarray*}
 By construction $(F_0,F_1,F_2)$ is $m$-reducible to $(Z_0,Z_1,Z_{2})$.

 Let us show that
  $W_{F_i(\bar{x})}\neq^\ast W_{x_i}$.    Fix $i$.
Assume contrary $W_{F_i(\bar{x})}=^\ast W_{x_i}$ and consider two cases:
  \begin{itemize}
  \item Let $h(\bar{x})\in Z_i$. Since $F_i(\bar{x})=a_i$, $W_{F_i(\bar{x})}=\omega$.
  At the same time $W_{x_i}\cap (3\omega+i)$ is finite from the choice of $h$  and finiteness of $W_{h(\bar{x})}\cap (3\omega+i)$, a contradiction.

 \item  Let $h(\bar{x})\not\in Z_i$. Since $F_i(\bar{x})=b_i$, $W_{F_i(\bar{x})}=\emptyset$. By assumption, $W_{x_i}$ is finite.
  %
  At the same time $W_{x_i}\cap (3\omega+i)$ is infinite from the choice of $h$  and infiniteness of $W_{\bar{x}}\cap (3\omega+i)$,
   a contradiction.
 %By analogy to the case~1 we have
 % $W_{F_i(\bar{x})}\neq^\ast W_{x_i}$.
 \end{itemize}

  Therefore $(F_0,F_1,F_2)$ is a required $3$-tuple.

\noindent $3)\to 4)$.  The implication is straightforward since $\varphi_{F_i(\bar{x})}\not\sim_l \varphi_{x_i}$
follows from $W_{F_i(\bar{x})}\not\sim_l W_{x_i}$.

  \noindent $4)\to 2)$.   Without loss of generality we assume $s=3$. The following construction is uniform for both $l$.
  First for $i\leq 2$ we define  functions  $G_i$ and $T_i$ which are computable with the oracle $z_l$:

    \begin{eqnarray*}
&G_i(\bar{x},\bar{y})=\left \{
\begin{array}{lll}
b_i(\bar{y}) & \mbox{ if }&  h(\bar{y})\in W^{z_l}_{x_i}\\
\uparrow &\mbox{ if }&  h(\bar{y})\not\in W^{z_l}_{x_i},
\end{array}
\right.\\
&T_i(\bar{x},\bar{y})=\left \{
\begin{array}{lll}
a_i(\bar{y}) & \mbox{ if }&  h(\bar{y})\in A_i\\
\uparrow &\mbox{ if }&  h(\bar{y})\not\in A_i.
\end{array}
\right.
\end{eqnarray*}


  By Reduction principle for function graphs \cite{Rogers} we find a    function
  $E_i(\bar{x},\bar{y})$ with the following properties:
  \begin{itemize}
  \item  $E_i(\bar{x},\bar{y})$ is computable with the oracle $z_l$, therefore for  some computable    function      $g_i:\omega^3\to \omega$,     $E_i(\bar{x},\bar{y})=K^{4,z_l}(g_i(\bar{x}),\bar{y})$,
      where $K^{4,z_l}$ is Kleene universal function for 3-arity functions computable with the oracle $z_l$.
  \item If $h(\bar{y})\in W^{z_l}_{x_i}\setminus A_i$ then $E_i(\bar{x},\bar{y})=b_i(\bar{y})$.
  If $h(\bar{y})\in A_i\setminus W^{z_l}_{x_i}$ then $E_i(\bar{x},\bar{y})=a_i(\bar{y})$.
  \end{itemize}
If $l=1$ by  Proposition~\ref{Smullyan} for $i<3$ there exist three computable functions
$n_0,\,n_1,\,n_2:\omega^3\to\omega$ such that
  \begin{align*}
  \varphi_{K^{4}(g_i(\bar{x}),n_0(\bar{g}(\bar{x})),n_1(\bar{g}(\bar{x})),n_2(\bar{g}(\bar{x})))}= \varphi_{n_i(\bar{g}(\bar{x}))}.
   \end{align*}

 % \MK{ vinesti v nachalo $\bar{g}(\bar{x})=(g_0(\bar{x}),g_1(\bar{x}),g_2(\bar{x}))$}

 \noindent  If $l=2$ there exist three computable functions
$n_0,\,n_1,\,n_2:\omega^3\to\omega$ such that
  \begin{align*}
  \varphi_{K^{4,z_2}(g_i(\bar{x}),n_0(\bar{g}(\bar{x})),n_1(\bar{g}(\bar{x})),n_2(\bar{g}(\bar{x})))}=^\ast \varphi_{n_i(\bar{g}(\bar{x}))}
   \end{align*}
   under  the condition that $K^{4,z_2}(g_i(\bar{x}),\bar{n}(\bar{g}(\bar{x})))\downarrow$.
 The last statement requires more details which we show below.
 It is easy to see that, for $i\leq 2 $,  $f_i(\bar{z},\bar{y})\leftrightharpoons K^{4,z_2}(z_i,\bar{y})$ is $\Sigma^o_2$-function. Therefore by Remark~\ref{rmalmosteq} there exist computable functions $\lambda_i$ such that
 for $(\bar{z},\bar{y})\in\dom(f_i)$
  \begin{align*}
  \varphi_{f_i(\bar{z},\bar{y})}=^\ast \varphi_{\lambda_i(\bar{z},\bar{y})}.
  \end{align*}

  By  Proposition~\ref{Smullyan},
    \begin{align*}
  \varphi_{\lambda_i(\bar{z},\bar{n}(\bar{z}))}= \varphi_{n_i(\bar{z})}.
     \end{align*}
     Therefore
    \begin{align*}
  \varphi_{f_i(\bar{z},\bar{n}(\bar{z}))}=^\ast \varphi_{n_i(\bar{z})}
  \end{align*}
 for $(\bar{z},\bar{n}(\bar{z}))\in\dom(f_i)$.
 Now we are ready do define $H:\omega^3\to\omega$:
  \begin{align*}
  H(\bar{x})=h(n_0(\bar{g}(\bar{x})),n_1(\bar{g}(\bar{x})),n_2(\bar{g}(\bar{x}))).
   \end{align*}
   Let us show that $H(\bar{x})=h(n_0(\bar{g}(\bar{x})),n_1(\bar{g}(\bar{x})),n_2(\bar{g}(\bar{x}) ))$ is a required computable function. Assume contrary that for some $x_0,\, x_1$ and $x_2$

 \[
H(x_0,x_1,x_2)\not\in
\Big( (A_i\cap W^{z_l}_{x_i})\cup (\overline{A_i}\cap \overline{W}^{z_l}_{x_i})
\Big)
\]
for some $i \in \{0, 1, 2 \} $.
  We have two cases:

  \begin{enumerate}
  \item[(a)] $H(\bar{x})\in A_i\setminus W^{z_l}_{x_i}$
  \item[(b)] $H(\bar{x})\in  W^{z_l}_{x_i}\setminus A_i$.
  \end{enumerate}
 It is worth noting that in both cases $K^{4,z_l}(g_i(\bar{x}),\bar{n}(\bar{g}(\bar{x})))\downarrow$.
In the case $(a)$,
 \begin{align*}
& \varphi_{F_i(\bar{n}(\bar{g}(\bar{x})))}=\varphi_{a_i(\bar{n}(\bar{g}(\bar{x})))} \mbox{ by the definition of $F_i$},\\
& \varphi_{a_i(\bar{n}(\bar{g}(\bar{x})))}= \varphi_{K^{4,z_l}(g_i(\bar{x}),\bar{n}(\bar{g}(\bar{x})))} \mbox{ by the definition of $g_i$},\\
& \varphi_{K^{4,z_l}(g_i(\bar{x}),\bar{n}(\bar{g}(\bar{x})))}= \varphi_{n_i(\bar{g}(\bar{x}))}\mbox{ by the choise of $\bar{n}$}.
\end{align*}


This contradicts the condition on $F_i$.
In the case $(b)$,
 \begin{align*}
& \varphi_{F_i(\bar{n}(\bar{g}(\bar{x})))}=\varphi_{b_i(\bar{n}(\bar{g}(\bar{x})))} \mbox{ by the definition of $F_i$},\\
& \varphi_{b_i(\bar{n}(\bar{g}(\bar{x})))}=\varphi_{K^{4,z_l}(g_i(\bar{x}),\bar{n}(\bar{g}(\bar{x})))} \mbox{ by the definition of $g_i$},\\
&\varphi_{K^{4,z_l}(g_i(\bar{x}),\bar{n}(\bar{g}(\bar{x})))}= \varphi_{n_i(\bar{g}(\bar{x}))}\mbox{ by the choise of $\bar{n}$}.
\end{align*}


This contradicts the condition on $F_i$.
Therefore $H$ is a required productive function.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{$m$-complete 3-tuple of $\Sigma^0_2$-sets}\label{index_sets}
Let us fix the following index sets:

\begin{align*}
&E_0=\{n\mid \pi_n\subseteq \{0,1,2\}\wedge\big( \varphi_n\cap  \omega\times\{0\}=^\ast\emptyset\big)\},\\
&E_1=\{n\mid \pi_n\subseteq \{0,1,2\}\wedge\big( \varphi_n\cap  \omega\times\{1\}=^\ast\emptyset\big)\},\\
&E_2=\{n\mid \pi_n\subseteq \{0,1,2\}\wedge\big( \varphi_n\cap  \omega\times\{2\}=^\ast\emptyset\big)\}.
\end{align*}
Using Proposition~\ref{criteria_m_compl} we show that  the 3-tuple $(E_0,E_1,E_2)$  is $m$-complete in the class of  $3$  -tuples of $\Sigma^0_2$-sets.

In order to define $(F_0,F_1,F_2)$ we first take  a computable function $h:\omega^3\to\omega$ such that


 \begin{eqnarray*}
\varphi_{h(x_0,x_1,x_2)}(3k)=\left \{
\begin{array}{ll}
0 & \mbox{ if }  \varphi_{x_0}(k)\downarrow\\
\uparrow &\mbox{ otherwise},
\end{array}
\right.
\end{eqnarray*}

 \begin{eqnarray*}
\varphi_{h(x_0,x_1,x_2)}(3k+1)=\left \{
\begin{array}{ll}
1 & \mbox{ if }  \varphi_{x_1}(k)\downarrow\\
\uparrow &\mbox{ otherwise},
\end{array}
\right.
\end{eqnarray*}

 \begin{eqnarray*}
\varphi_{h(x_0,x_1,x_2)}(3k+2)=\left \{
\begin{array}{ll}
2 & \mbox{ if }  \varphi_{x_2}(k)\downarrow\\
\uparrow &\mbox{ otherwise}.
\end{array}
\right.
\end{eqnarray*}
 Now we pick up appropriate functions $a_i$ and $b_i$ for $i\leq 2$.
The functions $b_i$ is defined by $\varphi_{b_i(\bar{x})}(k)=\varphi_{x_i}(k)+1$,  where $a_i$ is an index of $\rm{id}$ function.
Then we define  for $i\leq 2$
  \begin{eqnarray*}
F_i(\bar{x})=\left \{
\begin{array}{lll}
a_i & \mbox{ if }&  h(\bar{x})\in E_i\\
b_i(\bar{x}) &\mbox{ if }&  h(\bar{x})\not\in E_i.
\end{array}
\right.
\end{eqnarray*}
Let us show that $\varphi_{F_i(\bar{x})}\not\sim_2 \varphi_{x_i}$ for $i\leq 2$.
 Without loss of generality it is sufficient to consider $i=0$.
Assume $h(\bar{x})\not\in E_0$. Then $W_{h(\bar{x})}$ is infinite and infinitely often a value of $\varphi_{h(\bar{x})}$ is  zero.
By   construction, $W_{x_0}$ is infinite. Since for $k\in\omega$,
\begin{align*}
\varphi_{F_0(\bar{x})}(k)=\varphi_{b_0(\bar{x})}(k)=\varphi_{x_0}(k)+1,
\end{align*}
 there exist infinitely many $k\in\omega$ such that $\varphi_{F_0(\bar{x})}(k)\neq\varphi_{x_0}(k)$. As a corollary,
$\varphi_{F_0(\bar{x})}\neq^\ast\varphi_{x_0}$.
Assume $h(\bar{x})\in E_0$. Then  $\varphi_{x_0}$ is a finite function. Since for $k\in\omega$,
\begin{align*}
\varphi_{F_0(\bar{x})}(k)=\varphi_{a_0(\bar{x})}(k)= k,
\end{align*}
 we have $\varphi_{F_0(\bar{x})}\neq^\ast\varphi_{x_0}$.
\begin{lemma}

Let a $3$-tuple $(E_0,E_1,E_2)$ be $m$-complete in the class of  $3$-tuples of $\Sigma^0_2$-set.
Then the following 3-tuple
\begin{align*}
& Y_0=E _0\cap E_1\cap E_2,\\
& Y_1= E_1\cap E_2,\\
&Y_2=E_2\\
\end{align*}
is  $m$-complete in the class of  $3$-tuples  $(X_0,X_1,X_2)$ of $\Sigma^0_2$-set with the additional condition
$X_0\subseteq X_1\subseteq X_2$.
\end{lemma}
%\MK{may be add proof}

 \noindent By the choice of $(E_0,E_1,E_2)$  at the beginning of this section we have $Y_0\subseteq Y_1\subseteq Y_2$, where
\begin{align*}
&Y_0=\{n\mid \pi_n\subseteq \{0,1,2\}\wedge W_n \mbox{ is  finite}\},\\
&Y_1=\{n\mid \pi_n\subseteq \{0,1,2\}\vee
(\exists N)(\forall k\geq N)(\varphi_n(k)\downarrow\,\rightarrow\, \varphi_n(k)=0
\},\\
&Y_2=\{n\mid \pi_n\subseteq \{0,1,2\}\vee \varphi_n\cap  \omega\times\{2\}=^\ast\emptyset\big)\}.
\end{align*}



\begin{remark}
It is worth noting that if 3-tuple $(Z_0,Z_1,Z_2)$ is $m$-complete in  the class of 3-tuple  $(X_0,X_1,X_2)$
of $\Sigma^0_2$-sets with the additional condition $X_0\subseteq X_1\subseteq X_2$ then the set
$Z_0\cup(Z_2\setminus Z_1)\not\in \Sigma^0_2$ since this combination is the $m$-greatest 3-tuple among the similar combinations of $\Sigma^0_2$-sets.
\end{remark}


\subsection{Classes $K$    without computably presentable $\KR$}\label{without_constr}


Below we list important restrictions on a class $K$ of total computable numerical functions:

\begin{enumerate}
\item Together with the basic functions $\BF$ the class contains $+,\dotminus,\cdot, [\frac{x}{2}]$ and
$[\sqrt x]$.

\item  The class has a computable universal function  for all unary functions i.e. the sequence $\{\mathcal{F}_n\}_{n\in\omega}$ of all unary functions from $ K$ is computable.
\item There exists a computable function $H:\omega\to\omega$ such that for all $n\in\omega$
$\im(\mathcal{F}_{H(n)})= \{0\}\cup \{x+1\mid x\in W_n \}$. Moreover, for all $i\in W_n$,
$\mathcal{F}^{-1}_{H(n)}(i+1)$ is an infinite set.
%
\item It is closed under composition and either under the standard bounded recursion scheme or the following second  bounded  recursion scheme:
If $\alpha,\,\,g,\psi\in K$ and $f$ is defined by

  \begin{eqnarray*}
f(\bar{x},y)=\left \{
\begin{array}{lll}
\alpha(\bar{x})&\mbox{ if }& y=0\\
\psi(\bar{x},y,f(\bar{x},[\frac{y}{2}])) &\mbox{ if }& y\geq 1
\end{array}
\right.
\end{eqnarray*}
 and

\begin{align*}
f(\bar{x},y)\leq g(\bar{x},y)
\end{align*}
then $f\in K$.
\end{enumerate}

\begin{remark}\label{r_2}
It is worth noting that
 the class $K$ satisfying the restrictions above  contains all almost  constant functions,
  Cantor 3-tuple $(c,l,r)$, $\rm{sg}|x-y|$.

 \end{remark}
 \begin{remark}\label{r_e_classes} Some of natural examples that satisfy the restrictions above  are all $\mathcal{E}^n$, $n\geq 2$.
 For $\mathcal{E}^2$ the verification of satisfiability based on Ritchie's characterisation (see Preliminaries) and the existence of a computable
 universal function  for $\mathcal{E}^2$ and  for $\mathcal{E}^n$, $n\geq 3$ it is straightforward.
 Another good example is  the class $P$ of functions computable in polynomial time under binary notations of arguments and values.

 Characterization of $P$ in terms of the second  primitive recursion scheme was obtained by A.~Cobham in \cite{Cobham}. In particular, his result provides the item (4) for $P$, other items are straightforward.
 \end{remark}
\begin{theorem}\label{no_comp_copy}
Let $K$  satisfy the requirements above and $(\KR,\sigma_\str)$ be the structure generated by $\K$.
 Then $\KR$ does not have a computable presentation.
\end{theorem}
 The proof follows from Theorem~\ref{sigma02construct}   and the claim $A_0\cup(A_2\setminus A_1)\not\in \Sigma^0_2$ which  is based on the following proposition and Section~\ref{index_sets}.


\begin{proposition}
 $(Y_0,Y_1,Y_2)\leq_m (A_0,A_1,A_2)$.

\end{proposition}
 \begin{proof}
 We are going to construct a computable function $f$ such that $n\in Y_i\leftrightarrow f(n)\in A_i$. In order to do that we will construct a
  computable sequence $\{F_n\}_{n \in \omega}$ of computable functions
  by steps and then effectively find a  required reduction  $f$.


We take
\begin{itemize}
\item  a standard computable reduction function $\alpha:\omega\to\omega$ for $\rm{Fin}\leq_m \omega\setminus\rm{Tot}$ (c.f.  \cite{Shoenfield}) with the following  properties:
    \begin{itemize}
 \item if  $W_n$ is finite then $W_{\alpha(n)}$ is finite,
 \item if  $W_n$ is infinite then $\varphi_{\alpha(n)}$ is total,
\item  $\pi_n=\pi_{\alpha(n)}$,
\item If $(\exists^\infty a)\,\varphi_n(a)=x$ then $(\exists^\infty b)\,\varphi_{\alpha(n)}(b)=x$ and vice versa.
 \end{itemize}
\item a  computable function $t$ such that
\begin{itemize}
\item $W_{t(n)}= \{c(k,d)\mid \varphi_{\alpha(n)}(k)=d \}$.
\end{itemize}
\end{itemize}

 %It is worth noting that, by the  definition of $K$, $ W_{t(n)}\cup \{0\}=\im(\mathcal{F}_{H(t(n))})$.

%Now we point out the requirements on our construction which force us to do changes.

Now we point out the requirements on a step $s$  which we want to meet in our construction:
\begin{itemize}
\item $F^{s+1}_n \supseteq F^{s}_n$,
\item $\dom(F^s_n)=[0,\dots,m^s_n]$ is a proper  initial segment of $\omega$,
\item
 if $\mathcal{F}_{H(t_s(n))}(s+1)=c(c,d)+1\wedge d>2$ then
 $(\exists j)\, F_n(j)>2$,
  \item if  $\mathcal{F}_{H(t_s(n))}(s+1)=c(i,2)+1$
 then in the process of the construction we provide the following:
 $\overline{F_n}\not\in\{\overline{\mathcal{F}_0},\dots,\overline{\mathcal{F}_i}\}$,
\item $F_n=\bigcup_{s\in\omega} F^s_n$.
  \end{itemize}

\noindent \noindent  W.l.o.g. we assume now that K is closed under the second bounded recursion scheme  since the case
when K is closed under the standard bounded recursion scheme is much more easy so it is left to a reader.

  \noindent {\bf Description of the construction of $m^s_n$, $\{F^s_n\}_{n,s\in\omega}$, $t_s(n)$ and $I^{s}_n$}:

\noindent{\bf Step 0}

$m^n_0=0$, $F^0_n(0)=0$, $t_0(n)=t(n)$ and $I^0_n=0$.

\noindent{\bf Step s+1}

%

\noindent {\bf Case 1} If  $\mathcal{F}_{H(t_s(n))}(s+1)=c(i,0)+1$  or $\mathcal{F}_{H(t_s(n))}(s+1)=0$  then we proceed as follows:


  \begin{eqnarray*}
m^{s+1}_n=\left \{
\begin{array}{lll}
2m^s_n &\mbox{ if }& m^s_n>0\\
1 &\mbox{ if }& m^s_n=0
\end{array}
\right.
\end{eqnarray*}
and for all $j \leq m^s_n$, $F^{s+1}_n (j) = F^s_n (j)$,  for all $m^s_n \leq j\leq m^{s+1}_n$ we put  $F^{s+1}_n(j)= F^{s}_n(m^s_n)$, $t_{s+1}(n)=t_s(n)$ and $I^{s+1}_n=I^{s}_n$.

\noindent {\bf Case 2}  $\mathcal{F}_{H(t_s(n))}(s+1)=c(i,1)+1$ we consider the following subcases:

\begin{enumerate}
\item[Subcase 2.1] $i> s+1$.   We proceed as in Case~1.
\item[Subcase 2.2]$i\leq s+1$ and  $i\leq I^{s}_n$.   We proceed as in Case~1.
\item[Subcase 2.3] $ I^{s}_n < i\leq s+1$.
 We proceed as follows:
  \begin{eqnarray*}
m^{s+1}_n=\left \{
\begin{array}{lll}
2m^s_n &\mbox{ if }& m^s_n>0\\
1 &\mbox{ if }& m^s_n=0
\end{array}
\right.
\end{eqnarray*}
and for all $j \leq m^s_n$, $F^{s+1}_n (j) = F^s_n (j)$, for all $m^s_n \leq j< m^{s+1}_n$ we put  $F^{s+1}_n(j)= F^{s}_n(m^s_n)$ and for $F^{s+1}_n(m^{s+1}_n)$ we chose the least value
from $\{0,1\}$ such that $F^{s+1}_n(m^{s+1}_n)\neq F^{s}_n(m^s_n)$, $t_{s+1}(n)=t_s(n)$ and $I^{s+1}_n=i$.
\end{enumerate}


\noindent {\bf Case 3}
 If  $\mathcal{F}_{H(t_s(n))}(s+1)=c(i,2)+1$  then for all $j \leq m^s_n$, $F^{s+1}_n (j) = F^s_n (j)$ and  we proceed as follows:
$m^{s+1}_n=m^s_n+2(i+1)$ and for $k\leq i$   we chose the  values  of $F^{s+1}_n$ on the arguments $m^n_{s}+2k+1$ and $m^n_{s}+2k+2$ according with the following table:
%
\medskip

\begin{tabular}{ |p{2.5cm}|p{2.5cm}|p{2.7cm}| p{2.7cm}| }

%\multicolumn{4}{|c|}{} \\
%
$\mathcal{F}_k(m^s_n+2k+1)$& $\mathcal{F}_k(m^s_n+2k+2)$& $F^{s+1}_n(m^n_{s}+2k+1)$ & $F^{s+1}_n(m^n_{s}+2k+2)$\\
\hline
2& 2 &0&0\\
\hline
2& 0 &0&0\\
\hline
2& 1 &0&0\\
\hline
1& 2 &0&0\\
\hline
1& 1 &0&0\\
\hline
1& 0 &2&2\\
\hline
0& 2 &2&2\\
\hline
0& 1 &2&2\\
\hline
0& 0 &2&2\\
%
\hline
\end{tabular}
%
%
\medskip

\noindent The equality
%$W_{t_s(n)}\setminus W_{t_{s+1}(n)}$
$W_{t_{s+1} (n) } = W_{t_s(n)} \setminus \{c(i,2)\}$
defines the value of $t_{s+1}(n)$ and  $I^{s+1}_n = I^s_n$.

\noindent {\bf Case 4}
 If  $\mathcal{F}_{H(t_s(n))}(s+1)=c(i,d)+1$ and $d>2$  then  for all $j \leq m^s_n$, $F^{s+1}_n (j) = F^s_n (j)$ and  we proceed as  follows:
  \begin{eqnarray*}
m^{s+1}_n=\left \{
\begin{array}{lll}
2m^s_n &\mbox{ if }& m^s_n>0\\
1 &\mbox{ if }& m^s_n=0
\end{array}
\right.
\end{eqnarray*}
and for all $j \leq m^s_n$, $F^{s+1}_n (j) = F^s_n (j)$, for all $m^s_n \leq j< m^{s+1}_n$ we put  $F^{s+1}_n(j)= F^{s}_n(m^s_n)$ and $F^{s+1}_n (  m^{s+1}_n  ) = d$,  $t_{s+1}(n)=t_s(n)$
%
 and  $I^{s+1}_n = I^s_n$.

%%%%%%%%%%%%%%

 We put $F_n=\bigcup_{s\in\omega} F^s_n$ and effectively find  computable function $f:\omega\to\omega$ such that
 %$F_n\cap (W_{\alpha(n)}\times \omega)=\varphi_{f(n)}$.
 %
 $\varphi_{f (n)}  = (F_n \cap (W_ {\alpha (n)}  \times \omega ) ) \cup \{ c(x,d) \mid F_n(x)=d \wedge d>2 \}$.

  Now we show that $f$ is a required reduction.


%\noindent Case $n\in Y_0\leftrightarrow f(n)\in A_0$.

If $n\in Y_0$ then  $W_{\alpha(n)}$ is finite, so is $\varphi_{f(n)}$  and $f(n)\in A_0$.
%
%
If $n\not\in Y_0$ then there are two cases:

\noindent $1)$  $W_{\alpha(n)}$ is $\omega$, by construction, $\varphi_{f(n)}=F_n$ and $F_n$ is total, so  $f(n)\not\in A_0$.

\noindent $2)$ $\pi_n \not\subseteq \{0,1,2  \}$. Then for some $ j\in\omega$  $F_n (j) > 2$, so $ \pi_{f(n)} \not\subseteq \{0,1,2  \}$. Again  $f(n) \not\in A_0$.
  So we have $f^{-1}(A_0)=Y_0$.

%\noindent Case $n\in Y_1\leftrightarrow f(n)\in A_1$.


If $n\in Y_1\setminus Y_0$ then $\varphi_{\alpha(n)}$ is total and $\varphi_{\alpha(n)}=^* 0$. In this case $\varphi_{f(n)}=F_n$ and by construction $F_n\in \AC$ since $(\exists s_1\in \omega)(\forall s\geq s_1)\, I^n_s=I^n_{s_1}$.
So  $f(n)\in A_1\setminus A_0$.
%\MK{gde $n\not\in Y_1$}

%\noindent Case $n\in Y_2\leftrightarrow f(n)\in A_2$.

If $n\not\in Y_2$ then $\varphi_{\alpha(n)}$ is total and $\varphi_{f(n)}=F_n$. The case $\mathcal{F}_{H(t_s(n))}(s+1)=c(i,2)+1$ arises infinitely often and the collection of the corresponding numbers $i$ is infinite too.
 So, for infinitely many $i$,
either
${\rm im}(F_n)\not\subseteq \{0,1,2\}$ or
$\overline{F_n}\not\in \{\overline{\mathcal{F}_0},\dots,\overline{\mathcal{F}_i}\}$. Hence either ${\rm im}(F_n)\not\subseteq \{0,1,2\}$ or  $\overline{F_n}\not\in \KR$. That means $f(n)\not\in A_2$.

%Now we consider the most difficult case.
%
If $n\in Y_2\setminus Y_1$ then $\varphi_{\alpha(n)}=F_n$ is total. By the choice of $n$,
$(\exists N)(\forall i\geq N)\, \varphi_{\alpha(n)}(i)\neq 2$. Hence $(\exists^\infty i)\varphi_{\alpha(n)}(i)= 1$.

Let us note that after some step $s_0$ for all $i$ we have $c(i,2)\not\in W_{t_s(n)}$ for $s\geq s_0$. We define
$t_\infty(n)=t_{s_0}(n)$. It is easy to see that, for $s\geq s_0$, $t_\infty(n)=t_s(n)$.
%
On the step $s+1$, when $\mathcal{F}_{H(t_\infty(n))}(s+1)=c(i,1)+1$,  $F^{s+1}_n(m^{s+1}_n)\neq F^{s+1}_n(m^{s+1}_n-1)$.
Hence $F_n\not\in \AC$, so $f(n)\not\in A_1$.  So we have $f^{-1}(A_1)=Y_1$.

Using $s_0$ and $N$ from above we explain that $F_n\in \K$.

 Let $m_n=m^{s_0+1}_{n}$.
 It is easy to see
 % (see Appendix)
 that the following functions  belongs to $K$:
 \begin{itemize}
 \item the characteristic function of the set $A=\{m_n\cdot 2^i\mid i\geq 0\}$,
\item  the function $g(x)$, that computes $\max\{y\in A\mid y\leq x\}$ for $x\geq m_n$ and for $x< m_n$ it is equal to $0$,
%By definition, if $x\in A$ then $g(x)=x=m^{s+1}_n$ otherwise $x\in (g(x),g(2x))$
\item  the function $S(x)=\mu(s')(F^{s'}_n(x)\downarrow)$.
 \end{itemize}
% \MK{ to do}
 In order to meet our goal we construct the function $I(x)=I^{S(x)-1}_n$ by the following rules:

 Assume $I_0=I^{s_0}_n$. Then we define
  \begin{itemize}
  \item for $x<m_n$, $I(x)=0$,
  \item for $x=m_n$, $I(x)= I_0$,
  \item for $x>m_n$ and $g(x)>m_n$
\small{
   \begin{eqnarray*}
I(x)=\left \{
\begin{array}{l}
l(\mathcal{F}_{H(t_\infty(n))}(S(x)-1)-1) \mbox{ if }\\
  \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,I([\frac{x}{2}])\leq i\leq S(x)-1\wedge r(\mathcal{F}_{H(t_\infty(n))}(S(x)-1)-1)=1\\
I([\frac{x}{2}]) \mbox{ otherwise},
\end{array}
\right.
\end{eqnarray*}
}
   \item for $x>m_n$ and $g(x)=m_n$, $I(x)= I_0$.

  \end{itemize}


%
   From above we can see that $\lambda x.I(x)\in \K$.
%
%Let us note that in order to define   $F_(x)$ for $x\geq m_n$  we take a look on $\mathcal{F}_{H(t_\infty(n))}(S(x))$ and it has values either $<i,0>$ or
%$<i,1>$ for some $i\in\omega$. The same we do for $\mathcal{F}_{H(t_\infty(n))}(S([\frac{x}{2}]))$, and it has values either $<j,0>$ or
%$<j,1>$ for some $i\in \omega$.
%Using the characteristic functions of the sets $\{m_n\mid r(m_n)=0\}$ and $\{m_n\mid r(m_n)=1\}$ we can recognise which case takes place.
%
We can assume that $x\geq N$ and $S(x)>s_0$. Let us denote $i \leftrightharpoons l(\mathcal{F}_{H(t_\infty(n))}(S(x)-1)-1)$ and  consider two cases.

\noindent 1. Suppose $x\in A$.
%
 If $\mathcal{F}_{H(t_\infty(n))}(S(x))=c(i,0)+1$ then $F_n(x)=F_n([\frac{x}{2}])$.
 The same is done if  $\mathcal{F}_{H(t_\infty(n))}(S(x))=c(i,1)+1$ but $i\leq I(x)$ or $i>S(x)$.
%
 Otherwise, i.e., if  $\mathcal{F}_{H(t_\infty(n))}(S(x))=c(i,1)+1$ and $I(x)\leq i\leq S(x)$ then for the value of $F_n(x)$ we chose the first one from $\{0,1\}$ which differs from $F_n([\frac{x}{2}])$.

\noindent 2. Suppose $x\not\not\in A$.
%
 If $\mathcal{F}_{H(t_\infty(n))}(S([\frac{x}{2}]+1)=c(i,0)+1 \mbox{or } 0$ then $F_n(x)=F_n([\frac{x}{2}])$.
 The same is done if $\mathcal{F}_{H(t_\infty(n))}(S([\frac{x}{2}]+1)=c(i,0)+1$ but $i\leq I([\frac{x}{2}]+1)$ or
  $i>S([\frac{x}{2}]+1)$.
  Otherwise, i.e., if  $\mathcal{F}_{H(t_\infty(n))}(S([\frac{x}{2}]))=c(i,1)+1$ and $I([\frac{x}{2}])\leq i\leq S([\frac{x}{2}])$ %
  then for the value of $F_n(x)$ we chose the first one from $\{0,1\}$ which differs from $F_n([\frac{x}{2}])$.
%
 Therefore the scheme above shows that $F_n\in\K$.  So we have $f^{-1}(A_2)=Y_2$.




\end{proof}

\begin{corollary}
The structures $\widetilde{P}$, $\widetilde{\mathcal{E}}^n$, $n\geq 2$ do not have computable copies and
the fields of $\mathcal{E}^n$-numbers, $n\geq 3$ do not have computable copies.
\end{corollary}
\begin{proof}
The claim follows from Corollary~\ref{E-numb_rcfield} and Theorem~\ref{no_comp_copy}.
\end{proof}


%The claim follows from real closedness of the corresponding fields.
\bigskip
\begin{thebibliography}{1}
%
%\bibitem{ALR}
%Allender E., Loui M.C. and Regan K.W.,
%Complexity classes, In handbook: Algorithms and theory of computation handbook: general concepts and techniques,
%Chapman and Hall CRC,  2010.


\bibitem{Alaev}
Alaev,~P.~E.,
Computable Homogeneous Boolean Algebras and a Metatheorem,
A local Theory of Degrees of Unsolvability and $\Delta^0_2$-sets. Algebra and Logic volume 43, pp. 73–87, Springer, 2004.


\bibitem{Arslanov_0}
Arslanov,~M.~M.,
A local Theory of Degrees of Unsolvability and $\Delta^0_2$-sets. Kazan University Press, 1987.  (in Russian)

\bibitem{Arslanov}
Arslanov,~M.~M.,
On some generalisations of  a fixed point theorem.  \emph{News of universities, Mathematics} No 5, 1981, pp. 9--16.
 (in Russian)
%
\bibitem{Cobham}
Cobham, A., The intrinsic computational difficulty of functions.
In
Y. Bar-Hillel ed., Proc. of the 1964 International Congress for Logic,
Methodology, and the Philosophy of Science, pp. 24-30, North Holland,
Amsterdam, 1964.

%
\bibitem{Ersh_PRCM}
 Ershov,~Yu.~L.,
Problems of decidability and constructive models. Nauka, 1980 (in Russian).
%
\bibitem{Ersh_TH}
 Ershov,~Yu.~L.,
 Theory of numberings.  \emph{ in: E.R. Griffor, ed., Handbook of Computability
Theory. Elsevier Science B.V., Amsterdam}, 1999, pp.  473--503.
%
%
  \bibitem{ErshGonch}
Ershov,~Yu.~L. and Goncharov~S.~.S., Constructive models, Siberian School of Algebra
and Logic, Consultants Bureau, New York, 2000.
%
%
  \bibitem{Gonch1}
 Goncharov~S.~S.,
Countable Boolean Algebras and Decidability, Siberian School of Algebra and Logic, Springer, 1997.
%
  \bibitem{Grzegorczyk}
Grzegorczyk~A., Some classes of recursive functions, Rozprawy Mathemaczne IV, Warszawa, 1953.
%
  \bibitem{Khisamiev}
 Khisamiev~N., Constructive abelian groups, Handbook of recursive mathematics,
Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 1177--1231.
%
\bibitem{Ko}
Ko, Ker-I, Complexity Theory of Real Functions, Progress in Theoretical Computer Science, Springer, 1991.
%
\bibitem{KK_spectr}
Korovina~M. and
               Kudinov~O., Spectrum of the computable real numbers. Algebra Log. 55(6), 2017, pp. 485–500.

\bibitem{KK_up}
 Korovina M. and
                Kudinov O.,
The Uniformity Principle for Sigma-definability,
J. Log. Comput.,
  vol.19,
  No. 1, 2009,
   pp. 159--174.
%
\bibitem{Malcev}
 Mal’cev A.I., Constructive algebras. Uspechi mat. nauk, 16, No 3 (1961) pp. 3–60
(in Russian, English translation in: The Metamathematics of Algebraic Systems,
North Holand, Amsterdam, 1971, pp. 148–214).
%
\bibitem{Miller}
Miller~M, Gonzales~V. O.,
Degree spectra of real closed fields, Archive for Mathematical Logic  58, pp. 387–411, 2019.
%
\bibitem{Morozov}
 Morozov~A.S.,
Countable homogeneous boolean algebras, Algebra and Logic, 21, No. 3, 1982, pp. 269--282.
%
\bibitem{Rabin}
Rabin M.O., Computable algebra, general theory and theory of computable fields.
Trans. Amer. Math. Soc., 95, No 2 (1960) pp. 341—360.
%
\bibitem{Ritchie}
Ritchie, R.W., Classes of predictably computable functions. Trans. Amer. Math Soc. 106, 1963, pp. 139--173.
%
 \bibitem{Rogers}
Rogers~ H.,
  \emph{ Theory of Recursive Functions and Effective Computability}.
 McGraw-Hill, New York, 1967.
 %
\bibitem{Shoenfield}
Shoenfield~J.~R.,
 \emph{  Degrees of unsolvability},
 North-Holland Publ., 1971.

  \bibitem{Smullyan}
 Smullyan~R.M., Theory of Formal Systems, Annals of mathematics studies, 47, Princeton, N.J.
  \bibitem{Soarehbook}
 Soare~R.I.,
 \emph{ Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets}.
 Springer Science and Business Media, 1997.
 %%
 \bibitem{Weihrauchbook}
 Weihrauch~K.,
 \emph{ Computable Analysis} 2000.
 Springer Verlag.
 
\end{thebibliography}
\end{document}
