Лемма Шрайера (Lybbg Ojgwyjg)

Перейти к навигации Перейти к поиску

Лемма Шрайера — теорема из теории групп, использующаяся в алгоритме Шрайера-Симса. Теорема была доказана Отто Шрайером в 1927 году[1].

Из теоремы следует, что у конечно порождённой группы любая подгруппа с конечным индексом также является конечно порождённой[2].

Формулировка

[править | править код]

Пусть  — некоторая подгруппа конечно порождённой группы с порождающим множеством , то есть, .

Пусть  — трансверсаль левых смежных классов . Обозначим через представителя смежного класса, в котором содержится .

В таких обозначениях подгруппа порождена множеством .

Доказательство

[править | править код]

Формулировка для орбит

[править | править код]

В алгоритме Шрайера — Симса теорема применяется для специфического случая когда действует на множестве и является стабилизатором некоторого элемента .

Между элементами орбиты и трансверсалью есть взаимо-однозначное соответствие. А именно, все элементы одного смежного класса переводят в один и тот же элемент орбиты.

Поэтому обозначим через элемент , который переводит в , то есть, . В таких обозначениях лемму можно записать следующим образом: .

Примечания

[править | править код]
  1. Otto Schreier. Die Untergruppen der freien Gruppen // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1927-12. — Т. 5, вып. 1. — С. 161–183. — ISSN 1865-8784 0025-5858, 1865-8784. — doi:10.1007/bf02952517.
  2. Hall, Marshall 1910-1990 Verfasser. The Theory of Groups. — ISBN 9780486816906, 0486816907.