Введение

Группа, операция которой является композицией перестановок.

В математике группа перестановок — это группа G, элементы которой являются перестановками заданного множества M, а групповая операция — композицией перестановок в G (которые рассматриваются как биективные функции из множества M в само себя). Группа всех перестановок множества M называется симметрической группой M и часто обозначается как Sym(M). Таким образом, термин "группа перестановок" обычно означает подгруппу симметрической группы. Если M = {1, 2, ..., n}, то Sym(M) обычно обозначается Sn и может называться симметрической группой на n элементах. Согласно теореме Кэли, каждая группа изоморфна некоторой группе перестановок. Способ, которым элементы группы перестановок переставляют элементы множества, называется ее групповым действием. Групповые действия находят применение в изучении симметрий, комбинаторики и многих других областях математики, физики и химии.

Основные свойства и терминология

Пермутационная группа — это подгруппа симметрической группы, то есть её элементы являются перестановками заданного множества. Следовательно, это подмножество симметрической группы, замкнутое относительно композиции перестановок, содержащее тождественную перестановку и содержащее обратную перестановку для каждого своего элемента. Общее свойство конечных групп подразумевает, что конечное непустое подмножество симметрической группы является пермутационной группой тогда и только тогда, когда оно замкнуто относительно композиции перестановок. Степенью группы перестановок конечного множества называется число элементов этого множества. Порядок группы (любого типа) — это число элементов (мощность) в группе. По теореме Лагранжа, порядок любой конечной пермутационной группы степени n должен делить n!, поскольку n факториал является порядком симметрической группы Sn.

Нейтральный элемент и инверсы

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

В циклической записи e = (1)(2)(3)…(n), что по соглашению также обозначается просто (1) или даже. Поскольку биекции имеют обратные, то и пермутации также, а обратная к σ, обозначаемая σ−1, снова является пермутацией. Явно, если σ(x) = y, то и σ−1(y) = x. В двухстрочной записи обратную пермутацию можно получить, поменяв местами строки (и отсортировав столбцы, если требуется заданный порядок первой строки). Например,

Чтобы получить обратную к одиночному циклу, нужно изменить порядок его элементов на обратный. Таким образом,

Чтобы получить обратную к произведению циклов, сначала меняем порядок циклов на обратный, а затем находим обратную к каждому циклу по вышеописанному правилу. Таким образом,

Наличие ассоциативной операции, нейтрального элемента и обратных элементов для всех элементов превращает множество всех перестановок множества M в группу, Sym(M); группу перестановок.

Первобытные действия

Группа перестановок G, действующая транзитивно на непустом конечном множестве M, называется импримитивной, если существует некоторое нетривиальное разбиение множества M, которое сохраняется при действии G, где под "нетривиальным" понимается разбиение, отличное от разбиения на одноэлементные множества и разбиения на единственную часть. В противном случае, если G действует транзитивно, но не сохраняет никаких нетривиальных разбиений M, то группа G называется примитивной. Например, группа симметрий квадрата является импримитивной относительно вершин: если вершины пронумерованы 1, 2, 3, 4 в циклическом порядке, то разбиение на пары противоположных вершин {1, 3}, {2, 4} сохраняется каждым элементом группы. С другой стороны, полная симметрическая группа на множестве M всегда примитивна.

Олигоморфные группы

Когда группа G действует на множество S, это действие может быть естественным образом расширено на декартово произведение Sn множества S, состоящее из n-ок элементов S: действие элемента g на n-ок (s1, ..., sn) задается формулой g(s1, ..., sn) = (g(s1), ..., g(sn)). Группа G называется олигоморфной, если действие на Sn имеет лишь конечное число орбит для каждого положительного целого числа n. (Это выполняется автоматически, если S конечно, поэтому термин представляет интерес главным образом в случае бесконечного S.) Интерес к олигоморфным группам обусловлен, в частности, их применением в теории моделей, например, при рассмотрении автоморфизмов в счетно-категорических теориях.

История

Изучение групп изначально выросло из понимания групп перестановок. Перестановки сами по себе были интенсивно изучены Лагранжем в 1770 году в его работе об алгебраических решениях полиномиальных уравнений. Эта область процветала, и к середине XIX века существовала хорошо разработанная теория групп перестановок, систематизированная Камилем Жорданом в его книге «Traité des Substitutions et des Équations Algébriques» 1870 года. Книга Жордана, в свою очередь, была основана на работах, оставленных Эваристом Галуа в 1832 году. Когда Кэли ввёл понятие абстрактной группы, сразу не стало ясно, представляет ли это собой более широкое множество объектов, чем известные группы перестановок (которые имели определение, отличное от современного). Кэли впоследствии доказал, что эти два понятия эквивалентны в теореме Кэли. Другим классическим трудом, содержащим несколько глав о группах перестановок, является «Теория групп конечного порядка» Бернсайда, опубликованная в 1911 году. Первая половина XX века была периодом застоя в изучении теории групп в целом, но интерес к группам перестановок возродился в 1950-х годах благодаря Г. Виландту, чьи немецкие лекционные заметки были переизданы под названием «Конечные группы перестановок» в 1964 году.