Теорема Адяна – Рабина

В математическом предмете теории групп теорема Адяна -Рабина является результатом, который утверждает, что большинство «разумных» свойств конечно представимых групп алгоритмически неразрешимы . Теорема принадлежит Сергею Адяну (1955). и независимо Майкл О. Рабин (1958).

Markov property

Марковское свойство P конечно представимых групп — это свойство, для которого:

1. P — абстрактное свойство, то есть P сохраняется при групповом изоморфизме .
2. Существует конечно представимая группа $A_{+}$ со П. свойством
3. Существует конечно представимая группа $A_{-}$ которая не может быть вложена как подгруппа ни в одну конечно представимую группу со свойством P .

Например, быть конечной группой — это марковское свойство: мы можем взять $A_{+}$ быть тривиальной группой , и мы можем взять $A_{-}$ быть бесконечной циклической группой $\mathbb {Z}$.

Точная формулировка теоремы Адяна–Рабина.

В современных источниках теорема Адяна–Рабина обычно формулируется следующим образом:

Пусть P — марковское свойство конечно представимых групп. Тогда не существует алгоритма , который при конечном представлении $G=\langle X\mid R\rangle$, решает, будет ли группа $G$ определенное этим представлением, имеет свойство P .

Слово «алгоритм» здесь используется в смысле теории рекурсии . Более формально, заключение теоремы Адяна – Рабина означает, что множество всех конечных представлений

$\langle x_{1},x_{2},x_{3},\dots \mid R\rangle$

(где $x_{1},x_{2},x_{3},\dots$ — фиксированный счетно бесконечный алфавит, и $R$ — конечное множество отношений в этих образующих и их обратных) определяющие группы со свойством P , не является рекурсивным множеством .

Исторические заметки

Утверждение теоремы Адяна–Рабина обобщает аналогичный более ранний результат для полугрупп Андрея Маркова-младшего : доказано аналогичными методами. Также в контексте полугруппы Марков ввел вышеупомянутое понятие, которое теоретики групп стали называть марковским свойством конечно определенных групп. Этого Маркова, выдающегося советского логика, не следует путать с его отцом, известным русским исследователем-вероятителем Андреем Марковым, в честь которого цепи Маркова и марковские процессы названы .

По словам Дона Коллинза, понятие марковского свойства , как оно определено выше, было введено Уильямом Буном в его обзоре Mathematical Reviews на статью Рабина 1958 года, содержащую доказательство Рабина теоремы Адяна-Рабина.

Идея доказательства

В современных источниках Доказательство теоремы Адяна–Рабина осуществляется путем сведения к теореме Новикова–Буна посредством умелого использования объединенных произведений и расширений HNN .

Позволять $P$ быть марковским свойством и пусть $A_{+},A_{-}$ быть таким, как в определении марковского свойства выше. Позволять $G=\langle X\mid R\rangle$ — конечно определенная группа с неразрешимой проблемой слов, существование которой обеспечивается теоремой Новикова–Буна .

Затем доказательство приводит к рекурсивной процедуре, которая по данному слову $w$ в генераторах $X\cup X^{-1}$ из $G$, выводит конечно представленную группу $G_{w}$ такое, что если $w=_{G}1$ затем $G_{w}$ изоморфен $A_{+}$, и если $w\neq _{G}1$ затем $G_{w}$ содержит $A_{-}$ как подгруппа. Таким образом $G_{w}$ имеет собственность $P$ тогда и только тогда, когда $w=_{G}1$. Поскольку неясно, является ли $w=_{G}1$, отсюда следует, что неразрешимо, обладает ли конечно определенная группа свойством $P$.

Приложения

Следующие свойства конечно определенных групп являются марковскими и поэтому алгоритмически неразрешимы по теореме Адяна – Рабина:

1. Будучи тривиальной группой .
2. Будучи конечной группой .
3. Будучи абелевой группой .
4. Быть свободной группой .
5. Будучи нильпотентной группой .
6. Будучи разрешимой группой .
7. Быть послушной группой .
8. Будучи словесно-гиперболической группой .
9. Будучи группой без кручения .
10. Будучи полициклической группой .
11. Быть группой с решаемой словесной проблемой .
12. Будучи аппроксимируемо конечной группой .
13. Будучи группой конечной когомологической размерности .
14. Быть автоматической группой .
15. Быть простой группой . (Можно взять $A_{+}$ быть тривиальной группой и $A_{-}$ быть конечно определенной группой с неразрешимой проблемой слов, существование которой обеспечивается теоремой Новикова-Буна . Тогда из теоремы Кузнецова следует, что $A_{-}$ не вкладывается ни в одну конечно представимую простую группу. Следовательно, быть конечно представимой простой группой — это марковское свойство.)
16. Будучи группой конечной асимптотической размерности .
17. Будучи группой, допускающей равномерное вложение в гильбертово пространство .

Заметим, что из теоремы Адяна–Рабина также следует, что дополнение к марковскому свойству в классе конечно представимых групп алгоритмически неразрешимо. Например, свойства нетривиальности, бесконечности, неабелевой и т. д. для конечно представимых групп неразрешимы. Однако существуют примеры интересных неразрешимых свойств, когда ни эти свойства, ни их дополнения не являются марковскими. Таким образом, Коллинз (1969) доказал, что свойство хопфианства неразрешимо для конечно представимых групп, при этом ни хопфовость, ни нехопфовость не являются марковскими.

См. также

• Теорема вложения Хигмана
• Теория Басса – Серра

Дальнейшее чтение

• К. Ф. Миллер, III, Проблемы принятия решений для групп — обзор и размышления . Алгоритмы и классификация в комбинаторной теории групп (Беркли, Калифорния, 1989), стр. 1–59, Math. наук. Рез. Инст. Публикация, 23, Спрингер, Нью-Йорк, 1992 г., ISBN   0-387-97685-X