Теорема Адяна – Рабина - Википедия - Adian–Rabin theorem

В математическом предмете теория групп, то Теорема Адяна – Рабина результат, который утверждает, что наиболее "разумные" свойства конечно представимые группы алгоритмически неразрешимый. Теорема связана с Сергей Адян (1955)^[1] и, независимо, Майкл О. Рабин (1958).^[2]

Марковская собственность

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

п является абстрактным свойством, то есть п сохраняется под групповой изоморфизм.
Существует конечно представимая группа ${ displaystyle A _ {+}}$ с собственностью п.
Существует конечно представимая группа ${ displaystyle A _ {-}}$ который не может быть встроен как подгруппа в любой конечно представимой группе со свойством п.

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

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

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

Позволять п - марковское свойство конечно представимых групп. Тогда не существует алгоритм что, учитывая конечное представление ${ displaystyle G = langle X mid R rangle}$ , решает, будет ли группа ${ displaystyle G}$ определяется этой презентацией, имеет свойство п.

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

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

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

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

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

По словам Дона Коллинза,^[7] понятие Марковская собственность, как определено выше, был введен Уильям Бун в его Математические обзоры обзор статьи Рабина 1958 г., содержащей доказательство Рабина теоремы Адяна – Рабина.

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

В современных источниках^[3]^[4] доказательство теоремы Адьяна – Рабина проводится путем сведения к Теорема Новикова – Буна. через умное использование амальгамированные продукты и Расширения HNN.

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

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

Приложения

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

Быть банальной группой.
Конечная группа.
Будучи абелева группа.
Будучи конечно порожденным свободная группа.
Будучи конечно порожденным нильпотентная группа.
Быть конечно презентабельным разрешимая группа.
Быть конечно презентабельным податливая группа.
Быть словесно-гиперболическая группа.
Конечнопредставимая группа без кручения.
Полициклическая группа.
Будучи конечно презентабельной группой с решаемая проблема со словом.
Быть конечно презентабельным финитно аппроксимируемая группа.
Будучи конечно представительной группой конечных когомологическая размерность.
Будучи автоматическая группа.
Быть конечно презентабельным простая группа. (Можно взять ${ displaystyle A _ {+}}$ быть тривиальной группой и ${ displaystyle A _ {-}}$ быть конечно определенной группой с неразрешимой проблемой слов, существование которой обеспечивается Теорема Новикова-Буна. потом Теорема Кузнецова подразумевает, что ${ displaystyle A _ {-}}$ не вкладывается ни в какую конечно представительную простую группу. Следовательно, быть конечно представимой простой группой - это марковское свойство.)
Будучи конечно представительной группой конечных асимптотическая размерность.
Будучи конечно представительной группой, допускающей равномерное вложение в Гильбертово пространство.

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

Смотрите также

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

К. Ф. Миллер, III, Решение задач для групп - обзор и размышления. Алгоритмы и классификация в комбинаторной теории групп (Беркли, Калифорния, 1989), стр. 1–59, Math. Sci. Res. Inst. Publ., 23, Springer, New York, 1992, стр. ISBN 0-387-97685-X

[1] С. И. Адян, Алгоритмическая неразрешимость задач распознавания некоторых свойств групп. (на русском) Доклады Академии Наук СССР т. 103, 1955, с. 533–535.

[R-2] Майкл О. Рабин, Рекурсивная неразрешимость теоретико-групповых задач, Анналы математики (2), т. 67, 1958, с. 172–194.

[LS-3] а ^б Роджер Линдон и Пол Шупп, Комбинаторная теория групп. Перепечатка издания 1977 года. Классика по математике. Springer-Verlag, Берлин, 2001. ISBN 3-540-41158-5; Гл. IV, теорема 4.1, с. 192

[B-4] а ^б Г. Баумслаг. Разделы комбинаторной теории групп. Лекции по математике ETH Zürich. Birkhäuser Verlag, Базель, 1993. ISBN 3-7643-2921-1; Теорема 5, с. 112

[5] Джозеф Ротман, Введение в теорию групп, Тексты для выпускников по математике, Springer, 4-е издание; ISBN 0387942858; Теорема 12.32, с. 469

[6] А. Марков, "Невозможность алгоритмов распознавания некоторых свойств ассоциативных систем" [Невозможность алгоритмов распознавания определенных свойств ассоциативных систем]. (на русском) Доклады Академии Наук СССР т. 77, (1951), стр. 953–956.

[Collins-7] а ^б Дональд Дж. Коллинз, О распознавании групп Хопфа, Archiv der Mathematik, т. 20. 1969. С. 235–240.

[1]

[2]

[3]

[4]

[5]

[6]

[7]