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

Частково впорядкована множина (poset — англ. partially ordered set) — це множина $P$ з заданим частковим порядком $\leqslant$ (антисиметричним передпорядком), тобто з бінарним відношенням, що є транзитивним, рефлексивним та антисиметричним. Позначається $(P,\leqslant ).$

Додатні числа впорядковані за подільністю

Діаграма Гассе дільників числа 60, частково впорядкована за подільністю

Діаграма Гассе усіх підмножин триелементної множини {x, y, z}, які впорядковані відношенням включення множин.

Скінченні частково впорядковані множини графічно зображаються діаграмами Гассе.

Визначення

Частковим порядком, на множині $S$ називається бінарне відношення $\leqslant$, визначене деякою множиною $R_{\leqslant }\subset S\times S$), яке задовольняє наступні умови:

• Транзитивність: $\forall a,b,c:\quad (a\leqslant b)\wedge (b\leqslant c)\Rightarrow a\leqslant c$
• Рефлексивність: $\forall a:\quad (a\leqslant a)$
• Антисиметричність: $\forall a,b:\quad (a\leqslant b)\wedge (b\leqslant a)\Rightarrow a=b$

Терміни та позначення

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

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

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

Строгий і нестрогий порядок

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

$\forall a\;\neg (a\varphi a)$,

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

Пов'язані визначення

Незрівняні елементи

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

$a<b,\qquad a=b,\qquad b<a$

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

Мінімальні/максимальні та найменші/найбільші елементи

Максимальні та мінімальні елементи

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

Елемент $a\in M$ називається мінімальним (англ. minimal element), якщо не існує елемента $b<a$. Іншими словами $a$ — мінімальний елемент, якщо для будь-якого елемента $b\in M$ або $b>a$, або $b=a$, або $b$ і $a$ непорівнювані.

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

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

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

Верхні та нижні грані

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

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

Верхня і нижня множина

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

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

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

Спеціальні типи частково впорядкованих множин

Лінійно впорядковані множини

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

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

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

Цілком впорядковані множини

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

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

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

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

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

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

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

Теореми про частково впорядковані множини

До числа фундаментальних теорем про частково впорядковані множини відносяться принцип максимуму Гаусдорфа і лема Куратовського — Цорна, які є еквівалентними аксіомі вибору.

Приклади

• Множина $\mathbb {R}$ дійсних чисел із звичайним відношенням порядку є лінійно впорядкованою множиною.

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

• На множині натуральних чисел $\mathbb {N}$ визначимо відношення порядку за подільністю, тобто $a\leq b$ тоді і тільки тоді, коли $a$ є дільником $b.$ Таким чином ми отримаємо частково впорядковану множину. Наведені вище аксіоми справджуються тому, що будь-яке натуральне число є своїм дільником, два числа, які є дільниками одне одного, збігаються, і, нарешті, якщо $\ a$ є дільником $\ b,$ а $b$ є дільником $\ c,$ то $\ a$ є дільником $\ c.$ Ця множина не є лінійно впорядкованою, наприклад, жодне з чисел 2,3 не є дільником іншого. При цьому 1 є дільником будь-якого натурального числа, тому воно є найменшим елементом цієї частково упорядкованої множини.

• Ланцюг з $n$ елементів — це лінійно впорядкована множина з $n$ елементів. У комбінаториці ланцюг, який складається з $1<2<\ldots <n,$ позначається $[n]$ або $\mathbf {n} .$

• Будь-яка множина $A$ перетворюється на частково впорядковану множину, якщо визначити на ній таке відношення порядку: $a\leq b\iff a=b.$

У цьому разі можна порівняти два елементи $A$, лише коли вони збігаються. Така частково впорядкована множина називається антиланцюгом.

• Нехай $A$ — це довільна множина, а $\Omega (A)$ — це множина всіх підмножин $A$ (булеан). Визначимо на $\Omega (A)$ частковий порядок за включенням, тобто $B\leq C$ означає, що $B\subseteq C,$ де $B,C\in \Omega (A)$ — дві підмножини $A.$

Тоді $\Omega (A)$ перетворюється на частково впорядковану множину з найменшим елементом $\emptyset$ та найбільшим елементом $A.$

• Розглянемо множину $\mathbb {N} ^{n}$ всіх $n$-елементних послідовностей натуральних чисел з лексикографічним порядком. А саме,

$(a_{1},a_{2},\ldots ,a_{n})\leq (b_{1},b_{2},\ldots ,b_{n}),$

якщо $a_{1}<b_{1},$ або $a_{1}=b_{1},a_{2}<b_{2},$ або $\ldots$ або $a_{1}=b_{1},a_{2}=b_{2},\ldots ,a_{n}=b_{n};$ інакше кажучи, якщо у послідовності $b_{1}-a_{1},b_{2}-a_{2},\ldots ,b_{n}-a_{n}$ перший ненульовий елемент — додатний. У такий спосіб $\mathbb {N} ^{n}$ перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у комп'ютерній алгебрі (див. базис Гребнера).

Див. також

• Передпорядок
• Лінійно впорядкована множина
• Цілком впорядкована множина
• Найбільший та найменший елемент
• Максимальні та мінімальні елементи
• Верхня та нижня межа
• Послідовно-паралельний частковий порядок
• Щільний порядок

Джерела

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ, 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.(рос.)