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

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

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

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

Частково впорядкована множина (poset — Шаблон:Lang-en) — це множина $P$ з заданим частковим порядком $⩽$ (антисиметричним передпорядком), тобто з бінарним відношенням, що є транзитивним, рефлексивним та антисиметричним. Позначається $(P,⩽).$

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

Визначення

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

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

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

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

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

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

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

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

$\mathrm{\forall }a\mathrm{\neg }(a\phi a)$,

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

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

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

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

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

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

Максимальні та мінімальні елементи Шаблон:Main Шаблон:Main

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

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

Елемент $a$ називається найменшим ((Шаблон:Lang-en), якщо для будь-якого елементу $b\in M$ має місце нерівність $b⩾a$. Очевидно, всякий найменший елемент є також мінімальним, але зворотне в загальному випадку є невірним: мінімальний елемент $a$ може і не бути найменшим, якщо існують елементи $b$, непорівнювані з $a$.

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

Аналогічно вводяться поняття максимального (Шаблон:Lang-en) і найбільшого (Шаблон:Lang-en) елементів.

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

Шаблон:Main Нехай $A$ — підмножина частково впорядкованої великої множини $⟨M,⩽⟩$. Елемент $u\in M$ називається верхньою гранню (Шаблон:Lang-en) $A$, якщо будь-який елемент $a\in A$ не перевершує $u$. Аналогічно вводиться поняття нижньої грані (Шаблон:Lang-en) множини $A$.

Будь-який елемент, більший, ніж деяка верхня грань $A$, також буде верхньою гранню $A$. А будь-який елемент, менший, ніж деяка нижня грань $A$, також буде нижньою гранню $A$. Ці міркування ведуть до введення понять найменшої верхньої грані (Шаблон:Lang-en) і найбільшої нижньої грані (Шаблон:Lang-en).

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

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

Для елементу $m$ частково впорядкованої множини $⟨M,⩽⟩$ верхньою множиною (Шаблон:Lang-en) називається множина $M\uparrow m$ усіх елементів, яким $m$ передує ($\{x\in M\mid m⩽x\}$).

Двоїстим чином визначається нижня множина (Шаблон:Lang-en), як множина усіх елементів, передуючих заданому : $M\downarrow m\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\{x\in M\mid x⩽m\}$.

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

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

Нехай $⟨M,⩽⟩$ — частково впорядкована множина. Якщо в $M$ будь-які два елементи порівнянні, то множина $M$ називається лінійно впорядкованою (Шаблон:Lang-en). Лінійно впорядковану множину також називають абсолютно впорядкованою (Шаблон:Lang-en), або просто, впорядкованою множиноюШаблон:Sfn. Таким чином, в лінійно впорядкованій множині для будь-яких двох елементів $a$ і $b$ має місце одне і тільки одне зі співвідношень: або $a<b$, або $a=b$, або $b<a$.

Також всяку лінійно впорядковану підмножину частково впорядкованої множини називають ланцюгом (Шаблон:Lang-en), тобто ланцюг в частково впорядкованій множині $⟨M,⩽⟩$ — така його підмножина, в якій будь-які два елементи порівнювані.

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

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

Лінійно впорядкована множина називається цілком впорядкованою (Шаблон:Lang-en), якщо кожна його непорожня підмножина має найменший елементШаблон:Sfn. Такий порядок на множині називається повним порядком (Шаблон:Lang-en), в контексті, де його неможливо сплутати з повним порядком в сенсі повних частково впорядкованих множин, (Шаблон:Lang-en).

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

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

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

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

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

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

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

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

Приклади

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

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

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

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

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

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

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

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

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

$(a_1,a_2,\dots ,a_n)\le (b_1,b_2,\dots ,b_n),$

якщо $a_1<b_1,$ або $a_1=b_1,a_2<b_2,$ або $\dots$ або $a_1=b_1,a_2=b_2,\dots ,a_n=b_n;$ інакше кажучи, якщо у послідовності $b_1-a_1,b_2-a_2,\dots ,b_n-a_n$ перший ненульовий елемент — додатний. У такий спосіб ${\mathbb{N}}^n$ перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у комп'ютерній алгебрі (див. Шаблон:Li).

Див. також

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

Джерела

• Шаблон:Хаусдорф.Теория множеств
• Шаблон:Куратовский.Мостовский.Теория множеств
• Шаблон:Александров.Введение в теорию множеств и общую топологию
• Шаблон:Мальцев.Алгебраические системы
• Шаблон:Колмогоров.Фомин