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

[mihaild]

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

но множество $\{\varnothing, \{a\}\}=\{\{\}, \{\;\;, a\}\}$ не является парой, потому что в нем нет первого элемента пары.

Примерно так. Так как же всё-таки выглядит, как множество, функция $\varnothing \to \{a, b\}$?

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

Пусть $x=\varnothing$, тогда $\{\{\varnothing\},\{\varnothing,y\}\}$ -- это пара по Куратовскому.

Это верно. А вот верно ли что $\varnothing \in \{\{\varnothing\},\{\varnothing,y\}\}$?
"Быть элементом множества" и "быть элементом пары" - это сильно разные свойства.

[Vladimir Pliassov]

Значит, в надо доказать, что $\varnothing$ не принадлежит паре $\langle x, y\rangle$ как множеству $\{\{x\},\{x,y\}\}$, то есть под $\varnothing \notin \langle x, y\rangle$ следует понимать $\varnothing \notin \{\{x\},\{x,y\}\}.$

$\rhd$ Пусть $\varnothing \in \{\{x\},\{x,y\}\},$ тогда либо $\{x\}=\varnothing$, либо $\{x,y\}=\varnothing$, что не соответствует действительности. Значит, $\varnothing \notin \langle x, y\rangle\;\; \lhd$.

[mihaild]

Правильно. Если уж совсем подробно, то можно написать что $x \in \{x\}$ но $x \not\in \varnothing$.

[Vladimir Pliassov]

Спасибо! С Новым годом!

-- 01.01.2023, 01:12 --

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

Так как же всё-таки выглядит, как множество, функция $\varnothing \to \{a, b\}$?

Функция это множество пар. При домене, равном $\varnothing$, ни одна пара не образуется (так что зря я пытался привлечь к решению задачи определение пары по Куратовскому), значит, множество пар пустое: $\varnothing \to \{a, b\}=\varnothing.$

[Vladimir Pliassov]

Нет, $\varnothing \to \{a, b\}\colon \varnothing?$

Или можно записать как $(\varnothing \to \{a, b\})= \varnothing?$

[mihaild]

Нет, никакой из этих вариантов некорректен, перед записью $X \to Y$ должно идти обозначение функции, сама по себе эта запись никакого объекта не обозначает.
Допустима, например, запись "если $f: \varnothing \to Y$, то $f = \varnothing$". Или "если $f$ - функция $\varnothing \to Y$".

[Vladimir Pliassov]

Можно так: $f\colon \varnothing \to \{a, b\}\to f=\varnothing$?

[eugensk]

Vladimir Pliassov

Нужны хотя бы скобки, иначе это ребус. Или возьмите для следования другую стрелку, $\Rightarrow$, тогда будет понятно.
Если напишете словами как предлагает mihaild, будет совсем хорошо.

[Vladimir Pliassov]

1.

eugensk в сообщении #1575890 писал(а):

иначе это ребус.

Понятно:

$(f\colon \varnothing \to \{a, b\})\to f=\varnothing$ или

$f\colon \varnothing \to \{a, b\}\Rightarrow f=\varnothing$, а лучше

если $f\colon \varnothing \to \{a, b\}$, то $f=\varnothing$.

Спасибо!

2.

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

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

$f(\bigcap _i A_i)=\bigcap _i B_i$.

Это, кстати, доказать сможете?

В моей попытке доказательства теоремы Кантора-Бернштейна есть один пробел. Допустим, что уже доказано, что существует биекция

$$p\colon (A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots \to (B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots$$

и что

$$A=C\cup (A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots, \;\; B=D\cup (B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots\;,$$

где $C=\bigcap_i A_i\;\; D=\bigcap_i B_i$.

Теперь надо доказать, что $f\colon C\to D$ -- тоже биекция, но это пока не получается.

Существует биекция

$$p^{-1}\colon (B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots\to (A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots\; ,$$

поэтому, поскольку по условию теоремы $f\colon A\to B$ и $g\colon B\to A$ -- инъекции, то $f\colon C\to D$ и $g\colon D\to C$ -- тоже инъекции, но мы пришли к тому же, что и в условии теоремы, только с другими буквами. То есть для того, чтобы доказать, что $f\colon C\to D$ -- биекция, надо сначала доказать теорему.

Но, может быть, надо обратить внимание на то, что, например, при $A = B = \mathbb N$ и $f(x) = g(x) = x^2$ (то есть в предложенном Вами примере) для аргументов $0$ и $1$ имеем $f=g^{-1}, \;\; g=f^{-1}$, например, $g(f(1))=1$. При этом $C=D=\{0, 1\}$.

Если не только в этом примере, но и всегда, для элементов множеств $C$ и $D$ имеет место $g=f^{-1}$, $f=g^{-1}$, откуда $C=D$, и если удастся это доказать, то удастся доказать и то, что существует биекция $h\colon A\to B$, то есть удастся доказать теорему.

Между прочим, то, что $C=D$, означает, что множества $A$ и $B$ пересекаются: $A\cap B=C=D$.

Вопрос: всегда ли, при условии, что $f\colon A\to B$ и $g\colon B\to A$ -- инъекции, множества $A$ и $B$ пересекаются?

Если не всегда, то имеется такая цепь:

Инъекции $f\colon A\to B$ и $g\colon B\to A$;

инъекции $f\colon C\to D$ и $g\colon D\to C\;\; C\in A, D\in B$;

инъекции $f\colon C'\to D'$ и $g\colon D'\to C'\;\; C'\in C, D'\in D$

и так далее. Возможно, эта цепь бесконечна.

-- 01.01.2023, 18:02 --

Для того, чтобы было $C=D$, не обязательно, чтобы для элементов множеств $C$ и $D$ было $g=f^{-1}$, $f=g^{-1}$. Можно, чтобы при $s_i\in C, t_i\in D$ было так:

$f(s_1)=t_1, \;\; g(t_1)=s_2;$

$f(s_2)=t_2, \;\; g(t_2)=s_3;$

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

$f(s_n)=t_n, \;\; g(t_n)=s_1.$

И тогда, так же как и при $g=f^{-1}$, $f=g^{-1}$, легко задается биекция между $C$ и $D$.

[mihaild]

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

имеет место $g=f^{-1}$, $f=g^{-1}$, откуда $C=D$

Откуда тут это "откуда"?
Допустим у нас есть два различных равномощных множества $X$ и $Y$ и биекции между ними $f: X \to Y$, $g: Y \to X$ такие что $f^{-1} = g$. Тогда выполнено то, что у вас написано в "имеет место", но $X \neq Y$.

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

инъекции $f\colon C\to D$ и $g\colon D\to C\;\; C\in A, D\in B$;

Здесь, видимо, имелось в виду $C \subset A$, $D \subset B$.

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

$f(s_n)=t_n, \;\; g(t_n)=s_1.$

А кто вам сказал, что множество конечно?

В любом случае, вы пошли не в ту сторону, и смотреть, что там происходит с пересечением $C$ и $D$ - занятие бесперспективное (мы с самого начала легко могли заменить $B$ равномощным ему не пересекающимся с $A$ - кстати, сможете придумать, как по множествам $A$ и $B$ построить множество, равномощное $B$, не пересекающееся с $A$?). Вам нужно найти биекцию между $C$ и $D$. Докажите, что на её роль годится просто исходная $f$.

[Vladimir Pliassov]

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

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

имеет место $g=f^{-1}$, $f=g^{-1}$, откуда $C=D$

Откуда тут это "откуда"?
Допустим у нас есть два различных равномощных множества $X$ и $Y$ и биекции между ними $f: X \to Y$, $g: Y \to X$ такие что $f^{-1} = g$. Тогда выполнено то, что у вас написано в "имеет место", но $X \neq Y$.

Да, здесь на меня нашло затмение.

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

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

$f(s_n)=t_n, \;\; g(t_n)=s_1.$

А кто вам сказал, что множество конечно?

А это вопрос: возможно ли, чтобы $C, D$ были бесконечны? (Я спрашиваю, потому что пока что знаю только один пример (Ваш), где $C, D$ конечны, да еще и равны друг другу.)

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

Инъекции $f\colon A\to B$ и $g\colon B\to A$;

инъекции $f\colon C\to D$ и $g\colon D\to C\;\; C\subset A, D\subset B$;

инъекции $f\colon C'\to D'$ и $g\colon D'\to C'\;\; C'\subset C, D'\subset D$

и так далее?

(Так что каждое звено этой цепи является объектом теоремы Кантора-Бернштейна.) Причем, этот последний вопрос, как мне кажется, интересен сам по себе, безотносительно к доказательству теоремы.

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

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

инъекции $f\colon C\to D$ и $g\colon D\to C\;\; C\in A, D\in B$;

Здесь, видимо, имелось в виду $C \subset A$, $D \subset B$.

Да, конечно.

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

В любом случае, вы пошли не в ту сторону, и смотреть, что там происходит с пересечением $C$ и $D$ - занятие бесперспективное

Я говорил не о пересечении $C$ и $D$, об их совпадении, но теперь подозреваю, что они не всегда совпадают. Когда они совпадают, пересекаются $A$ и $B$.

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

мы с самого начала легко могли заменить $B$ равномощным ему не пересекающимся с $A$

При $C\ne \varnothing, D\ne \varnothing$ не вижу, как это сделать на Вашем примере.

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

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

Если в Вашем примере оставить функции $f$ и $g$, а множества строить так: $2\in A, 4\in B, 16\in A, 256\in B$ и так далее. Но в этом случае $C=D=\varnothing$.

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

Вам нужно найти биекцию между $C$ и $D$. Докажите, что на её роль годится просто исходная $f$.

Я не вижу, как это можно сделать. Если оба множества $C$ и $D$ бесконечны, то, как я писал, поскольку по условию теоремы $f\colon A\to B$ и $g\colon B\to A$ -- инъекции, то $f\colon C\to D$ и $g\colon D\to C$ -- тоже инъекции, но тут мы приходим к тому же, что и в условии теоремы, только с другими буквами. То есть для того, чтобы доказать, что $f\colon C\to D$ -- биекция, надо сначала доказать теорему.

[mihaild]

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

А это вопрос: возможно ли, чтобы $C, D$ были бесконечны?

А попробуйте придумать сами.
Тут полезно начать в обратную сторону: сначала выбрать $C$ и $D$, а потом добавить еще что-то, чтобы получить исходные $A$ и $B$.

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

то может ли быть цепь (возможно, бесконечная)

Ну возьмите например $A = B$ и тождественную функцию.

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

Если в Вашем примере оставить функции $f$ и $g$, а множества строить так: $2\in A, 4\in B, 16\in A, 256\in B$ и так далее.

Это без всяких примеров, и вообще в отрыве от Кантора-Бернштейна. Просто отдельная задача: даны два множества, построить третье, равномощное первому и не пересекающееся со вторым.

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

То есть для того, чтобы доказать, что $f\colon C\to D$ -- биекция, надо сначала доказать теорему

Нет, не надо (и это кстати не помогло бы всё равно).
Докажите, что 1) для любого $y \in D$ существует $x \in A$ такой что $f(x) = y$; 2) что этот $x \in C$.

[Vladimir Pliassov]

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

Вам нужно найти биекцию между $C$ и $D$. Докажите, что на её роль годится просто исходная $f$.

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

Докажите, что 1) для любого $y \in D$ существует $x \in A$ такой что $f(x) = y$; 2) что этот $x \in C$.

$\rhd$ Пусть $y \in D$, тогда $y \in B_1$, потому что $D=\bigcap_i B_i$ и поэтому $\forall B_i \;\; D\subset B_i$. Поскольку $B_1=f(A)$, для каждого $y \in B_1$ найдется $x\in A$ такой, что $f(x) = y$.

При этом $A=C\cup (A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots$ и $C\cap \big ((A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots\big )=\varnothing$, так как $C=\bigcap_i A_i$, и поэтому $\forall A_i \;\; C\subset A_i$,

и $B=D\cup (B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots$ и $D\cap \big ((B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots\big )=\varnothing$, так как $\forall B_i \;\; D\subset B_i$.

Кроме того, уже доказано, что существует биекция между $(A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots$ и $(B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots\; .$

Пусть $x\in (A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots\; ,$ тогда $y\in (B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots \; ,$ и потому $y\notin D$, что противоречит первому допущению.

Следовательно, $x\notin (A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots\; ,$ значит, $x\in C$. То есть $\forall y\in D\;\; \exists x\in C\colon f(x)=y$. Таким образом, доказано, что $f\colon C\to D$ -- сюръекция.

Так как по условию теоремы $f\colon A\to B$ -- инъекция, и $C\subset A, D\subset B$, то и $f\colon C\to D$ -- тоже инъекция. Так что $f\colon C\to D$ -- биекция. $\lhd$

[mihaild]

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

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

Это верно, но обосновывать надо, глядя на $f$ и определения $A_i$ и $B_i$, а не просто

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

существует биекция между $(A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots$ и $(B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots\; .$

То, что существует какая-то там биекция, ничего не говорит про $f$.
В остальном всё правильно.

[Vladimir Pliassov]

Про биекцию между $(A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots$ и $(B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots$ не надо.

Пусть $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 \; ,$ отсюда $y\in (B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots \; ,$ и потому $y\notin D$, что противоречит первому допущению.