XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 21
Текст из файла (страница 21)
Аналогично доказывается и правый закон. ~ 1ЗО 2. АЛГЕБРЫ: ГРУППЫ Н КОЛЬЦА Пусть и = (С,, 1) — группа, а, Ь вЂ” фиксированные элементы С. Рассмотрим задачу решения уравнений (2.1) а х=Ь, (2.2) х а = Ь в группе Д, т.е. поиска всех таких элементов х Е С, для которых уравнение (2.1) (или (2.2)) превращаетсл в тождество. Теорема 2.4.
В любой группе Д уравнения вида (2.1) и (2.2) имеют решения, и притом единственные. < Покажем, что х = а 1 6 есть решение (2.1). Действительно, а (а 1 Ь) =(а а 1 Ь) =Ь. Докажем единственность решения. Пусть для фиксированных а и Ь и некоторого х выполнено равенство а х = Ь. В группе для любого а существует и однозначно определен элемент а 1, обратный к а.
Умножив на него обе части равенства, получим а 1 (а х) = а ~ 6. В силу ассоциативности преобразуем последнее равенство к виду (а 1.а) х =а 1 Ь. Поскольку а ~ а=1, то 1 х=а 1 Ь, откудах=а ~ 6. Это решение единственное в силу единственности обратного элемента.
Аналогично из х а = Ь получаем х = 6. а 1, и это решение также единственное. ~ Замечание. При использовании аддитивной записи операции для коммутативной группы м = (С, +, 0) оба написанных вьппе уравнения сводятся к одному: а+х=Ь, а его решение есть х = 6+ (-а). Правую часть этого равенства в коммутативной группе называют разностью элементов 6 и а и обзначают Ь вЂ” а. Саму же операцию, сопоставляюшую упорядоченной паре (а,Ь) разность Ь вЂ” а,называют операцией вы иипаки,в. С учетом введенных обозначений решение уравнения в коммутативной группе можно записать так: х = Ь вЂ” а.
131 2.2. Груопоидм, лолугруппы, группы В случае коммутативной группы при употреблении для бинарной операции мультипликативной записи решения обоих уравнений имеют вид х = Ь а ~. Выражение Ь а 1 в коммутативной группе называют чпсиьиым оуи деления 6 на а и Ь обозначают — (или Ь/а), а саму операцию называют операциеи а деления.
Решение уравнения в этом случае записывают в виде х = — (или х = Ь/о). Ь а Пример 2.10. Рассмотрим группу подстановок и-й сте. пени Я„всех биекций и-элементного множества (1,2,...,и). Произвольную биекцию о из Я„обычно записывают в виде обозначая тем самым, что образ 1 (при отображении а) есть а1, образ 2 есть аз, ..., образ и есть а„. Биекцию множества (1,...,и) на себя называют иодсшавоекоб этого множества. Подстановку, которая отображает а1 в аг, аз в аз, ..., аь 1 вал, ааь в аы где 1~~ам аз, ..., аь <и и все а попарно различны, а все элементы, отличные от а|, ..., аь, отображаются сами в себя, называют циклом длины Й и записывают ее в виде (а1 аз ... аь). Например, подстановку иэ группы Я4 3 2 4 1 можно записать в виде (1 3 4). Цикл длины 2 называют шронсиозвциеб.
Транспозиция представляет такое отображение множества (1, ..., и) в себя, при котором два элемента меняются местами, а остальные остаются на своих местах. Так, полная запись транспозиции (3 4) в 84 будет иметь вид 1 2 4 3 132 г. ллгквры: п*уппы и кольцл Подстановка, обратная подстановке (', -':.) есть подстановка, которая отображает а1 в 1, аг в 2, ... а„ в и. Отметим, что при записи обратной подстановки элементы первой строки тем не менее записываются в обычном порядке: 1, ..., и. В группе Яз решим следующее уравнение: 1 2 3 Х Умножив обе части уравнения слева на 1 2 3 1 2 3 получим Х, Далее, умножив полученное уравнение справа на 1 2 3 .
1 2 3 окончательно получим Х= =(23). В полугруппе в общем случае законы сокращения и разрешимость уравнений типа (2.1) и (2.2) могут не иметь места. Например, в полугруппе квадратных матриц фиксированного порядка с операцией умножения матриц из матричного равенства АХ = АУ, вообще говоря, не следует, что Х = У. Это 2.2. Групвоидм, яолугрупвы, группы можно утверждать лишь при дополнительном предположении, что беФА ~ О. Можно доказать, что в свободном моноиде, порожденном некоторым конечным множеством, оба закона сокращения справедливы, но никаких обратных элементов не существует. В полугруппе можно умножать любой элемент а сам на себя, причем в силу ассоциативности операции полугруппы элемент а а ....
а определен однозначно. Этот элемент называют и-й в раз сюпепепью элемента а и обозначают а". При этом а' = а, а"=а а" ~, п=2 3 ... 1 ! В моноиде вводят также нулевую степень элемента, полагал оО 1 Если (А,, 1) — группа, то можно ввести и отрицательные степени элемента согласно равенству а "= (а ~)", п = 1, 2, ... Без доказательства сформулируем утверждения о свойствах степеней. Теорема 2.5. Для любой полугруппы а'в . а" = а'в+", (от) а'вв (гп п~щ Теорема 2.6.
Для любой группы а "= (а") ~ (п Е 1ч), ат.ов от+в (от)~ атв (~п п~ у) Определение 2.4. Полугруппу (в частности, группу) (А, ) называют циклической если существует такой элемент а, что любой элемент х полугруппы является некоторой (целой) степенью элемента а. Элемент а называют образующим элементном полуеруппы (еруппы). Пример 2.11.
а. Полугруппа (г1е, +, 0) циклическая, с образующим элементом 1. При аддитивной записи бинарной операции возведение элемента а в положительную степень и есть сумма и этих элементов, и это записывают п. а (или па, без знака умножения). б. Группа (Е, +, 0) также циклическая. Для нее образующими элементами могут быть 1 и — 1. Рассмотрим элемент 1.
134 г. Алгквры; группы и кольцл т д о ь=о, 1=1>...>1= (,>о) (-г ~=-~, в раз (-н) 1=о (-1) =(-1)+...+(-1) =-н (н >0). Я РВЗ Если в качестве образующего взять элемент -1, то О. (-1) = = О, отрицательные целые числа получаются как положительные „степени" -1, а положительные — как отрицательные „степени" -1. Например, ( — 2) ( — 1) = 2, 4 (-1) = — 4. в.
Группа (Ез, Юз, 0) вычетов по модулю 3 циклическая, причем любой ее ненулевой элемент является образующим. Действительно, для 1 имеем 1 Щз 1 = 2, 1 Юз 1 Юз 1 = О, а для 2 получим 2г 2 ®з 2 = 1 2 ®з 2 Юз 2 = О. Изучим подробнее строение конечных циклических групп, используя мультипликативную запись бинарной операции. Напомним, что конечное алгебра (конечная гррнна,в частности) — это алгебра, носитель которой — конечное множество. Порядком конечной еруппы называют количество элементов в этой группе. Так, например, аддитивная группа вычетов по модулю й имеет порядок й. Симметрическая группа степени н, т.е.
группа подстановок Я„, имеет порядок н!. Мультипликативная группа вычетов по модулю р, где р — простое число, имеет порядок р — 1. Порядок эяелеентва а циклической группы — это наименьшее положительное н, такое, что а" = 1. Теорема 2.7.
Порядок образующего элемента конечной циклической группы равен порядку самой группы. ~ Пусть и = (6,, 1) — конечная циклическая группа с образующим элементом а и н > 0 — порядок этого элемента. Тогда все степени ае = 1, аз = а, ..., а" з попарно различны. Действительно, если а =а~, 0 <1< й < н, то а~ ~ =а"+< О = = а"а ~ = а~а ~ = а~ ~ = 1. Поскольку й — 1< о, получено противоречие с выбором н как порядка элемента а (ибо найдена 135 2.3. Кольца, тела, цаец степень, меньшая и, при возведении в которую элемента а получится единица). Осталось доказать, что любая степень элемента а принадлежит множеству (1, а,..., а" '). Для любого целого от существуют также целые п, й, такие, что та = Йи+ д, где д — целое и 0(д(п. Тогда а'а = аа"+е = аа" ае = (а")а ае = 1 ае = = ае Е (1, а,..., а" 1).
Поскольку каждый элемент группы Д есть некоторая степень элемента а, то С = (1, а, ...,а" 1) и порядок группы равен н. ° Из доказанной теоремы следует, что в бесконечной циклической группе не существует такого и > О, что для образующего элемента а группы выполняется равенство а" = 1. 2.3.
Кольца, тела, поля Определение 2.5. Хольиом называют алгебру й = (В, +,, О, 1), сигнатура которой состоит нз двух бинарных и двух нульарных операций, причем для любых а, Ь, с Е В выполняются равенства: 1) а + (Ь+ с) = (а + Ь) + с; 2) а+Ь= Ь+а; 3) а+О=а; 4) для каждого а е В существует элемент а', такой, что а+а'=О; 5)а.(Ь с)=(а 6) с; б) а.1=1.а=а; 7) а (Ь+с) =а Ь+а.с, (Ь+с).а = Ь а+с а. Операцию + называют сложением кольна, операцвю умножением кольца, элемент Π— нулем кольца, элемент 1 — единииеб кольца. Равенства 1-7, указанные в определении, называют аксиомами колька.
Рассмотрим эти равенства с точки зрения понятия группы и моноида. 136 2. АЛГЕБРЫ: ГРУППЫ И КОЛЬЦА Аксиомы кольца 1-4 означают, что алгебра (В, +, 0), сигнатура которой состоит только из операций сложения кольца + и нуля кольца О, является абелевой группой. Эту группу называют аддитивноб группой иольиа Я и говорят также, что по сложению кольцо есть коммутативная (абелева) группа.
Аксиомы кольца 5 и 6 показывают, что алгебра (В,, 1), сигнатура которой включает только умножение кольца . и единицу кольца 1, есть моноид. Этот моноид называют лфльтпиилииатиеным моиоидом иольиа Я. а говорят, что по умножению кольцо есть моноид.
Связь между сложением кольца и умножением кольца уста навливает аксиома 7, согласно которой операция умножения дистрибутивна относительно операции сложения. Учитывал сказанное вьппе, отметим, что кольцо — зто алгебра с двумя бинарными и двумя нульарными операциями 'В.= (В, +,, О, 1), такая, что: 1) алгебра (В, +, 0) — коммутативная группа; 2) алгебра (В,, 1) — моноид; 3) операция (умножения кольца) дистрибутивна относительно операции + (сложения кольца). Замечание 2.2. В литературе встречается иной состав аксиом кольца, относящихся к умножению.
Так, могут отсутствовать аксиома 6 (в кольце нет 1) и аксиома 5 (умножение не ассоциативно). В этом случае выделяют ассоциативные кольца (к аксиомам кольца добавляют требование ассоциативности умножения) и кольца с единицей. В последнем случае добавляются требования ассоциативности умножения и существования единицы. Определение 2.6. Кольцо называют иомирпыиаивным, если его операция умножения коммутативна.
Пример 2.12. а. Алгебра (Е, +,, О, 1) есть коммутативное кольцо. Отметим, что алгебра (1че, +,, О, 1) кольцом г.г. К лв, 137 не будет, поскольку (г1в, +) — коммутативный моноид, но не группа. б. Рассмотрим алгебру Еь = ((0,1, ",Й вЂ” Ц, Юы Оь 0,1) (Й ) 1) с операцией Щ сложения по модулю Й и Оь (умножения по модулю Й). Последняя аналогична операции сложения по модулю Й: тп Оь и равно остатку от деления на Й числа тп п. Эта алгебра есть коммутативное кольцо, которое называют кольцом вычетпов по модулю Й.
в. Алгебра (2л, Л, т1, И, А) — коммутативное кольцо, что сиюдует из свойств пересечения и симметпрической разностпи мнохсестпв (см. с. 35). г. Пример некоммутативного кольца дает множество всех квадратных матриц фиксированного порядка с операциями сложения и умножения матриц. Единицей этого кольца является единичная матрица, а нулем — нулевая. д. Пусть т".. — линейное пространство. Рассмотрим множество всех линейных операторов, действующих в этом пространстве.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
