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

Материал из Википедии — свободной энциклопедии

Бинарное отношение $R$ на множестве $X$ называется отношением порядка, если имеют место

Транзитивность: $\forall x \forall y \forall z (x R y \land y R z \Rightarrow x R z)$ ;
Антисимметричность: $\forall x \forall y (x R y \land y R x \Rightarrow x = y)$ .

Отношение порядка называется нестрогим, если оно

Рефлексивно: $\forall x (x R x)$ .

Напротив, отношение строгого порядка

Антирефлексивно (или иррефлексивно): $\forall x (\lnot x R x)$ .

Отношение порядка называется полным (линейным), если любые два элемента множества так или иначе связаны этим отношением, т.е.:

Полнота: $\forall x \forall y (x R y \lor y R x)$ .

Полностью (линейно) упорядоченное множество называют также цепью. Очевидно, полнота (линейность) отношения порядка влечет рефлексивность этого отношения, поэтому такой порядок всегда нестрогий.

Рефлексивное, транзитивное, антисимметричное отношение называется частичным порядком. А рефлексивное, транзитивное (но не обязательно антисимметричное!) отношение называется квазипорядком (или предпорядком).

Обычно отношение строгого порядка (полного или частичного) обозначается знаком <, а отношение нестрогого порядка — знаком $\le$ .