4. Разбиение множества и классы эквивалентности.

Напоминаем, что X₁, ..., X_n называется разбиением мн-ва X, если: 1) ⁿ_i=1X_i=X; 2)  i,j{1,…,n} ij X_iX_j=.

Утв. (свойство отношения эквивалентности №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, что противоречит утверждению►

5. Основное свойство отношения эквивалентности.

Утв. (свойство №2): ] C₁, …,C_n – разбиение мн-ва Х, тогда  отношение эквивалентности на Х:C₁…C_n – все его классы эквивалентности. ◄Рассмотрим на мн-ве соотношение : хх   i=1,n: x и xC_i. Покажем, что отношение  является отношением эквивалентности: 1) – рефлективно, т.к. хх ( i=1,n: хС_i); 2) – симметрично. Если ху, т.е. {x,y}C_i, тогда {y,x}C_i  yx; 3) – транзитивно. Если ху, yz   i,j(1,…,n), x,yC_i, y,zC_j  C_iC_j  C_i=C_j (т.к. разбиение)  x,zC_i  хz►

6. Фактор множества. Примеры.

Def: ] – отношение эквивалентности на мн-ве Х; C₁…C_n – все различные классы эквивалентности относительно отношения . Тогда {C₁…C_n}=X/ называется фактор-множеством мн-ва Х относительно отношения экв. . Пр.: Z– целые числа, mN. На Z рассмотрим отношение _m: a_mb  m|a-b (или a, b имеют одинаковые остатки от деления на m). Отношение _m– называется отношением сравнимости по mod m. Запись a_mb эквивалентна ab(mod m). Легко видеть _m– отношение эквивалентности ◄►, найдем класс эквивалентности ] aZ, тогда a+mZ– класс эквивалентности относительно _m (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=Z_m={{mZ},…,{m-1+mZ}} (мн-во вычетов по mod m). Классы эквивалентности или элементы фактор-множества могут быть идентифицированы с помощью любого своего представителя:

Z_m={{-k+mZ}…{mZ}{1+mZ}…{k+mZ}}, Z₅={{5Z}…{4+5Z}}={{-2+5Z}{-1+5Z}{-3+5Z}… и т.д. 3+5Z, т.к. -2=(-1)5+3.

7. Алгебраические структуры. Определения и примеры полугрупп и моноидов.

Def: ] А – некоторое мн-во, отображение f:ААА называется бинарной операцией на мн-ве А. Пр.1: Z +– операция над Z, т.е. +: ZZZ, (a,b)|a+b (эта операция задана алгоритмически в ср. школе). M_n(R)– мн-во всех матриц размера nn с элементами на R. : M_n(R)M_n(R)M_n(R). Пр.2.: ] f– операция, заданная на А, МА. Рассмотрим операцию: : МММ, (m₁,m₂)| m₁fm₂). (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) Если А()– полугруппа и  е– един. элемент еА(), то А()–моноид.