Материал: discrete_mathematics

Елементи 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

2.Частковим порядком є відношення рівності iM на будь-якій множині M. Цей порядок іноді називають тривіальним.

3.Відношення нестрогого включення є відношенням часткового порядку, а відношення – відношенням строгого порядку на множині β(A) усіх підмножин (булеані) заданої множини A.

4.Задамо відношення ≤ і < на множині Rn кортежів дійсних чисел довжиною n так:

(a1, a2, …, an) ≤ (b1, b2, …, bn)

тоді й тільки тоді, коли a1 ≤ b1, a2 ≤ b2, …, an ≤ bn; аналогічно

(a1, a2, …, an) < (b1, b2, …, bn) тоді й лише тоді, коли

(a1, a2, …, an) ≤ (b1, b2, …, bn)

і принаймні для однієї координати i = 1, 2, …, n виконується ai < bi. Тоді (2, 3.7, 4) < (7, 24, 10), а кортежі (1, 4, –1.7) і (2, 2, 4)

непорівнювані. Аналогічно можна ввести частковий порядок на множинах N n, Z n і Q n.

5. Зафіксуємо строгий порядок розташування символів у довільному скінченному алфавіті A = {a1, a2, …, an}, наприклад, покладемо, що a1 < a2 < … < an. Тоді природним чином можна означити лексикографічний порядок на множині Am усіх слів довжиною m в алфавіті A, а саме: вважатимемо

ai1ai2…aim < aj1aj2…ajm

тоді й тільки тоді, коли ais = ajs для s = 1, 2, …, k – 1 і aik < ajk для певного k, k = 1, 2, …, m.

Лексикографічний порядок можна поширити на множину A* всіх слів у алфавіті A, якщо доповнити алфавіт A додатковим (порожнім) символом p і вважати, що p < ai для всіх i = 1, 2, …, n. При порівнюванні двох слів різної довжини спочатку слово меншої довжини доповнюють праворуч такою кількістю порожніх символів p, щоб воно зрівнялося за довжиною з другим словом, після чого обидва слова порівнюють як слова однакової довжини.

Нехай A = {a, b, c} і a < b < c, тоді

aac < aba, ab < abab, b < cba тощо.

Лексикографічний порядок лежить в основі впорядкування всіх словників, енциклопедій, індексів (предметних або іменних покажчиків), довідників, списків, таблиць тощо.

132

6. У множині N натуральних чисел відношення ділить – це частковий порядок. Маємо 4 ≤ 28, 11 ≤ 132, 5 ≤ 5, 1 ≤ n для будьякого n N. Пари чисел 7 і 22, 13 і 35 непорівнювані. ◄

Нехай M – частково впорядкована множина, A – деяка її непорожня підмножина. Верхньою гранню підмножини A M у множині M називають елемент b M такий, що a ≤ b для всіх a A. Елемент b називають найбільшим елементом множини M, якщо b – верхня грань множини M.

Аналогічно елемент c частково впорядкованої множини M називають нижньою гранню підмножини A M, якщо c ≤ a для будь-якого a A. Елемент c – найменший у множині M, якщо c – нижня грань самої множини M.

Отже, найбільший і найменший елементи, а також верхня й нижня грані (якщо вони існують) порівнювані відповідно зі всіма елементами даної множини M або підмножини A.

Елемент x M називають максимальним у множині M, якщо не існує такого елемента a M, що x < a. Відповідно елемент y M називають мінімальним у множині M, якщо не існує такого елементаa M, що a < y.

Очевидно, що коли в частково впорядкованій множині M існує найбільший елемент, то це єдиний максимальний елемент множини M. Аналогічно найменший елемент множини M – єдиний її мінімальний елемент. Зауважимо також, що частково впорядкована множина M може не мати найбільшого (найменшого) елемента й водночас мати один або кілька максимальних (мінімальних) елементів. У лінійно впорядкованій множині поняття найбільшого й максимального (найменшого й мінімального) елементів збігаються.

Приклад 2.31.

1.У множині Z цілих чисел із традиційним відношенням порядку множина N натуральних чисел має найменший елемент (число 1) і не має найбільшого елемента. Будь-яке від'ємне число, а також 0, є нижніми гранями для N.

2.У довільній множині M із тривіальним порядком iM (від-

ношенням рівності) кожен елемент a M є одночасно максимальним і мінімальним. Найбільшого й найменшого елементів у множині M немає.

133

3.Булеан β(A) множини A з відношенням часткового порядку

містить найменший елемент – порожню множину – і найбільший елемент – саму множину A. У множині D усіх непорожніх

підмножин множини A (тобто в множині β(A)\{ }) немає найменшого елемента, але всі одноелементні множини {a}, a A, є мінімальними елементами множини D.

4. У множині M усіх натуральних дільників числа n N, частково впорядкованій за відношенням "ділить", число 1 – найменший елемент, а n – найбільший. ◄

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

1.Означимо відношення R на множині цілих чисел Z так: mRn тоді й тільки тоді, коли m – n – невід'ємне парне число. Довести, що R – частковий порядок на Z. Чи є R лінійним порядком?

2.Нехай M – довільна множина. Означимо відношення R на

3. Нехай ≤A – частковий порядок на множині A, ≤B – частковий порядок на множині B. Назвемо прямим добутком частково впорядкованих множин A та B множину A × B із заданим на ній

відношенням ≤: (a1, b1) ≤ (a2, b2) a1 ≤A a2 та b1 ≤B b2. Довести, що ≤ – частковий порядок на A × B.

4.Довести чи спростувати таке твердження: якщо ≤ A – лінійний порядок на множині A, а ≤ B – лінійний порядок на множині B, то відношення ≤ , означене в попередній задачі, є лінійним порядком на множині A × B.

5.Нехай M – довільна множина. Означимо відношення R на

множині β(M) × β(M): (A,B) R (C,D) тоді й тільки тоді, коли A C і B D, A, B, C, D β(M). Визначити, чи є R:

(а) відношенням часткового порядку; (б) відношенням лінійного порядку?

6. Нехай R – транзитивне відношення на множині M. Довести, що R є частковим порядком на M тоді й тільки тоді, коли

R ∩ R–1 = iM.

134

7. Довести, що об'єднання R1 R2 відношень часткового порядку R1 і R2 на множині M є частковим порядком на множині M тоді й тільки тоді, коли R1 ° R2 R2 ° R1 R1 R2 і R1 ∩ R2–1 = iM.

8. Нехай ≤ і < – традиційні відношення порядку на множині натуральних чисел N. Довести, що:

9.Довести, що будь-яка непорожня скінченна частково впорядкована множина A містить мінімальний і максимальний елементи.

10.Довести, що скінченна частково впорядкована множина має найменший (найбільший) елемент тоді й тільки тоді, коли вона містить рівно один мінімальний (максимальний) елемент. Чи це так для нескінченних частково впорядкованих множин?

11.Знайти всі множини М, для яких існує повний порядок R на M такий, що R–1 також є повним порядком на М.

2.9.Парадокси теорії множин

Слово парадокс має грецьке походження та перекладається українською як несподіваний, дивний. Це слово вживають щодо висловлення (положення, ідеї), яке суттєво відрізняється від загальноприйнятого традиційного уявлення. Уживання терміна "парадокс" стосовно суперечностей, виявлених різними математиками в теорії множин Г. Кантора, є наївною спробою зменшити їх значення й надати їм характеру логічних курйозів, штучних, неприродних конструкцій. Точніше суть явища передає на-

зва антиномії теорії множин, оскільки термін антиномія є си-

нонімом терміна суперечність. Однак за традицією називатимемо сформульовані нижче положення парадоксами.

Парадокс Б. Рассела. Для будь-якої множини M коректним є питання, чи належить множина M собі як окремий елемент, тобто чи є множина M елементом самої себе, чи ні. Наприклад, множина всіх множин є множиною й тому належить сама собі, а множина всіх будинків у місті не є будинком, множина студентів в аудиторії не є студентом.

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

135