Вікіпедія

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

Інтерактивний перегляд історії
[перевірена версія][перевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
доповнення
Немає опису редагування
Рядок 1:
[[Файл:Lattice of the divisibility of 60.svg|thumb|right|250px|[[Діаграма Гассе]] [[дільник]]ів числа 60, частково впорядкована за [[подільність|подільністю]]]]
'''Частково впорядкованою множиною''' <math>(P,\leqslant),</math> називається [[множина]] <math>P</math> із заданим на ній [[рефлексивність|рефлексивним]], [[антисиметричність|антисиметричним]] та [[транзитивність|транзитивним]] [[бінарне відношення|бінарним відношенням]] <math>\leqslant</math> (називається&nbsp;— [[відношення нестрогого порядку]]).
[[Файл: Hasse diagram of powerset of 3.svg | right | thumb | 250px |[[Діаграма Гассе]] [[Булеан|усіх підмножин]] триелементної множини {x, y, z}, які впорядковані відношенням [[Підмножина|включення множин]].]]
Рядок 11:
== Визначення ==
'''Порядком''', або '''частковим порядком''', на множині <math>M</math> називається [[бінарне відношення]] <math>\varphi</math> на <math>M</math> (визначене деякою множиною <math> R_{\varphi} \subset M \times M </math>), яке задовольняє наступні умови{{Sfn| Колмогоров | 2004 | з = 36}}:
* ''[[Рефлексивність|]]''Рефлексивність'']]: <math>\forall a \; (a \varphi a)</math>
* ''[[Транзитивність|]]''Транзитивність'']]: <math>\forall a, b, c \; (a \varphi b) \wedge (b \varphi c) \Rightarrow a \varphi c </math>
* ''[[Антисиметричне відношення|''Антисиметричність'']]'': <math>\forall a, b \; (a \varphi b) \wedge (b \varphi a) \Rightarrow a = b</math>
 
Множина <math>M</math>, на якій задане відношення часткового порядку, називається '''частково впорядкованою''' ({{lang-en|partially ordered set, poset}}). Якщо бути зовсім точним{{Sfn|Александров|1977|с=78}}, то частково впорядкованою множиною називається пара <math>\langle M, \varphi \rangle</math>, де <math>M</math>&nbsp;— множина, а <math>\varphi</math>&nbsp;— відношення часткового порядку на <math>M</math>.
 
=== Терміни йта позначення ===
 
Відношення часткового порядку зазвичай позначають символом <math>\leqslant</math>, за аналогією з відношенням «менше або дорівнює» на множині [[Дійсне число|дійсних чисел]]. При цьому, якщо <math>a \leqslant b</math>, то кажуть, що елемент <math>a</math> ''не перевершує'' <math>b</math>, або, що <math>a</math> ''підпорядкований'' <math>b</math>.
 
Рядок 26 ⟶ 25:
 
=== Строгий і нестрогий порядок ===
Відношення, що задовольняє умовам рефлексивності, транзитивності і антисиметричності, також називають ''нестрогим'', або ''рефлексивним порядком''. Якщо умову рефлексивності замінити на умову ''[[Антирефлексивність|''антирефлексивності'']]'' (тоді властивості антисиметричності зміняться на асиметричність):
: <math>\forall a \; \neg (a \varphi a)</math>,
то отримаємо визначення ''строгого'', або ''антирефлексивного порядку''.
Рядок 39 ⟶ 38:
 
=== Незрівняні елементи ===
Якщо <math>a</math> і <math>b</math> -&nbsp;— дійсні числа, то має місце тільки одне з наступних співвідношень :
<center><math>
a < b, \qquad a=b, \qquad b<a
Рядок 45 ⟶ 44:
</center>
 
У разі, якщо <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> будуть непорівнювані. Можливість існування непорівнюваних елементів пояснює сенс терміну ''"«частково впорядкована множина"»''.
 
=== Мінімальні/максимальні та найменші/найбільші елементи ===
Рядок 52 ⟶ 51:
Через те, що в частково впорядкованій множині можуть бути пари непорівнюваних елементів, вводяться два різні визначення: ''мінімальний елемент'' і ''найменший елемент''.
 
Елемент <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>\mathbb{N}\setminus \{ 1 \} = \{ 2, 3, \ldots \}</math> натуральних чисел без одиниці, впорядковану по відношенню подільності <math>\mid</math>. Тут мінімальними елементами будуть [[Просте число|прості числа]], а ось найменшого елементу не існує.
Рядок 58 ⟶ 57:
Аналогічно вводяться поняття ''максимального'' ({{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}}).
 
=== Верхня і нижня множина ===
Рядок 75 ⟶ 74:
{{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;— не є лінійно впорядкованими.
 
=== Цілком впорядковані множини ===
Рядок 86 ⟶ 85:
Лінійно впорядкована множина називається ''цілком впорядкованою'' ({{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> не має найменшого елемента.
 
Цілком впорядковані множини грають виключно важливу роль в загальній [[Теорія множин|теорії множин]].
 
=== Повна частково впорядкована множина ===<!-- використовується для перенаправлення з [[Повна частково впорядкована множина]] і интервики з [[:en:Complete partial order]]-->
'''Повна частково впорядкована множина''' ({{lang-en|complete partial ordered, ω-complete partial ordered}}) -&nbsp;— частково впорядкована множина, у якої є ''дно'' -&nbsp;— єдиний елемент, який передує будь-якому іншому елементу і у кожної [[Спрямована множина|спрямованої підмножини]], у якої є [[Точна верхня і нижня межі множин#Супремум|точна верхня межа]]{{Sfn|Барендрегт|1985|с=23}}. Повні частково впорядковані множини застосовуються в [[Ламбда-числення|λ-обчисленнях]] і [[Інформатика|інформатиці]], зокрема, на них вводиться [[топологія Скотта]], на основі якої будується несуперечлива модель λ-обчислення і [[Семантика обчислень#Денотаційна сематника|денотаційна семантика обчислень]]. Спеціальним випадком повної частково впорядкованої множини є [[повні ґратки]] -&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>.
Рядок 114 ⟶ 113:
 
* Нехай <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> перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у [[комп'ютерна алгебра|комп'ютерній алгебрі]]
Отримано з https://uk.wikipedia.org/wiki/Частково_впорядкована_множина