Материал: discrete_mathematics

Рефлексивність композиції легко вивести із рефлексивності

R1 і R2: для довільного елемента a M (a, a) R1 і (a, a) R2, отже, (a, a) R1°R2. Для доведення симетричності розглянемо елемент

(a, b) R1°R2, тоді послідовно матимемо:

(a, b) R1 R2 ((a, b) R1 (a, b) R2) ((b, a) R1(b, a) R2) (b, a) R1 R2 (b, a) R1°R2.

(b, c) R1 R2. Далі див. доведення достатності вприкл. 2.26 (6). ◄ Сукупність множин {Bi | i I} називають розбиттям множини

A, якщо

Bi = A та Bi ∩ Bj = для i ≠ j.

i I

Множини Bi, i I, є підмножинами множини A. Їх називають

класами, суміжними класами, блоками чи елементами розбит-

тя. Очевидно, що кожний елемент a A належить одній і тільки одній множині Bi, i I.

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

SaR ={x | x M і a R x},

що складається зі всіх елементів множини M, еквівалентних елементу a. Потім візьмемо другий елемент b M такий, що

b SaR і утворимо множину

SbR ={ x | x M і b R x }

з елементів, еквівалентних b і т. д. Таким чином одержимо сукупність множин (можливо, нескінченну)

{SaR , SbR ,...}.

Побудовану сукупність {SiR | i I} називають фактормножиною

множини M за еквівалентністю R і позначають M/R.

Приклад 2.29.

1. Фактормножина за відношенням рівності E для будь-якої множини M має вигляд M/E = {{a} | a M }.

127

2. Фактормножина для відношення конгруентні за модулем 3 на множині N натуральних чисел складається із трьох класів

{3k | k N}, {3k – 1| k N} і {3k – 2 | k N}. ◄

Доведемо, що фактормножина M/R є розбиттям множини M. Оскільки за побудовою кожний елемент множини M належить

симетричності та транзитивності відношення R виводимо aRb і bRa. Із співвідношення aRb і правила побудови множини SaR маємо SaR SbR , а з bRa та правила побудови множини SbR одержу-

ємо протилежне включення SbR SaR . Отже, SaR = SbR , і з одер-

жаної суперечності випливає справедливість сформульованого твердження.

Очевидно, що будь-які два елементи з одного класу SiR еквівалентні, а будь-які два елементи із різних класів фактормножини M/R нееквівалентні. Класи SiR називають класами еквіва лентності за відношенням R. Клас еквівалентності, що містить елемент a M, часто позначають через [a]R.

Потужність |M/R| фактормножини M/R називають індексом розбиття, або індексом відношення еквівалентності R.

З іншого боку, припустимо, що для множини M задано деяке розбиття {Si | i I}. Побудуємо відношення T на множині M за таким правилом: a T b для a, b M тоді й тільки тоді, коли елементи a та b належать одному класу даного розбиття. Неважко переконатись, що відношення T рефлексивне, симетричне і транзитивне, тобто є еквівалентністю на множині M.

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

128

Нехай R – відношення еквівалентності на множині M. Відображення множини M на фактормножину M/R, що кожному елементу a M ставить у відповідність клас еквівалентності [a]R, якому належить елемент a, називають канонічним (природним) відображенням множини M на фактормножину M/R.

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

1. На множині N × N означимо відношення Q: ((a, b), (c, d)) Q a d = b c.

Довести, що Q – відношення еквівалентності на множині N × N.

2.Нехай M = N × N. Означимо на множині M відношення Q: (a, b) Q (c, d) тоді й тільки тоді, коли a + b = c + d. Довести, що Q

єеквівалентністю на M. Виписати всі елементи класів еквівалент-

ності [(1, 1)], [(2, 2)], [(4, 3)], [(1, 23)] і [(6, 8)] за відношенням R.

3.На множині N натуральних чисел означимо відношення R: mRn тоді й тільки тоді, коли m/n = 2k для деякого цілого k.

(а) Довести, що R – відношення еквівалентності на N.

(б) Скільки різних класів еквівалентності є серед [1]R, [2]R,

[3]R і [4]R?

(в) Скільки різних класів еквівалентності є серед [6]R, [7]R, [12]R, [24]R, [28]R, [42]R і [48]R?

4. Нехай у множині M зафіксовано деяку підмножину K M.

Означимо відношення R на β(M): A R B тоді й тільки тоді, коли

A ∩ K = B ∩ K, A, Bβ(M).

(а) Довести, що R – відношення еквівалентності на β(M).

(б) Для M = {1, 2, 3} і K = {1, 2} знайти класи еквівалентності

(д) Визначити кількість класів еквівалентності та кількість підмножин множини M у кожному класі еквівалентності за відношенням R, якщо | M | = n і | K | = m.

129

5.Довести, що перетин будь-якої сукупності відношень еквівалентності на множині M є еквівалентністю на M.

6.Навести приклад двох еквівалентностей R1 і R2 на множині

M = {1, 2, 3} таких, що R1 R2 неє еквівалентністю на множиніM.

7.Навести приклад двох еквівалентностей R1 і R2 на множині M = {1, 2, 3} таких, що R1°R2 не є еквівалентністю на M.

8.Побудувати найменше відношення еквівалентності Q на множині M = {1, 2, 3, 4}, що включає задане відношення R:

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

9.Навести приклад відношення R на множині M = {1, 2, 3}, для якого виконується R+ = R і яке не є еквівалентністю.

10.Довести, що коли R – рефлексивне і транзитивне відно-

шення на множині M, тоді R ∩ R–1 є відношенням еквівалентності на множиніM.

11. Довести, що для довільного відношення еквівалентності R три наведені твердження рівносильні:

1) (x, y) R; 2) [x]R ∩ [y]R ≠ ; 3) [x]R = [y]R.

12. Побудувати всі можливі розбиття множини: (а) M = {a, b, c}; (б) M = { , { }}.

13. Нехай M – скінченна множина. Яке відношення еквівалентності на M має:

(а) найбільший індекс; (б) найменший індекс?

14. Нехай R – відношення еквівалентності на скінченній множині M (|M| = n) і |R| = k. Довести, що k – n – завжди парне число.

2.8. Відношення порядку

Відношення R на множині M називають відношенням част кового (нестрогого) порядку, якщо воно рефлексивне, антисиметричне і транзитивне, тобто:

Множину M, на якій задано деякий частковий порядок, нази-

вають частково впорядкованою.

130

Елементи a, b M назвемо порівнюваними за відношенням R, якщо виконується aRb або bRa.

Частково впорядковану множину M, у якій будь-які два елементи порівнювані між собою, називають лінійно впорядкованою множиною, або ланцюгом. Відповідне відношення R, задане на лінійно впорядкованій множині, називають лінійним (доскона лим) порядком. Отже, відношення R на множині M називають відношенням лінійного порядку, якщо воно рефлексивне, антисиметричне, транзитивне й для будь-якої пари елементів a, b M виконується aRb або bRa.

Для позначення відношень порядку використовуватимемо знаки ≤ і ≥, які повторюють звичайні математичні знаки нерівностей, тобто для відношення порядку R замість aRb записуватимемо a ≤ b або b ≥ a та читатимо відповідно a менше або дорівнює b або b більше або дорівнює a. Очевидно, що ≤ – обернене відношення до ≥.

За кожним відношенням часткового порядку ≤ на довільній множині M можна побудувати інше відношення < на M, вважаючи, що a < b тоді й лише тоді, коли a ≤ b і a ≠ b. Це відношення називають відношенням строгого порядку на множині M. Зро-

зуміло, що відношення строгого порядку антирефлексивне, транзитивне, а також задовольняє умову сильної антисиметричності (асиметричності), тобто для жодної пари a, b M не може одночасно виконуватись a < b і b < a.

З іншого боку, за довільним відношенням строгого порядку < на множині M однозначно можна побудувати відповідне відношення часткового (нестрогого) порядку ≤, поклавши a ≤ b тоді й тільки тоді, коли a < b або a = b, a, b M. З огляду на такий простий зв'язок між відношеннями часткового (нестрогого) і строгого порядку можна обмежитися вивченням лише одного з них, наприклад ≤.

Приклад 2.30.

1. Традиційні відношення ≤ і < (≥ і >) – це відношення відповідно часткового й строгого порядку на множинах чисел N, Z і R. Більш того, множини N, Z і R, а також будь-які їхні підмножини лінійно впорядковані за відношеннями ≤ або ≥.

131