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

[mihaild]

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

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

Тут биективность не нужна. Докажите, что для любой функции $f$, $f(\varnothing) = \varnothing$.

-- 23.12.2022, 19:08 --

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

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

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

[Vladimir Pliassov]

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

Докажите, что для любой функции $f$, $f(\varnothing) = \varnothing$.

Мне пришло в голову, что аргументом функции может ведь быть не только элемент множества, но и его подмножество, и если принять, что каждое подмножество может быть аргументом, то и пустое тоже, и при этом функцией также должно являться подмножество (а нет элемент).

Я пока что не нашел почти ничего о функции от $\varnothing$.

[mihaild]

А, вы этого обозначения не знаете?
Формально, если $f: A \to B$ и $C \subseteq A$, то $f(C) = \{y \in B | \exists x \in C: f(x) = y\}$ - т.е. множество, состоящее из образов всех элементов из $C$. Это просто соглашение о записи.
(для случая, когда элементы множества с ним не пересекаются; если пересекаются, то лучше такую нотацию не использовать)

[Vladimir Pliassov]

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

Докажите, что для любой функции $f$, $f(\varnothing) = \varnothing$.

Как я понимаю, имея дело с пустым множеством $\varnothing$, приходится иметь дело с несуществующими вещами -- его элементами -- и с отношениями несуществующих вещей с существующими, например, с $\varnothing$ (которое существует, в отличие от своих элементов) и высказывать такие суждения как: "Если $x$ является элементом множества $\varnothing,$ то $x$ не существует ($x\in \varnothing \to \nexists x$)", или: "Если множество $B$ состоит только из несуществующих элементов, то $B=\varnothing$ (не знаю, как это записать символами).

Поэтому, по-моему, должна быть аксиома (или доказанное утверждение) "Если $x$ не существует, то и его образ $f(x)$ не существует ($\nexists x\to \nexists f(x)$)." (Мы утверждаем, что $x$ не существует, но, тем не менее, рассматриваем его образ и высказываем об этом образе суждение -- что он не существует.)

Используя это утверждение, утверждения, приведенные выше, и утверждение "если $f: A \to B$ и $C \subseteq A$, то $f(C) = \{y \in B |\; \; \forall x \in C: f(x) = y\}$ ", можно доказать, что $\forall f\colon f(\varnothing) = \varnothing$.

$\rhd$ Пусть $f(\varnothing)=B$, и пусть $x\in \varnothing$. Тогда $f(x)\in B$. Из того, что $x\in \varnothing$, следует также, что $\nexists x$, а отсюда следует, что и $\nexists f(x)$. Поскольку $B$ состоит из одних только $f(x)$, и при этом ни один $f(x)$ не существует, то $B$ состоит только из несуществующих элементов, и потому $B=\varnothing$, то есть $f(\varnothing) = \varnothing$ $.\lhd$

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

Формально, если $f: A \to B$ и $C \subseteq A$, то $f(C) = \{y \in B | \exists x \in C: f(x) = y\}$ - т.е. множество, состоящее из образов всех элементов из $C$.

Я думаю, что Вы хотели поставить не $\exists x$, а $\forall x$?

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

Это просто соглашение о записи.
(для случая, когда элементы множества с ним не пересекаются; если пересекаются, то лучше такую нотацию не использовать)

Я не понял, что Вы здесь имели в виду. Пересекаются множества, а элемент не является множеством (он является элементом одноэлементного подмножества). Разве может элемент пересекаться с множеством?

[mihaild]

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

приходится иметь дело с несуществующими вещами -- его элементами

Вот так думать скорее не надо.
Когда мы говорим "для всех элементов множества $A$ выполнено $P$", это означает, что если мы возьмем какой-то элемент $x$, проверим, принадлежит ли он $A$, и если окажется что принадлежит - то для него выполнено $P$. Если $A$ пустое, то процедура та же самая, просто мы никогда не дойдем до проверки собственно $P$.
Никаких "несуществующих элементов" нет.

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

($x\in \varnothing \to \nexists x$)

Вот так писать нельзя. Если вы делаете утверждение про $x$, то по нему не может быть кванторов.

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

$\nexists x\to \nexists f(x)$)

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

Исходя из вышесказанного, ваше рассуждение не является корректно сформулированным. Попробуйте еще раз. Вам нужно доказать, что $(x \in f(\varnothing)) \rightarrow \bot$ (например, можно взять и другую эквивалентную формулировку).

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

Я думаю, что Вы хотели поставить не $\exists x$, а $\forall x$?

Нет, именно $\exists x$. Элемент принадлежит образу множества ($f(C)$ называется образом $C$), если хотя бы что-то из множества отображается в этот элемент.

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

Разве может элемент пересекаться с множеством?

Да, рассмотрите, например множество $A = \{x, \{x\}\}$ (что такое $x$ - неважно). Какие у него элементы? Для каждого элемента $A$, найдите пересечение этого элемента с множеством $A$.

[Vladimir Pliassov]

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

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

Я думаю, что Вы хотели поставить не $\exists x$, а $\forall x$?

Нет, именно $\exists x$.

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

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

рассмотрите, например множество $A = \{x, \{x\}\}$ (что такое $x$ - неважно). Какие у него элементы? Для каждого элемента $A$, найдите пересечение этого элемента с множеством $A$.

Элементы множества $A$ это $x$ и $\{x\}$. $A\cap x=\varnothing, A\cap \{x\}=x$.

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

Когда мы говорим "для всех элементов множества $A$ выполнено $P$", это означает, что если мы возьмем какой-то элемент $x$, проверим, принадлежит ли он $A$, и если окажется что принадлежит - то для него выполнено $P$. Если $A$ пустое, то процедура та же самая, просто мы никогда не дойдем до проверки собственно $P$.

Элемент множества это некоторый объект, который множество содержит в качестве своего элемента.
$\varnothing$ -- множество, не содержащее ни одного элемента, следовательно, оно не содержит ни одного объекта в качестве своего элемента.
$x$ -- объект, следовательно, он не является элементом $\varnothing$.
Дальше не идем.

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

Никаких "несуществующих элементов" нет.

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

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

Когда мы говорим "для всех элементов множества $A$ выполнено $P$"

$A$ это переменная, если вместо нее можно вставить любое множество, вставим $\varnothing$, получим: "для всех элементов множества $\varnothing$ выполнено $P$". Получается, что мы высказываем суждение о несуществующих вещах, то есть об элементах множества $\varnothing$, что не допускается. Значит, относительно высказывания "для всех элементов множества $A$ выполнено $P$" должно иметься в виду, что $A\ne \varnothing$.

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

Докажите, что для любой функции $f$, $f(\varnothing) = \varnothing$.

Но верно ли, что для любой функции $f$, $f(\varnothing) = \varnothing$?

Пусть дано два множества: $A=\{a, \varnothing\}$ и $B=\{b, \varnothing\}$ и множества их подмножеств: $P=\{\{a, \varnothing\}, \{a\}, \{\varnothing\}, \varnothing\}$ и $Q=\{\{b, \varnothing\}, \{b\}, \{\varnothing\}, \varnothing\}$. Зададим биекцию $f\colon P\to Q\colon \{a, \varnothing\}\mapsto \{b, \varnothing\}, \{\varnothing\}\to \{\varnothing\}, \{a\}\mapsto \varnothing, \varnothing\mapsto \{b\}$. Таким образом, $f(\varnothing)=\{b\}$ (где $b$ существует, и потому $\{b\}\ne \varnothing$), то есть $f(\varnothing) \ne \varnothing$.

[mihaild]

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

Это берется как аксиома в той системе теории множеств, с которой я сейчас пытаюсь познакомиться

Нет, это не берется как аксиома, это просто из синтаксиса следует. В логике первого порядка нет способа записать "объект $x$ не существует". Там можно записать только "неверно, что существует $x$, такой что что-нибудь" (где, конечно, "что-нибудь" может быть и тождественной истинной, но тогда получившееся утверждение будет ложным).

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

В защиту этой идеи могу привести тот факт, что и лошадь, и привидение это существительные, хотя лошадь существует, а привидение нет

Это означает, что существует понятие "привидение". Но предъявить привидение, чтобы потом про него сказать, что его не существует - нельзя.

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

В такой системе мое доказательство того, что $f(\varnothing) = \varnothing$, по-моему, корректно

Такая система должна очень сильно отличаться от всего используемого в математике, поэтому, подозреваю, думать о ней не очень полезно.
Про то, как можно и как нельзя использовать кванторы написано в другом томе той же серии, "Языки и исчисления". Но для того чтобы изучать основы теории множеств он избыточен, это свой, довольно отдельный, раздел. Скорее всего проще просто сначала привыкнуть и попрактиковаться с тем, как правильно формулировать утверждения. Обычно у математиков даже не изучавших логические исчисления отдельно не возникает больших сложностей с тем, чтобы отличить корректную (синтаксически) формулировку от некорректной.
В частности, формулировка "тогда $x$ не существует" некорректна. Потому что когда мы записываем утверждение, то квантор существования записывается в начале, и дальше всё утверждение использует какой-то конкретный (но неизвестный) объект, и означает, что можно стереть квантор, вместо $x$ подставить какой-то объект (везде один и тот же) и получить верное утверждение (тут есть тонкий момент про то, как подставлять объекты в формулы - строго говоря, формулы это строчки, и множества или там натуральные числа в них писать нельзя, но думаю должно быть примерно понятно).

Т.е. если вы начинаете с предположения

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

Пусть $f(\varnothing)=B$, и пусть $x\in \varnothing$

То вы, конечно, придете к противоречию. Но оно вам всего лишь скажет, что либо $f(\varnothing) \neq B$, либо $x \notin \varnothing$. И поскольку второе очевидно истинно, то ничего полезного про первое получить не удастся.
Надеюсь, стало понятнее.

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

Но верно ли, что для любой функции $f$, $f(\varnothing) = \varnothing$?
Пусть дано два множества: $A=\{a, \varnothing\}$ и $B=\{b, \varnothing\}$

Да, тут вы правильно нашли еще один вариант, когда применение функции к подмножеству области определения можно трактовать неоднозначно.
Давайте, чтобы от этого избавиться, тут договоримся для $f: A \to B$ писать $f(x)$ для $x \in A$ (и понятно что это означает), а для $C \subset A$ писать $f[C]$ (с квадратными скобками), и это будет обозначать множество $\{y \in B | \exists x \in C: f(x) = y\}$.
Таким образом $f(x)$ и $f[x]$ - разные понятия. И вопрос выше относился к $f[\varnothing]$.

Обычно в очень большом количестве разделов не существует подмножества области определения, принадлежащего ей как элемент, поэтому для одного и того же множества $x$ корректна не более чем одна из записей $f(x)$ и $f[x]$, так что их обозначают одинаково; но, как вы обнаружили, в некоторых ситуациях это нарушается.
(важно: $f[C]$ не является общепринятым обозначением, я его ввёл тут для данной темы, если вы его увидите где-то в другом месте, оно вполне может означать что-то другое)

[Vladimir Pliassov]

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

применение функции к подмножеству области определения ... И вопрос выше относился к $f[\varnothing]$.

Тут, как я заметил, благодаря Вашему посту, интересное совпадение: для множества $P=\{\{a, \varnothing\}, \{a\}, \{\varnothing\}, \varnothing\}$ $\varnothing$ является одновременно и элементом множества $P$, и его подмножеством (аналогично с множеством $Q$). Но я не имел в виду, что $f(\varnothing)$ это образ $\varnothing$ как подмножества $P$, я имел в виду, что $f(\varnothing)$ это образ $\varnothing$ как элемента из $P$.

Тут разные отображения: одно отображает элементы, а другое подмножества, так что их надо обозначить разными буквами: первое $f$, а второе $g$, но при обоих этих отображениях $\varnothing$ отображается в $\{b\}$, так что для самого по себе $\varnothing$ (безотносительно к тому, является оно элементом или подмножеством) это одно и то же отображение.

Тут, так сказать, пересечение отображений $f(x)\; x\in P$ и $g(y)\; y\in P'$, где $P'$ это множество подмножеств $P$, а $g\colon P'\to Q$, во всяком случае, отображает $\varnothing\in P'$ в $\{b\}\in Q$: отображения $f(x)$ и $g(y)$ пересекаются в отображении $f[x]=g[y] \;\; x\in \{\varnothing\}, y\in \{\varnothing\}$ (здесь $\{\varnothing\}$ из выражения $x\in \{\varnothing\}$ это одноэлементное подмножество $P$, а $\{\varnothing\}$ из выражения $y\in \{\varnothing\}$ это одноэлементное подмножество $P'$), при этом образы $f(P)$ и $g(P')$ пересекаются в $f[\varnothing]=g[\varnothing]=\{b\}\in Q.$

[mihaild]

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

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

Не очень понятно. $f$ то, что вы ввели выше? А $g$ это что?
Если вы строите $g$ как отображение $2^P \to 2^Q$ ($2^X$ - это одно из стандартных обозначений для множества всех подмножеств $X$) по правилу $g(x) = \{f(p) | p \in x\}$ ($g(x) = f[x]$ в моих обозначениях выше), то будет $g[\varnothing] = \varnothing$.

[Vladimir Pliassov]

1.

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

Если вы строите $g$ как отображение $2^P \to 2^Q$ ... по правилу $g(x) = \{f(p) | p \in x\}$ ($g(x) = f[x]$ в моих обозначениях выше), то будет $g[\varnothing] = \varnothing$.

Я там написал: " $g\colon P'\to Q$, во всяком случае, отображает $\varnothing\in P'$ в $\{b\}\in Q$",-- то есть $g[\varnothing]=\{b\}.$

"Во всяком случае", отображает $\varnothing$ в $\{b\}$, потому что биекции здесь не может быть: $P'$ и $Q$ конечны, и мощность $P'$ больше мощности $Q$.

2.

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

$\varnothing$;

$\{\varnothing\}=2^\varnothing=T$ -- множество всех подмножеств $\varnothing$, их всего $2^0$;

$\big \{\{\varnothing\}, \varnothing\big \}=2^T=T'$ -- множество всех подмножеств $T$, их всего $2^1$;

$\Big \{\big \{\{\varnothing\}, \varnothing\big \},\big \{\{\varnothing\}\big \}, \{\varnothing\}, \varnothing\Big \}=2^{T'}=T''$ -- множество всех подмножеств $T'$, их всего $2^2$;

далее множество $T'''$ будет мощности $2^4$, множество $T''''$ -- мощности $2^{16}$ и так далее.

Множество $T'$ это множество $A=\{a, \varnothing\}$ при подстановке $\{\varnothing\}$ вместо $a$, $T''=P, \;T'''=P'$ при соответствующих заменах.

3. Проделав большую часть работы, я увидел, что для того, чтобы показать, что не всегда $f(\varnothing) = \varnothing$, можно было ее не проводить (но я не жалею, что ее провел, это было для меня очень полезно), достаточно взять множество $A=\{a, \varnothing\}$ и отобразить его само в себя таким образом: $f\colon A\to A\colon a\mapsto \varnothing, \varnothing \mapsto a$.

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

Обычно в очень большом количестве разделов не существует подмножества области определения, принадлежащего ей как элемент, поэтому для одного и того же множества $x$ корректна не более чем одна из записей $f(x)$ и $f[x]$, так что их обозначают одинаково

Это я не очень хорошо понимаю. Но, во всяком случае, на $\varnothing$ из выражения $A=\{a, \varnothing\}$ я смотрел не как на подмножество $A$, а как на элемент из $A$. И, по-моему, при отображении $f\colon A\to \bot$ от $\varnothing\in A$ на $\varnothing$ можно смотреть только как на элемент из $A$, а не как на подмножество множества $A$.

($\bot$ употребляют как знак для "нечто", правильно?)

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

когда применение функции к подмножеству области определения можно трактовать неоднозначно.

Должен признаться, что я все еще этого не понял. Как можно трактовать применение функции к подмножеству области определения неоднозначно? Мы просто отображаем подмножество $C\subset A$ в то же множество, в которое отображается $A$. Или я что-то не так понимаю?

[mihaild]

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

Я там написал: " $g\colon P'\to Q$,

А какое у вас определение $g$?

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

то есть $g[\varnothing]=\{b\}.$

Так точно не бывает.

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

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

Да, так можно. Обычно всё же добавляют элементы по одному: $A_0 = \varnothing$, $A_{n + 1} = A_n \cup \{A_n\}$. Так обычно строятся натуральные числа в теории множеств (про это будет дальше в книге).

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

достаточно взять множество $A=\{a, \varnothing\}$ и отобразить его само в себя таким образом: $f\colon A\to A\colon a\mapsto \varnothing, \varnothing \mapsto a$.

Да, это правильно. Если у нас $\varnothing$ принадлежит области определения, то отображение на нём может принимать произвольное значение.
Тут проблема была только в том, что одно и то же обозначение используется для двух разных вещей.

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

Но, во всяком случае, на $\varnothing$ из выражения $A=\{a, \varnothing\}$ я смотрел не как на подмножество $A$, а как на элемент из $A$

Всё правильно. Но можно еще посмотреть на него как на подмножество $A$, и спросить, какой будет образ этого подмножества. Это разные вопросы, и на них разные ответы.

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

$\bot$ употребляют как знак для "нечто", правильно?

Нет, $\bot$ - знак, обозначающий "ложь" (тождественно ложное утверждение).

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

Как можно трактовать применение функции к подмножеству области определения неоднозначно?

Вот в вашем примере.
Пусть у нас есть отображение $f: A \to B$. Тогда по нему легко построить отображение $g: 2^A \to 2^B$. Но вот это новое отображение часто обозначают той же буквой, что и старое, и $f(x)$ означает действительно $f(x)$ если $x \in A$, но эта же запись может означать $g(x)$ если $x \in 2^A$.. В случае, когда $A$ и $2^A$ не пересекаются, это не создает проблем. А вот если пересекаются (например $\varnothing \in A$) - то создает, потому что если $x \in A \cap 2^A$, то $f(x)$ можно трактовать двумя способами, и, скорее всего, получить два разных результата.
В этом нет ничего глубокого, это просто побочный эффект того, что $f$ и $g$ обозначают одной буквой. Но это обозначение слишком удобное, чтобы от него отказываться. И на самом деле оно часто довольно интуитивно - например в обсуждаемом доказательстве записано $f(A_i) = A_{i + 2}$, хотя, вообще говоря, $A_i$ совсем не обязано быть элементом $A$, и соответственно применять к нему $f$ в стандартном смысле нельзя.

[Vladimir Pliassov]

Цитата:

взаимно однозначное соответствие $f : A_0 \to A_2$, при котором $A_i$ соответствует $A_{i+2}$ (иногда это записывают так: $f(A_i)=A_{i+2}$).

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

Почему иногда? Я в подобных случаях все время так делаю и думал, что только так и делается. А как еще (если не считать записи $f[A_i]=A_{i+2}$, когда $A_i$ является подмножеством некоторого множества)? $f(A_i)=A_{i+2}$ это образ (под)множества$A_i$.

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

например в обсуждаемом доказательстве записано $f(A_i) = A_{i + 2}$, хотя, вообще говоря, $A_i$ совсем не обязано быть элементом $A$, и соответственно применять к нему $f$ в стандартном смысле нельзя.

В этом доказательстве $A_i$ не является элементом из $A$, в нем $A_i$ это подмножество $A$. Но почему Вы говорите, что применять к нему $f$ в стандартном смысле нельзя? Разве запись $f(A_i)=A_{i+2}$ в этой ситуации не стандартная?

Я хочу сказать, что я думаю, что функцию можно брать как от элемента множества, так и от множества или от подмножества множества. Разве это не так?

Если так, можно ли сказать, что множество является аргументом функции?

[mihaild]

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

Почему иногда?

Вот аналогично вашему примеру.
Представим, что $A$ содержит, в числе прочего, элементы $x, y, \{x, y\}$ и так получилось, что $A_2 = \{x, y\}$ (на самом деле прямо так получиться не может, но в данном случае неважно). Тогда в рассуждениях предполагается, что $f(A_2) = \{f(x), f(y)\}$. Но тем не менее $A_2$ само принадлежит $A$ как элемент, на нём $f$ как-то определена, и совершенно не обязательно вот так.

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

В этом доказательстве $A_i$ не является элементом из $A$, в нем $A_i$ это подмножество $A$

$A_i$ - это подмножество $A$. Оно может быть, а может не быть элементом $A$.

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

Разве запись $f(A_i)=A_{i+2}$ в этой ситуации не стандартная?

Запись довольно стандартная.
Под "применением в стандартном смысле" я имел в виду, что мы для элемента из области определения берем значение функции на этом элементе.

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

[Vladimir Pliassov]

1.

Множества $A=\{a, \varnothing\}$ и $P=2^A=\{\{a, \varnothing\}, \{a\}, \{\varnothing\}, \varnothing\}$ имеют общий элемент $\varnothing$, то есть пересекаются: $A\cap P=\varnothing$. Но, по определению, множества, пересечение которых является пустым множеством, не пересекаются. Таким образом, $A$ и $P$ не пересекаются. Что не так?

2.

Пересечением непересекающихся множеств является пустое множество, следовательно, каждое из непересекающихся множеств содержит пустое множество в качестве своего элемента. Так ли это?

[Geen]

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

имеют общий элемент $\varnothing$, то есть пересекаются: $A\cap P=\varnothing$.

Это неверно записано