Изоморфизмы упорядоченных множеств

Определение:

Два частично упорядоченных множества [math]A[/math] и [math]B[/math] называются изоморфными (англ. isomorphic), если между ними существует взаимно однозначное соответствие, сохраняющее порядок. Более формально, [math] \exists [/math] биекция [math] f:A \rightarrow B : \forall \, a_1,a_2 \in A : a_1 \leqslant a_2 \Leftrightarrow f(a_1)\leqslant f(a_1)[/math]

Изоморфизм конечных множеств

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Конечное линейно упорядоченное множество всегда имеет наименьший элемент. Возьмём любой элемент [math]x_1[/math]. Если он не наименьший, возьмём любой меньший него [math]x_2[/math]. Если и он не наименьший, ещё меньший — и так далее. Получим убывающую последовательность [math] x_1 \gt x_2 \gt \dots [/math] , которая рано или поздно должна оборваться, т.к. множество конечное. Присвоим наименьшему элементу номер 1. Из оставшихся снова выберем наименьший элемент и присвоим ему номер 2. Будем повторять эту операцию, пока в множестве не останется непомеченных элементов. Таким образом, мы доказали, что любое множество из [math] n [/math] элементов изоморфно множеству [math] \{ 1,2,\dots,n \} [/math]

[math]\triangleleft[/math]

Изоморфизм счетных множеств

Теорема:

Любые два счётных плотных линейно упорядоченных множества без наибольшего и наименьшего элементов изоморфны.

Доказательство:

[math]\triangleright[/math]

Пусть [math] A [/math] и [math] B [/math] — данные множества. Будем строить соответствие пошагово. Пусть мы сделали некоторое соответствие для подмножеств [math] A_n \subset A [/math] и [math] B_n \subset B [/math] из [math] n [/math] элементов. Возьмем любой элемент одного из множеств (для определенности [math] A [/math]), который не вошел в [math] A_n [/math]. Посмотрим, в каком отношении он находится со всеми элементами из [math] A_n [/math]. Он оказался либо наибольшим элементом, либо наименьшим элементом, либо стоящим между некоторыми элементами [math] a_i [/math] и [math] a_{i+1} [/math]. Найдем элемент [math] y [/math] [math] B [/math], находящийся в таком же отношении со всеми элементами [math] B_n [/math]. Мы можем это сделать, т.к. [math] B [/math] — плотное множество без максимального и минимального элементов. Будем считать эти два элемента эквивалентными. Тогда, мы научились получать из соответствия для [math] n [/math] элементов соответствие для [math] n+1 [/math] элемента. Чтобы в пределе получить соответствие для всех элементов, воспользуемся счетностью множеств. Пронумеруем все элементы и на каждом четном шаге будем выбирать еще взятый элемент из множества [math] A [/math], а на нечетном — из [math] B [/math].

[math]\triangleleft[/math]

См. также

• Отношение порядка
• Wikipedia — Линейно упорядоченное множество
• Wikipedia — Линейно упорядоченное множество

Источники информации

• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. 4-е изд., доп., М: МЦНМО, 2012
• Wikipedia — Частично упорядоченные множества