О граничной эквивалентности колец и матричных колец над ними

Важенин Ю.М., Нагребецкая Ю.В.


Пусть ${\cal B}_H (A; \sigma)$~--- границ разрешимости алгебраической системы
$\langle A; \sigma \rangle$ относительно иерархии языков $H$;
$S$ и $S A$~--- схемная и
схемно-альтернативная иерархии языков [1].
Будем говорить, что алгебраические системы $\langle A_1; \sigma_1 \rangle$
и $\langle A_2; \sigma_2 \rangle$ $H$-гранично эквивалентны и писать
$\langle A_1; \sigma_1 \rangle \approx_H\langle A_2; \sigma_2 \rangle$,
если ${\cal B}_H(A_1; \sigma_1)={\cal B}_H(A_2; \sigma_2)$.
Обозначим через $A^{n\times n}$
множество всех квадратных матриц порядка $n$ над множеством $A$. В работах
{[2, 3]} были найдены границы разрешимости относительно иерархии $S A$
колец ${\Bbb Z}$ и ${\Bbb Z}^{n\times n}$ в различных сигнатурах. Оказалось,
в частности, что
$\langle{\Bbb Z}\lo; +, \cdot\rangle\approx_{S A}
\langle{\Bbb Z}^{n\times n}; +, \cdot\rangle$ и
$\langle{\Bbb Z}; +, \cdot, 1\rangle\approx_{S A}
\langle{\Bbb Z}^{n\times n}; +, \cdot, e_{i j}\rangle$
для любых $i, j \in \{1, \ldots, n\}$, где $e_{i j}$~--- констант ,
интерпретируемая как соответствующая матричная единица.
Следующие теоремы устанавливают $H$-граничную эквивалентность
ряда важных колец и соответствующих матричных колец. \par
\smallskip
{\bf Теорем 1.} Пусть $R$~--- целостное кольцо или тело,
$K$~-- ассоциативное кольцо с единицей. Тогда
$\langle R; +, \cdot \rangle \approx_{S}
\langle R; +,\cdot, 1\rangle \approx_{S}
\langle R^{n\times n}; +,\cdot \rangle$ и
$\langle K; +, \cdot, 1 \rangle \approx_{S}
\langle K^{n\times n}; +, \cdot, e_{i j} \rangle$
для любых $n\ge 1$ и $i, j \in \{1, \ldots, n\} $.\par
\smallskip
Для кольца $R$ обозначим через $ M_n(R)$ алгебру с основным множеством
$\bigcup
\limits_{ 1\le k,l\le n} R^{k\times l}$
и операциями $\plus$ и $\mult$,
заключающимися в расширении при необходимости исходных матриц нужным
количеством нулевых строк и столбцов, добавляемых снизу и справа, с
последующими "обычными" сложением и умножением полученных матриц.\par
\smallskip
{\bf Теорема 2.} Пусть $R$~--- ассоциативное кольцо с единицей. Тогда
$\langle R; +,\cdot \rangle\approx_{S}
\langle M_n(R); \plus, \mult \rangle$
для любого $n\ge 1$.\par
\smallskip
{\bf Теорема 3.} Для любого $n\ge 1$
$\langle{\Bbb Z}\lo; +, \cdot\rangle\approx_{S A}
\langle M_n({\Bbb Z}); \plus, \mult \rangle$
и \\
${\cal B}_{SA}(M_n({\Bbb Z}); \plus, \mult)=
\{\forall\exists, \exists\forall, \forall\neg\vee, \exists\neg\wedge \}$. \par
\smallskip
\centerline{\bf Литература}
\par
\smallskip
\noindent
[1]\ \parbox[t]{135mm}{{\it Важенин Ю.М.} Множества, логика, алгоритмы.
Учебн. пособие. Екатеринбург: УрГУ, 1995.~--- 152 c.}\par
\smallskip
\noindent
[2]\ \parbox[t]{135mm}{{\it Важенин Ю.М.} О границах разрешимости
матричных колец // Вторые математические
чтения, посвященные памяти М.Я. Суслина. Тезисы докладов. Саратов,
1991.~ С.~82.} \par \smallskip \noindent [3]\
\parbox[t]{135mm}{{\it Важенин Ю.М., Нагребецкая Ю.В.} О границах
разрешимости колец целочисленных матриц // Международная
алгебраическая конференция, посвященная памяти Д.К. Фаддеева.
Тезисы докладов. Санкт-Петербург, 1997.~С.~178.}