§ 5. ОТНОШЕНИЯ ПОРЯДКА

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

Пусть R — бинарное отношение на множестве А.

ОПРЕДЕЛЕНИЕ. Бинарное отношение R на множестве А называется отношением порядка на А или порядком на А, если оно транзитивно и антисимметрично.

ОПРЕДЕЛЕНИЕ. Отношение порядка R на множестве А называется нестрогим, если оно рефлексивно на А, т. е. для всякого из А.

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

ОПРЕДЕЛЕНИЕ. Бинарное отношение R на множестве А называется строгим порядком на А, если оно транзитивно и антирефлексивно на А.

Примеры. 1. Пусть — множество всех подмножеств множества М. Отношение включения на множестве есть отношение нестрогого порядка.

2. Отношения на множестве действительных чисел являются соответственно отношением строгого и нестрогого порядка.

3. Отношение делимости во множестве натуральных чисел есть отношение нестрогого порядка.

ОПРЕДЕЛЕНИЕ. Бинарное отношение R на множестве А называется отношением предпорядка или предпорядком на А, если оно рефлексивно на и транзитивно.

Примеры. 1. Отношение делимости во множестве целых чисел не является порядком. Однако оно рефлексивно и транзитивно, значит является предпорядком.

2. Отношение логического следования является предпорядком на множестве формул логики высказываний.

Линейный порядок. Важным частным случаем порядка является линейный порядок.

ОПРЕДЕЛЕНИЕ. Отношение порядка на множестве называется отношением линейного порядка или линейным порядком на , если оно связанно на , т. е. для любых х, у из А

Отношение порядка, не являющееся линейным, обычно называют отношением частичного порядка или частичным порядком.

Примеры. 1. Отношение «меньше» на множестве действительных чисел есть отношение линейного порядка.

2. Отношение порядка, принятое в словарях русского языка, называется лексикографическим. Лексикографический порядок на множестве слов русского языка есть линейный порядок.

3. Отношение включения на совокупности подмножеств данного множества М является частичным порядком, если М содержит не менее двух различных элементов.

Одно и то же множество можно линейно упорядочить различными отношениями порядка. Так, например, на непустом конечном множестве М, состоящем из элементов, можно ввести различных линейных порядков.