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

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

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

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


\thispagestyle{empty}

\title[Вычислимо отделимые нумерации локально финитно отделимых алгебр]{Вычислимо отделимые нумерации локально финитно отделимых алгебр}
\author{Н.Х. Касымов}%

\address{Nadimulla Khabibullaevich Kasymov  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} National University of Uzbekistan,
\newline\hphantom{iii} University st., 4,
\newline\hphantom{iii} 100174, Tashkent, Uzbekistan}%
\email{nadim59@mail.ru}%

\thanks{\sc Kasymov N.Kh., Computably separable numbering of locally finitely separable algebras}
\thanks{\copyright \ 2023 Касымов Н.Х. 
Работа выполнена в рамках реализации Программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение № 075-02-2022-882)}
\thanks{\it Поступила 31 января 2023 г., опубликована 31 января 2023 г.}%

\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract.} It has been establish that the locally finitely separability of any universal algebra represented over a given uniformly computably separable equivalence is equivalent to the immune of the characteristic transversal of this equivalence. Examples are presented that demonstrate the infidelity of this criterion for finitely separable algebras, as well as for computably separable equivalences that are not uniform. It is shown that every infinite and co-infinite set is a characteristic transversal of a computably separable equivalence, over which only finitely approximable algebras are represented.
\medskip

\noindent{\bf Keywords:} numbered algebra, morphism, representation of universal algebra over equivalence and $\eta$-algebra, characteristic transversal of equivalence and numbering, uniformly computably separable numbering, finitely and locally finitely separability.
 \end{quote}
}


\section*{Введение}

С неопределяемыми в статье базовыми понятиями можно ознакомиться в \cite{1,2,3}. Используемые постановки вопросов, идеи и методы восходят к \cite{4,5}. Рассматриваются универсальные алгебры эффективных сигнатур.

Вычислимо отделимые алгебры играют и, по-видимому, будут играть в обозримой перспективе заметную роль как в теории вычислимых алгебр, так и в теоретической информатике (см. обзоры \cite{6,7}). Так, А.И. Мальцевым в \cite{5} было показано, что всякая позитивная нумерация конечно порожденной алгебры, обладающей ненулевыми конгруэнциями только конечного индекса является вычислимой, что поставило вопрос о справедливости данного утверждения в общем случае (без условия конечной порожденности). Оказалось, что имеются контрпримеры, причем именно и только в классе вычислимо отделимых алгебр (\cite{8}). Более того, всякая позитивная нумерация алгебры со счетной (в частности, нетеровой) решеткой конгруэнций является вычислимо отделимой (\cite{9,10}). Другой пример -- проблема Бергстры-Такера в теории абстрактных типов данных о существовании инициального в конечно-базируемом многообразии обогащения для любой конечно порожденной позитивной алгебры (\cite{11}). Отрицательное решение этой проблемы было получено предъявлением соответствующего примера конечно порожденной алгебры, имеющей вычислимо отделимую позитивную нумерацию с иммунной характеристической трансверсалью (\cite{12}).

Важнейшим подклассом класса вычислимо отделимых алгебр является класс равномерно вычислимо отделимых алгебр, для объектов которого существуют алгоритмы, позволяющие равномерно эффективно порождать характеристические индексы отделяющих множеств (\cite{13}). Достаточно сказать, что контрпример к упомянутой выше проблеме А.И. Мальцева является равномерно вычислимо отделимой алгеброй, а контрпример к проблеме Бергстры-Такера можно усилить, выбрав такую равномерно вычислимо отделимую позитивную конечно порожденную алгебру, никакое обогащение которой не является свободной системой ни в каком классе систем, конечно аксиоматизируемом универсальными предложениями специального, но весьма общего вида (\cite{6}). Отметим, что класс равномерно вычислимо отделимых алгебр весьма обширен. Например, в каждой $m$-степени содержится равномерно вычислимо отделимая алгебра. Особое место среди равномерно вычислимо отделимых алгебр занимают негативные алгебры, т.к. нумерованная алгебра вычислимо отделима тогда и только тогда, когда она аппроксимируется негативными алгебрами (\cite{13,14}), т.е. исключительной особенностью вычислимо отделимых алгебр, в отличие от других нумерованных систем, является их аппроксимируемость негативными алгебрами.  

Под словом эквивалентность понимается отношение эквивалентности на множестве натуральных чисел $\omega$. Если $\eta$ -- эквивалентность, то множество $\alpha\subseteq\omega$ называется $\eta$-замкнутым, если $\alpha$ является объединением подходящих $\eta$-классов (т.е. $x\in\alpha\wedge x=y\pmod\eta\Rightarrow y\in\alpha$). Эквивалентность будем называть бесконечной, если бесконечно число ее смежных классов. Говоря о расширении эквивалентности $\eta_0$ будем подразумевать ее расширение, являющееся отношением эквивалентности, т.е. всякое такое бинарное отношение $\eta_1$, что $\eta_0\subseteq\eta_1$ и $\eta_1$ -- эквивалентность. 

Если $(A,\nu)$ -- нумерованная алгебра, то ее нумерационную эквивалентность будем называть, для краткости, ядром нумерации и обозначать через $ker(\nu)$. Мы будем отождествлять понятия нумерации и алгоритмического представления универсальной алгебры. Точно так же, свойство представимости алгебры над эквивалентностью $\eta$ будет пониматься как равнообъемное свойству ''быть $\eta$-алгеброй''. 

Характеристической трансверсалью эквивалентности $\eta$ называется множество минимальных представителей всех смежных классов этой эквивалентности, т.е. $tr(\eta)=\{x\mid\forall y(x=y\pmod\eta\Rightarrow x\leqslant y)\}$. Характеристической трансверсалью нумерации (алгоритмического представления) $\nu$ называется характеристическая трансверсаль ее ядра, т.е. $tr(ker(\nu))=tr(\{\langle x,y\rangle\mid\nu x=\nu y\})$, которую, в целях сокращения, часто будем обозначать через $tr(\nu)$. Характеристическая трансверсаль представляет собой важный алгоритмический атрибут как эквивалентности, так и нумерации. Например, очевидно, что для негативной (позитивной) эквивалентности ее характеристическая трансверсаль вычислимо перечислима (коперечислима).

Пусть $(A,\nu)$ -- нумерованная алгебра. Подмножество $B$ алгебры $A$ называется $\nu$-вычислимым ($\nu$-перечислимым, $\nu$-коперечислимым), если вычислимо (вычислимо перечислимо, коперечислимо) множество $\nu^{-1}(B)$. Если из контекста будет ясно, какая нумерация имеется в виду, то подмножества алгебры будем называть просто вычислимыми (перечислимыми, коперечислимыми) без приставки $\nu$.   

Напомним, что универсальная алгебра называется финитно аппроксимируемой, если для любых двух различных ее элементов существует гомоморфизм на конечную алгебру, в котором образы этих элементов также различны. Аналогично, универсальная алгебра $A$ называется финитно отделимой, если для всякой ее подалгебры $A_0$ и любого элемента $a\in A\setminus A_0$ найдется такая конгруэнция конечного индекса, по модулю которой элемент $a$ отличен от всех элементов подалгебры $A_0$. Другими словами, на языке гомоморфизмов, существует такой гомоморфизм $\varphi$ из алгебры $A$ на конечную алгебру, что $\varphi(a)\notin\varphi(A_0)$. Аналогично, алгебра называется локально финитно отделимой, если для всякой ее конечно порожденной подалгебры и любого элемента вне этой подалгебры найдется конгруэнция конечного индекса, различающая данные элемент и подалгебру. Очевидно, что класс финитно отделимых алгебр является собственным подклассом класса локально финитно отделимых алгебр. Среди задач, связанных с алгоритмической разрешимостью алгебр, выделяется класс задач, связанных со структурными свойствами типа финитной отделимости. С алгоритмической точки зрения особенно важна локально финитная отделимость. Это связано с тем, что для конечно порожденных подалгебр всегда эффективен первый, начальный шаг порождения таких подалгебр и потому такие подалгебры будут эффективными, в то время как для бесконечно порожденных подалгебр множество порождающих, как и сама подалгебра, может иметь сколь угодно высокую алгоритмическую сложность. 

Предваряя следующие далее строгие определения будем говорить, что нумерация $\nu$ алгебры $A$ вычислимо отделима, если для любых различных $a_0,a_1\in A$ найдется такое множество (окрестность) $A_0$ для элемента $a_0$, что $a_0\in A_0$, $a_1\notin A_0$ и полный $\nu$-прообраз множества $A_0$ (т.е. $\nu^{-1}A_0$) вычислим. 

Особо подчеркнем следующее. Если $(A,\nu)$ -- нумерованная алгебра и $\nu$ вычислимо отделима, то $(A,\nu)$ аппроксимируется негативными алгебрами и если при этом $tr(\nu)$ иммунна, то характеристические трансверсали всех негативных гомоморфных образов нумерованной алгебры $(A,\nu)$ являются вычислимо перечислимыми подмножествами иммунного множества $tr(\nu)$. Поэтому все эти образы конечны и, следовательно, алгебра $A$ финитно аппроксимируема. Однако, вопросы (локально) финитной отделимости гораздо более тонкие. Очевидно, что из финитной отделимости любой алгебры следует ее локально финитная отделимость, которой, в свою очередь, при весьма общих предположениях (например, для любых двух различных элементов найдется конечно порожденная подалгебра, содержащая один из этих элементов и не содержащая второй) достаточно для финитной аппроксимируемости. Но цепочка обратных импликаций не имеет места. 

Заметим, что вычислимая отделимость нумерации позволяет вводить полезные топологии, базу которых образуют вычислимые подмножества нумерованных алгебр. Эти пространства являются $T_4$-пространствами (\cite{15}) и все операции нумерованных алгебр непрерывны как относительно вычислимо порожденных топологий, так и относительно существенно более сильных -- вычислимо перечислимо порожденных топологий (\cite{16}). 

Уместно отметить, что эффекты (равномерной) вычислимой отделимости ярко проявляют себя и в случае моделей, в частности -- линейных порядков. Так, всякая негативная нумерация линейного порядка типа рациональных чисел с естественным упорядочением продуктивна относительно вычислимых дедекиндовых сечений (\cite{17}). 

При этом, дедекиндово сечение $A|B$ линейного порядка $\langle L;\leqslant\rangle$ (в котором всякий элемент попадает либо в нижний класс $A$, либо в верхний класс $B$, причем $A\bigcap B=\emptyset$ и $\forall a\in A\forall b\in B(a\leqslant b)$) называется вычислимым в нумерации $\nu$ линейного порядка $L$, если вычислимо множество $A$ и на множество $\{\langle x,y\rangle|\nu x\leqslant\nu y\}$ налагаются естественные ограничения алгоритмического характера (вычислимость, позитивность, негативность и т.д.). Касательно продуктивности отметим, что семейство вычислимых сечений нумерованного линейного порядка называется продуктивным, если существует эффективная процедура, которая любому вычислимому (в смысле Ю.Л.Ершова, \cite{1}) семейству вычислимых сечений этого порядка сопоставляет (интенсионально, т.е. посредством алгоритма, способа вычисления, характеристического индекса) некоторое вычислимое сечение вне данного семейства. Более детально, семейство $\mathfrak{S}$ вычислимых дедекиндовых сечений вычислимо, если существует такая его нумерация $\mu:\omega\longrightarrow\mathfrak{S}$, что множество $\{\langle x,y\rangle|y\in\mu x\}$ вычислимо (алгоритмически разрешимо) и продуктивность семейства $\mathfrak{D}$ всех вычислимых сечений означает наличие эффективной процедуры ''выдающей'' для любого вычислимого подсемейства $\mathfrak{S}$ (заданного нумерацией $\mu$) семейства $\mathfrak{D}$ алгоритм разрешения некоторого вычислимого сечения $S$ из $\mathfrak{D}\setminus\mathfrak{S}$.  
 
В то же время, существует такое позитивное представление линейного порядка типа рациональных чисел, для которого вообще нет вычислимых сечений (\cite{18}). Отметим также тот очевидный факт, что для любой нумерованной системы семейство ее вычислимых автоморфизмов образует полугруппу с единицей. При этом, для любого вычислимого автоморфизма позитивной системы обратный к нему автоморфизм также вычислим. Однако, уже на уровне класса негативных представлений существует модель -- негативный линейный порядок, полугруппа вычислимых автоморфизмов которого бесконечна, но единственным вычислимо обратимым автоморфизмом этой полугруппы является единичный (\cite{19}).

Общеизвестно, что для эффективно заданного семейства конгруэнций процедура построения их точной верхней грани вполне прозрачна. Однако процесс ''расщепления'' конгруэнций не является удовлетворительным ни с алгоритмической, ни с алгебраической точек зрения. Оказалось, что именно равномерно вычислимо отделимые алгебры предоставляют возможность эффективного расщепления конгруэнций при некоторых, весьма общих, дополнительных условиях (\cite{20}), что еще раз подчеркивает важность свойства равномерности для вычислимо отделимых нумераций алгебр.

Касательно принципиальных различий между негативными и позитивными нумерациями, которые сохраняются при релятивизации относительно арифметических представлений, отметим следующее. Любая негативная эквивалентность является нумерационной для подходящей конечно порожденной когруэнц-простой универсальной алгебры (\cite{21}). Для позитивных эквивалентностей ничего подобного не имеет места (более подробно об этой проблематике см. обзор \cite{6}), что означает более богатые реализационные возможности негативных нумераций относительно позитивных. 

Исходя из сказанного, в настоящей работе рассматриваются равномерно вычислимо отделимые нумерации универсальных алгебр, обладающих свойством локально финитной отделимости. Основным результатом статьи является следующая алгоритмическая характеризация равномерно вычислимо отделимых эквивалентностей на языке представимости над ними локально финитно отделимых алгебр: 

Для равномерно вычислимо отделимой эквивалентности локально финитная отделимость всякой представимой над ней универсальной алгебры равносильна иммунности ее характеристической трансверсали. 

Показывается невозможность расширения этого критерия на класс вычислимо отделимых (не являющихся равномерно вычислимо отделимыми) эквивалентностей, а также его сужения на класс финитно отделимых универсальных алгебр. 

Показано также, что класс вычислимо отделимых эквивалентностей, над которыми представимы только финитно аппроксимируемые алгебры очень обширен, в отличие от класса равномерно вычислимо отделимых эквивалентностей с подобным свойством. В последнем случае, т.е. для бесконечной равномерно вычислимо отделимой эквивалентности, финитная аппроксимируемость всякой алгебры представимой над ней равносильна иммунности характеристической трансверсали этой эквивалентности. В то же время, любое кобесконечное множество (содержащее число $0$) является характеристической трансверсалью вычислимо отделимой эквивалентности, над которой представимы только финитно аппроксимируемые алгебры.


\section{Предварительные сведения}

Следуя Ю.Л.Ершову (\cite{1}) нумерацией $\nu$ не более чем счетного множества $N$ назовем всякое сюръективное отображение множества натуральных чисел $\omega$ на $N$. При этом, подмножество $N_0$ множества $N$ называется $\nu$-вычислимым ($\nu$-вычислимо перечислимым), если таковым является полный $\nu$-прообраз множества $N_0$, т.е. если множество $\{x|\nu x\in N_0\}$ всех $\nu$-номеров множества $N_0$ является вычислимым (вычислимо перечислимым). Иногда, когда из контекста ясно о какой нумерации $\nu$ множества $N$ идет речь, подмножества множества $N$ будем называть просто вычислимыми (вычислимо перечислимыми), без приставки $\nu$. В случае нумерованной алгебры $(A,\nu)$ мы предполагаем как эффективность сигнатуры $\Sigma$ этой алгебры, так и наличие эффективной процедуры, сопоставляющей каждой $\Sigma$-операции $F$, заданной на основном множестве алгебры $A$, алгоритм вычисления (клиниевский номер) тотальной функции $f$, представляющей операцию $F$ в нумерации $\nu$, т.е. $F(\nu\overline{x})=\nu f(\overline{x})$. Отметим, что такой подход к понятию нумерации алгебры концептуально восходит к А.И.Мальцеву (\cite{5}).
\par\smallskip
Если $A$ -- универсальная алгебра, то ее основное множество будем обозначать также через $A$. Из контекста всегда будет ясно о чем идет речь.

Пусть $A$ -- универсальная алгебра, $P(A)=\{B|B\subseteq A\}$ -- множество всех подмножеств множества $A$ и $\mathfrak{S}=\{S_i|i\in I\}\subseteq P(A)$ -- некоторое семейство подмножеств основного множества этой алгебры. Будем говорить, что элемент $a_0$ отделяется от элемента $a_1$ посредством $\mathfrak{S}$, если существует такое $i\in I$, что $a_0\in S_i$ и $a_1\notin S_i$. Если для всякой пары различных элементов $a_0,a_1$ алгебры $A$ имеет место отделимость $a_0$ от $a_1$ либо $a_1$ от $a_0$ посредством $\mathfrak{S}$, то $\mathfrak{S}$ назовем полным отделяющим семейством.        
\par\smallskip
\textbf{Определение 1.1.} {\em Нумерованная алгебра $(A,\nu)$ называется вычислимо отделимой, если всякая пара различных ее элементов отделяется подходящим $\nu$-вычислимым множеством.} 
\par\smallskip
Другими словами, если $a_0,a_1$ -- различные элементы алгебры $A$, то найдется такое $\nu$-вычислимое подмножество $A_0$ основного множества алгебры $A$, что $a_0\in A_0$ и $a_1\notin A_0$. Таким образом, вычислимая отделимость нумерованной алгебры равносильна существованию полного отделяющего семейства вычислимых (в данной нумерации) подмножеств. Заметим, что в силу симметричности ситуации (дополнение вычислимого множества также вычислимо) из вычислимой отделимости $a_0$ от $a_1$ следует вычислимая отделимость $a_1$ от $a_0$. Для $\nu$-вычислимо перечислимой отделимости (точная формулировка понятия дана в определении 1.3) это не так. Рассмотрим, например, связное двоеточие, которое реализуем так. Пусть $\alpha$ -- вычислимо перечислимое невычислимое подмножество $\omega$, $A=\{a_0,a_1\}$ и $\nu x=a_0$ для $x\in\alpha$, $\nu x=a_1$ для $x\notin\alpha$. Тогда $a_0$ является $\nu$-вычислимо перечислимо отделимым от $a_1$, но $a_1$ не является $\nu$-вычислимо перечислимо отделимым от $a_0$ и $\mathfrak{S}=\{\{a_0\}\}$ -- полное отделяющее семейство для нумерованной алгебры $(A,\nu)$ пустой сигнатуры.
\par\smallskip
Напомним (\cite{1,4,5}), что если $(A,\mu)$, $(B,\nu)$ -- нумерованные алгебры, то гомоморфизм $\varphi:A\longrightarrow B$ называется морфизмом, если он эффективен на номерах, т.е. существует вычислимая функция $f$ такая, что $\varphi\mu=\nu f$. Если $\mathfrak{B}=\{(B_i,\nu_i)|i\in I\}$ -- семейство нумерованных алгебр, то говорят, что нумерованная алгебра $(A,\mu)$ аппроксимируется $\mathfrak{B}$-алгебрами, если для всякой пары различных элементов $a_0,a_1\in A$ существует морфизм $\varphi_{\{a_0,a_1\}}$ из $(A,\mu)$ в подходящую $\mathfrak{B}$-алгебру, различающий эти элементы (т.е. $\varphi_{\{a_0,a_1\}}(a_0)\neq\varphi_{\{a_0,a_1\}}(a_1)$).
\par\smallskip
 
Следующая, уже упоминавшаяся выше, теорема о негативной аппроксимируемости играет важную роль в теории вычислимо отделимых алгебр:
\par\smallskip
\textbf{Теорема 1.2.} {\em Нумерованная алгебра вычислимо отделима тогда и только тогда, когда она аппроксимируется негативными алгебрами.} 
\par\smallskip
{\em Доказательство} в \cite{13,14}).
\par\smallskip
Таким образом, в рамках структурной теории вычислимо отделимых алгебр негативные алгебры определяют класс объектов, из которых строятся все вычислимо отделимые алгебры (как подходящие подпрямые произведения).
\par\smallskip
\textbf{Определение 1.3.} {\em Нумерованная алгебра $(A,\nu)$ называется отделимой, если всякая пара различных ее элементов отделяется подходящим $\nu$-вычислимо перечислимым множеством.} 
\par\smallskip
Если существует вычислимое (в смысле Ю.Л.Ершова, см. \cite{1}) полное семейство $\mathfrak{S}$ отделяющих вычислимо перечислимых множеств для нумерованной алгебры $(A,\nu)$ из этого определения, то нумерация называется эффективно отделимой, т.е. вместе с полнотой семейства $\mathfrak{S}$ (каждый элемент которого есть $\nu$-вычислимо перечислимое подмножество множества $A$) требуется наличие такой нумерации $\mu:\omega\longrightarrow\{\nu^{-1}S|S\in\mathfrak{S}\}$ множества, элементами которого являются полные $\nu$-прообразы элементов из $\mathfrak{S}$, что множество $\{\langle x,y\rangle|y\in\mu x\}$ вычислимо перечислимо. Неформально говоря, имея $\mu$-номер множества из семейства $\nu^{-1}\mathfrak{S}$ мы автоматически располагаем алгоритмом (постовским номером) для перечисления элементов этого множества.   
\par\smallskip
Напомним, что эквивалентность $\eta$ на $\omega$ называется отделимой, если для фактор-пространства $\omega/\eta$ существует полное отделяющее семейство $\eta$-замкнутых вычислимо перечислимых множеств $\mathfrak{S}$ (подразумевается естественная проектирующая нумерация $\pi:\omega\longrightarrow\omega/\eta$ фактор-пространства, т.е. $\pi x=x/\eta$). 

Аналогично, эквивалентность $\eta$ называется эффективно отделимой, если существует полное отделяющее семейство $\eta$-замкнутых вычислимо перечислимых множеств $\mathfrak{S}$, обладающее вычислимой нумерацией $\mu:\omega\longrightarrow\mathfrak{S}$ (т.е. множество $\{\langle x,y\rangle|y\in\mu x\}$ вычислимо перечислимо). Другими словами, эффективная отделимость эквивалентности $\eta$ означает, что существует вычислимое полное $T_0$-отделяющее семейство $\eta$-замкнутых вычислимо перечислимых множеств для пространства $\omega/\eta$, т.е. соответствующее топологическое пространство (порожденное базой вычислимо перечислимых множеств), является $T_0$-пространством или, иными словами, для любых двух различных классов эквивалентности найдется вычислимо перечислимая окрестность одного из них, не содержащая другой. 

Важно отметить, что для нумерованной алгебры $(A,\nu)$ в качестве элементов полного отделяющего семейства мы рассматриваем $\nu$-вычислимо перечислимые подмножества множества $A$ и в качестве вычислимой нумерации этого семейства выбирается (если она существует) подходящая вычислимая нумерация семейства полных $\nu$-прообразов этих множеств. Для эквивалентности $\eta$ рассматривается непосредственно полное отделяющее семейство $\eta$-замкнутых вычислимо перечислимых множеств и, при условии существования, вычислимая нумерация этого семейства.
\par\smallskip  
Ю.Л. Ершовым в \cite{1} было введено наиболее общее понятие отделимой нумерации множества (т.е. такой нумерации, ядро которого $T_0$-отделимо в перечислимо порожденной топологии) и дана следующая характеризация ядер вычислимых нумераций семейств вычислимо перечислимых множеств: 
\par\smallskip
\textbf{Теорема 1.4. (Ю.Л.Ершов, \cite{1})} {\em Отношение эквивалентности $\eta$ на $\omega$ является ядром вычислимой нумерации подходящего семейства вычислимо перечислимых множеств тогда и только тогда, когда $\eta$ эффективно отделима.}
\par\smallskip
Нумерованная алгебра, ядро представления которой отделимо (эффективно отделимо) называется отделимой (соответственно эффективно отделимой).
\par\smallskip
Применение теоремы 1.4 к универсальным алгебрам, с учетом некоторых специальных алгебраических фактов, дает следующий результат:
\par\smallskip
\textbf{Теорема 1.5.} {\em Нумерованная алгебра отделима тогда и только тогда, когда она аппроксимируется эффективно отделимыми алгебрами.}
\par\smallskip
{\em Доказательство} в \cite{16}.
\par\smallskip
Таким образом, в структурной теории отделимых алгебр роль и место эффективно отделимых подобны роли и месту негативных -- в теории вычислимо отделимых алгебр.
\par\smallskip
Как отмечалось в \cite{1}, класс эффективно отделимых алгебр не имеет удовлетворительного описания в терминах арифметической иерарахии. Этот класс представляется естественным, т.к. он лежит достаточно низко в арифметической иерархии и содержит в себе важнейшие нижние классы -- $\Sigma^0_1\bigcup\Pi^0_1$. Поэтому вопрос о строении нижней полурешетки эффективно отделимых конгруэнций (а это множество является нижней подполурешеткой решетки конгруэнций любой нумерованной алгебры \cite{22}), и ее важнейших подполурешеток может представлять интерес также и с точки зрения теоретической информатики.
\par\smallskip
Далее, говоря о совпадении (различии) элементов $\nu x,\nu y$ нумерованной алгебры $(A,\nu)$ по модулю конгруэнции $\theta$ алгебры $A$ в нумерации $\nu$ будем подразумевать совпадение (различие ) этих элементов в нумерованной фактор-алгебре $(A/\theta,\pi_\theta\nu)$, где $\pi_\theta$ -- естественное проектирование (элемента в содержащий его класс $\theta$-эквивалентности).
\par\smallskip
\textbf{Определение 1.6.} {\em Конгруэнция $\theta$ нумерованной алгебры $(A,\nu)$ называется $\nu$-позитивной ($\nu$-негативной, $\nu$-отделимой и т.д.), если таково ее ядро.}
\par\smallskip
Если из контекста ясно, о какой нумерации $\nu$ идет речь, то приставку $\nu$- будем опускать.
\par\smallskip
\textbf{Определение 1.7.} {\em Конгруэнция $\theta$ нумерованной алгебры $(A,\nu)$ называется равномерно вычислимо отделимой, если существует частичная вычислимая функция $\lambda z.g(x,y,z)$ такая, что для всех $x\neq y\pmod\theta$ функция $\lambda z.g(x,y,z)$ является характеристической для некоторого $\theta$-замкнутого множества, отделяющего $x$ от $y$.}
\par\smallskip
На языке эквивалентностей, неформально, эквивалентность $\eta$ на $\omega$ равномерно вычислимо отделима, если существует единообразная эффективная процедура, которая для каждой пары различных по модулю $\eta$ натуральных чисел ''выдает'' алгоритм разрешения $\eta$-замкнутого вычислимого множества, отделяющего эти числа.

Соответственно, нумерованная алгебра $(A,\nu)$ называется равномерно вычислимо отделимой, если существует эффективная процедура, которая для любой пары различных элементов $a_0,a_1\in A$ ''выдает'' характеристический индекс такого подходящего вычислимого множества $S\subseteq\omega$, что $S$ является $\nu$-замкнутым (т.е. $x\in S\wedge\nu x=\nu y\Rightarrow y\in S$), $a_0\in\nu S$ и $a_1\notin\nu S$. 
\par\smallskip
\textbf{Замечание 1.8.} Несмотря на наличие некоторой внешней аналогии в определении понятий равномерно вычислимо отделимой и эффективно отделимой нумерации алгебры, эти понятия фундаментально различны. Для равномерно вычислимо отделимых нумераций, вообще говоря, ни о какой эффективной отделимости не может быть и речи, т.к. в любой $m$-степени есть равномерно вычислимо отделимая нумерация, а эффективно отделимые лежат в классе $\Pi^0_2$ (см. Ю.Л.Ершов, \cite{1}). С другой стороны, имеются эффективно отделимые нумерации, не являющиеся равномерно вычислимо отделимыми (даже вычислимо отделимыми; простейший пример -- связное двоеточие, когда вычислимо перечислимое невычислимое $\alpha\subseteq\omega$ нумерует один элемент двухэлементного множества, а $\omega\setminus\alpha$ -- другой). Отметим, что в классе $\Pi^0_2\setminus\Pi^0_1$ содержатся как подпрямо неразложимые нумерованные алгебры, так и алгебры с артиновыми решетками конгруэнций (\cite{23}), для которых всякие отделимые нумерации являются эффективно отделимыми (\cite{16}). В случае вычислимо отделимых нумераций всякое вычислимо отделимое представление как подпрямо неразложимой алгебры, так и алгебры с артиновой решеткой конгруэнций содержится в классе $\Pi^0_1$, т.е. является негативным (\cite{6}).
\par\smallskip
Выше было отмечено, что равномерно вычислимо отделимые алгебры имеют ряд полезных применений, в т.ч. в теоретической информатике. И именно равномерно вычислимые алгебры, образующие важнейший подкласс вычислимо отделимых алгебр, позволили решить уже упоминавшиеся вопросы, в т.ч. описать границы применимости теоремы А.И.Мальцева о вычислимости конечно порожденных позитивных алгебр, обладающих ненулевыми конгруэнциями лишь конечного индекса (\cite{8}), а также решить проблему Бергстры-Такера в теоретической информатике о существовании позитивно представимых алгебр, никакие обогащения которых не являются свободными системами ни в каких конечно аксиоматизируемых универсалах весьма общего вида (\cite{6}).
\par\smallskip
\textbf{Замечание 1.9.} Касательно определения конечной порожденности. Мы принимаем бесконечные эффективные сигнатуры, но, при этом, алгебру называем конечно порожденной (локально конечной), если конечно порожденной (локально конечной) алгеброй является некоторое (любое) ее конечное обеднение. Для конечных сигнатур такое понимание совпадает с традиционным. Однако для бесконечных сигнатур это не так. Например, пусть $A=\langle\omega;\{f_n|n\in\{0,1,\dots\}\rangle$, где $\omega$ -- множество натуральных чисел и $\forall x\in\omega(f_n(x)=n)$. Тогда алгебра $A$ локально конечна, но порождается любым своим элементом и всеми сигнатурным  операциями. Если алгебра $A$ конечно порожденная, то для любого ее представления $\nu$ можно тривиально получить ее конечное конечно порожденное обогащение. В самом деле, пусть $c_1,\dots,c_n$ -- порождающие этой алгебры и $k_1\in\nu^{-1}(c_1),\dots,k_n\in\nu^{-1}(c_n)$. Обогатим конечную сигнатуру $\Sigma$ алгебры $A$ унарными функциями $f^\ast_1,\dots,f^\ast_n$ до сигнатуры $\Sigma^\ast$ и определим вычислимые функции $f_1\dots,f_n$, представляющие операции $f^\ast_1,\dots,f^\ast_n$ обогащения $A^\ast$ в нумерации $\nu$ так, что $\forall x\in\omega(f_1(x)=k_1,\dots,f_n(x)=k_n)$. Очевидно, что $A^\ast$ -- алгебра конечной сигнатуры, порождаемая любым своим элементом. Все наши результаты, если не оговорено противное, верны не только для конечных, но и для бесконечных эффективных сигнатур. Поэтому, говоря о конечной порожденности универсальной алгебры мы, по умолчанию, предполагаем  конечную порожденность некоторого ее конечного обеднения. 
\par\smallskip
Для нумерованной алгебры $(A,\nu)$ однозначно определено ядро ее представления, т.е. нумерационная эквивалентность $ker(\nu)=\{\langle x,y\rangle\mid\nu x=\nu y\}$. С другой стороны, для фиксированной эквивалентности $\eta$ вполне определен класс алгебр, имеющих нумерации с ядром $\eta$. Всякую такую алгебру будем называть представимой над $\eta$ или $\eta$-алгеброй. Такой подход, являющийся двойственным с точки зрения теории нумерованных алгебр, представляется целесообразным для формулировки и решения многих задач. Например:

- если  эквивалентность $\eta$ имеет гипериммунную характеристическую трансверсаль, то всякая $\eta$-алгебра локально конечна (при этом алгоритмическая сложность $\eta$ может быть какой угодно, \cite{6}); 

- если $\eta$ позитивна и не является вычислимо отделимой, то всякая $\eta$-алгебра имеет континуальную решетку конгруэнций (\cite{24});

- если $\eta$ вычислимо отделима и не негативна, то всякая $\eta$-алгебра имеет неартинову решетку конгруэнций (\cite{7});

- существует такая бесконечная позитивная эквивалентность $\eta$, что всякая операция любой $\eta$-алгебры действует на классах $\eta$-эквивалентности либо как проектирующая, либо как константа, т.е. эта эквивалентность -- ''наименьшая'' среди всех эквивалентностей с точки зрения представимости алгебр над эквивалентностями, т.к. функции-константы и проектирующие (и только они) согласованы с любой эквивалентностью (см. также \cite{6});

бесконечное подмножество $\alpha$ множества $\omega$ назовем наследственно высоким, если никакое его бесконечное подмножество (включая само $\alpha$) не лежит в классе $\Pi_3^0$ арифметической иерархии Клини-Мостовского. Понятие наследственно высокого множества (класс отделимых эквивалентностей с наследственно высокими характеристическими трансверсалями весьма обширен) позволяет легко доказать, что 

- всякая алгебра, обладающая отделимой нумерацией с наследственно высокой характеристической трансверсалью, финитно аппроксимируема (\cite{16}).

Другие подобные факты, связывающие структурные свойства алгебр с алгоритмическими свойствами их нумераций, можно найти в вышеупомянутых обзорах \cite{6,7}.

Исходя из соображений приоритетности ядерных эквивалентностей относительно алгебр, представимых над этими эквивалентностями, мы будем формулировать большинство наших результатов на языке представимости алгебр над эквивалентностями, т.е. $\eta$-алгебр, хотя, с учетом отмеченной выше двойственности, эти факты равносильны тем, которые формулируются с использованием традиционного подхода при очевидной интерпретации формулировок.


\section{Некоторые свойства равномерно вычислимо отделимых эквивалентностей и алгебр}

В настоящем разделе, носящем вспомогательный характер, приведем необходимые в дальнейшем факты о (равномерно) вычислимо отделимых эквивалентностях и алгебрах, сопровождая их примерами.

Согласно определению 1.7 эквивалентность $\eta$ равномерно вычислимо отделима, если существует такая частичная вычислимая функция $g$ от трех переменных, что если $x\neq y\pmod\eta$, то функция $\lambda z.g(x,y,z)$ является характеристической вычислимой функцией для некоторого $\eta$-замкнутого множества, отделяющего $x$ от $y$.

Напомним определения некоторых эквивалентностей из \cite{1}. 

Пусть $\alpha\subseteq\omega$. Тогда:

1) $\eta^\alpha=\{\langle 2x,2x+1\rangle|x\in\alpha\}\cup\{\langle 2x+1,2x\rangle|x\in\alpha\}\cup id\;\omega$;

2) $\eta_\alpha=\alpha^2\cup id\;\omega$;

3) $\eta^*_\alpha=\{\langle x,y\rangle|\gamma_x\smallsetminus\alpha=\gamma_y\smallsetminus\alpha\}$, где $\gamma$ --- каноническая нумерация конечных множеств (эквивалентно, $\eta^*_\alpha=\{\langle x,y\rangle|\gamma_x\bigtriangleup\gamma_y\subseteq\alpha\}$).

Легко проверить, что все эти эквивалентности вычислимо отделимы. 
\par\smallskip
\textbf{Предложение 2.1 (\cite{13}).} {\em Для любого $\alpha\subseteq\omega$ эквивалентность $\eta^\alpha$ является равномерно вычислимо отделимой.}
\par\smallskip
\textbf{Предложение 2.2 (\cite{13}).} {\em Для любого $\alpha\subseteq\omega$ имеет место $c(\eta^\alpha)\equiv_m\alpha$.}
\par\smallskip
\textbf{Следствие 2.3.} {\em Всякая $m$-степень содержит равномерно вычислимо отделимую эквивалентность.}
\par\smallskip
\textbf{Замечание 2.4.} В частности, число эквивалентностей типа $\eta^\alpha$, каждая из которых равномерно вычислимо отделима, есть континуум. Более того, функция $g$ из определения равномерно вычислимой отделимости едина для всех этих эквивалентностей.
\par\smallskip
\textbf{Определение 2.5.} {\em Эквивалентность $\eta$ на множестве $\omega$ называется равномерно аппроксимируемой вычислимыми эквивалентностями, если существует частичная вычислимая функция $h$ от четырех переменных, обладающая следующим свойством:

если $x\neq y\pmod\eta$, то $\lambda u,v.h(x,y,u,v)$ -- вычислимая функция, являющаяся характеристической для такого расширения $\eta^\ast$ эквивалентности $\eta$, по модулю которой $x,y$ также различны.}
\par\smallskip
\textbf{Предложение 2.6 (\cite{13})} {\em Эквивалентность является равномерно вычислимо отделимой тогда и только тогда, когда она равномерно аппроксимируется вычислимыми эквивалентностями.}
\par\smallskip
Т.к. основным объектом исследования данной работы являются равномерно вычислимо отделимые эквивалентности с иммунными характеристическими трансверсалями, то рассмотрим вкратце вопросы существования таких эквивалентностей.

Заметим, что ни для какого $\alpha\subseteq\omega$ эквивалентность $\eta^\alpha$ не обладает иммунной характеристической трансверсалью, т.к. $\{2x\mid x\in\omega\}\subseteq tr(\eta^\alpha)$, хотя многие другие интересные случаи реализуются и для $\eta^\alpha$. Например, легко проверить, что если $\alpha$ креативно, то $\eta^\alpha$ позитивна и $tr(\eta^\alpha)$ продуктивна.
\par\smallskip
\textbf{Определение 2.7.} {\em Эквивалентность называется эффективно бесконечной, если существует бесконечное вычислимо перечислимое множество натуральных чисел, попарно различных по ее модулю.}
\par\smallskip
Иначе говоря, эквивалентность $\eta$ эффективно бесконечна тогда и только тогда, когда существует разнозначное вычислимое вложение $id\;\omega$ в $\eta$ (т.е. для подходящей вычислимой функции $f$ верно $x\neq y\Rightarrow f(x)\neq f(y)$). Бесконечную эквивалентность не являющуюся эффективно бесконечной назовем {\em неэффективно бесконечной}.
\par\smallskip
Пусть $K_0$ -- класс эквивалентностей с иммунными характеристическими трансверсалями, $K_1$ -- класс неэффективно бесконечных эквивалентностей и $K_2$ -- класс эквивалентностей, характеристические трансверсали которых гипериммунны. Имеет место следующее
\par\smallskip
\textbf{Предложение 2.8.} {\em $K_0\supset K_1\supset K_2$. Все включения собственные.}
\par\smallskip
\begin{proof}
Отношения включения очевидны. Покажем строгость этих включений. Пусть $\alpha$ -- множество с иммунным не гипериммунным дополнением. Тогда $\eta^\ast_\alpha\in K_0\setminus K_1$ и $\eta_\alpha\in K_1\setminus K_2$.
\end{proof}
В классе равномерно вычислимых эквивалентностей свойства иммунности характеристической трансверсали и неэффективной бесконечности оказались равносильными.  
\par\smallskip
\textbf{Предложение 2.9 (\cite{13}).} {\em Равномерно вычислимо отделимая эквивалентность имеет иммунную характеристическую трансверсаль тогда и только тогда, когда она неэффективно бесконечна.}
\par\smallskip
\textbf{Следствие 2.10.} {\em Если $\omega\setminus\alpha$ иммунно, но не гипериммунно, то $\eta^\ast_\alpha$ не является равномерно вычислимо отделимой.}         
\par\smallskip
Ясно, что в этом случае эквивалентность $\eta^\ast_\alpha$ эффективно бесконечна, т.к. наличие сильной таблицы $\delta_0,\delta_1,\dots$ для $\omega\setminus\alpha$ (т.е. вычислимого по каноническим индексам семейства попарно непересекающихся конечных множеств, каждое из которых содержит число из $\omega\setminus\alpha$) гарантирует, что $m\neq n\Rightarrow\delta_m\setminus\alpha\neq\delta_n\setminus\alpha$, т.е. $\gamma^{-1}\delta_m\neq\gamma^{-1}\delta_n\pmod{\eta^\ast_\alpha}$, где $\gamma$ -- каноническая нумерация конечных множеств.   

Рассмотрим теперь вычислимо отделимые эквивалентности типа $\eta_\alpha$ с иммунными характеристическими трансверсалями -- с точки зрения наличия свойства ''быть равномерной'' (в смысле определения 1.7).
\par\smallskip
\textbf{Предложение 2.11 (\cite{13}).} {\em Если $\omega\setminus\alpha$ иммунно, но не гипериммунно, то эквивалентность $\eta_\alpha$ не является равномерно вычислимо отделимой.}
\par\smallskip

Напомним (\cite{3}), что множество $\alpha$ называется регрессивным, если существует некоторый его пересчет без повторений $\alpha=\{a_0,a_1,\dots\}$ такой, что для подходящей частичной вычислимой функции $\psi$ имеет место $\psi(a_{n+1})=a_n$ для всех $n\in\omega$ и $\psi(a_0)=a_0$.

\par\smallskip
\textbf{Предложение 2.12 (\cite{13}).} Пусть {\em $\alpha$ -- гиперпростое множество с регрессивным дополнением. Тогда эквивалентность $\eta_\alpha$ -- равномерно вычислимо отделима.}
\par\smallskip
Перейдем к рассмотрению необходимых понятий из теории равномерно вычислимо отделимо нумерованных универсальных алгебр.

Формула называется позитивной, если в ее записи нет знаков отрицания и импликации (см. А.И.Мальцев \cite{2}, п.7.4). Заметим, что позитивные формулы устойчивы относительно гомоморфизмов (также \cite{2}).
\par\smallskip
\textbf{Определение 2.13.} {\em Бескванторная формула  называется дизъюнктивно-импликативно-позитивной (ДИП-формулой), если она имеет один из следующих трех видов:

1. $A_{1}\vee\ldots\vee A_{n}\rightarrow P$;

2. $A_{1}\vee\ldots\vee A_{n}\rightarrow F$;

3. $P$, 

где $A_{i}$ -- атомарные, $P$ -- позитивная формулы, а $F$ -- ''ложь''.}

ДИП-формулами являются, в частности, конъюнкции отрицаний атомарных (случай 2), позитивные формулы (случай 3), а также бескванторные части однопосылочных квазитождеств вида $A_1\rightarrow P$ (при $n=1$ и атомарности $P$). Универсальное замыкание ДИП-формулы называется универсальным ДИП-предложением.  

Негативные алгебры, опять-таки, образуют важный класс равномерно вычислимо отделимых алгебр, что демонстрирует следующая
\par\smallskip
\textbf{Теорема 2.14 (\cite{6}).} {\em Для нумерованной алгебры $(A,\nu)$ равносильны следующие условия: 

1) $(A,\nu)$ -- равномерно вычислимо отделимая алгебра;

2) если $\Phi$ -- вычислимо перечислимое множество универсальных ДИП-предложений, реализующееся в $A$, то $(A,\nu)$ равномерно аппроксимируется негативными $\Phi$-алгебрами (т.е. негативными алгебрами, в которых реализуется $\Phi$).}
\par\smallskip
Ключевая идея доказательства заключается в следующем. Начиная с произвольного вычислимого разбиения $\omega$ на конечное число множеств (определяющих конечное вычислимое расширение ядра исходной нумерации) шаг за шагом перебираем предложения из $\Phi$, проверяя их на предмет истинности на этом разбиении, и если что-то из $\Phi$ ложно, то производим расщепление согласно левой части соответствующего ДИП-предложения (если $\varphi\in\Phi, \varphi=A_{1}\vee\ldots\vee A_{n}\rightarrow P$ и $\varphi$ ложно, то расклеиваем все атомарные формулы, участвующие в дизъюнкции в левой посылочной части формулы $\varphi$) и продолжаем процесс. Предельная система и будет негативной фактор-алгеброй исходной алгебры, в которой реализуется $\Phi$. Сделаем два важных замечания. Во-первых, для формул имеющих вид квазитождеств с не менее чем двумя посылками в левой части, скажем $\psi=A_{1}\wedge\dots\wedge A_{n}\rightarrow P\;(n\geqslant 2)$, при попытке реализации $\psi$ за счет расщепления возникает дилемма -- которое из $A_i$ расщепить? И этот вопрос принципиальный. Для ДИП-формул такие затруднения отсутствуют. Во-вторых, на каждом конечном шаге процедуры расщепления текущее вычислимое разбиение может и не быть алгеброй (т.е. для какой-то операции на эквивалентных относительно разбиения наборах значения операции неэквивалентны). Но для любой операции $f$ от $n$ аргументов реализуемость универсального предложения $\forall x,y[x=y\Rightarrow f(\overline{c},x,\overline{d})=f(\overline{c},y,\overline{d})]$ (где $\overline{c},\overline{d}$ -- параметры, выделенные контантами, а $\eta$ -- текущее разбиение), которое является универсальным ДИП-предложением, в алгебре $\langle\omega/\eta;f\rangle$ означает, что предельное разбиение согласовано со всеми операциями, т.е. является конгруэнцией, причем негативной, т.к. любая пара элементов либо никогда не расклеится, либо расклеится ровно один раз и больше никогда не склеится.
\par\smallskip
\textbf{Предложение 2.15.} {\em Всякая равномерно вычислимо отделимая бесконечная эквивалентность с не иммунной характеристической трансверсалью имеет бесконечное негативное расширение.}
\begin{proof} 
Пусть $\eta$ -- бесконечная равномерно вычислимо отделимая эквивалентность, $tr(\eta)$ не иммунна и $\alpha=\{a_0,a_1,\dots\}\subseteq tr(\eta)$ -- бесконечное вычислимое подмножество трансверсали. Обогатим алгебру $\langle\omega/\eta\rangle$ пустой сигнатуры счетным множеством констант $C=\{c_0,c_1,\dots\}$, стандартным образом интерпретируя константу $c_n$ в элемент $n/\eta$. Полагаем $\Phi=\{c_m\neq c_n\mid m\neq n\wedge m,n\in\alpha\}$. Т.к. $\Phi$ -- вычислимо перечислимое множество универсальных ДИП-предложений, реализующееся в равномерно вычислимо отделимой алгебре $\langle\omega/\eta;C\rangle$, то по теореме 2.14 эта алгебра имеет негативную фактор-алгебру, в которой реализуется $\Phi$, т.е. индекс этой негативной $\Phi$-конгруэнции бесконечен.
\end{proof}
\textbf{Предложение 2.16 (\cite{21}).} {\em Пусть $\eta$ -- бесконечная негативная эквивалентность и $\alpha$ -- бесконечное вычислимое подмножество характеристической трансверсали $tr(\eta)$. Тогда существует такое вычислимое расширение $\eta^\ast$ эквивалентности $\eta$, что $tr(\eta^\ast)=\alpha\cup\{0\}$.}
\par\smallskip
\textbf{Следствие 2.17.} {\em Всякая бесконечная равномерно вычислимо отделимая эквивалентность с не иммунной характеристической трансверсалью имеет бесконечное вычислимое расширение.}
\par\smallskip
Непосредственно вытекает из предложений 2.15 и 2.16. 


\section{Критерий локально финитной отделимости}

\textbf{Определение 3.1.} {\em Семейство конгруэнций $(\theta_i)_{i\in\omega}$ называется равномерно негативным, если множество $\{\langle x,y,m\rangle\mid x\neq y\,(\mbox{mod}\,\theta_m)\}$ вычислимо перечислимо.}
\par\smallskip
Следующее утверждение очевидно. 
\par\smallskip
\textbf{Предложение 3.2.} {\em Пересечение всех конгруэнций из любого равномерно негативного семейства негативных конгруэнций является негативной конгруэнцией, причем индекс этого пересечения строится равномерно эффективно по заданному алгоритму перечисления этого семейства.}
\par\smallskip
В частности, пересечение любого конечного множества негативных конгруэнций является негативной конгруэнцией.
\par\smallskip
\textbf{Предложение 3.3.} {\em Если характеристическая трансверсаль бесконечной равномерно вычислимо отделимой эквивалентности $\eta$ не иммунна, то существует не локально финитно отделимая универсальная $\eta$-алгебра.}
\par\smallskip
\begin{proof}
Пусть $\eta$ -- бесконечная равномерно вычислимо отделимая эквивалентность, $\lambda z.g(x,y,z)$ -- функция из определения равномерности $\eta$, $tr(\eta)$ не иммунна и $\alpha=\{0=a_0<a_1<\dots\}$ -- бесконечное вычислимое подмножество $tr(\eta)$. Определим нумерацию $\nu:\omega^2\longrightarrow\Omega$ (где $\Omega$ -- подсемейство семейства всех вычислимых расширений эквивалентности $\eta$, имеющих ровно два класса), сопоставляя каждой паре $\langle m,n\rangle$ при $m\neq n$ вычислимую эквивалентность $\alpha_{\langle m,n\rangle}$ как разность между $\omega^2$ и симметричным замыканием множества  $\{\langle x,y\rangle\mid g(a_m,a_n,x)=1\wedge g(a_m,a_n,y)=0\}$. Т.к. при различных по модулю эквивалентности $\eta$ числах $a_m,a_n$ функция $\lambda x.g(a_m,a_n,x)$ является всюду определенной вычислимой характеристической функцией некоторого $\eta$-замкнутого вычислимого множества $\beta$, отделяющего $a_m$ от $a_n$, то $\omega$ разбивается на две части: $\beta$ и $\omega\setminus\beta$, т.е. эквивалентность $\alpha_{\langle m,n\rangle}$ имеет ровно два вычислимых смежных класса -- $\beta$ и $\omega\setminus\beta$. Очевидно, что $\nu$ -- вычислимая нумерация семейства $\{\alpha_{\langle m,n\rangle}\mid\langle m,n\rangle\in\omega^2;m\neq n\}$ и потому, по предложению 3.2, эквивалентность 
$$\eta'=\bigcap_{\langle m,n\rangle\in\omega,m\neq n}\alpha_{\langle m,n\rangle}$$
является негативным и, очевидно, бесконечным расширением эквивалентности $\eta$. По предложению 2.16 эквивалентность $\eta'$ имеет бесконечное вычислимое расширение $\eta^\ast$, характеристическая трансверсаль которой есть $\alpha$. 
\par\smallskip
Построим не локально финитно отделимую алгебру $\langle\omega/\eta^\ast;p\rangle$ следующим образом: 
$$
p(x)=\left\{
\begin{array}{lcr}
0,\mbox{ если } x=0\pmod{\eta^\ast},\\
a_n,\mbox{ если } x=a_{n+1}\pmod{\eta^\ast},\\
\end{array}
\right.
$$
т.е. функция $p$ действует на классах $\eta^\ast$-эквивалентности как алгебра предшествования $P$ ($P=\langle\omega;p\rangle,p(n+1)=n,p(0)=0$). Ясно, что $p$ согласована с $\eta$, т.к. если $a=b\pmod\eta$, то $a=b\pmod{\eta^\ast}$ поскольку $\eta^\ast$ -- расширение $\eta$, но тогда $p(a)=p(b)$, т.е. $p$ согласована с $\eta$.
\par\smallskip
\textbf{Лемма 3.3.1.} {\em Если $U$ -- унарная алгебра, содержащая подалгебру изоморфную алгебре предшествования $P$, то $U$ не локально финитно отделима.}
\begin{proof}
Доказательство. Пусть $P$ -- подалгебра унара $U$. Обозначим через $c_0$ -- единственный неподвижный элемент в $P$ (относительно действия $p$), а через $c_1$ -- единственный (в $P$) $p$-прообраз элемента $c_0$. Пусть $\theta$ -- конгруэнция конечного индекса алгебры $U$. Тогда хотя бы в одном смежном $\theta$-классе содержится бесконечное множество $M$ элементов из $P$. Выберем произвольную пару элементов из $M$, отличных от $c_0,c_1$, скажем $a,b$ и пусть для определенности $a=p^k(b),p^l(a)=c_1;k,l\geqslant 1$. Легко проверить, что ''склейка'' элементов $a,b$ по модулю $\theta$ необходимо отождествляет элементы $c_0,c_1$ по модулю этой же конгруэнции. Следовательно, конечно порожденная подалгебра $\langle\{c_0\};p\rangle$ и элемент $c_1$ не различаются никакой конгруэнцией конечного индекса.
\end{proof}
Для завершения доказательства достаточно заметить, что определенная выше над эквивалентностью $\eta$ алгебра $\langle\omega/\eta;p\rangle$ содержит алгебру предшествования в качестве подалгебры. 
\end{proof}
\textbf{Замечание 3.4.} В лемме 3.3.1 вместо алгебры предшествования можно использовать любую подпрямо неразложимую бесконечную подалгебру $A$, в которой для некоторой  пары различных элементов, содержащихся в любой ненулевой конгруэнции, один из них лежит в подходящей конечно порожденной подалгебре $A_0$, а второй -- не принадлежит этой подалгебре.
\par\smallskip
Сформулируем критерий локально финитной отделимости всякой алгебры, представимой над равномерно вычислимо отделимой эквивалентностью.
\par\smallskip
\textbf{Теорема 3.5.} {\em Для бесконечной равномерно вычислимо отделимой эквивалентности $\eta$ следующие условия эквивалентны:

(1) характеристическая трансверсаль $tr(\eta)$ эквивалентности $\eta$ иммунна;

(2) всякая $\eta$-алгебра локально финитно отделима;

(3) всякая $\eta$-алгебра финитно аппроксимируема.}
\begin{proof}
(1)$\Rightarrow$(2). Пусть $\eta$ -- бесконечная равномерно вычислимо отделимая эквивалентность и алгебра $A$ эффективной сигнатуры $\Sigma$ представима над $\eta$. Допустим, что $A_0$ -- конечно порожденная элементами $C=\{c_0,\dots,c_m\}$ собственная подалгебра алгебры $A$ в сигнатуре $\Sigma$ (заметим, что сигнатура может быть и бесконечной, т.к. под конечной порожденностью мы понимаем порожденность конечным числом элементов и всеми неконстантными $\Sigma$-операциями, при этом полагаем, что все $\Sigma$-константы лежат в $C$) и $a\in A\setminus A_0$. Обогатим сигнатуру $\Sigma$ множеством константых символов для элемента $a$ и порождающих $c_0,\dots,c_m$, которые обозначим теми же буквами. Рассмотрим множество $T(C)$ всех $\Sigma$-термов. По условию $\forall t\in T(C)(a\neq t)$, поэтому в $A$ истинны все неравенства из множества $\Phi=\{a\neq t\mid t\in T(C)\}$. Зафиксируем нумерацию $\nu$ алгебры $A$ с ядром $\eta$, $\nu$-номер $k$ элемента $a$, множество $\nu$-номеров $C_\nu=\{k_0\in\nu^{-1}(c_0),\dots,k_m\in\nu^{-1}(c_m)\}$ порождающих подалгебры $A_0$ и обозначим через $T_\nu(C_\nu)$ множество всех термов из $T(C)$, в которых все $\Sigma$-операции заменены соответствущими представляющими вычислимыми функциями в нумерации $\nu$. В силу равномерности свойства вычислимой отделимости эквивалентности $\eta$, алгебра $(A,\nu)$ равномерно аппроксимируется негативными $\Phi$-алгебрами (см. предыдущий раздел, теорема 2.14, согласно которой для равномерно вычислимо отделимой алгебры, если в ней выполняется любое вычислимо перечислимое множество универсальных ДИП-предложений $\Phi$, то эта нумерованная алгебра аппроксимируется негативными $\Phi$-алгебрами). Таким образом, существует такое негативное расширение $\eta^\ast$ конгруэнции $\eta$, что в фактор-алгебре $\langle\omega/\eta^\ast;\Sigma\rangle$ реализуется вычислимо перечислимое множество $\{k\neq t_\nu\mid t_\nu\in T_\nu(C_\nu)\}$. Но характеристическая трансверсаль $tr(\eta^\ast)$ этой негативной конгруэнции $\eta^\ast$ является вычислимо перечислимым подмножеством иммунного множества $tr(\eta)$. Следовательно, $\eta^\ast$ -- конгруэнция конечного индекса, различающая элемент $a$ и подалгебру $A_0$.

(2)$\Rightarrow$(1). Пусть всякая алгебра, представимая над $\eta$ локально финитно отделима. Допустим, что $tr(\eta)$ не иммунна. Тогда, по предложению 3.3 существует не локально финитно отделимая $\eta$-алгебра. Противоречие. 

(1)$\Rightarrow$(3). Допустим, что характеристическая трансверсаль $tr(\eta)$ бесконечной равномерно вычислимо отделимой эквивалентности $\eta$ является иммунной, но при этом существует не финитно аппроксимируемая $\eta$-алгебра, скажем $A$, которая изоморфна вычислимой алгебре $\langle\omega/\eta;F\rangle$, где $F$ -- подходящее эффективное семейство вычислимых функций (для которых $\eta$ является конгруэнцией), представляющих операции этой алгебры в данном представлении (имеется в виду естественная проектирующая нумерация $\nu_\eta:\omega\longrightarrow A$, сопоставляющая каждому натуральному числу содержащий его $\eta$-класс). Пусть пара различных элементов $a_0,a_1$ алгебры $A$ не различается никакой конгруэнцией конечного индекса. Но по теореме 1.2 о негативной аппроксимируемости существует такое негативное конгруэнтное расширение $\eta^*$ эквивалентности $\eta$, по модулю которого эти элементы различны, т.е. $a_0/\eta^*\neq a_1/\eta^*$. Индекс $\eta^*$ необходимо бесконечен (т.к. по условию элементы $a_0$ и $a_1$ на различаются никакой конгруэнцией конечного индекса) и $tr(\eta^*)\subseteq tr(\eta)$. Но  характеристическая трансверсаль $tr(\eta^*)$ вычислимо перечислима, а $tr(\eta)$ иммунна. Следовательно, число $\eta^*$-классов должно быть конечным. Противоречие. Заметим, что в доказательстве данного пункта можно пренебречь свойством равномерности. 

(3)$\Rightarrow$(1). Пусть всякая $\eta$-алгебра финитно аппроксимируема, но $tr(\eta)$ бесконечна и не иммунна. Тогда, Тогда согласно доказательству предложения 3.3 существует унарная $\eta$-алгебра $A$, содержащая подалгебру, изоморфную алгебре предшествования $P$. Аналогично доказательству леммы 3.3.1 легко показать, что $A$ не финитно аппроксимируема. Противоречие. 
\end{proof}
Покажем, что условие локальности для свойства финитной отделимости в теореме 3.5 является существенным.
\par\smallskip
\textbf{Предложение 3.6.} {\em Существует такая равномерно вычислимо отделимая позитивная эквивалентность $\eta$ с иммунной характеристической трансверсалью, что некоторая $\eta$-алгебра не является финитно отделимой.}
\begin{proof}
Пусть $\delta_0=\{0\},\delta_1=\{1,2\},\delta_2=\{3,4,5\},\dots$ -- сильная последовательность попарно непересекающихся конечных множеств, в которой множество $\delta_n$ состоит из $n+1$ последовательных натуральных чисел. Определим вычислимую функцию $f$ так, что $f(x)=x+1$ при $x\in\delta_t\wedge x\neq\max\delta_t$. Если же $x=\max\delta_t$, то полагаем $f(x)=x$.
\par\smallskip

\par\smallskip 
Зафиксируем произвольное гиперпростое множество $\beta$ с регрессивным дополнением, некоторый пересчет которого прослеживается частичной вычислимой функцией $\psi$ (примеры таких множеств можно найти, например, в книге Х.Роджерса \cite{3}, глава 9, с. 182, теорема XVI (теорема Деккера, которая утверждает, что для любой разнозначной функции $f$ с невычислимой областью значений дополнение множества ее минимальных элементов $M_f=\{x|\forall y(x<y\Rightarrow f(x)<f(y))\}$, т.е. $\omega\setminus M_f$ -- гиперпросто; заметим, что множество $M_f$ из теоремы Деккера является регрессивным), см. также упражнение 9-44, с. 206).
\par\smallskip 
Определим множество $$\beta^\ast=\{z\mid\exists n[(z\in\delta_n\wedge n\in\beta)\vee z=\max\delta_n]\}.$$ и эквивалентность $\eta_{\beta^\ast}=\{\langle x,y\rangle\mid x,y\in\beta^\ast\}\cup id\;\omega$, т.е. $\eta_{\beta^\ast}$ имеет единственный нетривиальный смежный класс $\beta^\ast$.
\par\smallskip 
\textbf{Лемма 3.6.1.} {\em Множество $\beta^\ast$ -- гиперпростое с регрессивным дополнением.} 
\par\smallskip
\begin{proof}
Очевидно, что $\beta^\ast$ вычислимо перечислимо. Допустим, что $\omega\setminus\beta^\ast$ не гипериммунно и $\sigma^\ast_0,\sigma^\ast_1,\dots$ -- сильная таблица для $\omega\setminus\beta^\ast$ (т.е. $\sigma^\ast_0,\sigma^\ast_1,\dots$ -- перечислимая по каноническим индексам последовательность попарно непересекающихся конечных множеств, каждое из которых содержит элемент из дополнения $\beta^\ast$). Для всякого множества $\alpha\subseteq\omega$ через $\alpha^\delta$ обозначим оператор, сопоставляющий каждому $\alpha$ множество всех $\delta$-номеров всех элементов из множества $\alpha$, т.е. $$\alpha^\delta=\bigcup_{x\in\alpha}\{n|x\in\delta_n\}.$$

Заметим, что для любого $x$ имеется не более одного такого $n$, что $x\in\delta_n$. 

Построим следующую последовательность конечных множеств $\sigma_0,\sigma_1,\dots$ по шагам.
\par\smallskip
Шаг $0$. $$\sigma_0=\bigcup_{x\in\sigma^\ast_0}\{z\mid x\in\delta_z\}.$$

Шаг $s+1$. 
$$\sigma_{s+1}=\bigcup_{x\in\sigma^\ast_k}\{z\mid x\in\delta_z\},$$
где $$k=\min\{y\mid(\sigma^\ast_y)^\delta\cap(\sigma_0\cup\dots\cup\sigma_s)^\delta=\emptyset\}.$$ 
Конец шага $s+1$.
\par\smallskip
Индукцией по шагам построения нетрудно показать, что каждый шаг завершается предъявлением канонического индекса конечного множества, которое содержит элемент из дополнения $\beta$ и не пересекается со всеми множествами, построенными до данного шага, что противоречит гипериммунности $\omega\setminus\beta$.

Покажем, что $\omega\setminus\beta^*$ регрессивно. Для этого, назовем элемент множества $\delta_n$ предмаксимальным, если он не максимален, но больше всех остальных элементов из $\delta_n$. Для удобства будем полагать, что $\delta_0,\delta_1\subseteq\beta^\ast$. Определим вычислимую функцию $\psi^\ast$ следующим образом. Для данного натурального $x$ находим такое $n$, что $x\in\delta_n$ и полагаем $\psi^\ast(x)=f(x)$, если $x$ не является предмаксимальным в $\delta_n$. В противном случае, т.е. для предмаксимального $x$, полагаем $\psi^\ast(x)=\min\delta_{\psi(n)}$. Легко заметить, что $\psi^\ast$ регрессирует некоторый пересчет множества $\omega\setminus\beta^\ast$, т.к. каждый элемент из $\omega\setminus\beta$ ''заменяется'' подходящим отрезком $\delta_n$ и, по существу, регрессируются эти отрезки с сохранением корректности операции $\psi^\ast$. 
\end{proof}
Согласно лемме 3.6.1 и предложению 2.12 эквивалентность $\eta_{\beta^\ast}$ является равномерно вычислимо отделимой эквивалентностью с иммунной характиристической трансверсалью и потому, по теореме 3.5, любая алгебра представимая над этой эквивалентностью локально финитно отделима. Покажем, что над $\eta_{\beta^\ast}$ представима не финитно отделимая алгебра.

Зафиксируем два элемента $s,t\in(\omega\setminus\beta^\ast)$ и определим вычислимую алгебру $A=\langle\omega;h\rangle$, где 
$$
h(x,y)=\left\{
\begin{array}{lcl}
t,\mbox{ если } y\neq s,\\
f(x),\mbox{ если } y=s.\\
\end{array}
\right.
$$
Очевидно, что функция $h$ согласована с эквивалентностью $\eta_{\beta^\ast}$ и потому корректно определена позитивная фактор-алгебра $\langle A/\eta_{\beta^\ast};h\rangle$ вычислимой алгебры $A$  по конгруэнции $\eta_{\beta^\ast}$. Тогда $A_0=\langle\omega/\eta_{\beta^\ast}\setminus(\beta^\ast\cup\{s\});h\rangle$ -- подалгебра алгебры $\langle A/\eta_{\beta^\ast};h\rangle$, получающаяся из исходной фактор-алгебры удалением двух элементов -- $\beta^\ast$ и $s/\eta_{\beta^\ast}$. Покажем, что подалгебра $A_0$ и элемент $\beta^\ast$ не различаются никакой конгруэнцией конечного индекса. Для этого введем на дополнении множества $\beta^\ast$ функцию $d:\omega\setminus\beta^*\longrightarrow\omega$, которую назовем расстоянием до $\beta^\ast$ и полагаем $d(x)=\min\{n\mid f^n(x)\in\beta^\ast\}$.

Поскольку для всякого $n$ число элементов из дополнения $\beta^\ast$, расстояние от которых до $\beta^\ast$ больше этого $n$, бесконечно, то всякая конгруэнция конечного индекса содержит такой класс конгруэнтности, в котором содержится пара таких элементов, скажем $a,b$, что $d(a)<d(b)$. Из конгруэнтности этих элементов и того факта, что $\beta^\ast$ -- неподвижная точка относительно действия функции $f$, заключаем, что по модулю данной конгруэнции элементы $\beta^\ast$ и $f^{d(a)}(b)/\eta_{\beta^\ast}$ равны, хотя $f^{d(a)}(b)\notin\beta^\ast$. Таким образом, всякая конгруэнция конечного индекса отождествляет элемент $\beta^\ast$ с некоторым элементом подалгебры $A_0$. 
\end{proof}
\textbf{Замечание 3.7.} Пусть $T_\Sigma(C)$ -- абсолютно свободная алгебра $\Sigma$-термов эффективной сигнатуры $\Sigma$ от конечного множества $C$ сигнатурных порождающих. Напомним, что алгебра абсолютно свободна, если с учетом мощности множества порождающих из нее есть гомоморфизм в любую алгебру из класса всех $\Sigma$-алгебр. С точностью до изоморфизма удобно воспринимать ее как алгебру слов ($\Sigma$-термов), при этом значения любых $\Sigma$-термов различны. Легко заметить, что любая универсальная алгебра является гомоморфным образом подходящей абсолютно свободной. Зафиксируем некоторую геделевскую нумерацию $\gamma$ этой алгебры. Ясно, что любая $\Sigma$-алгебра $A$, порожденная множеством сигнатурных констант $C$, является гомоморфным образом алгебры $T_\Sigma(C)$. Выберем такой гомоморфизм и назовем его $\varphi$. Тогда нумерация $\nu_S=\varphi\gamma$ -- нумерация алгебры $A$, называется стандартной. Нетрудно заметить, что для любой нумерации $\nu$ алгебры $A$ стандартная нумерация $\nu_S$ сводится к $\nu$, т.е. существует такая вычислимая функция $f$, что $\nu_S=\nu f$. В случае позитивности $\nu$ имеет место также сводимость $\nu$ к $\nu_s$, т.е. эти нумерации оказываются вычислимо эквивалентными. Удобно смотреть на термы от эффективного множества порождающих как на ''имена'' классов конгруэнтности, содержащих эти термы (два терма равны, если совпадают их значения в алгебре). С этой точки зрения термы можно воспринимать как натуральные числа и, в некоторых случаях, такой подход кажется предпочтительнее перехода от натурального числа (геделевского номера терма) к самому терму и, далее, к значению терма в алгебре при соответствующем гомоморфизме.
\par\smallskip
Отметим следующий важный факт. Согласно предложению 3.6 над равномерно вычислимо отделимой эквивалентностью вида $\eta_\alpha$ при подходящем коиммунном $\alpha$ представима не финитно отделимая алгебра. Однако, по теореме 3.5, всякая $\eta_\alpha$-алгебра в этом случае будет локально финитно отделимой. Оказалось, что для эквивалентностей этого вида можно отказаться от условия равномерности.
\par\smallskip
\textbf{Предложение 3.8.} {\em Для любого $\alpha\subseteq\omega$ следующие условия равносильны:

(1) $tr(\eta_\alpha)$ иммунна;

(2) всякая $\eta_\alpha$-алгебра локально финитно отделима.}
\begin{proof}
(1)$\Rightarrow$(2). Будем говорить, что семейство функций $F$ согласовано с эквивалентностью $\eta$, если для каждой функции из $F$ эквивалентность $\eta$ является конгруэнцией.

Мы будем базироваться на следующем утверждении, доказанном в \cite{12}.
\par\smallskip
\textbf{Лемма 3.8.1 (\cite{12}).} {\em Пусть $F$ -- эффективное семейство вычислимых функций, согласованных с $\eta_\alpha$, где $\omega\setminus\alpha$ иммунно. Тогда для любого конечного множества $\gamma\subset\omega\setminus\alpha$ существует такое его конечное расширение $\delta$, что $\gamma\subset\delta\subset\omega\setminus\alpha$ и всякая функция из $F$ согласована с эквивалентностью $\eta_{\omega\setminus\delta}$.}  
\par\smallskip
Используем эту лемму следующим образом. 

Рассмотрим произвольную $\eta_\alpha$-алгебру $A$. Пусть $A_0$ -- конечно порожденная подалгебра алгебры $A$ и элемент $a$ не лежит в $A_0$, т.е. $a\in A\setminus A_0$. Рассмотрим два случая.

1. $a=\alpha$. В этом случае необходимо $A_0$ целиком лежит в $\omega\setminus\alpha$. В силу конечной порожденности эта подалгебра вычислимо перечислима и потому конечна (т.к. $\omega\setminus\alpha$ иммунно). Пусть прообраз $A_0$ (при естественном гомоморфизме заданном нумерацией $\nu:\omega\longrightarrow A$, где $\nu(x)=x/\eta_\alpha$) есть $\gamma\subset\omega\setminus\alpha$. По лемме 3.8.1 существует такое конечное расширение $\delta\supset\gamma$, что $\gamma\subset\delta\subset\omega\setminus\alpha$ и эквивалентность $\eta_{\omega\setminus\delta}$ является конгруэнцией конечного индекса алгебры $A=\langle\omega/\eta_\alpha;F\rangle$. Очевидно, что эта конгруэнция различает подалгебру $A_0$ и элемент $a=\alpha$. 

2. $a\in\omega\setminus\alpha$. По лемме 3.8.1 существует такое конечное $\delta\subset\omega\setminus\alpha$, что $\{a\}\subset\delta$ и все функции из $F$ согласованы с эквивалентностью $\eta_{\omega\setminus\delta}$. Тогда образ $a$ в конечной фактор-алгебре $\langle\omega/\eta_{\omega\setminus\delta};F\rangle$ не ''склеивается'' ни с каким элементом не только $A_0$, но даже и $A\setminus\{a\}$. 

(2)$\Rightarrow$(1). Аналогично предложению 3.3.
\end{proof}
Покажем теперь, что свойство равномерности в формулировке теоремы 3.5 также является существенным, т.е. для вычислимо отделимых эквивалентностей не являющихся равномерными эта теорема не имеет места. Из предложения 3.8 следует, что в классе эквивалентностей вида $\eta_\alpha$ таких контпримеров нет. Поэтому построение вычислимо отделимой эквивалентности с иммунной характеристической трансверсалью, над которой представима не локально финитная алгебра сопряжено с рассмотрением эквивалентностей более сложного вида.
\par\smallskip
\textbf{Теорема 3.9.} {\em Существует такая вычислимо отделимая эквивалентность $\eta$ с иммунной характеристической трансверсалью, которая является ядром представления подходящей универсальной алгебры, не являющейся локально финитно отделимой.}
\begin{proof}
Будем строить нужную эквивалентность и алгебру в два этапа. Сначала построим конечно порожденную алгебру $A=\langle\omega/\eta_\alpha;f,g\rangle$, где $\alpha$  -- множество с иммунным дополнением, а затем определим алгебру $A^\ast=\langle\omega/\eta^\ast_\alpha;f^\ast,g^\ast,h^\ast\rangle$, где $f^\ast,g^\ast$ -- одноместные вычислимые функции, строящиеся по $f,g$ соответственно, а $h^\ast$ -- вычислимая бинарная функция. При этом $tr(\eta^\ast_\alpha)$ будет иммунной, а $A^\ast$ -- не локально финитно отделимой.
\par\smallskip
В работе \cite{12} построена конечно порожденная $\eta_\alpha$-алгебра с иммунной характеристической трансверсалью. Обозначим ее через $A=\langle\omega/\eta_\alpha;c,f,g\rangle$, где $c$ -- порождающий элемент, а $f,g$ -- две одноместные вычислимые функции. Можно считать, что порождающий элемент $c$ не принадлежит объединению областей значений функций $f$ и $g$. При этом, класс $\alpha$ эквивалентности $\eta_\alpha$ является неподвижной точкой по модулю $\eta_\alpha$ как для $f$, так и для $g$, а порождающий элемент $c$ очевидно лежит в $\omega\setminus\alpha$.

Напомним, что $\eta^*_\alpha=\{\langle x,y\rangle|\gamma_x\smallsetminus\alpha=\gamma_y\smallsetminus\alpha\}$, где $\gamma$ -- каноническая нумерация конечных множеств.

Перейдем теперь к построению такой нумерованной алгебры $\langle\omega/\eta^\ast_\alpha;f^\ast,g^\ast,h^\ast\rangle$, которая не является локально финитно отделимой, но, при этом, характеристическая трансверсаль $tr(\eta^\ast_\alpha)$ иммунна. 

Пусть $\gamma$ -- каноническая нумерация конечных множеств. Тогда $tr(\eta^\ast_\alpha)$ -- иммунное множество (в противном случае наличие бесконечного вычислимо перечислимого подмножества $tr(\eta^\ast_\alpha)$ противоречит иммунности $\omega\setminus\alpha$, т.к. конечные множества, $\gamma$-номера которых лежат в $tr(\eta^\ast_\alpha)$ не пересекаются с $\alpha$). Покажем, что над $\eta^\ast_\alpha$ представима конечно порожденная алгебра. Для этого определим три вычислимые функции $f^\ast,g^\ast,h^\ast$: $$f^\ast(x)=\gamma^{-1}\{f(n)\mid n\in\gamma_x\};$$ $$g^\ast(x)=\gamma^{-1}\{g(n)\mid n\in\gamma_x\};$$ $$h^\ast(x,y)=\gamma^{-1}(\gamma_x\cup\gamma_y).$$
Покажем, что эти функции согласованы с $\eta^\ast_\alpha$. Пусть $x=y\pmod{\eta^\ast_\alpha}$. По определению $\gamma_x\setminus\alpha=\gamma_y\setminus\alpha$. Обозначим через $\sigma$ множество $\gamma_x\setminus\alpha$, тогда $$f^\ast(x)=\gamma^{-1}\{f(n)\mid n\in\sigma\}\pmod{\eta^\ast_\alpha},$$ т.к. $f$ тождественна на $\alpha$ по модулю $\eta_\alpha$. Аналогично, $$f^\ast(y)=\gamma^{-1}\{f(n)\mid n\in\sigma\}\pmod{\eta^\ast_\alpha},$$
т.е. $f^\ast(x)=f^\ast(y)\pmod{\eta^\ast_\alpha}$.

Для $g^\ast$ рассуждаем точно так же.

Пусть $x=u\pmod{\eta^\ast_\alpha}$ и $y=v\pmod{\eta^\ast_\alpha}$, т.е. $\gamma_x\setminus\alpha=\gamma_u\setminus\alpha$ и $\gamma_y\setminus\alpha=\gamma_v\setminus\alpha$. Тогда $\gamma_x\cup\gamma_y\setminus\alpha=\gamma_u\cup\gamma_v\setminus\alpha$, т.е. $h^\ast$ также согласована с $\eta^\ast_\alpha$.

Покажем, что корректно определенная фактор-алгебра $\langle\omega/\eta^\ast_\alpha;f^\ast,g^\ast,h^\ast\rangle$ конечно порожденная. Для этого зафиксируем $\gamma$-номер одноэлементного множества $\{c\}$, где $c$ -- порождающий элемент алгебры $\langle\omega;f,g\rangle$. Пусть $\gamma^{-1}(\{c\})=c^\ast$. Через $h^\ast(x_1,\dots,x_m)$ обозначим суперпозицию 
$$h^\ast(x_1,h^\ast(x_2,\dots,h^\ast(x_{m-1},x_m))\dots).$$
Если $n=\gamma^{-1}(\{k_0,\dots,k_l\})$ и $k_i=t_i(c)$, где $t_i$ -- $(f,g)$-терм, то $\gamma^{-1}(\{k_i\})=t^\ast_i(c^\ast)$, где $t^\ast_i(c^\ast)$ -- результат замены в $(f,g)$-терме $t_i$ символа $f$ на $f^\ast$, $g$ на $g^\ast$. Тогда $$h^\ast(t^\ast_0(c^\ast),\dots,t^\ast_l(c^\ast))=n,$$
т.е. алгебра $\langle\omega/\eta^\ast_\alpha;f^\ast,g^\ast,h^\ast\rangle$ конечно порожденная.

Наконец, убедимся в том, что алгебра $A^\ast$ является не локально финитно отделимой. Для этого докажем следующее вспомогательное утверждение
\par\smallskip
\textbf{Лемма 3.9.1.} {\em Стандартная нумерация всякой конечной алгебры конечной сигнатуры является вычислимой.}
\begin{proof}
Напомним, что нумерация универсальной алгебры называется стандартной, если она является наименьшей относительно сводимости (классов эквивалентных) нумераций этой алгебры (см. А.И.Мальцев \cite{5}). Пусть конечная алгебра $B$ конечной сигнатуры $\Sigma_0$ порождается множеством элементов $\{b_1,\dots,b_n\}$. Рассмотрим абсолютно свободную $\Sigma_0$-алгебру $T_{\Sigma_0}(X)$ от свободных порождающих $X=\{x_1,\dots,x_n\}$ и построим отображение $\varphi_0:\{x_1,\dots,x_n\}\longrightarrow\{b_1,\dots,b_n\}$, полагая $\varphi(x_i)=b_i,\;1\leqslant i\leqslant n$. Тогда $\varphi_0$ единственным образом продолжается до гомоморфизма $\varphi$ из $T_{\Sigma_0}(X)$ на $B$. Тем самым определена стандартная ''нумерация'' $\varphi$ из алгебры $T_{\Sigma_0}(X)$ на алгебру $B$ (см. замечание 3.7). Обогатим $\Sigma_0$ конечным множеством константных символов $C=\{c_1,\dots,c_n\}$ и рассмотрим конечную алгебру $T_\Sigma(C)$, порожденную сигнатурными константами, в сигнатуре $\Sigma=\Sigma_0\bigcup C$. 

Введем отношение $\equiv_B$ на множестве $T_\Sigma^2(C)$, полагая $t_1\equiv_B t_2\Leftrightarrow\varphi(t_1)=\varphi(t_2)$. Тогда $\equiv_B$ -- конгруэнция алгебры $T_\Sigma(C)$ и фактор-алгебра $T_\Sigma(C)/\equiv_B$ изоморфна $B$. Следуя А.И.Мальцеву (\cite{5}) определим функцию высоты терма $h:T_\Sigma(C)\longrightarrow\omega$ индуктивно по сложности терма:

- если $t$ константа, т.е. $t=c\in C$, то $h(t)=0$;

- если $t=f(t_1,\dots,t_n)$, где $f\in\Sigma$ -- $n$-арный функциональный символ ($n\geqslant 1$), то $h(t)=\max\{h(t_1),\dots,h(t_n)\}+1$.

Нетрудно понять, что $\Sigma$-алгебра $B$ конечной сигнатуры, порожденная множеством сигнатурных констант, конечна тогда и только тогда, когда для некоторого натурального $n$ всякий  $T_\Sigma(C)$-терм высоты $n$ равен (в $B$) некоторому $T_\Sigma(C)$-терму строго меньшей высоты. Зафиксируем наименьшее такое $n$ и определим множество $E$ всех равенств вида $t_1=\tau_1,\dots,t_m=\tau_m$ (где $t_1,\dots,t_m$ -- все $T_\Sigma(C)$-термы высоты $n$, а $\tau_1,\dots,\tau_m$ -- подходящие $T_\Sigma(C)$-термы высоты меньше чем $n$), которые верны в $B$. Очевидно, что инициальная (т.е. свободная без свободных порождающих в многообразии алгебр, заданном конечным множеством тождеств $E$) алгебра $T_\Sigma(C)/E$ для системы тождеств $E$ является гомоморфным прообразом алгебры $B$ (этот гомоморфный прообраз -- инициальная алгебра в многообразии заданном тождествами $E$). Добавим к $E$ все равенства между всеми $T_\Sigma(C)$-термами высоты менее $n$  и получим конечное расширение $E^\ast$ множества тождеств $E$. Т.к. каждый элемент алгебры $B$ представлен некоторым $T_\Sigma(C)$-термом высоты менее чем $n$, то инициальная система для $E^\ast$ изоморфна $B$ (если $t_1\neq t_2$ в $T_\Sigma(C)/E$, но $t_1=t_2$ в $B$, то выбираем $\tau_1=t_1,\tau_2=t_2,h(\tau_1)<n,h(\tau_2)<n$ и присоединяем равенство $\tau_1=\tau_2$ к $E$; существование таких $\tau_1,\tau_2$ очевидно, т.к. в каждом классе эквивалентных замкнутых термов есть терм высоты менее $n$). Таким образом, инициальная алгебра для $E^\ast$ изоморфна алгебре $B$. В силу конечной определенности в многообразии, заданном тождествами $E^\ast$, стандартная нумерация алгебры $B$ позитивна, а в силу конечности этой алгебры -- вычислима. 
\end{proof}
Заметим, что всякая неодноэлементная алгебра имеет нумерацию, не являющуюся вычислимо отделимой (\cite{25}), поэтому в лемме 3.9.1 стандартность нумерации существенна. 

Допустим, что $A^\ast$ локально финитно отделима. В алгебре $A=\langle\omega/\eta_\alpha;f,g\rangle$ элемент $c$ является порождающим, причем  он является единственным элементом, в который не переводится никакой элемент ни функцией $f$, ни функцией $g$. В алгебре $A^\ast=\langle\omega/\eta^\ast_\alpha;f^\ast,g^\ast,h^\ast\rangle$ канонический индекс множества $\{c\}$ также является порождающим элементом для $A^\ast$. Рассмотрим подалгебру $A^\ast_0$ алгебры $A^\ast$, основное множество которой совпадает с $\omega/\eta^\ast_\alpha\setminus\{c^\ast\}$, где $c^\ast=\gamma^{-1}(\{c\})/\eta^\ast_\alpha$, а порождающими являются $\gamma^{-1}(\{f(c)\})$ и $\gamma^{-1}(\{g(c)\})$. Ясно, что основное множество этой подалгебры совпадает с $A^\ast\setminus\{c^\ast\}$. Если $A^\ast$ локально финитно отделима, то в некоторой конечной фактор-алгебре алгебры $A^\ast$ образ элемента $c^\ast$ не принадлежит образу $A^\ast_0$. Но в этом факторе, по лемме 3.9.1, каждый класс эквивалентных замкнутых термов, в т.ч. и содержащий элемент $c^\ast$, вычислим.  

Назовем терм, составленный из функциональных символов $f,g$ от порождающего элемента $c$ в алгебре $\langle\omega/\eta_\alpha;f,g\rangle$ (не путать с $f^\ast,g^\ast$-символами и $\gamma$-номером множества $\{c\}$ в алгебре $\langle\omega/\eta^\ast_\alpha;f^\ast,g^\ast,h^\ast\rangle$), $\alpha$-термом, если его значение попадает в множество $\alpha$. Нетрудно заметить, что $\gamma$-номер любого $\alpha$-терма равен по модулю $\eta^\ast_\alpha$ $\gamma$-номеру пустого множества. Поэтому для любого $\alpha$-терма $t$ имеем 
$$\gamma^{-1}(\{c\})=h^\ast(\gamma^{-1}(\{c\}),\gamma^{-1}(\{t\}))\pmod{\eta^\ast_\alpha}\Leftrightarrow t\in\alpha.$$ Если допустить, что элемент $c^\ast$ и подалгебра $A^\ast_0$ различаются некоторой конгруэнцией конечного индекса, то по лемме 3.9.1 в фактор-алгебре по этой конгруэнции  элемент $c^\ast=\gamma^{-1}(\{c\})$ вычислим, но тогда и $\alpha$ вычислимо. Противоречие. 
\end{proof}
В частности, существует такая вычислимо отделимая эквивалентность с иммунной характеристической трансверсалью, над которой представима не финитно отделимая алгебра.
\par\smallskip
Таким образом, в условиях теоремы 3.5 нельзя отказаться как от алгебраического свойства локальности для финитной отделимости (предложение 3.6), так и от алгоритмического свойства равномерности для вычислимой отделимости (теорема 3.9). 
\par\smallskip
Заметим, что для неэффективно бесконечной вычислимо отделимой эквивалентности $\eta$ всякая $\eta$-алгебра финитно аппроксимируема, т.к. $tr(\eta)$ иммунна. Возможны ли такие эффекты для эффективно бесконечных эквивалентностей? Теорема 3.9 дает ответ.
\par\smallskip
\textbf{Следствие 3.10.} {\em Существует такая вычислимо отделимая эффективно бесконечная эквивалентность, что всякая представимая над ней алгебра финитно аппроксимируема.}
\par\smallskip
Действительно, таковой будет  эквивалентность $\eta^\ast_\alpha$ из теоремы 3.9, т.к. ее характеристическая трансверсаль иммунна, но, тем не менее, эта эквивалентность эффективно бесконечна.   

В следующем разделе мы приведем полное решение данного вопроса.
\par\smallskip
Сужая класс иммунных характеристических трансверсалей до гипериммунных и расширяя класс равномерно вычислимо отделимых эквивалентностей до класса вычислимо отделимых эквивалентностей получаем   
\par\smallskip
\textbf{Предложение 3.11.} {\em Пусть $\eta$ -- вычислимо отделимая эквивалентность с гипериммунной характеристической трансверсалью. Тогда всякая $\eta$-алгебра конечной сигнатуры локально финитно отделима.}
\begin{proof}
В данном случае всякая $\eta$-алгебра локально конечна (\cite{6}). Если $A_0$ -- конечно порожденная подалгебра $\eta$-алгебры $A$, то $A_0$ конечна. Допустим, что $ a\in A\setminus A_0$ и $A_0=\{a_1,\dots,a_n\}$. Зафиксируем некоторые $\nu$-номера этих элементов (подразумевается естественная нумерация $\nu(x)=x/\eta$): $k=\nu^{-1}(a)$ и $k_1=\nu^{-1}(a_1),\dots,k_n=\nu^{-1}(a_n)$. Тогда в алгебре $A$ выполнены неравенства $\nu k\neq\nu k_i\;(1\leqslant i\leqslant n)$. Имеем $n$ негативных конгруэнций, пересечение которых негативно и реализует вышеуказанное множество неравенств, т.е. фактор по этой конгруэнции различает элемент $a$ и подалгебру $A_0$, но индекс этой конгруэнции конечен, т.к. $tr(\eta)$ иммунна. 
\end{proof}
Приведем одну алгебраическую характеризацию вычислимо отделимых эквивалентностей.
\par\smallskip
\textbf{Предложение 3.12.} {\em Для бесконечной вычислимо отделимой эквивалентности $\eta$ следующие условия равносильны:

1) $\eta$ имеет бесконечное вычислимое расширение;

2) существует не финитно аппроксимируемая $\eta$-алгебра.}
\begin{proof}
1)$\Rightarrow$2). Определим над подходящим вычислимым расширением эквивалентности $\eta$ алгебру предшествования как в предложении 3.3.

2)$\Rightarrow$1). Допустим, что $\langle\omega/\eta;\Sigma\rangle$ -- не финитно аппроксимируемая $\eta$-алгебра эффективной сигнатуры $\Sigma$. По условию, существует пара различных элементов, отождествляемых любой конгруэнцией конечного индекса. Однако, существует негативная когруэнция $\eta^\ast$, по модулю которой эти элементы различны. Индекс этой конгруэнции необходимо бесконечен. По предложению 2.16 эквивалентность $\eta^\ast$ имеет бесконечное вычислимое расширение. 
\end{proof}


\section{Финитная аппроксимируемость}

Из предложения 3.6 следует, что иммунность характеристической трансверсали вычислимо отделимой эквивалентности (более того -- даже равномерно вычислимо отделимой эквивалентности) не является достаточным условием финитной отделимости любой алгебры, представимой над этой эквивалентностью. Аналогично, теорема 3.9 демонстрирует, что это же условие не является достаточным для локально финитной отделимости всякой алгебры, представимой над данной эквивалентностью. Иначе обстоит дело с финитной аппроксимируемостью. Из теоремы 1.2 о негативной аппроксимируемости следует, что всякая универсальная алгебра, представимая над эквивалентностью с иммунной характеристической трансверсалью является финитно аппроксимируемой. Возникает принципиальный вопрос. Верно ли обратное, т.е. является ли характеристическая трансверсаль бесконечной вычислимо отделимой эквивалентности, над которой представимы только финитно аппроксимируемые универсальные алгебры, иммунной? По теореме 3.5 для равномерно вычислимо отделимых эквивалентностей это так. Покажем, что в общем случае финитная аппроксимируемость любой алгебры, представимой над заданной бесконечной вычислимо отделимой эквивалентностью не является достаточным условием для иммунности характеристической трансверсали этой эквивалентности. Докажем гораздо более сильное утверждение, которому предпошлем некоторые необходимые определения.
\par\smallskip
\textbf{Определение 4.1.} {\em Эквивалентность называется неэлиминируемой, если число ее смежных классов конечно и ровно один смежный класс бесконечен.}  
\par\smallskip
Эквивалентность, не являющуюся неэлиминируемой назовем элиминируемой. Таким образом, любая элиминируемая эквивалентность либо бесконечна, либо содержит по крайней мере два бесконечных смежных класса. Пусть  $\mathbb{W}$ -- семейство всех негативных элиминируемых эквивалентностей и $\mathbb{W}=\{W_0,W_1,\dots\}$ -- некоторый фиксированный пересчет этого семейства. 
\par\smallskip
\textbf{Теорема 4.2.} {\em Пусть $\alpha$ -- бесконечное и кобесконечное множество, содержащее число $0$. Тогда существует такая эквивалентность $\eta$, каждый $\eta$-класс которой конечен, что $tr(\eta)=\alpha$ и всякая $\eta$-алгебра финитно аппроксимируема.}   
\begin{proof}
Пусть $\alpha=\{0=a_0<a_1<\dots\}$ -- бесконечное подмножество $\omega$ с бесконечным дополнением $\beta=\{b_0<b_1<\dots\}$. 

Дадим вначале неформальное описание. Шаг $s+1$ нашей неэффективной диагональной конструкции будет посвящен тому, что как строящаяся эквивалентность, так и все ее факторы (т.е. эквивалентные расширения) будут отличны от текущей негативной элиминируемой эквивалентности $W_s$. Для этого на шаге $s+1$ мы ''склеим'' подходящую пару элементов из $W_s$, соблюдая некоторые условия. На шаге $s+1$ будем также строить  конечный фрагмент $\eta_{s+1}$ эквивалентности $\eta$, которая определяется как предельное объединение этих фрагментов. Через $\omega_s$ будем обозначать некоторый начальный сегмент множества всех натуральных чисел, участвующих в определении $\eta_s$, т.е. $\omega_s=\{x\mid\exists y(\langle x,y\rangle\in\eta_s)\}$. 
\par\smallskip
Шаг $0$. $\eta_0=\emptyset,\omega_0=\emptyset$.
\par\smallskip
Шаг $s+1$. Для каждого числа $x$ назовем следующим за ним числом $x+1$. Для числа $x+1$ число $x$ назовем предыдущим.

Выберем такую пару различных по модулю $W_s$ элементов $a,b$, что

(1) $a<b$;

(2) $a\in\alpha,b\in\beta$;

(3) $\max\omega_s<a$.

Допустим, что такая пара $\langle a,b\rangle$ существует. Тогда полагаем

$$\omega_{s+1}=\{0,\dots,b\},$$
а в качестве $\eta_{s+1}$ выбираем такую наименьшую эквивалентность на множестве $\omega_{s+1}$, которая расширяет $\eta_s$, содержит пару $\langle a,b\rangle$, а также для всякого числа $z\in(\omega_{s+1}\setminus\omega_s)\cap\beta$, такого, что $a_l<z<a_{l+1}$ для некоторого $l$, отнесем пару $\langle a_l,z\rangle$ к $\eta_{s+1}$, кроме следующих двух особых случаев.

1. Если $m=\min(\omega_{s+1}\setminus\omega_s)$ есть число из $\beta$, то полагаем $m=\max\omega_s\pmod{\eta_{s+1}}$, т.е. мы ''склеиваем'' элемент из $\beta$ (наименьший в $\omega_{s+1}\setminus\omega_s$) с наибольшим числом из $\omega_s$.

2. Рассмотрим особый случай для пары $\langle a,b\rangle$. Пусть $b_0$ такой элемент из $\beta$, что предыдущий для $b_0$ элемент лежит в $\alpha$, а все следующие за $b_0$ вплоть до $b$ лежат в $\beta$, т.е. все числа из отрезка $b_0,b_0+1,\dots,b$ лежат в $\beta$. Все числа из этого отрезка объявляем $\eta_{s+1}$-эквивалентными числу $a$, а число $b_0-1$ -- наибольшее число из отрезка $[m,b]$ лежащее в $\alpha$ образует одноэлементный класс $\eta_{s+1}$-эквивалентности.

Таким образом, если существует пара $\langle a,b\rangle$ со свойствами (1)--(3), то шаг $s+1$ корректно завершается с занесением всех чисел из $\alpha$ на отрезке $[0,b]$ в характеристическую трансверсаль эквивалентности $\eta_{s+1}$ и при этом никакой элемент из $\beta$ на отрезке $[0,b]$ в нее не попадает.      

Конец шага $s+1$.

Определим $$\eta=\bigcup_{s\in\omega}\eta_s.$$

Покажем, что эквивалентность $\eta$ и будет удовлетворять условиям теоремы. Прежде всего убедимся в справедливости следующего утверждения.

\par\smallskip
\textbf{Лемма 4.2.1.} {\em Пусть $\gamma=\{c_0<c_1<\dots\}$ -- бесконечное подмножество $\omega$ с бесконечным дополнением $\delta=\{d_0<d_1<\dots\}$ и $E$ -- элиминируемая эквивалентность на $\omega$. Тогда существуют такие $c\in\gamma$ и $d\in\delta$, что $c<d$ и $c\neq d\pmod E$.}
\begin{proof}
Выбираем любой элемент $c_k$ из $\gamma$ и обозначим через $D$ класс $E$-эквивалентности элемента $c_k$. Предположим, что не существует больших чем $c_k$ элементов из $\delta$, которые не равны $c_k$ по модулю $E$. Тогда почти все элементы из $\delta$ (за исключением, быть может, конечного подмножества $\delta$) лежат в $D$. Если $E$ имеет бесконечное число смежных классов, то почти все они целиком лежат в $\gamma$. Берем любое число $c$ из какого-то класса вне $D$ и выбираем в $\delta$ (которое почти целиком лежит в $D$) число $d$ большее чем $c$. Если же классов конечное число, то, в силу элиминируемости $E$, найдется по крайней мере еще один бесконечный смежный класс $E$-эквивалентности, скажем $C$, в котором содержится бесконечное число элементов из $\gamma$. Выбираем любое $c\in C$ и большее чем $c$ число $d$ из $\delta\subseteq D$. Таким образом, в любом случае  найдется пара элементов $c,d$ со свойством $c\in\gamma,d\in\delta,c<d,c\neq d\pmod E$.     
\end{proof}
\par\smallskip

Из леммы 4.2.1 немедленно следует, что для каждого шага $s+1$ найдутся такие $a,b$, различные по модулю $W_s$, что $\max\omega_s<a<b$, $a\in\alpha$ и $b\in\beta$ и при этом все элементы из $\alpha$ трансверсальны (ни один элемент из $\beta$ не трансверсален), т.е. каждый шаг конструкции корректно завершается. Заметим, что тривиальным фактом является то обстоятельство, что если элемент не принадлежит характеристической трансверсали эквивалентности $\eta_s$, то таковым же он остается и для любого расширения этой эквивалентности. Гораздо более тонкое свойство заключается в том, что все элементы из $\alpha$ сохраняют свойство быть трансверсальными для предельного расширения $\eta$ эквивалентностей $\eta_s$. 

\par\smallskip
\textbf{Лемма 4.2.2.} {\em $tr(\eta)=\alpha$.}
\begin{proof}
В конце шага $s+1$ эквивалентность $\eta_{s+1}$ не ''склеивает'' никакой элемент из $\alpha\cap\omega_{s+1}$ ни с каким строго меньшим числом, т.е. все числа из $\alpha\cap\omega_{s+1}$ не $\eta$-эквивалентны никаким меньшим. Значит $\alpha\subseteq tr(\eta)$. С другой стороны, всякое число из $\beta$ к концу подходящего шага ''склеивается'' с некоторым меньшим числом из $\alpha$. Следовательно, $\beta\cap tr(\eta)=\emptyset$, откуда следует, что $tr(\eta)=\alpha$. 
\end{proof}
\par\smallskip

\textbf{Лемма 4.2.3.} {\em $\eta\neq W_s$ для любого $s\in\omega$. Более того, если $\eta^\ast$ -- расширение $\eta$, то $\eta^\ast$ также отлична от $W_s$.}
\begin{proof}
По определению шага $s+1$ в эквивалентность $\eta$ добавляется пара $\langle a,b\rangle$, различных по модулю $W_s$ элементов. Очевидно, что эти элементы равны по модулю любого расширения $\eta$. 
\end{proof}
Таким образом, для эквивалентности $\eta$ все $\eta$-классы конечны (т.е. $\eta$ тривиально вычислимо отделима), $tr(\eta)=\alpha$ и всякое негативное расширение $\eta$ имеет конечный индекс. По теореме 1.2 о негативной аппроксимируемости всякая $\eta$-алгебра аппроксимируется негативными, но всякий негативный фактор конечен. Следовательно, всякая $\eta$-алгебра финитно аппроксимируема. 
\end{proof}
\textbf{Замечание 4.3.} По теореме о негативной аппроксимируемости вычислимо отделимых алгебр (теорема 1.2) любая $\eta$-алгебра аппроксимируется негативными, т.е. имеет полную разделяющую систему негативных факторов. Но всякий негативный фактор по $\eta$ (для $\eta$ из теоремы 4.2) есть неэлиминируемая негативная эквивалентность -- с конечным числом смежных классов, из которых в  точности один класс бесконечен. Очевидно, что любая такая эквивалентность -- негативная (даже вычислимая) эквивалентность конечного индекса. Даже если бы мы рассматривали в качестве $\mathbb{W}$ семейство всех негативных эквивалентностей (включая неэлиминируемые) и, в случае отсутствия подходящей пары элементов $a,b$ различных по модулю $W_s$, пропускали бы соответствующий шаг, то результат был бы таким же. Некоторые неэлиминируемые эквивалентности, возможно, удалось бы ''ликвидировать'' в качестве кандидатов на негативные факторы эквивалентности $\eta$. Однако, большое (полное разделяющее) семейство эквивалентностей элиминировать не удалось бы. Это семейство состоит в точности из тех собственных факторов построенной эквивалентности $\eta$, которые имеют конечные индексы и обладают ровно одним бесконечным смежным классом. Этот факт обуславливает важность эквивалентностей типа $\eta_\alpha$ для коиммунных $\alpha$, т.к. негативные факторы таких эквивалентностей являются конечными и неэлиминируемыми.  
\par\smallskip     
\textbf{Следствие 4.4.} {\em Существует такая бесконечная вычислимо отделимая эквивалентность $\eta$ с вычислимой характеристической трансверсалью, что всякая $\eta$-алгебра финитно аппроксимируема.}
\par\smallskip     
\textbf{Следствие 4.5.} {\em Существует бесконечная вычислимо отделимая эквивалентность с вычислимой характеристической трансверсалью, всякое негативное расширение которой конечно и имеет ровно один бесконечный класс.}


\bigskip
\begin{thebibliography}{30} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).
	
\bibitem{1} Yu.L. Ershov, 
{\it The Theory of Enumerations [in Russian]}, Nauka, Moscow, 1977.

\bibitem{2} A.I. Mal'tsev, 
{\it Algebraic Systems [in Russian]}, Nauka, Moscow, 1970.

\bibitem{3} H.D.Rogers, 
{\it Theory of Recursive Functions and Effective Computability [in Russian]}, Mir, Moscow, 1972.

\bibitem{4} S.S. Goncharov, Yu.L. Ershov,
{\it Constructive Models}, Ser. Siberian School of Algebra and Logic, Kluwer Academic/Plenum Publishers, New York, etc., 2000.

\bibitem{5} A.I. Mal'tsev,  
{\it Constructive algebras. I}, Russian Math. Surveys, \textbf{16}:3 (1961), 77--129.

\bibitem{6} N.Kh. Kasymov,  
{\it Recursively separable enumerated algebras}, Russian Math. Surveys, \textbf{51}:3 (1996), 509--538.

\bibitem{7} N.Kh. Kasymov, R.N. Dadazhanov, F.N. Ibragimov,
{\it Separable Algorithmic Representations of Classical Systems and Their Applications}, Contemporary Mathematics. Fundamental Directions, \textbf{67}:4 (2021), 707--754.

\bibitem{8} N.Kh. Kasymov, 
{\it Positive algebras with congruences of finite index}, Algebra and logic, \textbf{30}:3 (1991), 190--199.

\bibitem{9} N.Kh. Kasymov, 
{\it Positive algebras with Noetherian congruence lattices}, Siberian Mathematical Journal, \textbf{33}:2 (1992), 338--341.

\bibitem{10} N.Kh. Kasymov, 
{\it Positive algebras with countable congruence lattices}, Algebra and logic, \textbf{31}:1 (1992), 12--23.

\bibitem{11} J.A. Bergstra, J.V. Tucker,
{\it A characterization of computable data types by means of a finite, equational specification method}, Lecture Notes in Comput.Sci., \textbf{85} (1980), 76--90.

\bibitem{12} N.Kh. Kasymov, 
{\it Algebras with finitely approximable positively representable enrichments}, Algebra and logic, \textbf{26}:6 (1987), 441--450.

\bibitem{13} N.Kh. Kasymov, 
{\it Enumerated algebras with uniformly recursive-separable classes}, Siberian Mathematical Journal, \textbf{34}:5 (1993), 869--882.

\bibitem{14} N.Kh. Kasymov, 
{\it Homomorphisms on negative algebras}, Algebra and logic, \textbf{31}:2 (1992), 81--89.

\bibitem{15} N.Kh. Kasymov, 
{\it Separation axioms and partitions of the set of natural numbers}, Siberian Mathematical Journal, \textbf{34}:3 (1993), 468--471.

\bibitem{16} N.Kh. Kasymov, 
{\it Homomorphisms onto effectively separable algebras}, Siberian Mathematical Journal, \textbf{57}:1 (2016), 36--50.

\bibitem{17} N.Kh. Kasymov, R.N. Dadazhanov,  
{\it Negative dense linear orders}, Siberian Mathematical Journal, \textbf{58}:6 (2017), 1015--1033.

\bibitem{18} A.S. Morozov, J.K. Truss,
{\it On computable automorphisms of the rational numbers}, J. Symbolic Logic, \textbf{66}:3 (2001), 1458--1470.

\bibitem{19} N.Kh. Kasymov, A.S. Morozov, 
{\it Definability of linear orders over negative equivalences}, Algebra and logic, \textbf{55}:1 (2016), 24--37.

\bibitem{20}  R.N. Dadazhanov, N.Kh. Kasymov, I.A. Khodzhamuratova, 
{\it Uniformly computably separable algebras with effectively splittable families of negative congruences},Siberian Mathematical Journal, \textbf{63}:3 (2022), 466--475.

\bibitem{21} N.Kh. Kasymov,   
{\it Algebras over negative equivalences}, Algebra and logic, \textbf{33}:1 (1994), 46--48.

\bibitem{22} N.Kh. Kasymov, A.S. Morozov
{\it Lower semilattices of separable congruences of numbered algebras}, Siberian Mathematical Journal (in print)

\bibitem{23} N.Kh. Kasymov, A.S. Morozov, I.A. Khodzhamuratova, 
{\it $T_1$-separable enumarations of subdirectly indecomposable algebras}, Algebra and logic, \textbf{60}:4 (2021), 263--278.

\bibitem{24} N.Kh. Kasymov,   
{\it The number of Q-congruences in positive algebras}, Algebra and logic, \textbf{31}:3 (1992), 182--187.

\bibitem{25} N.Kh. Kasymov, F.N. Ibragimov,  
{\it Separable enumerations of division rings and effective embeddability of rings therin}, Siberian Mathematical Journal, \textbf{60}:1 (2019), 62--70.
\end{thebibliography}

\end{document}
