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

Відношення порядку — це бінарне відношення на множині, яке є рефлексивним, антисиметричним і транзитивним.

Мотивація

Порядок — поширене поняття, з яким ми маємо справу й у повсякденному житті. Багато речей можна впорядкувати: слова за алфавітом, учнів у школі за зростом, товари за ціною. Усе це описує відношення порядку, яке зазвичай позначаємо символом ≤. Пов'язані символи: <, >, ≥. Їхнє значення очевидне.

Чого ми очікуємо від такого відношення? Уже із самого символу зрозуміло, що у відношенні порядку перебуватимуть і однакові елементи, тож ідеться про те, щоб означити властивості відношення «менше або дорівнює». Таке відношення має бути рефлексивним. Має виконуватися 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{eqnarray} M_{0{,}5}&=&\left\{0{,}5;, 1{,}5;, 2{,}5;, 3{,}5; \ldots\right\}\\ M_{0{,}7}&=&\left\{0{,}7;, 1{,}7;, 2{,}7;, 3{,}7; \ldots\right\}\\ M_{0{,}8}&=&\left\{0{,}8;, 1{,}8;, 2{,}8;, 3{,}8; \ldots\right\} \end{eqnarray}$$

На кожній множині 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 ми б потрапили, лише спустившись донизу, а цього робити не можна.