Изоморфизмы упорядоченных множеств — различия между версиями
Notantony (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 24 промежуточные версии 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( | + | <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> , которая рано или поздно должна оборваться, | + | |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> Линейно упорядоченное множество называют | |statement=Любые два счётных плотных<ref> Линейно упорядоченное множество называют | ||
− | плотным, если в нём нет соседних элементов (то есть между любыми двумя есть третий). </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>. Мы можем это сделать, | + | |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>. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
}} | }} | ||
− | |||
== Примеры == | == Примеры == | ||
− | Множество рациональных чисел интервала <tex> (a,b) </tex> и множество <tex> Q </tex> изоморфны. | + | *Любые равные конечные подмножества натуральных чисел изоморфны по [[#th1|теореме 1]]. |
+ | *Множество рациональных чисел некоторого интервала <tex> (a,b) </tex> и множество <tex> \mathbb{Q} </tex> изоморфны по [[#th2|теореме 2]]. | ||
+ | *Тождественное отображение всегда является автоморфизмом. | ||
+ | *Не существует автоморфизма упорядоченного множества <tex> \mathbb{N} </tex> натуральных чисел, отличного от тождественного. Для <tex> \mathbb{Z} </tex> это утверждение уже, очевидно, неверно. | ||
+ | *Для неотрицательных вещественных чисел операция извлечения корня является автоморфизмом. | ||
== См. также == | == См. также == | ||
* [[Отношение порядка|Отношение порядка]] | * [[Отношение порядка|Отношение порядка]] | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Примeчания== | ==Примeчания== | ||
<references/> | <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
Определение: |
Два частично упорядоченных множества и называются изоморфными (англ. isomorphic), если между ними существует изоморфизм (англ. isomorphism) — взаимно однозначное соответствие, сохраняющее порядок.
Более формально, биекция |
Определение: |
Взаимно однозначное отображение частично упорядоченного множества в себя, являющееся изоморфизмом, называют автоморфизмом (англ.automorphism). |
Изоморфизм конечных множеств
Теорема (1): |
Конечные линейно упорядоченные множества из одинакового числа элементов изоморфны. |
Доказательство: |
Конечное линейно упорядоченное множество всегда имеет наименьший элемент. Возьмём любой элемент | . Если он не наименьший, возьмём любой меньший него . Если и он не наименьший, ещё меньший — и так далее. Получим убывающую последовательность , которая рано или поздно должна оборваться, так как множество конечное. Присвоим наименьшему элементу номер . Из оставшихся снова выберем наименьший элемент и присвоим ему номер . Будем повторять эту операцию, пока в множестве не останется непомеченных элементов. Таким образом, мы доказали, что любое такое множество из элементов изоморфно множеству . Значит, между двумя конечными линейно упорядоченными множествами из одинакового числа элементов можно построить биекцию.
Изоморфизм счетных множеств
Теорема (2): |
Любые два счётных плотных[1] линейно упорядоченных множества без наибольшего и наименьшего элементов изоморфны. |
Доказательство: |
Пусть | и — данные множества. Будем строить соответствие пошагово. Пусть мы сделали некоторое соответствие для подмножеств и из элементов. Возьмем любой элемент одного из множеств (для определенности ), который не вошел в . Посмотрим, в каком отношении он находится со всеми элементами из . Он оказался либо наибольшим элементом, либо наименьшим элементом, либо стоящим между некоторыми элементами и . Найдем элемент в , находящийся в таком же отношении со всеми элементами . Мы можем это сделать, так как — плотное множество без наибольшего и наименьшего элементов. Будем считать эти два элемента эквивалентными. Тогда, мы научились получать из соответствия для элементов соответствие для элемента. Чтобы в пределе получить соответствие для всех элементов, воспользуемся счетностью множеств. Пронумеруем все элементы и на каждом четном шаге будем выбирать еще не взятый элемент из множества с наименьшим номером, а на нечетном — из .
Примеры
- Любые равные конечные подмножества натуральных чисел изоморфны по теореме 1.
- Множество рациональных чисел некоторого интервала теореме 2. и множество изоморфны по
- Тождественное отображение всегда является автоморфизмом.
- Не существует автоморфизма упорядоченного множества натуральных чисел, отличного от тождественного. Для это утверждение уже, очевидно, неверно.
- Для неотрицательных вещественных чисел операция извлечения корня является автоморфизмом.
См. также
Примeчания
- ↑ Линейно упорядоченное множество называют плотным, если в нём нет соседних элементов (то есть между любыми двумя есть третий).