Раздел 3. Элементы общей алгебры - Приднестровский государственный университет им. Т. Г. Шевченко инженерно-технический...
.RU

Раздел 3. Элементы общей алгебры - Приднестровский государственный университет им. Т. Г. Шевченко инженерно-технический...


^ Раздел 3. Элементы общей алгебры 3.1: Алгебраическая операция. Алгебра

Пусть M - произвольное множество.

Определение 3.1: Функцию типа : M n  M называется n - арной операцией, определенной на множестве М.

n - называется арностью операции , M называется основным или несущим множеством операции.

Если n=1, то операция называется унарной, если n=2 - то бинарной.

В данном определении выделим два момента:

  1. Так как операция есть функция, то результат ее применения определяется однозначно.

  2. Так как область значений операции лежит во множестве M, на которое операция действует, то говорят, что операция замкнута на множестве M.

Элементы xi набора (x1, x2,...,xn)Mn , где xiM, i=1,2,...n, называются операндами.

Операции обычно обозначают символами, называемыми операторами.

Если операция унарная, то оператор располагают перед операндом. Например, -a (унарный минус)

Если операция бинарная, то возможны три случая расположения операторов:

  1. оператор перед операндами (prefix). Например, +xy

  2. оператор между операндами (infix). Например, x+y

  3. оператор после операндов (postfix). Например, xy+

Определение 3.2: Совокупность множества M вместе с определенным на нем множеством операций =<1, 2,...,k> называется алгеброй и обозначается A=. При этом  называется сигнатурой алгебры.

Пусть MM и операции 1,  2,...  k замкнуты на множестве M, тогда A = есть подалгебра алгебры A.

Определение 3.3: Типом алгебры называется вектор арностей входящих в нее операций.

^ Примеры алгебр:

  1. Алгебра на множестве действительных чисел R с операциями + и 

A1= Ее подалгеброй будет A1  = , где N- множество натуральных чисел. Так как + и  - бинарные операции, тип данных алгебр (2,2).

  1. Рассмотрим квадрат с вершинами a 1, a 2, a 3, a 4 пронумерованными против часовой стрелки, а также всевозможные повороты этого квадрата относительно центра О, переводящие вершины в вершины. Таких различных поворотов будет 4: 0, /2, , 3/2. Обозначим их соответственно через , , , . Т.о. получим алгебру с основным множеством { a 1, a 2, a 3, a 4} и определенными на нем операциями поворота , , , .

A2=<{ a 1, a 2, a 3, a 4};, , , >


a 2 a1

/2

 2 ( a 3)= a 1


3/2

a3 a 4


Рис.3.1. Пример алгебры.

Определение 3.4: Операция, отображающая любой элемент в самого себя, называется тождественной.

В данном примере  - тождественная операция, так как (a1)= a1, (a2)= a 2, (a3)=a3, (a4)=a4. Подалгебры в этой алгебре нет.

  1. Рассмотрим множество О={, , ,  }содержащее повороты из п. 2) и определим бинарную операцию композиции двух поворотов  как их последовательное выполнение. Рассмотрим алгебру A3=Если множество конечно, то операции удобно задавать таблицей Келли:























































Подалгеброй рассматриваемой алгебры будет A3 =.


^ 3.2: Свойства бинарных алгебраических операций

Рассмотрим бинарную операцию  типа умножения, определенную на множестве A.

Определение 3.4:Операция называется коммутативной, если a,bA ab=ba.

Определение 3.5: Операция называется ассоциативной, если a,b,cA a(bc)=(ab)c.

Определение 3.6: Пусть  элемент e, такой что a ea=a. Тогда e называется левой единицей (или левым единичным элементом) по отношению к операции . Если  элемент e, такой что a ae=a, то e называется правой единицей (или правым единичным элементом) по отношению к операции . Если  элемент e, такой что a ea=ea=a, то e называется двусторонней единицей или просто единицей (единичным элементом) по отношению к операции .

Например, На множестве R по отношению к умножению число 1 является двусторонней единицей: 1x=x1=x, а по отношению к сложению двусторонней единицей является число 0: x+0=0+x=x. По отношению к вычитанию число 0 является правой единицей, но не левой: x-0=x, но 0-x=-x.

Определение 3.7: Пусть  - бинарная операция типа умножения с единицей, определенная на множестве A и xy=e, где x,yA. Тогда x называют левым обратным элементом к y и обозначают y-1, а y называют правым обратным элементом к x и обозначают x-1. Если xy=yx=e, то x называют обратным к y, а y называют обратным к x.

Менее общим свойством является свойство идемпотентности.

Определение 3.8: Операция называется идемпотентной, если a аa=a.

Идемпотентными являются операции   множеств.

Пусть на множестве A определены две бинарные операции  - типа умножения и типа сложения.

Определение 3.9: Если для a,b,cA abc=abac, то говорят, что операция  дистрибутивна по отношению к  слева. Если для a,b,cA bca=baca, то говорят, что операция  дистрибутивна по отношению к  справа.

Утверждение 3.1: Если по отношению к умножению существует единица, то она единственна, если существует обратный элемент, то он единственный.

Определение 3.10: Алгебра вида , где 2 - бинарная операция, определенная на множестве A, называется группоидом.

Если 2 - операция типа умножения, то группоид называется мультипликативным и его единичный элемент называется единицей и обозначается 1, а если 2 - операция типа сложения, то группоид называется аддитивным и его единичный элемент называется нулем и обозначается 0.

^ 3.3: Гомоморфизм и изоморфизм алгебры

Алгебры с различными типами имеют существенно различное строение. Если же алгебры имеют один и тот же тип, то наличие у них сходства характеризуется с помощью понятия гомоморфизма и изоморфизма.

Пусть даны два группоида и

Определение 3.11: Если существует отображение  : А В, такое что (x  y) = (х)  (y) для  x,y  А, то отображение  называется гомоморфизмом.

Смысл данного определения в том, что независимо от того, выполнена ли сначала операция  в множестве А, а затем отображение , или сначала выполнено отображение , а затем операция  в В - результат одинаков.

x ; y  x  y

 

(x);(y) (x  y) = (x)  (y)



Рис.3.2. Коммутативная диаграмма.

Определение 3.12: Гомоморфизм, являющийся инъекцией, называется мономорфизмом.

Определение 3.13: Гомоморфизм, являющийся сюръекцией, называется эпиморфизмом.

Определение 3.14: Гомоморфизм, являющийся биекцией, называется изоморфизмом.

Рассмотрим две алгебры и , они должны быть гомоморфны, те. (x + y) = (x)  (y) , (x  y) = (x)  (y)

Определение 3.15: Если область определения и область значений отображения совпадают, гомоморфизм называется эндоморфизмом, а изоморфизм - автоморфизмом.

Пример: Пусть дано множество А, |A|=m и рассмотрим и

и рассмотрим отображение :P(A)P(A), такое что каждому множеству Х ставится в соответствие дополнение X до универсального, обозначается . Покажем , что  - автоморфизм.

Пусть множества X, Y  Р(А), тогда

 ( X  Y) = =  =  (X )   ( Y )

 ( X  Y) = =  =  ( X )   ( Y ) 

т.е.  - изоморфизм, но так как область определения и область значения совпадают, то  -автоморфизм.
^ 3.4: Полугруппы

Определение 3.16: Группоид <А;  называется полугруппой, если относительно определенной на нем бинарной операции  имеет место ассоциативный закон, т.е.

 а,b,с  А а  ( b  с ) = (а  b)  с.

Примеры:
Определение 3.17: Если полугруппа обладает единицей, то ее называют моноидом.

Утверждение 3.1: Единица в полугруппе единственна.

Определение 3.18: Если в полугруппе имеет место коммутативный закон, то ее называют абелевой.  а,b  А а  b = b  а

Прежде чем рассмотреть тему далее рассмотрим следующее определение.

Определение 3.19: Подстановкой n - ой степени называется взаимно однозначное отображение множества А из n элементов в себя.

Пусть множество А = { а, а, а}, тогда  шесть различных перестановок элементов а, а, а:

(а, а, а) , (а, а, а) , (а, а, а) , (а, а, а) , (а, а, а) ,(а, а , а).

В случае, когда А = n всевозможных различных перестановок элементов множества А будет n= 123…n (n-факториал). 3!=123=6.

Запишем всевозможные подстановки из трех элементов (всевозможные подстановки третьей степени). Число всевозможных подстановок равно числу всевозможных перестановок.

- тождественная подстановка,



Определение 3.20: Произведением двух подстановок называется подстановка, получаемая в результате последовательного выполнения сначала 1 - ой, а затем 2 - ой из перемножаемых подстановок.

Пример:



Результат умножения всевозможных подстановок можем определить таблицей Келли.

a b c d e f

a a b c d e f

b b a d c f e

c c e a f b d

d d f b e a c

e e c f a d b

f f d e b c a


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

М = {a,b,c,d,e,f }, M, - полугруппа, т.к. a(bc)=(ab)c, ad=bc, d=d a,b,cM.

Данная полугруппа - моноид. Единицей является подстановка а, т.к. аb = b b M.

Теорема 3.1: Любая полугруппа с единицей изоморфна некоторой полугруппе подстановок.

Рассмотренная полугруппа подстановок не является абелевой т.к. dc  cd, b f.

Пример: Полугруппы и моноиды имеют особое значение при обработке строк символов в теории формальных языков.

Пусть А ={х,у,z}, х,у,z будем рассматривать как символы, а не как объекты т.е. А -алфавит. Определим множество А* как множество всех строк символов – А* = {х,у,z,ху,хz,уz,хуz,… }. Множество А* - бесконечно. На множестве А* определим операцию конкатенции ( ) следующим образом хуz  z =хуzz ;    =   , A*.

Каждая строка  имеет конечную длину   , равную числу символов в , причем разрешены повторения:  х  =1,  хуzz  =4. Для обозначения пустой строки введем символ а0 А*, тогда |а0| = 0, а0   =   а0 , таким образом, для  А – алфавита, структура является моноидом, а а0 - единица по отношению к .

Данный пример важен, т.к. для достаточно большого алфавита А, содержащего, например, все символы, доступные периферийному устройству компьютера, все языки программирования являются подмножествами множества А* и, это понятие является основным при изучении формальных языков.

Пусть дан группоид , рассмотрим уравнения а  х = b и х  а = b где а,b  А. Эти уравнения могут быть разрешимы или не разрешимы.

Определение 3.21: Если  с  А, а  с = b и с  а = b, то говорят, что уравнения разрешимы.

Уравнение может иметь несколько решений.

Определение 3.22: Группоид называется квазигруппой, если уравнение ах=b и ха=b имеют единственное решение для а,bА.

Приведенный выше пример полугруппы подстановок есть квазигруппа, т.к. хd=e, х=d и dу=е, у=d.

Различают квазигруппы с левой и правой единицей (рассмотренный выше пример полугруппы подстановок есть квазигруппа с единицей).

^ 3.5: Группы

Определение 3.23: Группой называется полугруппа , если

1) для аА еА, такой что ае=еа=а;

  1. для аА а-1А , такой что аа-1=а-1а=е, т.е. существуют единичный и братный элементы.

Т.к. - полугруппа , то в группе имеет место ассоциативный закон, т.е. для а,b,сА а(bс)=(аb)с.

Если множество А конечно, то группа называется конечной.

Число, равное А, т.е. число элементов группы, называется порядком группы.

Группа, в которой операция коммутативна, называется абелевой.

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

Для абелевых групп операция обычно обозначается как + (сложение), а единичный элемент - 0 (нуль).

Свойства групп

  1. Для a,b уравнения aх=b, ya=b однозначно разрешимы внутри группы А.

  1. (а  b)-1 = b-1  а-1

Определение 3.24(2-е определение группы): Полугруппа называется группой, если она является квазигруппой.

Примеры групп:

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

Здесь e=1, a-1= .

  1. Множество целых чисел с операцией сложения . Здесь e=0, a-1= -a.

  2. Алгебра , где множество О - множество всех поворотов квадрата относительно своего центра. Данная алгебра является циклической группой, т.к. (см. п. 3 из примера §3.1.)

= /2=(/2)1, ==(/2)2, =3/2=(/2)3, =2 =(/2)4.

-1=, -1=, -1=, -1=.

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

Теорема 3.2: Любая конечная группа изоморфна группе подстановок на множестве ее элементов.
^ 3.6: Кольцо

Определение 3.25: Алгебра называется кольцом, если :

  1. - абелева группа,

  2. - полугруппа.

  3. для  а,b,сM а(bс)=(аb) (ас),

(аb)с=(ас)(bс).

т.е. M – кольцо, если

  1.  а,b,сM а(bс)=(аb)с,

  2.  а,bM аb=bа,

  3.  0M а0=0a=а,

  4.  -aM а(-a)=(-a)а=0,

  5.  а,b,сM а(bс)=(аb)с,

  6. для  а,b,сM а(bс)=(аb)(ас)

(аb)с=(ас)(bс)

Примеры колец:

, ,

- не является кольцом, т.к. 3+5=8-четное число.

Определение 3.26: Кольцо называется коммутативным, если относительно умножения  для  а,bM аb=bа.

Определение 3.27: Если относительно умножения  кольцо обладает единицей, т.е.  еM ае=еа=а, то кольцо называется кольцом с единицей.

Определение 3.28: Если в кольце а  0 и b  0, но а  b = 0, то кольцо называется кольцом с делителями нуля, а а, b - делители нуля.

^ Пример кольца с делителями нуля:

ПустьM=ZZ=a,bZ. На данном множестве определим операции + и :

(a,b)+(c,d)=(a+c,b+d)

(a,b)(c,d)=(ac,bd)

Проверкой можно убедиться, что - кольцо, с единичным элементом (0,0):

(a,b)+(0,0)=(a+0,b+0)=(a,b)

Рассмотрим пары: (a,0)(0,0) и (b,0)(0,0).

(a,0)(b,0)= (a0,0b)=(0,0).


^ Свойства кольца


1) Т.к. - абелева группа, то

а) нулевой элемент единственный.

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

в) в сумме из n элементов скобки можно расставлять произвольно или опустить.

2) Т.к. - полугруппа, то в произведении из n элементов скобки можно расставлять произвольно или опустить.

3) Уравнение а х = b имеет единственное решение. Это уравнение определяет новую алгебраическую операцию на множестве М, называемую вычитанием: х = b – а. Относительно введенной операции имеют место свойства :

а  ( b - с ) = (аb) – (ас) ; ( b - с )  а = (bа) – (са)

4) а  0 = 0

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

Для  bM b  ( - b ) = 0, а(b(-b))=аb-аb

5) b = - ( - b )

6) - аb = - ( аb )

( - а )( - b ) = аb
3.7: Поле

Определение 3.29: Коммутативное кольцо , в котором существует хотя бы один элемент а  0, что уравнение а  х = b имеет единственное решение, где а,b M, называется полем ,т.е. выполняются следующие аксиомы

1) а  b = b  а,

2) а  ( b  с) = (а  b)  с,

3) а  0 = 0  а = а,

4) а  ( - а ) = 0,

5) аb = bа,

6) а  (bс ) = ( аb )с,

7) а(b  с) = аb  ас,

8) уравнение ах = b,а  0 - разрешимо.


^ Примеры полей:

  1. Множество действительных чисел с операциями сложения и умножения




Свойства полей


1) Любое поле содержит единицу, причем единственную. Минимальное поле может состоять из 2 - ух элементов (из нулевого для сложения и единичного для умножения {0, e}

2) Для  а М  а-1 М  а а-1 = е причем единственный.

3) Рассмотрим решение уравнения а  х = b, а  0

а-1ах = а-1b,

ех = а-1b,

х = а-1b,

х =.

Таким образом определили новую операцию - деление, относительно которой выполняются свойства:

1) ad = bc, b,d  0.

2) , b,d  0.


3) = , b,d  0.


4) , b, c,d  0.

В поле нет делителей нуля.

5) Если для некоторого целого, положительного числа n ( n , n > 0 ) выполняется равенство , где е - единица поля, то и  а М, а  0 выполняется равенство = 0, верно и обратное утверждение.

В этом случае наименьшее из таких чисел n называется характеристикой поля, в противном случае характеристикой поля считается число 0, а n называют аддитивным порядком поля.

Теорема 3.3: Ненулевые элементы поля имеют один и тот же аддитивный порядок.

Аналогично определяется мультипликативный порядок, а именно как наименьшее из целых положительных чисел m, таких что

Характеристика любого конечного поля является простым числом. Если поле имеет характеристику 0, то оно бесконечно.



rabochaya-programma-praktiki-dlya-napravleniyaspecialnosti-210202-65-proektirovanie-i-tehnologiya-elektronno-vichislitelnih-sredstv-podgotovki-inzhenerov-dlya-fakulteta.html
rabochaya-programma-praktiki-po-vneuchebnoj-vospitatelnoj-rabote-dlya-specialnostej.html
rabochaya-programma-praktiki.html
rabochaya-programma-preddiplomnoj-praktiki-dlya-slushatelej-pyatogo-kursa-obuchayushihsya-na-ochnoj-forme-obucheniya-po-specialnosti-030501-65-yurisprudenciya-stranica-3.html
rabochaya-programma-predmet-anglijskij-yazik-klass-2-obrazovatelnaya-oblast-filologiya.html
rabochaya-programma-predmet-fizika-klass-7-stranica-3.html
  • college.bystrickaya.ru/-2-reformi-nikolaya-i-istoriya-rossii-s-drevnejshih-vremen-do-konca-xx-veka-v-3-h-knigah.html
  • learn.bystrickaya.ru/glava-11-slastenin-v-a-i-dr-pedagogika-ucheb-posobie-dlya-stud-vissh-ped-ucheb-zavedenij-v-a-slastenin-i.html
  • kontrolnaya.bystrickaya.ru/rabochaya-programma-po-discipline-sovremennie-informacionnie-tehnologii-dlya-specialnosti-030301-psihologiya.html
  • esse.bystrickaya.ru/rabochaya-programma-geografiya-dlya-7-8-klassov-sostavitel.html
  • student.bystrickaya.ru/22-priobshenie-uchashihsya-k-sovremennim-nauchnim-dostizheniyam-polozhenie-o-festivale-innovacionnih-proektov-4-ispolzovanie.html
  • zadachi.bystrickaya.ru/razoruzhenie-nezakonnih-formirovanij-v-chechne.html
  • lektsiya.bystrickaya.ru/pravitelstvo-sankt-peterburga-informacionnij-byulleten-administracii-sankt-peterburga-33-684-30-avgusta-2010-g.html
  • thesis.bystrickaya.ru/primenenie-reamberina-v-kompleksnom-lechenii-bolnih-s-sochetannimi-i-mnozhestvennimi-dezintegriruyushimi-perelomami-taza-14-01-15-travmatologiya-i-ortopediya.html
  • ucheba.bystrickaya.ru/prakticheskij-seminar-aktualnie-voprosi-teorii-i-praktiki-parnoj-terapii.html
  • textbook.bystrickaya.ru/himiya-prirodnih-terpenoidnih-soedinenij-m-zh-burkeev-doktor-him-nauk-professor.html
  • nauka.bystrickaya.ru/vnastoyashem-razdele-mi-kratko-rassmotrim-osobennosti-dvizheniya-zaryazhennih-chastic-v-magnitnom-i-elektricheskom-polyah-v-magnitosfere-zemli-sbolee-podrobnim-izlozhen.html
  • holiday.bystrickaya.ru/obrasheniya-grazhdan-v-zakonodatelnoe-sobranie-sverdlovskoj-oblasti-sverdlovskoj-oblasti.html
  • literature.bystrickaya.ru/doklad-kachestvo-obrazovaniya-v-mou-sosh-20.html
  • writing.bystrickaya.ru/derzhavne-regulyuvannya-komercjno-dyalnost-chast-4.html
  • essay.bystrickaya.ru/bflomov-problemi-obsheniya-v-psihologii-uchebnoe-posobie-tekst-predostavlen-pravoobladatelem-logopatopsihologiya.html
  • learn.bystrickaya.ru/glava-11-knopka-lyuboe-izmenenie-etogo-teksta-a-takzhe-vosproizvedenie-ego-v-kommercheskih-celyah.html
  • desk.bystrickaya.ru/otchet-o-samoobsledovanii-osnovnoj-obrazovatelnoj-programmi-po-napravleniyu-190500-ekspluataciya-transportnih-sredstv-stranica-3.html
  • nauka.bystrickaya.ru/v-proizvodstvo-sulfata-ammoniya.html
  • shpargalka.bystrickaya.ru/upravlenie-gosudarstvennoj-sobstvennostyu.html
  • holiday.bystrickaya.ru/montazh-odnoetazhnogo-promishlennogo-zdaniya.html
  • prepodavatel.bystrickaya.ru/statya-predstavlyaet-soboj-obzornij-material-po-psihoterapii-zavisimostej-ot-psihoaktivnih-veshestv-vipolnenie-po-16-metodikam-videlyayutsya-sleduyushie-razdeli-problemi-psihoterapiya-kak-metod-stranica-3.html
  • textbook.bystrickaya.ru/i-politika.html
  • occupation.bystrickaya.ru/nauchno-issledovatelskaya-rabota-po-napravleniyam-temam-fizika-elementarnih-chastic-fizika-visokih-energij-teoriya-kalibrovochnih-polej-i-fundamentalnih-vzaimodejstvij-kosmologiya.html
  • uchebnik.bystrickaya.ru/vipishite-recepti-oharakterizujte-ls-po-sheme-metodicheskie-rekomendacii-i-k-ontrolnie-zadaniya-dlya-studentov.html
  • esse.bystrickaya.ru/razdel-i-3-informacionnaya-karta-aukciona-reglamentiruyushaya-poryadok-razmesheniya-zakaza.html
  • holiday.bystrickaya.ru/migel-de-servantes-saavedra-stranica-46.html
  • abstract.bystrickaya.ru/1-analiz-bis-organizacii.html
  • knowledge.bystrickaya.ru/obrazec-pismennogo-priglasheniya-na-roditelskoe-sobranie-uchebno-metodicheskoe-posobie-minsk-ripo-2003-udk-37-013.html
  • kontrolnaya.bystrickaya.ru/razdel-torgovlya-i-obshestvennoe-pitanie-tarifno-kvalifikacionnogo-spravochnika.html
  • klass.bystrickaya.ru/aalebedenko-e-n-chernozyomova.html
  • thescience.bystrickaya.ru/i-konf-otchet-o-rezultatah-samoobsledovaniya.html
  • credit.bystrickaya.ru/organizacionnie-i-didakticheskie-problemi-prepodavaniya-kursa-normografii-teorii-i-metodologii-normotvorchestva.html
  • uchit.bystrickaya.ru/tema-16-problema-istini-testi-dlya-samoproverki-znanij-razdel-i-chto-takoe-filosofiya-tema-filosofiya-v-sisteme.html
  • learn.bystrickaya.ru/etkin-anatolij-j-vechernej-i-zaochnoj-form-obucheniya-uskorennoe-vtoroe-visshee-eksternat.html
  • textbook.bystrickaya.ru/iii-organizaciya-dokumentooborota-i-ispolneniya-dokumentov-prika-z.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.