Глава девятая. УПОРЯДОЧЕННЫЕ И ВПОЛНЕ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА

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

Множество называется упорядоченным или линейно упорядоченным, если на его элементах определено отношение подчиненное следующим условиям:

1. Для любых двух элементов либо либо либо

2. Для двух элементов имеет место одно и только одно из соотношений:

3. Из следует

Если предполагаются выполненными лишь требования 2 и 3, то множество называется частично упорядоченным или полуупорядоченным. Один важный класс полуупорядоченных множеств изучается в теории структур. См. по этому поводу Биркгоф Г. Теория структур. — М.: ИЛ, 1952.

Если то говорят, что а предшествует следует за а или что а находится перед после а.

Из отношения определяется несколько производных отношений:

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

Если некоторое множество упорядочено или частично упорядочено, то и каждое его подмножество упорядочено или соответственно частично упорядочено тем же самым отношением.

Может случиться, что упорядоченное или полуупорядоченное множество обладает «первым элементом», который предшествует всем остальным. Например, таково число 1 в ряду натуральных чисел.

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

Примеры. 1. Каждое упорядоченное конечное множество является вполне упорядоченным.

2. Ряд натуральных чисел вполне упорядочен, потому что в любом непустом подмножестве множества натуральных чисел имеется первый элемент.

3. Множество целых чисел в «естественном» порядке не является вполне упорядоченным, потому что в нем самом нет первого элемента. Однако его можно вполне упорядочить, если расположить его элементы, например, так:

или, например, так:

где все положительные числа предшествуют остальным.

(см. скан)

Пусть подмножество частично упорядоченного множества Если все элементы х из удовлетворяют условию то называется верхней границей множества Если в существует наименьшая верхняя граница так что для всех других верхних границ выполнено условие то является однозначно определенной границей и называется верхней гранью множества

Примеры. 1. Верхняя грань множества отрицательных чисел в поле рациональных чисел равна нулю. 2. Множество натуральных чисел не имеет в верхней границы и, конечно, не имеет верхней грани. 3. Множество рациональных чисел х со свойством имеет в верхнюю границу 2, но не имеет верхней грани. Однако, если присоединить к вещественное число то множество приобретает верхнюю грань