Перегляд вихідного коду сторінки Частково впорядкована множина

[[Файл:Infinite lattice of divisors.svg|thumb|upright|Додатні числа впорядковані за [[подільність|подільністю]]]]
[[Файл:Lattice of the divisibility of 60.svg|thumb|right|250px|[[Діаграма Гассе]] [[дільник]]ів числа 60, частково впорядкована за [[подільність|подільністю]]]]
[[Файл: Hasse diagram of powerset of 3.svg | right | thumb | 250px |[[Діаграма Гассе]] [[Булеан|усіх підмножин]] триелементної множини {x, y, z}, які впорядковані відношенням [[Підмножина|включення множин]].]]
'''Частково впорядкована множина''' (poset — {{lang-en|partially ordered set}}) — це [[множина]] <math>P</math> з заданим частковим порядком <math>\leqslant</math> ([[антисиметричне відношення|антисиметричним]] [[передпорядок|передпорядком]]), тобто з [[бінарне відношення|бінарним відношенням]], що є [[транзитивне відношення|транзитивним]], [[рефлексивне відношення|рефлексивним]] та [[антисиметричне відношення|антисиметричним]]. Позначається <math>(P,\leqslant).</math>

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

== Визначення ==
'''Частковим порядком''', на множині <math>S</math> називається [[бінарне відношення]] <math>\leqslant</math>, визначене деякою множиною <math> R_{\leqslant} \subset S \times S</math>), яке задовольняє наступні умови{{Sfn| Колмогоров | 2004 | з = 36}}:
* ''[[Транзитивне відношення|Транзитивність]]'': <math>\forall a, b, c: \quad (a \leqslant b) \wedge (b \leqslant c) \Rightarrow a \leqslant c </math>
* ''[[Рефлексивне відношення|Рефлексивність]]'': <math>\forall a: \quad (a \leqslant a)</math>
* ''[[Антисиметричне відношення|Антисиметричність]]'': <math>\forall a, b: \quad (a \leqslant b) \wedge (b \leqslant a) \Rightarrow a = b</math>

=== Терміни та позначення ===
Відношення часткового порядку зазвичай позначають символом <math>\leqslant</math>, за аналогією з відношенням «менше або дорівнює» на множині [[Дійсне число|дійсних чисел]]. При цьому, якщо <math>a \leqslant b</math>, то кажуть, що елемент <math>a</math> ''не перевершує'' <math>b</math>, або, що <math>a</math> ''підпорядкований'' <math>b</math>.

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

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

=== Строгий і нестрогий порядок ===
Відношення, що задовольняє умовам рефлексивності, транзитивності і антисиметричності, також називають ''нестрогим'', або ''рефлексивним порядком''. Якщо умову рефлексивності замінити на умову ''[[Антирефлексивність|антирефлексивності]]'' (тоді властивості антисиметричності зміняться на асиметричність):
: <math>\forall a \; \neg (a \varphi a)</math>,
то отримаємо визначення ''строгого'', або ''антирефлексивного порядку''.

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

=== Незрівняні елементи ===
Якщо <math>a</math> і <math>b</math>&nbsp;— дійсні числа, то має місце тільки одне з наступних співвідношень :
{{center|<math>
a < b, \qquad a=b, \qquad b<a
</math>
}}

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

=== Мінімальні/максимальні та найменші/найбільші елементи ===
Максимальні та мінімальні елементи
{{main|Максимальні та мінімальні елементи}}
{{main|Найбільший та найменший елемент}}

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

Елемент <math>a \in M</math> називається '''мінімальним''' ({{lang-en|minimal element}}), якщо не існує елемента <math>b < a</math>. Іншими словами <math>a</math>&nbsp;— мінімальний елемент, якщо для будь-якого елемента <math>b \in M</math> або <math>b>a</math>, або <math>b=a</math>, або <math>b</math> і <math>a</math> непорівнювані. 

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

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

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

=== Верхні та нижні грані ===
{{main|Верхня та нижня межа}}
Нехай <math>A</math>&nbsp;— підмножина частково впорядкованої великої множини <math>\langle M, \leqslant\rangle</math>. Елемент <math>u \in M</math> називається ''верхньою гранню'' ({{lang-en|upper bound}}) <math>A</math>, якщо будь-який елемент <math>a \in A</math> не перевершує <math>u</math>. Аналогічно вводиться поняття ''нижньої грані'' ({{lang-en|lower bound}}) множини <math>A</math>.

Будь-який елемент, більший, ніж деяка верхня грань <math>A</math>, також буде верхньою гранню <math>A</math>. А будь-який елемент, менший, ніж деяка нижня грань <math>A</math>, також буде нижньою гранню <math>A</math>. Ці міркування ведуть до введення понять ''[[Супремум|найменшої верхньої грані]]'' ({{lang-en|least upper bound}}) і ''[[Інфімум|найбільшої нижньої грані]]'' ({{lang-en|greatest lower bound}}).

=== Верхня і нижня множина ===
{{main|Верхня множина}}
[[Файл: Upset.svg|thumb|Елементи верхньої множини <math>2^{\{1,2,3,4\}} \uparrow \{1\}</math> відмічені зеленим]]
Для елементу <math>m</math> частково впорядкованої множини <math>\langle M, \leqslant\rangle</math> '''верхньою множиною''' ({{lang-en|upper set, upset}}) називається множина <math>M \uparrow m</math> усіх елементів, яким <math>m</math> передує (<math>\{ x \in M \mid m \leqslant x\}</math>).

[[Двоїстість (теорія порядку)|Двоїстим]] чином визначається '''нижня множина''' ({{lang-en|down set, lower set}}), як множина усіх елементів, передуючих заданому : <math>M \downarrow m \stackrel{\mathrm{def}}{ = } \{ x \in M \mid x \leqslant m\}</math>.

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

=== Лінійно впорядковані множини ===
{{main|Лінійно впорядкована множина}}

Нехай <math>\langle M, \leqslant\rangle</math>&nbsp;— частково впорядкована множина. Якщо в <math>M</math> будь-які два елементи порівнянні, то множина <math>M</math> називається ''лінійно впорядкованою'' ({{lang-en|linearly ordered set}}). Лінійно впорядковану множину також називають ''абсолютно впорядкованою'' ({{lang-en|totally ordered set}}), або просто, ''впорядкованою множиною''{{Sfn|Колмогоров|2004|с=38}}. Таким чином, в лінійно впорядкованій множині для будь-яких двох елементів <math>a</math> і <math>b</math> має місце одне і тільки одне зі співвідношень: або <math>a<b</math>, або <math>a=b</math>, або <math>b<a</math>.

Також всяку лінійно впорядковану підмножину частково впорядкованої множини називають ''ланцюгом'' ({{lang-en|chain}}), тобто ланцюг в частково впорядкованій множині <math>\langle M, \leqslant \rangle</math>&nbsp;— така його підмножина, в якій будь-які два елементи порівнювані.

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

=== Цілком впорядковані множини ===
{{main|Цілком впорядкована множина}}

Лінійно впорядкована множина називається ''цілком впорядкованою'' ({{lang-en|well-ordered}}), якщо кожна його непорожня підмножина має найменший елемент{{Sfn|Колмогоров|2004|с=40}}. Такий порядок на множині називається ''повним порядком'' ({{lang-en|well-order}}), в контексті, де його неможливо сплутати з повним порядком в сенсі [[#Повна частково впорядкована множина|повних частково впорядкованих множин]], ({{lang-en|complete order}}).

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

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

=== Повна частково впорядкована множина ===<!-- використовується для перенаправлення з [[Повна частково впорядкована множина]]-->
'''Повна частково впорядкована множина''' ({{lang-en|complete partial ordered, ω-complete partial ordered}})&nbsp;— частково впорядкована множина, у якої є ''дно''&nbsp;— єдиний елемент, який передує будь-якому іншому елементу і у кожної [[Спрямована множина|спрямованої підмножини]], у якої є [[Точна верхня і нижня межі множин#Супремум|точна верхня межа]]{{Sfn|Барендрегт|1985|с=23}}. Повні частково впорядковані множини застосовуються в [[Ламбда-числення|λ-обчисленнях]] і [[Інформатика|інформатиці]], зокрема, на них вводиться {{li|топологія Скотта|Q=Q895815}}, на основі якої будується несуперечлива модель λ-обчислення і [[Денотаційна семантика|денотаційна семантика обчислень]]. Спеціальним випадком повної частково впорядкованої множини є [[Повна ґратка|повні ґратки]]&nbsp;— якщо будь-яка підмножина, не обов'язково спрямована, має точну верхню грань, то вона виявляється повними ґратками.

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

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

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

== Приклади ==
* Множина <math>\R</math> [[дійсні числа|дійсних чисел]] із звичайним відношенням порядку є лінійно впорядкованою множиною.

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

* На множині натуральних чисел <math>\N</math> визначимо відношення порядку за [[подільність|подільністю]], тобто <math>a\leq b</math> тоді і тільки тоді, коли <math>a</math> є [[дільник]]ом <math>b.</math> Таким чином ми отримаємо частково впорядковану множину. Наведені вище аксіоми справджуються тому, що будь-яке натуральне число є своїм дільником, два числа, які є дільниками одне одного, збігаються, і, нарешті, якщо <math>\ a</math> є дільником <math>\ b,</math> а <math>b</math> є дільником <math>\ c,</math> то <math>\ a</math> є дільником <math>\ c.</math> Ця множина не є лінійно впорядкованою, наприклад, жодне з чисел 2,3 не є дільником іншого. При цьому 1 є дільником будь-якого натурального числа, тому воно є [[найменший елемент|найменшим елементом]] цієї частково упорядкованої множини.

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

* Будь-яка множина <math>A</math> перетворюється на частково впорядковану множину, якщо визначити на ній таке відношення порядку: <math>a\leq b \iff a=b.</math>
У цьому разі можна порівняти два елементи <math>A</math>, лише коли вони збігаються.
Така частково впорядкована множина називається '''антиланцюгом'''.

* Нехай <math>A</math>&nbsp;— це довільна множина, а <math>\Omega(A)</math>&nbsp;— це множина всіх підмножин <math>A</math> ([[булеан]]). Визначимо на <math>\Omega(A)</math> частковий порядок за [[включення]]м, тобто <math>B\leq C</math> означає, що <math>B\subseteq C,</math> де <math>B,C\in\Omega(A)</math>&nbsp;— дві підмножини <math>A.</math>
: Тоді <math>\Omega(A)</math> перетворюється на частково впорядковану множину з найменшим елементом <math>\empty</math> та найбільшим елементом <math>A.</math>

* Розглянемо множину <math>\N^n</math> всіх <math>n</math>-елементних послідовностей натуральних чисел з [[лексикографічний порядок|лексикографічним порядком]]. А саме,
: <math>(a_1,a_2,\ldots,a_n) \leq (b_1,b_2,\ldots,b_n),</math>
якщо <math>a_1<b_1,</math> або <math>a_1=b_1, a_2<b_2,</math> або <math>\ldots</math> або <math>a_1=b_1, a_2=b_2, \ldots, a_n=b_n;</math> інакше кажучи, якщо у послідовності <math>b_1-a_1,b_2-a_2,\ldots,b_n-a_n</math> перший ненульовий елемент&nbsp;— додатний.
У такий спосіб <math>\N^n</math> перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у [[Комп'ютерна алгебра|комп'ютерній алгебрі]]
(див. {{li|базис Гребнера|Q=Q1551631}}).

== Див. також ==
{{Портал|Математика}}
* [[Передпорядок]]
* [[Лінійно впорядкована множина]]
* [[Цілком впорядкована множина]]
* [[Найбільший та найменший елемент]]
* [[Максимальні та мінімальні елементи]]
* [[Верхня та нижня межа]]
* [[Послідовно-паралельний частковий порядок]]
* [[Щільний порядок]]

== Примітки ==
{{Reflist}}

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

{{Теорія порядку|state=expanded}}

[[Категорія:Теорія порядку]]
[[Категорія:Бінарні відношення]]