Отношение порядка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Бинарное отношение <math>R</math> на множестве <math>X</math> называется '''отношением п...»)
(нет различий)

Версия 04:49, 8 ноября 2011

Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется отношением порядка, или отношением частичного порядка, если имеют место

Множество [math]X[/math], на котором введено отношение частичного порядка, называется частично упорядоченным.

Отношение [math]R[/math], удовлетворяющее условиям рефлексивности, транзитивности, антисимметричности также называют нестрогим, или рефлексивным частичным порядком и обычно обозначают символом [math]\leqslant[/math]. Если условие рефлексивности заменить на условие антирефлексивности:

[math]\forall x \neg(xRx)[/math],

то получим определение строгого, или антирефлексивного частичного порядка, обозначаемое обычно символом [math]\lt [/math]. В общем случае, если [math]R[/math] — транзитивное, антисимметричное отношение, то

[math]R_{\leqslant} = R \cup \{(x, x) | x \in X\}[/math] — рефлексивный порядок
[math]R_{\lt } = R \setminus \{(x, x) | x \in X\}[/math] — антирефлексивный порядок.

Отношение частичного порядка [math]R[/math] называется линейным порядком, если выполнено условие

[math]\forall x \forall y (x R y \lor y R x)[/math]

Множество [math]X[/math], на котором введено отношение линейного порядка, называется линейно упорядоченным, или цепью.

Отношение [math]R[/math], удовлетворяющее только условиям рефлексивности и транзитивности, называется квазипорядком, или предпорядком.

Примеры

  • На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка, а «больше или равно» и «меньше или равно» — нестрогого.
  • Отношение Делимость|делимости на множестве целых чисел являются отношением нестрогого порядка.