Теорема Хигмана об вложении: любая конечно порожденная рекурсивно представленная группа вложима в конечно представленную. Свойства, следствия и связь с теоремой Новикова-Буна.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В теории групп теорема о вложении Хигмана утверждает, что каждая конечно порождённая рекурсивно представленная группа R может быть вложена как подгруппа в некоторую конечно представленную группу G. Это результат Грэма Хигмана, полученный в 1960-х годах. С другой стороны, существует простая теорема, утверждающая, что каждая конечно порождённая подгруппа конечно представленной группы рекурсивно представима, поэтому рекурсивно представленные конечно порождённые группы являются (с точностью до изоморфизма) точно конечно порождёнными подгруппами конечно представленных групп. Поскольку каждая счётная группа является подгруппой конечно порождённой группы, теорему можно переформулировать и для этих групп. Как следствие, существует универсальная конечно представленная группа, содержащая все конечно представленные группы в качестве подгрупп (с точностью до изоморфизма); фактически, её конечно порождённые подгруппы являются точно конечно порождёнными рекурсивно представленными группами (опять же, с точностью до изоморфизма). Теорема о вложении Хигмана также влечёт за собой теорему Новикова — Буна (первоначально доказанную в 1950-х годах другими методами) о существовании конечно представленной группы с алгоритмически неразрешимой проблемой о слове. Действительно, довольно легко построить конечно порождённую рекурсивно представленную группу с неразрешимой проблемой о слове. Тогда любая конечно представленная группа, содержащая эту группу в качестве подгруппы, также будет иметь неразрешимую проблему о слове. Стандартное доказательство теоремы использует последовательность расширений HNN, начинающуюся с R и заканчивающуюся группой G, для которой можно показать, что она имеет конечную презентацию.
In group theory, Higman's embedding theorem states that every finitely generated recursively presented group R can be embedded as a subgroup of some finitely presented group G. This is a result of Graham Higman from the 1960s. On the other hand, it is an easy theorem that every finitely generated subgroup of a finitely presented group is recursively presented, so the recursively presented finitely generated groups are (up to isomorphism) exactly the finitely generated subgroups of finitely presented groups. Since every countable group is a subgroup of a finitely generated group, the theorem can be restated for those groups. As a corollary, there is a universal finitely presented group that contains all finitely presented groups as subgroups (up to isomorphism); in fact, its finitely generated subgroups are exactly the finitely generated recursively presented groups (again, up to isomorphism). Higman's embedding theorem also implies the Novikov Boone theorem (originally proved in the 1950s by other methods) about the existence of a finitely presented group with algorithmically undecidable word problem. Indeed, it is fairly easy to construct a finitely generated recursively presented group with undecidable word problem. Then any finitely presented group that contains this group as a subgroup will have undecidable word problem as well. The usual proof of the theorem uses a sequence of HNN extensions starting with R and ending with a group G which can be shown to have a finite presentation.