logo
Pogrebnoj

§ 8. Упорядоченные множества

Среди разнообразных взаимодействий между элементами данного множества есть такие, которые сравнивают между собой элементы и определяют, какой из них «больше» и «меньше» в определенном смысле. Такие взаимодействия называются отношениями порядка. Дадим точное определение. Пусть X Ф0.

Определение

Отношением порядка или порядком на X, называется бинарное (т. е. двухместное) отношение P на X , которое имеет специальные свойства антисимметричности и транзитивности, т. е. выполнены аксиомы:

П 1. Антисимметричность

"a, be X [aPb a bPa ^ a = b]

П 2. Транзитивность

"a, b, ce X [aPb a bPc ^ aPc].

Для отношений порядка употребляется символ a < b.

Понятие порядка весьма общее. Более привычными и наиболее важными являются два специальных типа порядка:

  1. Нестрогий, если P рефлексивно.

  2. Строгий, если P антирефлексивно.

Поскольку для бинарных отношений на A из антирефлексивности и транзитивности следует

антисимметричность, то строгий порядок задается двумя аксиомами:

СП 1. Антирефлексивность

"a е X [aPa]

СП 2. Транзитивность

"a, b, cе X [aPb a bPc ^ aPc]

Пример

    1. R, a > b;

    2. R, a < b;

    3. X *0, b( x), А с 5.

Для строгого порядка будем употреблять обычную запись: a > b, a < b означает, что b > a .

Нестрогий порядок задается тремя аксиомами: НСП 1. Рефлексивность "a е А [aPa].

НСП 2. Антисимметричность. НСП 3. Транзитивность.

Нестрогий порядок будем обозначать a > b , a < b обозначает, что b > a

Примеры

      1. R, a > b .

      2. R, a < b.

      3. X *0,b(x), А с 5.

Строгий и нестрогий порядки очень тесно связаны и могут быть определены один через другой.

        1. если есть a > b, то a > b ^ a > b v a = b;

        2. если есть a > b, то a > b ^ a > b v a ^ b.

Это позволяет легко переходить от одного типа порядка к другому. Таким образом, задание одного типа автоматически означает наличие и другого типа.

Отношения порядка делятся также на линейный порядок, когда любые два элемента данного множества можно сравнить между собой:

"a, be X [a > b v b > a v a = b], и частичный, когда имеются несравнимые между собой элементы:

$a, bе X: a > b a b > a a a ^ b.

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

Отметим только, что линейный и частичный порядки можно показать на очень простых примерах.

          1. R, a > b - линейный;

          2. X ^ 0, b(x), А с В - частичный,

А, В - несравнимы в смысле порядка А с В.