Лема 1. У будь-якій частково впорядкованій множині може існувати не більш однієї верхньої і не більш однієї нижньої універсальних границь.

Доведення. Дійсно, нехай існує два найменших елементи О і О*. Тоді справедливо О £ О* і О* £ О. Звідси по властивості антисиметричності О = О*. Аналогічно доводиться і випадок для I і I*. Лема доведена.

Існують частково впорядковані множини без універсальних границь, наприклад мно­жина Z не має ні нижньої, ні верхньої універсальної границі, а множина N має тільки нижню універсальну границю.

Існують і скінченні частково впорядковані множини без універсальних границь, на­при­клад множина R={a,b,c,d,e,f} з визначеним на ній частковим порядком a₈ = {(a,a), (b,b), (c,c), (a,b), (b,c), (a,c), (d,d), (e,e), (f,f), (d,e), (e,f), (d,f)}. Претенденти на нижні і верхні універсальні границі – елементи a, d і c, f означенню в дійсності не задовольняють.

Визначення. Якщо в частково впорядкованій множині виконується умова, що для будь-яких х,у має місце х £ у або у £ х, то вона називається лінійно впорядкованою.

З відношенням часткового порядку £ пов'язаний ряд інших відношень:

§ строгого порядку х < y, що означає, що х £ у, але х ¹ у (ясно, що це іррефлексивне, асиметричне і транзитивне відношення);

§ незрівнянності х у, що означає, що ні х £ у, ні у £ х.

Тоді для кожної пари (х,у) Î R, де R – частково упорядкована множина, справедливо: або х = у, або х < у, або х > у, або х у.

Чому ми приділяємо багато часу відношенням порядку? Це пов'язано з тим, що в ком­п'ю­теризованих системах у сфері керування реалізуються процедури застосування рішень на основі аналізу оцінок можливих рішень, причому множина оцінок звичайно становить собою частково упорядковану множину. Природно, розроблювач пропонує процедуру, що за без­печує вибір екстремальної оцінки. У такий спосіб ми переходимо до необхідності введення на упорядкованих множинах границь. З універсальними границями ми вже знайомі, але їх недостатньо для аналізу всіх можливих ситуацій.

Елемент m частково упорядкованої множини R називається мінімальним (макси­маль­ним), якщо не існує такого r_i Î R, що r_i < m (r_i > m).

Очевидно, якщо частково упорядкована множина має універсальну границю О (чи I), то вона є мінімальним (максимальним) елементом.

Легко привести приклад частково упорядкованої множини, що має декілька міні­маль­них і максимальних елементів: на множини R={a, b, c, d, e, f} розглянемо вже знайомий нам частковий порядок a₈ = {(a,a), (b,b), (c,c), (d,d), (e,e), (f,f), (a,b), (b,c), (a,c), (d,e), (e,f), (d,f)}. Тоді a і d – мінімальні елементи, а c і f - максимальні елементи.

Крім того, в частково упорядкованій множини можна погодити порядок з нумерацією.

Лема 2. Елементи скінченної частково впорядкованої множини R={r_1,...,r_n} завжди можна перенумерувати таким чином: R={х₁ ...х_n }, що з x_i < x_j буде випливати i < j.

Доведення. Початкову нумерацію виконаємо яким завгодно шляхом. Потім проведемо послідовно ряд перестановок: елементи в отриманій нумерації змінюємо місцями, якщо у від­по­відній парі графіку відношення £ вони стоять у зворотньому порядку. Очевидно, число таких перестановок рівне чи менше числа пар. За побудовою нумерації для будь-якої пари x_i < x_j елемент x_i отримає менший номер. Лема доведена.

Для аналізу мінімальних чи максимальних елементів по приналеж­ності до частково впорядкованої множини R по відношенню до її підмножини S також вводять нові поняття.

Визначення. Назвемо елемент а Î R нижньою (верхньою) границею підмножини S, якщо а £ x (a ³ x) для всіх хÎS.

Визначення. Назвемо елемент b Î R нижньою гранню підмножини S, якщо:

1) b – нижня границя підмножини S;

2) b ³ b¢, де b¢ - будь-яка нижня границя підмножини S.

Визначення. Назвемо елемент c Î R верхньою гранню підмножини S, якщо:

1) c – верхня границя множини S;

2) c £ c¢, де c¢ - будь-яка верхня границя множини S.

Далі будемо писати b = inf S, c = sup S (infimum – наголос на другому i, supremum – наголос на e). Іноді використовуються терміни "точна нижня границя" і "точна верхня границя", відповідно.

Аналогічно тому як було доведено єдиність універсальних границь, можна довести єдиність верхньої і нижньої граней.

Тепер, ознайомившись з низкою об’єктів і методів дискретної матема­тики, повернемося до підтверджения проголошеної вище тези про те, що дискретна мате­ма­тика не набір розріз­нених ідей, а сукупність пов’язаних між собою концеп­ту­альних понять, які використовуються в багатьох несхожих одна на іншу ситуаціях. Ми продемонструємо на прикладі ­можливість установлення і дослідження основного принципу, який фактично єдиним чином розв’язує проблеми для всіх згаданих різних випадків.

Приклад. На основі порядку, визначеного на множині N, ми можемо формально отри­мати звичайні відношення порядку на множинах чисел Z, Q і R. Спочатку розглянемо Z. Щоб полегшити міркування, розіб’ємо Z таким чином: Z = NÈ{0}ÈA.

Тому A = {-x: x Î N}. Визначимо відношення, яке будемо називати повним відношенням порядку на Z, розгляданням всіх можливих елементів xі у із розбиття {NÈ{0}ÈA}.

Якщо x = у, то x£ уі у£ x. Нехай x ¹ у. Тоді:

а) якщо x, уÎ N, то порядок в Z той же, що й в N;

б) якщо x, уÎ А,то x £ у тоді і тільки тоді, коли - у £ -xв N (тобто - 5 £ -4, тому що 4 £ 5);

в) якщо x = 0 і уÎ N, то x £ y;

г) якщо x Î А і у = 0, то x £ y;

д) якщо x Î А і yÎN,то x £ y або в супротивному випадку у£ x.

На основі порядку на Z і звичайних арифметичних операцій з цілими числами ми можемо визначити поря­док на Q:

a/b£ c/dтоді і тільки тоді, коли а×d < b×с.

Легко пересвідчитись, що це твердження виконується. Насамкінець, визначимо відношення порядку на множині дійсних чисел R. Розглянемо десяткові зображе­ння двох дійсних додатних чисел:

D =… 0d_n…d₂d₁d₀d₁d₂…,

C = …0c_m…c₂c₁c₀g₁g₂….

Якщо d_i = c_i і d_i = g_i для всіх i, то D = C і, отже, D £ C і C£ D. В супротивному випадку:

а) якщо d_n ¹ 0, c_m ¹ 0 і n ¹ m, то D £ C, якщо n < m, і C£ D, якщо m < n;

б) якщо n = m і d_i ¹ c_i,але d_j = c_j для всіх j таких, що i < j £ n, то із d_i < c_i робимо висновок, що D £ C, і, навпаки, якщо c_i < d_i, то C£ D;

в) якщо n = m і d_i = c_i для всіх i, але d_k ¹ g_k для деяких kі d_j = g_j для всіх j таких, що 0 < j £ k, тоді C£ D, якщо g_k < d_k, і D £ C, якщо d_k < g_k.

В цьому легко пересвідчитись. Від’ємні числа можуть бути досліджені так же, як в Z.

Насамкінець, зазначимо, що використання природного порядку на R визначає нові множини, що називаються інтервалами:

[а, b] = {x: x Î R, а £ x £ b} - замкнений інтервал (відрізок) від а до b;

]а, b[ = {x: x Î R, а < x < b} - відкритий інтервал від а до b.

Тут числа а і b називаються кінцевими точками. Замкнений інтервал включає в себе кінцеві точки, а відкритый ні. Зручно також визначити напіввідкриті інтервали:

[a, b[ = {x: xÎ R, a £ x < b},

]a, b] = {x: xÎR, a < x £ b},

Для зручності будемо використовувати такі позна­чення:

] - ¥, а] = {x: x £ а},

]-¥, а[ = {x: x < а},

[а, ¥[ = {x: а £ x},

]a,¥[ = {x: a < x},

]-¥,¥[ = R.

Інтервали і множини чисел ми будемо використовувати час від часу в нашому курсі.

2. Відношення еквівалентності. Ще одним важливим класом бінарних відношень є відношення еквівалентності.

Визначення. Бінарне відношення на множині R, що має властивості рефлексивності, симетричності і транзитивності, назвемо відношенням еквівалентності і будемо позначати E або =.

Приклад відношення еквівалентності – відношення рівності.

З поняттям відношення еквівалентності тісно пов’язане поняття розбиття, яке роз­гля­нене в попередній лекції. Розбиття часто застосовують при створенні комп’ютеризованих систем, наприклад при створенні класифікаторів.