Верещагин, Шень. Изоморфизмы.

[caxap]

97. Покажите, что не существует автоморфизма упорядоченного множества $\mathbb N$, отличного от тождественного.

Я извиняюсь, но, по-моему, такой автоморфизм есть. Пускай этим отображением 1 переходит в 2, а 2 в 1, остальные натуральные числа переходят в себя. Введём новый порядок: он схож с естественным для всех чисел, отличных от 1 и 2; для 1 и 2 он такой $2 \leqslant' 1$. Т. е. получим множество $\mathbb N$ с порядком $\leqslant'$ таким, что $2\leqslant' 1\leqslant' 3 \leqslant' 4 \leqslant' \cdots$. Чем не автоморфизм?

(P. S)

Про то, что отношения порядка могут быть разными в области определения и области значения изоморфизма (и, наверное, автоморфизма, в частности) написано в той же книге:

Верещагин, Шень писал(а):

биекция $f:A\to B$ называется изоморфизмом частично упорядоченных множеств $A$ и $B$, если

$$a_1\leqslant a_2\quad \iff \quad f(a_1) \leqslant f(a_2)$$

для любых элементов $a_1,a_2\in A$ (знак $\leqslant$ слева обозначает порядок в множестве $A$, справа -- в множестве $B$).

Далее даже идёт пример изоморфизма множества всех положительных делителей числа 30 с отношением "быть делителем" в качестве отношения порядка и множества $\{a,b,c\}$, упорядоченного по включению.

[paha]

автоморфизм: $x\le y$ равносильно $f(x)\le f(y)$

[caxap]

paha
Да, но ведь (см. P.S.) отношения $\leqslant$ могут быть разными. В книжке, правда, написано про изоморфизм. Но автоморфизм -- это изоморфизм в себя.

[id]

Уже не в себя, если порядок другой.

[paha]

caxap в сообщении #357382 писал(а):

то изоморфизм в себя.

а данный, конкретный порядок входит в "себя"

-- Ср сен 29, 2010 19:40:59 --

Минимальный элемент должен переходить в себя, следующий за ним поэтому тоже... и т.д.

[caxap]

id
Мне почему-то казалось, что "в себя" значит, что область определения равна области значения. Разве не так? (Странно, что в книжке об этом ничего не написано: "в себя" и всё.)

[Joker_vD]

Цитата:

что "в себя" значит, что область определения равна области значения

Ну да. Но тут-то область определения не просто $\mathbb N$, a $(\mathbb N, \leqslant)$.

[Ales]

А разве это не очевидно?

[caxap]

Ales в сообщении #357395 писал(а):

А разве это не очевидно?

Мне нет. Казалось, что отношение порядка -- это что-то "внешнее", что мы задаём (как хотим) и в области определения/значения не включается. Что ж, буду знать, спасибо.

Получается, изоморфизм $(\mathbb N,\leqslant_1)\to(\mathbb N,\leqslant_2)$ уже не автоморфизм?

[Ales]

caxap в сообщении #357400 писал(а):

Ales в сообщении #357395 писал(а):

А разве это не очевидно?

Мне нет. Казалось, что отношение порядка -- это что-то "внешнее", что мы задаём (как хотим) и в области определения/значения не включается. Что ж, буду знать, спасибо.

Получается, изоморфизм $(\mathbb N,\leqslant_1)\to(\mathbb N,\leqslant_2)$ уже не автоморфизм?

Автоморфизм упорядоченного множества - это взаимно однозначное отображение множества само на себя (образ равен прообразу), сохраняющее отношение порядка.

В задаче требуется доказать очевидное утверждение.

Но хотя это и очевидно, математик все же должен уметь сводить это утверждение к аксиомам. Или хотя бы представлять как это свести к аксиомам.

-- Ср сен 29, 2010 19:19:42 --

Ваш пример с двумя отношениями порядка - не автоморфизм.

[caxap]

Ales в сообщении #357404 писал(а):

Автоморфизм упорядоченного множества - это взаимно однозначное отображение множества само на себя (образ равен прообразу), сохраняющее отношение порядка.

В определении изоморфизма (из той же книги) так же сказано, "взаимно-однозначное ... сохраняющее порядок", но, тем не менее, потом идут примеры, где на области определения и значений порядки разные (напр. порядок "быть делителем" и "включается" -- см. P.S. в первом посте).

Ales в сообщении #357404 писал(а):

Но хотя это и очевидно, математик все же должен уметь сводить это утверждение к аксиомам. Или хотя бы представлять как это свести к аксиомам.

Я не математик И свести к аксиомам не смогу, т. к. не знаю их. Эта книжка предназначена для младшекурсников и старшеклассников и доказательства типа того, которое набросил paha вполне годится. Я уже в нём разобрался. Спасибо всем.

[Null]

биекция $f:A\to A$ называется автоморфизмом частично упорядоченных множеств $A$ и $A$, если

$$a_1\leqslant a_2\quad \iff \quad f(a_1) \leqslant f(a_2)$$

для любых элементов $a_1,a_2\in A$ (знак $\leqslant$ слева обозначает порядок в множестве $A$, справа -- в множестве $A$).

[caxap]

?

[caxap]

Спасибо за разъяснения
Ещё задачка. Проверьте, пожалуйста.

98. Рассмотрим множество $\mathcal P(A)$ всех подмножеств некоторого $k$-элементного множества $A$, частично упорядоченного по включению. Найдите число автоморфизмов этого множества.

(Извиняюсь, понял свою ошибку, сейчас попробую исправить)

При автоморфизме порядок сохранится (т. е. $a\subset b \iff \varphi(a)\subset \varphi(b)$ для любых $a,b$, где $\varphi$ -- автоморфизм), только если произойдёт "перестановка" элементов $\mathcal P(A)$ одной мощности. $j$-элементных множеств в $\mathcal P(A)$ имеется $\binom kj$, а способов "перестановки" элементов -- $\binom kj !$. По комбинаторному правилу умножения всего способов будет $\prod\limits_{j=0}^k \binom kj !$. Каждой "перестановке" соответствует автоморфизм, значит автоморфизмов столько же.

[caxap]

Что-то туго идёт... Но есть такое предположение, что число искомых автоморфизмов столько же, сколько и перестановок множества $A$, т. е. $k!$. Не знаю, как это строго объяснить, но идея такая: если мы будем учитывать порядок элементов в множествах (т. е. заменим множества на кортежи) и у нас имеется алгоритм, который будет из кортежа $A$ делает кортеж $\mathcal P(A)$, то если мы переставим элементы в $A$, то кортеж $\mathcal P(A)$ тоже изменится. Автоморфизм получается так: первый элемент исходного кортежа $\mathcal P(A)$ переводится в первый элемент "переставленного", второй элемент -- во второй элемент и т. д.

(Я плохо умею выражать свои мысли словами, поэтому пример)

Prelude> let p [] = [[]]; p (x:xs) = map (x:) (p xs) ++ p xs;

Prelude> p "abc"
["abc","ab","ac","a","bc","b","c",""]
Prelude> p "bca"
["bca","bc","ba","b","ca","c","a",""]

Т. е. перестановке $(a,b,c)\mapsto (b,c,a)$ соответсвует автоморфизм $\varphi$ такой, что

$$\begin{gathered} \{a,b\}\mapsto \{b,c\};\quad \{a,c\}\mapsto \{a,b\};\quad \{b,c\}\mapsto \{a,c\};\\ \{a\}\mapsto \{b\};\quad \{b\}\mapsto \{c\};\quad \{c\}\mapsto \{a\};\\ \varnothing\mapsto \varnothing; \quad\{a,b,c\}\mapsto\{a,b,c\}. \end{gathered}$$