1. Бінарні відношення. Рефлексивні, симетричні, транзитивні бінарні відношення. Розбиття на класи. Фактор-множина.

Прямим добутком двох множин А, В назив. множина всіх впорядкованих пар елементів а, b таких, що аА і bВ і позначається АВ.

АВ={<а, b>: аА  bВ}. Якщо, наприклад, А={1,2}, В={3,4}, то АВ={<1,3>, <1,4>, <2,3>, <2,4>}, ВА={<3, 1>, <3, 2>, <4,1>, <4, 2>}. З цього прикладу випливає, що АВВА.

Бінарним відношенням між елементами множини А і В називається будь-яка підмножина пря мого добутку АВ.Якщо елементи а, b перебувають у бінарному відношенні , то це позначають так <a, b > або а  b.

Бінарне відношення еквівалентності визначають, як правило, на одній множині, тобто, розглядають прямий добуток АА.

Бінарне відношення   АА називається відношення еквівалентності, якщо воно:

1. рефлексивне, тобто (а) (а, а);

2. симетричне, тобто (а, b) (а, b  b, а);

3. транзитивне, тобто ( а, b, с) (а, b  b, с  а, с).

Очевидно, що =АА є відношення еквівалентності.

Взагалі для визначення того, чи буде бінарне відношення  відношенням еквівалентності потрібно перевірити виконання вимог 1, 2, 3.

Озн. Сукупність S непорожніх підмножин множини А називають розбиттям множини А, якщо кожний її елемент належить одній і тільки одній підмножині з S.

Кожна непорожня множина А завжди має два тривіальні розбиття: поелементне і ціле розбиття.

Нехай  - будь-яке віднош. еквівалентності з АА.Сукупність всіх елементів хА, які знаходяться у віднош.  з елементом а наз. класом еквівалентності і позначається [а].Таким чином, [а]={хА:х, а}.

З означення випливають так дві властивості:

1. Кожний елемент аА належить своєму класу еквівалентності [а] (це випливає з рефлексивності ).

2. Різні класи еквівалентності не перетинаються.

Доведення проведемо методом від супротивного, використовуючи модифікацію АВ А 

Припустимо, що різні класи еквівалентності [а], [b] перетинаються і с їх спільний елемент, тобто са і сb. Покажемо, що а=b.Нехай ха. Тоді х,а і так як а,с, то х,с. Оскільки х,с, то х,b. Це означає, що хb або аb. Аналогічно показуємо, що bа. Звідси слідує, що а=b.

Сукупність усіх класів еквівалентності множини А за відношенням еквівалентності  називається фактор-множиною і позначається А/.

Наприклад. Фактор-множина від А=Z за відношенням еквівалентності ={х,у: (х-у)**3} є А\={{3к},{3к+1}, {3к