Теорема Кантора-Бернштейна 2

[Vladimir Pliassov]

А, у меня получилась совсем не та цепочка и не биекция.

Пусть $A=B=\mathbb N$ и пусть имеются функции $f: A\to B$ и $g: B\to A$ такие, что

$$\ldots \;, f(5)=4, g(4)=3, f(3)=2, g(2)=1,$$

$$f(1)=0, g(0)=0, f(0)=1, g(1)=2, f(2)=3, g(3)=4, f(4)=5 \ldots $$

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

[mihaild]

Vladimir Pliassov в сообщении #1576241 писал(а):

А, у меня получилась совсем не та цепочка и не биекция.

У вас даже не функция получилась.

Vladimir Pliassov в сообщении #1576241 писал(а):

Но это, конечно, не решение заданной задачи

Это уже почти решение.

[Vladimir Pliassov]

mihaild в сообщении #1576243 писал(а):

У вас даже не функция получилась.

Получилась комбинация двух перемежающихся функций.

[mihaild]

Vladimir Pliassov в сообщении #1576247 писал(а):

Получилась комбинация двух перемежающихся функций

Я про

Vladimir Pliassov в сообщении #1576233 писал(а):

$$f: \mathbb N \to \mathbb N: 0\mapsto 0, 0\mapsto 1, 1\mapsto 2, 2\mapsto 3, 3\mapsto 4, 4\mapsto 5, \ldots \; ,$$

Это не функция, потому что нулю соответствуют два элемента.

Ваши $f$ и $g$ удовлетворяют свойству, что для некоторого $x$ цепочка $x, f^{-1}(x), g^{-1}(f^{-1}(x)), f^{-1}(g^{-1}(f^{-1}(x))), \ldots$ бесконечна (кстати, можете указать подходящий $x$ и явно её выписать?). Как теперь избавиться от $g$, чтобы было просто $x, f^{-1}(x), f^{-1}(f^{-1}(x)), \ldots$?

[Vladimir Pliassov]

Да, конечно,

$$f: \mathbb N \to \mathbb N: 0\mapsto 0, 0\mapsto 1, 1\mapsto 2, 2\mapsto 3, 3\mapsto 4, 4\mapsto 5, \ldots \; ,$$

$$f^{-1}: \mathbb N \to \mathbb N: 0\mapsto 0, 0\mapsto 1, 1\mapsto 2, 2\mapsto 3, 3\mapsto 4, 4\mapsto 5, \ldots $$

это не функции (потому что нулю соответствуют два элемента, потом я это увидел -- когда Вы сказали), я имел в виду, что

$$\ldots \;, f(5)=4, g(4)=3, f(3)=2, g(2)=1,$$

$$f(1)=0, g(0)=0, f(0)=1, g(1)=2, f(2)=3, g(3)=4, f(4)=5 \ldots $$

это комбинация двух перемежающихся функций.

mihaild в сообщении #1576299 писал(а):

Ваши $f$ и $g$ удовлетворяют свойству, что для некоторого $x$ цепочка $x, f^{-1}(x), g^{-1}(f^{-1}(x)), f^{-1}(g^{-1}(f^{-1}(x))), \ldots$ бесконечна (кстати, можете указать подходящий $x$ и явно её выписать?

$$f(x)=y=\left\{ \begin{array}{rcl} x+1 \;\; if \;\; 2\mid x \\ x-1 \;\; if \;\; 2\nmid x\\ \end{array} \right, \;\; g(y)=x=\left\{ \begin{array}{lcl} y+1 \;\; if \;\; 2\nmid y \\ y-1 \;\; if \;\; 2\mid y\wedge y\ne 0\\ 0 \;\; if \;\; y=0 \end{array} \right\;\; \;\; x, y\in \mathbb N.$$

$$f^{-1}(x)=z=\left\{ \begin{array}{lcl} x+1 \;\; if \;\; 2\nmid x \\ x-1 \;\; if \;\; 2\mid x\wedge x\ne 0\\ 0 \;\; if \;\; x=0 \end{array} \right, \;\; g^{-1}(z)=x=\left\{ \begin{array}{lcl} z+1 \;\; if \;\; 2\mid z \\ z-1 \;\; if \;\; 2\nmid z\\ \end{array} \right\;\; \;\; x, z\in \mathbb N.$$

mihaild в сообщении #1576299 писал(а):

Как теперь избавиться от $g$, чтобы было просто $x, f^{-1}(x), f^{-1}(f^{-1}(x)), \ldots$?

$$h(x)=\left\{ \begin{array}{lcl} x+2 \;\; if \;\; 2\mid x \\ x-2 \;\; if \;\; 2\nmid x\wedge x\ne1\\ 0 \;\; if \;\; x=1\\ \end{array} \right\Rightarrow h^{-1}(x)=\left\{ \begin{array}{lcl} x+2 \;\; if \;\; 2\nmid x \\ x-2 \;\; if \;\; 2\mid x\wedge x\ne 0\\ 1 \;\; if \;\; x=0 \end{array} \right\;\; \;\; x\in \mathbb N.$$

[Vladimir Pliassov]

Нет, не так. Сейчас попытаюсь исправить.

[Vladimir Pliassov]

Попытался исправить. Итак,

$$\ldots \;, f(5)=4, g(4)=3, f(3)=2, g(2)=1,$$

$$f(1)=0, g(0)=0, f(0)=1, g(1)=2, f(2)=3, g(3)=4, f(4)=5 \ldots $$

это комбинация двух перемежающихся функций, причем $f(x)=f^{-1}(x)$ и $g(y)=g^{-1}(y)$ (аргументы в обеих функциях можно обозначить одной и той же буквой, но для наглядности я обозначил разными).

mihaild в сообщении #1576299 писал(а):

Ваши $f$ и $g$ удовлетворяют свойству, что для некоторого $x$ цепочка $x, f^{-1}(x), g^{-1}(f^{-1}(x)), f^{-1}(g^{-1}(f^{-1}(x))), \ldots$ бесконечна (кстати, можете указать подходящий $x$ и явно её выписать?)

$$f^{-1}(x)=f(x)=\left\{ \begin{array}{rcl} x+1 \;\; if \;\; 2\mid x \\ x-1 \;\; if \;\; 2\nmid x\\ \end{array} \right, \;\; g^{-1}(y)=g(y)=\left\{ \begin{array}{lcl} y+1 \;\; if \;\; 2\nmid y \\ y-1 \;\; if \;\; 2\mid y\wedge y\ne 0\\ 0 \;\; if \;\; y=0 \end{array} \right\;\; \;\; x, y\in \mathbb N.$$

mihaild в сообщении #1576299 писал(а):

Как теперь избавиться от $g$, чтобы было просто $x, f^{-1}(x), f^{-1}(f^{-1}(x)), \ldots$?

$$h^{-1}(x)=h(x)=\left\{ \begin{array}{lcl} x+2 \;\; if \;\; 2\mid x \\ x-2 \;\; if \;\; 2\nmid x\wedge x\ne1\\ 0 \;\; if \;\; x=1\\ \end{array} \right\;\; x\in \mathbb N.$$

Здесь тоже для наглядности можно было бы обозначить аргументы функций $h$ и $h^{-1}$ разными буквами.

В этом случае (в отличие от предыдущего), когда я говорю: "для наглядности", -- я имею в виду, что функцию $f: \mathbb N\to \mathbb N$ можно рассматривать как отображение $\mathbb N$ само в себя (тогда имеется одно множество), а можно рассматривать ее как отображение множества $\mathbb N$ в его копию (тогда имеется два множества). Обозначим оригинал $\mathbb N_1,$ а копию $\mathbb N_2.$ Тогда пусть $x\in \mathbb N_1$, а $y\in \mathbb N_2$.

[mihaild]

А что в предыдущей попытке было не так? Я вроде бы ошибок не вижу.

Вот в последней точно что-то не так: если $h^{-1} = h$, то $h^{-1}(h^{-1}(x)) = h^{-1}(h(x)) = x$, и цепочка получается конечной (точнее повторяющейся).
Но с вашим определением $h$ не получается $h^{-1} = h$: $h(h(2)) = 6 \neq 2$.

И как вы придумали вашу $h$? Я имел в виду, что если у вас уже есть $f$ и $g$, то из них можно изготовить подходящую $h$, вообще не задумываясь, как устроены $f$ и $g$, лишь бы цепочка $x, f^{-1}(x), g^{-1}(f^{-1}(x)), f^{-1}(g^{-1}(f^{-1}(x))), \ldots$ была бесконечной.

[Vladimir Pliassov]

mihaild в сообщении #1576361 писал(а):

А что в предыдущей попытке было не так?

Там $f(x)$ и $g(y)$ были выписаны верно, а $f^{-1}(x)$ и $g^{-1}(y)$ неверно.

$f(x)=f^{-1}(x)$ и $g(y)=g^{-1}(y)$, это видно из

$$\ldots \;, f(5)=4, g(4)=3, f(3)=2, g(2)=1,$$

$$f(1)=0, g(0)=0, f(0)=1, g(1)=2, f(2)=3, g(3)=4, f(4)=5 \ldots \;.$$

mihaild в сообщении #1576361 писал(а):

Вот в последней точно что-то не так... с вашим определением $h$ не получается $h^{-1} = h$: $h(h(2)) = 6 \neq 2$.

Правда! $h(x)\ne h^{-1}(x)$. Так что из первой попытки надо взять

$$h(x)=\left\{ \begin{array}{lcl} x+2 \;\; if \;\; 2\mid x \\ x-2 \;\; if \;\; 2\nmid x\wedge x\ne1\\ 0 \;\; if \;\; x=1\\ \end{array} \right\Rightarrow h^{-1}(x)=\left\{ \begin{array}{lcl} x+2 \;\; if \;\; 2\nmid x \\ x-2 \;\; if \;\; 2\mid x\wedge x\ne 0\\ 1 \;\; if \;\; x=0 \end{array} \right\;\; \;\; x\in \mathbb N.$$

Можно (для наглядности) аргумент при $h^{-1}$ обозначить через $y$:

$$h(x)=\left\{ \begin{array}{lcl} x+2 \;\; if \;\; 2\mid x \\ x-2 \;\; if \;\; 2\nmid x\wedge x\ne1\\ 0 \;\; if \;\; x=1\\ \end{array} \right\Rightarrow h^{-1}(y)=\left\{ \begin{array}{lcl} y+2 \;\; if \;\; 2\nmid y \\ y-2 \;\; if \;\; 2\mid y\wedge y\ne 0\\ 1 \;\; if \;\; y=0 \end{array} \right\;\; \;\; y\in \mathbb N.$$

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

Интересно, что $\mathbb N$ это вполне упорядоченное множество: оно имеет наименьший элемент $0$, то есть у него есть начало и нет конца, но при этом обе цепочки, которые построены на этом множестве, не имеют ни начала, ни конца (начало $\mathbb N$ находится у них в середине).

[mihaild]

Да, всё правильно. Порядок на $\mathbb N$ вообще не связан с возможностью разных цепочек.
Собственно ИМХО более простым вариантом было бы построить биекцию $\mathbb N \to \mathbb Z$, а дальше на $\mathbb Z$ нужную функцию (биекцию, у которой бывают бесконечные цепочки прообразов) построить тривиально. Ваше решение тоже можно считать имеет такой вид.

И кстати если слегка поработать, то можно показать, что множество $C$ из исходной задачи естественно разбивается на непересекающиеся группы: закольцованные цепочки разных длин, и бесконечные в обе стороны цепочки.

[Vladimir Pliassov]

Вы имеете в виду $C=\bigcap_i A_i$? Но тогда и $D=\bigcap_i B_i$, правильно?

Если так, то надо сначала убедиться, что бывают бесконечные $C, D$. Пока что мне известен только один случай, иллюстрирующий теорему Кантора-Бернштейна (Ваш пример, где $A=B=\mathbb N, f(x)=x^2, g(y)=y^2 \;\; x\in A, y\in B$), и в нем $C, D$ конечны и равны друг другу (равны $\{0, 1\}$).

[mihaild]

Vladimir Pliassov в сообщении #1576386 писал(а):

Если так, то надо сначала убедиться, что бывают бесконечные $C, D$.

Вообще в теореме Кантора-Бернштейна ничего не говорится о том, что исходные инъекции не должны быть биекциями, так что Ваша $h$ выше годится.

Но если хочется пример, где она содержательна, и $C$ бесконечно - попробуйте построить его так: взять $U = \mathbb N_1$, $V = \mathbb N_2$, и добавить еще какие-нибудь множества $X$ и $Y$ (не пересекающиеся с $U$ и $V$) так, чтобы можно было взять $A = X \cup U$, $B = Y \cup V$, $f(X) \subsetneq Y$, $f(U) = V$, $g(Y) \subsetneq X$, $g(V) = U$, $f|_U = h$. Тогда получится $C \subseteq U$, и нужная бесконечная цепочка будет, причем $f$ изначально не биекция.
Т.е. берем, и собираем пример из двух частей: одна обеспечивает нетривиальность применения теоремы, вторая - существование бесконечной цепочки.

[Vladimir Pliassov]

Мне кажется, что должно быть не $C \subseteq U$, а $C=U=\mathbb N_1$.

Если обозначить, как у Верещагина-Шеня, $C_n= A_n\setminus A_{n+1}$ и аналогично $D_n= B_n\setminus B_{n+1}$, то $A=C+\bigcup_i C_i$, $B=D+\bigcup_i D_i$ ($+$ вместо $\cup$, потому что $C$ и $\bigcup_i C_i$ и $D$ и $\bigcup_i D_i$ не пересекаются, впрочем, $C_i$ тоже не пересекаются между собой, и $D_i$ не пересекаются между собой, но не знаю как написать).

Как я понимаю, $X=\bigcup_i C_i, \;\; Y=\bigcup_i D_i, \;\; C=U, \;\;D=V$.

mihaild в сообщении #1576387 писал(а):

причем $f$ изначально не биекция.

То есть $f:X\to Y$ не биекция, и $f: A\to B$ не биекция, но $f|_U = h: (C=U)\to (D=V)$ -- биекция.

[mihaild]

Vladimir Pliassov в сообщении #1576391 писал(а):

Мне кажется, что должно быть не $C \subseteq U$, а $C=U=\mathbb N_1$.

А это зависит от того, что будет происходить на $X$. Может там еще какие-то элементы, у которых можно бесконечно брать прообраз, добавятся.

Vladimir Pliassov в сообщении #1576391 писал(а):

Как я понимаю, $X=\bigcup_i C_i, \;\; Y=\bigcup_i D_i, \;\; C=U, \;\;D=V$.

Можно и так. Смотря как построите.

[Vladimir Pliassov]

mihaild в сообщении #1576392 писал(а):

А это зависит от того, что будет происходить на $X$. Может там еще какие-то элементы, у которых можно бесконечно брать прообраз, добавятся.

Если $X=\bigcup_i C_i, \;\; Y=\bigcup_i D_i,$ то, по-моему, таких элементов быть не может.

Например, цепочка, которую мы вывели, базируется на функциях

$$f^{-1}(x)=f(x)=\left\{ \begin{array}{rcl} x+1 \;\; if \;\; 2\mid x \\ x-1 \;\; if \;\; 2\nmid x\\ \end{array} \right, \;\; g^{-1}(y)=g(y)=\left\{ \begin{array}{lcl} y+1 \;\; if \;\; 2\nmid y \\ y-1 \;\; if \;\; 2\mid y\wedge y\ne 0\\ 0 \;\; if \;\; y=0 \end{array} \right\;\; \;\; x, y\in \mathbb N.$$

В этой цепочке

$$\ldots \;, f(5)=4, g(4)=3, f(3)=2, g(2)=1,$$

$$f(1)=0, g(0)=0, f(0)=1, g(1)=2, f(2)=3, g(3)=4, f(4)=5 \ldots$$

обратим внимание на функцию $g(y)$ вблизи нуля:

$$\ldots \;, g(4)=3, g(3)=4, g(2)=1, g(1)=2, \ldots$$

дальше должно бы было быть $g(0)=-1$ (что невозможно, так как $-1\notin \mathbb N$), если бы было условие $g(y)=y-1 \;\; if \;\; 2\mid y$, но условие другое: $g(y)=y-1 \;\; if \;\; 2\mid y\wedge y\ne 0$ и потом $g(y)=0 \;\; if \;\; y=0$. Благодаря этому условию, функция $g$, дойдя до нуля, не прерывается, и благодаря этому условию, существуют функции

$$h(x)=\left\{ \begin{array}{lcl} x+2 \;\; if \;\; 2\mid x \\ x-2 \;\; if \;\; 2\nmid x\wedge x\ne1\\ 0 \;\; if \;\; x=1\\ \end{array} \right\Rightarrow h^{-1}(y)=\left\{ \begin{array}{lcl} y+2 \;\; if \;\; 2\nmid y \\ y-2 \;\; if \;\; 2\mid y\wedge y\ne 0\\ 1 \;\; if \;\; y=0 \end{array} \right\;\; \;\; y\in \mathbb N,$$

из которых функцией $h^{-1}(y)$ можно бесконечное число раз брать прообраз от любого элемента $y$ относительно функции $h$.

Теперь рассмотрим то, что происходит по теореме Кантора-Бернштейна. Имеем $f: A\to B$ и $g: B\to A$.

Обозначим через $x_i$ элемент множества $C_i$ и через $y_i$ элемент множества $D_i$ (что собой представляют $C_i$ и $D_i$, было сказано уже много раз). Имеем цепочки

$$\ldots \;, g^{-1}(x_3)=y_2, f^{-1}(y_2)=x_1, g^{-1}(x_1)=y_0,$$

и

$$\ldots \;, f^{-1}(y_3)=x_2, g^{-1}(x_2)=y_1, f^{-1}(y_1)=x_0,$$

которые обе прерываются, потому что ни $g^{-1}$ не может отобразить $x_0\in C_0$ в какой бы то ни было $y\in Y$, ни $f^{-1}$ не может отобразить $y_0\in D_0$ в какой бы то ни было $x\in X$.

Так что из этих функций невозможно построить такую функцию $h^{-1}$, чтобы ею от элемента множества $X=\bigcup_i C_i$ или от элемента множества $Y=\bigcup_i D_i$ можно было бесконечное число раз брать прообраз относительно функции $h$.

Других же функций здесь, по-моему, не предполагается.