x, y, z

Доказательство теоремы Кантора-Бернштейна

# 23 Мар 2015 06:48:22
Evgeniy

Если существуют инъекции $f\colon A \rightarrow B$ и $g\colon B \rightarrow A$, тогда множества $A$ и $B$ равномощны, то есть существует биекция $h\colon A \rightarrow B$.

Иными словами, теорема утверждает следующее. Если $\left | A \right | \le \left | B \right |$ и $\left | B \right | \le \left | A \right |$, тогда $\left | A \right | = \left | B \right |$.

Доказательство

Положим
$%\width{16}\begin{align*} &C_0 = A\setminus g(B); \\ &C_n = gf(C_{n-1}),\ n=1,2...\end{align*}%$

Далее положим $C = \bigcup_{n} C_n.$

Заметим, что $gf(C)\subset C$.

Определим отображение

$h(x)=\begin{cases} f(x), & x\in C \\ g^{-1}(x), & x\notin C \end{cases}$

Область определения $h$ совпадает с $A$.

Если $x\notin C$, тогда $x\notin C_0$, поэтому $x\in g(B)$, то есть существует $h(x)=g^{-1}(x)$.

Докажем, что $h$ инъективное.

Пусть $x_1\neq x_2$. Возможны следующие три случая.

Если $x_1, x_2 \in C$, тогда $h(x_1)=f(x_1)\neq f(x_2)=h(x_2)$.

Если $x_1, x_2 \notin C$, тогда $h(x_1)=g^{-1}(x_1)\neq g^{-1}(x_2)=h(x_2)$.

Если $x_1\in C,\ x_2 \notin C$. Предположим, что $h(x_1)=f(x_1)=g^{-1}(x_2)=h(x_2)$. Тогда $gf(x_1)=x_2$, то есть $x_2\in C$ — противоречие.

Итак, инъективность $h$ показана.

Докажем, что $h$ сюръективное.

Если $y\in f(C)$, тогда $y=f(x)$, где $x\in C$, то есть $y=h(x)$.

Если $y\notin f(C)$, тогда $g(y)\notin C$.

Действительно, если $g(y)\in C$, тогда $g(y)\in gf(C_{n})$ либо $g(y)\in C_0=A\setminus g(B)$.

В первом случае $y\in f(C_{n})\subset f(C)$, что противоречит предположению $y\notin f(C)$.

Второй случай также невозможен, поскольку $C_0$ не содержит образов элементом из $B$.

Таким образом, $y=g^{-1}(x),\ x\notin C$, то есть $y=h(x)$, что и означает сюръективность.

Итак, $h$ — искомая биекция.

Теорема доказана.

Наглядная иллюстрация, как конструировалось отображение $h$.
Наглядная иллюстрация, как конструировалось отображение h.
Здесь множества $A$ и $B$ — горизонтальные отрезки, отображения $f$ и $g$ — гомотетии центрами соответственно в $Q$ и $P$. Жирной линией на верхнем отрезке справа налево $C_0,\ C_1,\ C_2,\dots$, на нижнем соответственно $f(C_0),\ f(C_1),\ f(C_2),\dots$

Примечательно, что это биективное отображение между множествами произвольной мощности строится таким "дискретным" способом.
*Имя:
Заголовок:
[tex-clear] [tex-help] [ted]
  • formulas >

*Вычислите
Captcha
Отправляя данные, вы соглашаетесь с Правилами сайта.