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

проверено

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

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

  1. рефлексивности: $x\preccurlyeq x$ для всех $x\in A$;
  2. антисимметричности: $(x\preccurlyeq y)$ $\wedge$ $(y\preccurlyeq x)$ $\Rightarrow x=y$ для всех $x,y\in A$;
  3. транзитивности: $(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$2) на множестве действительных чисел $\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}$3) не является отношением частичного порядка, так как не обладает свойством антисимметричности: 2 делится на -2 и -2 делится на 2, но $2\neq-2$. Но то же самое отношение на множестве натуральных чисел $\mathbb{N}$ является отношением частичного порядка.

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

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

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

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

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

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

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

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

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

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

Литература

1)
partial order relation
4)
strict partial order relation
5)
linear order relation
6)
см. пример 2
glossary/relation/order.txt · Последние изменения: 15.02.2014 12:02:10 — Ладилова Анна
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0