Зорич. Теорема Шредера-Бернштейна.

[Slow]

Докажем, что если множества $X,Y,Z$ таковы, что $Z\subset Y\subset X$ и $|X|=|Z|$, то $|X|=|Y|$. Пусть $f:X \to Z$ - биекция. Тогда построим биекцию $g:X\to Y$
$\begin{equation*} g(x) = \begin{cases} f(x) &\text{если $x\in f^n(X)\setminus f^n(Y)$ для некоторого $n \in \mathbb{N}$}\\ x &\text{иначе} \end{cases} \end{equation*}$
Возьмем множество $X = \mathbb{N}$, $Z=\{ x\in \mathbb{N}| \text{x делится на 4} \}$, $Y=\{ x\in \mathbb{N}| \text{x делится на 2} \}$
$f(x)=4x$, тогда $g(1) = 1$, но $1\notin Y$. У меня уже от упражнений из Зорича мозг взрывается((.

[Padawan]

Это довольно трудная теорема. Возьмите и прочитайте её доказательство где-нибудь еще. В Колморове, Фомине, например.

[Slow]

Там же другое доказательство. Меня интересует именно это, потому что мне кажется что в Зориче ошибка.

[Xaositect]

А в Зориче натуральные числа с нуля? В данном случае надо учитывать в верхней альтернативе $f^0(X) \setminus f^0(Y) = X\setminus Y$.

[Slow]

Я правильно понимаю что мы оставляем на месте только элементы $f^n(Y\setminus Z)$?

[мат-ламер]

Кстати, тут на форуме были жалобы по поводу доказательства Зоричем этой теоремы. (Однако Зорич многократно переиздаётся.)

[Slow]

Дочитал Зорича до натуральных чисел, там они начинаются с единицы.

[gangstervano]

Посмотрите тут Теорема 1.4.3 [Дудаков С. М. Основы теории моделей.]

Это единственно доказательство которое я смог понять. В книге Колмогорова, Фомина как-то уж слишком поверхностно.

[ewert]

gangstervano в сообщении #1320705 писал(а):

В книге Колмогорова, Фомина как-то уж слишком поверхностно.

Колмогорова-Фомина никак не назовёшь поверхностными. Другое дело, что и в небрежности изложения им никак не откажешь, из-за чего д-во у них получилось не слишком внятным. Но как только попытаешься вникать -- идея становится очевидной, и идея эта весьма проста. Вообще их вариант доказательства, наверное, оптимален -- и коротко, и без ненужных изобретательств.

Идея такая (обозначения изменю на более разумные, ПМСМ). Берём любой $x_0\in X$ и вытягиваем из него цепочку прообразов: $y_0=g^{-1}(x_0)\in Y$, $x_1=f^{-1}(y_0)\in X$, $y_1=g^{-1}(x_1)\in Y$ и т.д. Эта цепочка может оборваться, если у какого-то элемента прообраза не окажется -- а может продолжаться неограниченно долго.

Порядком $l_{x_0}$ элемента $x_0$ назовём длину соответствующей цепочки, т.е. количество её звеньев. В частности, если у $x_0$ нет прообраза, то $l_{x_0}=0$. Для элементов $y_0\in Y$ понятие порядка вводится аналогично, только цепочка начинается с $f^{-1}$, а не с $g^{-1}$.

Теперь -- ключевое и вполне очевидное утверждение, которое Колмогоров-Фомин как-то зажевали, из-за чего их изложение доказательства сильно проиграло: $l_{f(x_k)}=l_{x_k}+1$ -- или, другими словами, применение функции к любому элементу удлинняет цепочку прообразов ровно на одно звено (в частности, бесконечная цепочка остаётся бесконечной). Естественно, для игреков всё ровно так же, с заменой $f$ на $g$.

Далее всё уже достаточно напрашивается. Изменение на единичку -- это, собственно, изменение чётности. Посему разбиваем $X$ на $X_0$ (элементы чётного порядка), $X_1$ (порядка нечётного) и $X_{\infty}$ (порядка бесконечного, т.е., собственно, неопределённой чётности). Для игреков -- аналогично.

Из-за увеличения порядка ровно на единичку функция $f$ инъективно переводит $X_1$ в $Y_0$, $X_0$ в $Y_1$ и $X_{\infty}$ в $Y_{\infty}$. В двух последних случаях -- это не только инъекция, но и биекция, т.к. для элементов на выходе длина цепочки не менее единицы и, следовательно, у них прообраз существует.

Для $f\colon X_1\mapsto Y_0$ -- это, конечно, не более чем инъекция (вообще говоря). Но зато биекцию между двумя этими множествами осуществляет функция $g$. Вот и всё.

Это -- очень лаконичное и без выкрутасов доказательство. Мне раньше читать его не доводилось, но вот сейчас вчитался -- и мне сильно понравилось.

Прочитать Дудакова не смог, он откровенный пижон. У него какое-то безумное нагромождение дополнительных конструкций и понятий, абсолютно не нужных для реализации основной идеи (как я её понял -- ведь понять её достоверно нет никакой возможности в силу безумия). Между тем та самая идея (как я её понял, ещё раз соррю) весьма тоже проста и привлекательна, и при этом не требует для своей реализации ничего, кроме минимальных, самых что ни на есть базовых понятий теории множеств. Реализация, правда, выйдет несколько длиннее, чем у К.-Ф., но оно того стоит: построение биекции окажется исключительно конструктивным.