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

[Vladimir Pliassov]

Доказательство теоремы Кантора – Бернштейна в "НАЧАЛЕ ТЕОРИИ МНОЖЕСТВ" Н. К. Верещагина, А.Шеня

(https://www.mccme.ru/free-books/shen/sh ... art1-2.pdf стр. 20 - 21),

очевидно, годится не для всех случаев. Авторы сами пишут:

Цитата:

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

и на этом основывают доказательство. Имеется другое доказательство в Википедии, я пытался его постичь, пока не постиг, но, как мне кажется, нашел свое доказательство, более простое и очевидное. Буду признателен, если кто-нибудь его подтвердит или опровергнет.

Цитата:

Теорема Кантора — Бернштейна (в англ. литературе теорема Кантора — Бернштейна — Шредера), утверждает, что если существуют инъективные отображения $f:A\to B$ и $g:B\to A$ между множествами $A$ и $B$, то существует взаимно-однозначное отображение $h\colon A\to B$ . Другими словами, что мощности множеств $A$ и $B$ совпадают:

$$|A|=|B|.$$

Другими словами, теорема утверждает следующее:

Из $\mathfrak a\leqslant \mathfrak b$ и $\mathfrak b\leqslant \mathfrak a$ следует, что $\mathfrak a=\mathfrak b,$ где $\mathfrak a,\mathfrak b$ — кардинальные числа.

Википедия.

Итак, надо доказать, что существует взаимно-однозначное отображение $h\colon A\to B$ .

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

Обозначим $A,B$ соответственно как $A_0, B_0.$

Пусть $f\colon A_0\to B_0$ и $g\colon B_0\to A_0$ не являются биекциями, тогда

$$f(A_0)=B_1\subsetneq B_0, \;\; g(B_0)=A_1\subsetneq A_0,$$

$$f(A_1)=B_2\subsetneq B_1, \;\; g(B_1)=A_2\subsetneq A_1$$

и так далее, и вообще

$$f(A_n)=B_{n+1}\subsetneq B_n, \;\; g(B_n)=A_{n+1}\subsetneq A_n.$$

При этом

$$f(A_0\setminus A_1)=B_1\setminus B_2, \;\; g(B_0\setminus B_1)=A_1\setminus A_2,$$

$$f(A_1\setminus A_2)=B_2\setminus B_3, \;\; g(B_1\setminus B_2)=A_2\setminus A_3,$$

и так далее.

Заметим, что

$$(A_0\setminus A_1)\cap (A_1\setminus A_2)=\varnothing, \;\; (A_1\setminus A_2)\cap (A_2\setminus A_3)=\varnothing, \;\; \ldots $$

и

$$(B_0\setminus B_1)\cap (B_1\setminus B_2)=\varnothing, \;\; (B_1\setminus B_2)\cap (B_2\setminus B_3)=\varnothing \;\; \ldots \; .$$

Имеем биекции

$$f\colon (A_0\setminus A_1)\to (B_1\setminus B_2), \;\; f\colon (A_1\setminus A_2)\to (B_2\setminus B_3), \;\; \ldots $$

Имеем также биекции

$$g\colon (B_0\setminus B_1)\to (A_1\setminus A_2), \;\; g\colon (B_1\setminus B_2)\to (A_2\setminus A_3), \;\; \ldots$$

и потому биекции

$$g^{-1}\colon (A_1\setminus A_2)\to (B_0\setminus B_1), \;\; g^{-1}\colon (A_2\setminus A_3)\to (B_1\setminus B_2), \;\; \ldots \;\; .$$

Таким образом, имеем биекцию

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

то есть биекцию

$$h\colon A\to B.$$

$\lhd$

[mihaild]

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

очевидно, годится не для всех случаев. Авторы сами пишут:

Цитата:

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

И как из этого следует, что оно для чего-то не годится? Это пересечение может быть пусто, может быть непусто, доказательство работает в обоих случаях одинаково.

Ваше рассуждение, по сути, повторяет первую часть оригинального, только т.к. вы не перешли к одному множеству, вам пришлось писать в два раза больше. И вы пропустили важный момент, из-за которого один из переходов не обоснован.
Попробуйте применить ваше рассуждение к $A = B = \mathbb N$ и $f(x) = g(x) = x^2$. Внимательно напишите, какие получаются $A_i$ и $B_i$, какое получается $h$, и проверьте, является ли оно биекцией $\mathbb N \to \mathbb N$.

[Vladimir Pliassov]

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

Попробуйте применить ваше рассуждение к $A = B = \mathbb N$ и $f(x) = g(x) = x^2$. Внимательно напишите, какие получаются $A_i$ и $B_i$, какое получается $h$, и проверьте, является ли оно биекцией $\mathbb N \to \mathbb N$.

$A_0=B_0=\{0, 1, 2, 3, 4, 5, 6, \ldots\},$

$A_1=B_1=\{0, 1, 4, 9, 16, 25, 36, \ldots\},$

$A_2=B_2=\{0, 1, 16, 81, 256, 625, 1296, \ldots\}.$

$A_0\setminus A_1=B_0\setminus B_1=\{2, 3, 5, 6, 7, 8, \;\;\;\; 10, 11, 12, 13, 14, 15, \;\;\;\; 17, 18, 19 \ldots\},$

$A_1\setminus A_2=B_1\setminus B_2=\{4, 9, 25, 36, 49, 64, \;\;\;\; 100, 121, \ldots \}.$

$$h\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_0\setminus A_1)\to (B_1\setminus B_2)$ и $(A_1\setminus A_2)\to (B_0\setminus B_1)$,

то есть

$$h\colon \{2, 3, 5, 6, 7, 8, \;\;\;\; 10, 11, 12, 13, 14, 15, \;\;\;\; 17, 18, 19 \ldots\}\cup \{4, 9, 25, 36, 49, 64, \;\;\;\; 100, 121, \ldots\cup \ldots\} \to$$

$$\to \{2, 3, 5, 6, 7, 8, \;\;\;\; 10, 11, 12, 13, 14, 15, \;\;\;\; 17, 18, 19 \ldots\}\cup \{4, 9, 25, 36, 49, 64, \;\;\;\; 100, 121, \ldots \}\cup \ldots \; ,$$

где $\{2, 3, 5, 6, 7, 8, \;\;\;\; 10, 11, 12, 13, 14, 15, \;\;\;\; 17, 18, 19 \ldots\}\to \{4, 9, 25, 36, 49, 64, \;\;\;\; 100, 121, \ldots \}$ и

$\{4, 9, 25, 36, 49, 64, \;\;\;\; 100, 121, \ldots \}\to \{2, 3, 5, 6, 7, 8, \;\;\;\; 10, 11, 12, 13, 14, 15, \;\;\;\; 17, 18, 19 \ldots\}$.

Дошел досюда и увидел, что здесь

$$(A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots \ne A_0,$$

потому что имеется множество $\{0, 1\}$, к которому, очевидно, относятся слова из "НАЧАЛ ТЕОРИИ МНОЖЕСТВ" Н. К. Верещагина, А.Шеня (https://www.mccme.ru/free-books/shen/sh ... art1-2.pdf, стр. 22):

Цитата:

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

Так что в моем доказательстве после слов

"Имеем также биекции

$$g\colon (B_0\setminus B_1)\to (A_1\setminus A_2), \;\; g\colon (B_1\setminus B_2)\to (A_2\setminus A_3), \;\; \ldots$$

и потому биекции

$$g^{-1}\colon (A_1\setminus A_2)\to (B_0\setminus B_1), \;\; g^{-1}\colon (A_2\setminus A_3)\to (B_1\setminus B_2), \;\; \ldots \;\; .$$

" Надо написать:

Кроме того имеются: подмножество $C$, представляющее собой пересечение всех $A_i$, подмножество $D$, представляющее собой пересечение всех $B_i$ (возможно, что $C=D=\varnothing $) и -- в случае, когда $C\ne \varnothing, D\ne \varnothing$, -- биекция $C\to D$.

Таким образом, имеем биекцию

$$h\colon C\cup (A_0\setminus A_1)\cup (A_1\setminus A_2)\cup \ldots \to D\cup (B_0\setminus B_1)\cup (B_1\setminus B_2)\cup \ldots \; ,$$

то есть биекцию

$$h\colon A\to B.$$

$\lhd$

Думаю, что теперь доказательство удовлетворительно. Или в нем еще что-то не так?

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

Ваше рассуждение, по сути, повторяет первую часть оригинального,

С этим согласен.

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

только т.к. вы не перешли к одному множеству, вам пришлось писать в два раза больше.

Но все же можно и так? И в каком-то отношении это более наглядно: теорема ведь для двух множеств, я и доказывал для двух множеств. Хотя, разумеется, можно и так, как у Н. К. Верещагина, А.Шеня.

Правда, возникает вопрос: у них имеется (биективное) отображение $C\to C$ (это хорошо видно на рис. 4). Это понятно если $C\ne \varnothing$, но если $C=\varnothing$, разве возможно отображение? Ведь при отображении элемент отображается в элемент, а в $C=\varnothing$ нет элементов. Я, чтобы избежать употребления понятия отображения $\varnothing\to \varnothing$, написал: "и в -- случае, когда $C\ne \varnothing, D\ne \varnothing$, -- (имеется) биекция $C\to D$."

Или считается, что отображение $\varnothing\to \varnothing$ существует (несмотря на то, что в $\varnothing$ нет элементов)?

[mihaild]

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

Думаю, что теперь доказательство удовлетворительно. Или в нем еще что-то не так?

Да, теперь всё так, по модулю того, что утверждения типа "$f$ задает биекцию между $A_{n} \setminus A_{n + 1}$ и $B_{n + 1} \setminus B_{n + 2}$", в принципе, тоже стоило бы обосновать.

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

Но все же можно и так?

Да, можно.

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

И в каком-то отношении это более наглядно: теорема ведь для двух множеств, я и доказывал для двух множеств.

На мой взгляд, это менее наглядно. Тут довольно стандартная ситуация: у нас есть техническое утверждение с нетривиальным доказательством (как из биекции $A_0 \to A_2$ сделать биекцию $A_0 \to A_1$), и интересное утверждение, тривиально сводящееся к этому техническому. Мне в таких ситуациях представляется разумным их разделять (и возможно техническое утверждение стоило бы вообще вынести в отдельную лемму). Но это скорее дело вкуса.

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

Или считается, что отображение $\varnothing\to \varnothing$ существует (несмотря на то, что в $\varnothing$ нет элементов)?

Это не просто считается, это следует из определения.
Вообще при чтении вы должны были заметить небольшую непоследовательность в изложении: рассуждения ведутся о функциях, но они не определены. Когда дойдете до определения функции (34 страница), подстановкой $\varnothing$ в качестве домена сможете понять, какие бывают функции с пустой областью определения.

[Vladimir Pliassov]

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

по модулю того, что утверждения типа "$f$ задает биекцию между $A_{n} \setminus A_{n + 1}$ и $B_{n + 1} \setminus B_{n + 2}$", в принципе, тоже стоило бы обосновать.

Я это подозревал.

Сначала три соображения.

1). Если $f$ -- инъекция, то $G\to f(G)$ -- биекция, поскольку, кроме того, что она инъекция, она еще и сюръекция, так как в каждый элемент $y\in f(G)$ отображается некоторый элемент $x\in G$.

2). Если $f$ -- инъекция, то и $f^{-1}$ тоже инъекция: если бы при $f^{-1}$ два элемента $y_1, y_2\in f(G)$ отображались в один и тот же элемент $x\in G$, то при отображении, обратном к $f^{-1}$ (то есть при $f$), $x$ должен был бы отображаться в два элемента $x$ и $y$, что невозможно, так как $f$ -- однозначное отображение.

3). Если $f$ инъекция, то $f$ это инъекция от любого множества, так что инъекциями являются как $G\to f(G)$, так и $H\to f(H) \;\; H\subset G$.

Теперь доказательство.

$\rhd$ Пусть $x\in A_n\setminus A_{n+1}$, тогда $x\in A_{n}$, откуда $f(x)\in B_{n+1}$, и потому $f(x)\notin B_n\setminus B_{n+1}.$

$A_n\to f(A_n)=B_{n+1}$ -- биекция, $n=\overline {0, \infty}$. Поэтому существует и биекция $B_{n+1}\to f^{-1}(B_{n+1})=A_n$.


Поскольку $f(A_{n+1})=B_{n+2}$, то $f^{-1}(B_{n+2})=A_{n+1}$, и для каждого $y'\in B_{n+2}$ имеем $f^{-1}(y')\in A_{n+1}$, так что $f^{-1}(y')\notin A_n\setminus A_{n+1}$, откуда вследствие биективности

$f$ не существует $x\in A_n\setminus A_{n+1}$, образ которого принадлежал бы $B_{n+2}$: если бы он принадлежал $B_{n+2}$, то существовало бы обратное отображение $f^{-1}(y')\in A_n\setminus A_{n+1}.$

Таким образом, $f(x)\notin B_{n+2}$.


При этом $\forall x\colon x\in A_n\setminus A_{n+1}$ имеем $f(x)\in B_n$ и поэтому $f(x)\in (B_n\setminus B_{n+2})\setminus (B_n\setminus B_{n+1})=B_{n+1}\setminus B_{n+2}$, то есть $f(A_{n} \setminus A_{n + 1})\subset B_{n + 1} \setminus B_{n + 2}$.

Аналогично доказывается, что $f^{-1}(B_{n + 1} \setminus B_{n + 2})\subset A_{n} \setminus A_{n + 1}$.


$f\colon A_{n} \setminus A_{n + 1}\to B_{n + 1} \setminus B_{n + 2}$ и $f^{-1}\colon B_{n + 1} \setminus B_{n + 2}\to A_{n} \setminus A_{n + 1}$ это инъекции. Но это и сюръекции (в этом их отличие от первоначальных инъекций

$f\colon A\to B$ и $g\colon B\to A$ для случаев, когда $f(A_0)=B_1\subsetneq B_0, \;\; g(B_0)=A_1\subsetneq A_0$), докажем это для $f^{-1}\colon B_{n + 1} \setminus B_{n + 2}\to A_{n} \setminus A_{n + 1}$:


каждый элемент $x\in (A_{n} \setminus A_{n + 1})$ функцией $f$ отображается в некоторый элемент $y\in (B_{n + 1} \setminus B_{n + 2})$, значит, при функции $f^{-1}$ каждый $x\in (A_{n} \setminus A_{n + 1})$ является

образом некоторого $y\in (B_{n + 1} \setminus B_{n + 2})$.


После доказательства того, что что $f^{-1}(B_{n + 1} \setminus B_{n + 2})\subset A_{n} \setminus A_{n + 1}$, аналогично доказывается, что и $f\colon A_{n} \setminus A_{n + 1}\to B_{n + 1} \setminus B_{n + 2}$ -- сюръекция.

Таким образом, $f\colon A_{n} \setminus A_{n + 1}\to B_{n + 1} \setminus B_{n + 2}$ -- биекция. $\lhd$

[mihaild]

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

Если $f$ -- инъекция, то и $f^{-1}$ тоже инъекция

Тут нужно чуть точнее - какой у неё домен? И еще можно заметить, что если $f^{-1}$ вообще определена, то из этого уже следует, что $f$ и $f^{-1}$ инъекции.

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

Если $f$ инъекция, то $f$ это инъекция от любого множества

Тут понятно, что вы хотите сказать, но только благодаря контексту. Правильно так: если $f$ инъекция, то её ограничение на любое подмножество области определения тоже инъекция.

Само рассуждение получается слишком длинным, и использует $f^{-1}$ без каких-либо уточнений, хотя собственно существования этой функции нам и достаточно.

Лучше так.
Пусть $x \in A_n \setminus A_{n + 1}$, тогда $f(x) \in B_{n + 1} \setminus B_{n + 2}$ (доказывается в 1 строчку).
Пусть $y \in B_{n + 1} \setminus B_{n + 2}$. Тогда существует $x \in A_n \setminus A_{n + 1}$ такой что $f(x) = y$ (доказывается тоже в одну строчку).
Из этого по определению следует, что $f_{A_n \setminus A_{n + 1}}$ - биекция между $A_n \setminus A_{n + 1}$ и $B_{n + 1} \setminus B_{n + 2}$.

[Vladimir Pliassov]

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

Пусть $x \in A_n \setminus A_{n + 1}$, тогда $f(x) \in B_{n + 1} \setminus B_{n + 2}$ (доказывается в 1 строчку).

Я доказывал по такой схеме: $f(x)\notin B_n\setminus B_{n+1}$ и $f(x)\notin B_{n+2}$ и при этом $f(x)\in B_n$, поэтому $f(x) \in B_{n + 1} \setminus B_{n + 2}$. Но ведь то, что $f(x)\notin B_n\setminus B_{n+1}$ и $f(x)\notin B_{n+2}$ надо доказать? Или то, что $f(x) \in B_{n + 1} \setminus B_{n + 2}$ можно доказать как-то иначе?

[mihaild]

Да, $B_n$ тут вообще не нужно.
По определению, $B_{n + 1} = f(A_n)$, поэтому $x \in A_n \setminus A_{n + 1} \rightarrow x \in A_n \rightarrow f(x) \in B_{n + 1}$.
Аналогично, $B_{n + 2} = f(A_{n + 1})$, поэтому $f(x) \in B_{n + 2} \rightarrow x \in A_{n + 1}$ (тут нужна инъективность), соответственно $x \in A_n \setminus A_{n + 1} \rightarrow x \notin A_{n + 1} \rightarrow f(x) \notin B_{n + 2}$.
Комбинируя, $x \in A_n \setminus A_{n + 1} \rightarrow f(x) \in B_{n + 1} \wedge f(x) \notin B_{n + 2}$.

[Vladimir Pliassov]

Да, действительно, можно обойтись без $B_n$, достаточно показать, что $f(x) \in B_{n + 1} \wedge f(x) \notin B_{n + 2}$.

Но Вы пишете: $x \notin A_{n + 1} \rightarrow f(x) \notin B_{n + 2}$, а, по-моему, это еще надо доказать.

То, что $x \in A_{n + 1} \rightarrow f(x) \in B_{n + 2}$ (как и вообще то, что $x \in A_{n} \rightarrow f(x) \in B_{n + 1}$), выводится из того, что $x \in A \rightarrow f(x) \in f(A)$.

Но

$$x \notin A_{n + 1} \rightarrow f(x) \notin B_{n + 2}$$

из

$$x \in A_{n + 1} \rightarrow f(x) \in B_{n + 2},$$

как мне кажется, не следует непосредственно, то есть не принимая во внимание конкретные обстоятельства, по логике: из того, что $P\to Q$ разве следует, что $\neg P\to \neg Q$? Если гром грянул, то мужик перекрестился, но если гром не грянул, разве не может мужик, тем не менее, перекреститься, например, проходя мимо церкви?

Можно ли здесь применить таблицу истинности?

То, что $x \notin A_{n + 1} \rightarrow f(x) \notin B_{n + 2},$ можно, по-моему, доказать так:

$$y'\in B_{n + 2}\to f^{-1}(y') \in A_{n + 1}\to f^{-1}(y') \notin (A_{n}\setminus A_{n + 1}).$$

Отсюда

$$x\in (A_{n}\setminus A_{n + 1})\to f(x)\notin B_{n + 2}$$

(потому что, если бы было $f(x)\in B_{n + 2}$, то было бы $f^{-1}\big(f(x)\big)=x\in A_{n + 1}$), но $x\notin A_{n + 1}.$

[mihaild]

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

как мне кажется, не следует непосредственно, то есть не принимая во внимание конкретные обстоятельства, по логике: из того, что $P\to Q$ разве следует, что $\neg P\to \neg Q$?

Не следует. Поэтому я и написал, что тут нужна инъективность. Для неинъективной $f$ это неверно.
Для инъективной же $f$ выполнено $x \notin C \rightarrow f(x) \notin f(C)$. Потому что $f(x) \in f(C) \rightarrow \exists x' \in C: f(x) = f(x')$, и из инъективности $x = x'$.

ИМХО тут не стоит писать $f^{-1}$, на данном этапе частичные обратные только запутывают.

[Vladimir Pliassov]

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

Для инъективной же $f$ выполнено $x \notin C \rightarrow f(x) \notin f(C)$. Потому что $f(x) \in f(C) \rightarrow \exists x' \in C: f(x) = f(x')$, и из инъективности $x = x'$.

Спасибо, понял.

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

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

Пусть $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 в сообщении #1574729 писал(а):

Само рассуждение получается слишком длинным, и использует $f^{-1}$ без каких-либо уточнений,

Какие уточнения Вы имеете в виду (на случай использования $f^{-1}$)?

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

Тут довольно стандартная ситуация: у нас есть техническое утверждение с нетривиальным доказательством (как из биекции $A_0 \to A_2$ сделать биекцию $A_0 \to A_1$), и интересное утверждение, тривиально сводящееся к этому техническому. Мне в таких ситуациях представляется разумным их разделять (и возможно техническое утверждение стоило бы вообще вынести в отдельную лемму). Но это скорее дело вкуса.

Это я не очень хорошо понимаю.

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

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

Если $f$ -- инъекция, то и $f^{-1}$ тоже инъекция

Тут нужно чуть точнее - какой у неё домен? И еще можно заметить, что если $f^{-1}$ вообще определена, то из этого уже следует, что $f$ и $f^{-1}$ инъекции.

Здесь я исходил из того, что любое отображение, как однозначное, так и многозначное, имеет обратное: при многозначном не получается обратного инъективного, при неинъективном получается многозначное обратное. Там дальше у меня написано:

"если бы при $f^{-1}$ два элемента $y_1, y_2\in f(G)$ отображались в один и тот же элемент $x\in G$, то при отображении, обратном к $f^{-1}$ (то есть при $f$), $x$ должен был бы отображаться в два элемента $x$ и $y$, что невозможно, так как $f$ -- однозначное отображение." Это ведь правильно? Или я что-то упустил? И здесь ведь $G$ это домен?

[mihaild]

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

Какие уточнения Вы имеете в виду (на случай использования $f^{-1}$)?

Писать $f^{-1}$ очень удобно, когда $f$ является биекцией. В тех же случаях, когда $f$ всего лишь инъекция, $f^{-1}$ оказывается только частичной функцией, и надо внимательно следить, что мы её применяем только там, где она определена. В рассуждениях подобных этому ИМХО это отслеживание отнимает больше сил, чем экономит введение $f^{-1}$.

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

Это я не очень хорошо понимаю

Есть два утверждения:
1. Если $A_2 \subset A_1 \subset A_0$, и $|A_2| = |A_0|$, то $|A_1| = |A_0|$. Это утверждение выглядит не очень естественно, но его доказательство относительно интересно.
2. Если $|A| \leq |B|$ и $|B| \leq |A|$, то $|A| = |B|$ (теорема Кантора-Бернштейна). Это утверждение содержательно, но самый простой способ его доказать - это доказать утверждение 1 (само по себе непонятно зачем нужное), и дальше из утверждения 1 вывести утверждение 2 (а это уже делается очень просто).

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

Здесь я исходил из того, что любое отображение, как однозначное, так и многозначное, имеет обратное: при многозначном не получается обратного инъективного, при неинъективном получается многозначное обратное

Термин "отображение" для многозначного случая лучше не употреблять, слишком часто отображение считается синонимом функции. Для общего случая есть термин "бинарное отношение" (или иногда просто "отношение"), это дальше в книге будет.

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

Это ведь правильно?

Это зависит от деталей определений. Если считать, что отображение - это произвольное бинарное отношение (подмножество декартова квадрата), то всё так. Если же это функция, то говорить об отображении, обратном к $f^{-1}$, если она неинъективна, вообще нельзя.

[Vladimir Pliassov]

Спасибо!

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

$A = B = \mathbb N$ и $f(x) = g(x) = x^2$

Теперь хотелось бы найти побольше разных примеров множеств $A$ и $B$, не равных друг другу, и функций $f$ и $g$, также не одинаковых, как для случаев, когда $\bigcap _i A_i= \bigcap _i B_i=\varnothing$, так и для случаев, когда $\bigcap _i A_i\ne \varnothing, \; \bigcap _i B_i\ne \varnothing$ (кстати, может ли быть одновременно $\bigcap _i A_i=\varnothing$ и $\bigcap _i B_i\ne \varnothing$?).

Например, при $A= \mathbb N\setminus \{0\}, B=\mathbb N\setminus \{0, 1\}$ и $f(x)=2x, y=x^2$ имеем $\bigcap _i A_i= \bigcap _i B_i=\varnothing$.

[mihaild]

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

кстати, может ли быть одновременно $\bigcap _i A_i=\varnothing$ и $\bigcap _i B_i\ne \varnothing$?

А можете ли вы выразить одно пересечение через другое? Хотя бы для конечных индексов?

[Vladimir Pliassov]

$f(\bigcap _i A_i)=\bigcap _i B_i$. Поскольку $f$ -- биекция, то $\bigcap _i A_i=\varnothing \wedge \bigcap _i B_i\ne \varnothing$ невозможно?