Порядковые числа

[bubu gaga]

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

Даны два разных множества $M$ и $M'$. У нас есть отношения частичного порядка $R_\omega \subset M \times M$ и $R_{\omega'} \subset M' \times M'$. Изоморфизмом называется биективное отображение для которого

$$ a \; \omega \; b \qquad \Leftrightarrow \qquad f(a) \; \omega' \; f(b)$$

.

Собственно что нам мешает переопределить $\omega'$ следующим образом?

$$a' \; \omega' \; b' \qquad \Leftrightarrow \qquad f^{-1}(a') \; \omega \; f^{-1}(b') $$

Тогда любое биективное отображение является изоморфизмом, и любые два множества с биективной функцией из одного в другое являются изоморфными? Чего я не вижу? Спасибо.

[Cave]

bubu gaga
Мы не имеем права переопределять порядок. Изначально заданы два множества и частичные порядки на них. После этого упорядоченным множеством называется пара из двух объектов - множества и частичного порядка на нём.
Изоморфизм определяется для частично упорядоченных множеств (то есть он, конечно, определяется и для многих других структур, но мы говорим именно про эти), а биекция - для произвольных множеств.

[Руст]

Так как f биективное, то оба условия эквивалентны.

[ewert]

bubu gaga писал(а):

Тогда любое биективное отображение является изоморфизмом, и любые два множества с биективной функцией из одного в другое являются изоморфными? Чего я не вижу? Спасибо.

Попробую немного другими словами. Любое отображение $f:\;M\mapsto M'$ индуцирует соответствующее отображение $F:\;M\!\times\!M\mapsto M'\!\times\!M'$, действующее по правилу: $F(x,y)=(f(x),f(y))$. Если $f$ биективно, то и $F$, конечно, тоже.

Однако теперь у нас наряду с $f$ есть еще два отношения (даже не обязательно порядка -- просто бинарные отношения) $R_{\omega}$ и $R_{\omega'}$. Т.е. два подмножества соответствующих декартовых произведений. И эти подмножества, в принципе, могут выбираться независимо друг от друга и от отображения $f$.

Так вот: $f$ называется изоморфизмом, если а) оно само по себе является биекцией и б) при этом соответствующее отображение $F$ между $R_{\omega}$ и $R_{\omega'}$ также оказывается биекцией. Ну а это уж как повезёт, разумеется.

[bubu gaga]

Следующий вопрос: если множества разной мощности, то биективной функции не существует. А если они одинаковой мощности? Как например доказать, что никакая функции не подойдёт? Все возможные отображения перебрать не получится, следовательно нужно доказать, что такое отображение не будет обладать заданными качествами. Но этих качеств только 2, биективность и сохранение порядка.

И они как мне кажется друг другу не особо противоречат. Вот почему мне так кажется. Грубо говоря нам нужна функция которая переводит $i$-ый по порядку элемент из $M$, в $i$-ый по порядку элемент в $M'$. Первым шагом берём любую биективную функцию $f: \; M \mapsto M'$ и пузырьковой сортировкой сортируем образ. Вот и функция.

Есть ли пример, как доказывается неизоморфность частично упорядоченных множеств?

[ewert]

bubu gaga писал(а):

Грубо говоря нам нужна функция которая переводит $i$-ый по порядку элемент из $M$, в $i$-ый по порядку элемент в $M'$.

Это ну очень грубо говоря. Тем самым подразумевается, что элементы множества можно перенумеровать, т.е. что оно конечно или счётно. Тогда действительно никаких проблем с равномощностью, но это -- очень уж частный случай.

[Narn]

bubu gaga писал(а):

Как например доказать, что никакая функции не подойдёт? Все возможные отображения перебрать не получится, следовательно нужно доказать, что такое отображение не будет обладать заданными качествами. Но этих качеств только 2, биективность и сохранение порядка.

И они как мне кажется друг другу не особо противоречат. Вот почему мне так кажется. Грубо говоря нам нужна функция которая переводит $i$-ый по порядку элемент из $M$, в $i$-ый по порядку элемент в $M'$. Первым шагом берём любую биективную функцию $f: \; M \mapsto M'$ и пузырьковой сортировкой сортируем образ. Вот и функция.

Есть ли пример, как доказывается неизоморфность частично упорядоченных множеств?

В частично упорядоченном множестве нельзя говорить об $i$-м элементе, так как там не все элементы обязаны быть сравнимы друг с другом. Простейший пример: $M=\{a,b,c\}$, $\omega = \{(a,b),(a,c)\}$, $\omega ' = \{(a,c),(a,b)\}$. В первом упорядоченном множестве два максимальных элемента, во втором один. Поэтому они не могут быть изоморфны.

Даже линейно упорядоченные множества (то есть ч.у. множества, в которых любые два элемента сравнимы друг с другом) не обязаны быть изоморфны. Например, целые числа и натуральные с естественным отношением порядка. В множестве натуральных чисел есть наименьший элемент, а в множестве целых его нет. Поэтому они не изоморфны. Здесь тоже нельзя говорить об $i$-м элементе.

Даже сделать множество вполне упорядоченным (то есть ввести на нем линейный порядок, при котором каждое непустое подмножество имеет минимальный элемент) можно разными, то есть неизоморфными способами (на бесконечном множестве). Возьмем натуральные числа и определим новое отношение порядка. Пусть на четных числах оно совпадает со стандартным, на нечетных тоже, и все нечетные числа больше всех четных. Формально: пусть $\omega$ состоит из пар $(a,b)$, где $a<b$ (это стандартный порядок), а $\omega '$ состоит из пар $(a,b)$, где либо $a<b$ и числа одинаковой четности, или $a$ четное и $b$ нечетное. Эти упорядоченные множества ($(\mathbb{N}, \omega)$ и $(\mathbb{N}, \omega ')$) не изоморфны, так как во втором имеются элементы, которым предшествует бесконечно много элементов (например, 1), а в первом их нет. Даже здесь нельзя говорить об $i$-м элементе относительно порядка $\omega '$.

Во всех примерах $\omega$ и $\omega '$ имеют одинаковую мощность.

Вообще, изоморфные объекты - это объекты неразличимые. То есть все свойства, которые можно сформулировать через отношение порядка, должны быть у них одинаковы. Если одно из ч. у. множеств каким-то из этих свойств обладает, а второе нет, то они неизоморфны. Доказательство неизоморфности и заключается в указании таких свойств (типа "иметь два максимальных элемента", "иметь наибольший элемент", "быть вполне упорядоченным", и так далее).

А изоморфны всегда будут конечные линейно упорядоченные множества (если там $n$ элементов, то каждое такое множество изоморфно множеству первых $n$ натуральных чисел со стандартным отношением порядка). Здесь пройдет Ваше доказательство (можно взять первый элемент, второй и т.д.).

[bubu gaga]

Во-первых, спасибо всем за ответы!

Narn писал(а):

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

Во-вторых, самая большая моя проблема с теорией множеств, это то, что на таком уровне абстракции я едва различаю, что дано, что надо доказывать, а что является очевидным. Можно я попробую применить упомянутый способ доказательства, а Вы проверите?

Есть ряд натуральных чисел. Это вполне упорядоченное множество, и это даётся по определению. Ничего доказывать не надо. У ряда натуральных чисел есть наименьший элемент. Это часть определения полной упорядоченности. Допустим это множество изоморфно множеству целых чисел. Тогда полная упорядоченность передаётся (видимо потому что полная упорядоченность является частным случаем частичной упорядоченности?) с ряда натуральных чисел, на множество целых чисел. Тогда у ряда целых чисел должен появиться наименьший элемент, а это противоречит определению целых чисел.

Это похоже на правду?

[Narn]

bubu gaga писал(а):

Есть ряд натуральных чисел. Это вполне упорядоченное множество, и это даётся по определению. Ничего доказывать не надо. У ряда натуральных чисел есть наименьший элемент. Это часть определения полной упорядоченности. Допустим это множество изоморфно множеству целых чисел. Тогда полная упорядоченность передаётся (видимо потому что полная упорядоченность является частным случаем частичной упорядоченности?) с ряда натуральных чисел, на множество целых чисел. Тогда у ряда целых чисел должен появиться наименьший элемент, а это противоречит определению целых чисел.

Это похоже на правду?

Похоже, но, возможно, лучше писать формальнее: пусть $f : \mathbb{N} \to \mathbb{Z}$ - изоморфизм упорядоченных стандартным образом натуральных и целых чисел. То есть $f$ - биекция и $a<b$ тогда и только тогда, когда $f(a)<f(b)$. Наша задача - доказать, что такой биекции не существует. Рассмотрим $f(1)$ и $f(1)-1$. Так как $f(1)-1 < f(1)$, то $f^{-1}(f(1)-1)<1$. Но натурального числа, меньшего 1, не бывает. Все.

Мне непонятно, что Вы имеете в виду, говоря

bubu gaga писал(а):

Допустим это множество изоморфно множеству целых чисел. Тогда полная упорядоченность передаётся (видимо потому что полная упорядоченность является частным случаем частичной упорядоченности?) с ряда натуральных чисел, на множество целых чисел.

Передать-то полную упорядоченность можно (целые и натуральные числа равномощны, возьмем любую биекцию $f : \mathbb{N} \to \mathbb{Z}$ и объявим, что целое число $a$ предшествует целому $b$, если $f^{-1}(a)<f^{-1}(b)$. Например, можно так : $0<1<-1<2<-2<3<-3<\dots$. Но мы получили другой порядок, не тот, с которым мы рассматриваем целые числа. Посмотрите ещё раз сообщения Cave и ewert. Сейчас сам отредактирую свое сообщение, я там тоже неточно выражался.

[bubu gaga]

Narn писал(а):

Мне непонятно, что Вы имеете в виду, говоря

Я очень не точно выражаюсь, к моему сожалению.

Имелось в виду, что классы изоморфных между собой множеств отличаются лишь значениями элементов. Изоморфизм - это же сохранение формы. То есть если мы представим польностью упорядоченное множество, как набор ячеек, где в каждой из них записано значение оригинального ряда $M$, то $f$ даёт нам возможность поменять значения в этих ячейках на соответствующие значения из $M'$, да так, что никто не заметит разницы между полученным рядом и $M'$.

В Вашем примере, если мы заменим по $f$, то конечно оригинальное $\mathbb{Z}$ сильно отличается от "индуцированного" такой заменой.