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

[Ales]

Тоже думаю, что число перестановок. Но доказать это можно, используя факт, что подмножество, состоящее из одного элемента, должно перейти в подмножество, состоящее из одного элемента.

[caxap]

То, что автоморфизм должен каким-то образом переставлять элементы $\mathcal P(A)$ одной мощности, я уже понял. Но нельзя просто переставить два любых элемента одной мощности (как я пытался делать в моём первом "доказательстве"), т. к. это "нарушит порядок" во всем множестве. Надо их переставлять "согласовано". Можно каждой перестановке $A$ (каждой биекции $A\to A$) сопоставить автоморфизм $\mathcal P(A)$ (в крайнем случае, это можно доказать глупым способом, как я писал: заменяя множества кортежами, построив алгоритм составления кортежа $\mathcal P(A)$ из $A$ и т. д.). Но как доказать, что других автоморфизмов нет?

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

[Хорхе]

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

Хотелось бы услышать советы от гуру, типа Хорхе, id, paha и др.

(Оффтоп)

Разве можно проигнорировать такую лесть?

Да, Ваш ответ $k!$ правильный. И ключевая идея имеено в том, что одноэлементные множества переходят в одноэлементные. Дальше надо доказать "согласованность". Есть много способов. Я, например, рассуждаю так: для подмножества $B=\{x_1,\dots,x_l\}\in A$ можно написать $B=\bigvee_{j=1}^l \{x_j\}$ ($\bigvee$ обозначает наименьший элемент, который не меньше данных; чтобы он был корректно определен, чум должен быть решеткой, что выполнено для булеана). Думаю, Вы сможете теперь завершить доказательство.

[caxap]

Хорхе в сообщении #358277 писал(а):

для подмножества $B=\{x_1,\dots,x_l\}\in A$ можно написать $B=\bigvee_{j=1}^l \{x_j\}$ ($\bigvee$ обозначает наименьший элемент, который не меньше данных; чтобы он был корректно определен, чум должен быть решеткой, что выполнено для булеана).

Если честно, ничего не понял Ещё смущает $\in A$ (имеется в виду $\subset A$ или $\in \mathcal P(A)$?).

Попробую ещё раз по своему. Одноэлементное множество $\{a_i\}\in \mathcal P(A)$ должно переходить в одноэлементное. Каждая такая перестановка $\{a_i\}\mapsto \{a_j\}$ однозначно "восстанавливает" всё остальное множество $\mathcal P(A)$ так, чтобы оно было изоморфно исходному. Для этого восстановления надо заменить $a_i$ на $a_j$ (и наоборот) во всех множествах, в которые эти элементы включаются. Это выглядит как простое переименование $a_i$ в $a_j$ (и наоборот), поэтому порядок должен сохранится. Любую перестановку 1-элементных множеств в $\mathcal P(A)$ можно представить как совокупность таких попарных перестановок. Всего перестановок 1-элементных множеств $k!$; соответствующих автоморфизмов столько же.

Предположим теперь, что есть неучтённый автоморфизм, который не переставляет 1-элементные множества, а переставляет 2-элементные. Но если произойдёт такая перестановка $\{a_i,a_j\}\mapsto \{a_l,a_m\}$, то порядок не сохранится: до перестановки $\{a_i\}$ включался в первое множество $\{a_i,a_j\}$, а после перестановки в $\{a_i\}\not\subset\{a_l,a_m\}$. Значит это не автоморфизм.
Аналогично можно доказать, что невозможен автоморфизм, который не переставляет 1- и 2-элементные множества, а переставляет 3-элементные. И т. д.

Таким образом неучтённых автоморфизмов нет и их всего $k!$.

[Хорхе]

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

Ещё смущает $\in A$ (имеется в виду $\subset A$ или $\in \mathcal P(A)$?).

Да, очепятка. Оба Ваши предположения правильны.

-- Сб окт 02, 2010 19:01:33 --

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

Но если произойдёт такая перестановка $\{a_i,a_j\}\mapsto \{a_l,a_m\}$, то порядок не сохранится: до перестановки $\{a_i\}$ включался в первое множество $\{a_i,a_j\}$, а после перестановки в $\{a_i\}\not\subset\{a_l,a_m\}$. Значит это не автоморфизм.

Тут небольшая неточность: скажем, $a_i$ может входить в $\{a_l,a_m\}$, но тогда $a_j$ не входит.

А в целом правильно, у Вас большие успехи, поздравляю!

[caxap]

Хорхе в сообщении #358348 писал(а):

А в целом правильно

Спасибо!

Там в этой теме ещё несколько задачек, но они вроде бы попроще. Надо их добить

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

У $30$ такие делители: $1, 2, 3, 5,\ 6=2\cdot 3,\ 10=2\cdot 5,\ 15=3\cdot 5,\ 30=2\cdot 3\cdot 5$. Изоморфизм будет такой:

$$\begin{gathered} \{a\}\mapsto 2;\quad \{b\}\mapsto 3; \quad\{b\}\mapsto 5\\ \{a,b\}\mapsto 2\cdot 3=6;\quad\text{и т. д.}\\ \varnothing \mapsto 1;\quad \{a,b,c\}\mapsto 30;\quad \text{<<}|\text{>>}\mapsto \text{<<}\subset\text{>>} \end{gathered}$$

[Хорхе]

Слегка чересчур лаконично, но зато на этот раз без подсказок и без неточностей.

[caxap]

Спасибо, что проверили!

99. Покажите, что множество целых положительных чисел, частично упорядоченное отношением "$x$ делит $y$", имеет континуум различных автоморфизмов.

По основной теореме арифметики любое натуральное число можно представить как произведение каких-то простых чисел, причём единственным образом. Значит, как и в прошлой задаче, можно построить изоморфизм данного множества на $\mathcal P(\mathbb N)$. Количество автоморфизмов $\mathcal P(\mathbb N)$ равно числу способов перестановки одноэлементных подмножеств в нём. Т. е. нужно найти мощность множества функций из $\mathbb N$ на $\mathbb N$. А $|\mathbb N^{\mathbb N}|=\aleph_0^{\aleph_0}=\mathfrak c$.

[Хорхе]

Небольшая неточность: нас интересует не все $\mathbb N^{\mathbb N}$, а только биекции. Впрочем, биекций тоже континуум (это легко показать).

[caxap]

Хорхе
Да, я биекции и имел в виду. Ещё раз спасибо.

[caxap]

103. Покажите, что множество рациональных чисел интервала $(0,1)$ и множество $\mathbb Q$ изоморфны.

За основу возьмём функцию $x\mapsto 1/x$ (она переводит рациональные числа в рациональные: $\frac nm\mapsto \frac mn$). Чтобы это был изоморфизм из $(0,1)\cap\mathbb Q$ на $\mathbb Q$, надо сделать из неё возрастающую функцию на интервале $(0,1)$, которая стремится к $\pm \infty$, когда $x$ стремится соотв. к $1$ и $0$. Сначала отразим её относительно $Ox$ (заменим $x$ на $-x$). Затем правую ветвь поднимем на 2, чтобы она пересекла $Ox$ в точке $x=1/2$. Левую ветвь на столько же опускаем и ещё сдвигаем вправо на 1. Получается такой изоморфизм:

$$x\mapsto\begin{cases} -\frac 1x+2, & 0<x<\frac 12;\\ -\frac 1{x-1}-2, & \frac 12 \leqslant x < 1.\end{cases}$$

(Рисунок)

Рациональные числа переводятся в рациональные (в формуле происходят только рациональные операции: добавление и отнимание целых чисел, "оборачивание", замена знака).

[Хорхе]

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

[caxap]

Спасибо за проверку.

Хорхе в сообщении #358544 писал(а):

построил бы нечто кусочно линейное, что первым в голову приходит

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

[caxap]

104. Докажите, что множество двоично-рациональных чисел (вида $m/2^n$, $m\in \mathbb N$, $n\in \mathbb Z$) интервала $(0,1)$ изоморфно множеству $\mathbb Q$.

Уже известна теорема о том, что все плотные счётные лумы без наибольшего и наименьшего элемента изоморфны. Множество дв.-рац. чисел интервала $(0,1)$ счётно (биекция $\frac mn \mapsto \frac m{2^n}$, $|\mathbb Q|=\aleph_0$), плотно (между любыми дв.-рац. числами $m/2^n$ и $m'/2^{n'}$ есть третье -- их среднее арифметическое: $\frac 12 \frac{m 2^{n'}+m' 2^n}{2^n 2^{n'}}=\frac {m 2^{n'}+m' 2^n}{2^{n+n'+1}}$) без наиб. и наим. элемента (можно неограниченно приблежаться дв.-рац. числами как к нулю, так и к единице). По указанной теореме это множество изоморфно $\mathbb Q$ (которое тоже удовлетворяет всем условиям, но это, по-моему, очевидно).

100. Докажите, что лумы $\mathbb Z\times\mathbb N$ и $\mathbb Z\times\mathbb Z$ не изоморфны. (Порядок такой: сначала сравниваются вторые координаты, а если они равны, то первые.)

А вот с этой что-то не разберусь никак. Пробовал от противного (предположил, что изоморфизм есть). Но никакое противоречие не удалось найти.

[Хорхе]

Пока собирался уточнять условие сотой задачи, стрелки превратились в крестики.

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