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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 30 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition=Два [[Отношение порядка|частично упорядоченных]] множества <tex>A</tex> и <tex>B</tex> называются '''изоморфными''' (англ. ''isomorphic''), если между ними существует взаимно однозначное соответствие, сохраняющее порядок.
+
|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_1)</tex>
+
<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'').
 +
}}
 +
 
== Изоморфизм конечных множеств ==
 
== Изоморфизм конечных множеств ==
 
{{Теорема
 
{{Теорема
|statement=Конечные линейно упорядоченные множества из одинакового числа элементов изоморфны.
+
|id=th1
|proof=Конечное линейно упорядоченное множество всегда имеет наименьший элемент. Возьмём любой элемент <tex>x_1</tex>. Если он не наименьший, возьмём любой меньший него <tex>x_2</tex>. Если и он не наименьший, ещё меньший — и так далее. Получим убывающую последовательность <tex> x_1 > x_2 > \dots </tex> , которая рано или поздно должна оборваться, т.к. множество конечное. Присвоим наименьшему элементу номер 1. Из оставшихся снова выберем наименьший элемент и присвоим ему номер 2. Будем повторять эту операцию, пока в множестве не останется непомеченных элементов. Таким образом, мы доказали, что любое множество из <tex> n </tex> элементов изоморфно множеству <tex> \{ 1,2,\dots,n \} </tex>
+
|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>. Значит, между двумя конечными линейно упорядоченными множествами из одинакового числа элементов можно построить биекцию.
 
}}
 
}}
  
 
== Изоморфизм счетных множеств ==
 
== Изоморфизм счетных множеств ==
 
 
{{Теорема
 
{{Теорема
|statement=Любые два счётных плотных линейно упорядоченных множества без наибольшего и наименьшего элементов изоморфны.
+
|id=th2
|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> y </tex> <tex> B </tex>, находящийся в таком же отношении со всеми элементами <tex> B_n </tex>. Мы можем это сделать, т.к. <tex> B </tex> — плотное множество без максимального и минимального элементов. Будем считать эти два элемента эквивалентными. Тогда, мы научились получать из соответствия для <tex> n </tex> элементов соответствие для <tex> n+1 </tex> элемента. Чтобы в пределе получить соответствие для всех элементов, воспользуемся счетностью множеств. Пронумеруем все элементы и на каждом четном шаге будем выбирать еще взятый элемент из множества <tex> A </tex>, а на нечетном — из <tex> B </tex>.
+
|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 — Линейно упорядоченное множество]]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Отношения]]

Текущая версия на 19:44, 4 сентября 2022

Определение:
Два частично упорядоченных множества [math]A[/math] и [math]B[/math] называются изоморфными (англ. isomorphic), если между ними существует изоморфизм (англ. isomorphism) — взаимно однозначное соответствие, сохраняющее порядок.
Более формально, [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_2)[/math]


Определение:
Взаимно однозначное отображение частично упорядоченного множества в себя, являющееся изоморфизмом, называют автоморфизмом (англ.automorphism).


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

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

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

Теорема (2):
Любые два счётных плотных[1] линейно упорядоченных множества без наибольшего и наименьшего элементов изоморфны.
Доказательство:
[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] 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]

Примеры

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

См. также

Примeчания

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

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