Теория групп. Введение ч.1
С этой статьи мы начнем цикл, посвященный основам теории групп. Пока будет лишь дана мотивация основных определений, каких-то специальных знаний не потребуется, достаточно школьных знаний на уровне ~7 класса.
В конце каждой статьи будет пара задач, решение которых можно будет найти либо в следующей статье, либо в книге «Системная математика в понятном изложении» Владимира Колонцова, которую я куда-нибудь прикреплю.
Чтобы первое знакомство с группами было комфортным, мы отложим абстрактное определение до конца статьи и обсудим примеры, которые сделают определение наиболее естественным.
Симметрии
Рассмотрим обычный равносторонний треугольник АВС. Он обладает симметрией: при повороте вокруг его центра на 120 градусов треугольник возвращается на место, лишь меняется порядок вершин. Будем обозначать положение треугольника порядком вершин против часовой стрелки, начиная с верхней.
Если нам зачем-то придет в голову обозначать такой поворот отдельной буквой, например R, то изменение порядка вершин можно условно записать так:
R(ABC) = CAB
Договоримся также обозначать последовательное применение двух поворотов, как их умножение R×R = R².
Тогда запись R²(ABC) = BCA означает, что мы два раза повернули треугольник АВС на 120 градусов.
Но повернув треугольник три раза мы придем к изначальному расположению вершин, то есть
R³(ABC) = ABC
Обозначим R³ = 1, ведь мы можем считать, что при трехкратном повороте мы просто не трогали треугольник. Но почему единица? Раз мы обозначаем два последовательных поворота как умножение, то хотелось бы, с одной стороны, чтобы выполнялось интуитивное равенство R×1 = R.
С другой стороны, если мы сначала повернули треугольник, а затем не сделали с ним ничего, это, очевидно, равноценно тому, что мы его просто повернули, и если обозначить ничегонеделанье как 1, то мы приходим к тому же равенству R×1 = R.
Получилось такое множество операций над треугольником — {1, R, R²}, которые мы умеем умножать друг на друга. Можно даже составить таблицу умножения всех этих элементов друг на друга:
Всё, к чему мы пока пришли, это ввели странную систему обозначений, чтобы крутить бедный треугольник. Но зачем? Придется подождать, чтобы мы увидели объект, который хотим описать, так что терпение)
Деление с остатком
Как вы помните (надеюсь) со школы, при делении целых чисел друг на друга, не всегда в итоге получаются целые. Для этого вводится деление целых чисел с остатком.
К примеру, деление произвольного целого числа z на 3 с остатком можно записать так:
z = 3k + r
Здесь r — остаток, а k — неполное частное.
При делении любого целого числа на n остаток не будет превосходить n - 1, иначе частное можно было бы увеличить ещё на 1. Таким образом, остатки при делении на число n могут быть от 0 до n - 1 (остаток 0 мы полагаем, когда число делится нацело).
На примере тройки, выпишем остатки при делении всех целых чисел на 3 подряд.
Как мы видим, остатки зациклились, так будет при делении на любое число.
Каждому целому числу мы можем поставить в соответствие один из n остатков при делении на n. Таким образом, при конкретном n из целых чисел выделяются подмножества эквивалентных чисел, тех, которые имеют одинаковые остатки при делении на n.
Это называется факторизация. Факторизация — это разделение исходного множества на подмножества, в каждом из которых элементы эквивалентны друг другу по некоторому отношению эквивалентности. Неформально, это некоторое правило, по которому мы для каждой пары объектов можем сказать, эквивалентны они или нет. Получившийся набор подмножеств называется фактормножеством. Мы ещё обсудим понятие отношения в другой статье, а пока достаточно интуитивного представления.
Из целых чисел при делении на 3 получилось фактормножество {0,1,2}. Это также можно воспринимать как функцию r, которая каждому элементу из множества целых чисел ℤ в наше множество {0,1,2}
r: ℤ → {0,1,2}
(обозначение f: X → Y означает, что функция f имеет область определения — множество X и область значений — Y)
Итак, если мы каждому числу ставим в соответствие некоторый остаток при делении на 3, тогда если числа нам важны только с точки зрения делимости на 3, мы можем вместо чисел рассматривать их остатки.
Но с числами мы могли производить много разных операций. Все те же операции можно ввести и для остатков, к примеру за сумму остатков от x и от y мы можем принять остаток от их суммы x + y, за произведение — остаток от произведения и т.д.:
r(x) + r(y) = r(x+y)
Можно выписать таблицу сложения остатков для деления на 3:
Уже можно было бы увидеть сходство с таблицей умножения поворотов треугольника, но мы пока притворимся, что ничего не заметили)
Перестановки
Треугольники и числа довольно привычны для нас ещё со школы, так что сейчас хотелось бы привести более абстрактный пример.
Возьмем абсолютно произвольное множество из трех элементов
A = {x, y, z}
Вообще-то в произвольном множестве элементы не упорядочены и от изменения порядка перечисления элементов множество не изменится:
{x, y, z} = {x, z, y} = {y, z, x} = …
Но можно составить из элементов множества упорядоченный набор, такое множество называют кортеж — (x, y, z) ≠ (y, z, x).
Часто возникает задача найти число всех кортежей из n элементов. Показать, что это число равно n! (факториал) оставляется читателю в качестве упражнения :)
Так как во всех кортежах одинаковый набор элементов, можно попытаться сделать из одного кортежа другой. Для этого определим функцию, которая каждому элементу из кортежа ставит элемент из кортежа (быть может, тот же самый), то есть осуществляет перестановку элементов кортежа. Главное. чтобы двум разным элементам не был поставлен в соответствие один и тот же.
Применив к кортежу одну перестановку, можно применить к результату новую перестановку, то есть осуществить композицию перестановок.
Мы уже встречались с последовательным применением действий в первом пункте, когда к результату одного поворота применяли другой.
Когда к действию одной функции мы применяем другую, это не отличается от того, как если бы мы к изначальному элементу применили некоторую новую функцию, композицию тех двух функций. Тогда можно определить операцию, которая паре функций ставит в соответствие третью, мы отвлекаемся от элементов, на которые действуют эти функции и рассматриваем операции уже между функциями.
Таким образом можно определить операцию, которая берет две перестановки и ставит им в соответствие третью. Из всех перестановок будет одна, которая выполняет роль отсутствия поворота треугольника из первого примера, это перестановка, которая каждый элемент кортежа переводит в него же. И так же, подобно единице при умножении, эта перестановка при композиции не будет ничего менять. Назовем эту перестановку тождественной.
Рассмотрим такую перестановку: x → x, y → z, z → y
При повторном применении, то есть при композиции с самой собой, все элементы вернутся в изначальные места, то есть композиция этой перестановки с самой собой дает тождественную. На самом деле, абсолютно к любой перестановке можно построить такую, которая с ней в композиции даст тождественную.
Рассмотрим произвольный элемент х, пусть перестановка переводит его в у. Если в новой перестановке элемент у будет переходить в х, тогда при композиции х вернется в себя. Если мы построим новую перестановку по такому принципу, пройдясь по всем элементам, тогда после композиции каждый элемент перейдет в себя, то есть будет тождественная перестановка.
Если построить композицию трёх функций, то, казалось бы, нужно уже пользоваться скобками, чтобы определить порядок действия функций, но диаграмма ниже наглядно (я надеюсь) поясняет, что результат от расстановки скобок зависеть не будет.
И так как речь здесь не про перестановки, а про произвольные функции, композиция никаких функций не будет нуждаться в расстановке скобок.
Итог
Из всех этих примеров мы вынесем те свойства, которые верны для каждой построенной системы и создадим из них новый объект, который назовем группой.
Группой будем называть некоторое множество G, между элементами которого определена бинарная операция (бинарная — берет два элемента и делает из них третий), назовем её умножением ×, причем для всех элементов из G выполнены следующие требования:
1) Ассоциативность
Речь лишь о независимости от расстановки скобок:
(x × y) × z = x × (y × z)
2) Существование единичного элемента
Во множестве G найдется такой элемент е, что для всех других элементов группы выполнено:
е × x = x × e = x
3) Существование обратных элементов
Для каждого элемента в группе найдется такой элемент, что их произведение равно единичному элементу:
x × y = y × x = e
В качестве упражнений оставляю доказать, что единичный элемент в группе единственный и что для каждого элемента обратный к нему единственный.
Всем удачи, ждите продолжения :)
Учебник Колонцова: