Материал: Ответы на экзаменационные вопросы по дискретной математике

Элемент моноида — обратимый, если для него найдётся такой элемент из этого моноида , что , где — нейтральный элемент по отношению к операции «». Понятно, что элемент в таком случае тоже обратимый.

Этот элемент называется обратным по отношению к . Если выполняется только первое равенство (), то называется левым обратным элементом, а если только второе (), то правым. При этом называется соответственно обратимым слева и/или справа.

Теорема. Обратный элемент единственен.

Доказательство. Пусть и — два обратных элемента по отношению к . Тогда:

Не все элементы моноидов имеют обратные элементы. Например, в только и обратимы (остальные элементы имеют обратные, не принадлежащие , но принадлежащие ).

Теорема. Если и обратимы, то тоже обратим, при этом

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

Действительно, в силу ассоциативности операции «» выполняются равенства:

Следствие. Элемент также обратим, при этом .

Группы рассматриваются далее.

5. Группа. Абелева группа. Аддитивная группа. Мультипликативная группа. Конечная группа. Таблица Кэли. Циклическая группа. Декартово произведение групп Группа

Группа — моноид, все элементы которого обратимы. То есть группа — это множество , в котором введена бинарная операция «» (напомним, обязательно замкнутая), удовлетворяющая трём условиям:

1. Ассоциативность: .

2. Существует нейтральный элемент , то есть такой элемент, что для любого элемента справедливо равенство .

3. У каждого элемента существует обратный , то есть такой, что

Очевидно, что любая группа является полугруппой (моноидом), а обратное неверно.

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

Коммутативные группы (то есть группы, в которых операция «» коммутативна, то есть ) называют абелевыми. В них групповую операцию обычно называют сложением и обозначают «»; нейтральный элемент обозначают символом (нуль); обратный к называют противоположным элементом и обозначают «».

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

Если групповая операция — сложение, то группу называют аддитивной, а если умножение — мультипликативной.

Примеры:

1. Аддитивные абелевы группы: множества .

2. Мультипликативные абелевы: множества (у нуля нет такого обратного элемента , чтобы ); множество мультипликативной группой не является, так как в нем всего лишь два обратимых элемента — и .

3. Множество является мультипликативной абелевой группой.

4. Группа (рациональных чисел) — подгруппа аддитивной абелевой группы (вещественных чисел), а множество — всех положительных вещественных чисел — подгруппа мультипликативной абелевой группы .

5. Множество — (целых чисел, кратных , в частности — чётных чисел) — подгруппа аддитивной абелевой группы .

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

7. Матрицы одного размера образуют аддитивную абелевую группу.

8. Множество квадратных невырожденных () матриц порядка образуют (некоммутативную) мультипликативную группу.

9. Множество целых комплексных (гауссовых) чисел вида (то есть ) — аддитивная абелева группа.

10. Множество степеней двойки: — мультипликативная абелева группа.

11. Множество комплексных единиц: — мультипликативная абелева группа. Может быть охарактеризована как группа корней четвертой степени из единицы.

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

Теорема. Для любых уравнения и однозначно разрешимы.

Доказательство. Рассмотрим уравнение .

Существование решения. Легко проверить, что ( — обратный к ) является решением данного уравнения.

Единственность решения. Пусть — решения уравнения . Тогда и , откуда . Умножим равенство слева на и, воспользовавшись свойством ассоциативности, получим .

Уравнение рассматривается аналогично.

Таблица Кэли

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

Пример. Множество — является мультипликативной группой (нейтральный элемент: ; обратный элемент сама : ). Таблица Кэли: