1. Бинарные oтношения.

Пусть А, В- непустые мн-ва. Декартовым произвдением множеств А и В называется мн-во всех упорядоченных пар (а,b), где а А, b В. Обозначается А×В.

Бинарным отношением на мн-ве М называется подмно-во декартова произведения М×М. Если ρ - бинарное отношение на мн-ве М и (а,b) ρ, то говорят что эл-нт a находится в от­ношении ρ с элементом b. Обозначения: (a,b) ρ, aρb, а≈b(ρ). Пр-­рами бинарных отношений на мно-ве всех натуральных чисел служат отношения <, >,≥, ≤,=, ( - отношение делимости: (а,b) <=> а b).

Cв-ва бинарных отношений:

1. рефлексивность а М(а,а) ρ;

2. симметричность: если а,b М из того, что (а,b) ρ (b,а) ρ;

3. антисимметричность: если а,b М из того, что (а,b) ρ и (b,a) ρ a=b

4. транзитивность:если а,b,c М из того что (а,b) ρ и (b,с) ρ следует (а,с) ρ.

5. антирефлексивность:если а М (а,а) ρ.

Рефлексивное, симметричное и транзитивное бинарное отно­шение наз-ся отношением эквив-ти или эквив-тью. Антисимметричное и транзитивное бинарное отношение на­зывается отношением порядка.

Пусть ρ – эквив-ть. Если а М, обозначим K_a={b|(a,b) ρ}, назовем К_а классом по эквив-ти ρ, порож­денным элементом а.

Говорят, что семейство { }, подмн-в мн-ва М задает разбиение мн-ва М, если вып-ся условия:

1. каждое подмножество этого семейства не пусто;

2. если ,=>

3. 

Пр-ры: 1)отношение «=» чисел на R

2)на Z отношение сравнимости по модулю а≡b(mod m)

3) отношение ~ (подобия) треугольников.

Т1. Мн-во всех классов по эквив-ти ρ, заданной на множ-ве М, образует разбиение мн-ва М. Обратно, если задано разбиение{ } , мн-ва М, то на М найдется эквив-ть , классы по которой задают исходное разбиение.

Док Рассм-м произвольный класс K_a={b|(a,b) ρ} по эквив-ти ρ. К_а ,так как поск-ку, в силу рефл-ти, (а,а) ρ. Чтобы показать, что различные классы по эквив-ти ρ не пересекаются, докажем, что если 2 класса имеют общий эл-нт, то они совпадают. Пусть следовательно, (а,с) ρ и (b,с) ρ. Так как ρ - симметричное отношение, то (с,b) ρ , и, в силу транзитивности, (а,b) ρ. Для любого элемента х К_а (а,x) ρ. Поскольку (b,а) ρ и (а,x) ρ, то, в силу транзитивности ρ, (b,x) ρ и, поэтому х К_b ,откуда К_а . Аналогично, К_b К_а, следовательно, К_а= К_b.

По определению , Пусть а М, тогда а К_а, следовательно а Значит М .Поэтому М= .Т.О. классы по эквив-ти ρ образуют разбиение мн-ва М.

Обратно, пусть дано разбиение{ } , множества М. Определим отношение σ следующим образом: σ={(а,b)| найдется при некотором что a,b }. Пусть а М, тогда a ,=,> a , (а,а) . σ — рефлексивное отношение. Если (a,b) ,то а,b , поэтому b,a , что влечет (b_ya) . σ- сим­метричное отношение. Пусть (a,b) и (b,c) . Из этого следует, что а,b , b,c . Так как b ,то , , зна­чит a,b,c . σ - транзитивное отношение. Окончательно, σ-экви­в-ть. Если а , то класс К_а по σ совпадает, по опр-ию σ, с мн-вом . ЧТД.

Мн-во всех классов К_а по эквив-ти ρ на мн-­ве М наз-ся фактор-мн-вом и обозначается М/ρ.

Пр-ры. 1.М={1;2;3;4;5;6;7}, ρ ={(1;1);(2;2);(3;3);(4;4);(5;5); (6;6);(7;7);(1;3);(3;1);(2;5);(2;7);(5;7);(5;2);(7;2);(7;5);(4;6);(6;4)}.Не­посредственной проверкой убеждаемся, что ρ- отношение эквив-ти. Построим фактор-мн-во М/ ρ={{l;3};{2;5;7};{4;6}}.