Теорема вложения Хигманса - Higmans embedding theorem - Wikipedia

В теория групп, Теорема вложения Хигмана заявляет, что каждый конечно порожденный рекурсивно представленная группа р может быть встроен как подгруппа некоторых конечно представленная группа грамм. Это результат Грэм Хигман с 1960-х гг.^[1]

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

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

Как следствие, Существует универсальная конечно определенная группа который содержит все конечно определенные группы как подгруппы (с точностью до изоморфизма); на самом деле его конечно порожденные подгруппы - это в точности конечно порожденные рекурсивно представленные группы (опять же с точностью до изоморфизма).

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

Обычное доказательство теоремы использует последовательность Расширения HNN начиная с р и заканчивая группой грамм который можно показать, чтобы иметь конечное представление.^[2]

Теорема вложения Хигманса - Higmans embedding theorem - Wikipedia

Рекомендации