Теорема 12. Конечные линейно упорядоченные множества из одинакового числа элементов изоморфны. Доказательство

для любых элементов (слева знак обозначает порядок в множестве , справа - в множестве ).

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

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

Доказательство. Конечное линейно упорядоченное множество всегда имеет наименьший элемент (возьмем любой элемент; если он не наименьший, возьмем меньший, если и он не наименьший, еще меньший - и так далее; получим убывающую последовательность , которая рано или поздно должна оборваться). Присвоим наименьшему элементу номер . Из оставшихся снова выберем наименьший элемент и присвоим ему номер и так далее. Легко понять, что порядок между элементами соответствует порядку между номерами, то есть что наше множество изоморфно множеству .

95. Докажите, что множество всех целых положительных делителей числа с отношением " быть делителем" в качестве отношения порядка изоморфно множеству всех подмножеств множества , упорядоченному по включению.

96. Будем рассматривать финитные последовательности натуральных чисел, то есть последовательности, у которых все члены, кроме конечного числа, равны . На множестве таких последовательностей введем покомпонентный порядок: , если при всех . Докажите, что это множество изоморфно множеству всех положительных целых чисел с отношением " быть делителем" в качестве порядка.

Взаимно однозначное отображение частично упорядоченного множества в себя, являющееся изоморфизмом, называют автоморфизмом частично упорядоченного множества . Тождественное отображение всегда является автоморфизмом, но для некоторых множеств существуют и другие автоморфизмы. Например, отображение прибавления единицы ( ) является автоморфизмом частично упорядоченного множества целых чисел (с естественным порядком). Для множества натуральных чисел та же формула не дает автоморфизма (нет взаимной однозначности).

97. Покажите, что не существует автоморфизма упорядоченного множества натуральных чисел, отличного от тождественного.

98. Рассмотрим множество всех подмножеств некоторого - элементного множества , частично упорядоченное по включению. Найдите число автоморфизмов этого множества.

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

Вот несколько примеров равномощных, но не изоморфных линейно упорядоченных множеств (в силу теоремы 12 они должны быть бесконечными).

• 
  Отрезок (с обычным отношением порядка) не изоморфен множеству , так как у первого есть наибольший элемент, а у второго нет. (При изоморфизме наибольший элемент, естественно, должен соответствовать наибольшему.)
  
• 
  Множество (целые числа с обычным порядком) не изоморфно множеству (рациональные числа). В самом деле, пусть является изоморфизмом. Возьмем два соседних целых числа, скажем, и . При изоморфизме им должны соответствовать какие - то два рациональных числа и , причем , так как . Но тогда рациональным числам между и должны соответствовать целые числа между и , которых нет.
  
• 
  Более сложный пример - множества и . Возьмем в две копии нуля (из той и другой компоненты); мы обозначали их и . При этом . При изоморфизме им должны соответствовать два целых числа и , для которых . Тогда всем элементам между и (их бесконечно много: , , , , , , ) должны соответствовать числа между и - но их лишь конечное число.
  

00. Докажите, что линейно упорядоченные множества и (с описанным выше порядком) не изоморфны.

101. Будут ли изоморфны линейно упорядоченные множества и ?

102.Будут ли изоморфны линейно упорядоченные множества и ?

Отображение осуществляет изоморфизм между интервалами и . Но уже не так просто построить изоморфизм между множествами рациональных точек этих интервалов (то есть между и ), поскольку умножение на переводит рациональные числа в иррациональные. Тем не менее изоморфизм построить можно. Для этого надо взять возрастающие последовательности рациональных чисел и , сходящиеся соответственно к и и построить кусочно - линейную функцию , которая переводит в и линейна на каждом из отрезков (рис.7.1 ). Легко понять, что она будет искомым изоморфизмом.

103. Покажите, что множество рациональных чисел интервала и множество изоморфны. (Указание: здесь тоже можно построить ломаную; впрочем, у этой задачи есть и другое решение, которое начинается с того, что функция переводит рациональные числа в рациональные.)

Более сложная конструкция требуется в следующей задаче (видимо, ничего проще, чем сослаться на общую теорему 13, тут не придумаешь).

104. Докажите, что множество двоично - рациональных чисел интервала изоморфно множеству . (Число считается двоично - рациональным, если оно имеет вид , где - целое число, а - натуральное.)

Чтобы в пределе получить изоморфизм между множествами и , мы должны позаботиться о том, чтобы все элементы обоих множеств были рано или поздно охвачены. Это можно сделать так: поскольку каждое из множеств счетно, пронумеруем его элементы и будем выбирать неохваченный элемент с наименьшим номером (на нечетных шагах - из , на четных - из ). Это соображение завершает доказательство.

105. Сколько существует неизоморфных счетных плотных линейно упорядоченных множеств (про наименьший и наибольший элементы ничего не известно). (Ответ: .)

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

Доказательство этого утверждения происходит так же, как и в теореме 13 - с той разницей, что новые необработанные элементы берутся только с одной стороны (из данного нам множества), а пары к ним подбираются в множестве рациональных чисел.