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

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

• Рефлексивность: [math]\forall x (xRx)[/math]
• Транзитивность: [math]\forall x \forall y \forall z (x R y \land y R z \Rightarrow x R z)[/math];
• Антисимметричность: [math]\forall x \forall y (x R y \land y R x \Rightarrow x = y)[/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], удовлетворяющее только условиям рефлексивности и транзитивности, называется квазипорядком, или предпорядком.

Примеры

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