Алгебраические структуры
 Скачать 158.6 Kb.
|
|
Алгебраические структуры Под алгебраической структурой понимается множество объектов любой природы, в котором определены некоторые операции. Чаще всего это бинарные операции, то есть сопоставление любым двум элементам из множества некоторого другого элемента из этого же множества по некоторому правилу. Тот факт, что обязательно принадлежит множеству , называется Замкнутостью структуры по отношению к этой операции. Далее, если не оговорено противное, мы будем считать все рассматриваемые ниже бинарные операции замкнутыми. В алгебраической структуре может быть введены одна или несколько операций. Мы рассмотрим 6 следующих структур: три с одной бинарной операцией – полугруппы, моноиды и группы; и три с двумя бинарными операциями – кольца, области целостности и поля. Полугруппы Определение. Полугруппой называется множество с введённой в нем бинарной операцией, обладающей свойством ассоциативности (или, что тоже самое, сочетательности). То есть в полугруппе для любых трех элементов должно выполняться равенство: Здесь « ◦ » - символ бинарной операции. Примеры. 1) Множество c введенной в нем операцией сложения – полугруппа, т.к.
2) Множество с введенной в нем операцией умножения – полугруппа, т.к. 1) (замкнутость) 2) (ассоциативность) 3) Множество рациональных чисел ( – где целые числа) с операцией сложения – полугруппа. 4) Множество без нулевого элемента с операцией умножения – полугруппа. 5) Множество без нулевого элемента с операцией деления – не полугруппа, т.к. нет ассоциативности 6) Множество матриц одного размера с операцией сложения – полугруппа. 7) Множество квадратных матриц одного порядка с операцией умножения – полугруппа. Моноиды Определение. Если в множестве M введена некоторая операция « ◦ », то единичным элементом или единицей по отношению к этой операции называется такой элемент , что для любого элемента выполняется равенство: . Такого элемента может и не быть. Определение. Моноидом называется полугруппа с единицей, т.е. полугруппа, в которой существует единичный элемент. Примеры
Тоже верно относительно полугруппы – множество рациональных чисел, полугруппы – множество вещественных чисел, полугруппы – множество комплексных чисел.
Определение. Элемент a моноида называется обратимым, если для него найдётся такой элемент из этого моноида, что , где e- единичный элемент по отношению к операции « ◦ ». Этот элемент b называется обратным по отношению к и обозначается , так что. Если выполняется только первое равенство, то b называется левым обратным элементом (), а если только второе (), то правым. При этом называется соответственно обратимым слева или справа. Не все элементы моноидов имеют обратные элементы. Например, в только 1 и -1 обратимы (т.к. остальные элементы имеют обратные, не принадлежащие ). Теорема. Если и обратимы, то тоже обратим, при этом . Доказательство Действительно, в силу ассоциативности операции « ◦ » выполняются равенства: ч.т.д. Следствие. Элемент также обратим, при этом ( =. Определение. Группой называется моноид, все элементы которого обратимы. То есть группа – это множество G, в котором введена бинарная операция « ◦ » (напомним, обязательно замкнутая), удовлетворяющая условиям:
Определение. Подструктурой данной алгебраической структуры называется подмножество, само являющееся структурой с теми же структурными операциями. Например, подполугруппа – подмножество полугруппы, само являющееся полугруппой; подмоноид – подмножество моноида, являющееся моноидом; подгруппа – подмножество группы, являющееся группой. Очевидно, что сама структура есть своя подструктура; единичный элемент, если он существует, тоже подструктура (состоящая из одного элемента). Эти подструктуры называются несобственными, остальные – собственные. В дальнейшем, если не оговорено противное, под подструктурой будем понимать только собственные подструктуры. Следствие. Множество обратимых элементов моноида само является моноидом, т.е. подмоноидом, а, следовательно, множество всех обратимых элементов подгруппы есть группа. Коммутативные группы (т.е. группы, в которых операция « ◦ » коммутативна, т.е. ) обычно называют абелевыми. В них групповую операцию обычно называют сложением и обозначают « + », а единичный элемент обозначают символом 0; обратный к называют противоположным элементом и обозначают символом «-». В некоммутативных группах групповую операцию обычно называют умножением « · » или никак не обозначают; единичный элемент обозначают символом 1. Если групповая операция сложение, то группу называют аддитивной, а если умножение – мультипликативной. Примеры. 1) Аддитивными группами являются множества . 2) Мультипликативными – множества ; множество мультипликативной группой не является, т.к. в нем всего лишь 2 элемента 1 и -1, обратимы. 3) Группа (рациональных чисел) – подгруппа (вещественных чисел), а множество - всех положительных чисел – подгруппа мультипликативной группы . 4) Множество – (целых чисел, кратных , в частности – четных чисел) – подгруппа аддитивной группы . 5) Множество нечетных чисел – не есть подгруппа , так как неч+чет=чет не этому множеству. 6) Матрицы одинакового размера образуют абелеву аддитивную группу. 7) Множество квадратных невырожденных () матриц n порядка образуют (некоммутативную) мультипликативную группу (т.е. по умножению). Если в группе конечное число элементов, то группа называется конечной, а число элементов в ней – порядком группы. Конечные группы порядка можно задавать так называемой таблицей умножения (сложения) размером . Такую таблицу называют таблицей Кэли группы. Пример конечной группы – множество всех корней -ой степени из 1 в множестве комплексных чисел с обычной операцией умножения, т.е. множество чисел вида , . Порядок группы . Составим, например, таблицу Кэли для .
Определение. Прямым (декартовым) произведением групп называется новая группа, обозначаемая , элементами которой служат наборы (или, что то же самое, кортежи) элементов из данных групп. означает, что ={}, причем , , а групповая операция « ◦ » состоит в том, что, если , то ◦ . Это, действительно, группа, т.к. роль единичного элемента играет кортеж , где – единичный элемент -ой группы, а обратные элементы задаются формулой (то, что ◦ = ◦ = – очевидно). – -ая степень группы означает -кратное умножение ее самой на себя. . – группа, состоящая из двух элементов с групповой операцией сложение по модулю 2. Поэтому состоит из последовательной длины n символов 0 или 1 с поэлементным сложением по модулю 2. Например, в : 011001+110101=101100. Заметим еще, что в для любого элемента x справедливо равенство , так что противоположный (обратный) элемент для любого элемента равен самому этому элементу: -. Циклические группы Очевидно следующее утверждение: пересечение любого множества подгрупп данной группы само является подгруппой этой группы. Пусть задан некоторый непустой набор элементов группы (конечный или бесконечный). Обозначим через () пересечение всех подгрупп, содержащих как подмножество. Тогда () – подгруппа исходной группы. Она называется подгруппой, порожденной . В частности, если состоит из одного элемента , то () называется циклической подгруппой, порожденной элементом . Очевидно, что эта подгруппа состоит из всевозможных степеней , поэтому она обязательно абелева, т.е. коммутативная. Если группа совпадает с циклической подгруппой, порожденной каким-то ее элементом, то сама эта группа называется циклической. Таким образом, циклическая группа всегда абелева. Нетрудно доказать, что всякая подгруппа циклической группы сама является циклической. Пример. Группа, элементами которой являются корни -ой степени из 1 в множестве комплексных чисел с групповой операцией умножение, является циклической. Действительно, это конечная группа n-ого порядка. Ее элементы , . Группа подстановок Определение. Пусть одно конечное множество из элементов . Подстановкой -ого порядка (или степени ) называется взаимно-однозначное отображение (или, что то же самое, биекция) этого множества самого на себя:. Замечание. Так как природа элементов множества нас не интересует, то можем считать, что элементами являются числа (номера) . Поэтому подстановку можно записать символом: Во второй строке записаны номера тех элементов, которым сопоставляются элементы из I строки: . Поэтому в написанной матрице столбцы можно как угодно переставлять, подстановка останется той же. В множестве подстановок вводится операция умножение. Определение. Произведением двух подстановок и называется результат проведения сначала первой из них, а затем второй:). Для этого представляют столбцы так, чтобы ее первая строка совпадала со второй строкой ; тогда I строка есть первая строка , а вторая строка – есть вторая строка . Пример. В результате множество перестановок становится группой. Единичный элемент – это тождественная подстановка . Обратный к это , так как . Эта группа называется симметрической группой степени n и обозначается . Очевидно, что порядок этой группы (т.е. число ее элементов) равен (число перестановок из). Примеры. 1) Запишем все 6=3! Элементов симметрической группы : ; ; ; ; ; 2) Найти Как видим , т.е. умножение подстановок некоммутативно. 3) Найти обратную подстановку к и проверить. Циклы Определение. Пусть некоторая подстановка такова, что ; … ; (все числа – разные) или, что тоже самое, ; … . Тогда набор элементов называется орбитой любого из чисел , а сама подстановка называется циклом длины и записывается так: (). Циклы называются независимыми, если у них нет общих чисел. Циклы длины 1 – это, очевидно, тождественная подстановка ; в произведениях подстановок их можно не записывать. Теорема. Любую подстановку можно записать в виде произведения независимых циклов, и эти циклы определяются однозначно. Доказательство Очевидно, что отношение между числами «принадлежность одной -орбите» есть отношение эквивалентности (действительно, это отношение )
Пример. Определение. Подстановка вида (), где , сводящаяся к перестановке двух чисел между собой, или, что тоже самое, цикл длины 2, называется транспозицией. Нетрудно показать, что любую подстановку можно представить в виде произведения транспозиций. Такое представление не единственно. Все подстановки подразделяются на 2 класса: четные и нечетные. Если в матрице подстановки есть 2 столбца , для которых , а или , а , то такая пара столбцов называется инверсией подстановки. Подстановка называется четной или нечетной в зависимости от того, четно или нечетно число ее инверсий. Если подстановка четная, то при любом способе разложения ее в произведение транспозиций число множителей (т.е. транспозиций) четно, а если нечетная – то число этих транспозиций нечетно. Следствие. Так как при перемножении четных подстановок, очевидно, снова получается четная подстановка, то множество всех четных подстановок является подгруппой симметрической группы . Эта подгруппа называется знакопеременной группой и обозначается . Произведение нечетных подстановок, очевидно, тоже есть четная подстановка (число транспозиций неч+неч=четно), поэтому нечетные подстановки не образуют подгруппу. Примеры.
Сосчитаем число инверсий . Инверсии – это пары столбцов 1-3, 1-4, 2-3, 2-4, 3-4, 6-8, 7-8. Поэтому , т.е. подстановка нечетная. Разложим сначала ее на циклы: . Как видим, число транспозиций в произведении равно 5, т.е. нечетно. Обратная операция: Изоморфизм: Теорема Кэли Определение. Пусть задано отображение группы в группу . Оно называется гомоморфизмом (или просто морфизмом), если оно произведению любых прообразов сопоставляет произведение их образов, то есть если , , а ; , то . Если гомоморфирзм есть одновременно биекция, т.е. взаимно-однозначное соответствие, то он называется изоморфизмом. Запись изоморфизма . Примеры. 1. Группы и по сложению изоморфны группам положительных чисел и по умножению (изоморфизм называется логорифмированием).
Теорема Кэли: любая конечная группа изоморфна некоторой подгруппе симметрической группы, то есть группе подстановок. Кольца Определение. Непустое множество называется кольцом, если в нем определены 2 операции: сложение и умножение, обладающие следующими свойствами:
Очевидно, что любое кольцо есть полугруппа. Определение. Если в кольце умножение коммутативно, т.е. , то кольцо называется коммутативным (т.е. добавили еще одну аксиому). Примеры. 1) Множества , Q (рациональные числа ), (вещественные числа), (комплексные числа - кольца); 2) множество четных чисел () – кольцо; 3) множество чисел, кратных – кольцо; 4) множество нечетных чисел – не кольцо, т.е. нет замкнутости и нет 0; 5) множество матриц с элементами из кольца – некоммутативное кольцо; 6) множество вещественных функций; 7) множество многочленов с коэффициентами из коммутативного кольца ; 8) пары () целых чисел, если определено сложение: , умножение: . Определение. Обратная операция для сложения называется вычитанием, а ее результат называется разностью Замечание. Если один из сомножителей равен 0, то произведение равно 0. Действительно, . Обратное утверждение (справедливое для чисел) неверно, то есть из того, что произведение равно 0 не следует, что один из сомножителей равен 0. Определение. Элементы , принадлежащие кольцу , для которых , называются делителями нуля. Определение. Коммутативное кольцо без делителей 0 называется областью целостности. Определение. Подмножество кольца называется подкольцом , если оно само есть кольцо. Теорема. Для того, чтобы непустое множество кольца было подкольцом необходимо и достаточно, чтобы разность и произведение любых двух элементов снова принадлежали . Действительно, легко проверить, что в этом случае все аксиомы кольца выполняются. Примеры. 1. – подкольцо , – подкольцо , – подкольцо . 2. – подкольцо кольца . 3. – область целостности, так как они коммутативны и не имеют делителей 0. 4. Пары () целых чисел с введенными сложением и умножением имеют делители 0. Действительно: для , т.е. делители 0. Т.е. это кольцо коммутативное, но не есть область целостности. 5. Кольцо матриц размера () – некоммутативное и имеет делители 0. Действительно, , то есть и – делители нуля. Поля Определение. Единицей кольца называется элемент, удовлетворяющий условиям для любого . Если кольцо содержит 1, то оно единственно, и кольцо называется кольцом с 1 (это моноид). Замечание. Однако бывают кольца без 1 (например, кольцо, в частности – кольцо четных чисел). Определение. Полем называется коммутативное кольцо с 1, содержащее не менее 2х элементов, которые для каждого имеют единственный обратный элемент , т.е. . Замечание 1. Поле – это группа, так как оно удовлетворяет всем аксиомам группы. Замечание 2. Очевидно, что для полю уравнения и имеют единственное решение в этом поле. Действительно, существует обратный к элемент , т.е. . Тогда (поле коммутативно). Замечание 3. В поле нет делителей 0. Действительно, пусть . В поле существует , тогда , т.е. – не делители 0. Определение. Обратная операция для умножения называется делением, а ее результат называется частным. Обозначается: . В любом поле: Можно также положить и , т.е. определить степени для любого в поле. Примеры. 1) Множество – не поле, т.к. нет обратных элементов (кроме ±1). 2) – пол, для . 3) – не поле (нет обратных элементов). 4) Множество матриц – не поле, во-первых, некоммутативно, во-вторых, не для всех элементов есть обратные (обратная матрица, как мы знаем, есть только для неособых () матриц). 5) Множество вещественных функций – не поле (не для всех функций есть обратные). 6) Пары () целых чисел – не поле (существуют делители 0). 7) Множество чисел с рациональным – поле ( или – целые – не поле). 8) Множество вещественных чисел вида , где – рациональные числа – поле (надо доказать, что результаты умножения и деления принадлежат этому полю). 9) Множество из двух элементов 0 и 1, если ввести операции сложения 0+0=1+1=0; 0+1=1+0=1 и умножения 0·0=0·1=1·0=0; 1·1=1 – есть поле. Идеалы Определение. Подкольцо кольцаназывается идеалом, если при и . Примеры. 1. Множество четных чисел является идеалом в кольце целых чисел. Действительно, произведение любого четного числа и любого целого числа есть четное число, т.е. принадлежит этому идеалу. 2. Множество вещественных функций таких, что – идеал в кольце вещественных чисел. Действительно, этому идеалу, т.к. . 3. В любом кольце всё кольцо и подмножество {0} – есть иделы кольца (это очевидно). 4. В кольце множество всех кратных чисел – идеал в , т.к. n для любого принадлежит идеалу. Например, – идеал в кольце. Определение. Идеал кольца , состоящий из кратных элемента называется главным идеалом, порожденным элементом и обозначается (). Так в Z: (2) : {2, 4, 6, ….} (3) : {3, 6, 9, ….} Нулевой идеал {0}=(0) является всегда главным. Если кольцо имеет 1, то единичный идеал (1) является как легко видеть, всем кольцом . Теорема. Любое поле не содержит идеалов, кроме (1) и (0). Доказательство: Пусть – ненулевой идеал поля К. Возьмем . K – поле, поэтому существует , тогда , следовательно , где – любой элемент из , следовательно , т.е. – единичный идеал. Ч.т.д. Замечание 1. Ясно, что в любом кольце, отличном от поля, любой необратимый элемент порождает идеал (), отличный от (0) и (1). Например, в Замечание 2. Все идеалы в кольце – главные, т.о. подкольца исчерпывают все идеалы кольца . Сравнения Пусть – главный идеал кольца . Определение. Два элемента называются сравнениями по модулю (или по идеалу ), если их разность . Запись: . Пусть – кольцо (целые числа). Тогда , если при делении не получаются одинаковые остатки. Действительно, . Примеры: (т.к. ) (т.к. ) Определение. Множество элементов кольца, сравнимых с по модулю , называется классом вычетов по модулю (по идеалу ). Элемент называется представителем класса вычетов . Пример в , т.е. идеал (3); Лемма 1. Два класса вычетов и или не пересекаются или совпадают. Иначе говоря, классы вычетов по модулю образуют разбиение кольца . Пример в по (3): , , , имеется лишь три класса вычетов , причем любой элемент из принадлежит лишь одному из этих классов. Лемма 2. (Свойства сравнений) ; , т.е. ; . Тогда: 1) . (Сравнение можно складывать или вычитать). Действительно: пусть ; ; ; . Тогда т.е.. 2) (Сравнения можно перемножать). , так как ; . 3) (следствие 2). 4) Действительно, , поэтому и из 3) : . 5) Если ; , то , где . Действительно, , следовательно , где , т.е. , т.е. . Замечание. Из не следует, что , то есть сравнения нельзя умножать на любое число.
Например в , по . Примеры: 1) 2) Найти остаток при делении ? , т.е. остаток равен 0. 3) Найти 2 последние цифры числа 2341. Для этого достаточно найти остаток при делении на 100; для этого выясним остаток при делении на 25 и на 4: , т.е. последние 2 цифры могут быть 02; 27; 52; 77. , значит последние цифры могут быть только 52. 4) Доказать, что (2630-1)(5·7·11·31). Надо дать 4 сравнения 2630 по модулю 5, 7, 11, 31. Итак , а тогда по 5 свойству , где , то есть . Замечание 1. Приведем без доказательства еще два полезных свойства сравнений, которые выражены следующей теоремой: Теорема Ферма
Примеры. 1) 2) Замечание 2. При решении задач на сравнение также удобно пользоваться функцией Эйлера. Определение. Функцией Эйлера называется число классов вычетов по модулю , взаимно простых с модулем . Теорема. Если натуральное число имеет каноническое разложение на простые множители , то функция Эйлера равна: . Примем эту теорему без доказательства, доверяя Эйлеру. Пример. Вычислим функцию Эйлера . , т.е. =. Определение. мультипликативная функция, если для любых взаимно-простых справедливо: . Очевидно, что функция Эйлера – мультипликативная! Теорема Эйлера. Для любого модуля и любого натурального числа , взаимнопростого с числом , имеет место формула Эйлера: . Пример. Найти остаток от деления числа 174249 на 13. Заметим, что числа 174 и 13 взаимно просты. Сначала вычислим значение функции Эйлера от делителя: . Затем разделим показатель степени 249 на с остатком: . Тогда . По теореме Эйлера , тогда, откуда , и т.о. , получаем и т.к. , то с учетом , получим . , т.е. . Окончательно получаем: , т.е. остаток от деления 174249 на 13 равен 5. Кольца классов вычетов Теорема. Пусть – главный идеал кольца . Тогда множество классов вычетов по модулю образуют кольцо c операциями: Действительно, все аксиомы кольца очевидны при таких введенных операциях сложения и умножения. 0 элемент – это , для любого класса вычетов можно образовать противоположный элемент такой, что . Примеры. Z/(3): . ; . Противоположный это . Действительно, . Определение. Кольцо называется кольцом классов вычетов по модулю (или по идеалу ). Кольца классов вычетов кольца целых чисел обозначаются Например, кольцо : Характеристика кольца Определение. Пусть – кольцо с 1. Целое положительное число m называется характеристикой кольца , если и никакое другое положительное число, меньше , этим свойством не обладает. Если такого m нет, то говорят, что кольцо имеет характеристику 0. Так кольцо имеет характеристику 0, т.к. ; поле также имеет характеристику 0. Кольцо , т.е. множество классов вычетов по , имеет характеристику . Действительно . Кольцо , т.е. множество классов вычетов по модулю 3: . , т.е. характеристика равна 3. Лемма. Если характеристика кольца равна , то для любого . Теорема. Характеристика любого кольца без делителей 0 (в частности, поля) либо 0, либо простое число. Действительно, если нет делителей 0, т.е. нет таких чисел , что , то из определения характеристики следует, что либо , либо – простое, так как в противном случае и, следовательно, , т.е. есть делители 0. Ч.т.д. Следствие. – множество классов вычетов по , где – не простое, имеет делители 0. Например, имеет делители 0: . Простые идеалы Определение. Идеал в кольце называется простым, если из следует, что либо , либо . Единичный идеал (1) – всегда простой, т.к. это само кольцо . В кольце целых чисел идеал простой при простом. Так, например, – прост, так как (3) содержит числа кратные 3, – простое. Если число кратно 3, то хотя бы один множитель кратен 3. Идеал (6) – не прост, так как 6=2·3 – не простое. Например, 30 (6), 30=3·10, 3 (6), 10 (6). Теорема. Идеал кольца является простым тогда и только тогда, когда кольцо классов вычетов не содержит делителей 0. Доказательство Кольцо классов вычетов не имеет делителей 0 в том и только в том случае, если из , где следует, что либо , либо , но тогда: либо либо , что равносильно по определению тому, что идеал – простой. Ч.т.д. Поля классов вычетов. Минимальные поля Теорема. (Следствие из предыдущей) Кольцо классов вычетов кольца целых чисел по модулю является полем тогда и только тогда, когда – простое число. Действительно, всякое конечное кольцо без делителей 0 есть поле. Например, . Если , то . Если , то , т.к. . Делителей нуля нет, т.е. – поле. : – есть делители 0, так как 4 – не простое. , т.е. – не поле. Определение. Множество L поля называется подполем , если оно само является полем при тех же операциях сложения и умножения, которые введены в поле . Так, например, поле рациональных чисел есть подполеполя вещественнных чисел , а – подполе поля комплексных чисел . Определение. Поле, неимеющее подполей, отличных от него самого, называется минимальным. Примеры. 1) Поле рациональных чисел – минимально. 2) Поля вычетов кольца целых чисел по простым модулям: - минимальны. Евклидовы кольца Определение. Евклидовым кольцом называется кольцо без делителей 0, в котором каждому ненулевому элементу сопоставляется целое неотрицательное число , называющееся нормой , со следующими свойствами:
Примеры. 1. Кольцо – евклидово кольцо с нормой . Действительно 1), если – целое; 2) деление с остатком введено. 2. Кольцо целых гауссовских чисел – евклидово кольцо с нормой . Действительно: 1), т.к. . 2) можно ввести деление с остатком, например: Т.е. 3. Кольцо многочленов от одной переменной с коэффициентами в поле – евклидово кольцо с нормой степень многочлена . Действительно: 1) Пусть тогда 2) алгоритм деления многочлен на многочлен известен. Свойства евклидовых колец
Определение. Пусть – любое кольцо без делителей 0. Говорят, что делит (то есть делится на без остатка), если такой, что . Запись: . Ясно, что из |