Частково впорядкована множина
Частково впорядкована множина (poset — англ. partially ordered set) — це множина з заданим частковим порядком (антисиметричним передпорядком), тобто з бінарним відношенням, що є транзитивним, рефлексивним та антисиметричним. Позначається
Скінченні частково впорядковані множини графічно зображаються діаграмами Гассе.
Частковим порядком, на множині називається бінарне відношення , визначене деякою множиною ), яке задовольняє наступні умови[1]:
Відношення часткового порядку зазвичай позначають символом , за аналогією з відношенням «менше або дорівнює» на множині дійсних чисел. При цьому, якщо , то кажуть, що елемент не перевершує , або, що підпорядкований .
Якщо і , то пишуть , і кажуть, що менше , або, що строго підпорядковане .
Іноді, щоб відрізнити довільний порядок на деякій множині від відомого відношення «менше або дорівнює» на множині дійсних чисел, замість і використовують спеціальні символи і відповідно.
Відношення, що задовольняє умовам рефлексивності, транзитивності і антисиметричності, також називають нестрогим, або рефлексивним порядком. Якщо умову рефлексивності замінити на умову антирефлексивності (тоді властивості антисиметричності зміняться на асиметричність):
- ,
то отримаємо визначення строгого, або антирефлексивного порядку.
Якщо і — дійсні числа, то має місце тільки одне з наступних співвідношень :
У разі, якщо і — елементи довільної частково впорядкованої множини, то існує четверта логічна можливість: не виконується жодне з вказаних трьох співвідношень. В цьому випадку елементи і називаються непорівнюваними. Наприклад, якщо — множина дійснозначних функцій на відрізку , то елементи і будуть непорівнювані. Можливість існування непорівнюваних елементів пояснює сенс терміну «частково впорядкована множина».
Максимальні та мінімальні елементи
Через те, що в частково впорядкованій множині можуть бути пари непорівнюваних елементів, вводяться два різні визначення: мінімальний елемент і найменший елемент.
Елемент називається мінімальним (англ. minimal element), якщо не існує елемента . Іншими словами — мінімальний елемент, якщо для будь-якого елемента або , або , або і непорівнювані.
Елемент називається найменшим ((англ. least element, lower bound (opp. upper bound)), якщо для будь-якого елементу має місце нерівність . Очевидно, всякий найменший елемент є також мінімальним, але зворотне в загальному випадку є невірним: мінімальний елемент може і не бути найменшим, якщо існують елементи , непорівнювані з .
Очевидно, що якщо в множині існує найменший елемент, то він єдиний. А ось мінімальних елементів може бути декілька. Як приклад, розглянемо множину натуральних чисел без одиниці, впорядковану по відношенню подільності . Тут мінімальними елементами будуть прості числа, а ось найменшого елементу не існує.
Аналогічно вводяться поняття максимального (англ. maximal element) і найбільшого (англ. greatest element) елементів.
Нехай — підмножина частково впорядкованої великої множини . Елемент називається верхньою гранню (англ. upper bound) , якщо будь-який елемент не перевершує . Аналогічно вводиться поняття нижньої грані (англ. lower bound) множини .
Будь-який елемент, більший, ніж деяка верхня грань , також буде верхньою гранню . А будь-який елемент, менший, ніж деяка нижня грань , також буде нижньою гранню . Ці міркування ведуть до введення понять найменшої верхньої грані (англ. least upper bound) і найбільшої нижньої грані (англ. greatest lower bound).
Для елементу частково впорядкованої множини верхньою множиною (англ. upper set, upset) називається множина усіх елементів, яким передує ().
Двоїстим чином визначається нижня множина (англ. down set, lower set), як множина усіх елементів, передуючих заданому : .
Нехай — частково впорядкована множина. Якщо в будь-які два елементи порівнянні, то множина називається лінійно впорядкованою (англ. linearly ordered set). Лінійно впорядковану множину також називають абсолютно впорядкованою (англ. totally ordered set), або просто, впорядкованою множиною[2]. Таким чином, в лінійно впорядкованій множині для будь-яких двох елементів і має місце одне і тільки одне зі співвідношень: або , або , або .
Також всяку лінійно впорядковану підмножину частково впорядкованої множини називають ланцюгом (англ. chain), тобто ланцюг в частково впорядкованій множині — така його підмножина, в якій будь-які два елементи порівнювані.
З наведених вище прикладів частково впорядкованих множин тільки множина дійсних чисел є лінійно впорядкованою. Множина дійснозначних функцій на відрізку (за умови ), булеан (при ), натуральні числа з відношенням подільності — не є лінійно впорядкованими.
Лінійно впорядкована множина називається цілком впорядкованою (англ. well-ordered), якщо кожна його непорожня підмножина має найменший елемент[3]. Такий порядок на множині називається повним порядком (англ. well-order), в контексті, де його неможливо сплутати з повним порядком в сенсі повних частково впорядкованих множин, (англ. complete order).
Класичний приклад цілком впорядкованої множини — множина натуральних чисел . Твердження про те, що будь-яка непорожня підмножина містить найменший елемент, рівносильно принципу математичної індукції. Як приклад лінійно впорядкованої, але не цілком впорядкованої множини можна навести множину невід'ємних чисел, впорядковану природним чином . Дійсно, його підмножина не має найменшого елемента.
Цілком впорядковані множини грають виключно важливу роль в загальній теорії множин.
Повна частково впорядкована множина (англ. complete partial ordered, ω-complete partial ordered) — частково впорядкована множина, у якої є дно — єдиний елемент, який передує будь-якому іншому елементу і у кожної спрямованої підмножини, у якої є точна верхня межа[4]. Повні частково впорядковані множини застосовуються в λ-обчисленнях і інформатиці, зокрема, на них вводиться топологія Скотта , на основі якої будується несуперечлива модель λ-обчислення і денотаційна семантика обчислень. Спеціальним випадком повної частково впорядкованої множини є повні ґратки — якщо будь-яка підмножина, не обов'язково спрямована, має точну верхню грань, то вона виявляється повними ґратками.
Впорядкована множина тоді і тільки тоді є повною частково впорядкованою, коли будь-яка функція , монотонна відносно порядку володіє хоча б одною нерухомою точкою: .
Будь-яку множину можна перетворити на повну частково впорядковану виділенням дна і визначенням порядку як і для всіх елементів множини .
До числа фундаментальних теорем про частково впорядковані множини відносяться принцип максимуму Гаусдорфа і лема Куратовського — Цорна, які є еквівалентними аксіомі вибору.
- Множина дійсних чисел із звичайним відношенням порядку є лінійно впорядкованою множиною.
- Натуральні числа, цілі числа, раціональні числа, ірраціональні числа тощо всі є підмножинами дійсних чисел, тому утворюють лінійно впорядковані множини зі звичайним відношенням порядку.
- На множині натуральних чисел визначимо відношення порядку за подільністю, тобто тоді і тільки тоді, коли є дільником Таким чином ми отримаємо частково впорядковану множину. Наведені вище аксіоми справджуються тому, що будь-яке натуральне число є своїм дільником, два числа, які є дільниками одне одного, збігаються, і, нарешті, якщо є дільником а є дільником то є дільником Ця множина не є лінійно впорядкованою, наприклад, жодне з чисел 2,3 не є дільником іншого. При цьому 1 є дільником будь-якого натурального числа, тому воно є найменшим елементом цієї частково упорядкованої множини.
- Ланцюг з елементів — це лінійно впорядкована множина з елементів. У комбінаториці ланцюг, який складається з позначається або
- Будь-яка множина перетворюється на частково впорядковану множину, якщо визначити на ній таке відношення порядку:
У цьому разі можна порівняти два елементи , лише коли вони збігаються. Така частково впорядкована множина називається антиланцюгом.
- Нехай — це довільна множина, а — це множина всіх підмножин (булеан). Визначимо на частковий порядок за включенням, тобто означає, що де — дві підмножини
- Тоді перетворюється на частково впорядковану множину з найменшим елементом та найбільшим елементом
- Розглянемо множину всіх -елементних послідовностей натуральних чисел з лексикографічним порядком. А саме,
якщо або або або інакше кажучи, якщо у послідовності перший ненульовий елемент — додатний. У такий спосіб перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у комп'ютерній алгебрі (див. базис Гребнера ).
- Передпорядок
- Лінійно впорядкована множина
- Цілком впорядкована множина
- Найбільший та найменший елемент
- Максимальні та мінімальні елементи
- Верхня та нижня межа
- Послідовно-паралельний частковий порядок
- Щільний порядок
- ↑ Колмогоров, 2004.
- ↑ Колмогоров, 2004, с. 38.
- ↑ Колмогоров, 2004, с. 40.
- ↑ Барендрегт, 1985, с. 23.
- Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ , 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)
- Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)
- Александров П.С. Введение в теорию множеств и общую топологию. — Москва : Наука, 1977. — 368 с. — ISBN 5354008220.(рос.)
- Мальцев А. И. Алгебраические системы. — Москва : Наука, 1970. — 392 с.(рос.)
- Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 4-е изд. — Москва : Наука, 1976. — 544 с. — ISBN 5-9221-0266-4.(рос.)