§ 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), А с В - частичный,

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

§ 9. Вполне упорядоченные множества Определение

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

Примеры

1) N вполне упорядочено;

2. Z - не вполне упорядочено: - N с Z не имеет наименьшего элемента;

3. Q, I, R - не вполне упорядочены.

Легко видеть, что каждое вполне упорядоченное множество является линейно упорядоченным. Действительно, "a, b e X,

рассмотрим { a, b} . Оно имеет наименьший элемент. Если это a, то a < b. Если это b, то b < a. В обоих случаях a, b сравнимы и порядок линейный.

Среди функций, действующих в упорядоченных множествах, естественно, наиболее важны те, что согласованы с отношением порядка.

Пусть A, B - упорядоченные множества, f: A ® B. Если

"a, be A [a> b ^ f (a) > f(b)], то функция f называется

изотонной функцией или порядковым гомоморфизмом. Если f - биекция A на B и взаимно изотонна, то f - называется порядковым изоморфизмом множеств A, B. Эти множества в таком случае называются порядково изоморфными, или подобными между собой. Запись: A ~ B.

Поскольку функция подобия есть биекция, то A ~ B ^ A = B.

Подобие есть более сильное условие, чем равномощность. Понятно, что подобие множеств есть отношение эквивалентности.

Аналогично мощности, то общее, что присущее каждому множеству из класса подобных множеств, называется

порядковым типом множества. Запись: A.

Порядковым типом n -элементного линейно упорядоченного (тогда оно вполне упорядоченно) является число

n e N, n > 1,0 ::= 0,{a}::= 1. Таким образом, число множества N₀

является порядковым типом.

В линейно упорядоченном множестве A можно ввести обратный (инверсный) порядок: a < b заменяется на b < a. Полученное упорядоченное множество обозначается A *. Ясно, что (A *)* = A. Для конечных множеств n* = n. Далее укажем обозначение для порядковых типов основных числовых множеств.

N = w, N * = w*. Ясно, что w* ФЮ, т. к. в N порядок полный, а в N * - нет. Z = ж,ж* = ж. Q = h,h* = h R = 1,1* = 1.

Аналогом подмножества непустого множества является понятие отрезка упорядоченного множества. Отрезком упорядоченного множества A , определенным элементом a e A , называется упорядоченное множество A_a = {xe A: x< a}. Если

b < a, то, очевидно, (A_a)_b = A_b. Поставив в соответствие "a e A его отрезок A_a, получим подобие A и {A_a}_aeA.

Пусть имеется дизъюнктное семейство {A_i }_ieI упорядоченных множеств по упорядоченному семейству индексов I, A = u A_t. A можно упорядочить. Если

ie I

ae A_t, be A.,i > j, то считаем a > b. Порядковый тип множества A = u A_i называется сумой порядковых типов

ieI

A, i e y. В частности, A u B и B u A есть разные упорядоченные множества, их порядковые типы, вообще говоря, различны.

Примеры

1. 1 + w=w и вообще, n +w=w, т. к. множества

^an ...^{, a}m ^{} и {b}Ц^, К.^ ^bn^{, a}l^{, a}2 ^,."^,> ^am^,.^{} по}д^обны;

2. w+ n Ф w, т. к. w+ n есть порядковый тип множества

^{al^,..^{, a}m^,...^, ^ ^b2^,...^{, b}n ^};

3. ю* +ю = ж, также ю* +юф w+w*;

4. 1 +1 +1 есть порядковый тип множества [ a, b ].

Сравнение порядковых типов основано на понятии «короче».

Если А ~ В_ь, то говорят, что А короче В, тогда, если А = a,

В = Ь, считают a < b.

Оказывается, что из двух вполне упорядоченных множеств одно подобно другому или отрезку другого, т. е. a < Ь, a = b, или a > b.

Порядковый тип вполне упорядоченного множества называется порядковым, или ординальным числом. Итак, 0 и л е N есть одновременно и кардинальные, и ординальные числа.

с - порядковое число. с*, p,h,1 - не порядковые числа, т. к. это порядковые типы не вполне упорядоченных множеств.

Каждое множество порядковых чисел вполне упорядоченно. Аналогом отсутствия наибольшей мощности есть такой факт: если a - множество порядковых чисел, то существует порядковое число a > a_i. a +1 есть первое, следующее за a .

Последнее предшествующее есть не всегда, например, для с, т. е. есть числа 1-го и 2-го типа.