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

2018-05-29T14:52:08Z

31.173.80.70:

{{Определение
|definition=Два [[Отношение порядка|частично упорядоченных]] множества <tex>A</tex> и <tex>B</tex> называются '''изоморфными''' (англ. ''isomorphic''), если между ними существует '''изоморфизм''' (англ. ''isomorphism'') — взаимно однозначное соответствие, сохраняющее порядок.
<br>Более формально, <tex> \exists </tex> биекция <tex> f:A \rightarrow B : \forall \, a_1,a_2 \in A : a_1 \leqslant a_2 \Leftrightarrow f(a_1)\leqslant f(a_2)</tex>
}}
{{Определение
|definition=Взаимно однозначное отображение частично упорядоченного множества в себя, являющееся изоморфизмом, называют '''автоморфизмом''' (англ.''automorphism'').
}}

== Изоморфизм конечных множеств ==
{{Теорема
|id=th1
|about=1
|statement=Конечные [[Отношение порядка|линейно упорядоченные]] множества из одинакового числа элементов изоморфны.
|proof=Конечное линейно упорядоченное множество всегда имеет наименьший элемент. Возьмём любой элемент <tex>x_1</tex>. Если он не наименьший, возьмём любой меньший него <tex>x_2</tex>. Если и он не наименьший, ещё меньший — и так далее. Получим убывающую последовательность <tex> x_1 > x_2 > \dots </tex> , которая рано или поздно должна оборваться, так как множество конечное. Присвоим наименьшему элементу номер <tex> 1 </tex>. Из оставшихся снова выберем наименьший элемент и присвоим ему номер <tex>2</tex>. Будем повторять эту операцию, пока в множестве не останется непомеченных элементов. Таким образом, мы доказали, что любое такое множество из <tex> n </tex> элементов изоморфно множеству <tex> \{ 1,2,\dots,n \} </tex>. Значит, между двумя конечными линейно упорядоченными множествами из одинакового числа элементов можно построить биекцию.
}}

== Изоморфизм счетных множеств ==
{{Теорема
|id=th2
|about=2
|statement=Любые два счётных плотных<ref> Линейно упорядоченное множество называют
плотным, если в нём нет соседних элементов (то есть между любыми двумя есть третий). </ref> [[Отношение порядка|линейно упорядоченных]] множества без наибольшего и наименьшего элементов изоморфны.
|proof=Пусть <tex> A </tex> и <tex> B </tex> — данные множества. Будем строить соответствие пошагово. Пусть мы сделали некоторое соответствие для подмножеств <tex> A_n \subset A </tex> и <tex> B_n \subset B </tex> из <tex> n </tex> элементов. Возьмем любой элемент одного из множеств (для определенности <tex> A </tex>), который не вошел в <tex> A_n </tex>. Посмотрим, в каком отношении он находится со всеми элементами из <tex> A_n </tex>. Он оказался либо наибольшим элементом, либо наименьшим элементом, либо стоящим между некоторыми элементами <tex> a_i </tex> и <tex> a_{i+1} </tex>. Найдем элемент в <tex> B </tex>, находящийся в таком же отношении со всеми элементами <tex> B_n </tex>. Мы можем это сделать, так как <tex> B </tex> — плотное множество без наибольшего и наименьшего элементов. Будем считать эти два элемента эквивалентными. Тогда, мы научились получать из соответствия для <tex> n </tex> элементов соответствие для <tex> n+1 </tex> элемента. Чтобы в пределе получить соответствие для всех элементов, воспользуемся счетностью множеств. Пронумеруем все элементы и на каждом четном шаге будем выбирать еще не взятый элемент из множества <tex> A </tex> с наименьшим номером, а на нечетном — из <tex> B </tex>.
}}

== Примеры ==
*Любые равные конечные подмножества натуральных чисел изоморфны по [[#th1|теореме 1]].
*Множество рациональных чисел некоторого интервала <tex> (a,b) </tex> и множество <tex> \mathbb{Q} </tex> изоморфны по [[#th2|теореме 2]].
*Тождественное отображение всегда является автоморфизмом.
*Не существует автоморфизма упорядоченного множества <tex> \mathbb{N} </tex> натуральных чисел, отличного от тождественного. Для <tex> \mathbb{Z} </tex> это утверждение уже, очевидно, неверно.
*Для неотрицательных вещественных чисел операция извлечения корня является автоморфизмом.

== См. также ==
* [[Отношение порядка|Отношение порядка]]

==Примeчания==
<references/>

== Источники информации ==
*[http://www.mccme.ru/free-books/shen/shen-logic-part1-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. 4-е изд., доп., М: МЦНМО, 2012]
* [[wikipedia:ru:Частично_упорядоченные_множества| Wikipedia — Частично упорядоченные множества]]
* [[wikipedia:ru:Линейно_упорядоченное_множество| Wikipedia — Линейно упорядоченное множество]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Отношения]]

Викиконспекты - Вклад участника [ru]

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