
\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[Равномерные $m$-эквивалентности]{Равномерные $m$-эквивалентности и нумерации классических систем}
\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}%

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

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

\thanks{\sc Kasymov N.Kh., Dadazhanov R.N., Zhavliev S.K.,
Uniform $m$-equivalencies and enumerations of classical systems}
\thanks{\copyright \ 2021 Касымов Н.Х., Дадажанов Р.Н., Джавлиев С.К.}
\thanks{\it Поступила 1 января 2015 г., опубликована 31 декабря 2015 г.}%

\semrtop \vspace{1cm}
\maketitle {\small

\begin{quote}
\noindent{\sc Abstract.} The paper considers the representability of algebraic structures (groups, lattices, semigroups, etc.) over equivalence relations on natural numbers. The concept of (uniform) $m$-equivalence is studied. It is proved that the numbering equivalence of any numbered group is uniform $m$-equivalence. On the other hand, an example is constructed of a uniform $m$-equivalence over which no group is representable. It is shown that the upper and lower semilattices are not representable over a perfect equivalence with a compressed characteristic transversal.
\medskip
	
\noindent{\bf Keywords:} uniform $m$-equivalence, group, lattice, field.
\end{quote}
}


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

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

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

Однако, наиболее общие алгоритмические представления (нумерации) групп, по-видимому еще не рассматривались, т.к. в наиболее общей постановке вопрос кажется труднообозримым. В настоящей работе вводится понятие равномерной m-эквивалентности и показывается, что ядро алгоритмического представления любой группы является равномерной m-эквивалентностью.

Вместе с тем, установлено, что далеко не всякая равномерная m-эквивалентность является ядром алгоритмического представления подходящей группы.

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

Отдельный пункт посвящен структурам степеней представимости колец и полей. 

С неопределяемыми понятиями можно ознакомиться в \cite{12,13,14}.

Далее, как для краткости, так и отдавая дань русскоязычной традиции в теории вычислимости, в значительной степени определившей появление данного направления теории алгоритмов, алгоритмические представления будем называть нумерациями.

Под словом эквивалентность понимается эквивалентность на множестве натуральных чисел $\omega$.

Для нумерации $\nu$ через $ker(\nu)$ будем обозначать нумерационную эквивалентность, которую, также для краткости, назовем ядром $\nu$.

Нумерацией $\nu$ универсальной алгебры $\mathfrak{A}=\langle A;F_0,F_1,\dots,\rangle$ называется такое отображение из множества натуральных чисел $\omega$ на $A$, для которого любая $m$-местная операция $F_n$, заданная на $A$, поддерживается такой подходящей вычислимой функцией $f_n$, что $\forall\overline{x}\in\omega^m[F_n(\nu(\overline{x})=\nu(f_n(\overline{x}))]$, т.е. $\mathfrak{A}$ изоморфна фактор-алгебре $\langle\omega;f_0,f_1,\dots,\rangle/ker(\nu)$ вычислимой алгебры $\langle\omega;f_0,f_1,\dots,\rangle$ по конгруэнции $ker(\nu)$.     

\begin{definition} 
	Универсальная алгебра называется представимой над эквивалентностью $\eta$, если существует ее нумерация с ядром $\eta$.       
\end{definition}

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

\begin{definition}\label{def2}
Эквивалентность $\eta$ называется $m$-эквивалентностью (равномерной $m$-эквивалентностью), если существует такое семейство $F$ вычислимых функций (перечислимое семейство $F$ вычислимых функций), индуцирующих перестановки фактор-множества $\omega/\eta$, что для всякой пары натуральных чисел $x,y$ найдется такая функция $f\in F$, которая $m$-сводит класс $\{x\}/\eta$ к классу $\{y\}/\eta$.       
\end{definition}

Тривиальными примерами равномерных $m$-эквивалентностей являются разрешимые эквивалентности.

\section{Группы}
	 
\begin{theorem}\label{theorem1}
	Если $(G,\nu)$ -- нумерованная группа, то ядро $ker(\nu)$ ее нумерации -- равномерная $m$-эквивалентность.
\end{theorem}	 

\begin{proof}
	Пусть $a,b\in G,a=\nu(k),b=\nu(l)$. Обозначим через $\eta$ ядро $ker(\nu)$. Очевидно, что отображение $\pi_{a,b}=\lambda x.[ba^{-1}x]$ -- перестановка на основном множестве группы $G$, переводящая элемент $a$ в $b$. Рассмотрим вычислимую функцию $f=\lambda x.[l\ast(k)^{-1}\ast x]$, где $\ast$ обозначает вычислимую операцию, представляющую в нумерации $\nu$ операцию умножения в группе $G$, а $()^{-1}$ -- вычислимую операцию, поддерживающую операцию взятия обратного элемента в группе $G$. Ясно, что функция $f$ поддерживает перестановку $\pi_{a,b}$ на $\nu$-номерах (т.е. $\pi_{a,b}\nu=\nu f$) и $m$-сводит класс $\{k\}/\eta$ к классу $\{l\}/\eta$. Чтобы показать равномерность достаточно сопоставить каждой паре $\langle k,l\rangle\in\omega^2$ функцию $f_{k,l}=\lambda x.[l\ast(k)^{-1}\ast x]$.  
\end{proof}

\textbf{Замечание 1.} Мы работаем в сигнатуре $\langle\cdot,^{-1}\rangle$, которая обеспечивает равномерность. В сигнатуре с одной бинарной групповой операцией $\langle\cdot\rangle$ теорема \ref{theorem1} верна в той части, которая утверждает, что ядро нумерации -- $m$-эквивалентность.
\par\smallskip

Отметим, что вычислимые перестановки, определяемые семейством $F$, не обязательно образуют группу, т.к. обратная перестановка может и не поддерживаться вычислимой на номерах функцией. Для позитивных нумераций это множество будет группой. Но уже в случае негативных нумераций можно указать вычислимые перестановки, обратные к которым вычислимыми не будут и потому эта оценка неулучшаема в иерархии Клини-Мостовского (см. \cite{15}).

В обзоре \cite{16} ставился вопрос: ''существует ли конечно-определенная алгебра (в частности группа), нумерационная эквивалентность стандартной нумерации которой предполная?''.

\begin{corollary}\label{cor1}
	Ни над какой предполной эквивалентностью не представима никакая группа.
\end{corollary}

\begin{proof}
	Перестановка $\pi_{a,b}$ на $G$ из теоремы \ref{theorem1} имеет неподвижную точку тогда и только тогда, когда $a=b$ (в этом случае она будет единичной), т.е. соответствующая представляющая вычислимая функция в случае $a\neq b$ не имеет неподвижных точек по модулю ядра представления и потому ядро не может быть предполной эквивалентностью. 
\end{proof}

Таким образом, не только не существует конечно-определенной группы с предполным позитивным ядром (т.к. необходимым условием конечной определенности алгебры является позитивность ее стандартной нумерации), но и предполно нумерованной группы любой алгоритмической сложности.

Теорема \ref{theorem1} порождает два естественных вопроса: 

-- насколько велик класс равномерных $m$-эквивалентностей?

-- является ли условие равномерности для $m$-эквивалентности достаточным для представимости над ней группы?

Семейство $F$ вычислимых функций назовем $m$-сводящим для эквивалентности $\eta$, если оно удовлетворяет условиям определения \ref{def2}. 

Пусть $f$ -- вычислимая перестановка на $\omega$. Обозначим $F_f=\{f^n|n\in Z\}$, где $Z$ множество целых чисел и $f^0(x)=x\;(x\in\omega),f^{-k}=(f^k)^{-1}\;(k\in\omega)$. Покажем, что класс равномерных $m$-эквивалентностей довольно велик.

\begin{proposition}\label{prop1}
	Для любой вычислимой перестановки $f$ без конечных циклов, разбивающей $\omega$ на бесконечное число орбит, существует континуум таких равномерных $m$-эквивалентностей, для которых вычислимое семейство $F_f$ является $m$-сводящим.
\end{proposition}

\begin{proof}
	По условию перестановка $f$ разбивает $\omega$ на множество орбит $O_f(x)=\{f^k(x)|k\in Z\}$. Определим $a_0=0, a_{n+1}=\min\{y|y\notin O_f(a_0)\cup\dots\cup O_f(a_n)\}$ (т.е. $a_k$ -- наименьшее число из своей орбиты) и $\leqslant_f$-упорядочим $f$-орбиты так, что все элементы орбиты $a_i$ предшествуют всем элементам орбиты $a_j$, если $a_i<a_j$. Внутри каждой орбиты полагаем $x\leqslant_f y\Leftrightarrow\exists k\geq 0(f^k(x)=y)$. Пусть $A=\{a_0<a_1<\dots\}$. Построим эквивалентность $\eta_0$, задав ее классами $\eta_0$-эквивалентности следующим образом: $M_0=A, M_{n+1}=f^{n+1}M_0,M_{-n-1}=f^{-n-1}M_0,n\in\omega$. Очевидно, что вычислимое семейство $F_f$ является $m$-сводящим для $\eta_0$. Будем строить семейство эквивалентностей, используя бинарное дерево, исходя из $\eta_0$. Неформально, эквивалентности $\eta_{01},\eta_{10},\eta_{11}$ строятся из $\eta_0=\eta_{00}$ путем ''сдвига'' всех $f$-орбит относительно $f$-орбиты $a_0$ на одну позицию вправо, если в индексе $\eta$ стоит $1$, т.е. $a_0=a_1\wedge a_1=f^{-1}(a_2)\pmod{\eta_{01}}$ и соответствующей ''склейкой'' всех образов и прообразов относительно $f$. Аналогично, $a_0=f^{-1}(a_1)a_1\wedge a_1=a_2\pmod{\eta_{10}}$ и $a_0=f^{-1}(a_1)\wedge a_1=f^{-1}(a_2)\pmod{\eta_{11}}$. Таким образом, если орбита $O_f(a_k)$ сдвигается относительно $a_{k-1}$ на одну позицию вправо, то все орбиты $O_f(a_l),l>k$ также сдвигаются ровно на одну позицию вправо. Опишем эту конструкцию строго.  
	
	Пусть $E=\{\overline{\varepsilon}=\varepsilon_0\varepsilon_1\dots|\varepsilon_i\in\{0,1\}\}$ -- множество всех счетно-бесконечных последовательностей из нулей и единиц и $\overline{\varepsilon}\in E$. Построим отображение из $\varphi: E\longrightarrow\Theta$, где $\Theta$ -- множество всех эквивалентностей на $\omega$ так, что для $i\in\omega$	
	$$
	\left\{
	\begin{array}{lcr}
	\varepsilon_i=0\Rightarrow a_i=a_{i+1}\pmod{\varphi(\overline{\varepsilon})},\\
	\varepsilon_i=1\Rightarrow a_i=f^{-1}(a_{i+1})\pmod{\varphi(\overline{\varepsilon})}.\\
	\end{array}
	\right.
	$$  
	
	При этом, если $x=y\pmod{\varphi(\overline{\varepsilon})}$, то все соответствующие $f$-образы и $f$-прообразы $x,y$ также будут равны по модулю $\varphi(\overline{\varepsilon})$ и $\varphi(\overline{\varepsilon})$ -- наименьшая эквивалентность с этим свойством.
	
	На языке $\varepsilon$-последовательностей $\eta_0=\varphi(00\dots),\eta_1=\varphi(10\dots)$ и т.д. Для эквивалентности $\varphi(11\dots)$ (в последовательности все единицы) $\forall i\in\omega(a_i=f^{-1}(a_{i+1})\pmod{\varphi(11\dots)})$. 
	
	Покажем, что $\varphi$ инъективно. Если $\overline{\varepsilon}^1\neq\overline{\varepsilon}^2$, то существует наименьшее $k$, для которого $\varepsilon^1_k\neq\varepsilon^2_k$. Пусть, для определенности $\varepsilon^1_k=0,\varepsilon^2_k=1$. Тогда $\langle a_k,a_{k+1}\rangle\in\overline{\varepsilon}^1\smallsetminus\overline{\varepsilon}^2$. Аналогично рассматривается случай $\varepsilon^1_k=1,\varepsilon^2_k=0$.
		
	По построению семейство $F_f$ является $m$-сводящим для любой эквивалентности из $\{\varphi(\overline{\varepsilon})|\overline{\varepsilon}\in E\}$. Из инъективности $\varphi$ следует континуальность последнего множества.
\end{proof}

\begin{proposition}\label{prop2}
	Если все классы эквивалентности $\eta$ разрешимы, то она является $m$-эквивалентностью.
\end{proposition}

\begin{proof}
	Если классы $\alpha=\{p\}/\eta$ и $\beta=\{q\}/\eta$ совпадают, то $m$-сведение осуществляет тождественная функция. Если же они различны, то вычислимая функция, отображающая класс $\alpha$ в точку $q$, класс $\beta$ в точку $p$ и тождественная на $\omega\smallsetminus(\alpha\cup\beta)$ -- искомая.
\end{proof}

\begin{proposition}\label{prop3}
	Если равномерная $m$-эквивалентность имеет хотя бы один разрешимый класс, то она разрешима.
\end{proposition}

\begin{proof}
	Пусть $\eta$ -- равномерная $m$-эквивалентность и $\eta$-класс $\beta$ разрешим. По условию существует перечислимое семейство $F$ $m$-сводящих функций. Очевидно, $x=y\pmod\eta\Leftrightarrow\exists f\in F[f(x)\in\beta\wedge f(y)\in\beta]$, т.е. $\eta$ позитивна. Аналогично, $x\neq y\pmod\eta\Leftrightarrow\exists f\in F[f(x)\in\beta\wedge f(y)\notin\beta]$, что обеспечивает негативность $\eta$.    
\end{proof}

\begin{corollary}\label{cor2}
	Если неразрешимая эквивалентность имеет хотя бы один разрешимый смежный класс, то над ней не представима никакая группа
\end{corollary}

Пусть $\eta$ -- эквивалентность. Множество $\alpha\subseteq\omega$ называется $\eta$-замкнутым, если $x\in\alpha\wedge x=y\pmod\eta\Rightarrow y\in\alpha$.

\begin{definition}\label{def3} 
	Эквивалентность $\eta$ называется вычислимо отделимой (отделимой), если для всяких различных по модулю $\eta$ натуральных чисел $x,y$ существует такое $\eta$-замкнутое вычислимое (перечислимое) множество $\alpha$, что $x\in\alpha$ и $y\notin\alpha$ ($(x\in\alpha\wedge y\notin\alpha)\vee(x\notin\alpha\wedge y\in\alpha)$).
\end{definition}

Рассмотрим следующие примеры эквивалентностей (см. \cite{13}, с.58, 174-175):

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

(2) $\eta_\alpha=\{\langle x,y\rangle|x,y\in\alpha\}\cup id\;\omega,\alpha\subseteq\omega$;

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

\begin{proposition}\label{prop4}
	Для всякого $\alpha\subseteq\omega$ имеет место:
	
	1. $\eta^\alpha$ -- $m$-эквивалентность. При этом, ее равномерность равносильна разрешимости $\alpha$.
	
	2. $\eta_\alpha$ является $m$-эквивалентностью тогда и только тогда, когда $\alpha$ разрешимо.
\end{proposition}

\begin{proof}
	1. По предложению \ref{prop2} для всякого $\alpha\subseteq\omega$ эквивалентность $\eta^\alpha$ -- $m$-эквивалентность, а по предложению \ref{prop3} ее равномерность влечет разрешимость.
	
	2. Очевидно, что для $\eta_\alpha$ вычислимая отображаемость класса $\alpha$ в любой другой класс требует разрешимости $\alpha$, т.к. все $\eta_\alpha$-классы (кроме, возможно, класса $\alpha$) одноэлементны.
\end{proof}

\begin{corollary}\label{cor4}
	Над $\eta^\alpha$ (как и над $\eta_\alpha$) представима группа тогда и только тогда, когда $\alpha$ разрешимо.
\end{corollary}

\begin{proposition}\label{prop5}
	Всякая пара смежных классов ядра неразрешимой позитивной нумерации любой группы является вычислимо изоморфной (т.е. для любой пары смежных классов ядра существует вычислимая перестановка на $\omega$, индуцирующая перестановку фактор-множества $\omega/\eta$, переводящая один из этих классов на другой). При этом, существует равномерно эффективно зависящая от $x,y$ процедура построения характеристического индекса вычислимого изоморфизма на $\omega$, являющегося перестановкой на $\omega/\eta$ и переводящего $\{x\}/\eta$ в $\{y\}/\eta$. 
\end{proposition}

\begin{proof}
	Пусть $\eta$ -- ядро неразрешимой позитивной нумерации группы. Согласно теореме \ref{theorem1} $\eta$ -- равномерная $m$-эквивалентность, а по предложению \ref{prop3} все $\eta$-классы невычислимы. Для данных $x,y$ найдем перестановку $f_0\in F$, осуществляющую $m$-сведение $\{x\}/\eta$ к $\{y\}/\eta$ и построим инъективную функцию $g_0$, совпадающую с $f_0$ по модулю $\eta$, следующим образом:
	
	Шаг $0$. $g_0(0)=f_0(0)$;
	
	Шаг $s+1$. Если $f_0(s+1)\notin\{g_0(0),g_0(1),\dots,g_0(s)\}$, то определим $g_0(s+1)=f_0(s+1)$. В противном случае, перечисляя класс $\{f_0(s+1)\}/\eta$ ищем первое $z$ отличное от всех $g_0(i)\;(0\leqslant i\leqslant s)$ и $\eta$-эквивалентное $f_0(s+1)$ (а такое $z$ обязательно найдется в силу бесконечности класса $\{f_0(s+1)\}/\eta$) и полагаем $g_0(s+1)=z$. Конец шага $s+1$.
	
	Следовательно, класс $\{x\}/\eta$ $1$-сводится к $\{y\}/\eta$ функцией $g_0$. Аналогично, найдем $f_1\in F$, $m$-сводящую $\{y\}/\eta$ к $\{x\}/\eta$ и построим для нее соответствующую инъективную вычислимую функцию $g_1$, совпадающую с $f_1$ по модулю $\eta$. Тогда $g_1$ $1$-сводит $\{y\}/\eta$ к $\{x\}/\eta$ и, таким образом, классы $\{x\}/\eta$ и $\{y\}/\eta$ лежат в одной $1$-степени.
	
	Теперь, опираясь на челночный метод доказательства теоремы Майхилла о вычислимой изоморфности $1$-эквивалентных множеств, который в нашем случае существенно упрощает позитивная бесконечность всех $\eta$-классов, будем строить по шагам конечные множества соответствий вида $\{\langle u_0,v_0\rangle,\dots,\langle u_s,v_s\rangle\}$ так, что $u_i=u_j\pmod\eta\Leftrightarrow v_i=v_j\pmod\eta$ и $\forall n\in\omega\exists k,l(n=u_k\wedge n=v_l)$, используя на четных шагах функцию $g_0$ и на нечетных -- $g_1$. Детали опускаем. 
	
	Очевидно, что все построения, приведенные в данном доказательстве равномерно зависят от $x,y$.
\end{proof}

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

\begin{proposition}\label{prop6}
	Если над $\eta$ представима группа, то для любого $\eta$-класса существует такое представление над $\eta$ подходящей группы, для которого данный класс будет единицей.
\end{proposition}

\begin{proof}
	Пусть задана группа $\mathfrak{G}=\langle G;\cdot,^{-1}\rangle$ с единицей $e$. Определим трансляцию $\varphi_d=\lambda x.[x\cdot d]$, где $d$ -- произвольный фиксированный элемент $d\neq e$. Очевидно, что трансляция $\varphi_d$ биективна на $G$. На множестве $G$ определим некоторую структуру с одной бинарной $\ast$ и одной унарной операцией $[]^{-1*}$ следующим образом: $a\ast b=ad^{-1}b;\;[a]^{-1*}=da^{-1}d$. Тогда $\mathfrak{G}^*=\langle G;\ast,[]^{-1*}\rangle$ -- группа с единицей $d$, изоморфная $\mathfrak{G}$, причем $\varphi_d$ осуществляет изоморфизм из $\mathfrak{G}$ на $\mathfrak{G}^*$. Действительно, по определению $a\ast b=ad^{-1}b$, но  $\varphi^{-1}_d(a)=ad^{-1},\varphi^{-1}_d(b)=bd^{-1}$ и $\varphi_d((ad^{-1})(bd^{-1}))=ad^{-1}bd^{-1}d=ad^{-1}b=a\ast b$. Аналогично, т.к. $\varphi^{-1}_d(a)=ad^{-1}$, то $\varphi_d((ad^{-1})^{-1})=\varphi_d(da^{-1})=da^{-1}d=[a]^{-1*}$. 
	
	Пусть группа $\langle G;\cdot\rangle$ с единицей $e$ представима над $\eta$, т.е. имеет такую нумерацию $\nu$, ядро которой есть $\eta$. Зафиксируем любой отличный от единицы элемент $d\in G$ и некоторые $\nu$-номера этого элемента и обратного к $d$ элемента, скажем $\nu(n_0)=d,\nu(n_1)=d^{-1}$. Теперь определим вычислимую функцию $f_d=\lambda x.[x\cdot n_0]$, зададим нумерацию $\nu_d$ основного множества группы $\langle G;\cdot\rangle$ такую, что $\nu_d=\nu f_d$, и определим вычислимые операции $\ast:\nu_d(x)\ast\nu_d(y)=\nu_d(x\cdot n_1\cdot y)$ и $[\nu_d(x)]^{-1*}=\nu(n_0\cdot x^{-1}\cdot n_0)$. Очевидно, что $d$ -- единица группы $\langle G;\ast\rangle$, заданной нумерацией $\nu_d$ с ядром $\eta$.
\end{proof}

\section{Вычислимо прошиваемые множества}

Рассмотрим более подробно равномерные $m$-эквивалентности, всякие пары смежных классов которых вычислимо изоморфны (т.е. переводятся друг в друга вычислимыми перестановками на $\omega$).

\begin{definition}\label{def4} 
	Множество назовается вычислимо прошиваемым, если существует вычислимая перестановка без конечных циклов с бесконечным числом орбит, в каждой из которых содержится ровно один элемент этого множества.
\end{definition}

Заметим, что согласно определению вычислимо прошиваемое множество как бесконечно, так и кобесконечно.

Если множество $\alpha$ содержит ровно по одному элементу в каждой орбите вычислимой перестановки без циклов $f$ с бесконечным числом орбит, то будем говорить, что $f$ прошивает $\alpha$ (или, что $\alpha$ прошивается $f$). Для множества $\alpha$, прошиваемого вычислимой перестановкой $f$, через $\eta_{\alpha,f}$ обозначим эквивалентность 
$$
	x=y\pmod{\eta_{\alpha,f}}\Leftrightarrow\exists n\in Z(f^n(x)\in\alpha\wedge f^n(y)\in\alpha),
$$ 
которая очевидно является равномерной $m$-эквивалентностью, любая пара смежных классов которой вычислимо изоморфна.  

\begin{proposition}\label{prop7}
	Всякая вычислимая перестановка без циклов с бесконечным числом орбит является прошивающей для континуума множеств.
\end{proposition}

\begin{proof}
	Аналогично доказательству предложения \ref{prop1}.    	        
\end{proof} 

\begin{proposition}\label{prop8}
	Всякое вычислимо прошиваемое множество является смежным классом подходящей равномерной $m$-эквивалентности, всякая пара смежных классов которой вычислимо изоморфна.  
\end{proposition}

\begin{proof}
	Пусть $\alpha$ прошивается вычислимой перестановкой $f$. Тогда семейство множеств $\{f^n\alpha|n\in Z\}$ -- классы однозначно определенной равномерной $m$-эквивалентности $\eta_{\alpha,f}$.    	        
\end{proof}

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

\begin{proposition}\label{prop9}
	Если перечислимое множество $\alpha$ прошивается вычислимой функцией $f$, то эквивалентность $\eta_{\alpha,f}$ разрешима.
\end{proposition}

\begin{proof}
	Действительно, $x=y\pmod{\eta_{\alpha,f}}\Leftrightarrow\exists n\in Z(f^n(x)\in\alpha\wedge f^n(y)\in\alpha)$.
\end{proof}

\begin{corollary}\label{cor5}
	 Перечислимое множество вычислимо прошиваемо тогда и только тогда, когда оно бесконечное, кобесконечное и разрешимое.
\end{corollary}

\begin{proof}
	Вычислимая прошиваемость бесконечного, кобесконечного и разрешимого множества очевидна. Обратное следует из предложения \ref{prop8}.
\end{proof}

Назовем эквивалентность $\eta$ вычислимо прошиваемой, если существуют такой ее $\eta$-класс $\alpha$ и вычислимая перестановка $f$, что $\eta_{\alpha,f}=\eta$.

\begin{corollary}\label{cor6}
	Если $(G,\nu)$ -- неразрешимая позитивная группа, то ядро $ker(\nu)$ не является вычислимо прошиваемым.
\end{corollary}

\begin{proof}
	По следствию \ref{cor5} в случае вычислимой прошиваемости ядра нумерации оно разрешимо.
\end{proof}

Характеристической трансверсалью эквивалентности $\eta$ будем называть множество всех натуральных чисел, являющихся наименьшими в содержащих их $\eta$-классах (в обозначениях $tr(\eta)=\{x|\forall y(x=y\pmod\eta\Rightarrow x\leqslant y)\}$).

\begin{proposition}\label{prop10}
	Всякое бесконечное, кобесконечное и коперечислимое множество вычислимо прошиваемо.
\end{proposition}

\begin{proof}
	Пусть $\alpha$ -- бесконечное коперечислимое множество с бесконечным дополнением. Рассмотрим такую позитивную эквивалентность $\eta$ с бесконечными смежными классами, характеристическая трансверсаль которой есть $\alpha$ (о существовании таких эквивалентностей и общих методах их построения см., например, \cite{13}, с. 296). Используя алгоритм перечисления для $\eta$ можно построить по шагам через конечные аппроксимации такую вычислимую перестановку $f$ на $\omega$, которая тождественна по модулю $\eta$ и каждый $\eta$-класс является $f$-орбитой. Приведем алгоритм вычисления графика $G_f$ функции $f$ с умеренной степенью детализации.
		
	Через $\eta^s$ будем обозначать часть эквивалентности $\eta$, построенную за $s$ шагов некоторого фиксированного эффективного пересчета $\eta$.
	
	Шаг 0. $G_f^0=\emptyset$, $\eta^0=\emptyset$.
	
	Шаг s+1. Пусть $C_0,\dots,C_m$ все нетривиальные классы эквивалентности $\eta^s$, каждый из которых является цепью $\eta^s$-эквивалентных чисел вида $a_0,f(a_0),\dots,f^n(a_0)$ (где число $a_0$ не имеет $f$-прообраза, а $f^n(a_0)$ не имеет $f$-образа на шаге $s$). При этом, число $a_0$ назовем началом цепи, а $f^n(a_0)$ -- ее концом. Упорядочим цепи по их началам. Расширим классы $C_0,\dots,C_m$ по модулю эквивалентности $\eta^{s+1}$. Если цепи были различны на шаге $s$, а на шаге $s+1$ пересеклись (т.е. какие-то их элементы стали $\eta^{s+1}$эквивалентными), то для этих цепей расширяем график $G_f^s$ до $G_f^{s+1}$ так, что концы меньших цепей отображаются функцией $f$ на начала больших (на четных шагах) и концы больших -- в начала меньших (на нечетных шагах). Конец шага s+1.
	
	Положим $$G_f=\bigcup_{s\in\omega}G_f^s.$$
	Очевидно, что $f$ -- вычислимая перестановка, прошивающая множество $\alpha$.
\end{proof}

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

Пееред формулировкой следующего утверждения введем некоторые понятия. В соответствии с определением \ref{def3} для заданной эквивалентности $\eta$ построим топологическое пространство $[\eta]_{comp}$, базой открытых множеств которого является семейство всех $\eta$-замкнутых перечислимых множеств. Эту топологию будем называть отделимой ($T_1$-отделимой, хаусдорфовой, регулярной и т.д.), если таковым является пространство $[\eta]_{comp}$. Замечательным свойством этой топологии является тот факт, что если универсальная алгебра $\mathfrak{A}$ представима над $\eta$, то все ее операции, поддерживаемые подходящими вычислимыми функциями в естественной проектирующей нумерации $\nu(x)=\{x\}/\eta$, непрерывны в этой топологии. Для одноместных операций это очевидно, т.к. прообразы перечислимых множеств перечислимы, так же как и то, что морфизм двух нумерованных систем является непрерывным отображением. Непрерывность в общем случае показана в \cite{17}.

Если вычислимо прошиваемая эквивалентность позитивна, то по предложению \ref{prop9} она разрешима и над ней, очевидно, представима группа. Покажем, что существует вычислимо прошиваемая эквивалентность низкой алгоритмической сложности, над которой не представима никакая группа.  

\begin{theorem}\label{theorem2}
	Существует вычислимая перестановка, являющаяся $m$-сводящей для такой равномерной $m$-эквивалентности, над которой не представима никакая группа.
\end{theorem}

\begin{proof}
	В \cite{18} построен пример такого множества $\alpha$, вычислимо прошиваемого подходящей вычислимой перестановкой $f$ на $\omega$, что топологическое пространство $[\eta_{\alpha,f}]_{comp}$ является $T_1$-отделимым, но не хаусдорфовым. Более того, не существует двух непустых непересекающихся перечислимых $\eta_{\alpha,f}$-замкнутых множеств. Хорошо известно, что если топологическая группа $T_1$-отделима, то она $T_2$-отделима, т.е. хаусдорфова. Поэтому, если бы над $\eta_{\alpha,f}$ была представима группа, то пространство $[\eta_{\alpha,f}]_{comp}$ было бы хаусдорфовым (заметим, что ключевым моментом является непрерывность групповых операций относительно введенной топологии). Таким образом, над неразрешимой равномерной $m$-эквивалентностью $\eta_{\alpha,f}$ не представима никакая группа.         
\end{proof}

Отметим, что алгоритмическая сложность эквивалентности $\eta_{\alpha,f}$ из теоремы \ref{theorem2} находится в классе $\Pi^0_2$; более точно, она является эффективно $T_1$-отделимой, т.е. существует такое эффективное семейство $S$ перечислимых $\eta_{\alpha,f}$-замкнутых множеств, что для любых $x\neq y\pmod{\eta_{\alpha,f}}$ найдутся такие $\sigma_0,\sigma_1\in S$, что $\{x\}/\eta_{\alpha,f}\subseteq\sigma_0\wedge\{y\}/\eta_{\alpha,f}\cap\sigma_0=\emptyset$ и $\{y\}/(\eta_{\alpha,f})\subseteq\sigma_1\wedge\{x\}/(\eta_{\alpha,f})\cap\sigma_1=\emptyset$.

\section{Решетки}

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

\begin{theorem}\label{theorem3}
Для всякого $\alpha\subseteq\omega$ эквивалентность $\eta^*_\alpha$ является вычислимо отделимой $m$-эквивалентностью, любая пара смежных классов которой вычислимо изоморфна. При этом, если $\alpha$ коперечислимо, то эквивалентность $\eta^*_\alpha$ является негативной и равномерной.
\end{theorem}

\begin{proof}
Обозначим через $\Gamma_{x,y}$ множество $\gamma$-номеров всех конечных расширений множества $\gamma_x$ вне $\gamma_y\smallsetminus\gamma_x$, т.е. $\Gamma_{x,y}=\{z|\gamma_x\subseteq\gamma_z\wedge(\gamma_y\smallsetminus\gamma_x)\cap\gamma_z=\emptyset\}$. Например, $\Gamma_{x,0}$, где $\gamma_x\neq\emptyset,\gamma_0=\emptyset$ -- есть совокупность канонических индексов всех конечных расширений множества $\gamma_x$, а $\Gamma_{0,x}$ -- множество номеров всех конечных множеств, не пересекающихся с $\gamma_x$. 

Покажем, что $\eta^*_\alpha$ вычислимо отделима для любого $\alpha$. Действительно, пусть $x\neq y\pmod{\eta^*_\alpha}$. Выберем такие $x_0,y_0$, что $\gamma_x\setminus\alpha=\gamma_{x_0}\setminus\alpha,\gamma_y\setminus\alpha=\gamma_{y_0}\setminus\alpha$ и $\gamma_{x_0},\gamma_{y_0}\subseteq\omega\setminus\alpha$, т.е. $x_0,y_0$ -- $\gamma$-номера множеств, целиком лежащих в $\omega\setminus\alpha$. Легко проверить, что $\Gamma_{x_0,y_0}$ -- $\eta^*_\alpha$-замкнутое вычислимое множество, содержащее $x$ и не содержащее $y$.

Перейдем к построению требуемой перестановки $f_{x,y}$. Для данных $x\neq y\pmod{\eta^*_\alpha}$ таких, что $\gamma_x,\gamma_y\subseteq\omega\smallsetminus\alpha$, построим множества (их характеристические индексы) $\Gamma_{x,y},\Gamma_{y,x}$ и установим вычислимое взаимно однозначное соответствие между ними следующим образом. Для каждого $z\in\Gamma_{x,y}$ найдем такое $u$, что $\gamma_u=\gamma_z\smallsetminus\gamma_x$ и определим $\gamma_v=\gamma_u\cup\gamma_y$. Тогда $v\in\Gamma_{y,x}$. Полагаем $f_{x,y}(z)=v$ и $f_{x,y}(v)=z$. На всех числах из $\omega\smallsetminus(\Gamma_{x,y}\cup\Gamma_{y,x})$ положим $f_{x,y}$ тождественной.

Покажем, что $f_{x,y}$ есть функция, согласованная с $\eta^*_\alpha$, действующая как бесконечное множество циклов длины 2 на $\Gamma_{x,y}\cup\Gamma_{y,x}$. Пусть $z_1\in\Gamma_{x,y}$ и $f_{x,y}(z_1)=p_1$. Тогда однозначно определено такое $u_1$, что $\gamma_{u_1}=\gamma_{z_1}\smallsetminus\gamma_x$ и $\gamma_{p_1}=\gamma_y\cup\gamma_{u_1}$, причем множество $\gamma_{u_1}$ не пересекается с $\gamma_y$. Для $z_2\in\Gamma_{x,y}$ существуют однозначно определенные соответствующие $u_2,p_2$. Теперь, если $z_1=z_2\pmod{\eta^*_\alpha}$, то $\gamma_{z_1}\smallsetminus\alpha=\gamma_{z_2}\smallsetminus\alpha$, т.е. $\gamma_{u_1}\smallsetminus\alpha=\gamma_{u_2}\smallsetminus\alpha$. Поэтому $p_1=p_2\pmod{\eta^*_\alpha}$. Инъективность $f_{x,y}$ очевидна. Биективность следует из того, что всякого $p\in\Gamma_{y,x}$ существует такое единственное $u$ (а именно, $\gamma_p=\gamma_y\cup\gamma_u$), что $f_{x,y}(z)=p$, где $\gamma_z=\gamma_x\cup\gamma_u$. Аналогично показывется корректность $f_{x,y}$ на аргументах из $\Gamma_{y,x}$. Таким образом, $f_{x,y}$ -- вычислимая перестановка на $\omega$, индуцирующая перестановку на $\omega/\eta^*_\alpha$, которая переводит класс $\{x\}/\eta^*_\alpha$ в класс $\{y\}/\eta^*_\alpha$.  

Негативность $\eta^*_\alpha$ при коперечислимости $\alpha$ очевидна. Т.к. множество всех минимальных (в содержащих их классах) элементов эквивалентности перечислимо, то для каждой пары чисел $\langle x,y\rangle$, таких что $\gamma_x,\gamma_y\subseteq\omega\smallsetminus\alpha$ применяем описанную выше процедуру и получим вычислимое семейство $\{f_{x,y}|\gamma_x,\gamma_y\subseteq\omega\smallsetminus\alpha\}$ вычислимых перестановок с требуемым свойством, т.е. $\eta^*_\alpha$ является равномерной $m$-эквивалентностью, всякие два класса которой вычислимо изоморфны.     
\end{proof}

\begin{corollary}\label{cor7}
	Для любого $\alpha$ над $\eta^*_\alpha$ представима решетка, изоморфная подрешетке решетки всех конечных подмножеств некоторого множества. 
\end{corollary}

\begin{proof}
	Нетривиальным является случай кобесконечного $\alpha$. Для любых $x,y\in\omega$ определим $x\sqcup y=\gamma^{-1}(\gamma_x\cup\gamma_y),x\sqcap y=\gamma^{-1}(\gamma_x\cap\gamma_y)$. Согласованность введенных операций с $\eta^*_\alpha$, существование точных верхних и нижних граней, а также наличие наименьшего элемента очевидны.
\end{proof}

Любая группа без кручения, имеющая вычислимую копию, обладает неразрешимой негативной нумерацией (\cite{19}). В связи с этим возникает вопрос: ''представима ли группа над эквивалентностью $\eta^*_\alpha$ для некоторого коперечислимого неразрешимого $\alpha$''?

Напомним (\cite{13}, с.288), что позитивная эквивалентность $\eta$ называется совершенной, если не существует нетривиальных $\eta$-замкнутых вычислимых множеств. 

Ниже решетка понимается как алгебра (в сигнатуре $\langle\sqcup,\sqcap\rangle$).

\begin{proposition}\label{prop11}
	Существует такая позитивная эквивалентность, над которой не представима никакая верхняя (нижняя) полурешетка.
\end{proposition}

\begin{proof}
	Пусть $\eta$ -- совершенная эквивалентность со сжатой характеристической трансверсалью. Примеры таких эквивалентностей можно найти в \cite{13}. В \cite{16,20} показано, что всякая $n$-местная вычислимая функция, согласованная с $\eta$ действует на фактор-множестве $\omega/\eta$ либо как константа, либо как проектирующая. Предположим, что бинарная вычислимая операция $f$ представляет операцию взятия точной верхней (нижней) грани на $\omega/\eta$. Тогда индуцированный $f$ позитивный частичный порядок $x\leqslant_\eta y\Leftrightarrow f(x,y)=y\pmod\eta$ не может быть линейным (\cite{21}) и потому имеется два $\leqslant_\eta$-несравнимых $\eta$-класса, скажем $\{k\}/\eta$ и $\{l\}/\eta$. Рассмотрим трансляцию $t=\lambda x.[f(x,k)]$. Тогда, в силу идемпотентности $t(k)=k\pmod\eta$, но $t(l)\neq k\pmod\eta\wedge t(l)\neq l\pmod\eta$ и одноместная вычислимая функция $t$ оказывается как не константой, так и не проектирующей (тождественной). Противоречие.        
\end{proof}

Предложение \ref{prop11} порождает принципиальный вопрос: ''над всякой ли негативной эквивалентностью представима решетка как алгебра''?

\begin{definition}\label{def5}
	Граф $\langle\Gamma;P\rangle$ называется позитивно (негативно) представимым над эквивалентностью $\eta$, если существует такая его нумерация $\nu$, что $ker(\nu)=\eta$ и множество $\{\langle x,y\rangle|\langle\nu x,\nu y\rangle\in P\}$ перечислимо (коперечислимо).
\end{definition}

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

Теперь под словом решетка будем понимать частично упорядоченное множество.

\begin{proposition}\label{prop12}
	(a) Над любой негативной эквивалентностью негативно представим линейный порядок. 
	
	(b) Над всякой позитивной эквивалентностью позитивно представима решетка, однако существует такая позитивная эквивалентность, над которой позитивно не представим никакой линейный порядок.
\end{proposition}

\begin{proof}
	(a) В \cite{21} показано, что над всякой негативной эквивалентностью с бесконечным множеством смежных классов негативно представим плотный линейный порядок и, тем более, решетка (как частичный порядок). 
	
	(b) Пусть $\eta$ -- позитивная эквивалентность с не менее чем двумя $\eta$-классами, которые мы зафиксируем, скажем $\alpha,\beta$. Тогда порядок $\alpha\times\omega\cup\omega\times\beta\cup\eta$ есть позитивная решетка с нулем ($\alpha$), единицей ($\beta$) и множеством остальных попарно несравнимых между собой по модулю $\eta$ элементов. Существование позитивной эквивалентности, над которой позитивно не представим никакой линейный порядок доказано в упомянутой выше работе \cite{21}.    	        
\end{proof}

\section{Трансляционно предполные алгебры, кольца и полугруппы}

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

Т.к. понятие кольца включает в себя подпонятие своей аддитивной коммутативной группы, то ядро нумерации любого кольца является равномерной $m$-эквивалентностью. Тем более это касается тел и полей. Поэтому все общие результаты, сформулированные для групп в предыдущих разделах, справедливы и для любых колец.

Известно (\cite{22}), что над любой негативной эквивалентностью представимы как конечно порожденные, так и конгруэнц-простые универсальные алгебры. Представимость же конгруэнц-простой алгебры над позитивной эквивалентностью равносильна ее разрешимости. Вместе с тем, если эквивалентность (не обязательно позитивная) имеет, к примеру, гипериммунную характеристическую трансверсаль, то всякая представимая над ней алгебра конечной сигнатуры локально конечна (\cite{16}). Если позитивная эквивалентность не является вычислимо отделимой, то решетка конгруэнций всякой представимой над ней универсальной алгебры континуальна (\cite{16}). Поэтому, с точки зрения представимости богатых классов систем над эквивалентностями, негативные эквивалентности можно трактовать как более приоритетные относительно позитивных. Следующие важные классы универсальных алгебр подтверждают сказанное.

Унарная термальная операция с фиксированными элементами алгебры в качестве параметров называется трансляцией.

\begin{definition}\label{def6}
	Универсальная алгебра называется трансляционно полной, если всякая пара различных ее элементов переводится в любую другую пару различных элементов подходящей
	трансляцией.
\end{definition}

Очевидно, что всякая трансляционно полная алгебра является конгруэнц-простой. Обратное неверно. Классический пример трансляционно полной алгебры -- любое тело (\cite{23}).

\begin{definition}\label{def7}
	Универсальная алгебра называется трансляционно предполной, если существует такая пара различных ее элементов, в которую переводится любая пара различных элементов подходящей трансляцией.
\end{definition}

Фактически из определения следует, что всякая трансляционно предполная алгебра является подпрямо неразложимой. Обратное неверно.

Определение \ref{def7} существенно шире определения \ref{def6}. Простейший пример нетривиальной трансляционно предполной не простой алгебры -- алгебра предшествования $P=\langle\omega;p\rangle,p(0)=0,p(n+1)=n$.
\smallskip

Для множества $\alpha\subseteq\omega$ и эквивалентности $\eta$ через $[\alpha]_\eta$ обозначим $\eta$-замыкание множества $\alpha$ (т.е. наименьшее $\eta$-замкнутое расширение $\alpha$). Будем говорить, что число $x$ является $\eta$-отвергаемым множеством $\alpha$, если $x\notin[\alpha]_\eta$. Легко понять, что для любой негативной эквивалентности $\eta$ отношение ''число $x$ является $\eta$-отвергаемым конечным множеством $\delta$'' -- перечислимое и равномерно зависящее от $x,\delta$ (можно считать, что $\delta$ задано своим каноническим индексом или дано в явном виде). Если ясно о какой эквивалентности $\eta$ идет речь, то будем говорить, что $x$ отвергается $\delta$.   

\begin{theorem}\label{theorem4}
	Над любой негативной эквивалентностью представима трансляционно полная универсальная алгебра.
\end{theorem}

\begin{proof}
	Пусть $\eta$ -- негативная эквивалентность. Если характеристическая трансверсаль $tr(\eta)$ конечна, то $\eta$ разрешима и доказывать нечего. Поэтому предполагаем, что $tr(\eta)=\{t_0,t_1,\dots\}$ бесконечна. Заметим, что $tr(\eta)$ перечислима, т.к. $x\in tr(\eta)\Leftrightarrow\forall z<x(z\neq x\pmod\eta)$. Покажем, что для любой пары $x\neq y\pmod\eta$ существует разрешимое $\eta$-замкнутое множество, отделяющее $x,y$ и, более того, это множество равномерно строится по данным $x,y$.
	
	Шаг $0$. $A_x^0=\{x\},A_y^0=\{y\}$.
	
	Шаг $s+1$. Пусть $z$ -- наименьшее натуральное число, не принадлежащее $A_x^s\cup A_y^s$. Проверяем $z$ на предмет его отвержения хотя бы одним из множеств $A_x^s,A_y^s$. Если $z$ отвергается $A_x^s$, то полагаем $A_x^{s+1}=A_x^s,A_y^{s+1}=A_y^s\cup\{z\}$; если $x$ отвергается $A_y^s$, то $A_x^{s+1}=A_x^s\cup\{z\},A_y^{s+1}=A_y^s$. Если $z$ отвергается обоими множествами, то относим его к $A_x^{s+1}$. Конец шага $s+1$.
	
	Определим $$A_x=\bigcup_{s\in\omega}A_x^s,A_y=\bigcup_{s\in\omega}A_y^s.$$ 
	
	Индукцией по шагам построения легко показать, что каждый шаг заканчивается с отнесением текущего тестируемого натурального числа к одному из двух множеств, а также тот факт, что $[A_x^s]_\eta\cap[A_y^s]_\eta=\emptyset$ для любого шага $s$. Поэтому перечислимые $A_x,A_y$ не пересекаются, являются $\eta$-замкнутыми и их объединение покрывает все $\omega$. Равномерная зависимость индексов характеристических функций $A_x,A_y$ от $x,y$ очевидна.
	
	Теперь для каждой пары $\langle x,y\rangle$ различных по модулю $\eta$ чисел построим вычислимое семейство трансляций $T_{x,y}=\{f_{x,y,m,n}|m,n\in\omega\}$ следующим образом:  $$z\in A_x\Rightarrow f_{x,y,m,n}(z)=t_m;z\in A_y\Rightarrow f_{x,y,m,n}(z)=t_n,$$ где $t_m,t_n\in tr(\eta),m\neq n$.
	
	Наконец, определим вычислимое семейство трансляций $$T=\bigcup_{x\neq y\pmod\eta}T_{x,y}.$$
	Очевидно, что любая трансляция $f\in T$ согласована с $\eta$, т.е. $x=y\pmod\eta\Rightarrow f(x)=f(y)\pmod\eta$ и потому корректно определена фактор-алгебра $\langle\omega/\eta;T\rangle$ вычислимой алгебры $\langle\omega;T\rangle$ по конгруэнции $\eta$. Т.к. для любой пары различных по модулю $\eta$ чисел $x,y$ и любых различных $t_m,t_n\in tr(\eta)$ найдется трансляция из $T$, переводящая $x$ в $t_m$ и $y$ в $t_n$, то алгебра $\langle\omega/\eta;T\rangle$ трансляционно полна. 
\end{proof}

\begin{corollary}\label{cor8}
	Над любой негативной эквивалентностью представима трансляционно предполная универсальная алгебра.
\end{corollary}

\textbf{Замечание 2.} Негативные нумерации представляются в определенном смысле не менее естественными, чем позитивные. Так, например, простейшая группа целых чисел по сложению $\langle Z;+\rangle$ имеет неразрешимые негативные нумерации, хотя она устойчива относительно позитивных представлений; любое бесконечное поле, имеющее вычислимую копию (как отмечалось выше), также имеет неразрешимую негативную нумерацию (см. \cite{19}), в то время как всякое позитивное представление любого поля является разрешимым.
\par\smallskip 

\begin{proposition}\label{prop13}
	Всякая хаусдорфова нумерация трансляционно предполной универсальной алгебры негативна.
\end{proposition}

\begin{proof}
	В \cite{18}.
\end{proof}

\begin{corollary}\label{cor9}
	Никакая трансляционно предполная универсальная алгебра не представима ни над какой не негативной эквивалентностью, каждый смежный класс которой перечислим.
\end{corollary}

\begin{proof}
	В противном случае, по предложению \ref{prop13}, ввиду очевидной $T_2$-отделимости (даже дискретности) соответствующего пространства следует негативность ядра представления.  
\end{proof}

В частности, никакая трансляционно предполная универсальная алгебра не представима ни над какой неразрешимой позитивной эквивалентностью.
\par\smallskip 

Рассмотрим более широкие семейства классических систем.

Будем называть функцию $f:\omega^n\longrightarrow\omega$ согласованной с эквивалентностью $\eta$, если $\eta$ -- конгруэнция алгебры $\langle\omega;f\rangle$.  Как обычно, функция $C^n_m:\omega^n\longrightarrow\omega$, с областью значений $\{m\} (m\in\omega)$, называется константой, а $I^n_m:\omega^n\longrightarrow\omega$, где $1\leqslant m\leqslant n$ и $\forall\langle x_1,\dots,x_n\rangle\in\omega^n(I^n_m(x_1,\dots,x_n)=x_m)$ -- проектирующей функцией. Обозначим $$U=\bigcup_{m,n\in\omega}\{C^n_m\}\cup\bigcup_{1\leqslant m\leqslant n,n\in\omega}\{I^n_m\}.$$ 
 Очевидно, что любая функция согласована с двумя эквивалентностями -- нулевой ($id\;\omega$) и единичной ($\{\langle x,y\rangle|x,y\in\omega\}$). Ясно также, что всякая $U$-функция согласована с любой эквивалентностью над $\omega$. 

\begin{proposition}\label{prop14}
	Над любой эквивалентностью представима коммутативная полугруппа. 
\end{proposition}

\begin{proof}
	Определим умножение на $\omega$ как $C^2_m$, где $m$ -- любое фиксированное натуральное число. Тогда операция $C^2_m$ вычислима и очевидно согласована с любой эквивалентностью $\eta$ на $\omega$, а потому корректно определена фактор-алгебра $\langle\omega/\eta;C^2_m\rangle$ вычислимой коммутативной полугруппы $\langle\omega;C^2_m\rangle$, т.е. полугруппа $\langle\omega;C^2_m\rangle$ представима над $\eta$.
\end{proof}

Заметим, что в качестве полугруппового умножения взять и $I^2_1$, но тогда полугруппа не будет коммутативной.

\begin{proposition}\label{prop15}
	Для любого $\alpha\subseteq\omega$ над эквивалентностью $\eta^*_\alpha$ представима коммутативная полугруппа с единицей.
\end{proposition} 

\begin{proof}
	Определим операцию умножения $\ast$: $x\ast y=\gamma^{-1}(\gamma_x\cup\gamma_y)$. Легко проверить, что $\ast$ согласована с $\eta^*_\alpha$ для любого $\alpha\subseteq\omega$. Единицей данной коммутативной полугруппы будет $\eta^*_\alpha$-класс, порожденный всеми $\alpha$-расширениями пустого множества, т.е. $\varepsilon=\{x|\gamma_x\subseteq\alpha\}$. 
\end{proof}

\begin{proposition}\label{prop16}
	Существует позитивная эквивалентность, над которой не представима никакая полугруппа с единицей.
\end{proposition} 

\begin{proof}
	Пусть $\eta$ -- упоминавшаяся выше совершенная эквивалентность со сжатой характеристической трансверсалью. Тогда всякая вычислимая функция, согласованная с $\eta$, действует на фактор-множестве $\omega/\eta$ либо как константа, либо как проектирующая (\cite{16}). Поэтому, если над $\eta$ представима полугруппа с единицей $e$ и умножением $\ast$, то это умножение действует на $\omega/\eta$ либо как константная, либо как проектирующая операция. Если $\ast$ действует как константа, то обозначим через $c$ такой элемент полугруппы, что $\forall a,b(a\ast b=c)$. Тогда $\forall a(e\ast a=a\ast e=a=c)$, что невозможно в нетривиальной полугруппе. 
	
	Пусть $\ast$ действует как проектирующая, т.е. либо подобно $I^2_1$, либо как $I^2_2$. В первом случае $\forall a(e=e\ast a)$ (т.к. $\ast$ действует как $I^2_1$), но, в то же время $\forall a(e\ast a=a)$ (т.к. $e$ -- единица полугруппы). Поэтому $\forall a(e=a)$, что возможно лишь для одноэлементного моноида. Случай $I^2_2$ рассматривается аналогично.
\end{proof}

Заметим, что если рассматривать полугруппы не с двусторонними, а с левыми (правыми) единичными элементами, то имеет место

\begin{proposition}\label{prop17}
	Над любой эквивалентностью представима полугруппа с левой (правой) единицей.
\end{proposition} 

\begin{proof}
	В самом деле, если принять в качестве группового умножения операцию $I^2_2$, то любой элемент полугруппы будет являться левой единицей. Аналогично, для операции $I^2_1$ всякий элемент будет правой единицей.
\end{proof}

\section{Степени представимости}

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

Пусть $\mathbb{G}_p$ -- класс позитивно представимых бесконечных групп, $\Sigma$ -- множество всех бесконечных позитивных эквивалентностей и $K_G(\eta)$ -- класс всех групп, представимых над эквивалентностью $\eta$. На $\Sigma$ определим следующий предпорядок: $$\eta_0\leqslant_{G_p}\eta_1\leftrightharpoons\forall G\in\mathbb{G}_p[G\in K_G(\eta_0)\Rightarrow G\in K_G(\eta_1)].$$
Симметричное замыкание предпорядка $\leqslant_{G_p}$ разбивает множество $\Sigma$ на классы $\equiv_{G_p}$-эквивалентности и на фактор-множестве $\Sigma/\equiv_{G_p}$ порождается частичный порядок $D_{G_p}=\langle\Sigma/\equiv_{G_p};\leqslant_{G_p}\rangle$, в котором через $\leqslant_{G_p}$ обозначен и частичный порядок на фактор-множестве, индуцированный действием $\leqslant_{G_p}$ на $\Sigma$. Корректность такого перехода при факторизации очевидна. Неформально, $\eta_0\leqslant_{G_p}\eta_1$ означает, что всякая группа, представимая над $\eta_0$ является представимой и над $\eta_1$, а структура частичного порядка $D_{G_p}$ отражает алгоритмическую природу эквивалентностей с точки зрения соотношений между реализуемыми над ними классами групп. Отметим, что любая группа из $\mathbb{G}_p$ определяется некоторым $\equiv_{G_p}$-классом. Элементы $D_{G_p}$ будем называть степенями позитивной представимости групп. Отметим, что степени представимости конечных систем образуют изолированные точки в структуре частично упорядоченного множества степеней и, с точки зрения дескриптивной теории вычислимости, представляют ''вырожденный случай''. Поэтому мы рассматриваем все степени представимости в контексте отсутствия степеней, порожденных конечными эквивалентностями.

Например, из теоремы \ref{theorem1} следует, что все позитивные эквивалентности, не являющиеся $m$-равномерными лежат в одной $\equiv_{G_p}$-степени, являющейся наименьшей относительно $\leqslant_{G_p}$ и определяющей пустой класс групп. Однако, из теоремы \ref{theorem2} вытекает, что в этой же степени находятся и некоторые равномерные $m$-эквивалентности.

Аналогично, рассматривая класс негативно представимых бесконечных групп $\mathbb{G}_n$ и множество всех бесконечных негативных эквивалентностей $\Pi$ получаем структуру степеней негативной представимости групп $D_{G_n}=\langle\Pi/\equiv_{G_n};\leqslant_{G_n}\rangle$. Можно рассматривать более широкие классы $\mathbb{SG}_p\;(\mathbb{SG}_n)$ позитивно (негативно) представимых бесконечных полугрупп и соответствующие множества степеней позитивной (негативной) представимости для классов полугрупп. При этом, $\equiv_{G_p}$-степени представлений групп будут, вообще говоря, ''распадаться'' для представлений полугрупп, т.е. $\equiv_{SG_p}\subseteq\equiv_{G_p}$, т.к. одинаковые $\equiv_{G_p}$-степени для групп могут быть различными для более широкого класса полугрупп (при рассмотрении групп в сигнатуре с одной бинарной групповой операцией).

На настоящий момент относительно изучена ситуация для степеней позитивной и негативной представимости линейных порядков. Так, для структуры $D_{L_p}$ степеней позитивной представимости линейных порядков доказана ее бесконечность, существование несравнимых степеней, отсутствие наибольшего элемента, наличие степени, определяющей пустой класс линейных порядков и т.д. (см. \cite{24}). Строение же структуры $D_{L_n}$ степеней негативной представимости линейных порядков оказалось совершенно иным -- она также бесконечна, но имеет наибольший элемент, при этом всякая степень определяет достаточно богатый класс линейных порядков представимых над любой эквивалентностью из этой степени и т.д. (см. \cite{21}).

Для групп, полугрупп и колец ситуация не изучена. Самая простейшая ситуация -- для степеней позитивной представимости полей $D_{F_p}$.
             
\begin{proposition}\label{prop18}
	Частично упорядоченное множество степеней позитивной представимости бесконечных полей двухэлементно и изоморфно типу ординала 2.
\end{proposition} 

\begin{proof}
	В самом деле, любая неразрешимая позитивная эквивалентность лежит в степени позитивной представимости, которая определяет пустой класс полей, т.к. над такой эквивалентностью не представимо поле. С другой стороны, над любой разрешимой бесконечной эквивалентностью представимо всякое бесконечное поле, обладающее вычислимой копией. 
\end{proof}

О структуре $D_{G_p}$ степеней позитивной представимости групп имеет место почти тривиальное

\begin{proposition}\label{prop19}
	Частично упорядоченное множество степеней позитивной представимости бесконечных групп имеет не менее трех элементов, два из которых несравнимы.
\end{proposition} 

\begin{proof}
	Все эквивалентности не являющиеся $m$-равномерными (и даже некоторые равномерные $m$-эквивалентности) образуют наименьшую степень $d_0$ в $D_{G_p}$. С другой стороны, степень $d_1$, содержащая $\eta_1=id\;\omega$, определяет устойчивую относительно позитивных нумераций простейшую группу $G_1=\langle Z;+\rangle$. Теперь, если $d_2$ -- степень, содержащая неразрешимую эквивалентность $\eta_2$, являющуюся ядром представления некоторой конечно порожденной группы $G_2$, то $G_1\in K_G(\eta_1)\smallsetminus K_G(\eta_2)\wedge G_2\in K_G(\eta_2)\smallsetminus K_G(\eta_1)$, т.е. $\eta_1\nleqslant_{G_p}\eta_2$ и $\eta_2\nleqslant_{G_p}\eta_1$.
\end{proof}

Другие естественные вопросы, касающиеся строения структуры степеней представлений указанных выше систем, открыты. Например, является ли структура $D_{G_p}$ бесконечной?

Напомним (\cite{12}), что если $(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)$).

Можно ввести еще одну естественную структуру степеней, содержащую как позитивные, так и негативные степени. Напомним, что эквивалентность $\eta$ на $\omega$ называется отделимой (эффективно отделимой), если существует $T_0$-отделяющее семейство $\eta$-замкнутых перечислимых множеств пространства $\omega/\eta$ (вычислимое $T_0$-отделяющее семейство $\eta$-замкнутых перечислимых множеств пространства $\omega/\eta$). Ю.Л. Ершовым в \cite{13} было введено наиболее общее понятие отделимой нумерации множества (т.е. такой нумерации, ядро которого $T_0$-отделимо в перечислимой топологии) и дана следующая характеризация ядер отделимых нумераций семейств перечислимых множеств: 

\bigskip

{\it Нумерация семейства перечислимых множеств отделима тогда и только тогда, когда ее ядро эффективно отделимо.}

\bigskip 

Применение этой теоремы к алгебрам почти непосредственно дает следующий результат:

\begin{proposition}\label{prop20}
	Нумерованная алгебра отделима тогда и только тогда, когда она аппроксимируется эффективно отделимыми алгебрами.
\end{proposition} 
Доказательство в \cite{17}.

Класс эффективно отделимых алгебр лежат в классе $\Pi^0_2$, но не содержит $\Delta^0_2$. Этот класс представляется естественным, т.к. он лежит низко в арифметической иерархии и содержит в себе важнейшие нижние классы -- $\Sigma^0_1\bigcup\Pi^0_1$. Поэтому вопрос о строении структуры степеней эффективно отделимых групп $D_{G_E}$ может представлять интерес с точки зрения теоретической информатики. 

\bigskip
\begin{thebibliography}{99} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).
	
\bibitem{1}  A.I. Mal'tsev, 
{\it Strictly related models and recursively perfect algebras}, Dokl. Akad. Nauk SSSR, \textbf{145}:2 (1962),  276--279.

\bibitem{2}  A.I. Mal'tsev, 
{\it On recursive Abelian groups}, Dokl. Akad. Nauk SSSR, \textbf{146}:5 (1962),  1009--1012. 

\bibitem{3} A.S. Morozov,
{\it On computable groups of automorphisms of models}, Algebra and Logic, \textbf{25}:4 (1986),  415--424.

\bibitem{4} A.S. Morozov, 
{\it Elementary properties of groups of recursive permutations}, Dokl. Akad. Nauk SSSR, \textbf{305}:2 (1989),  274--276.

\bibitem{5} A.S. Morozov, 
{\it On theories of classes of groups of recursive permutations}, Trudy Inst. Mat. Sib. Otd. AN SSSR, 12 (1989),  91--104.

\bibitem{6} A.S. Morozov, 
{\it Groups of computable automorphisms}, in: Yu.L. Ershov (ed.) et al., Handbook of recursive mathematics, vol. 1: Recursive model theory (Stud. Log. Found. Math., 138), Amsterdam, Elsevier, 1998, 311--345.

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

\bibitem{8} V. Harizanov, R. Miller, A. S. Morozov,
{\it Simple structures with complex symmetry}, Algebra and Logic, \textbf{49}:1 (2010), 68--90.

\bibitem{9} A.S. Morozov, 
{\it Once again on the Higman question}, Algebra and Logic, \textbf{39}:2 (2000), 78--83. 

\bibitem{10} N. G. Khisamiev,
{\it On positive and constructive groups}, Siberian Math. J., \textbf{53}:5 (2012), 906--917.

\bibitem{11} N.G. Khisamiev,
{\it The arithmetic hierarchy of abelian groups}, Siberian Math. J., \textbf{29}:6 (1988), 987--999.

\bibitem{12} 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{13} Yu.L. Ershov, 
{\it The Theory of Enumerations [in Russian]}, Nauka, Moscow, 1977.

\bibitem{14} S.S. Goncharov,
{\it Computability and computable models}, Mathematical Problems from Applied Logic. II. Logics for the XXIst Century, eds. Gabbay D.M., Goncharov S.S., Zakharyaschev M., eds., Springer, New York, 2007, 99--216.

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

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

\bibitem{17} N.Kh. Kasymov, 
{\it Homomorphisms onto effectively separable algebras}, Sib. Math. J., \textbf{57}:1 (2016), 36--50.

\bibitem{18} N.Kh. Kasymov, A.S. Morozov, I.A. Khodzhamuratova, 
{\it $T_1$-separable enumarations of subdirectly indecomposable algebras}, Algebra and logic (to be published).

\bibitem{19} B.M. Khoussainov, T. Slaman, P. Semukhin,
{\it $\prod_1^0$-presentasions of algebras}, Archive for Mathematical Logic, \textbf{45}:6 (2006), 769--781.

\bibitem{20} N.Kh. Kasymov, B.M. Khoussainov,
{\it Finitely generated enumerable and absolutely locally finite algebras}, Vychisl. Sist., \textbf{116} (1986), 3--15.

\bibitem{21} N.Kh. Kasymov, R.N. Dadazhanov,  
{\it Negative dense linear orders}, Sib. Math. J., \textbf{58}:6 (2017), 1015--1033.

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

\bibitem{23} N.Kh. Kasymov, F.N. Ibragimov,  
{\it Separable enumerations of division rings and effective embeddability of rings therin}, Sib. Math. J., \textbf{60}:1 (2019), 62--70.

\bibitem{24} E.B. Fokina, B.M. Khoussainov, P. Semukhin, D. Turetskiy,
{\it Linear orders realized by c.e. equivalence relations}, Journal of Symbolic Logic, \textbf{81}:2 (2016), 463--482.





\end{thebibliography}

\end{document}
