6. Основні поняття теорії відношень

Означення. Для будь-яких двох множин і довільна підмножина називається бінарним відношенням між і (або просто на , якщо = ). Для впорядкованої пари використовують позначення і кажуть, що знаходиться у відношенні з . Якщо ж два елементи не зв’язані відношенням , то записуємо , або .

Приклади. 1. Нехай . Визначимо на цій множині відношення : . Явний запис відношення має вигляд:

.

2. Множина є відношенням на множині : ; ; .

3. Множина є відношенням на множині : ; , , .

4. Множина є відношенням на множині .

5. Множина всіх пар точок , площини таких, що , є відношенням ”бути симетричним відносно осі ”.

6. Множина задає добре знайомі декартові координати точки на площині. Оскільки ця множина дорівнює множині , то за означенням вона є відношенням.

7. На множині людей також можна вказати відношення: „бути начальником”, „бути братом”, „бути молодшим”, „жити в одному місті”, «вчитися в одній академгрупі».

Для будь-якої непорожньої множини визначимо такі окремі випадки відношень:

Означення. Повним (універсальним) відношенням називається відношення, яке виконується для будь-якої пари елементів множини .

Таким чином, .

Універсальними є: відношення з прикладу 7, відношення „вчитися в одній академгрупі” на множині студентів групи ІБД 2х.

Означення. Порожнім відношенням називається відношення, яке не виконується для жодної пари елементів множини .

Таким чином, оскільки , то є відношенням на .

Порожнім є відношення „бути братом” на множині жінок.

Означення. Тотожним (діагональним) відношенням називається відношення, яке виконується тільки між елементом і ним.

.

Тотожнім є відношення з прикладу 5.

З кожним бінарним відношенням на множинах і зв’язані дві множини – область визначення і область значень.

Означення. Множина перших компонент всіх пар, які входять до відношення називається областю визначення відношення .

Означення. Множина других компонент всіх пар, які входять до відношення називається областю значень відношення .

Приклад. Розглянемо відношення з прикладу 1, явний запис якого має вигляд:

.

Тоді , .

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

Оскільки відношення – це множина, над ним можна виконувати всі теоретико-множинні операції: переріз, об’єднання, віднімання, доповнення. Крім того для відношень має зміст операція обернення. Перехід від до здійснюється взаємною перестановкою компонент кожної пари, яка входить до відношення.

Означення. Нехай – бінарне відношення на множинах і . Відношенням, оберненим до відношення називається таке відношення , що тоді і тільки тоді, коли .

.

Таким чином, обернене відношення зв’язує ті ж самі пари елементів, що й , але в зворотному порядку. Отже, якщо , то і , .

Приклад. Нехай і : . Тоді

.