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

[mihaild]

Да, так. Еще можно сказать, почему именно

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

Пусть $x\in (A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots\; ,$ тогда $f(x)=y\in (B_1\setminus B_2)\cup (B_2\setminus B_3)\cup \ldots \; ,$

Посмотрим, куда именно в левой части попадает $x$, и это нам даст, куда в правой части попадает $y$.

[Vladimir Pliassov]

Об этом я уже писал:

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

Пусть $y \in B_{n + 1} \setminus B_{n + 2}$. Тогда $y \in B_{n + 1}$, и существует $x \in A_n$ такой, что $f(x) = y$. Пусть $x\in A_{n + 1}$, тогда $f(x)=y\in B_{n + 2}$, что противоречит допущению $y \in B_{n + 1} \setminus B_{n + 2}$, отсюда $x\notin A_{n + 1}$, откуда $x \in A_n \setminus A_{n + 1}$.

[mihaild]

Да, тогда всё хорошо. Сможете выписать, куда в итоге в получившейся биекции переходит элемент $x \in A$, в зависимости от того, лежит он в каком-то из $A_i$ или в $C$?
(у вас вроде бы всё нужное чтобы это сказать уже написано, просто может быть полезно собрать в одном месте)

[Vladimir Pliassov]

Биекция

$$h\colon A\to B\colon h(x)=\left\{ \begin{array}{lcl} f(x) \;\; if\; x\in A_0\setminus A_1, A_2\setminus A_3, \ldots \;,\\ g^{-1}(x) \;\; if\; x\in A_1\setminus A_2, A_3\setminus A_4, \ldots\;,\\ f(x)\;\; if\; x\in C. \end{array} \right.$$

Если обозначить как у Верещагина-Шеня $C_n= A_n\setminus A_{n+1}$, будет

$$h\colon A\to B\colon h(x)=\left\{ \begin{array}{lcl} f(x) \;\; if\; x\in C_0, C_2, \ldots \;,\\ g^{-1}(x) \;\; if\; x\in C_1, C_3, \ldots\;,\\ f(x)\;\; if\; x\in C. \end{array} \right.$$

Обозначим аналогично $D_n= B_n\setminus B_{n+1}$.

Имеем

$$\left\{ \begin{array}{lcl} \forall x\in C_n \;\; h(x)=y\in D_{n+1}, \\ \forall x\in C_{n+1} \;\; h(x)=y\in D_n, \\ \forall x\in C \;\; h(x)=y\in D. \end{array} \right.$$

[mihaild]

Да, всё так. Словами это можно сформулировать так: возьмем элемент, возьмем его прообраз относительно $g$, возьмем прообраз прообраза относительно $f$, и т.д. Есть три варианта: цепочка оборвется на элементе из $A$, на элементе из $B$, цепочка будет бесконечной. Если цепочка обрывается на $A$ или не обрывается вообще - то берем образ относительно $f$, если обрывается на $B$ - то берем прообраз относительно $g$.

[Vladimir Pliassov]

1.

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

как по множествам $A$ и $B$ построить множество, равномощное $B$, не пересекающееся с $A$?

Если $A$ и $B$ не пересекаются, строить нечего. Пусть они пересекаются.

Пример для конечных множеств:

Пусть $A=\{1,2,3,4,5,6\}, B=\{4,5,6,7,8,9,10\}$, тогда $A\cap B=\{4,5,6\}$. Возьмем $B'=\{7,8,9,10,11,12,13\}$. $\vert B'\vert=\vert B\vert$, при этом $A\cap B'=\varnothing.$

Пример для бесконечных множеств:

Пусть $A=\{1,2,3,\; \ldots\}, B=\{3,2,1,0,-1,-2\; \ldots\;,\}$ тогда $A\cap B=\{1,2,3\}$. Возьмем $B'=\{0,-1,-2, \; \ldots\}.$ $\;$ $\vert B'\vert=\vert B\vert$, при этом $A\cap B'=\varnothing.$

2.

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

Словами это можно сформулировать так: возьмем элемент

это будет $x_1$, пусть он лежит в $C_n$ при достаточно большом $n$

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

возьмем его прообраз относительно $g$

это будет $y_1\in D_{n-1}$

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

возьмем прообраз прообраза относительно $f$

это будет $x_2\in C_{n-2}$

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

и т.д. Есть три варианта: цепочка оборвется на элементе из $A$, на элементе из $B$, цепочка будет бесконечной.

Я думаю, цепочка, конечно же, оборвется, когда мы придем либо к соответствующему $x\in C_0$, либо к соответствующему $y\in D_0$ (в зависимости от четности $n$). Другое дело, если бы мы брали образ, образ от образа и так далее, здесь цепочка не может оборваться, потому что (это, правда, надо бы доказать) множества $\{C_0, C_2 \ldots\}, \{C_1, C_3 \ldots\}$ и $\{D_0, D_2 \ldots\}, \{D_1, D_3 \ldots\}$ бесконечны (я в этом уверен). Но, может быть, я что-то не так понял. Кстати, и у Верещагина-Шеня

(https://www.mccme.ru/free-books/shen/sh ... art1-2.pdf стр. 22) читаем:

Цитата:

Заметим, что пересечение всех множеств $A_i$ вполне может быть непусто: оно состоит из тех элементов, у которых можно сколько угодно раз брать $f$-прообраз

Здесь мне сразу было странно, что говорится не об образах, а о прообразах этих элементов.

[mihaild]

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

Пример для бесконечных множеств

Это пример, а как быть в общем случае?
(задача не слишком интересная, по сути просто на понимание определений)

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

Я думаю, цепочка, конечно же, оборвется, когда мы придем либо к соответствующему $x\in C_0$, либо к соответствующему $y\in D_0$

А если мы начинали из $C$?

[Vladimir Pliassov]

Об этом я не подумал.

Если начинать из $C$, то, независимо от того, конечны или бесконечны $C$ и $D$, возможна такая замкнутая цепочка (которую можно назвать бесконечной):

$g^{-1}(x)=y, f^{-1}(y)=x,

$g^{-1}(x)=y, f^{-1}(y)=x,$ и т.д., --

или такая замкнутая цепочка ("у попа была собака"):

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

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

.............................................

$g^{-1}(x_k)=y_n, \;\; f^{-1}(y_k)=x_1$

и снова и снова, где $k$ -- число элементов $x$ и число элементов $y$ в цепочке.

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

[mihaild]

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

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

Попробуйте это доказать. Начните с какого-нибудь простого варианта, например $C = D = \mathbb N$, $f = g$. Т.е. у нас просто есть биекция натуральных чисел в себя. Какие при этом могут быть цепочки прообразов?

[Vladimir Pliassov]

А, может быть, надо так смотреть.

Имеем последовательность (цепь):

$$A, f(A), g\big(f(A)\big), f\Big( g\big(f(A)\big)\Big), \ldots \eqno (1)$$

и, соответственно, последовательности:

$$x, f(x), g\big(f(x)\big), f\Big( g\big(f(x)\big)\Big), \ldots \;\; x\in C_0 \eqno (2)$$

и

$$a, f(a), g\big(f(a)\big), f\Big( g\big(f(a)\big)\Big), \ldots \;\; a\in C. \eqno (3)$$

Последовательность не имеет конца, но имеет начало, поэтому, с какого бы члена ни начинать реверсивное движение, придем к началу, то есть реверсивное движение не может быть бесконечно. Вторая и третья последовательности соответствуют первой последовательности, поэтому, когда первая последовательность при реверсивном движении приходит к первому члену, то же самое делают и вторая и третья, и после этого движение прекращается не только у первой последовательности, но и у второй и третьей. Так что, даже если членами третьей последовательности являются только $x$ и $f(x)$, которые могут переходить друг в друга до бесконечности, они перестают это делать, когда первая последовательность при реверсивном движении приходит к своему первому члену.

[mihaild]

Непонятно. Что такое $A$?
И тут нет никакого $C_0$, мы рассматриваем только часть конструкции, возникающей в теореме Кантора-Бернштейна - множества $C$ и $D$.

[Vladimir Pliassov]

$A$ -- это одно из двух множеств, о которых теорема, $C_0=A_0\setminus A_1$. Я имел в виду, что множества $C$ и $D$ надо рассматривать только вместе с остальной конструкцией, а не сами по себе.

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

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

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

Попробуйте это доказать. Начните с какого-нибудь простого варианта, например $C = D = \mathbb N$, $f = g$. Т.е. у нас просто есть биекция натуральных чисел в себя. Какие при этом могут быть цепочки прообразов?

Теперь я думаю, что доказать это не получится, потому что это не так: цепочку можно строить, начиная с произвольного элемента $x\in C$ или с произвольного элемента $y\in D$, не только так, что выбранный элемент будет в начале цепочки, но и так, что он будет в ее середине -- то есть строить цепочку в обе стороны от этого элемента.

[mihaild]

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

Я имел в виду, что множества $C$ и $D$ надо рассматривать только вместе с остальной конструкцией, а не сами по себе.

Очень полезно в таких случаях выделять интересные части отдельно, и рассматривать их независимо от всего остального. Бесконечная цепочка очевидно никогда не выйдет за пределы $C$ и $D$, поэтому можно считать, что есть только они.

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

Теперь я думаю, что доказать это не получится, потому что это не так: цепочку можно строить, начиная с произвольного элемента $x\in C$ или с произвольного элемента $y\in D$, не только так, что выбранный элемент будет в начале цепочки, но и так, что он будет в ее середине -- то есть строить цепочку в обе стороны от этого элемента.

Может и так. Теперь у вас задача - либо построить биекцию $f: \mathbb N \to \mathbb N$, такую что для какого-то элемента цепочка $x, f^{-1}(x), f^{-1}(f^{-1}(x)), \ldots$ бесконечна, либо доказать, что так не бывает.
(ИМХО гораздо интереснее решать такие задачи, когда ответ неизвестен)

[Vladimir Pliassov]

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

Теперь у вас задача - либо построить биекцию $f: \mathbb N \to \mathbb N$, такую что для какого-то элемента цепочка $x, f^{-1}(x), f^{-1}(f^{-1}(x)), \ldots$ бесконечна, либо доказать, что так не бывает.

$$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 \; .$$

Можно начать с любого натурального числа, например, с $5$, во второй строке и идти влево (против стрелок), когда строка кончится, перейти на второе звено первой строки, то есть на $0\to 1$ (пропустив $0\to 0$) и идти вправо (по стрелкам) до бесконечности. Это будет движение от прообразов к образам функции $f: \mathbb N \to \mathbb N$.

Можно начать с любого натурального числа, например, с $5$, в первой строке и идти влево (против стрелок), когда строка кончится, перейти на второе звено второй строки, то есть на $0\to 1$ (пропустив $0\to 0$) и идти вправо (по стрелкам) до бесконечности. Это будет движение от образов к прообразам функции $f: \mathbb N \to \mathbb N$.

Таким образом, построена биекция $f: \mathbb N \to \mathbb N$, такая что для некоторого элемента (например, для $x=5$) цепочка $x, f^{-1}(x), f^{-1}(f^{-1}(x)), \ldots$ бесконечна.

[mihaild]

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 \; ,$$

Это что-то странное. Куда у вас $0$ переходит?