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

Определения

Определение:

Бинарное отношение $R$ на множестве $X$ называется отношением частичного порядка, если оно обладает следующими свойствами: Рефлексивность: $\forall a \in X: aRa$. Антисимметричность: $\forall a, b \in X:$ если $aRb$ и $bRa$, то $a = b$. Транзитивность: $\forall a, b, c \in X:$ если $aRb$ и $bRc$, то $aRc$.

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

Отношение частичного порядка также называют нестрогим порядком.

Определение:

Бинарное отношение $R$ на множестве $X$ называется строгим отношением частичного порядка, если оно обладает следующими свойствами: Антирефлексивность: $\forall a \in X: aRa$ — не выполняется. Антисимметричность: $\forall a, b \in X:$ если $aRb$ и $aRx$, то $a = b$. Транзитивность: $\forall a, b, c \in X:$ если $aRb$ и $bRc$, то $aRc$.

Определение:

Бинарное отношение $R$ на множестве $X$ называется отношением линейного порядка, если оно является отношением частичного порядка и обладает следующим свойством: $\forall a \in X \forall b \in X либо aRb, либо bRa$.

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

Определение:

Бинарное отношение $R$ на множестве $X$ называется отношением полного порядка, если оно является отношением линейного порядка и обладает следующим свойством: $\forall Y \in X \exists a \in Y \forall b \in Y: aRb$.

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

Отношение нестрогого порядка обозначают символом $\leqslant$. Запись вида $a \leqslant b$ читают как "$a$ меньше либо равно $b$".

Отношение строгого порядка обозначают символом $\lt$. Запись вида $a \lt b$ читают как "$a$ меньше $b$".

Примеры

• На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка, а «больше или равно» и «меньше или равно» — нестрогого, причем линейного порядка, но не полного.
• Отношение "являться делителем" на множестве целых чисел является отношением частичного порядка.
• $a$ находится в отношении с $b$, если $\frac{a}{b} \leqslant 1$. В качестве множества возьмём натуральные числа. Проверим свойства:

1) $\forall a \in X:\frac{a}{a} \leqslant 1$

2) $\forall a, b \in X:$ если $\frac{a}{b} \leqslant 1$ и $\frac{b}{a} \leqslant 1$, то $a = b$

3) $\forall a, b, c \in X:$ если $\frac{a}{b} \leqslant 1$ и $\frac{b}{c} \leqslant 1$, то $\frac{a}{c} \leqslant 1$

4) $\forall a \in X \forall b \in X либо \frac{a}{b} \leqslant 1, либо \frac{b}{a} \leqslant 1$

5) $\forall Y \in X \exists a \in Y \forall b \in Y: \frac{a}{b} \leqslant 1$ — очевидно, в любом подмножестве натуральных чисел есть наименьшее.

Таким образом данное отношение является отношением полного порядка.

Ссылки

• Wikipedia: Частично упорядоченные множества