Курсовая работа: Комбінаторика

Транзитивним є відношення менше (< ), не більше (≤ ), подільності ( ), рівносильності (≡ ), конгруентності (), паралельності (║ ), подібності (~ ).

Антитранзистивними є відношення перпендикулярності ().

Відношення між елементами множин можуть мати одну, дві, три або не володіти ні однією властивістю.

Наприклад, відношення перпендикулярності в множині прямих є симетричним, але не має рефлексивної і транзитивної властивостей, відношення р „число х більше числа у” у множині натуральних чисел є транзитивним, але не володіє властивостями рефлективності і симетричності.

§ 2. 4. Відношення еквівалентності.

Бінарне відношення р називається відношенням еквівалентності, якщо воно рефлексивне, симетричне і транзитивне.

Відношення: „бути однокурсником” у множині студентів; „мати один і той же корінь” у множині слів є відношеннями еквівалентності.

Якщо між елементами деякої множини, встановлено відношення еквівалентності, то цим самим ми розбиваємо задану множину на класи.

Розглянемо відношення р: „давати однакову остачу при діленні на 3” у множині невід’ємних цілих чисел. Цим самим ми розбиваємо задану множину на такі класи, які не перетинаються:

К₁ = {0, 3, 6, 9 ......} – остача нуль

К₂ = {4, 7, 10 ......} – остача один

К₃ = {5, 8, 11 ......} – остача два

Класи, на які відношення еквівалентності розбиває множину А називаються класами еквівалентності . Це розбиття характеризується такими властивостями:

1. Ці класи не порожні

К_і ≠ Ш для всіх і = 1, 2, 3, ......, n

2. Будь-які два класи не перетинаються

К_і ∩ К_у = для будь-яких і, у = 1, 2, 3, ......, n

3. Об’єднання усіх класів дає універсальну множину А

К_і = А

Легко переконатися, що елементи із одного класу еквівалентні між собою, а елементи із різних класів – ні.

Теорема

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

Доведення

Нехай в множині А є відношення еквівалентності р . Візьмемо з цієї множини якийсь елемент а і виділимо в окремий клас К (а ) всі елементи, які знаходяться з а у відношенні р

К (а ) = {у | у є А, ару } (1)

Задане відношення р розіб’є всю множину А на ряд класів К, в результаті чого ми одержимо множину класів {К (а )}.

Доведемо, що множина {К (а )} для всіх а є А є розбиттям на класи, тобто що вона задовольняє трьом умовам розбиття на класи, а саме, що:

1) К (а ) ≠ Ш

2) К (а ) ∩ К (b) = Ш

3) К (а ) = А

Покажемо, що справедлива перша умова.

Раз р є відношенням еквівалентності, то воно є рефлексивне, тобто ара . Значить К (а ) має хоча б один елемент а і вже К (а ) не порожня множина

К (а ) ≠ Ш

Покажемо, що справджується умова 2) для будь-яких а і b є А,

якщо а b .