Частково впорядкована множина (poset — ) — множина з заданим частковим порядком (антисиметричним передпорядком), тобто з бінарним відношенням, що є транзитивним, рефлексивним та антисиметричним. Позначається
Скінченні частково впорядковані множини графічно зображають діаграмами Гассе.
Визначення Частковим порядком, на множині називається бінарне відношення , визначене деякою множиною ), яке задовольняє такі умови: Транзитивність: Рефлексивність: Антисиметричність:
Терміни та позначення Відношення часткового порядку зазвичай позначають символом , за аналогією з відношенням «менше або дорівнює» на множині дійсних чисел. При цьому, якщо , то кажуть, що елемент не перевершує , або, що підпорядкований .
Якщо і , то пишуть , і кажуть, що менше , або, що строго підпорядковане .
Іноді, щоб відрізнити довільний порядок на деякій множині від відомого відношення «менше або дорівнює» на множині дійсних чисел, замість і використовують спеціальні символи і відповідно.
Строгий і нестрогий порядок Відношення, що задовольняє умовам рефлексивності, транзитивності і антисиметричності, також називають нестрогим, або рефлексивним порядком. Якщо умову рефлексивності замінити на умову антирефлексивності (тоді властивості антисиметричності зміняться на асиметричність): , то отримаємо визначення строгого, або антирефлексивного порядку.
Пов'язані визначення
Незрівняні елементи Якщо і — дійсні числа, то має місце тільки одне з таких співвідношень :
У разі, якщо і — елементи довільної частково впорядкованої множини, то існує четверта логічна можливість: не виконується жодне зі вказаних трьох співвідношень. У цьому випадку елементи і називаються непорівнюваними. Наприклад, якщо — множина дійснозначних функцій на відрізку , то елементи і будуть непорівнювані. Можливість існування непорівнюваних елементів пояснює сенс терміну «частково впорядкована множина».
Мінімальні/максимальні та найменші/найбільші елементи Максимальні та мінімальні елементи
Через те, що в частково впорядкованій множині можуть бути пари непорівнюваних елементів, вводяться два різні визначення: мінімальний елемент і найменший елемент.
Елемент називається мінімальним (), якщо не існує елемента . Іншими словами — мінімальний елемент, якщо для будь-якого елемента або , або , або і непорівнювані.
Елемент називається найменшим (), якщо для будь-якого елементу має місце нерівність . Очевидно, всякий найменший елемент є також мінімальним, але зворотне в загальному випадку є невірним: мінімальний елемент може і не бути найменшим, якщо існують елементи , непорівнювані з .
Очевидно, що якщо в множині існує найменший елемент, то він єдиний. А ось мінімальних елементів може бути декілька. Як приклад, розглянемо множину натуральних чисел без одиниці, впорядковану по відношенню подільності . Тут мінімальними елементами будуть прості числа, а ось найменшого елементу не існує.
Аналогічно вводяться поняття максимального () і найбільшого () елементів.
Верхні та нижні грані
Нехай — підмножина частково впорядкованої великої множини . Елемент називається верхньою гранню () , якщо будь-який елемент не перевершує . Аналогічно вводиться поняття нижньої грані () множини .
Будь-який елемент, більший, ніж деяка верхня грань , також буде верхньою гранню . А будь-який елемент, менший, ніж деяка нижня грань , також буде нижньою гранню . Ці міркування ведуть до введення понять найменшої верхньої грані () і найбільшої нижньої грані ().
Верхня і нижня множина
Для елементу частково впорядкованої множини верхньою множиною () називається множина усіх елементів, яким передує ().
Двоїстим чином визначається нижня множина (), як множина усіх елементів, які передують заданому : .
Спеціальні типи частково впорядкованих множин
Лінійно впорядковані множини
Нехай — частково впорядкована множина. Якщо в будь-які два елементи порівнянні, то множина називається лінійно впорядкованою (). Лінійно впорядковану множину також називають абсолютно впорядкованою (), або просто, впорядкованою множиною. Таким чином, у лінійно впорядкованій множині для будь-яких двох елементів і має місце одне і тільки одне зі співвідношень: або , або , або .
Також всяку лінійно впорядковану підмножину частково впорядкованої множини називають ланцюгом (), тобто ланцюг у частково впорядкованій множині — така її підмножина, в якій будь-які два елементи порівнювані.
З наведених вище прикладів частково впорядкованих множин тільки множина дійсних чисел є лінійно впорядкованою. Множина дійснозначних функцій на відрізку (за умови ), булеан (при ), натуральні числа з відношенням подільності — не є лінійно впорядкованими.
Цілком впорядковані множини
Лінійно впорядкована множина називається цілком впорядкованою (), якщо кожна її непорожня підмножина має найменший елемент. Такий порядок на множині називається повним порядком (), у контексті, де його неможливо сплутати з повним порядком у сенсі повних частково впорядкованих множин, ().
Класичний приклад цілком впорядкованої множини — множина натуральних чисел . Твердження про те, що будь-яка непорожня підмножина містить найменший елемент, рівносильне принципу математичної індукції. Як приклад лінійно впорядкованої, але не цілком впорядкованої множини можна навести множину невід'ємних чисел, впорядковану природним чином . Дійсно, її підмножина не має найменшого елемента.
Цілком впорядковані множини грають виключно важливу роль у загальній теорії множин.
Повна частково впорядкована множина Повна частково впорядкована множина () — частково впорядкована множина, в якої є дно — єдиний елемент, який передує будь-якому іншому елементу, і в кожної спрямованої підмножини якої є точна верхня межа. Повні частково впорядковані множини застосовують у λ-численні та інформатиці, зокрема, на них вводиться , на основі якої будується несуперечлива модель λ-числення і денотаційна семантика обчислень. Спеціальним випадком повної частково впорядкованої множини є повна ґратка — якщо будь-яка підмножина, не обов'язково спрямована, має точну верхню грань, то вона виявляється повною ґраткою.
Впорядкована множина тоді і тільки тоді є повною частково впорядкованою, коли будь-яка функція , монотонна відносно порядку має хоча б одну нерухому точку: .
Будь-яку множину можна перетворити на повну частково впорядковану, виділивши дно і визначивши порядок як і для всіх елементів множини .
Теореми про частково впорядковані множини До числа фундаментальних теорем про частково впорядковані множини відносяться принцип максимуму Гаусдорфа і лема Куратовського — Цорна, які є еквівалентними аксіомі вибору.
Приклади Множина дійсних чисел із звичайним відношенням порядку є лінійно впорядкованою множиною.
Натуральні числа, цілі числа, раціональні числа, ірраціональні числа тощо всі є підмножинами дійсних чисел, тому утворюють лінійно впорядковані множини зі звичайним відношенням порядку.
На множині натуральних чисел визначимо відношення порядку за подільністю, тобто тоді і тільки тоді, коли є дільником Таким чином ми отримаємо частково впорядковану множину. Наведені вище аксіоми справджуються тому, що будь-яке натуральне число є своїм дільником, два числа, які є дільниками одне одного, збігаються, і, нарешті, якщо є дільником а є дільником то є дільником Ця множина не є лінійно впорядкованою, наприклад, жодне з чисел 2,3 не є дільником іншого. При цьому 1 є дільником будь-якого натурального числа, тому воно є найменшим елементом цієї частково упорядкованої множини.
Ланцюг з елементів — це лінійно впорядкована множина з елементів. У комбінаториці ланцюг, який складається з позначається або
Будь-яка множина перетворюється на частково впорядковану множину, якщо визначити на ній таке відношення порядку: У цьому разі можна порівняти два елементи , лише коли вони збігаються. Така частково впорядкована множина називається антиланцюгом.
Нехай — довільна множина, а — множина всіх підмножин (булеан). Визначимо на частковий порядок за включенням, тобто означає, що де — дві підмножини Тоді перетворюється на частково впорядковану множину з найменшим елементом та найбільшим елементом
Розглянемо множину всіх -елементних послідовностей натуральних чисел з лексикографічним порядком. А саме,
якщо або або або інакше кажучи, якщо в послідовності перший ненульовий елемент — додатний. У такий спосіб перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у комп'ютерній алгебрі (див. ).
Див. також
Передпорядок Лінійно впорядкована множина Цілком впорядкована множина Найбільший та найменший елемент Максимальні та мінімальні елементи Верхня та нижня межа Послідовно-паралельний частковий порядок Щільний порядок
Примітки
Джерела