Релация на наредба

Релацията на наредба е бинарна релация върху множество, която е рефлексивна, антисиметрична и транзитивна.

Мотивация

Наредбата е обичайно понятие, с което работим и в обикновения живот. Много неща можем да наредим по някакъв начин – думите по азбучен ред, учениците в училище по ръст, стоките по цена. Всичко това описва релацията на наредба, която обикновено означаваме със символа ≤. Свързаните символи са: <, >, ≥. Значението им е очевидно.

Какво бихме очаквали от такава релация? Още от символа е ясно, че в релацията на наредба ще има елементи, които са еднакви – целта ни е да определим свойствата на релацията „по-малко или равно“. Такава релация трябва да е рефлексивна. Трябва да е изпълнено a ≤ a.

Какво още? Със сигурност няма да е изпълнена симетричност – ако имаме наредба по цена, то ако колата е по-евтина от хляба, със сигурност хлябът няма да е и по-евтин от колата. Какво бихме очаквали в общия случай, ако се случи a ≤ b и b ≤ a? Би ли имало смисъл понякога? Да, ако a = b. Единственият случай, когато редът на елементите, поставени в релацията, няма значение, е когато тези елементи са еднакви – наредбата е антисиметрична.

И накрая, ако знаем, че колата е по-скъпа от хляба, а самолетът е още по-скъп от колата, очакваме самолетът със сигурност да е по-скъп от хляба. Това описва транзитивността.

Частична наредба

Онова, което определихме преди малко, всъщност е само частична наредба, не е пълна. Защо не е пълна? Нека опитаме да определим наредба върху множества. Как бихме могли да сравним две множества?

Казваме, че множеството A е по-малко или равно на множеството B, ако A ⊆ B, тоест ако A е подмножество на B. Това е смислено, защото ако имаме A = {1, 2} и B = {1, 2, 3}, за A бихме могли да кажем, че е по-малко – B съдържа същите елементи като A и освен това съдържа и числото три. Така например ще е изпълнено:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

Затруднението е, когато искаме да сравним тези множества: A = {a, b} и B = {a, c}. Кое от тях е по-малко или по-голямо? Затруднението е, че макар двете множества да съдържат елемента a, вторият им елемент е различен. Нито едно от множествата не е подмножество на другото, така че не е изпълнено нито A ≤ B, нито B ≤ A. Такива множества са несравними чрез нашата наредба.

Затова определяме напълно наредено множество или още верига, ако всеки два елемента от множеството са сравними. Такива множества са например числовите множества с класическата наредба. За всеки две реални числа a, b можеш да решиш дали a ≤ b, или b ≤ a.

Примери от живота

Пример, когато си струва да не сравняваме, би могъл да бъде наредбата по красота, релацията < би означавала „да бъдеш по-грозен“. Може би трябва да я определим по-скоро обратно, > като „да бъдеш по-хубав“, за да сме по-коректни :-). Вероятно има смисъл да сравняваме помежду си две жени, например „Мария“ < „Елена“ в смисъл, че Елена е по-хубава от Мария. Или двама мъже: „Георги“ < „Николай“ в смисъл, че Николай е по-хубав от Георги.

Проблемът е, че едва ли можем да сравняваме красотата на мъж и на жена. По-хубава ли е Елена, или Николай? По-добре да не го разглеждаме…

Ако в последния пример се ограничим например само до жените, можем да кажем, че имаме напълно наредено множество, защото можем да сравним красотата на всички жени.

Минимален и максимален елемент, най-малък и най-голям елемент

Ако имаме наредено множество M, елементът min ∈ M наричаме минимален, ако не съществува x ∈ M, за което x < min. Тоест не можем да намерим елемент, който да е по-малък от елемента min.

Елементът max ∈ M наричаме максимален, ако не съществува x ∈ M, за което x > max. Тоест не можем да намерим елемент, който да е по-голям.

Предишните две понятия се различават от понятията най-малък и най-голям.

Елементът a ∈ M наричаме най-малък, ако за всички x ∈ M е изпълнено a ≤ x. Тоест най-малкият елемент a е по-малък или равен на всички останали елементи на множеството M.

Елементът b ∈ M наричаме най-голям, ако за всички x ∈ M е изпълнено b ≥ x. Най-големият елемент b е по-голям или равен на всички останали елементи на множеството M.

Каква е разликата между най-голям и максимален елемент? Максимални елементи може да има няколко, защото множеството не е непременно напълно наредено. Ако се върнем към примера със сравняването на хора по външност, можем да кажем, че Елена е най-хубавата жена, а Николай е най-хубавият мъж. Но тези две личности вече не можем да сравним помежду си, не знаем дали е по-хубава Елена, или Николай.

И двата елемента са максимални. Не можем да намерим човек, който да е по-хубав от Николай – Николай е по-хубав от всички останали мъже, а с жените не можем да го сравняваме. Подобно е и за Елена – тя е по-хубава от всички жени, а с мъжете не можем да я сравняваме.

Но нито един от тях не е най-голям, в този смисъл най-хубав. Защото, за да е Николай най-хубав/най-голям, трябва да е по-хубав от всички хора, включително от всички жени. Но вече казахме, че с жените не можем да го сравняваме, затова не може да е най-хубавият човек, а е само, в терминологията на теорията на наредбите, максимален.

Вероятно лесно се вижда, че ако множеството има най-голям елемент, този елемент е и максимален. Ако елементът a е по-голям от всички останали елементи на множеството (определение на най-голям елемент), със сигурност не можем да намерим елемент, който да е още по-голям (определение на максимален елемент).

Пример за множество, което има най-голям и най-малък елемент, е затвореният интервал [0; 1]. Ако изберем същия интервал, но отворен, той нямаше да има нито най-голям, нито най-малък елемент: (0; 1).

Ако искаме безброй много минимални елементи, бихме могли да определим наредбата R така. Първо определяме помощни множества M_x. Множествата ще имат този вид: за всяко x от интервала (0; 1) определяме множеството M_x = {y | y = x + n}, където n е цяло неотрицателно число. Така получаваме например такива множества:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Във всяко множество M_x определяме класическата наредба, която означаваме с R_x. Накрая просто обединяваме тези наредби: R = ∪ R_x. В тази наредба можем да сравняваме винаги само в рамките на първоначалните вериги. Така можем да установим дали 0,5 ≤ 2,5, но вече не можем да установим дали 0,5 ≤ 2,7, защото тези числа не са в едно и също множество M_x и затова връзката им не е определена.

В тази релация на наредба е изпълнено, че всеки елемент от интервала (0; 1) е минимален елемент.

Диаграми на Хасе

Наредените множества можем да изобразим с помощта на диаграма на Хасе. Това е граф, в който върховете представят елементите на множеството, а ребро между върховете (a; b) ни казва, че a < b и не съществува c, за което a < c < b. Тоест между елементите a и b няма друг елемент. При това върхът a трябва да е в графа по-ниско от върха b. Пример за диаграма на Хасе:

Тази диаграма на Хасе изобразява наредено множество {A, B, C, D, E, F}. При това е изпълнено: A < B, B < E, освен това разбира се е изпълнено A < E, но между тези върхове няма ребро, защото съществува връх B, за който A < B < E. Елементите E и D са несравними, защото нито един не е над другия, нито под другия.

Макар диаграмите на Хасе обикновено да се чертаят така подредено, това не е задължително. Предишната диаграма на Хасе може да изглежда и така:

Друг пример може да е множеството A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Това са естествените делители на числото 60. Наредбата по делимост може да се изобрази така:

Наредбата по делимост означава, че (a; b) ∈ R тогава и само тогава, когато a дели b. От диаграмата можем да забележим, че над всяко число има числата, които то дели. Например над числото 6 са числата 12, 30 и 60. Над числото 4 са числата 12, 20 и 60. И т.н. Обратно, над числото 3 няма числото 10, защото три не дели десет – внимание, числото 10 визуално е над числото 3, но към него не води „отдолу нагоре“ никаква линия. Ако от числото 3 се движим само нагоре, можем да стигнем до числата 15 и 6 и от тях до числото 30. До числото 10 бихме стигнали само ако слезем надолу, което не е позволено.