Дискретная математика (стр. 3 )

Единичный элемент всегда единственен, так как если бы существовал второй единичный элемент e`, то e*e` = e и e*e` =e`, отсюда e = e`.

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

Теорема: если операция ассоциативна, то результат её последовательного применения к n элементам множества, на котором она определена, не зависит от расстановки скобок. Доказательство индукцией по n. При n=3 - это закон ассоциативности. Сделаем индуктивное предположение, что теорема верна для (n-1) сомножителя. Получим из этого, что она верна и для n сомножителей.

Для этого достаточно доказать, что для каждых k и t, где 1 <= k < t <= n-1 (a(1)*a(2)*…*a(k))*(a(k+1)*…*a(n)) = (a(1)*a(2)*…*a(t))*(a(t+1)*…*a(n)),так как внутри скобок расстановка их несущественна по индуктивному предположению. Для каждого 1 <= j <= n a(j) – это элемент множества – носителя операции. Пользуясь индуктивным предположением, представим рассматриваемое равенство в виде: (a(1)*a(2)*…*a(k))*((a(k+1)*…*a(t))*(a(t+1)*…*a(n))) = ((a(1)*a(2)*…*a(k))*(a(k+1)*…*a(t)))*(a(t+1)*…*a(n)). Другими словами, вторую скобку левой части равенства разобьём на две скобки, так же как и первую скобку правой части равенства.

Во второй скобке левой части число сомножителей (n-k) не меньше двух, так как k<(n-1), то и (n-k)>1. В первой скобке правой части число сомножителей (t) тоже не меньше двух, так как t>1. Одновременно t и (n-k) не могут быть равны двум при n>3: если t=2, то k=1 и при (n-k)=2 получаем, что n=3.

Операция не выводит из множества и, значит, каждую из трёх полученных скобок можно заменить соответствующим ей элементом множества: a(p)*(a(s)*a(w)) = (a(p)*a(s))*a(w)), где a*(p)= a(1)*a(2)*…*a(k), a(s)= (k+1)*…*a(t) и a(w)= a(t+1)*…*a(n). При t=2 a(p)=a(1) и a(s)=a(2). При (n-2)=2 a(s)=a(n-1) и a(w)=a(n). Полученное равенство является законом ассоциативности. Теорема доказана.

Алгебры, решётки

Алгеброй называется множество с заданными на нём операциями. Множество называется носителем алгебры. Множество {0, 1, 2, 3} с операциями сложения и умножения по модулю четыре – это алгебра с двумя операциями. Множество из четырёх поворотов 0, 90, 180 и 270 градусов с операцией наложения поворотов – это алгебра с одной операцией. Множество действительных чисел с обычными (привычными нам) операциями сложения и умножения - это алгебра с двумя операциями.

Множество – носитель решётки – это частично упорядоченное множество. В решётке определены две ассоциативных операции – верхняя (условно обозначается ) и нижняя (условно обозначается ) грани. Таким образом, в решётке две операции и отношение порядка.

Множество целых чисел – это линейно упорядоченное множество. Верхняя грань ab=max(a, b). Нижняя грань ab = min(a, b). Получили решётку.

Определим на натуральных числах частичный порядок: a <= b, если a нацело делит b. Верхняя грань a и b – это их наименьшее общее кратное, а нижняя – наибольший общий делитель. Получили решётку.

Множество B – это множество двоичных векторов длины n. Двоичное число v длины n не больше двоичного числа w длины n, если каждый разряд (позиция) числа v не превышает соответствующего разряда числа w. Например, для n = 3 двоичное число 010 не больше двоичного числа 011, а двоичные числа 010 и 100 не сравнимы. Диаграмма Хассе для введённого частичного порядка на B:

 

 

Операции: vw (верхняя грань) – это поразрядное (побитное) or, а vw (нижняя грань) – это поразрядное (побитное) and. Например: 100010 = 110, 011101 = 111, 100010 = 000, 011101 = 001. Для поразрядных операций двоичные числа удобно писать друг под другом. Получили решётку. Из диаграммы Хассе видно, что верхняя грань vw находится в диаграмме выше v и w и соединена с ними, тогда как нижняя грань – ниже и тоже соединена.

Множество – степень P(M) частично упорядочено по отношению включения подмножеств множества M: M(j)<=M(k), если M(j)M(k). Здесь M(j) M и M(k) M. Верхняя грань – это объединение подмножеств, а нижняя – их пересечение. Получили решётку.

Упорядоченное множество не является решёткой, если существуют такие v и w, что у них нет верхней или нижней грани или какая-то из граней не единственна. По вышеприведённой диаграмме Хассе для отношения Парето видно, что элементы <1,2> и <2,1> (не сравнимые) не имеют нижней грани, а элементы <3,2> и <2,3> (тоже не сравнимые) не имеют верхней грани. Значит, это отношение Парето не решётка.

В вышеприведённой диаграмме Хассе с шестью элементами a, b, c, d, e и f у не сравнимых между собой двух элементов b и c имеется две верхних грани, а у не сравнимых между собой двух элементов d и e имеется две нижних грани. Значит, и этот частичный порядок с данной диаграммой Хассе не решётка.

В решётке операции верхней и нижней граней ассоциативны (без доказательства), поэтому говорят о верхних и нижних гранях конечного подмножества элементов решётки. Верхняя грань всех элементов конечной решётки – это её max, а нижняя – min. В решётке для частичного порядка на B max = 111, а min – 000.

Глава 5. Алгебры с одной операцией: полугруппы, моноиды, группы

Множество с заданной на нём бинарной ассоциативной операцией, называется полугруппой. Для проверки, является ли множество относительно данной операции полугруппой, надо выяснить два вопроса: не выводит ли операция из множества и ассоциативность самой операции. Примером бесконечной полугруппы является множество слов алфавита A = {a1, a2, … ,an} с операцией приписывание первого слова ко второму. Из двух слов после приписывания получается новое слово. Операция ассоциативна, так как порядок получения итогового слова из трёх исходных не влияет на результат. Всё равно, или мы сначала припишем второе слово к первому, а уже к ним – третье, или сначала припишем третье слово в конец второго, а затем полученное слово припишем к первому.

Бесконечной полугруппой является и множество натуральных чисел с операцией наибольший общий делитель (nod). Операция nod ассоциативна, так как nod(x, nod(y, z)) = nod(nod(x, y),z) = наибольшему общему делителю(x, y,z). Операция nod не выводит из множества натуральных чисел, так как наибольший общий делитель тоже натуральное число.

Полугруппа может быть коммутативной и не коммутативной. Рассмотренная полугруппа с операцией приписывание слов не коммутативна, а полугруппа с операцией nod – коммутативна.

Моноид – это полугруппа с единичным элементом. Примерами коммутативных моноидов на множестве {1, 2, 3, 4} являются моноиды с операциями max и min:

Операционной единицей по операции max является минимум множества {1, 2, 3, 4} – 1, а операционной единицей по операции min является максимум этого множества – 4. В таблице Кэли операционную единицу удобно писать первым элементом. Единичный элемент множества не меняет ни верхней строки таблицы, ни правого её столбца (то есть самого множества).

Примерами коммутативных моноидов на множестве двоичных чисел длины n являются моноиды с поразрядными операциями or и and. Операционной единицей по операции поразрядного or является двоичное слово длины n, состоящее из одних нулей, а операционной единицей по операции поразрядного and является двоичное слово длины n, состоящее из одних единиц.

Примеры таких моноидов для n = 1 и n = 2:

Коммутативными моноидами являются моноиды на множестве - степени P(X) с ассоциативными операциями or и and. Эти операции не выводят из множества – степени. Операционной единицей по операции or является пустое множество, а операционной единицей по операции and является само множество X.

Примерами бесконечных коммутативных моноидов на целых неотрицательных числах являются моноиды с операциями обычных сложения и умножения. Операционной единицей по сложению является ноль, а операционной единицей по умножению – единица.

Примером бесконечного коммутативного моноида на натуральных числах является коммутативный моноид с операцией получения наименьшего общего кратного (nok). Операция nok ассоциативна, так как nok(x, nok(y, z)) = nok(nok(x, y),z) = наименьшему общему кратному(x, y,z). Операция nok не выводит из множества натуральных чисел, так как наименьшее общее кратное тоже натуральное число.

Операционной единицей по операции nok является 1, так как для любого x nok(1,x) = nok(x,1) = x. Заметим, что в отличие от операции nok у операции nod нет оперативной единицы.

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

Элемент моноида a называется обратимым, если в моноиде существует обратный ему элемент a, такой что a*a=a*a=e. Моноид, все элементы которого обратимы, называется группой. Коммутативный моноид иногда называется абелевым. У группы могут быть подгруппы, если операция не выводит из подгруппы. В подгруппе всегда есть единичный элемент, и для каждого элемента в подгруппе есть обратный. Подгруппа называется собственной, если она отлична от самой группы.

Пересечение подполугрупп – это подполугруппа, пересечение подмоноидов – это подмоноид (а может быть и подгруппа), а пересечение подгрупп – это подгруппа. Это следует из того, что операционная единица находится во всех подмоноидах и во всех подгруппах, и, значит, находится в их пересечении. Если взять любой не единичный элемент из пересечения подгрупп, то он будет находиться во всех подгруппах пересечения, и, значит, там же находится и обратный взятому элементу элемент, а по определению пересечения этот обратный элемент находится и в пересечении подгрупп.

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

Обратный элемент единственен. Пусть a * b = b * a = e и существует b`: a * b` = b` * a = e. Тогда b` = e * b` = (b * a) * b` = b * (a * b`) = b * e = b. Очевидно, что (a) = a. Произведение a * b обратимых элементов a и b тоже обратимо, так как, (a * b) * (b * a) = a * (b * b) * a = a * a = e. Получили, что (a * b) = b * a.

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

Все обратимые элементы моноида (если они есть) образуют группу. Таким образом, у моноида может быть подгруппа. Если операция коммутативна, то группа будет коммутативной или абелевой. У группы могут быть подгруппы. Например, рассмотрим коммутативный моноид на множестве {0, 1, 2, 3} с операцией целочисленного умножения по модулю четыре:

При целочисленном умножении целые числа – операнды перемножаются, а результат операции берётся по модулю четыре. Единицей по операции целочисленного умножения является 1. Справа от моноида приведена его коммутативная подгруппа, состоящая из единичного элемента (1) и обратимого элемента (3), обратного самому себе.

Операции целочисленного умножения и сложения по модулю n ассоциативны, так как если результатом одной операции является число вида n*t + k, где t > 0, а k – это остаток, то при второй операции, в которой число n*t + k будет операндом, на результат операции число n*t не влияет.

Примером коммутативной группы порядка четыре является множество из четырёх поворотов на 0, 90, 180 и 270 градусов с операцией наложения поворотов. Элемент 180 градусов обратен сам себе, а элементы 90 и 270 градусов обратны друг другу.

Коммутативной группой порядка n (n > 1) на множестве {0, 1, … , n-1} является группа с операцией сложения по модулю n. Операционной единицей по сложению по модулю n является 0, а обратным элементу k при 1 < k < n является элемент n - k, так как n – k + k = n, а n равен 0 по модулю n.

Коммутативной группой порядка (p – 1) на множестве {1, 2, …, (p-1)} является группа с операцией умножения по модулю p (p – простое число и p > 1). Например, при p = 5 таблица Кэли для этой группы имеет вид:

Операционной единицей по умножению по модулю n является элемент 1. Обратным элементу 4 является он сам, а элементы 2 и 3 обратны друг другу. Заметим, что в групповой таблице Кэли в каждой её строке и в каждом столбце находятся все элементы группы, и все строки и все столбцы разные. Отсюда, в частности, следует, что двух одинаковых элементов в строке или в столбце групповой таблицы Кэли быть не может.

Бесконечной коммутативной группой на целых (на рациональных, на действительных) числах является группа с обычной операцией сложения. Обратным элементом по сложению элементу x является элемент –x. Бесконечной коммутативной группой на рациональных (на действительных) числах является группа с операцией умножения. Обратным элементом по умножению элементу x является элемент 1/x.

Порядок элемента q в группе – это q = min(q`: a= e). У каждого элемента в группе есть порядок. Можно считать, что порядок e равен единице. У элемента группы, обратного самому себе, порядок равен двум. В группе с операцией умножения по модулю p элементы 2 и 3 имеют порядок четыре.

В группе каждый не единичный элемент a порядка q образует так называемую циклическую подгруппу порядка q: {a, a= a*a, … ,a=a, e}. Циклическая подгруппа всегда коммутативна.

Циклические группы и группы подстановок

Если группа состоит из всех степеней одного элемента, то она называется циклической. Циклическими группами порядка четыре являются группа H из четырёх поворотов на 90, 180, 270 и 0 градусов, группа G на множестве {0, 1, 2, 3} с операцией сложения по модулю четыре и группа W на множестве {1, 2, 3, 4} с операцией умножения по модулю пять.

Группа H = {90гр., 180гр., 270 гр., 0гр.} = {270гр., 180гр., 90гр., 0гр}. Как видно, образующих циклическую группу элементов несколько, для группы H их два: 90 и 270 градусов. Их порядок равен порядку H. Элемент 180 градусов образует циклическую подгруппу порядка два группы H.

Группа G = {1, 2, 3, 0} = {3, 2, 1, 0}. Здесь образующими циклическую группу G могут быть элементы или 1, или 3, а элемент 2 образует подгруппу группы G. Группа W = {2, 4, 3, 1} = {3, 4, 2, 1}. Здесь образующими циклическую группу W могут быть элементы или 2, или 3, а элемент 4 образует подгруппу группы W.

Группа сложения по модулю пять на множестве {0, 1, 2, 3, 4} – это циклическая группа порядка пять:

Циклическая группа порядка пять может быть образована любым своим не единичным элементом. Циклическая группа всегда коммутативна. Всякая подгруппа циклической группы тоже циклична. Например, у циклической группы порядка шесть на множестве {0, 1, 2, 3, 4, 5} и с операцией сложения по модулю шесть есть циклическая подгруппа порядка три на множестве {0, 2, 4} и циклическая подгруппа порядка два на множестве {0, 3}.

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

Например, возьмём целые числа и обычную операцию сложения. Образуют эту бесконечную не циклическую группу элементы 1 и (-1), так как сколько ни прибавляй 1 к 1, (-1), нуля никогда не получишь. У этой группы есть подмоноиды. Например, подмоноидом этой группы являются все целые неотрицательные числа с операцией сложения.

Группы порядков два и три могут быть только циклическими:

Здесь справа от заполненной таблицы Кэли для циклической группы порядка три приведена она же, но заполненная только для единичного элемента – 0. Как работает единичный элемент – ясно всегда. На месте 1*1 элемент 0 поставить нельзя, так как тогда в этой строке под элементом 2 окажется тоже элемент 2, а в каждой строке и каждом столбце групповой таблицы Кэли должны быть разные элементы. Отсюда группа порядка три может быть только циклической.

Групп порядка четыре – две, и одна из них циклическая. Не циклической группой порядка четыре является коммутативная четвертная группа Клейна V4 = {a, b, c, d}, в которой каждый элемент обратен сам себе:

Справа приведена таблица Кэли с заполненными строкой и столбцом для единичного элемента a и заполненной элементами a главной диагональю, так как в V4 все элементы имеют порядок два. На пересечении элементов b и с (аналогично c и b) можно поставить только элемент d, далее на пересечении элементов b и d – только элемент c, и окончательно на пересечении элементов d и с – только элемент b.

Для получения всей группы V4 достаточно любых двух не единичных элементов: b и c, или b и d, или c и d. Интересным является вопрос, сколько надо элементов для получения не циклической группы. Теоретически на него пока ответа нет, а вот практически получается, что только два. Алгоритм решения этого вопроса такой: берутся два элемента, не входящие в одну циклическую подгруппу не циклической группы (желательно больших порядков) и последовательно перемножаются все их степени и результаты предыдущих перемножений до тех пор, пока новых элементов после очередного перемножения больше не получается. Если полученная подгруппа совпадает с самой группой, то два исходных элемента вместе являются порождающей парой для не циклической группы.

У не циклической группы циклических подгрупп не менее трёх. Например, у четвертной группы Клейна V4 ровно три циклических подгруппы порядка два. Результат перемножения любых двух элементов из различных циклических групп не циклической группы не может находиться ни в одной из этих циклических подгрупп. Отсюда он находится в какой-то третьей циклической подгруппе, так как каждый элемент не циклической группы обязательно входит в циклическую подгруппу.

Группа всех биекций конечного множества мощности n (n > 1) в себя называется симметрической группой степени n и обозначается S. Порядок её равен n!. Это не коммутативная группа. Каждая биекция называется подстановкой и записывается так:. Каждое iпоказывает, в какой элемент множества мощности n перешёл элемент k этого множества. Например, для n = 3 циклический сдвиг записывается подстановкой: . При этом сдвиге (биекции) 1 переходит в 2, 2 – в 3 и 3 - в 1. Верхний вектор у всех подстановок при фиксированном n один и тот же, поэтому подстановку можно записывать только нижним вектором длины n.

Например, Sсостоит из шести элементов: {, , , , , }. Эти шесть биекций можно проиллюстрировать как самосовмещения равностороннего треугольника с пронумерованными вершинами:

 

Первая биекция из симметрической группы степени три – это единичная биекция, когда треугольник остаётся на месте. Вторая биекция – это поворот на 120 градусов по часовой стрелке (120). Третья биекция – это поворот на 240 градусов по часовой стрелке (240). Четвёртая биекция – это симметрия относительно биссектрисы, проходящей через первую вершину (1). Пятая биекция - это симметрия относительно биссектрисы, проходящей через третью вершину (3). Шестая биекция - это симметрия относительно биссектрисы, проходящей через вторую вершину (2).

Произведением подстановок f и g является композиция отображений: (fg)(k) = f( g( k )). Например, f = и g = , тогда fg = . Элемент 1 множества {1, 2, 3, 4} сначала биекцией g переводится в элемент 2 того же множества, а затем биекцией f элемент 2 переводится в элемент 3. Итого, элемент 1 композицией биекций fg переводится в элемент 3. Аналогично, элемент 2 сначала биекцией g переводится в элемент 3, а затем биекцией f элемент 3 переводится в элемент 2. Итого, элемент 2 композицией биекций fg не меняется, остаётся самим собой: 2.

Элемент 3 сначала биекцией g переводится в элемент 4, а затем биекцией f элемент 4 переводится в элемент 1. Итого, элемент 3 композицией биекций fg переводится в элемент 1. Элемент 4 сначала биекцией g переводится в элемент 1, а затем биекцией f элемент 1 переводится в элемент 4. Итого, элемент 4 композицией биекций fg не меняется.

Каждая подстановка является произведением независимых циклов. Например, подстановку можно записать и так: , поскольку элементы 1 и 3 остаются на своих местах в подстановке (циклы длины единица), а элемент 2 переходит в элемент 5, 5 – в 4 и 4 возвращается в элемент 2 (цикл длины три). Разумеется, циклравен цикламиЦикл длиной k можно записать k способами. Обычно циклы длиной единица не пишут.

Циклы независимы, так как не имеют в своём составе одинаковых элементов. При биекции один элемент переходит в один и только один элемент, поэтому в циклах не может быть одинаковых элементов. Порядок подстановки равен наименьшему общему кратному длин составляющих его циклов. Порядок подстановки равен трём.

Среди подстановок есть так называемые беспорядки, когда каждый из элементов при биекции не остаётся на своём месте. Беспорядки не содержат циклов длины единица. Например, беспорядком является подстановка =Порядок этой подстановки равен шести.

Среди беспорядков выделяют так называемые равноцикловые беспорядки, состоящие только из циклов равной длины, большей единицы. Например, подстановка6) является равноцикловым беспорядком. Если в биекции участвует простое число элементов (n – простое), то равноцикловые беспорядки в этом случае состоят из одного цикла. Например, для n = 5 подстановкаявляется равноцикловым беспорядком. Порядок равноциклового беспорядка равен длине составляющих его циклов.

Изоморфизм групп

Группы G и H изоморфны, если существует биекция f, переводящая G в H и сохраняющая групповую операцию: f(g1*g2) = f(g1)#f(g2) = h1#h2. Здесь групповая операция в группе G обозначена символом *, а в группе H – символом #. Например, симметрическая группа степени три изоморфна группе самосовмещений равностороннего треугольника, а группа классов вычетов по мод, 180 и 270 градусов (C переходит в 0 град., C- в 90, C - в 180 и C - в 270) и обе они изоморфны циклической группе порядка четыре.

Свойства изоморфизма: 1. Групповая единица e из группы G переходит в групповую единицу e` из группы H, так как f(e) # f(g) = f(e*g) = f(g) = f(g*e) = f(g) #f(e) для каждого g из группы G, то и f(e) = e`.

2. Обратный элемент переходит в обратный: f(g) = f(g) , так как f(g) # f(g) = f(g*g) = f(e) = e`. Аналогично получим, что f(g)#f(g) = e`.

3. Обратное отображение f, переводящее группу H в группу G тоже изоморфизм. Обратное отображение существует, поскольку f – биекция. Покажем, что f(h1#h2) = f(h1)*f(h2). Существуют g1 и g2, такие что f(g1) = h1 и f(g2) = h2. f(g1*g2) = f(g1) # f(g2) = h1# h2, значит, что g1*g2 = f(h1#h2) = f(h1)*f(h2).

Все циклические группы одного порядка изоморфны. Если порядок циклической группы равен числу k, то эта группа изоморфна группе поворотов, кратных углу 360/k градусов. Например, при k = 4 циклическая группа изоморфна группе поворотов на 0, 90, 180 и 270 градусов.

Группы одного порядка могут быть не изоморфными. Например, четвертная группа Клейна V4 не изоморфна циклической группе порядка четыре. Можно считать, что изоморфные группы – это одна и та же группа, только элементы и групповая операция обозначены иначе.

Теорема Кэли: каждая конечная группа порядка n изоморфна некоторой подгруппе симметрической группы S. Получается, что групп не много. Доказательство: пусть в группе G n элементов и первый из них – это групповая (операционная) единица. Каждый из n элементов имеет номер от 1 до n включительно. Составим таблицу Кэли для группы G, содержащую только номера элементов, а не сами элементы.

Каждому элементу группы G с номером k поставим в соответствие подстановку из симметрической группы степени n, в которой в качестве нижней строки взята соответствующая этому элементу строка из только что полученной таблицы Кэли. Фактически нижняя строка подстановки для номера k элемента группы содержит номера элементов группы G, полученные после воздействия элемента с номером k на верхнюю строку подстановки.

Например, для четвертной группы Клейна её элементы a, b, c и d получат номера 1, 2, 3 и 4 соответственно, а её таблица Кэли примет вид: Справа от таблицы Кэли приведены подстановки для элементов V4: элемент a получит первую, (самую левую) подстановку, элемент b – вторую и так далее. Заметим, что все подстановки, кроме первой, единичной подстановки, являются равноцикловыми беспорядками.

Множество полученных подстановок обозначим как H. Докажем, что H – это группа. Единичная подстановка в H есть. Произведение подстановок из H даст подстановку, соответствующую произведению элементов из G, которые соответствуют подстановкам – сомножителям. Другими словами, операция не выводит из H. Обратная подстановка тоже находится в H, достаточно взять строку для обратного элемента из G.

Группы G и H изоморфны, так как биекция сохраняет групповую операцию: всё равно, что сначала перемножаются элементы из G, а затем берётся строка, соответствующая полученному произведению, или перемножаются подстановки, что соответствуют тому же перемножению всех элементов группы G. Отсюда H – это подгруппа симметрической группы степени n. Теорема доказана.

Каждая полученная вышеописанным образом из групповой таблицы подстановка, кроме единичной, является равноцикловым беспорядком. Заметим, что каждая такая подстановка уже беспорядок, так как ни один элемент группы при умножении на другой не единичный элемент не совпадёт сам с собой.

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

Более точная формулировка теоремы Кэли: всякая конечная группа порядка n изоморфна некой подгруппе симметрической группы S, состоящей только из равноцикловых и единичной подстановок. В таблице истинности строка и столбец, соответствующие не единичному элементу группы, являются равноцикловыми беспорядками с длиной циклов, равной порядку этого элемента.

Смежные классы по подгруппе. Теорема Лагранжа

Если у группы G существует подгруппа H, то тогда группа разбивается относительно этой подгруппы на множество левых смежных классов. Левым смежным классом G по H называют множество элементов вида g*h, где g – фиксированный элемент из группы G, а h пробегает все элементы подгруппы H. Отсюда мощность любого левого смежного класса равна порядку подгруппы H.