Частково впорядкована множина

Відношення часткового порядку зазвичай позначають символом ${\displaystyle \leqslant }$, за аналогією з відношенням «менше або дорівнює» на множині дійсних чисел. При цьому, якщо ${\displaystyle a\leqslant b}$, то кажуть, що елемент ${\displaystyle a}$ не перевершує ${\displaystyle b}$, або, що ${\displaystyle a}$ підпорядкований ${\displaystyle b}$.

Якщо ${\displaystyle a\leqslant b}$ і ${\displaystyle a\neq b}$, то пишуть ${\displaystyle a<b}$, і кажуть, що ${\displaystyle a}$ менше ${\displaystyle b}$, або, що ${\displaystyle a}$ строго підпорядковане ${\displaystyle b}$.

Іноді, щоб відрізнити довільний порядок на деякій множині від відомого відношення «менше або дорівнює» на множині дійсних чисел, замість ${\displaystyle \leqslant }$ і ${\displaystyle <}$ використовують спеціальні символи ${\displaystyle \preccurlyeq }$ і ${\displaystyle \prec }$ відповідно.

Відношення, що задовольняє умовам рефлексивності, транзитивності і антисиметричності, також називають нестрогим, або рефлексивним порядком. Якщо умову рефлексивності замінити на умову антирефлексивності (тоді властивості антисиметричності зміняться на асиметричність):

${\displaystyle \forall a\;\neg (a\varphi a)}$,

то отримаємо визначення строгого, або антирефлексивного порядку.

Якщо ${\displaystyle a}$ і ${\displaystyle b}$ — дійсні числа, то має місце тільки одне з наступних співвідношень :

${\displaystyle a<b,\qquad a=b,\qquad b<a}$

У разі, якщо ${\displaystyle a}$ і ${\displaystyle b}$ — елементи довільної частково впорядкованої множини, то існує четверта логічна можливість: не виконується жодне з вказаних трьох співвідношень. В цьому випадку елементи ${\displaystyle a}$ і ${\displaystyle b}$ називаються непорівнюваними. Наприклад, якщо ${\displaystyle M}$ — множина дійснозначних функцій на відрізку ${\displaystyle [0,1]}$, то елементи ${\displaystyle f(x)=x}$ і ${\displaystyle g(x)=1-x}$ будуть непорівнювані. Можливість існування непорівнюваних елементів пояснює сенс терміну «частково впорядкована множина».

Через те, що в частково впорядкованій множині можуть бути пари непорівнюваних елементів, вводяться два різні визначення: мінімальний елемент і найменший елемент.

Елемент ${\displaystyle a\in M}$ називається мінімальним (англ. minimal element), якщо не існує елемента ${\displaystyle b<a}$. Іншими словами ${\displaystyle a}$ — мінімальний елемент, якщо для будь-якого елемента ${\displaystyle b\in M}$ або ${\displaystyle b>a}$, або ${\displaystyle b=a}$, або ${\displaystyle b}$ і ${\displaystyle a}$ непорівнювані. Елемент ${\displaystyle a}$ називається найменшим ((англ. least element, lower bound (opp. upper bound)), якщо для будь-якого елементу ${\displaystyle b\in M}$ має місце нерівність ${\displaystyle b\geqslant a}$. Очевидно, всякий найменший елемент є також мінімальним, але зворотне в загальному випадку є невірним: мінімальний елемент ${\displaystyle a}$ може і не бути найменшим, якщо існують елементи ${\displaystyle b}$, непорівнювані з ${\displaystyle a}$.

Очевидно, що якщо в множині існує найменший елемент, то він єдиний. А ось мінімальних елементів може бути декілька. Як приклад, розглянемо множину ${\displaystyle \mathbb {N} \setminus \{1\}=\{2,3,\ldots \}}$ натуральних чисел без одиниці, впорядковану по відношенню подільності ${\displaystyle \mid }$. Тут мінімальними елементами будуть прості числа, а ось найменшого елементу не існує.

Аналогічно вводяться поняття максимального (англ. maximal element) і найбільшого (англ. greatest element) елементів.

Нехай ${\displaystyle A}$ — підмножина частково впорядкованої великої множини ${\displaystyle \langle M,\leqslant \rangle }$. Елемент ${\displaystyle u\in M}$ називається верхньою гранню (англ. upper bound) ${\displaystyle A}$, якщо будь-який елемент ${\displaystyle a\in A}$ не перевершує ${\displaystyle u}$. Аналогічно вводиться поняття нижньої грані (англ. lower bound) множини ${\displaystyle A}$.

Будь-який елемент, більший, ніж деяка верхня грань ${\displaystyle A}$, також буде верхньою гранню ${\displaystyle A}$. А будь-який елемент, менший, ніж деяка нижня грань ${\displaystyle A}$, також буде нижньою гранню ${\displaystyle A}$. Ці міркування ведуть до введення понять найменшої верхньої грані (англ. least upper bound) і найбільшої нижньої грані (англ. greatest lower bound).

Елементи верхньої множини ${\displaystyle 2^{\{1,2,3,4\}}\uparrow \{1\}}$ відмічені зеленим

Для елементу ${\displaystyle m}$ частково впорядкованої множини ${\displaystyle \langle M,\leqslant \rangle }$ верхньою множиною (англ. upper set, upset) називається множина ${\displaystyle M\uparrow m}$ усіх елементів, яким ${\displaystyle m}$ передує (${\displaystyle \{x\in M\mid m\leqslant x\}}$).

Двоїстим чином визначається нижня множина (англ. down set, lower set), як множина усіх елементів, передуючих заданому : ${\displaystyle M\downarrow m{\stackrel {\mathrm {def} }{=}}\{x\in M\mid x\leqslant m\}}$.

Нехай ${\displaystyle \langle M,\leqslant \rangle }$ — частково впорядкована множина. Якщо в ${\displaystyle M}$ будь-які два елементи порівнянні, то множина ${\displaystyle M}$ називається лінійно впорядкованою (англ. linearly ordered set). Лінійно впорядковану множину також називають абсолютно впорядкованою (англ. totally ordered set), або просто, впорядкованою множиною[3]. Таким чином, в лінійно впорядкованій множині для будь-яких двох елементів ${\displaystyle a}$ і ${\displaystyle b}$ має місце одне і тільки одне зі співвідношень: або ${\displaystyle a<b}$, або ${\displaystyle a=b}$, або ${\displaystyle b<a}$.

Також всяку лінійно впорядковану підмножину частково впорядкованої множини називають ланцюгом (англ. chain), тобто ланцюг в частково впорядкованій множині ${\displaystyle \langle M,\leqslant \rangle }$ — така його підмножина, в якій будь-які два елементи порівнювані.

З наведених вище прикладів частково впорядкованих множин тільки множина дійсних чисел є лінійно впорядкованою. Множина дійснозначних функцій на відрізку ${\displaystyle [a,b]}$ (за умови ${\displaystyle a<b}$), булеан ${\displaystyle {\mathcal {P}}(M)}$ (при ${\displaystyle |M|\geqslant 2}$), натуральні числа з відношенням подільності — не є лінійно впорядкованими.

Лінійно впорядкована множина називається цілком впорядкованою (англ. well-ordered), якщо кожна його непорожня підмножина має найменший елемент[4]. Такий порядок на множині називається повним порядком (англ. well-order), в контексті, де його неможливо сплутати з повним порядком в сенсі повних частково впорядкованих множин, (англ. complete order).

Класичний приклад цілком впорядкованої множини — множина натуральних чисел ${\displaystyle \mathbb {N} }$. Твердження про те, що будь-яка непорожня підмножина ${\displaystyle \mathbb {N} }$ містить найменший елемент, рівносильно принципу математичної індукції. Як приклад лінійно впорядкованої, але не цілком впорядкованої множини можна навести множину невід'ємних чисел, впорядковану природним чином ${\displaystyle \mathbb {R} _{+}=\{x:x\geqslant 0\}}$. Дійсно, його підмножина ${\displaystyle \{x:x>1\}}$ не має найменшого елемента.

Цілком впорядковані множини грають виключно важливу роль в загальній теорії множин.

Повна частково впорядкована множина (англ. complete partial ordered, ω-complete partial ordered) — частково впорядкована множина, у якої є дно — єдиний елемент, який передує будь-якому іншому елементу і у кожної спрямованої підмножини, у якої є точна верхня межа[5]. Повні частково впорядковані множини застосовуються в λ-обчисленнях і інформатиці, зокрема, на них вводиться топологія Скотта, на основі якої будується несуперечлива модель λ-обчислення і денотаційна семантика обчислень. Спеціальним випадком повної частково впорядкованої множини є повні ґратки — якщо будь-яка підмножина, не обов'язково спрямована, має точну верхню грань, то вона виявляється повними ґратками.

Впорядкована множина ${\displaystyle M}$ тоді і тільки тоді є повною частково впорядкованою, коли будь-яка функція ${\displaystyle f\colon M\rightarrow M}$, монотонна відносно порядку ${\displaystyle a\leqslant b\Rightarrow f(a)\leqslant f(b)}$ володіє хоча б одною нерухомою точкою: ${\displaystyle \exists _{x\in M}f(x)=x}$.

Будь-яку множину ${\displaystyle M}$ можна перетворити на повну частково впорядковану виділенням дна ${\displaystyle \bot }$ і визначенням порядку ${\displaystyle \leqslant }$ як ${\displaystyle \bot \leqslant m}$ і ${\displaystyle m\leqslant m}$ для всіх елементів ${\displaystyle m}$ множини ${\displaystyle M}$.