\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{mathrsfs}

\def\udcs{510.67} %Здесь автор определяет УДК своей работы
\def\mscs{03B10,03D35} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{1}


\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}

\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]
     {\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 Том 20, стр. 144--144 (2023) \hspace{63.7mm}{\rm\small УДК \udcs}}
     \newline
        {\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

%\hoffset-15.3ex\voffset-16.2ex%AUXILIARY AUTHOR'S SETTING

\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[Prime models of infinite dimensions having $\omega$-stable theories]{The Tarski-Lindenbaum algebra of the class of prime models with infinite algorithmic dimensions having omega-stable theories}%
\author{{M.G. PERETYAT'KIN}}%
\address{Mikhail G. Peretyatkin  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Institute of Mathematics and Mathematical Modeling,
\newline\hphantom{iii} Shevchenko 28,
\newline\hphantom{iii} 050010, Almaty, Kazakhstan}%
\email{peretyatkin@math.kz}%

\thanks{\sc Peretyat'kin, M.G., The Tarski-Lindenbaum algebra of the class of prime models with infinite algorithmic dimensions having omega-stable theories}%
\thanks{\copyright \ 2024 Peretyat'kin M.G}
\thanks{\rm This research is funded by the Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan (Grant No BR20281002).}%
\thanks{\it Received December, 14, 2023, published July, 14, 2024}%



\semrtop \vspace{1cm} \maketitle {\small
\begin{quote}
\noindent{\sc Abstract. }


We study the class of all prime strongly constructivizable models of infinite
algorithmic dimensions having $\omega$-stable theories in a fixed finite rich
signature. It is proved that the Tarski-Lindenbaum algebra of this class
considered together with a G\"odel numbering of the sentences is a Boolean
$\Pi^0_4$-algebra whose computable ultrafilters form a dense subset in the
set of all ultrafilters; moreover, this algebra is universal with respect to
the class of Boolean $\Sigma^0_3$-algebras. This gives a characterization to
the Tarski-Lindenbaum algebra of the class of all prime strongly
constructivizable models of infinite algorithmic dimensions having
$\omega$-stable theories.

\medskip

\noindent{\bf Keywords:} Tarski-Lindenbaum algebra, strongly constructive model, computable
isomorphism, semantic class of models, $\omega$-stable theory, prime model.
\end{quote}
}

\bigskip

The problem of characterizing Tarski-Lindenbaum algebras of some semantic
classes of models of a finite rich signature was considered in the works
[10], [7], [11], [12], [13], and others. In this work, we describe the
Tarski-Lindenbaum algebra of the class of all prime strongly
constructivizable models of infinite algorithmic dimensions having
$\omega$-stable theories.

\medskip

%==============================================================================
{\bf Preliminaries.~}\addcontentsline{toc}{section}{\numberline{}Preliminaries}%
%==============================================================================
We consider theories in first-order predicate logic {\itshape with equality}
and use general concepts of model theory, algorithm theory, Boolean algebras
and constructive models found in [6], [14], [15], [1], and [4]. We consider
signatures admitting G\"odel's numberings of the formulas. Generally,
{\itshape incomplete theories} are considered.

A finite signature is called {\itshape rich}, if it contains at least one
$n$-ary predicate or function symbol for $n\!>\!1$, or two unary function
symbols. A theory $F$ is called {\itshape finitely axiomatizable} if it is
defined by a finite set of axioms, and its signature is finite. The following
notations are used: $\mbox{\itshape FL}(\sigma)$ is the set of all formulas
of signature $\sigma$, $\mbox{\itshape FL}_n(\sigma)$ is the set of all
formulas of signature $\sigma$ with $n$ free variables $x_0,x_1,...,x_{n-1}$,
$\mbox{\itshape SL}(\sigma)$ is the set of all sentences (i.e., closed
formulas) of signature $\sigma$. In the work, we use a finite rich signature
$\sigma$, and consider a fixed G\"odel numbering $\varPhi_i$,
$i\in\mathbb{N}$, of the set $\mbox{\itshape SL}(\sigma)$. The set of all
G\"odel numbers of formulas from a set $\varSigma\subseteq\mbox{\itshape
SL}(\sigma)$ is denoted by $\operatorname{Nom}(\varSigma)$. We use notation
$\mathcal{P}(A)$ for the power-set of $A$, and $|A|$ or
$\operatorname{Card}(A)$ for cardinality of the set $A$. The set of all
finite tuples $\alpha$ of the form
$\alpha=\langle\alpha_0,\alpha_1,\ldots\!,\alpha_n\rangle$,
$\alpha_i\in\{0,1\}$, is denoted by $2^{<\omega}$. The empty tuple is denoted
by $\varnothing$. The {\itshape canonical $($G\"odel$)$ index} of a finite
tuple of zeros and ones of the form
$\varepsilon=\raisebox{0.25ex}{\footnotesize$\langle$}\varepsilon_0,\varepsilon_1,\ldots,\varepsilon_{n-1}\raisebox{0.25ex}{\footnotesize$\rangle$}$,
$\varepsilon_i\in\{0,1\}$, is the number $\operatorname{Nom}(\varepsilon)\;=
2^n+\varepsilon_0 2^{n-1}+\varepsilon_1 2^{n-2}+\ldots+\varepsilon_{n-1}-1$.
We often write shortly
$\raisebox{0.25ex}{\footnotesize$\langle$}\varepsilon\raisebox{0.25ex}{\footnotesize$\rangle$}$
instead of $\operatorname{Nom}(\varepsilon)$.

A countable or finite model $\mathfrak{M}$ together with a numeration
$\nu:\mathbb{N}\xrightarrow{onto}|\mathfrak{M}|$ is called a {\itshape
numerated model} and is denoted by $(\mathfrak{M},\nu)$. We denote by
$\mathfrak{M}_\nu$ the model obtained by enriching signature of
$\mathfrak{M}$ to $\sigma'=\sigma\cup\{c_i\mid i\in\mathbb{N}\}$ in such a
way that each new constant $c_i$ is interpreted by $\nu(n)$ in
$|\mathfrak{M}|$. A numerated model $(\mathfrak{M},\nu)$ is said to be
{\itshape constructive} if the atomic diagram $\mbox{\itshape
A\rule{-0.11ex}{0pt}D}(\mathfrak{M}_\nu)$ is computable, and
$(\mathfrak{M},\nu)$ is {\itshape strongly constructive} if the theory
$\operatorname{Th}(\mathfrak{M}_\nu)$ is decidable. Two numerated models
$(\mathfrak{N},\nu)$ and $(\mathfrak{M},\upsilon)$ are said to be {\itshape
computably isomorphic}, denoted
$(\mathfrak{N},\nu)\cong(\mathfrak{M},\upsilon)$, if there is an isomorphism
$\mu$ between $\mathfrak{N}$ and $\mathfrak{M}$, and two computable functions
$f(x)$ and $g(x)$, such that the following diagram is commutative:

\vskip0.251ex
\centerline{\includegraphics[scale=0.1198]{Fig1}}%\Figura()<fig1>[c]
\vskip0.951ex

\noindent%
In a parallel way, we also write $\mathfrak{N}\cong\mathfrak{M}$ to indicate
that abstract models $\mathfrak{N}$ and $\mathfrak{M}$ (without numerations)
are isomorphic.

We consider Boolean algebras in the signature
$\sigma_{_{BA}}=\{\cup,\cap,-,\mathbf{0},\mathbf{1}\}$. Let $\mathcal{B}$ be
a Boolean algebra, and $a\in\mathcal{B}$. By $\mathcal{B}[a]$, we denote the
restriction of the Boolean algebra $\mathcal{B}$ on the set of all
subelements of the element $a$ counting that $\mathbf1=a$ and $-x$ is defined
as $a\,{\!\smallsetminus\!}\,x$ in $\mathcal{B}[a]$. If $b$ is an element in
a Boolean algebra and $\alpha\in\{0,1\}$, then $b^\alpha$ means $b$ for
$\alpha=1$ and $-b$ for $\alpha=0$. Similarly, if $\varPhi$ is a formula and
$\alpha\in\{0,1\}$, then $\varPhi^\alpha$ means $\varPhi$ for $\alpha=1$ and
$\mbox{\footnotesize\raisebox{-0.39ex}{$\urcorner\,$}}\varPhi$ for
$\alpha=0$.

Let $T$ be a theory of signature $\sigma$. On the set of sentences
$\mbox{\itshape SL}(\sigma)$, an equivalence relation $\sim_T$ is defined by
the rule $\varPhi\sim_T\varPsi\Leftrightarrow T\vdash(\varPhi\iff\varPsi)$.
The logical connectives $\lor$, ${{\,\&\,}}$, and
$\mbox{\footnotesize\raisebox{-0.39ex}{$\urcorner\,$}}$ generate Boolean
operations $\cup$, $\cap$, and $-$ on the quotient set $\mbox{\itshape
SL}(\sigma)/\sim_T$; One can easily check that, these operations are
well-defined on the $\sim_T$-classes. Thereby, we obtain an algebra of the
form
$$
L(T)= \bigl(\mbox{\itshape SL}(\sigma)/\sim_T\;;\
\cup,\cap,-,\mathbf{0},\mathbf{1}\bigr),
$$
that, in fact, is a Boolean algebra. It is called the {\itshape
Tarski-Lindenbaum algebra} of the theory $T$; alternatively, it is called the
{\itshape Boolean sentence algebra} of $T$, cf. [3]. By $\mathcal{L}(T)$, we
denote the Tarski-Lindenbaum algebra $L(T)$ considered together with a
G\"odel numbering $\gamma$; thereby, the concept of a computable isomorphism
is applicable to such objects. A similar construction with respect to
formulas with $n$ free variables gives a definition of the {\itshape
Tarski-Lindenbaum algebra} $L_n(T)$ of theory $T$ {\itshape with $n$ free
variables}, $n<\omega$. Such algebras are often considered in the case when
the theory $T$ is complete.

Following Rogers, we use the notation $W_n$ for $n$th computably enumerable
set in Post's numbering of the family of all c.e. sets, [14,\,Sec.\,5.2].
Moreover, $W_n^t$ is a finite part of the set $W_n$ that can be computed in
$t$ steps. Furthermore, we denote by $W^X_n$ the computably enumerable set
with c.e. index $n$ relative to computability with an oracle
$X\subseteq\mathbb{N}$, [14,\,Sec.\,9.3].

We give an example of a complete set in the hierarchy class $\Pi^1_1$.

{\bf Lemma 0.1.} {\itshape There is a computable sequence
$(\mathcal{L}_i,\nu_i)$, $i<\omega$, of constructive linear orderings such
that}
$$
\mathcal{W}=\bigl\{n\mid\,\mathcal{L}_n~\mbox{\itshape is a well-ordered
set}\,\bigr\}
\eqno(0.1)
$$
{\itshape is an $m$-complete in the class $\Pi^1_1$ set}.

{\sc Proof.} See a construction in [9,\,p.\,44]. \hfill\mbox{$\Box$}

%================================================================================
\section{Boolean algebras over classes of hierarchies}
%================================================================================

Let $\Xi$ be a class of a hierarchy, eg. $\Sigma^0_n$, $\Delta^0_n$,
$\Pi^0_n$, $\Sigma^1_n$, or $\Pi^1_n$ with $0\!<\!n\!<\!\omega$ (actually, we
do not concern other classes of hierarchies in this paper). A numerated
Boolean algebra $(\mathcal{B},\nu)$ is called a $\Xi$-{\itshape algebra}, if
all its signature operations are uniformly presentable by computable
functions on $\nu$-numbers, while the equality predicate in $\mathcal{B}$ is
a $\Xi$-relation in the numeration $\nu$; i.e., there exist computable
functions $u(x,y)$, $v(x,y)$, $w(x)$, and a relation $E(x,y)$ which represent
the Boolean algebra as follows, for any $x,y\in\mathbb{N}$:\vskip-2.5ex
$$
\renewcommand{\arraystretch}{1.3}\arraycolsep=0pt\begin{array}[t]{lllll}
&\nu(x)\cup\nu(y)=\nu(u(x,y)),\\
&\nu(x)\cap\nu(y)=\nu(v(x,y)),\\
&-\nu(x)=\nu(w(x)),\\
&\nu(x)=\nu(y)\,\Leftrightarrow\,E(x,y), \ \ E\in\Xi.
\end{array}
\eqno(1.1)
$$
A Boolean algebra $\mathcal{B}$ is said to be a $\Xi$-algebra, if there is a
numeration $\nu$ such that $(\mathcal{B},\nu)$ is a Boolean $\Xi$-algebra.

As it is accepted, cf. [14,\,Sec.\,14.1], the class of all relations on
$\mathbb{N}$ expressible by $\Sigma^X_n$-forms is denoted by $\Sigma^X_1$,
while the class of all relations expressible by $\Pi^X_n$-forms is denoted by
$\Pi^X_1$; we also denote $\Delta^X_n=\Sigma^X_n\cap\Pi^X_n$. In particular,
$\Sigma^X_1$ is the class of all $X$-enumerable relations on the set
$\mathbb{N}$.

A numerated Boolean algebra $(\mathcal{B},\nu)$ is said to be $X$-{\itshape
enumerable} if all operations in $(\mathcal{B},\nu)$ are presented by
computable functions, while the equality relation is $X$-enumerable in the
numeration $\nu$. A Boolean algebra $\mathcal{B}$ is said to be an
$X$-{\itshape enumerable} algebra if there is a numeration $\nu$ such that
$(\mathcal{B},\nu)$ is an $X$-enumerable Boolean algebra.

{\bf Lemma 1.1.} {\itshape For an arbitrary numerated Boolean
$\Sigma^X_1$-algebra $(\mathcal{B},\nu)$, there is a numeration $\upsilon$ of
$\mathcal{B}$ such that $(\mathcal{B},\upsilon)$ is a Boolean
$\Sigma^X_1$-algebra whose computable ultrafilters form a dense set in the
set of all ultrafilters of the algebra $(\mathcal{B},\upsilon)$}.

{\sc Proof.} Cf. [12,\,Lem.\,2]. \hfill\mbox{$\Box$}

%================================================================================
\section{An isomorphism criterion for Boolean sentence algebras}
%================================================================================

Generalizing constructions of computable isomorphisms in the works [11],
[12], and [13], we obtain the following criterion for isomorphism of a given
numerated Boolean algebra to a segment of the Tarski-Lindenbaum algebra of a
class of models.

{\bf Theorem 2.1.} {\itshape Given a numerated Boolean algebra
$(\mathcal{B},\nu)$ together with a class $K$ of models of a finite rich
signature $\sigma$ and a sentence $\varPhi$ of the signature $\sigma$.
Suppose that $g_i$, $i\in\mathbb{N}$, is a generating set for $\mathcal{B}$,
and $\theta_i$, $i\in\mathbb{N}$ is a generating set for
$\mathcal{L}(\operatorname{Th}(K))$. A partial mapping $\lambda^\ast$ defined
by rule $\lambda^\ast(g_i)=\theta_i$, $i\in\mathbb{N}$, uniquely determines
an isomorphism}
$$
\lambda:\mathcal{B}\to\mathcal{L}(\operatorname{Th}(K\cap\operatorname{Mod}_\sigma(\varPhi)))
\eqno(2.1)
$$
{\itshape if and only if for all $\alpha$ in $2^{<\omega}$,
$\alpha=\raisebox{0.25ex}{\footnotesize$\langle$}\alpha_0,\alpha_1,...,\alpha_k\raisebox{0.25ex}{\footnotesize$\rangle$}$,
we have}:
$$
g_0^{\alpha_0}\cap...\cap g_k^{\alpha_k}\ne\mathbf0\ \Leftrightarrow\
\varPhi{\,\&\,}\theta_0^{\alpha_0}{\,\&\,}...{\,\&\,}\theta_k^{\alpha_k}\
\mbox{\itshape has a $K$-model}.
\eqno(2.2)
$$
{\itshape Moreover, the mapping $\lambda$ represents a computable
isomorphism}
$$
\lambda:(\mathcal{B},\nu)\to(\mathcal{L}(\operatorname{Th}(K\cap\operatorname{Mod}_\sigma(\varPhi))),\gamma)
\eqno(2.3)
$$
{\itshape with respect to a G\"odel numbering $\gamma$ of $\mbox{\itshape
SL}(\sigma)$, whenever the sequence $g_i$, $i\in\mathbb{N}$, is computable in
$(\mathcal{B},\nu)$, while $\theta_i$, $i\in\mathbb{N}$, is computable in the
G\"odel numbering $\gamma$}.

{\sc Proof.} For any tuple $\alpha$ in $2^{<\omega}$,
$\alpha=\raisebox{0.25ex}{\footnotesize$\langle$}\alpha_0,...,\alpha_k\raisebox{0.25ex}{\footnotesize$\rangle$}$,
consider elements:
$$
\renewcommand{\arraystretch}{1.3}\arraycolsep=0pt\begin{array}[t]{lllll}
b_\alpha=g_0^{\alpha_0}\cap...\cap g_k^{\alpha_k},
\\
\varTheta_\alpha=\theta_0^{\alpha_0}{\,\&\,}...{\,\&\,} \theta_k^{\alpha_k}.
\end{array}
\eqno(2.4)
$$
For an arbitrary finite set of tuples
$\alpha,\,\beta,\,\ldots\,\delta\,\in2^{<\omega}$, we put
$$
\lambda(b_{\alpha}\cup b_{\beta}\cup...\cup b_{\delta})\;=\;
\varTheta_{\alpha}\lor \varTheta_{\beta}\lor...\lor \varTheta_{\delta}.
\eqno(2.5)
$$%

Based on (2.2), it is possible to show that $\lambda$ is a bijective mapping
from $\mathcal{B}$ to
$\mathcal{L}\bigl(\operatorname{Th}(K\cap\operatorname{Mod}(\varPhi))\bigr)$
because the expressions involved in (2.5) cover all elements of the algebras
we are considering; moreover, $\mu$ is an isomorphism from $\mathcal{B}$ into
$\mathcal{L}\bigl(\operatorname{Th}(K\cap\operatorname{Mod}(\varPhi))\bigr)$.
Obviously, $\mu$ is a computable isomorphism in numerations $\nu$ and
$\gamma$ provided that the generating sequences are computable in these
numerations.

Theorem 2.1 is proved. \hfill\mbox{$\Box$}

%================================================================================
\section{Strong constructivizations of prime models}
%================================================================================

A model $\mathfrak{M}$ is called {\itshape prime} if it can be elementarily
embedded in any other model of theory $T=\operatorname{Th}(\mathfrak{N})$.
Vaught's criterion in [16] states that a countable complete theory $T$ has a
prime model if and only if the family of principal type in of this theory is
dense in the family of all types (equivalently, all Tarski-Lindenbaum
algebras $L_n(T)$, $n<\omega$, are atomic), while the model $\mathfrak{N}$ of
theory $T$ is prime if and only if any finite tuple
$\bar{a}\in|\mathfrak{N}|$ realizes a principal type of this theory.

Let us consider some technical facts about prime models.

{\bf Lemma 3.1.} {\itshape Let $T$ be a complete decidable theory. The set
$\mathcal{A}'$ of all formulas of the Tarski-Lindenbaum algebras
$\mathcal{L}_n(T)$, $n\in\mathbb{N}$ that are not atoms of theory $T$ is
computably enumerable}.

{\sc Proof.} A formula $\varphi(\bar{x})$ is not an atom of theory $T$ if
either it is inconsistent with $T$ or there exists a formula $\psi(\bar{x})$
such that both formulas $\varphi(\bar{x}){\,\&\,}\psi(\bar{x})$ and
$\varphi(\bar{x}){\,\&\,}\mbox{\footnotesize\raisebox{-0.39ex}{$\urcorner\,$}}\psi(\bar{x})$
are compatible with $T$. Based on this, it is simple to construct an
effective enumeration of the set $\mathcal{A}'$.
\hfill\mbox{$\Box$}

{\bf Lemma 3.2.} {\itshape Let $T$ be a complete decidable theory. The set
$\mathcal{A}$ of atomic formulas of the Tarski-Lindenbaum algebras
$\mathcal{L}_n(T)$, $n\in\mathbb{N}$ is computably enumerable if and only if
$\mathcal{A}$ is computable, i.e. $\mathcal{A}$ is uniformly computable in
the parameter $n$}.

{\sc Proof.} Implication $\Leftarrow$ is obvious. As for the implication
$\Rightarrow$, this assertion is a simple consequence of Lemma 3.1.
\hfill\mbox{$\Box$}

A model $\mathfrak{N}$ is said to be {\itshape strongly constructivizable} if
it admits a strong constructivization. A model $\mathfrak{N}$ has algorithmic
dimension $1$, symbolically $\dim_{s.c.}(\mathfrak{N})=1$, if $\mathfrak{N}$
is strongly constructivizable, moreover, any two strong constructivizations
$\nu_1$ and $\nu_2$ $\mathfrak{N}$ are equivalent, that is the numbered
models $(\mathfrak{N},\nu_1)$ and $(\mathfrak{N},\nu_2)$ are constructively
isomorphic, symbolically $(\mathfrak{N},\nu_1)\cong(\mathfrak{N},\nu_2)$. If
$\dim_{s.c.}(\mathfrak{N})=1$, we say that the model $\mathfrak{N}$ is
{\itshape autostable with respect to strong constructivizations} or simply
{\itshape autostable}, since the case of weak constructivizations is not
considered in this paper. A model $\mathfrak{N}$ has algorithmic dimension
$\omega$, symbolically $\dim_{s.c.}(\mathfrak{N})=\omega$, if there is an
infinite sequence of strong constructivizations $\nu_i$, $i<\omega$ of this
model such that any two numerated models in the sequence
$(\mathfrak{N},\nu_i)$, $i<\omega$ are not isomorphic.

It was proved in [8] that, for any strongly constructivizable model
$\mathfrak{N}$ only cases $\dim_{s.c.}(\mathfrak{N})=1$ and
$\dim_{s.c.}(\mathfrak{N})=\omega$ are possible, while the cases of finite
algorithmic dimensions $\dim_{s.c.}(\mathfrak{N})=n$, $1<n<\omega$, are
impossible. Namely, the following assertion is proved.

{\bf Theorem 3.3.} (Nurtazin criterion on autostability). {\itshape Let
$\mathfrak{M}$ be a strongly constructivizable model of a complete decidable
theory $T$. Then the following claims are equivalent}:

(a) {\itshape $\mathfrak{M}$ is autostable with respect to strong
constructivizations},

(b) {\itshape there is a finite sequence $\bar{a}$ of elements
$|\mathfrak{M}|$ such that enrichment $(\mathfrak{M},\bar{a})$ of the model
$\mathfrak{M}$ with these constants is a prime model and the family of sets
of atoms of Tarski-Lindenbaum algebras $\mathcal{L}_n(T')$, $n\in\mathbb{N}$,
of theory $T'=\operatorname{Th}(\mathfrak{M},\bar{a})$ is computable, i.e. ,
the indicated family is uniformly computable in the parameter $n$}.

{\itshape Moreover, if conditions $(a)$ and $(b)$ are not satisfied, there
exists an infinite sequence $\nu_i$, $i<\omega$ of strong constructivizations
of the model $\mathfrak{M}$ such that, for any $i,j<\omega$, $i\ne j$,
numbered models $(\mathfrak{M},\nu_i)$ and $(\mathfrak{M},\nu_j)$ are not
constructively embeddable in each other}.

{\sc Proof.} See [8,\,Th.\,1]. \hfill\mbox{$\Box$}

Now, we present two key statements for prime models.

{\bf Theorem 3.4.} {\itshape Let $T$ be a complete decidable theory with a
prime model $\mathfrak{N}$. A model $\mathfrak{N}$ is strongly
constructivizable if and only if the set of principal types of the theory $T$
is computable}.

{\sc Proof.} See [2,\,Th.\,1] or [5,\,Sec.\,1]. \hfill\mbox{$\Box$}

{\bf Theorem 3.5.} {\itshape Let $T$ be a complete decidable theory with a
strongly constructivizable prime model $\mathfrak{N}$. The following
statements are equivalent to each other}:

{\footnotesize\ttfamily(a)} {\itshape the set of formulas $\mathcal{A}$
presenting atoms in the Tarski-Lindenbaum algebras $\mathcal{L}_n(T)$,
$n\in\mathbb{N}$, is computably enumerable},

{\footnotesize\ttfamily(b)} {\itshape the set of formulas $\mathcal{A}$
presenting atoms in the Tarski-Lindenbaum algebras $\mathcal{L}_n(T)$,
$n\in\mathbb{N}$, is computable uniformly in $n$},

{\footnotesize\ttfamily(c)} {\itshape the model $\mathfrak{N}$ is autostable
with respect to strong constructivizations}.

{\sc Proof.} The proof is based on the Nurtazin criterion [8].

(a)$\Rightarrow$(b) This implication follows from Lemma 3.2.

(b)$\Rightarrow$(c) By assumption, the prime model $\mathfrak{N}$ is strongly
constructivizable, while the theory $T$ is complete and decidable. We also
suppose that the set of atoms $\mathcal{A}$ of theory $T$ is computable.
Applying an effective version of Vaught's construction for an isomorphism
between elementary equivalent prime models, [16], it is possible to construct
a computable isomorphism $\mu:(\mathfrak{N},\nu)\to(\mathfrak{N},\nu')$ for
any two strong constructivizations $\nu$ and $\nu'$ of the model
$\mathfrak{N}$.

(c)$\Rightarrow$(a) Assume that the prime model $\mathfrak{N}$ is autostable
with respect to strong constructivizations, i.e., Part (a) of Theorem 3.3
holds. Then, Part (b) of Theorem 3.3 must also hold, i.e., there is a finite
sequence $\bar{a}$ of elements in $|\mathfrak{N}|$ such that the model
$\mathfrak{N}^\ast=(\mathfrak{N},\bar{a})$ of theory
$T^\ast=\operatorname{Th}(\mathfrak{N},\bar{a})$ of signature
$\sigma^\ast=\sigma\cup\{a_i\mid a_i\in\bar{a}\}$ is a prime model and the
family of atoms of the Tarski-Lindenbaum algebras
$\mathcal{L}_n(\operatorname{Th}(\mathfrak{N},\bar{a}))$, $n\in\mathbb{N}$,
is computable uniformly in $n$. By condition, the model $\mathfrak{N}$ itself
is prime. Since any finite tuple in a prime model realizes a principal type,
there is a formula $\theta(\bar{z})$ that is an atom of theory $T$ such that
$\mathfrak{N}\models\theta(\bar{a})$ holds.

We consider a technical statement linking the theories $T$ and $T^\ast$:
$$
\renewcommand{\arraystretch}{1.3}\arraycolsep=0pt\begin{array}[t]{lllll}
\phi(\bar{x})\in\mbox{\itshape FL}(\sigma)~\mbox{\itshape is an atom of\/}~
T\,\Leftrightarrow~ \mbox{\itshape there
is}~\varphi(\bar{x},\bar{z})\in\mbox{\itshape FL}(\sigma)~\mbox{\itshape
s.t.}
\\[-0.551ex]
\varphi(\bar{x},\bar{a})~\mbox{\itshape is an atom
of\/}\,~T^\ast\!\!,~\mbox{\itshape and\/}~
T\vdash\phi(\bar{x})\iff(\exists\bar{z})[\varphi(\bar{x},\bar{z}){\,\&\,}\theta(\bar{z})].
\end{array}
\eqno(3.1)
$$%

First, we suppose that formula $\phi(\bar{x})$ is an atom of theory $T$.
Consider a tuple $\bar{c}$ in $\mathfrak{N}$ such that
$\mathfrak{N}\models\phi(\bar{c})$. Since model $\mathfrak{N}$ is prime, all
types realized in $\mathfrak{N}$ are principal. From this, it follows that
there is a formula $\varphi(\bar{x},\bar{z})$, which is an atom of theory
$T$, and, in $\mathfrak{N}$, we have $\varphi(\bar{c},\bar{a})$. Moreover,
$\varphi(\bar{c},\bar{a}){\,\&\,}\theta(\bar{a})$ holds because, by
assumption, we have $\mathfrak{N}\models\theta(\bar{a})$. Thus, formula
$\varphi'(\bar{x},\bar{z})=\varphi(\bar{x},\bar{z}){\,\&\,}\theta(\bar{z})$
is satisfied in $\mathfrak{N}$ on the tuple $\xi=(\bar{c},\bar{a})$.
Therefore, the formula $\varphi'(\bar{x},\bar{z})$ is equivalent in $T$ to
the formula $\varphi(\bar{x},\bar{z})$ since the latter is an atom of theory
$T$. As a result, we obtain that, in theory $T$, it is provable
$\phi(\bar{x})\sim(\exists\bar{z})[\varphi(\bar{x},\bar{z}){\,\&\,}\theta(\bar{z})]$.

Now, we suppose that $\varphi(\bar{x},\bar{a})$ is an atom of theory
$T^\ast$. Consider the formula
$$
\phi(\bar{x})=(\exists\bar{z})[\varphi(\bar{x},\bar{z}){\,\&\,}\theta(\bar{z})].
\eqno(3.2)
$$
Our goal is to show that this formula is an atom of the theory $T$. For this,
it is sufficient to show that, for arbitrary tuples $\bar{c}_1$ and
$\bar{c}_2$ in $\mathfrak{N}$ of appropriate lengths, it follows from
$\mathfrak{N}\models\phi(\bar{c}_1)$ and $\mathfrak{N}\models\phi(\bar{c}_2)$
that there is an automorphism $\mu$ of the model $\mathfrak{N}$ such that
$\mu(\bar{c}_1)=\bar{c}_2$. Since $\mathfrak{N}\models\phi(\bar{c}_1)$, the
right-hand side expression in (3.2) ensures that there is a tuple $\bar{e}_1$
in $\mathfrak{N}$ such that
$\mathfrak{N}\models\varphi(\bar{c}_1,\bar{e}_1){\,\&\,}\theta(\bar{e}_1)$.
Similarly, by virtue of $\mathfrak{N}\models\phi(\bar{c}_2)$, expression
(3.2) provides that there is a tuple $\bar{e}_2$ in $\mathfrak{N}$ such that
$\mathfrak{N}\models\varphi(\bar{c}_2,\bar{e}_2){\,\&\,}\theta(\bar{e}_2)$.
Since the formula $\theta(\bar{z})$ is an atom of theory $T$, and, in the
model $\mathfrak{N}$ both $\theta(\bar{a})$ and $\theta(\bar{e}_1)$ hold,
there must be an automorphism $\mu_1:\mathfrak{N}\to\mathfrak{N}$ sending
$\bar{e}_1$ to $\bar{a}$. Denote $\mu_1(\bar{c}_1)$ by
$\bar{c}^{\,\prime}_1$. Similarly, both $\theta(\bar{a})$ and
$\theta(\bar{e}_2)$ are satisfied in the model $\mathfrak{N}$, so there must
be an automorphism $\mu_2:\mathfrak{N}\to\mathfrak{N}$ sending $\bar{e}_2$ to
$\bar{a}$. Denote $\mu_2(\bar{c}_2)$ by $\bar{c}^{\,\prime}_2$. In view of
the properties of automorphisms $\mu_1$ and $\mu_2$, we have
$\mathfrak{N}\models\varphi(\bar{c}^{\,\prime}_1,\bar{a}){\,\&\,}\theta(\bar{a})$
and
$\mathfrak{N}\models\varphi(\bar{c}^{\,\prime}_2,\bar{a}){\,\&\,}\theta(\bar{a})$.
By assumption, formula $\varphi(\bar{x},\bar{a})$ is an atom of theory
$T^\ast$. Therefore, there is an automorphism
$\mu_0:\mathfrak{N}\to\mathfrak{N}$ that is identical on tuple $\bar{a}$ and
maps tuple $\bar{c}^{\,\prime}_1$ into tuple $\bar{c}^{\,\prime}_2$. It
remains to verify that the composition of automorphisms
$\mu=\mu^{-1}_2\mu_0\mu_1$ ensures the relations $\mu(\bar{c}_1)=\bar{c}_2$
and $\mu(\bar{a})=\bar{a}$. This shows that the formula (3.2) is an atom of
theory $T$.

Thereby, the relation (3.1) indeed takes place, thus allowing us to complete
proof of the part (c)$\Rightarrow$(a). Based on the presentation (3.1), it is
possible to organize an effective enumeration of the set $\mathcal{A}$ of
atoms of theory $T=\operatorname{Th}(\mathfrak{N})$ that is exactly what is
required.

Theorem 3.5 is proved.

%================================================================================
\section{Compact binary trees and the canonical construction}
%================================================================================

Definition of the notion of a compact binary tree can be found in
[9,\,Sec,\,2.1]. In this work, we use for such trees a more specialized term
{\itshape compact binary trees} instead.

A {\itshape full compact binary tree} is a partially ordered set
$\mathcal{D}_0=\langle \mathbb{N},\preccurlyeq\rangle$ of the form shown in
Fig. 4.1(a). In particular, $1\preccurlyeq8$, $6\preccurlyeq6$,
$\mbox{\footnotesize\raisebox{-0.39ex}{$\urcorner\,$}}(6\preccurlyeq9)$, and
$\mbox{\footnotesize\raisebox{-0.39ex}{$\urcorner\,$}}(9\preccurlyeq6)$ is
satisfied. There are two natural operations within the tree, $L(n)=2n+1$ is
the {\itshape left successor}, and $R(n)=2n+2$ is the {\itshape right
successor} of an element $n\in\mathbb{N}$. A nonempty set
$\mathcal{D}\subseteq\mathbb{N}$ is said to be a {\itshape compact binary
tree} whenever the following conditions are satisfied: $m\preccurlyeq
n{\,\&\,} n\in\mathcal{D}\Rightarrow m\in\mathcal{D}$, and
$L(n)\in\mathcal{D}\Leftrightarrow R(n)\in\mathcal{D}$, for all
$m,n\in\mathbb{N}$. An element $n$ in a compact binary tree $\mathcal{D}$
such that $L(n)\not\in\mathcal{D}$ is said to be a {\itshape dead end} of the
tree $\mathcal{D}$. The set of all dead-end elements in a tree $\mathcal{D}$
is denoted by $\operatorname{Dend}(\mathcal{D})$. A tree is called {\itshape
atomic} if, above each of its elements, there is at least one dead-end
element.

A few examples of compact binary trees are given in Fig.\,4.1(a,b,c).

\vskip0.751ex
\centerline{\includegraphics[scale=0.1198]{Fig2}}%\Figura(1.100)<fig2>[c]
\vskip0.251ex
\centerline{Fig.\,4.1. Examples of compact binary trees}
\vskip1.0ex

A natural operation of the {\itshape direct sum} of two given trees
$\mathcal{D}_1$ and $\mathcal{D}_2$ is available. The tree
$\mathcal{D}_1\oplus\mathcal{D}_2$ is obtained by attaching isomorphic copies
of the trees $\mathcal{D}_1$ and $\mathcal{D}_2$ to the two dead-end elements
in the three-element tree given in Fig.\,4.1(b) as it is schematically shown
in Fig.\,4.2.

\vskip0.551ex%
\centerline{\includegraphics[scale=0.1198]{Fig3}}%\Figura(1.100)<fig3>[c]
\vskip0.251ex%
\centerline{Fig.\,4.2. Scheme of the operations $\oplus$ for compact binary trees}
\vskip1.05751ex%

A set $\pi\subseteq\mathcal{D}$ is called a {\itshape chain} in the tree
$\mathcal{D}$, if $m,n\in\pi\Rightarrow m\preccurlyeq n \lor n\preccurlyeq m$
and $m\preccurlyeq n{\,\&\,} n\in\pi \Rightarrow m\in \pi$, for all
$m,n\in\mathbb{N}$. If $\mathcal{D}$ is a compact binary tree, we denote by
$\varPi(\mathcal{D})$ the set of all {\itshape maximal chains}, while
$\varPi^{fi\!n}(\mathcal{D})$ is the set of all {\itshape maximal finite
chains} in the tree $\mathcal{D}$. A tree $\mathcal{D}$ is said to be
{\itshape superatomic}, if the set $\varPi(\mathcal{D})$ is at most
countable.

See [9,\,Sec.\,2.1] for definitions concerning the trees in detail.

{\bf Lemma 4.1.} {\itshape There is a tree $\mathcal{D}^\star$ which is a
superatomic (the more, atomic), computably enumerable, non-computable compact
binary tree for which both families $\varPi^{fin}(\mathcal{D}^\star)$ and
$\varPi(\mathcal{D}^\star)$ are computable}.

{\sc Proof.} Let $\mathcal{D}$ be the tree shown in Fig.\,4.1(c). Since
$\mathcal{D}$ is computable, the set $\operatorname{Dend}(\mathcal{D})$ is
also computable. Moreover, $\operatorname{Dend}(\mathcal{D})$ is infinite,
thus there is a computable bijective mapping
$f:\mathbb{N}\to\operatorname{Dend}(\mathcal{D})$. Let $K\subseteq\mathbb{N}$
be a computably enumerable non-computable set. Let
$\mathcal{D}^\star=\mathcal{D}\cup\{L(f(i))\mid i\in K\}\cup\{R(f(i))\mid
i\in K\}$. It is simple to check that the set $\mathcal{D}^\star$ is an
atomic computably enumerable compact binary tree. Moreover, both families
$\varPi(\mathcal{D}^\star)$ and $\varPi^{fin}(\mathcal{D}^\star)$ are
computable. In particular, $\varPi(\mathcal{D}^\star)$ is countable ensuring
that the tree $\mathcal{D}^\star$ is superatomic. By construction,
reducibility $n\in K\Leftrightarrow L\bigl(f(n)\bigr)\in\mathcal{D}^\star$
takes place, thus the tree $\mathcal{D}^\star$ is not computable.

Lemma 4.1 is proved. \hfill\mbox{$\Box$}

{\bf Lemma 4.2}. {\itshape There is an effective operator sending an
arbitrary constructive linear ordering $(\mathcal{L},\nu)$ into a tree
$\mathcal{D}(\mathcal{L},\nu)$ such that the following claims hold}:

(a) {\itshape for any constructive linear ordering $(\mathcal{L},\nu)$, the
tree $\mathcal{D}(\mathcal{L},\nu)$ is computable},

(b) {\itshape the tree $\mathcal{D}(\mathcal{L},\nu)$ is superatomic if and
only if $\mathcal{L}$ is well ordered},

(c) {\itshape if $\mathcal{L}$ is well ordered, the family of chains
$\varPi(\mathcal{D}(\mathcal{L},\nu))$ is computable}.

{\sc Proof.} See [9,\,Lem.\,2.2.1]. \hfill\mbox{$\Box$}

By $\mathcal{D}_n$, we denote the closure of the set $W_n$ up to a compact
binary tree, while $\mathcal{D}^X_n$ is the closure of the set $W^X_n$ up to
a compact binary tree. It can be checked that the tree $\mathcal{D}_n$ is
computably enumerable, while the tree $\mathcal{D}^X_n$ is computably
enumerable with oracle $X$. Moreover, each c.e. tree is presented in the
sequence $\mathcal{D}_n$, $n\in\mathbb{N}$, and each c.e. tree in computation
with oracle $X$ is presented in the sequence $\mathcal{D}^X_n$,
$n\in\mathbb{N}$. The number $n$ is considered as a c.e. index for the tree
$\mathcal{D}_n$, and $n$ is considered as a c.e. index for the tree
$\mathcal{D}^X_n$ considered in computability with an oracle $X$.

We denote by $\mathfrak{P}_n$ the truth-table condition with the G\"odel
number $n$, cf [9,\,Sec.\,3.1]. We write $A\models\mathfrak{P}_n$ to indicate
that $\mathfrak{P}_n$ is satisfied in the set $A\subseteq\mathbb{N}$. The set
of the form
$$
\varOmega(m)=\{A\subseteq\mathbb{N}\mid(\forall i\in
W_m)\,A\models\mathfrak{P}_i\},
\eqno(4.1)
$$
is said to be the {\itshape parametric Stone space} with an index $m$, cf.
definition of $\,\mathcal{R}_m$ in [9,\,Sec.\,3.1].

Main statement on the {\itshape canonical construction} of finitely
axiomatizable theories can be found in [9]. Its part involved in construction
of this work states the following:

{\bf Theorem 4.3.} [9,\,Th.\,3.1.1] {\itshape Effectively in a pair of
integers $(m,s)$ and a finite rich signature $\sigma$, it is possible to
construct a finitely axiomatizable theory $F=\mbox{${\mathbb
F}$\rule{-0.07ex}{0pt}\scriptsize${\mathbb C}$}(m,s,\sigma)$ of signature
$\sigma$ together with an effective sequence $\theta_n$, $n\in \mathbb{N}$,
of sentences of the signature $\sigma$ such that the family of extensions of
$F$ defined by
$$
F[A]=F\cup\{\theta_i|i\in
A\}\cup\{\mbox{\footnotesize\raisebox{-0.39ex}{$\urcorner\,$}}\theta_j|j\in
\mathbb{N}{{\!\smallsetminus\!}} A\},~A\subseteq\mathbb{N}, \eqno(4.2)
$$
satisfies the following properties}:

\vskip0.15ex
\begin{list}{~}{\topsep0ex\partopsep0ex\parskip0ex\parsep0pt\itemsep0ex\leftmargin3.8ex\labelwidth2.8ex\labelsep0.93ex}\itemsep=0.12ex%
\item[\footnotesize\ttfamily(A)\,]
{\itshape for any $A\subseteq\mathbb{N}$, the theory $F[A]$ is either
complete or contradictory};
\item[\footnotesize\ttfamily(B)\,]
{\itshape the theory $F[A]$, $A\subseteq\mathbb{N}$, is consistent if and
only if $A\in\varOmega(m)$};
\item[\footnotesize\ttfamily(C)\,]
{\itshape for an arbitrary $A\in\varOmega(m)$, theory $F[A]$ has a prime
model if and only if the tree $\mathcal{D}_s^A$ is atomic; moreover},
\\[0.351ex]
{\footnotesize$\bullet$} {\itshape a prime model of the theory $F[A]$, if it
exists, is strongly constructivizable if and only if the set $A$ is
computable and the family of chains $\varPi^{fi\!n}(\mathcal{D}_s^A)$ is
computable},
\\[0.351ex]
{\footnotesize$\bullet$} {\itshape a prime model of the theory $F[A]$, if it
exists and is strongly constructivizable, has algorithmic dimension $1$ if
and only if the tree $\mathcal{D}_s^A$ is computable; otherwise, the model
has algorithmic dimension $\omega$}.
\item[\footnotesize\ttfamily(D)\,]
{\itshape for an arbitrary $A\in\varOmega(m)$, theory $F[A]$ is
$\omega$-stable if and only if the tree $\mathcal{D}_s^A$ is superatomic}.

\end{list}

Notice that, Part (A) and Part (B) of Theorem 4.3 state that the collection
$F[A]$, $A\in\varOmega(m)$, represents exactly the set of all possible
complete extensions of the theory
$F=\mbox{$\mathbb{F}$\rule{-0.07ex}{0pt}\scriptsize$\mathbb{C}$}(m,s,\sigma)$.

%===========================================================================
\section{The sentence algebra of the class of prime models with infinite algorithmic dimensions having $\omega$-stable theories}
%===========================================================================

We fix a finite rich signature $\sigma$. We denote by $P(\sigma)$ the class
of all prime models of signature $\sigma$, by $W(\sigma)$ the class of all
models of signature $\sigma$ with $\omega$-stable theories, and by
$M^{\,\,\omega}_{s.c.}(\sigma)$, the class of all strongly constructivizable
models of signature $\sigma$ having infinite algorithmic dimensions.
Intersection of these classes $PW^{\,\,\omega}_{\!s.c.}=P(\sigma)\cap
W(\sigma)\cap M^{\,\,\omega}_{s.c.}(\sigma)$ is the main object of our
further study. We use a fixed G\"odel numbering $\varPhi_i$,
$i\in\mathbb{N}$, for the set of all sentences of signature $\sigma$, and
$\varphi_i(\bar{x}_i)$, $i\in\mathbb{N}$, for the set of all formulas of
signature $\sigma$.

{\bf Theorem 5.1.} {\itshape The following assertions hold}:

(a) {\itshape $\bigl(\mathcal{L}(PW^{\,\,\omega}_{\!s.c.}),\gamma\bigr)$ is a
Boolean $\Sigma^1_1$-algebra, where $\gamma$ is a G\"odel numbering of the
set of sentences of signature $\sigma$},

(b) {\itshape computable ultrafilters of
$\bigl(\mathcal{L}(PW^{\,\,\omega}_{\!s.c.}),\gamma\bigr)$ form a dense set
among arbitrary ultrafilters in the algebra},

(c) {\itshape for an arbitrary numerated Boolean $\Sigma^1_1$-algebra
$(\mathcal{B},\nu)$ whose computable ultrafilters form a dense set among
arbitrary ultrafilters, there is a sentence $\varTheta$ of signature $\sigma$
such that $(\mathcal{B},\nu)\cong(\mathcal{L}
\bigl(\operatorname{Th}(\operatorname{Mod}(\varTheta)\cap
PW^{\,\,\omega}_{\!s.c.})\bigr),\gamma)$}.

(d) {\itshape for an arbitrary Boolean $\Sigma^1_1$-algebra $\mathcal{B}$,
there is a sentence $\varTheta$ of signature $\sigma$ such that
$\mathcal{B}\cong\mathcal{L}
\bigl(\operatorname{Th}(\operatorname{Mod}(\varTheta)\cap
PW^{\,\,\omega}_{\!s.c.})\bigr)$}.

{\sc Proof.} (a) By the Goncharov-Nurtazin-Harrington criterion (Theorem
3.4), a prime model $\mathfrak{N}$ of a complete decidable theory $T$ is
strongly constructivizable if and only if the family of principal types
realized in $\mathfrak{N}$ is computable. In addition, by a corollary of the
Nurtazin criterion for autostability (Theorem 3.5) the strongly
constructivizable prime model $\mathfrak{N}$ is autostable with respect to
strong constructivizations if and only if the family $\mathcal{F}$ of
formulas presenting atoms in the Tarski-Lindenbaum algebras $L_n(T)$,
$n\in\mathbb{N}$, is computably enumerable. Otherwise, when the set
$\mathcal{F}$ is not computably enumerable, by the Nurtazin criterion for
autostability (Theorem 3.5), we have $\dim_{s.c.}(\mathfrak{N})=\omega$. From
this, we obtain that, a sentence $\varPsi$ of signature $\sigma$ has a model
in the class $PW^{\,\,\omega}_{\!s.c.}$ if and only if there are natural
parameters $m$ and $n$ such that the following collection of conditions is
satisfied

\vskip1.01ex
{\renewcommand{\baselinestretch}{1.25}\normalsize\tabcolsep=0.621ex\hskip-1.251ex%
\begin{tabular}{cll}
%---------------------------------------------------------------------------
{\footnotesize\ttfamily(a)} & $W_m\cap W_n=\varnothing$ ${\,\&\,}$ $W_m\cup W_n=\mathbb{N}$, & $\forall\,{\,\&\,}\forall\exists$\\%
%---------------------------------------------------------------------------
{\footnotesize\ttfamily(b)} & $T=\{\varPhi_i\mid i\in W_m\}$ is a complete theory, & $\forall\exists$\\%
%---------------------------------------------------------------------------
{\footnotesize\ttfamily(c)} & $\varPsi\in T$, & $\exists$\\%
%---------------------------------------------------------------------------
{\footnotesize\ttfamily(d)} & $(\forall\varphi(\bar{x}))\,\bigl[\varphi(\bar{x})$ consistent\,$\Rightarrow$\,$\exists\theta(\bar{x})\,[\,(\,\theta(\bar{x})\rightarrow\varphi(\bar{x})\,){\,\&\,}\theta(\bar{x})$ is atomic\,$]\,\bigr]$, & $\forall\exists\forall$\\[0.251ex]%
%---------------------------------------------------------------------------
{\footnotesize\ttfamily(e)} & $(\forall q)\bigl[(\forall i\in W_q)\,\varphi_i(\bar{x}_i)$ is atomic\,\,$\Rightarrow$\,$(\exists j\not\in W_q)\bigl(\varphi_j(\bar{x}_j)$ is atomic\,$\bigr)\bigr]$, & $\forall\exists\forall$\\[0.251ex]%
%---------------------------------------------------------------------------
{\footnotesize\ttfamily(f)} & $(\forall$\,countable\,$\mathfrak{N}\in\operatorname{Mod}(T))(\forall n\!<\!\omega)\bigl[\mathcal{L}_n(\operatorname{Th}(\mathfrak{N},|\mathfrak{N}|))$ is superatomic $\bigr]$.~& $\forall^1$%
%---------------------------------------------------------------------------
\end{tabular}
\vskip1.01ex
}%end\baselinestretch

\noindent
Thus, we obtain a prefix $\forall^1$ for the condition as a whole. Finally,
sentences $\varPhi$ and $\varPsi$ are equivalent on the class
$PW^{\,\,\omega}_{\!s.c.}$ if and only if
$(\varPhi{\,\&\,}\mbox{\footnotesize\raisebox{-0.39ex}{$\urcorner\,$}}\varPsi)\lor(\varPsi{\,\&\,}\mbox{\footnotesize\raisebox{-0.39ex}{$\urcorner\,$}}\varPhi)$
does not have a model in this class. This gives the required prefix
$\exists^1$ for (a).

(b) Let $T$ be an arbitrary complete theory extending
$\operatorname{Th}(PW^{\,\,\omega}_{\!s.c.})$, and $\varPsi$ be a sentence
provable in $T$. Obviously, $\varPsi$ has a model $\mathfrak{N}\in
PW^{\,\,\omega}_{\!s.c.}$. From this, we have that complete decidable theory
$T'=\operatorname{Th}(\mathfrak{N})$ presenting a computable ultrafilter in
$\operatorname{St}(\operatorname{Th}(PW^{\,\,\omega}_{\!s.c.}))$ is found in
the neighborhood $\varPsi$ of the ultrafilter $T$ in this Stone space. This
gives the required density property posed in (b).

The proof of Part (c) is given in the forthcoming text. As for Part (d), it
is a simple consequence of Part (c) and Lemma 1.1 with an $m$-complete in
$\Sigma^1_1$ set $X$.

We begin the proof of Part (c) of Theorem 5.1.

We use the following $m$-complete in the class $\Pi^1_1$ set
$$
A^1=\{n\in\mathbb{N}\mid\mathcal{L}_n\mbox{ \itshape is a well ordering}\,\},
\eqno(5.1)
$$
where $\mathcal{L}_n=(L_n,\nu_n)$, $n\in\mathbb{N}$, is an effective sequence
of constructive linear orderings, cf. Lemma 0.1. Therefore, its complement
$E^1=\mathbb{N}{\!\smallsetminus\!} A_1$ is an $m$-complete in $\Sigma^1_1$
set.

Given a numerated Boolean $\Sigma^1_1$-algebra $(\mathcal{B},\nu)$ that
satisfies
$$
\mbox{\itshape computable ultrafilters of}\ (\mathcal{B},\nu)\ \mbox{\itshape
form a dense set in}\ \operatorname{St}(\mathcal{B}). \eqno(5.2)
$$%

It is possible to assume, that $\mathcal{B}$ is a nontrivial algebra. By
definition, signature operations $\cup$, $\cap$ and $-$ in $\mathcal{B}$ are
presentable by computable functions on $\nu$-numbers, while the equality is a
$\Sigma^1_1$-relation in the numeration $\nu$, i.e.,
$\nu(x)\!=\!\nu(y)\Leftrightarrow H(x,y)$ is satisfied for a binary relation
$H\in\Sigma^1_1$. Respectively, the inequality relation
$H'(x,y)=_{dfn}(\nu(x)\ne\nu(y))$ is $\Pi^1_1$. Therefore, there is a unary
relation $H^\ast$ in $\Pi^1_1$ such that, for any finite tuple of zeros and
ones $\alpha\!=\!\langle\alpha_0,\alpha_1,\ldots,\alpha_n\rangle$, we have
$$
\nu(0)^{\alpha_0}\!\cap\nu(1)^{\alpha_1}\!\cap\ldots\cap\nu(n)^{\alpha_n}\!\!\ne\!\mathbf0\
\Leftrightarrow\ \langle\alpha_0,\!\alpha_1,\ldots\!,\!\alpha_n\rangle\in
H^\ast,\ \ H^\ast\in\Pi^1_1.
$$%

Since $H^\ast$ is $\Pi^1_1$, it is $m$-reducible to $A^1$, i.e., there is a
general computable function $f(x)$ such that for arbitrary tuples $\alpha\in
2^{<\omega}$,
$\alpha=\raisebox{0.25ex}{\footnotesize$\langle$}\alpha_0,...,\alpha_n\raisebox{0.25ex}{\footnotesize$\rangle$}$,
we have
$$
\nu(0)^{\alpha_0}\!\cap\nu(1)^{\alpha_1}\!\cap\ldots\cap\nu(n)^{\alpha_n}
\!\!\ne\!\mathbf0\ \Leftrightarrow\
\mathcal{L}_{f(\langle\alpha_0,\alpha_1,...,\alpha_n\rangle)}~\mbox{\itshape
is well ordering}.
\eqno(5.3)
$$%

Let us check that the object we built above represents some kind of a tree.

{\bf Lemma 5.2.} {\itshape The following assertions are true}:

(a) $f(\varnothing)\in A^1$,

(b) {\itshape for any $\alpha$ in $2^{<\omega}$, $f(\alpha)\in A^1$
$\Leftrightarrow$ $f(\alpha0)\in A^1$ or $f(\alpha1)\in A^1$},

(c) {\itshape for any $\alpha$ in $2^{<\omega}$, $f(\alpha)\in E^1$
$\Leftrightarrow$ $f(\alpha0)\in E^1$ and $f(\alpha1)\in E^1$}.

{\sc Proof.} Part (a) is a consequence of the fact that algebra $\mathcal{B}$
is nontrivial. Part (b) follows from the definition of the function $f(x)$
and relation $H^\ast(x)$, representing an ideal in the free Boolean algebra,
while (c) is a corollary from (b). \hfill\mbox{$\Box$}

Now, our goal is to choose a pair $(m,s)$ of integer parameters to be
considered with the canonical construction, cf. Theorem 4.3.

{\itshape Choice of} $m$. We choose $m$ such that
$\varOmega(m)=\mathcal{P}(\mathbb{N})$, cf. (4.1). For this, it is enough to
get $m$ such that $W_m=\varnothing$.

{\itshape Choice of} $s$. For this purpose, we describe a computable
functional $\mathscr{F}$ from $\mathcal{P}(\mathbb{N})$ to
$\mathcal{P}(\mathbb{N})$, actually, yielding compact binary trees. For an
arbitrary $A\subseteq\mathbb{N}$, witness of $\mathscr{F}$ with input $A$ is
found via the function $f(x)$ in (5.3) by scheme
$$
\renewcommand{\arraystretch}{1.3}\arraycolsep=0pt\begin{array}[t]{lllll}
\mathscr{F}:A\mapsto\operatorname{Tree}(L^\ast,\nu^\ast)\mapsto\operatorname{Tree}(L^\ast,\nu^\ast)\oplus\mathcal{D}^\star=\mathscr{F}(A)=\mathcal{D}^A_s,~~\mbox{\itshape
where}
\\[0.551ex]
\mbox{\footnotesize\ttfamily(a)}~\,(L^\ast,\nu^\ast)=\mathcal{L}_{f(\varnothing)}+\mathcal{L}_{f(\langle\alpha_0\rangle)}+
\ldots + \mathcal{L}_{f(\langle\alpha_0,...,\alpha_n\rangle)}+ \ldots\ ,
\\
\mbox{\footnotesize\ttfamily(b)}~\,\alpha_k=\begin{cases}1, & \mbox{\itshape
if }k\in A,\\ 0, & \mbox{\itshape if }k \not\in A,
\end{cases}~~\mbox{\itshape for all}~\,k\in\mathbb{N};
\\
\mbox{\footnotesize\ttfamily(c)}~\,s~\mbox{\itshape is an index of the
algorithm for}~A\mapsto\mathscr{F}(A)~\mbox{\itshape with an oracle}~A.
\end{array}
\eqno(5.4)
$$
Here, $\mathcal{D}^\star$ is a fixed superatomic computably enumerable
non-computable tree with computable $\varPi^{fin}(\mathcal{D})$, cf. Lemma
4.1, while $(L,\nu)\mapsto\operatorname{Tree}(L,\nu)$ is an effective
transformation from linear orderings to binary trees, cf. Lemma 4.2. The
transformation $A\mapsto\mathscr{F}(A)$, $A\subseteq\mathbb{N}$, is realized
via Turing's computation by an algorithm $\mathcal{M}$ with an oracle $A$. We
put $s$ to be a G\"odel number of the algorithm $\mathcal{M}$, cf. (5.4)(c).

Choice of the pair of parameters $(m,s)$ is finished.

Let us study main properties of the transformation
$\mathscr{F}:A\mapsto\mathcal{D}^A_s$.

{\bf Lemma 5.3.} {\itshape The following assertions hold}:

(a) {\itshape For any $A\subseteq\mathbb{N}$, $\mathcal{D}^A_s$ is a tree}.

(b) {\itshape For any computable set $A\subseteq\mathbb{N}$,
$\mathcal{D}^A_s$ is a computable enumerable non-computable tree}.

(c) {\itshape For any computable set $A\subseteq\mathbb{N}$, the family
$\varPi^{fin}(\mathcal{D}^A_s)$ is computable}.

(d) {\itshape For any computable set $A\subseteq\mathbb{N}$, tree
$\mathcal{D}^A_s$ is superatomic $\Leftrightarrow$ linear order $L^\ast$ in
$(5.4)(a)$ is well ordered}.

{\sc Proof.} Given a set $A\subseteq\mathbb{N}$. Let $(L^\ast,\nu^\ast)$ be a
linear order built by rule (5.4)(a) with using function $f(x)$ in (5.3). By
construction, $(L^\ast,\nu^\ast)$ is a constructive linear order whenever $A$
is a computable set.

We turn to prove separate parts of Lemma 5.3.

(a) Use Lemma 4.2 together with Lemma 4.1 describing properties of the tree
$\mathcal{D}^\star$ in (5.4). Moreover, some elementary properties of the
operation $\otimes$ for trees have to be used.

(b) Suppose that $A$ is computable. Then, $(L^\ast,\nu^\ast)$ is a
constructive linear ordering. By Lemma 4.2(a), the tree
$\operatorname{Tree}(L^\ast,\nu^\ast)$ is computable, however, by Lemma 4.1,
another tree $\mathcal{D}^\star$ is a computably enumerable non-computable
tree. From this, we obtain that their sum
$\operatorname{Tree}(L^\ast,\nu^\ast)\oplus\mathcal{D}^\star$ is a computably
enumerable non-computable tree.

(c) Suppose that $A$ is computable. Then, $(L^\ast,\nu^\ast)$ is a
constructive linear ordering. By Lemma 4.2(a), tree
$\operatorname{Tree}(L^\ast,\nu^\ast)$ is computable, thus ensuring the
family $\varPi^{fin}\bigl(\operatorname{Tree}(L^\ast,\nu^\ast)\bigr)$ to be
computable. By Lemma 4.1, another family $\varPi^{fin}(\mathcal{D}^\star)$ is
also computable. Based on elementary properties of the operation $\otimes$,
we obtain that the family
$\varPi^{fin}\bigl(\operatorname{Tree}(L^\ast,\nu^\ast)\oplus\mathcal{D}^\star\bigr)$
is computable.

(d) Suppose that $A$ is computable. Then, $(L^\ast,\nu^\ast)$ is a
constructive linear ordering. In the case when $L^\ast$ is well ordering, by
Lemma 4.2(b), the tree $\operatorname{Tree}(L^\ast,\nu^\ast)$ is superatomic
while by Lemma 4.1 the tree $\mathcal{D}^\star$ is also superatomic.
Therefore, their sum
$\operatorname{Tree}(L^\ast,\nu^\ast)\otimes\mathcal{D}^\star$ is
superatomic. In the other case, when the order $L^\ast$ is not well-ordering,
by Lemma 4.2(b), the tree $\operatorname{Tree}(L^\ast,\nu^\ast)$ is not
superatomic, thus, the whole tree
$\operatorname{Tree}(L^\ast,\nu^\ast)\otimes\mathcal{D}^\star$ is not
superatomic as well.

Lemma 5.3 is proved. \hfill\mbox{$\Box$}

Now we turn to the final part of the proof.

In accordance with demands in Part (c) of Theorem 5.1, we have to point out a
sentence $\varTheta$ of a given finite rich signature $\sigma$. For this, we
use the canonical construction, cf. Theorem 4.3. Let us apply Theorem 4.3 to
the pair $(m,s)$ specifying also signature $\sigma$ for the target theory. As
a result, we obtain an effective sequence $\theta_i$, $i\in\mathbb{N}$, of
sentences of signature $\sigma$ together with a finitely axiomatizable theory
$F=\mbox{$\mathbb{F}$\rule{-0.07ex}{0pt}\scriptsize$\mathbb{C}$}(m,s,\sigma)$
of signature $\sigma$. We put $\varTheta$ to be the sentence that is a
conjunction of axioms of the theory
$F=\mbox{$\mathbb{F}$\rule{-0.07ex}{0pt}\scriptsize$\mathbb{C}$}(m,s,\sigma)$.

Notice that, Part (A) together with Part (B) of Theorem 4.3 ensure that, for
an arbitrary set $A\in\varOmega(m)$ and corresponding sequence
$\alpha\in2^{<\omega}$ linked with $A$ via the rule (5.4)(b), it is satisfied
$$
F[A]\vdash\theta^{\alpha_k}_k,~\mbox{\itshape for all}~k\in\mathbb{N}.
\eqno(5.5)
$$%

Now, we are going to check that $\varTheta$ satisfies all requirements in
Theorem 5.1(c).

Consider an arbitrary finite tuple of zeros and ones
$\alpha=\raisebox{0.25ex}{\footnotesize$\langle$}\alpha_0,...,\alpha_k\raisebox{0.25ex}{\footnotesize$\rangle$}$.
Let us construct an intersection of elements in $\mathcal{B}$ by the rule
$$
b_\alpha=\nu(0)^{\alpha_0}\cap\nu(1)^{\alpha_1}\cap...\cap\nu(k)^{\alpha_k}.
\eqno(5.6)
$$
We also consider a conjunction of corresponding sentences $\theta_i$
$i\in\mathbb{N}$, by the rule
$$
\beta_\alpha=\theta_0^{\alpha_0}{\,\&\,}\theta_1^{\alpha_1}{\,\&\,}...{\,\&\,}\theta_k^{\alpha_k}\;.
\eqno(5.7)
$$%

The main idea behind the construction is to provide the following relation:

{\bf Lemma 5.4.} {\itshape For any tuple $\alpha\in2^{<\omega}$,
$b_\alpha\ne\mathbf0$ if and only if formula $\varTheta{\,\&\,}\beta_\alpha$
is satisfied in a model $\mathfrak{M}\in PW^{\,\,\omega}_{\!s.c.}$}.

{\sc Proof.} First, we assume that $b_\alpha\ne\mathbf0$. Since computable
ultrafilters form a dense set among arbitrary ultrafilters in the Boolean
algebra $(\mathcal{B},\nu)$, cf. (5.2), it is possible to find a sequence
$\alpha^\ast=\raisebox{0.25ex}{\footnotesize$\langle$}\alpha_i\mid
i<\omega\raisebox{0.25ex}{\footnotesize$\rangle$}$ extending $\alpha$ such
that the set $A$ linked with $\alpha^\ast$ by rule (5.4)(b) is computable,
and
$$
\nu(0)^{\alpha_0}\cap...\cap\nu(i)^{\alpha_i}\ne\mathbf0,\ \ \mbox{\itshape
for all}~\;i\in\mathbb{N}.
\eqno(5.8)
$$
By (5.3), we obtain that
$\mathcal{L}_{f(\langle\alpha_0,...,\alpha_i\rangle)}$ is a well ordered set
for all $i\in\mathbb{N}$; thus, the sequence (5.4)(a) consists of well
orderings only. Therefore, their sum $(L^\ast,\nu^\ast)$ is also a well
ordering. By Lemma 5.3(d), the tree $\mathcal{D}^A_s$ is superatomic. The
more, $\mathcal{D}^A_s$ is an atomic tree. We have, $A\in\varOmega(m)$
because $\varOmega(m)=\mathcal{P}(\mathbb{N})$ by choice of $m$. By Parts (A)
and (B) of Theorem 4.3, theory $F[A]$ is consistent and complete.
Furthermore, by Parts (C) and (D) of Theorem 4.3, theory $F[A]$ has a prime
strongly constructivizable model $\mathfrak{M}$ of infinite algorithmic
dimension whose theory is $\omega$-stable. By virtue of (5.5), we have
$F[A]\vdash\theta^{\alpha_i}_i$ for all $i\in\mathbb{N}$. From this, we
obtain $\mathfrak{M}\models\beta_\alpha$. Thereby, the formula
$\varTheta{\,\&\,}\beta_\alpha$ is satisfied in the model $\mathfrak{M}\in
PW^{\,\,\omega}_{\!s.c.}$.

Now, we assume that sentence $\varTheta{\,\&\,}\beta_\alpha$ is satisfied in
a model $\mathfrak{M}\in PW^{\,\,\omega}_{\!s.c.}$. Consider the set of
integers
$$
A=\{i\in\mathbb{N}\mid\mathfrak{M}\models\theta_i\}, \eqno(5.9)
$$
which is obviously computable. Build an infinite sequence
$\alpha^\ast=\raisebox{0.25ex}{\footnotesize$\langle$}\alpha_i\mid
i<\omega\raisebox{0.25ex}{\footnotesize$\rangle$}$ linked with $A$ by the
rule (5.4)(b). Since $A\in\varOmega(m)=\mathcal{P}(\mathbb{N})$, theory
$F[A]$ is consistent and complete. By (5.9), all axioms of the theory $F[A]$
are satisfied in the model $\mathfrak{M}$. By Part (C) of Theorem 4.3, the
tree $\mathcal{D}^A_s$ is superatomic, thus the tree
$\operatorname{Tree}(L^\ast,\nu^\ast)$ in (5.4) is superatomic as well. By
Lemma 5.3(c), linear order $\mathcal{L}^\ast$ in (5.4)(a) is well ordering.
In view of (5.3), we obtain that
$\mathcal{L}_{f(\langle\alpha_0,...,\alpha_s\rangle)}$ is a well ordered set
for all $s\in\mathbb{N}$. Applying relation (5.3) to the sequence $\alpha$,
we finally obtain $b_\alpha\ne\mathbf0$.

Lemma 5.4 is proved. \hfill\mbox{$\Box$}

Let us map elements $\nu(i)$, $i\in\mathbb{N}$, of Boolean algebra
$\mathcal{B}$ to sentences $\theta_i$, $i\in\mathbb{N}$, of signature
$\sigma$ by the rule $\lambda^\ast(\nu(k))=\theta_k$, $k\in\mathbb{N}$. By
Lemma 5.4 together with Theorem 2.1, it is possible to extend this mapping up
to a computable isomorphism
$\lambda:(\mathcal{B},\nu)\to\bigl(\mathcal{L}\bigl(\operatorname{Th}\bigl(\operatorname{Mod}(\varTheta)\cap
PW^{\,\,\omega}_{\!s.c.}\bigl)\bigl),\gamma\bigr)$ that is exactly what is
required.

Thereby, Part (c) of Theorem 5.1 is completely proved.

Theorem 5.1 is proved. \hfill\mbox{$\Box$}

%=================================================================================
\section{Conclusion}
%=================================================================================

Theorem 5.1 characterizes the Tarski-Lindenbaum algebra of the class of all
prime strongly constructivizable models of infinite algorithmic dimensions
having $\omega$-stable theories. For comparison, the work [11] have been
devoted to a similar problem for the class $P_{\!s.c.}$ of all strongly
constructivizable prime models, while another work [13] concerned the same
problem for the class $P^{1}_{\!s.c.}$ of all prime strongly
constructivizable models of algorithmic dimension one.

Let us turn to a few open questions concerning statement of Theorem 5.1. We
write $\mbox{\itshape R\rule{-0.11ex}{0pt}M}(T)$ for Morley Rank of a
complete theory $T$. We use notation
$R^{\,\mbox{\tiny\(\leqslant\)}\!\alpha}(\sigma)$ for the class of models
$\mathfrak{M}$ of signature $\sigma$ satisfying $\mbox{\itshape
R\rule{-0.11ex}{0pt}M}(\operatorname{Th}(\mathfrak{M}))\leqslant\alpha$.
Similar notation $R^{\,\mbox{\tiny\(\geqslant\)}\!\alpha}(\sigma)$ is also
used.

By $\alpha$, we denote an arbitrary constructive ordinal.

{\bf Question 6.1.} {\itshape Find a characterization of the
Tarski-Lindenbaum algebra of the class of models
$PW^{\,\,\omega}_{\!s.c.}\!\cap R^{\,\mbox{\tiny\(\leqslant\)}\!\alpha}$.}

{\bf Question 6.2.} {\itshape Find a characterization of the
Tarski-Lindenbaum algebra of the class of models
$PW^{\,\,\omega}_{\!s.c.}\!\cap R^{\,\mbox{\tiny\(\geqslant\)}\!\alpha}$.}

{\bf Hypothesis 6.3.} {\itshape For any constructive ordinal $\alpha$, the
Tarski-Lindenbaum algebra of the class of models
$PW^{\,\,\omega}_{\!s.c.}\!\cap R^{\,\mbox{\tiny\(\geqslant\)}\!\alpha}$ is
characterized by a statement analogous to that presented in Theorem 5.1}.

Notice that, the canonical construction is actually applicable to the cases
(involved in the questions we formulated above) with an arbitrary ordinal
$\alpha$ satisfying $15\leqslant\alpha<\omega^{_{CK}}_1$, cf.
[9,\,Th.\,3.1.1].

\bigskip

%======================================================================================
\begin{thebibliography}{16} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).
%======================================================================================

\bibitem{1}
Goncharov S.S., Ershov Yu.L. {\it Constructive models}, Siberian School of
Algebra Logic, New York, NY: Consultants Bureau, XII, 2000.

\bibitem{2}
Goncharov S.S., Nurtazin A.T. {\it Constructive models of complete decidable
theories}, Algebra Logic, {\bf12}:2 (1973), 67-77.

\bibitem{3}
Hanf W., Myers D. {\it Boolean sentence algebras: Isomorphism constructions},
J. Symbolic Logic, {\bf48}:2 (1983), 329-338.

\bibitem{4}
Harizanov V.S. {\it Pure computable model theory}, Handbook of Recursive
Mathematics, Edited by Yu.L.Ershov, S.S.Goncharov, A.Nerode, J.B.Remmel,
North-Holland Publishing Company, 1998, Chapter 1, 1-114.

\bibitem{5}
Harrington L. {\it Recursively presented prime models}, J. Symbolic Logic,
{\bf39}:2 (1974), 305-309.

\bibitem{6}
Hodges W. {\it A shorter model theory}, Cambridge University Press,
Cambridge, 1997.

\bibitem{7}
Lempp S., Peretyat'kin M.G., Solomon R. {\it The Lindenbaum algebra of the
theory of the class of all finite models}, Journal of Mathematical Logic,
World Scientific Publishing Company and Singapore University Press, {\bf2}:2
(2002), 145-225.

\bibitem{8}
Nurtazin A.T. {\it Strong and weak constructivizations and computable
families}, Algebra Logic, {\bf20}:3 (1974), 177-184.

\bibitem{9}
Peretyat'kin M.G. {\it Finitely axiomatizable theories}, Plenum, New York,
1997.

\bibitem{10}
Peretyat'kin M.G. {\it Finitely axiomatizable theories and Lindenbaum
algebras of semantic classes}, Contemporary mathematics, {\bf257} (2000),
221-239.

\bibitem{11}
Peretyat'kin M.G. {\it On the Tarski-Lindenbaum algebra of the class of all
strongly constructivizable prime models}, Proceedings of the Turing Centenary
Conference CiE2012, Lecture notes in Computer Science, {\bf7318},
Springer-Verlag: Berlin-Heidelberg (2012), 589-598.

\bibitem{12}
Peretyat'kin M.G. {\it The Tarski-Lindenbaum algebra of the class of all
strongly constructivizable countable saturated models}, Bonizzoni, V.
Brattka, and B. Lowe (editors), CiE 2013, Lecture notes in Computer Science,
{\bf7921}, Springer-Heidelberg (2013), 342-352.

\bibitem{13}
Peretyat'kin M.G. {\it The Tarski-Lindenbaum algebra of the class of all
strongly constructivizable prime models of algorithmic dimension one},
Siberian Electronic Mathematical Reports, {\bf17} (2020), 913–922.

\bibitem{14}
Rogers H.J. {\it Theory of Recursive Functions and Effective Computability}.
Mc. Graw-Hill Book Co., New York, 1967.

\bibitem{15}
Sikorski R. {\it Boolean algebras}. 3rd edition, Springer-Verlag, Berlin
Heidelberg, New York, 1969.

\bibitem{16}
Vaught R.L. {\it Denumerable models of complete theories}, Infinitistic
methods, Proceedings of the Symposium on Foundations of Mathematics, Warsaw,
2–9 September, 1959, Warsaw, and Pergamon Press, Oxford, London, New York,
and Paris (1961), 303–321.

\end{thebibliography}

\end{document}
