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

Определения

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

Бинарное отношение [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]\forall Y \in X \exists a \in Y \forall b \in Y: 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]a \leqslant b[/math]. В качестве множества возьмём натуральные числа. Проверим свойства:

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

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

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

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

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

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

Ссылки

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