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

Нехай <math>\langle M, \leqslant\rangle</math> - частково впорядкована множина. Якщо в <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|well-ordered}}), якщо кожна його непорожня підмножина має найменший елемент{{Sfn|Колмогоров|2004|с=40}}. Такий порядок на множині називається ''повним порядком'' ({{lang-en|well-order}}), в контексті, де його неможливо сплутати з повним порядком в сенсі [[#Повна частково впорядкована множина|повних частково впорядкованих множин]], ({{lang-en|complete order}}).

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

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