Тема 2. Відношення і функції

2.1. Відношення

Почнемо з простого прикладу. Позначимо через S множину всіх студентів університету, а через Т множину всіх його викладачів. Для кожного студента s ( S і кожного t ( T, одно із двох є істинне:

• s відвідує лекції t; або

• s не відвідує лекції t.

Введемо поняття відношення. Нехай s ( S і t ( T. Позначимо sRt факт відвідування s лекцій t, підкреслюючи тим самим, що s і t перебувають один з одних в певних відносинах, а саме, студент - викладач. Літера R походить від слова relation – відношення. Якщо тепер розглянути всі можливі пари (s, t) студент- викладач, тоді деякі з цих пар задовольняють відношення sRt, а інші ні. Іншими словами, відношення R може бути представлене множиною пар, для яких sRt істинно. Це підмножина всіх можливих пар (s, t).

Означення 2.1.1. Множина A B = {(a, b) : a ( A і b ( B} називається декартовим добутком множин A і B. Іншими словами , A B це множина всіх впорядкованих пар (a, b), де a ( A і b ( B .

Означення 2.1.2. Нехай A і B довільні множини. Відношення R на А і В це підмножина декартового добутку A B.

Зауваження. В багатьох випадках A = B. Тоді під відношенням R на A будемо розуміти підмножину декартового добутку A А.

Приклад 2.1.1. Нехай A = {1, 2, 3, 4}. Визначимо відношення R на A написавши (x, y) ( R якщо x < y. Тоді

R = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}.

Приклад 2.1.2. Нехай A множина всіх підмножин множини {1, 2}; тобто, A = {( , {1}, {2}, {1, 2}}. Тоді

R = {((, {1}), ((, {2}), ((, {1, 2}), ({1}, {1, 2}), ({2}, {1, 2})}

є відношення на A , де (P,Q) ( R якщо P ( Q.

2.2. Відношення еквівалентності

Почнемо з прикладу.

Приклад 2.2.1. Раціональним називається число виду p/q, де p ( Z і q ( N. Воно може бути представлено також у вигляді впорядкованої пари (p, q), де p ( Z і q ( N. Нехай A = {(p, q) : p ( Z і q ( N}. Визначимо відношення R на A написавши ((p₁, q₁), (p₂, q₂)) ( R якщо p1q2 = p2q1, тобто, якщо p₁/q₁ = p₂/q₂.

Відношення R має цікаві властивості:

• ((p, q), (p, q)) ( R для всіх (p, q) ( A;

• для будь яких ((p₁, q₁), (p₂, q₂)) (R, також ((p₂, q₂), (p₁, q₁)) (R; і

• для будь яких ((p₁, q₁), (p₂, q₂)) ( R і ((p₂, q₂), (p₃, q₃)) (R, маємо ((p₁, q₁), (p₃, q₃)) (R.

Вони описують еквівалентність простих дробів.

Дослідимо ці властивості в загальному випадку. Нехай R є відношення на множині A.

Означення 2.2.1. Припустимо, що ( a ( A, (a, a) ( R. Таке відношення R називається рефлексивним.

Приклад 2.2.2. Відношення R визначене на множині Z як (a, b) (R якщо a ( b, є рефлексивне.

Приклад 2.2.3. Відношення R визначене на множині Z як (a, b) (R якщо a < b, не рефлексивне.

Означення 2.2.2. Припустимо, що ( a, b ( A, (b, a) ( R якщо (a, b) ( R. В цьому випадку відношення R називається симетричним.

Приклад 2.2.4. Let A = {1, 2, 3}.

• Відношення R = {(1, 2), (2, 1)} симетричне, але не рефлексивне.

• Відношення R = {(1, 1), (2, 2), (3, 3)} рефлексивне і симетричне.

• Відношення R = {(1, 1), (2, 2), (3, 3), (1, 2)} рефлексивне, але не симетричне.

Означення 2.2.3. Припусимо, що a, b, c ( A і (a, c) ( R завжди, коли (a, b) ( R і (b, c) ( R. В цьому випадку відношення R називається транзитивним.

Приклад 2.2.5. Нехай A = {1, 2, 3}.

• Відношення R = {(1, 2), (2, 1), (1, 1), (2, 2)} є симетричне і транзитивне, але не рефлексивне.

• Відношення R = {(1, 1), (2, 2), (3, 3)} є симетричне , транзитивне і рефлексивне.

• Відношення R = {(1, 1), (2, 2), (3, 3), (1, 2)} є рефлексивне і транзитивне, але не симетричне.

Означення 2.2.4. Припустимо, що відношення R на множині A є рефлексивним, симетричним і транзитивним. Таке відношення називається еквівалентністю.

Приклад 2.2.6. Визначимо відношення R на Z написавши (a, b) ( R якщо різниця a - b є кратною 3. Тоді R є відношенням еквівалентності на Z. Щоб пересвідчитися в цьому, досить помітити, що ( a ( Z, a - a = 0 є кратним 3, так що (a, a) ( R. Це значить, що R рефлексивне. Припустимо тепер, що a, b ( Z. Якщо (a, b) ( R, то a - b кратне 3. Іншими словами, a - b = 3k для деякого k ( Z, так що b - a = 3(- k). Значить b- a також кратне 3, тому (b, a) (R. Звідси слідує, що R симетричне. Нарешті припустимо, що a, b, c Ѓ( Z . Якщо (a, b), (b, c) ( R, тоді a- b і b - c кратні 3. Іншими словами , a- b = 3k і b- c = 3m для деяких k,m ( Z, так що a- c = 3(k +m). Значить a- c є кратним 3, так що (a, c) ( R. Звідси слідує, що R є транзитивним.