Материал: discrete_mathematics

2. Для скінченної множини A = {a1, a2, …, an} установити взаємно однозначну відповідність між множинами β(A) і {0, 1}|A|.

Довільній множині Mβ(A) поставимо у відповідність двійковий вектор (b1, b2, …, bn) {0, 1}|A|, означений так: bk = 1, якщо

bk M, інакше bk = 0, k = 1,2,…,n.◄

Бієктивне відображення з A в A називають підстановкою множини A.

Для довільної відповідності C між A та A позначимо через

C(n) відповідність C °C °…°C (n входжень літери C). Вважаємо,

що C(0) = iA та C(1) = C.

Наведемо приклади відповідностей, відображень і функцій.

Приклад 2.23.

1.Відповідність між клітинками та фігурами на шахівниці у будь-який момент гри є функціональною, але не є відображенням, оскільки не всі поля шахівниці зайняті фігурами.

2.Відповідність між натуральними числами й сумами цифр їхнього десяткового запису є відображенням. Це відображення не є ін'єктивним, оскільки йому належать, наприклад, такі пари,

як (17, 8) і (26, 8).

3.Відповідність, за якою кожному натуральному числу n N відповідає число 3n, є взаємно однозначною відповідністю між множиною всіх натуральних чисел і множиною натуральних чисел, кратних 3.

4.Відповідність між множиною точок координатної площини R2 і множиною всіх векторів з початком у точці (0, 0) є взаємно однозначною.

5.Нехай f – відповідність між A та B. Довести, що f – усюди

визначена тоді й тільки тоді, коли iA f °f –1.

Нехай f – усюди визначена відповідність між A та B, а x – довільний елемент множини A (x A), тоді (x, x) iA. Зі всюди ви-

значеності f випливає, що існує такий елемент y B, що (x, y) f, тоді (y, x) f –1 та (x, x) f °f –1, отже, iA f °f –1. Для доведення оберненого твердження розглянемо довільний елемент

x A (x, x) iA

(з умови задачі) (x, x) f °f –1 ( y: (x, y) f (y, x) f –1).

Із останнього твердження випливає всюди визначеність f. ◄

112

Завдання для самостійної роботи

1. Нехай задано множини A = {a, b, c, d} та B = {1, 2, 3, 4, 5} і відповідності між A та B:

C1 = { (a, 1), (a, 2), (a, 5), (b, 1), (b, 4), (d, 2), (d, 4), (d, 5)}, C2 = { (a, 2), (a, 5), (b, 2), (b, 3), (c, 3), (d, 2), (d, 3)},

C3 = { (b, 1), (b, 2), (b, 4), (c, 1), (c, 5), (d, 1), (d, 2)}.

Визначити:

Побудувати графіки та діаграми відповідностей C1, C2, C3 і відповідностей із п. (б)–(е).

2. Нехай задано множини A = {a, b, c, d}, B = {1, 2, 3, 4, 5} і

5. Нехай C1 – відповідність між A та B, C2 – відповідність між B і G. Довести, що коли C1 ° C2 = D, то

Pr1D Pr1C1 та Pr2D Pr2C2.

113

6. Що можна сказати про відповідність C між множинами A та B, якщо:

(а) для будь-якого x A існує y B такий, що (x, y) C; (б) з (x, y), (x, z) C випливає y = z;

(в) з (x, y), (z, y) C випливає x = z;

(г) для будь-якого y B існує x A такий, що (x, y) C;

(д) для будь-якого x A існує єдиний y B такий, що (x, y) C, і навпаки, для будь-якого t B існує єдиний z A такий, що

(z, t) C?

7. Нехай задано такі відповідності між множинами

A = {a, b, c, d, e} і B = {1, 2, 3, 4, 5}:

C1 = {(a, 3), (a, 4), (b, 1), (b, 5), (c, 2), (d, 2), (d, 5)}, C2 = {(a, 1), (b, 2), (c, 3), (c, 4), (e, 5)},

C3 = {(a, 1), (b, 3), (c, 4), (d, 2), (e, 4)},

C4 = {(a, 2), (a, 3), (b, 2), (c, 3), (c, 5), (d, 1), (e, 3), (e, 4)}, C5 = {(a, 3), (b, 4), (c, 5), (d, 1), (e, 2)}.

Визначити, які з відповідностей усюди визначені, функціональні, ін'єктивні, сюр'єктивні, бієктивні (взаємно однозначні). Побудувати графіки та діаграми цих відповідностей.

8. Установити взаємно однозначну відповідність між мно-

жинами:

(а) Ak та ANk; (б) β(A) та {0, 1} A.

9. Нехай f – відповідність між A та B. Довести, що: (а) f функціональна тоді й тільки тоді, коли f –1 °f iB; (б) f є відображенням тоді й тільки тоді, коли

iA f °f –1 та f –1 °f iB;

(в) f сюр'єктивна тоді й тільки тоді, коли iB f –1 °f; (г) f ін'єктивна тоді й тільки тоді, коли f °f –1 iA; (д) f взаємно однозначна тоді й тільки тоді, коли

f °f –1 = iA та f –1 °f = iB.

2.6. Відношення. Властивості відношень

Підмножину R декартового степеня M n деякої множини M

називають n-місним (n-арним) відношенням на множині M.

Кажуть, що елементи a1, a2, …, an M перебувають у відношенні

R, якщо (a1, a2, …, an) R.

114

При n = 1 відношення R M називають одномісним, або унарним. Таке відношення часто називають також ознакою, або

характеристичною властивістю елементів множини M. Кажуть,

що елемент a M має ознаку R, якщо a R і R M. Наприклад, ознаки непарність і кратність 7 виділяють із множини N натуральних чисел відповідно унарні відношення

R′ = {2k – 1 | k N } і R′′ = {7k | k N }.

Найпопулярнішими в математиці є двомісні, або бінарні відношення, на вивченні властивостей яких зупинимося детальніше. Далі скрізь під словом відношення розумітимемо бінарне відношення. Якщо елементи a, b M перебувають у відношенні R, тобто (a, b) R, то це часто записують також у вигляді aRb. Зауважимо, що бінарні відношення іноді розглядають як окремий випадок відповідностей (а саме – як відповідності між однаковими множинами), тому багато означень і понять для відношень подібні до аналогічних означень і понять для відповідностей.

Приклад 2.24. Наведемо приклади бінарних відношень на різних множинах.

1. Відношення на множині N натуральних чисел:

R1 – відношення менше чи дорівнює, тоді

4 R1 9, 5 R1 5 і 1 R1 m для будь-якого m N; R2 – відношення ділиться на, тоді

24 R2 3, 49 R2 7 і m R2 1 для будь-якого m N;

R3 – відношення є взаємно простими, тоді

15 R3 8, 366 R3 121, 1001 R3 612;

R4 – відношення складаються з однакових цифр, тоді

(a, b) R7 (c, d), якщо a ≤ c і b ≤ d. Зокрема,

115

(1, 7) R7 (20, 14), (–12, 4) R7 (0, 17),

а пари (2, –7) і (1, 4) та(3, –5) і (–3, 2) не належать відношенню R7. 3. Відношення на множині студентів певного факультету:

R8 – відношення є однокурсником,

R9 – відношення молодший за віком від. ◄

Відношення можна задавати у ті самі способи, що й звичайні множини. Наприклад, якщо множина M скінченна, то довільне відношення R на M можна задати списком пар елементів, що перебувають у відношенні R.

Крім того, зручно задавати бінарне відношення R на скінченній множині M = {a1, a2, …, an} за допомогою матриці бінарного відношення. Це квадратна матриця C порядку n, у якій елемент cij, що стоїть на перетині i-го рядка та j-го стовпчика, познача-

ють так: cij = 1, якщо ai R aj, і cij = 0 – в іншому разі. Відношення можна задавати також за допомогою графіків і

діаграм. Графік відношення означають і будують так само, як і графік відповідності. Поняття діаграми (або графа) відношення можна означити аналогічно відповідності. Однак частіше діаг раму (граф) відношення R на скінченній множині

M = {a1, a2, …, an}

означають так. Поставимо у взаємно однозначну відповідність елементам множини M деякі точки площини. Із точки ai до точки aj проводимо напрямлену лінію (стрілку) у вигляді відрізка чи кривої тоді й тільки тоді, коли aiRaj. Зокрема, якщо aiRai, то відповідну стрілку, що веде з ai в ai, називають петлею.

Приклад 2.25. Для множини M = {2, 7, 36, 63, 180} матриці відношень R1, R2, R3 із прикладу 2.24 мають вигляд:

Діаграми (графи) відношень R1, R2, R3 подано на рис. 2.3. ◄

116