В книге Колмогорова, Фомина как-то уж слишком поверхностно.
Колмогорова-Фомина никак не назовёшь поверхностными. Другое дело, что и в небрежности изложения им никак не откажешь, из-за чего д-во у них получилось не слишком внятным. Но как только попытаешься вникать -- идея становится очевидной, и идея эта весьма проста. Вообще их вариант доказательства, наверное, оптимален -- и коротко, и без ненужных изобретательств.
Идея такая (обозначения изменю на более разумные, ПМСМ). Берём любой
![$x_0\in X$ $x_0\in X$](https://dxdy-04.korotkov.co.uk/f/7/9/4/794c6f1b3b189816a9973dda0d498a2482.png)
и вытягиваем из него цепочку прообразов:
![$y_0=g^{-1}(x_0)\in Y$ $y_0=g^{-1}(x_0)\in Y$](https://dxdy-04.korotkov.co.uk/f/b/5/e/b5e6a9acbeb27ebd495572a8a4f90be682.png)
,
![$x_1=f^{-1}(y_0)\in X$ $x_1=f^{-1}(y_0)\in X$](https://dxdy-03.korotkov.co.uk/f/e/0/5/e055d3917f76f38887bcf1d98bee7cb582.png)
,
![$y_1=g^{-1}(x_1)\in Y$ $y_1=g^{-1}(x_1)\in Y$](https://dxdy-03.korotkov.co.uk/f/a/2/7/a272b766fe07ca8225d8a0dbde6d1de682.png)
и т.д. Эта цепочка может оборваться, если у какого-то элемента прообраза не окажется -- а может продолжаться неограниченно долго.
Порядком ![$l_{x_0}$ $l_{x_0}$](https://dxdy-03.korotkov.co.uk/f/6/0/d/60d8af33f4b28f3d2d184f9fbb358cc782.png)
элемента
![$x_0$ $x_0$](https://dxdy-03.korotkov.co.uk/f/e/7/1/e714a3139958da04b41e3e607a54445582.png)
назовём длину соответствующей цепочки, т.е. количество её звеньев. В частности, если у
![$x_0$ $x_0$](https://dxdy-03.korotkov.co.uk/f/e/7/1/e714a3139958da04b41e3e607a54445582.png)
нет прообраза, то
![$l_{x_0}=0$ $l_{x_0}=0$](https://dxdy-04.korotkov.co.uk/f/7/5/4/754a84477329a5d37d31f4244b7f9fa382.png)
. Для элементов
![$y_0\in Y$ $y_0\in Y$](https://dxdy-03.korotkov.co.uk/f/2/7/7/277014232a447a0f3b7d25e8843a074682.png)
понятие порядка вводится аналогично, только цепочка начинается с
![$f^{-1}$ $f^{-1}$](https://dxdy-01.korotkov.co.uk/f/8/f/a/8fac22af20becca270bc855e487906cb82.png)
, а не с
![$g^{-1}$ $g^{-1}$](https://dxdy-04.korotkov.co.uk/f/3/8/d/38d63a2e3c8cc0fd6c8e5669ae00df7882.png)
.
Теперь -- ключевое и вполне очевидное утверждение, которое Колмогоров-Фомин как-то зажевали, из-за чего их изложение доказательства сильно проиграло:
![$l_{f(x_k)}=l_{x_k}+1$ $l_{f(x_k)}=l_{x_k}+1$](https://dxdy-04.korotkov.co.uk/f/b/e/6/be6daa70eb1560e1ab587e777fa6e8af82.png)
-- или, другими словами, применение функции к любому элементу удлинняет цепочку прообразов ровно на одно звено (в частности, бесконечная цепочка остаётся бесконечной). Естественно, для игреков всё ровно так же, с заменой
![$f$ $f$](https://dxdy-02.korotkov.co.uk/f/1/9/0/190083ef7a1625fbc75f243cffb9c96d82.png)
на
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
.
Далее всё уже достаточно напрашивается. Изменение на единичку -- это, собственно, изменение чётности. Посему разбиваем
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
на
![$X_0$ $X_0$](https://dxdy-01.korotkov.co.uk/f/0/7/4/07478cd102054dc58a97f6fd8df8470582.png)
(элементы чётного порядка),
![$X_1$ $X_1$](https://dxdy-01.korotkov.co.uk/f/4/a/0/4a0dab614eaf1e6dc58146666d67ace882.png)
(порядка нечётного) и
![$X_{\infty}$ $X_{\infty}$](https://dxdy-04.korotkov.co.uk/f/3/1/b/31b50d8a44bef7c023a54c823bcd5d2e82.png)
(порядка бесконечного, т.е., собственно, неопределённой чётности). Для игреков -- аналогично.
Из-за увеличения порядка ровно на единичку функция
![$f$ $f$](https://dxdy-02.korotkov.co.uk/f/1/9/0/190083ef7a1625fbc75f243cffb9c96d82.png)
инъективно переводит
![$X_1$ $X_1$](https://dxdy-01.korotkov.co.uk/f/4/a/0/4a0dab614eaf1e6dc58146666d67ace882.png)
в
![$Y_0$ $Y_0$](https://dxdy-03.korotkov.co.uk/f/2/a/d/2ad50bdc891a4fc6dba3ac6e78eaef8882.png)
,
![$X_0$ $X_0$](https://dxdy-01.korotkov.co.uk/f/0/7/4/07478cd102054dc58a97f6fd8df8470582.png)
в
![$Y_1$ $Y_1$](https://dxdy-04.korotkov.co.uk/f/3/9/6/39642bfad803492a79c3a1f56cf4852482.png)
и
![$X_{\infty}$ $X_{\infty}$](https://dxdy-04.korotkov.co.uk/f/3/1/b/31b50d8a44bef7c023a54c823bcd5d2e82.png)
в
![$Y_{\infty}$ $Y_{\infty}$](https://dxdy-04.korotkov.co.uk/f/f/a/c/fac4736a9f51eb64812b689aaf4a24bb82.png)
. В двух последних случаях -- это не только инъекция, но и биекция, т.к. для элементов на выходе длина цепочки не менее единицы и, следовательно, у них прообраз существует.
Для
![$f\colon X_1\mapsto Y_0$ $f\colon X_1\mapsto Y_0$](https://dxdy-01.korotkov.co.uk/f/0/c/7/0c7755d11815279eeb9b5826f49bfe5f82.png)
-- это, конечно, не более чем инъекция (вообще говоря). Но зато биекцию между двумя этими множествами осуществляет функция
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
. Вот и всё.
Это -- очень лаконичное и без выкрутасов доказательство. Мне раньше читать его не доводилось, но вот сейчас вчитался -- и мне сильно понравилось.
Прочитать Дудакова не смог, он откровенный пижон. У него какое-то безумное нагромождение дополнительных конструкций и понятий, абсолютно не нужных для реализации основной идеи (как я её понял -- ведь понять её достоверно нет никакой возможности в силу безумия). Между тем та самая идея (как я её понял, ещё раз соррю) весьма тоже проста и привлекательна, и при этом не требует для своей реализации ничего, кроме минимальных, самых что ни на есть базовых понятий теории множеств. Реализация, правда, выйдет несколько длиннее, чем у К.-Ф., но оно того стоит: построение биекции окажется исключительно конструктивным.