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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

Нетривиальный пример

Можно привести не совсем тривиальный пример: [math]a[/math] находится в отношении с [math]b[/math], если [math]\frac{a}{b} \leqslant 1[/math]. В качестве множества возьмём натуральные числа. Проверим свойства:

1) [math] \forall a \in X:\frac{a}{a} \leqslant 1[/math]

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

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

4) [math]\forall a \in X \forall b \in X либо \frac{a}{b} \leqslant 1, либо \frac{b}{a} \leqslant 1[/math]

5) [math]\exists a \in X \forall b \in X: \frac{a}{b} \leqslant 1[/math] - очевидно это [math] a = 1 [/math]

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

Ссылки

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