Напоминаем, что X1, ..., Xn называется разбиением мн-ва X, если: 1) Èni=1Xi=X; 2) " i,jÎ{1,…,n} i¹j XiÇXj=Æ.
Утв. (свойство отношения эквивалентности №1): мн-во всех классов эквивалентности ²~² на мн-ве X есть разбиение мн-ва X (мн-во X разбивается на классы эквивалентности).◄а) X=ÈxÎXx (т.к. xÎx). В этом объединении содержатся одинаковые элементы (по пред. утверждению). Тогда по этому утверждению: ÈxÎXx=xÈx¢È…Èx²Èy=xÈy, где x~x¢, причем x=x¢=…=x². б) Допустим, что y¹x: yÇx¹Æ, т.е. $ zÎyÇx Þ zÎx и zÎy Þz~x и z~y Þ x~y Þ x=y, что противоречит утверждению►
Основное свойство отношения эквивалентности.
Утв. (свойство №2): ] C1, …,Cn – разбиение мн-ва Х, тогда $ отношение эквивалентности на Х:C1…Cn – все его классы эквивалентности. ◄Рассмотрим на мн-ве соотношение r: хrх¢ Û $ i=1,n: x и x¢ÎCi. Покажем, что отношение r является отношением эквивалентности: 1) r– рефлективно, т.к. хrх ($ i=1,n: хÎСi); 2) r– симметрично. Если хrу, т.е. {x,y}ÌCi, тогда {y,x}ÌCi Þ yrx; 3) r– транзитивно. Если хrу, yrz Þ $ i,jÎ(1,…,n), x,yÎCi, y,zÎCj Þ CiÇCj¹Æ Þ Ci=Cj (т.к. разбиение) Þ x,zÎCi Þ хrz►
Фактор множества. Примеры.
Def: ] r– отношение эквивалентности на мн-ве Х; C1…Cn – все различные классы эквивалентности относительно отношения r. Тогда {C1…Cn}=X/r называется фактор-множеством мн-ва Х относительно отношения экв. r. Пр.:Z– целые числа, mÎN. На Z рассмотрим отношение rm: armb Û m|a-b (или a, b имеют одинаковые остатки от деления на m). Отношение rm– называется отношением сравнимости по modm. Запись armb эквивалентна aºb(mod m). Легко видеть rm– отношение эквивалентности ◄►, найдем класс эквивалентности ] aÎZ, тогда a+mZ– класс эквивалентности относительно rm (a+mZ={a+mk| kÎZ}). Иногда класс эквивалентности a+mZ называют вычетом по mod m. Z разбивается m на классы эквивалентности a+mZ. Классы эквивалентности определяются множеством остатков от деления на m, т.е. числами вида 0,1,…,m-1. Значит Z разбивается на классы эквивалентности Z={mZ}È{1+mZ}È…È{{m-1)+mZ}, Z/m=Zm={{mZ},…,{m-1+mZ}} (мн-во вычетов по mod m). Классы эквивалентности или элементы фактор-множества могут быть идентифицированы с помощью любого своего представителя:
Zm={{-k+mZ}…{mZ}{1+mZ}…{k+mZ}}, Z5={{5Z}…{4+5Z}}={{-2+5Z}{-1+5Z}{-3+5Z}… и т.д. 3+5Z, т.к. -2=(-1)×5+3.
Алгебраические структуры. Определения и примеры полугрупп и моноидов.
Def: ] А – некоторое мн-во, отображение f:А´А®А называется бинарной операцией на мн-ве А. Пр.1:Z ²+²– операция над Z, т.е. ²+²: Z´Z®Z, (a,b)|®a+b (эта операция задана алгоритмически в ср. школе). Mn(R)– мн-во всех матриц размера n´n с элементами на R. ²*²: Mn(R)´Mn(R)®Mn(R). Пр.2.: ] f– операция, заданная на А, МÌА. Рассмотрим операцию: j: М´М®М, (m1,m2)|® m1fm2). (1+2Z)ÌZ. Рассмотрим операцию ²+² на мн-ве (1+2Z), отображение ²+²: (1+2Z)´(1+2Z)®Z, не является операцией на (1+2Z).
Def: ] А(*)– мн-во с бинарной операцией, операция ²*² ассоциативна, если " a,b,сÎA Þ a+(b+с)=(a+b)+с; операция ²*² коммутативна, если " a,bÎA Þ a*b=b*a. Пр.: Рассмотрим операцию на R.] *: Z´Z®Z,(a,b)|®-a-b; (1*2)*3=(-1-2)*(-3)=0, 1*(2*3)=(-1)*(-2-3)=4.
Def: ] А(*)– мн-во с бинарной операцией: 1) Элемент еÎА: " аÎАÞ а´е=е´а=а называется единичным элементом мн-ва; 2) ] е– ед. элемент А(*), Элемент аÎА называется обратимым элементом, если $ а--1ÎА: а´а-1= а--1´а=е.
Утв.: А(*)– мн-во с бинарной операцией: 1) если $е– единичный элемент А(*), то он единственный; 2) если а обратим, то а-1– единственный. ◄1) от противного: допустим, что $ е¢=е, е¢ÎА, е¢– ед. элемент. " хÎА Þ х´е-1= е-1´х=х. Выберем х=е е=е´е-1= е-1´е=е¢, то е– ед. элемент; 2) самостоятельно►
Def: ] А(*)– мн-во с бинарной операцией (*): 1) Если ²*² ассоциативна, то А(*)– полугруппа; 2) Если А(*)– полугруппа и $ е– един. элемент еÎА(*), то А(*)–моноид.
Определения и примеры групп.
Def: ] А(*)– мн-во с бинарной операцией (*): 3) Если А(*)– моноид и " аÎА: а– обратим, то А(*)– группа; 4) Если А(*)– группа и ²*²– коммутативна, то А(*)– абелева группа.
4)] W={1,2…n}. Мн-во всех биективных преобразований мн-ва W относит. композиции отображений.
Sn– симметрическая группа порядка n (группа всех подстановок). g: W®W и h: W®W, g°e=e°g=g,
Определения и примеры колец.
Def: Пусть А(*,°)– мн-во с двумя бинарными операциями называется кольцом, если: а) А(*)– абелева группа; б) А(°)– полугруппа; в) операции ²*² и ²°² дистрибутивны, т.е. " a,b,cÎA Þ a°(b*c)=(a°b)*(a°c), (b*c)°a=(b°a)*(c°a). Def: Кольцо наз. коммутативным, если операция ²°² коммутативна.Def: Кольцо А(*,°) наз. кольцом с единицей, если относительно ²°² А(°)– моноид ($ еÎА – ед. элемент относит ²°²).
Пр.:1) Mn(R)– кольцо матриц под R (+,×). A(BC)=(AB)C, A+B=B+A, A(B+C)=AB+AC;
2) Zm– мн-во вычетов на mod m, Zm={mZ, 1+mZ, …, (m-1)+mZ}. Определим операции на Zm: а) [i+ mZ]+[j+ mZ]=[(i+j)(mod m)+mZ], б) [i+ mZ]×[j+ mZ]=[(i×j)(mod m)+mZ].
m=7: [6+7Z]+[5+7Z]=[4+7Z], [6+7Z]×[5+7Z]=[2+7Z].
Обратный: [а+mZ]+[x+mZ]= [mZ] (xÜm-a),
-[3+7Z]=[4+7Z] единица [1+mZ]. Zn– коммутативное кольцо с единицей. Zm– кольцо вычетов по mod m, Zm={0,…,m-1}
Пример m=3
m=2
Z2={[4+2Z],[-3+2Z]}
3) Z(+,×)– ком. кольцо с единицей.
Определения и примеры полей. Делители нуля.
Def: Пусть А(*,°)– мн-во с двумя бинарными операциями, А(*,°)– наз.полем, если: 1) А(*,°)– коммутативное кольцо с единицей; 2) ] ÆÎА– ед. элемент А(*) и " aÎA, a¹Æ $ а-1– обратный элемент к а относительно ²°².
Пр.:1) Кольцо многочленов над полем. Пусть P– поле. Рассмотрим мн-во последовательностей вида: (а0,а1 …,аk) аiÎР. Если последовательность обладает тем свойством, что $ iÎN: "j>i аj= аj+1=…=0, то такая послед. наз. многочленом. ] P[x]– мн-во всех многочленов над полем P. На P[x] определим операции:
Ck=åki=0ak-ibi. P[x](+,·) – коммутативное кольцо с ²1²◄►.
Степенью многочлена будем называть такое iÎN, что ai¹0, a+1=aI+2=…=0. Рассмотрим многочлены, обозначим: (1,0,0,…)=1, (0,1,0,…)=х, (0,0,1,0,…)= =х×х=х2, (0,0,…,1,0,…)=хi. Легко видеть, что многочлен (а0,…,аi,аi+1,… ) i-ой степени может быть записан в виде: а0+а1х+а2х2+…+ аiхi.
