Частковий порядок

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

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

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

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

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

Визначення

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

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

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

Відношення часткового порядку зазвичай позначають символом ${\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), або просто, впорядкованою множиною. Таким чином, в лінійно впорядкованій множині для будь-яких двох елементів ${\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), якщо кожна його непорожня підмножина має найменший елемент. Такий порядок на множині називається повним порядком (англ. 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) — частково впорядкована множина, у якої є дно — єдиний елемент, який передує будь-якому іншому елементу і у кожної спрямованої підмножини, у якої є (точна верхня межа). Повні частково впорядковані множини застосовуються в λ-обчисленнях і інформатиці, зокрема, на них вводиться , на основі якої будується несуперечлива модель λ-обчислення і . Спеціальним випадком повної частково впорядкованої множини є  — якщо будь-яка підмножина, не обов'язково спрямована, має точну верхню грань, то вона виявляється повними ґратками.

Впорядкована множина ${\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}$.

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

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

Приклади

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Примітки

1. Колмогоров, 2004.
2. Колмогоров, 2004, с. 38.
3. Колмогоров, 2004, с. 40.
4. Барендрегт, 1985, с. 23.

Джерела

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : , 1937. — 304 с. — .(рос.)

• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)

• Александров П.С. Введение в теорию множеств и общую топологию. — Москва : Наука, 1977. — 368 с. — .(рос.)
• Мальцев А. И. Алгебраические системы. — Москва : Наука, 1970. — 392 с.(рос.)
• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 4-е изд. — Москва : Наука, 1976. — 544 с. — .(рос.)