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

[Vladimir Pliassov]

Geen в сообщении #1575163 писал(а):

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

А, надо $A\cap P=\{\varnothing\}$. Спасибо! Соответственно, ответ на второй вопрос: нет.

Пересечение множеств это множество.

[svv]

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

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

Пересечением множеств $A$ и $B$ является множество, каждый элемент которого (а не оно само!) принадлежит и $A$, и $B$.

[Vladimir Pliassov]

svv в сообщении #1575176 писал(а):

Пересечением множеств $A$ и $B$ является множество, каждый элемент которого (а не оно само!) принадлежит и $A$, и $B$

Пусть $C=A\cap B$ и $(C\in A) \wedge (C\in B)$. Тогда $C\in C$, что, как я читал, строго-настрого запрещено в системе Цермело — Френкеля.

[mihaild]

Правильно, следовательно, $C$, удовлетворяющего этому условию не существует - пересечение двух множеств не может быть элементом их обоих.

[Vladimir Pliassov]

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

Правильно, следовательно, $C$, удовлетворяющего этому условию не существует

в системе Цермело — Френкеля, но, может быть, в какой-то другой системе существует?

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

пересечение двух множеств не может быть элементом их обоих.

Но при этом оно может быть элементом одного из них: пусть $A=\{x, y, \{x\}\}, B=\{x, z\}$. Тогда $A\cap B=\{x\}\in A$.

[mihaild]

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

в системе Цермело — Френкеля, но, может быть, в какой-то другой системе существует?

Да, говорить о существовании абстрактных объектов есть смысл только применительно к какой-то модели. Тут есть некоторые тонкие моменты (ZF это набор аксиом, а множества существуют или нет в её моделях), но пока что достаточно, что ZF (включающая аксиому регулярности) доказывает, что не существует множества с указанными вами свойствами.
Есть и другие подходы, например в учебнике Куратовского, если я правильно помню, теория множеств строится без аксиомы регулярности. Эта аксиома вне теории множеств, насколько я знаю, не слишком важна, она всего лишь удобна технически для нужд самой теории множеств. В большей части остальной математики все используемые множества строятся, в конечном итоге, из натуральных чисел, и автоматически получаются фундированными.

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

Но при этом оно может быть элементом одного из них

Да, может.

[Vladimir Pliassov]

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

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

Функцию $f$ можно рассматривать безотносительно к ее области определения и области значений:

например, пусть $f$ это когда что-нибудь возводят в квадрат: $f(a)=a^2$ (при этом, разумеется, для объекта, который подставляется вместо $a$ должно быть определено, как именно он возводится в квадрат). Я здесь ничего не сказал об области определения и области значений $f$, область определения можно выбрать любую (для объектов, которые ее составляют, должно быть определено, как они возводятся в квадрат), область значений определится сама.

Пусть $\mathrm {dom} \,f=A, \;\; A= \{x, y, \{x, y\}\}$ и $\{x, y\}=A_2$. Пусть также дано правило, по которому при возведении множества в степень каждый его элемент возводится в эту степень. Тогда

$$f(A)=\{x, y, \{x, y\}\}^2=\{x^2, y^2, \{x, y\}^2\}, \;\; f(A_2)=\{x, y\}^2=\{x^2, y^2\}\to f(A)=\{x^2, y^2, \{x^2, y^2\}\}.$$

.

Если же для $A_2$ $f(a)=a^2$ и дано правило, по которому при возведении $A_2$ в степень каждый его элемент возводится в эту степень, а для множества $A$ $f$ определена таким образом, что для его элементов

$$f(a)=\left\{ \begin{array}{rcl} a^2 \;\; if\; a=\{x, y\} \\ a^3\;\; if\; a=x=y\\ \end{array} \right.$$

то все равно и для $A$, и для $A_2$ определена одна и та же функция $f$:

$$f(A)=\{x^3, y^3, \{x, y\}^2\}, \;\; f(A_2)=\{x^2, y^2\}\to f(A)=\{x^3, y^3, \{x^2, y^2\}\}.$$

То есть функция $f$ для $A_2$ в составе $A$ определена так же, как и функция $f$ для $A_2$ самого по себе.

Но если функция $f$ для $A_2$ в составе $A$ определена не так же, как и функция $f$ для $A_2$ самого по себе, то это уже просто другая функция, зачем же ее считать той же самой функцией и обозначать той же буквой?

Я, наверное, опять что-то не понял.

[mihaild]

Возведение в квадрат тут лишнее - не дает ничего поверх просто $f$, и запись $\{x\}^2$ выглядит странно.

Давайте еще раз, с с начала.
У нас есть два множества, $A = \{x, y, z\}$ ($x \neq y$, $x \neq z$, $y \neq z$) и $B = \{p, q, r\}$. И есть функция $f: A \to B$, $f(x) = p$, $f(y) = q$, $f(z) = r$.
Но по этой $f$ легко можно построить новую функцию, $g: 2^A \to 2^B$, определенную как обсуждалось выше. Будет, например, $g(\{z\}) = \{r\}$ и $g(\{x, y\}) = \{p, q\}$.
Тут пока что всё строго.

Но оказывается, что функция, подобная $g$, нужна очень часто, при этом мы часто имеем $A \cap 2^A = \varnothing$. Поэтому тут есть уже менее строгое обозначение: а именно, давайте разрешим писать $f(t)$ не только для $t \in A$, но и для $t \in 2^A$.
С этим не возникает проблем, пока $A \cap 2^A$ пусто - строго говоря, мы просто вводим новую функцию $h: A \cup 2^A \to B \cup 2^B$, определенную по правилу

$$h(t) = \begin{cases} f(t), t \in A \\ g(t), t \in 2^A\end{cases}$$

И договариваемся, что дальше у нас $f$ будет обозначать $h$ (хотя вообще говоря, конечно, переиспользовать уже введенные символы нехорошо).
Проблема начинается, если $A \cap 2^A$ непусто, например если $z = \{x, y\}$ - в этом случае $h$ не является корректно определенной. Поэтому для таких случаев писать $f(t)$ подразумевая $g(t)$ не стоит.
И, разумеется, для произвольного множества $A$ ничего не известно про то, пересекается ли оно с каким-нибудь из своих элементов. В этом случае, когда мы видим запись $f(t)$, она может означать как $f(t)$ в стандартном смысле, так и $g(t)$, и что именно - приходится догадываться из контекста. Это неприятно, но, увы, традиционные обозначения такие.

Т.е. да, $f$ для $A_2$ "в составе" $A$ (т.е. как подмножества $A$) может быть определена не так, как $f$ для $A_2$ "самого по себе" (как элемента $A$). На практике проблем с этим нет, но с формальными определениями могут быть.

[Vladimir Pliassov]

Спасибо! Теперь я, кажется, почти все понял, хотелось бы только кое-что уточнить.

Для этого хотел бы сначала повторить, что функцию $f$ можно рассматривать безотносительно к ее области определения и области значений (это понадобится ниже), например, если $f(t)=t^2$, то, независимо от области определения $f$ (от $\mathrm {dom} \,f$), любой объект, который подставляется вместо $t$, возводится в квадрат (при этом, разумеется, для объекта, который подставляется вместо $t$ должно быть определено, как именно он возводится в квадрат). Это касается как элементов, так и множеств. При возведении в квадрат множества каждый элемент множества возводится в квадрат.

При $f\colon A\to B\colon f(t)=t^2 \;\; t\in A$ возводить множество в квадрат приходится, когда какой-то элемент из $A$ представляет собой множество, например, когда $A = \{x, y, z\}$ ($x \neq y$, $x \neq z$, $y \neq z$) и $z=\{x, y\}$ (здесь $A$ пересекается со своим элементом $z$), то есть $A = \{x, y, \{x, y\}\}$ и надо возвести в квадрат $z=\{x, y\}$.

(Когда выбрана область определения $f$, область значений $f$ определяется сама собой.)

Когда функция возводит аргумент не в квадрат, а, скажем, в куб, то, естественно, ее следует обозначить другой буквой, например, $g\colon g(t)=t^3$.

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

Но оказывается, что функция, подобная $g$, нужна очень часто, при этом мы часто имеем $A \cap 2^A = \varnothing$. Поэтому тут есть уже менее строгое обозначение: а именно, давайте разрешим писать $f(t)$ не только для $t \in A$, но и для $t \in 2^A$.
С этим не возникает проблем, пока $A \cap 2^A$ пусто - строго говоря, мы просто вводим новую функцию $h: A \cup 2^A \to B \cup 2^B$, определенную по правилу

$$h(t) = \begin{cases} f(t), t \in A \\ g(t), t \in 2^A\end{cases}$$

И договариваемся, что дальше у нас $f$ будет обозначать $h$ (хотя вообще говоря, конечно, переиспользовать уже введенные символы нехорошо).
Проблема начинается, если $A \cap 2^A$ непусто, например если $z = \{x, y\}$ - в этом случае $h$ не является корректно определенной. Поэтому для таких случаев писать $f(t)$ подразумевая $g(t)$ не стоит.

Я думаю, что проблема здесь начинается, только если, безотносительно к области определения, $f\ne g$, то есть, например, если $f(t)=t^2$, а $g(t)=t^3$. Тогда нельзя не определиться: возводить в квадрат или в куб (разумеется, если элемент-прообраз не равен нулю или единице), и если не определились, возникает проблема.

Если же $f=g$, и разные буквы взяты только потому, что $f$ берется для области определения, равной $A$, а $g$ для области определения, равной $2^A$, то, даже если $A \cap 2^A$ непусто, проблемы не будет, потому что либо каждый элемент $A \cup 2^A$ будет возводиться в квадрат, либо каждый элемент $A \cup 2^A$ будет возводиться в куб.

Отмечу, что $A \cap 2^A$ непусто только в том случае, когда $A$ пересекается с каким-то своим элементом, если не пересекается, то $A \cap 2^A$ пусто, и нет проблемы с тем, чтобы $h$ обозначить как $f$.

[mihaild]

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

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

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

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

Это касается как элементов, так и множеств. При возведении в квадрат множества каждый элемент множества возводится в квадрат.

Это не очень хорошее определение, потому что в теории множеств все элементы - это тоже множества, ничего другого не бывает. Чтобы работать с другими объектами, нужно их как-то обозначать множествами. Например, число $2$ обычно обозначается множеством $\{\varnothing, \{\varnothing\}\}$ (потому что число $0$ удобно задавать пустым множеством, а для $n+1$ использовать $n \cup \{n\}$). Про это (задание натуральных чисел множествами) пока не надо особо думать, дальше в книге будет изложено подробнее, но иметь в виду, что всё, что есть в теории множеств - это множества - нужно.

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

Я думаю, что проблема здесь начинается, только если, безотносительно к области определения, $f\ne g$, то есть, например, если $f(t)=t^2$, а $g(t)=t^3$.

Тут получается, что вы квадратом и кубом обозначаете просто какие-то произвольные функции, поэтому их введение ничего особо не дает. И в объяснении выше $g$ полностью определяется по $f$.
Но попробую объяснить в ваших обозначениях:

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

При возведении в квадрат множества каждый элемент множества возводится в квадрат.

При $f\colon A\to B\colon f(t)=t^2 \;\; t\in A$ возводить множество в квадрат приходится, когда какой-то элемент из $A$ представляет собой множество, например, когда $A = \{x, y, z\}$ ($x \neq y$, $x \neq z$, $y \neq z$) и $z=\{x, y\}$ (здесь $A$ пересекается со своим элементом $z$), то есть $A = \{x, y, \{x, y\}\}$ и надо возвести в квадрат $z=\{x, y\}$.

Нам никто не вправе запретить рассмотреть функцию $f_1$, такую что $f_1(x) = x^2$, $f_1(y) = y^2$, $f_1(\{x, y\}) = \text{жёлтые ботинки}$. При этом построенная по ней $g_1$ будет иметь $g_1(\{x, y\}) = \{f_1(x), f_1(y)\} = \{x^2, y^2\} \neq \text{жёлтые ботинки}$.

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

Если же $f=g$, и разные буквы взяты только потому, что $f$ берется для области определения, равной $A$, а $g$ для области определения, равной $2^A$,

Так не бывает, функции с разными областями определения не равны.

[ewert]

Можно 5 коп.? Уже третью страницу идёт совершенно праздный разговор, если именно применительно к Кантору-Бернштейну. Ведь при доказательстве этой теоремы с самого начала подразумевается, что оба вложения строгие и, соответственно, области определения функций на каждом шаге не пусты (в противном случае само утверждение теоремы оказывается тривиальным; и, кстати, по этой же причине подразумевается, что оба множества бесконечны, но это уже технические детали).

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

[mihaild]

ewert в сообщении #1575319 писал(а):

Уже третью страницу идёт совершенно праздный разговор, если именно применительно к Кантору-Бернштейну.

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

[Vladimir Pliassov]

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

но с этим тоже разобраться надо.

Совершенно согласен.

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

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

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

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

Да, конечно, поскольку функция это отображение из множества в множество, без этих множеств ее не бывает. Я неправильно называл функцией то, что имел в виду. Я имел в виду то, чем похожи, как Вы говорите, "чем-то похожие функции на разных доменах", то есть тот принцип, по которому, независимо от того, на каком домене, при отображении по прообразу определяется образ (я думаю, Вы это имели в виду). Для функции $f(t)=t^2$ этим принципом является: "на входе $t$, на выходе $t^2$".

Назовем этот принцип принципом функции и для функции $f$ обозначим его $\dot f$ ($f$ с точкой над). Тогда, независимо от того, на каком домене, функция $f(t)=t^2$ имеет принцип $\dot f(t)=t^2$, по которому аргумент возводится в квадрат.

Принципом функции $g(t)=t^2$ является $\dot g(t)=t^2$, и $\dot g(t)=\dot f(t)$, или просто $\dot g=\dot f$.

Принципом функции $h(t)=t^3$ является $\dot h(t)=t^3$, и $\dot h(t)\ne \dot f(t)$, или просто $\dot h\ne \dot f$.

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

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

Но оказывается, что функция, подобная $g$, нужна очень часто, при этом мы часто имеем $A \cap 2^A = \varnothing$. Поэтому тут есть уже менее строгое обозначение: а именно, давайте разрешим писать $f(t)$ не только для $t \in A$, но и для $t \in 2^A$.
С этим не возникает проблем, пока $A \cap 2^A$ пусто - строго говоря, мы просто вводим новую функцию $h: A \cup 2^A \to B \cup 2^B$, определенную по правилу

$$h(t) = \begin{cases} f(t), t \in A \\ g(t), t \in 2^A\end{cases}$$

И договариваемся, что дальше у нас $f$ будет обозначать $h$ (хотя вообще говоря, конечно, переиспользовать уже введенные символы нехорошо).
Проблема начинается, если $A \cap 2^A$ непусто, например если $z = \{x, y\}$ - в этом случае $h$ не является корректно определенной. Поэтому для таких случаев писать $f(t)$ подразумевая $g(t)$ не стоит.

Я думаю, что проблема здесь начинается, только если $\dot f\ne \dot g$, то есть, например, если $f(t)=t^2$, а $g(t)=t^3$. Тогда нельзя не определиться: возводить в квадрат или в куб (разумеется, если элемент-прообраз не равен нулю или единице), и если не определились, возникает проблема.

Если же $\dot f=\dot g$, то, даже если $A \cap 2^A$ непусто, проблемы не будет, потому что либо каждый элемент $A \cup 2^A$ будет возводиться в квадрат, либо каждый элемент $A \cup 2^A$ будет возводиться в куб.

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

Нам никто не вправе запретить рассмотреть функцию $f_1$, такую что $f_1(x) = x^2$, $f_1(y) = y^2$, $f_1(\{x, y\}) = \text{жёлтые ботинки}$. При этом построенная по ней $g_1$ будет иметь $g_1(\{x, y\}) = \{f_1(x), f_1(y)\} = \{x^2, y^2\} \neq \text{жёлтые ботинки}$.

Конечно, такая функция может быть задана, но (тут, наверное, недоразумение) я задал (как я полагал) не просто функцию $f_1(t) = t^2$, а функцию $f_1(t) = t^2$ с условием, что

при возведении в квадрат множества каждый элемент множества возводится в квадрат, поэтому $f_1(\{x, y\})=\{x, y\}^2=\{x^2, y^2\}$.

Пусть $f_1(\{x, y\}) = \text{жёлтые ботинки}$, тогда и $\{x^2, y^2\} = \text{жёлтые ботинки}$, и поэтому $g_1(\{x, y\}) = \{f_1(x), f_1(y)\} = \{x^2, y^2\}=\text{жёлтые ботинки}=f_1(\{x, y\})$.

[mihaild]

Программистский юмор писал(а):

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

У вас теперь аж три обозначения $\cdot^2$, $\dot f(\cdot)$, $f(\cdot)$ для одного и того же. Это просто перегоняет проблему на другой уровень обозначений.

А содержательная проблема в следующем: для функции $f$ значение $f(\{x, y\})$ не обязано никак быть связано со значениями $f(x)$ и $f(y)$. Для функции $g$ обязательно выполнено $g(\{x, y\}) = g(\{x\}) \cup g(\{y\})$.
Т.е. никто априори не сказал, что магическая операция "возведение в квадрат" должна удовлетворять свойству $\{x, y\}^2 = \{x^2, y^2\}$ - бывают и операции, этому свойству не удовлетворяющие. И именно с ними будут проблемы при отождествлении $f$ и $g$.

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

я задал (как я полагал) не просто функцию $f_1(t) = t^2$, а функцию $f_1(t) = t^2$ с условием, что при возведении в квадрат множества каждый элемент множества возводится в квадрат

Такую функцию вы задать можете, и для функции такого вида проблем с отождествлением $f$ и $g$ действительно не будет даже если $A \cap 2^A \neq \varnothing$. Но это накладывает существенное ограничение на функцию $f$.

Собственно в тексте доказательства из книги: $f(A_2) = A_4$. Но при этом вполне может быть, что $A_2$ является элементом $A$, но при этом $A_4$ вообще не является элементом $A$, и отображение $f$ может переводить $A_2$ (как элемент $A$) вообще в любой элемент $A$, не беспокоясь о том, куда оно переводит элементы самого $A_2$.

[Vladimir Pliassov]

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

У вас теперь аж три обозначения $\cdot^2$, $\dot f(\cdot)$, $f(\cdot)$ для одного и того же.

Нет, $\dot f(\cdot)$ это для одного, $f(\cdot)$ для другого, а $\cdot^2$ -- и для одного, и для другого. Мне никак не удается объяснить то, что мне кажется очень простым: что и при $f(t)=t^2 \;\; t\in \mathbb Z$, и при $f(t)=t^2 \;\; t\in \mathbb Q$ аргумент возводится в квадрат, то есть это происходит независимо от того, на каком домене. Это значит, что принцип $\dot f\colon$ "на входе $t$, на выходе $t^2$" не зависит от домена.

$f(\cdot)$ это функция, она не отделима от конкретного домена, когда домен меняется, она перестает быть тем, чем она была.

А $\dot f(\cdot)$ это то, что я назвал принципом функции (но можно назвать по-другому), он не меняется при смене домена.