Отношение порядка на множестве

Отношение порядка на множестве

Отношение частичного порядка

Определение 1. Бинарное отношение $\preccurlyeq$ на множестве $A$ называется отношением частичного порядка¹⁾, если оно удовлетворяет свойствам

рефлексивности: $x\preccurlyeq x$ для всех $x\in A$ ;
антисимметричности: $(x\preccurlyeq y)$ $\wedge$ $(y\preccurlyeq x)$ $\Rightarrow x=y$ для всех $x,y\in A$ ;
транзитивности: $(x\preccurlyeq y)$ $\wedge$ $(y\preccurlyeq z)$ $\Rightarrow x\preccurlyeq z$ для всех $x,y,z\in A$ .

Пример 1. Пусть $\mathcal{P}(U)$ — множество всех подмножеств множества $U$ . Отношение включения $\subseteq$ на $\mathcal{P}(U)$ является отношением частичного порядка.

Пример 2. Упорядочение $\leqslant$ ²⁾ на множестве действительных чисел $\mathbb{R}$ является отношением частичного порядка.

Пример 3. На множестве комплексных чисел $\mathbb{C}$ определим бинарное отношение $\leqslant$ как множество упорядоченных пар комплексных чисел $(x_1+y_1i,x_2+y_2i)$ таких, что $x_1\leqslant x_2$ и $y_1\leqslant y_2$ . Тогда $\leqslant$ удовлетворяет свойствам

рефлексивности;
антисимметричности;
транзитивности,

и по определению является отношением частичного порядка.

Пример 4. Отношение делимости на множестве целых чисел $\mathbb{Z}$ ³⁾ не является отношением частичного порядка, так как не обладает свойством антисимметричности: 2 делится на -2 и -2 делится на 2, но $2\neq-2$ . Но то же самое отношение на множестве натуральных чисел $\mathbb{N}$ является отношением частичного порядка.

Достаточно часто наряду с отношением частичного порядка встречаются бинарные отношения, которые вместо отношения рефлексивности удовлетворяют отношению антирефлексивности. Например, на множестве действительных чисел в случае, если $x\leqslant y$ и $x\neq y$ пишут $x< y$ .

Определение 2. Бинарное отношение $\prec$ на множестве $A$ называется отношением строгого частичного порядка⁴⁾, если оно удовлетворяет свойствам

антирефлексивности: $x\not\prec x$ для всех $x\in A$ ;
антисимметричности: $(x\prec y)$ $\wedge$ $(y\prec x)$ $\Rightarrow x=y$ для всех $x,y\in A$ ;
транзитивности: $(x\prec y)$ $\wedge$ $(y\prec z)$ $\Rightarrow x\prec z$ для всех $x,y,z\in A$ .

Отношение линейного порядка

Определение 3. Бинарное отношение $\preccurlyeq$ на множестве $A$ называется отношением линейного порядка⁵⁾, если

$\preccurlyeq$ является отношением частичного порядка;
для любых $x,y\in A$ либо $x\preccurlyeq y$ , либо $y\preccurlyeq x$ .

Пример 5. Бинарное отношение $\leqslant$ на множестве комплексных чисел $\mathbb{C}$ из примера 1 не является отношением линейного порядка, так как ни пара $(1,i)$ , ни $(i,1)$ не принадлежат бинарному отношению $\leqslant$ .

Пример 6. На множестве комплексных чисел $\mathbb{C}$ определим бинарное отношение $\preccurlyeq$ как множество упорядоченных пар комплексных чисел $(a,b)$ , удовлетворяющих условию $|a|<|b|$ или $|a|=|b|,\textrm{arg}~(a)\leqslant\textrm{arg}~(b)$ . Отношение $\preccurlyeq$ является отношением линейного порядка.

Пример 7. На множестве действительных чисел $\mathbb{R}$ упорядочение $\leqslant$ ⁶⁾ является отношением линейного порядка.

Упорядоченные множества

Про множество, на котором задано отношение частичного порядка, говорят, что оно частично упорядочено. Если же задано отношение линейного порядка, то множество называют линейно упорядоченным, или просто упорядоченным.