О границах разрешимости групп и полугрупп преобразований бесконечного множества

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


Пусть $ISym$ и $IPar$~--- классы всех бесконечных симметрических групп
и всех инверсных полугрупп преобразований бесконечных множеств, рассматриваемых
в сигнатуре $\langle \cdot, ^{-1}, 1 \rangle$.
Зафиксируем произвольные $S\in ISym$ и $P\in IPar$.
В~[1] анонсирован следующий результат: теории
$\forall\neg\vee ISym$, $\exists\neg\wedge ISym$, $\forall\neg\vee S$,
$\exists\neg\wedge S$ являются $SA$-критическими~[2], теории
$\forall\exists\forall ISym$, $\exists\forall\exists ISym$,
$\forall\exists\forall S$, $\exists\forall\exists S$
неразрешимы.
Следующее утверждение является существенным продвижением
в решении проблемы границы разрешимости~[2] для классов $ISym$, $IPar$,
группы $S$ и полугруппы $P$.\par
\smallskip
{\bf Теорема}. Теории
$\exists\forall\wedge\vee ISym$,
$\exists\forall\wedge\vee IPar$,
$\exists\forall\wedge\vee S$,
$\exists\forall\wedge\vee P$
разрешимы, теории
$\forall\exists\forall IPar$, $\exists\forall\exists IPar$,
$\forall\exists\forall P$, $\exists\forall\exists P$
неразрешимы.\par
Таким образом, возникет естественный вопрос о
неразрешимости $\forall\exists$-теорий
вышеперечисленных классов и алгебраических систем. При
положительном ответе на этот вопрос будет справедлив \par
\smallskip
{\bf Гипотеза}. Границей разрешимости классов $ISym$, $IPar$ и алгебраических
систем $S$ и $P$ является множество
$\{\forall\neg\vee, \exists\neg\wedge, \forall\exists, \exists\forall\neg\}$.
\par
\bigskip
\centerline{\bf Литература}
\par
\medskip
\noindent
[1]\ \parbox[t]{133mm}{{\it Маевский В.В.} Об ограниченных теориях
бесконечных групп и полугрупп~// Международная конференция по алгебре,
посвященная памяти А.И.~Мальцева. Тезисы докладов. Новосибирск,
1989.---~C.~73.}\par
\medskip
\noindent [2]\ \parbox[t]{133mm}{{\it Важенин Ю.М.} Множества, логика, алгоритмы.
Учебн. пособие. Екатеринбург: УрГУ, 1995.~--- 152 c.}\par
\smallskip
\noindent
\par
}