§ 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-го типа.