Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
§2. Алгебраические операции.
Основные типы алгебраических структур
1°. Алгебраические операции.
Алгебра − наука об алгебраических операциях.
Пусть X − произвольное множество.
Определение 1. n-арной алгебраической операцией на X называется отображение . Т.е. n-компонентному элементу однозначно ставится в соответствие элемент .
Задача. Пусть . Сколько n-арных алгебраических операций на ? Ответ. Таких операций
Алгебраические операции при n=1 называются унарными, при n=2 – бинарными, n=3 – тернарными. Далее, как правило, будут рассматриваться бинарные операции.
Если , то пишут или . Операции на X обозначают символами . Последний символ используется для операции сложения, остальные − для операции умножения.
Определение 2. Множество X с конкретной алгебраической операцией называется алгебраической структурой.
На одном и том же множестве X могут быть заданы различные алгебраические структуры.
Примеры (алгебраических операций и алгебраических структур).
1. так, что имеем
2. 3.
4. Деление не является алгебраической операцией на R, так как не определено деление на нуль. Однако оно является алгебраической операцией на .
5-8. То же самое для С.
9.
10. Скалярное произведение не является алгебраической операцией на множестве векторов, т.к. .
11. - множество всех отображений относительно операции композиции является алгебраической структурой.
12. Как правило, алгебраическая операция на конечном множестве может быть задана с помощью таблицы Кэли, которая описывает результат операции на любой паре элементов множества. Рассмотрим множество, состоящее из 3-х элементов: {Доска, Окно, Тряпка} (кратко {Д, О, Т}). Введем следующую операцию, обозначаемую (символ операции). Соответствующую таблицу Кэли можно выбрать в виде
|
2 1 |
Д |
О |
Т |
|
Д |
Д |
О |
Д |
|
О |
О |
Д |
Т |
|
Т |
Т |
Т |
Д |
13. Примерами тернарных операций на являются:
Обычно полезно изучать операции со специальными свойствами.
Определение 3. Бинарная операция на X называется коммутативной, если ; ассоциативной, если выполняется .
Задача. Пусть . Сколько коммутативных бинарных операций на X? Ответ. Таких операций .
Примеры.
Теорема 1 (обобщённая ассоциативность). Если операция ассоциативна, то в выражении скобки можно расставлять в любых местах.
Доказательство. Проводится методом математической индукции. Для утверждение повторяет определение ассоциативности. Пусть . Рассмотрим выражения
и .
Пусть − обычная ассоциативность. ■
Определение 4. Элемент называется нейтральным относительно алгебраической операции , если
|
. |
(1) |
Теорема 2. Нейтральный элемент единственен.
Доказательство. (от противного). Пусть и − два нейтральных элемента
(по условию нейтральности ) и
(по условию нейтральности )
.■
Определение 5. Множество с заданной на нем бинарной ассоциативной операцией называется полугруппой. Полугруппа с нейтральным элементом называется моноидом или полугруппой с единицей.
Определение 6. Элемент моноида называется симметричным к элементу , если
|
(2) |
Теорема 3. Если в моноиде для есть симметричный элемент, то такой элемент единственен.
Доказательство. Пусть для данного два симметричных элемента и Тогда в силу (1) и (2) имеем:
.■
Обычно умножение называют мультипликативной операцией, сложение – аддитивной. В случае мультипликативной операции результат операции называют произведением, нейтральный элемент – единицей (обозначают 1), симметричный элемент к – обратным (пишут ). В случае аддитивной операции результат операции называют суммой (x+y), нейтральный – нулём (обозначают 0), симметричный – противоположным (обозначают ).
Теорема 4. Если в моноиде для элементов и есть симметричные элементы и соответственно, то для элемента также существует симметричный элемент, равный
Доказательство. Для доказательства теоремы необходимо проверить условия (2): Проверим первое из этих равенств. Имеем:
Аналогично проверяется второе условие из (2).■
2°.Группа, свойства группы.
Определение 7. Непустое множество G с заданной алгебраической операцией называется группой, если
1) – ассоциативная операция.
2) В G нейтральный элемент .
3) симметричный элемент из
Если – коммутативная операция, то группа называется коммутативной или абелевой.
Операция, относительно которой G − группа, называется групповой операцией. Если групповая операция − умножение, то группа называется мультипликативной, если – сложение, то G – аддитивная группа.
Примеры.
Свойства группы.
1°. В группе G нейтральный элемент и симметричный элемент.
Доказательство следует из теорем 1 и 2.
2°. Для уравнения имеют единственное решение:
, .
Доказательство. Покажем, что – решение уравнения . Имеем: , т.е. − решение.
Если z – другое решение, то после умножения слева на x – единственное решение. Аналогично для другого уравнения.
3°. Закон сокращения в группе. Если .
Доказательство следует из свойства 2°.
Важный пример (группа перестановок степени ).
Пусть − произвольное множество из элементов; например,
Определение 8. Перестановкой степени называется взаимнооднозначное отображение множества в .
Множество всех перестановок степени обозначается . Каждую перестановку будем в дальнейшем обозначать строчной буквой греческого алфавита: Перестановка изображается двурядным символом:
.
Такой символ обозначает отображение
Лемма 1. Число различных перестановок степени равно
Доказательство. В качестве первого элемента можно выбрать любой из элементов, в качестве второго − любой из оставшихся элементов, и т.д. Всего различных возможностей выбора Таким образом, ■
На множестве перестановок вводится операция умножения по формуле
Например, если
то
Лемма 2. Множество образует группу, не являющуюся коммутативной.
Доказательство. Вначале проверим ассоциативность умножения. Пусть и Тогда по определению легко проверить выполнение равенства Тождественная перестановка является нейтральным элементом в рассматриваемом множестве, симметричный элемент получается перестановкой строк. Некоммутативность легко проверяется на предыдущем примере.■
Замечание. Если и − коммутативная операция, то таблица Кэли симметрична относительно диагонали.
3°.Кольцо, свойства кольца.
В алгебре изучаются множества и с несколькими, например, с двумя, алгебраическими операциями.
Определение 9. Непустое множество называется кольцом и обозначается , если выполняются условия:
1) (K;+) – абелева группа.
2) умножение ассоциативно, т.е.
3) умножение дистрибутивно относительно сложения, т.е.
, .
Кольцо называется коммутативным (понятия абелева кольца нет!!!), если умножение коммутативно. Если относительно умножения существует нейтральный элемент, то кольцо называется кольцом с единицей.
Примеры колец.
, ,
образует коммутативное кольцо с единицей.
|
0 |
1 |
|
|
0 |
0 |
0 |
|
1 |
0 |
1 |
|
0 |
1 |
|
|
0 |
0 |
1 |
|
1 |
1 |
0 |
Например, (1010) (0110)=(1100); (1010) (0110)=(0010).
Операции и − алгебраические, нейтральный элемент – нулевая битовая строка (0…0). Для каждой битовой строки противоположным элементом является эта же битовая строка. Доказательство коммутативности, ассоциативности операций и и дистрибутивность логического умножения относительно операции сводятся к доказательству этих свойств для битовых строк длиной 1, которое проводится прямыми вычислениями. Т.о., пространство битовых строк с операциями , является кольцом, которое обозначается . Это кольцо является ассоциативным кольцом с единицей.
Так как (;+) абелева группа, то противоположный элемент . Поэтому в К можно ввести операцию вычитания: .В силу свойства группы единственное решение уравнения .
Свойства кольца.
1) Умножение дистрибутивно относительно вычитания, т.е.
.
Доказательство.
.
2) .
Доказательство. Т.к. . Аналогично доказывается, что .
Утверждение, обратное свойству 2), неверно. А именно, существуют кольца, в которых произведение двух ненулевых элементов равно нулю, т.е но . Такие кольца называются кольцами с делителями нуля. Например, множество непрерывных функций – кольцо с делителями нуля. Действительно, если ,
Аналогично, − множество матриц размера − кольцо с делителями нуля.
3) Если − отличный от нуля элемент из , не являющийся делителем нуля, и
(закон сокращения в кольце). Аналогично,
Доказательство.
4)
Доказательство.
4°.Поле, свойства поля.
Пусть P – множество, содержащие не менее двух элементов.
Определение 10. Множество с заданными на нём алгебраическими операциями сложения + и умножения называется полем и обозначается (), если:
1) (P;+) – абелева группа.
2) (P\{0};) – абелева группа.
3) Умножение дистрибутивно относительно сложения, т.е.
Т.о., поле – это коммутативное и ассоциативное кольцо с единицей, в котором все ненулевые элементы составляют мультипликативную группу.
Примеры полей.
Свойства поля.
1) В поле Р нет делителей нуля.
Доказательство. Пусть Умножим на : . С другой стороны,
2) Свойство сокращения на ненулевой элемент: из
3) , уравнение в поле P имеет единственное решение .
Доказательство. При доказываемое свойство – это свойство группы, при − свойство кольца.
Решение уравнения обозначается и называется частным от деления на . Т.о., в поле определено деление на ненулевой элемент.
Вывод. В произвольном поле можно проводить все операции, как в обычной арифметике: сложение, вычитание, умножение, деление на ненулевой элемент, раскрытие скобок, приведение подобных, … .
Итак, алгебраические структуры – это множества с алгебраическими операциями. Дальнейшее обобщение – алгебраические системы, являющиеся совокупностью множества, алгебраических операций и отношений. Это стык алгебры и математической логики.
5°.Подполугруппа, подгруппа.
Пусть − бинарная алгебраическая операция на .
Определение 11. Подмножество называется замкнутым относительно , если выполняется
Если подмножество множества замкнуто относительно , то на определена операция: каждой паре ставится в соответствие
Определение 12. Такая операция на называется операцией, индуцированной операцией .
Лемма 3. Пусть − полугруппа и замкнуто относительно Тогда является полугруппой относительно индуцированной операции.
Доказательство. Для доказательства леммы достаточно показать, что операция ассоциативна на множестве Это очевидно, так как все элементы являются элементами , а на введенная операция ассоциативна.■
Определение 13. Пусть − полугруппа. Подмножество , замкнутое относительно , называется подполугруппой.
Пример. − полугруппа (и даже группа), а − подполугруппа (но не группа).
Определение 14. Пусть пара () – группа. называется подгруппой, если X замкнуто относительно и X − группа относительно индуцированной операции.
Определение 15. Пусть тройка (P,+,) − кольцо (поле). Подмножество называется подкольцом (подполем), если Y замкнуто относительно и и Y является кольцом (полем).
Пример. − подполе в поле
Теорема 5. Пусть () – группа. является подгруппой в
1) X замкнуто относительно ; 2) , где − нейтральный элемент в ;
3) существует .
Доказательство. Достаточность − очевидна.
Необходимость. Пусть − подгруппа в . Тогда условие 1) выполнено по определению подгруппы.
Проверим условие 2). Так как − подгруппа, то − нейтральный элемент в . Докажем, что , т.е. совпадает с нейтральным элементом в . Действительно, умножим равенство на (симметричный элемент к в смысле , т.е. ). С одной стороны имеем: , с другой − . Отсюда следует, что .
Осталось проверить 3). Пусть . Тогда , являющийся симметричным в , т.е. . Это и означает выполнение условия 3).■
Аналогичные теоремы доказываются для подколец и подполей.
Теорема 6. Если в группе взяты две подгруппы и , то их пересечение , т.е. совокупность элементов, лежащих одновременно в обоих множествах, также будет подгруппой группы .
Доказательство. Действительно, если в пересечении содержатся элементы и , то они лежат в подгруппе , а потому в лежат и произведение , и симметричный элемент . По тем же соображениям элементы и принадлежат подгруппе , а потому они входят и в .■
Интересный пример подгруппы − циклические подгруппы. Вначале введем некоторые понятия. Если − элемент группы , то n-ой степенью элемента называется произведение n элементов, равных . Отрицательные степени элемента вводятся как произведения сомножителей, равных . Легко видеть, что . Для доказательства достаточно взять произведение сомножителей, из которых первые равны , а остальные − , и произвести все сокращения. Под нулевой степенью элемента будем понимать нейтральный элемент. В силу обобщенной ассоциативности легко показать, что имеют место равенства:
|
(3) |
Обозначим подмножество группы , состоящее из всех степеней элемента .
Лемма 4. Множество является подгруппой группы .
Доказательство очевидно.
Определение 16. Подгруппа называется циклической подгруппой группы .
Легко видеть, что циклическая подгруппа всегда коммутативна, даже если сама группа некоммутативна. Если все степени элемента являются различными элементами, то называется элементом бесконечного порядка . Если существуют и из , такие, что , то называется элементом конечного порядка. Легко видеть, что в этом случае . Наименьшее такое, что называется порядком элемента .
Определение 17. Группа называется циклической группой, если она состоит из степеней одного из своих элементов , т.е. совпадает с одной из своих циклических подгрупп . Элемент в этом случае называется образующим элементом группы .
Примеры.
1) − циклическая группа с образующим элементом 1.
2) Группа корней n-ой степени из 1 − циклическая мультипликативная группа с образующим элементом, получаемом при .
6°.Гомоморфизм и изоморфизм групп
Определение 18. Пусть и − множества, и − бинарные операции (на и соответственно). Гомоморфизмом из в называется отображение такое, что
Пример. Отображение является гомоморфизмом из в Это следует из справедливости равенства
Замечания.
1. Аналогично определяется понятие гомоморфизма, если на множествах и определены несколько операций.
2. Так как полугруппа, группа, кольцо и т.д. множества с операциями, то ясно, что такое гомоморфизм полугрупп, групп и т.д.
Определение 19. Изоморфизм − это биективный гомоморфизм.
Определение 20. Пара изоморфна паре , если изоморфизм из в .
Обозначение. означает, что изоморфно . Иногда пишут .
Примеры.
Теорема 7. Пусть − изоморфизм. Тогда
Доказательство.
Следствие. Из доказанной теоремы следует, что если и − группа, то − также группа. Аналогично для колец и полей.
Теорема 8. Все бесконечные циклические группы изоморфны между собой. Изоморфны между собой также и все конечные циклические группы данного порядка .
Доказательство. Действительно, любая бесконечная циклическая группа с образующим элементом отображается взаимно однозначно на аддитивную группу , если каждому элементу этой группы ставится в соответствие число . Это отображение является изоморфизмом, так как согласно (3) при перемножении степеней элемента показатели складываются. Если рассматривается конечная циклическая группа порядка с образующим элементом , то, рассматривая мультипликативную группу корней −ой степени из единицы и обозначая , изоморфизм строится сопоставлением элементу группы числа . Изоморфность такого отображения следует из следствия к теореме из § 1.■
17