Доказательство Кантора

[Sed]

Доказательство Кантора.

Формулировку взял с Вики, если есть претензии, готов поправить.

Предположим, что существует множество $A$, равномощное множеству всех своих подмножеств $2^A$, то есть, что существует такая биекция $f$, ставящая в соответствие каждому элементу множества $A$ некоторое подмножество множества $A$.

Рассмотрим множество $B$, состоящее из всех элементов $A$, не принадлежащих своим образам при отображении $f$ (оно существует по аксиоме выделения): $B=\{x\in A : x \notin f(x)\}$.

-----------------------------------

На этом моменте пока остановлюсь.
В той же вики схема аксиом выделения определена так: $\forall A \exists B \forall B (b \in c \leftrightarrow b \in a \land \varphi(b))$, где $\varphi(b)$ - любое математически корректное суждение о $b$.

Любопытно, конечно, где определен полный перечень синтаксических правил корректности математических утверждений ? Предчувствую, что конечного исчерпывающего списка нет, а если и есть какие-то критерии корректности, то сформулированы они, наверняка, теми же формулами, корректность которых они только призваны определить. Если ссылки на “теорию корректности” есть, буду признателен.

Впрочем, к математической корректности формулировки свойства $\varphi(b)$, как $B=\{x\in A : x \notin f(x)\}$ у меня претензий нет. Как, впрочем, и о дальнейших рассуждениях теоремы, приводящих к противоречию.

Я согласен с тем, что при заданных ограничениях на $f$, а именно: “элементы множества $A$ не принадлежат подмножествам $A$, которые они “нумеруют”“, действительно, отображение невозможно, т.к. $B$ пусто.
Меня больше интересует, почему этот вывод распространяется на все $f$ ?

К примеру, возьмем “множество $B$, состоящее из элементов $A$, принадлежащих своим образам при отображении $f$”. При таком $B$ и $f$ противоречия нет (по крайне мере пока это не доказано иным путем).

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

На каком именно этапе, вдруг, это маленькое противоречие относительно конкретного $f$ распространяется на все $f$ ?

На мой взгляд, это примерно тоже самое, как доказывать, отсутствие биекции между болезнями и болеющими людьми: “давайте-ка, возьмем только такую выборку, когда каждой болезни сопоставлены лишь те люди, которые ей не болеют, а т.к. по определению такое $f$ биективно, то существует болеющий человек, который ничем не болеет, противоречие, следовательно биекции, нет”.

Ну и второе замечание, теорема доказывает противоречивость свойства $\varphi$, т.к. множество $B$ - пусто. Да, свойство $\varphi: x \notin f(x)$ противоречиво, но есть неопределенная совокупность других свойств $\varphi$, например, $\varphi: x \in f(x)$. А вообще, все эти схемы выделения - просто те или иные ограничения на $f$ и доказательство для одного из них никак не распространяется на другое. Доказывать надо для общего случая, когда никаких ограничений на $f$ нет.

[Xaositect]

Можете почитать учебник Колмогоров, Драгалин. "Математическая логика". Там есть и про синтаксис формул, и про теорию множеств. Куда лучше Википедии.

Теперь по доказательству и другим вещам.

Sed в сообщении #770021 писал(а):

Ну и второе замечание, теорема доказывает противоречивость свойства $\varphi$, т.к. множество $B$ - пусто

Это неправда. Противоречие возникает не потому, что $B$ пусто, а потому, что оно не имеет прообраза. Либо в википедии написана чушь, либо Вы что-то неправильно поняли.

Sed в сообщении #770021 писал(а):

На каком именно этапе, вдруг, это маленькое противоречие относительно конкретного $f$ распространяется на все $f$ ?

Тут дело как раз в том, что никакое конкретного $f$ мы ничего не рассматривает. Мы вначале берем произвольное $f$, для него строим множество $B$ и доказываем, что для произвольного $f$ его $B$ не лежит в его образе.

Sed в сообщении #770021 писал(а):

К примеру, возьмем “множество $B$, состоящее из элементов $A$, принадлежащих своим образам при отображении $f$”. При таком $B$ и $f$ противоречия нет (по крайне мере пока это не доказано иным путем).

А это и вовсе неважно. Если мы с помощью какого-то $B$ можем прийти к противоречию - значит исходная посылка неверна. Если мы делаем какие-то манипуляции с какими-то другими множествами, это никак не влияет на то, что $\{x\in A| x\notin f(x)\}$ не имеет прообраза.

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

Теорема. Для любого множества $A$ не существует биекции между $A$ и $2^A$.

Доказательство. Докажем, что любая функция из $A$ в $2^A$ не может являться биекцией. Возьмем произвольную $f\colon A\to 2^A$ и докажем, что $f$ - не биекция, методом от противного.
Пусть $f$ - биекция. Рассмотрим для нее множество $B = \{x\in A| x\notin f(x)\} \subset A$. Раз $f$ - биекция, существует какой-то элемент $b\in A$, соотвествующий этому подмножеству, т.е. $f(b) = B$. Возможны два варианта:

1) $b\in B$. С одной стороны, так как $B = f(b)$, это значит $b\in f(b)$. С другой стороны, поскольку $B$ содержит только элементы, удовлетворяющие условию $x\notin f(x)$, $b$ тоже должно ему удовлетворять, т.е. $b\notin f(b)$.
2) $b\notin B$, то есть $b\notin f(b)$. Поскольку $B$ содержит все элементы, удовлетворяющие условию $x\notin f(x)$, $b$ тоже должен ему принадлежать, т.е. $b\in B$.

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

[arseniiv]

Xaositect в сообщении #770035 писал(а):

$B = \{A| x\notin f(x)\} \subset A$

Опечатка.

[Xaositect]

arseniiv в сообщении #770040 писал(а):

Xaositect в сообщении #770035 писал(а):

$B = \{A| x\notin f(x)\} \subset A$

Опечатка.

Спасибо, исправил.

[Sed]

В вики доказательство такое же.

Цитата:

Если мы с помощью какого-то $B$ можем прийти к противоречию - значит исходная посылка неверна. Если мы делаем какие-то манипуляции с какими-то другими множествами, это никак не влияет на то, что $\{x \in A|x \notin f(x)\}$ не имеет прообраза.

То, что оно не имеет прообраза, как раз доказано теоремой.
А вот почему $f$ считается произвольной, когда она ограничена требованием на область определения и значения $\{x \in A|x \notin f(x)\}$ (на словах: $f$ такова, что область определения не является частью области значений), непонятно. Это все равно, чтобы потребовать, чтобы функция не была инъективной. С чего бы это, если в условии этого нет ?
Ведь если $f$ произвольна, то она может быть инъективной, сюръективной, биективной (а то и вообще не быть функцией).
По сути, вводится дополнительная посылка (ограничение на вид $f$), а именно: функция не инъективна (свойство $\varphi$). После чего строится противоречие, но какая именно посылка опровергается непонятно.
По моему теорема доказывает следующее утверждение: “если $f$ не инъективна, то она не биективна”, что как бы, и так понятно, из определения биекции, как конъюнкции инъекции и сюръекции.

[Xaositect]

Sed в сообщении #770067 писал(а):

А вот почему $f$ считается произвольной, когда она ограничена требованием на область определения и значения $\{x \in A|x \notin f(x)\}$ (на словах: $f$ такова, что область определения не является частью области значений), непонятно. Это все равно, чтобы потребовать, чтобы функция не была инъективной. С чего бы это, если в условии этого нет ?

Я вас не понимаю. Для любой функции существует множество $\{x\in A | x\notin f(x)\}$. Это множество может быть пустым, может не быть, но мы строго доказали, что оно не может иметь вид $f(b)$.

Sed в сообщении #770067 писал(а):

Ведь если $f$ произвольна, то она может быть инъективной, сюръективной, биективной .

У нас есть только одно ограничение: $f$ --- это функция из $A$ в $2^A$. Из этого мы доказываем, что она не может быть биекцией.

-- Ср окт 02, 2013 20:18:14 --

Sed в сообщении #770067 писал(а):

По моему теорема доказывает следующее утверждение: “если $f$ не инъективна, то она не биективна”, что как бы, и так понятно, из определения биекции, как конъюнкции инъекции и сюръекции.

Нет. Возьмем, например, $A = \{1\}$, $f$ -- функция, которая отображает $1$ в $\{1\}$. Эта функция инъективна, но для нее все рассуждения проходят. $B$ будет пустым множеством, и не существует элемента $b\in A$ такого, что $f(b) = B$.

-- Ср окт 02, 2013 20:19:32 --

Sed в сообщении #770067 писал(а):

По сути, вводится дополнительная посылка (ограничение на вид $f$), а именно: функция не инъективна (свойство $\varphi$). После чего строится противоречие, но какая именно посылка опровергается непонятно.

Никаких ограничений на $f$, кроме того, что $f$ --- функция из $A\to 2^A$, не предполагается. Я не понимаю, где Вы увидели инъективность.

[Sed]

Цитата:

Я вас не понимаю.

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

Цитата:

Для любой функции существует множество $\{x\in A| x\notin f(x)\}$.
Это множество может быть пустым, может не быть,
но мы строго доказали, что оно не может иметь вид $f(b)$.

Согласен, с каждым предложением.

Цитата:

У нас есть только одно ограничение: $f$ --- это функция из $A$ в $2^A$.

Согласен.

Цитата:

Из этого мы доказываем, что она не может быть биекцией.

Да, пытаемся доказать.

Цитата:

Возьмем, например, $A=\{1\}$, $f$ -- функция, которая отображает $1$ в $\{1\}$.
Эта функция инъективна, но для нее все рассуждения проходят. $B$ будет пустым множеством, и не существует элемента $b \in A$ такого, что $f(b)=B$.

Несколько замечаний.
Это доказательство (опустим подробности) построено по другому.
Во-первых, Вы доказываете небиективность $f$ на одном множестве, а именно $\{1\}$, в то время, как теорема Кантора претендует на доказательство для всех множеств.
Во-вторых, Вы предположили инъективность $f$, в то время, как в доказательстве Кантора предположена неинъективность $f$.
Тем не менее, небиективность $f$ Вами доказана (опустим подробности).

Есть еще пару замечаний не влияющих на итог "доказательства".

Цитата:

$B$ будет пустым множеством, и не существует элемента $b \in A$ такого, что $f(b)=B$.

Обращаю внимание, что Вы не требовали Канторовского: $\{x\in A| x\notin f(x)\}$, а даже говорили о инъективности. Т.е. $\{x\in A| x\in f(x)\}$, поэтому я не вижу противоречия, если есть такой элемент $b \in A$, такого что $f(b)=B$ и соответственно, $B$ не пусто.
Другое дело, что такая $f$ не биективна по другой причине. Потому что существует элемент $f(x)$, для которого не существует прообраза, отличного от $b$, т.к. подмножества всего два, а элемент только один.

Цитата:

Никаких ограничений на $f$, кроме того, что $f$ --- функция из $A \to 2^A$, не предполагается.

Согласен.

Цитата:

Я не понимаю, где Вы увидели инъективность.

Ну, как же.
Дано произвольное множество $A$ и функция $f$, про которую известно следующее.
Область определения $A$ (элементы $x \in A$).
Область значений – множество подмножеств $P(A)$ (элементы $f(x) \subseteq A$).
Так ?
Доказать, что $f$ не биективна.
Так ?
Есть, как минимум, два способа. Один Вы предложили выше: доказывать, что множество элементов меньше множества подмножеств на конкретных множествах. По сути, по индукции. Этот способ плох тем, что понятия “больше, меньше” не валидны для множеств, которые не вполне упорядочиваемы.
Можно, например, лексографически доказать для всех конечных правильных скобочных последовательностей (в рамках $\mathbb{N}$), что все соответствующие им конечные множества удовлетворяют условию не биективности $f$. Но с бесконечными последовательностями это не пройдет.

Второй способ – Канторовский.
Дано произвольное множество $A$ и функция $f$, про которую известно следующее.
Область определения $A$ (элементы $x \in A$).
Область значений – множество подмножеств $P(A)$ (элементы $f(x) \subseteq A$).

Все. Больше ничего не дано.

Таким образом, функция $f$ может быть инъективна, сюръективна, биективна.

Требуется доказать, что функция не биективна.

Доказательство сводится к следующему.
Предположим, что функция не является инъективной, т.е. область определения не является частью области значений, т.е. аргументы (элементы $x \in A$) не могут быть значениями (элементами $x \in f(x)$).
Все !
Из этого предположения $ \{x\in A| x\notin f(x)\}$ (неинъективности $f$) немедленно следует, что $f$ не биективна.
Все верно.
Но какое это имеет отношение к доказательству небиективности $f$, когда она не является не инъективной (т.е. когда условие $\varphi =\{ x \notin f(x)\}$ не выполняется ?
Мы доказали только, что если функция не инъективна (т.е. множество $B$ элементов их $A$, являющихся элементами $f(x)$) пусто, то $f$ не биективна.
Да, посылка о биеквности $f$ оказалась ложной. Но не на все “случаи жизни”, а только на случай не инъективности $f$.

[Xaositect]

Я боюсь, Вам стоит разобраться в базовых понятиях. Вы не понимаете, что такое инъективность. Ни множество $\{x\in A| x\notin f(x)\}$, ни $\{x\in A| x\in f(x)\}$ никакого отношения к инъективности не имеют.

Sed в сообщении #770122 писал(а):

Есть, как минимум, два способа. Один Вы предложили выше: доказывать, что множество элементов меньше множества подмножеств на конкретных множествах. По сути, по индукции. Этот способ плох тем, что понятия “больше, меньше” не валидны для множеств, которые не вполне упорядочиваемы.

Я ничего такого не говорил. Никакого больше-меньше.

Sed в сообщении #770122 писал(а):

Предположим, что функция не является инъективной, т.е. область определения не является частью области значений, т.е. аргументы (элементы $x \in A$) не могут быть значениями (элементами $x \in f(x)$).

Вообще говоря, для функции из $A\to 2^A$ аргументы не могут быть значениями. Аргументы тут - это элементы множества $A$, а значения - подмножества. Это совершенно разные вещи.
Кстати, в доказательстве не говорится, что ситуация $x\in f(x)$ невозможна.
А инъективность - и вовсе другая вещь. Инъективная функция - это та, которая переводит разные элемент в разные.

-- Ср окт 02, 2013 22:34:21 --

Sed в сообщении #770122 писал(а):

Мы доказали только, что если функция не инъективна (т.е. множество $B$ элементов их $A$, являющихся элементами $f(x)$) пусто, то $f$ не биективна.

Доказательство работает и в том случае, когда $B$ пусто, и в том случае, когда оно непусто.

[Sed]

Цитата:

Я боюсь, Вам стоит разобраться в базовых понятиях.

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

Цитата:

Вы не понимаете, что такое инъективность. Ни множество $\{x\in A|x \notin A\}$, ни $\{x\in A| x\in A\}$ никакого отношения к инъективности не имеют.
Аргументы тут - это элементы множества $A$, а значения - подмножества. Это совершенно разные вещи.

Например, дано множество $A=\{1\}$.
Оно содержит только один элемент $1$ и только два подмножества $\{\}, \{1\}$.
Область определения функции $f$ - это элементы множества $A$, т.е. в нашем случае единственный элемент $1$.
Область значений функции $f$ - это подмножества множества $A$, т.е. в нашем случае это $\{\}, \{1\}$.
В данном случае возможны только две функции $f_1: 1 \to \{\}$ и $f_2: 1 \to \{1\}$.
В данном случае, в области значений (подмножествах множества $A$) всегда остается элемент (подмножество $A$), который не имеет образа (элемента из области определения (т.е. элементов множества $A$)). Для $f_1$ это элемент $\{1\}$ - собственное подмножество $A$, для $f_2$ это элемент $\{\}$ - пустое множество (несобственное подмножество $A$).
Т.е. все функции не биективны. Нет среди этих всех (целых двух) функций такой, когда бы каждому элементу области определения (элементов $A$) ставился в взаимноднозначное соответствие каждый элемент множества $P(A)$ (множества подмножеств $A$).
Так ?
Таким образом, мы доказали для множества $A=\{1\}$, что биективной $f$ не существует.

Теперь посмотрим, насколько корректно говорить о функциях, для которых мы только что доказали свойство “не биективности”, как об инъективных или сюръективных функциях.
Итак (пока воспользуюсь вики).
Инъекция. .
Отображение $F$ множества $X$ в множество $Y(F: X \to Y)$ называется инъекцией (или вложением, или взаимно однозначным отображением множества $X$ в множество $Y$, если разные элементы множества $X$ переводятся в разные элементы множества $Y$.
Удовлетворяют ли $f_1,f_2$ этим требованиям ? Вполне, т.е. они инъективны.
Сюръекция.

Отображение $F: X \to \Y$ называется сюръективным (или сюръекцией, или отображением на $Y$), если каждый элемент множества $Y$ является образом хотя бы одного элемента множества $X$, то есть $\forall y \in Y \exists x \in X: y=F(x)$.
Удовлетворяют ли $f_1,f_2$ этим требованиям ? Нет, т.к. есть подмножества $A$, не имеющие прообраза - элемента $A$.

Несколько слов о некоторой неточности в моем предыдущем сообщении.
Конечно, помимо стандартного смысла инъекции и сюръекции, в соответствии с вышеприведенными определениями, я имел в виду кое-что еще.
Я (и Кантор тоже) обратил внимание на то, что $f_1,f_2$ можно классифицировать по признаку принадлежности элементов области определения (элементов $A$) к элементам области значения (подмножеств $A$). Например, для $f_1 : 1 \to \{\}$ требование Кантора $\{x \in A | x \notin f(x)\}$ выполняется, т.е. $\{1\in \{1\} \land 1 \notin \{\}\}$, а для $f_2: 1 \to \{1\}$ требование Кантора $\{x \in A | x \notin f(x)\}$ не выполняется т.е. . $\{1\in \{1\} \land 1 \notin \{1\}\}$ - ложь (противоречие).

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

Цитата:

Доказательство работает и в том случае, когда $B$ пусто, и в том случае, когда оно непусто.

Ну, вот на примере предложенного Вами одноэлементного множества $\{1\}$ и предложенной мной функции $f_2$ (она ведь допускается в число “произвольных” $f$, не так ли ?), выведите противоречие с посылкой о биективности $f_2$ методом Кантора…
Такая функция не биективна, Вы уже приводили доказательсвто в прошлом посте, но к методу доказательства Кантора оно не имеет никакого отношения.

[arseniiv]

Что там приходить к противоречию? Предположим, $f_1 = \{(1,\varnothing)\}$ — биекция… но какая же она биекция? Глазами видно же, т. к. не сюръекция. Пойдём длинным путём, хорошо. $B = \{1\}$. Если $f_1$ — биекция, у $B$ должен быть прообраз. А нету. Всё.

[Xaositect]

Sed в сообщении #770129 писал(а):

Несколько слов о некоторой неточности в моем предыдущем сообщении.
Конечно, помимо стандартного смысла инъекции и сюръекции, в соответствии с вышеприведенными определениями, я имел в виду кое-что еще.

До этой фразы все хорошо.

Sed в сообщении #770129 писал(а):

Я (и Кантор тоже) обратил внимание на то, что $f_1,f_2$ можно классифицировать по признаку принадлежности элементов области определения (элементов $A$) к элементам области значения (подмножеств $A$). Например, для $F_1 : 1 \to \{\}$ требование Кантора $\{x \in A | x \notin f(x)\}$ выполняется, т.е. $\{1\in \{1\} \land 1 \notin \{\}\}$, а для $f_2: 1 \to \{1\}$ требование Кантора $\{x \in A | x \notin f(x)\}$ не выполняется т.е. . $\{1\in \{1\} \land 1 \notin \{1\}\}$ - ложь (противоречие).

А вот и корень недопонимания. $\{x\in A | x\notin f(x)\}$ - это не требование, а множество. Символом $\{x\in Z| P(x)\}$ обозначается множество всех элементов множества $Z$, удовлетворяющих свойству $P$. Т.е. $z\in \{x\in Z| P(x)\} \Leftrightarrow z\in Z \wedge P(z)$. Для любого множеcтва $Z$ и предиката $P$ это множество существует; в этом и состоит утверждение аксиомы выделения.

Соответственно, послкдний шаг в док-ве Кантора можно записать в таком виде: Если $b\in A$, то $b\in B \Leftrightarrow b\in \{x\in A| x\notin f(x)\} \Leftrightarrow b\notin f(b) \Leftrightarrow b\notin B$. (первое по определению B, второе по определению выделенного подмножества, третье по предположению $f(b) = B$) Получаем противоречие вида $p\Leftrightarrow \neg p$

Sed в сообщении #770129 писал(а):

Ну, вот на примере предложенного Вами одноэлементного множества $\{1\}$ и предложенной мной функции $f_1$ (она ведь допускается в число “произвольных” $f$, не так ли ?), выведите противоречие с посылкой о биективности $f_1$ методом Кантора…
Такая функция не биективна, Вы уже приводили доказательсвто в прошлом посте, но к методу доказательства Кантора оно не имеет никакого отношения.

Легко. Для нашей функции $f_1\colon 1\mapsto \{\}$ множество $B = \{x\in \{1\}| x\notin f_1(x)\}$ будет равно $\{1\}$ (потому что $1\notin f(1) = \{\}$). Видно, что у него прообраза нет. А если по Кантору, то понятно, что ни для какого элемента $b\in A$ не выполняется $f_1(b) = B$, так как если $b\in B$, то $b\notin f_1(b) = B$, а если $b\notin B$, то $b\in f_1(b) = B$ (этот случай в нашей конкретной ситуации невозможен).

[provincialka]

(Оффтоп)

Немного о терминологии.

Sed в сообщении #770129 писал(а):

Для $f_1$ это элемент $\{1\}$ - собственное подмножество $A$, для $f_2$ это элемент $\{\}$ - пустое множество (несобственное подмножество $A$).

Мне кажется, что наоборот, подмножество $\{1\}$, совпадающее с $A$, - несобственное, а пустое множесто - собственное подмножество, хотя и тривиальное.

[Someone]

Sed в сообщении #770129 писал(а):

Я (и Кантор тоже) обратил внимание на то, что $f_1,f_2$ можно классифицировать по признаку принадлежности элементов области определения (элементов $A$) к элементам области значения (подмножеств $A$). Например, для $F_1 : 1 \to \{\}$ требование Кантора $\{x \in A | x \notin f(x)\}$ выполняется, т.е. $\{1\in \{1\} \land 1 \notin \{\}\}$, а для $f_2: 1 \to \{1\}$ требование Кантора $\{x \in A | x \notin f(x)\}$ не выполняется т.е. . $\{1\in \{1\} \land 1 \notin \{1\}\}$ - ложь (противоречие).

Вы неправильно понимаете, что делается в доказательстве. Там абсолютно не важно, выполняется условие $x\in f(x)$ для какого-нибудь $x$ или не выполняется. Там строится множество, которое не совпадает с $f(x)$ ни для какого $x$. Отсюда тривиально следует, что не существует биекции $A$ на $2^A$.

Вообще, теорему, о которой идёт речь, следует формулировать и доказывать в таком виде: для любого множества $A$ не существует сюръективного отображения множества $A$ на множество $2^A$. Никакой инъективности предполагать не надо.

Sed в сообщении #770129 писал(а):

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

Нисколько они не похожи, и старайтесь не менять смысла стандартных терминов. Это не приведёт ни к чему, кроме непонимания.

[Sed]

Xaositect в сообщении #770136 писал(а):

Легко. Для нашей функции $f_1\colon 1\mapsto \{\}$ множество $B = \{x\in \{1\}| x\notin f_1(x)\}$ будет равно $\{1\}$ (потому что $1\notin f(1) = \{\}$). Видно, что у него прообраза нет. А если по Кантору, то понятно, что ни для какого элемента $b\in A$ не выполняется $f_1(b) = B$, так как если $b\in B$, то $b\notin f_1(b) = B$, а если $b\notin B$, то $b\in f_1(b) = B$ (этот случай в нашей конкретной ситуации невозможен).

Я там поправил $f_1$ на $f_2$ (перепутал), но Вы уже начали отвечать, с Вашего позволения, поправлю и Ваше доказательство, чтобы Вам не переписывать (укажите на ошибки, если будут):
"Для нашей функции $f_2\colon 1\mapsto \{\}$ множество $B = \{x\in \{1\}| x\notin f_2(x)\}$ будет равно $\{\}$ (потому что $1\notin f_2(1) = \{\}$). Видно, что у него прообраза нет."
Вроде логику понял, но все-равно не могу признать этого перехода. Почему из пустоты $B$ следует, опровержение посылки о биективности $f_2$, а не посылки о том, что элементы области значения $x, x \in A$ не являются элементами элементов области определения $f_2(x), f_2(x) \subseteq A$, ведь это возможно.

Xaositect в сообщении #770136 писал(а):

А вот и корень недопонимания. $\{x\in A | x\notin f(x)\}$ - это не требование, а множество. Символом $\{x\in Z| P(x)\}$ обозначается множество всех элементов множества $Z$, удовлетворяющих свойству $P$. Т.е. $z\in \{x\in Z| P(x)\} \Leftrightarrow z\in Z \wedge P(z)$. Для любого множеcтва $Z$ и предиката $P$ это множество существует; в этом и состоит утверждение аксиомы выделения. )

Я ее так и понимаю. Такое множество существует, нет сомнений у меня.

Xaositect в сообщении #770136 писал(а):

Соответственно, послкдний шаг в док-ве Кантора можно записать в таком виде: Если $b\in A$, то $b\in B \Leftrightarrow b\in \{x\in A| x\notin f(x)\} \Leftrightarrow b\notin f(b) \Leftrightarrow b\notin B$. (первое по определению B, второе по определению выделенного подмножества, третье по предположению $f(b) = B$) Получаем противоречие вида $p\Leftrightarrow \neg p$

Да, я с этими эквивалентностями согласен. Мои сомнения касаются не этого противоречия, оно очевидно. Мои сомнения касаются выбора ложной посылки. Я не сомневаюсь в существовании $B$, я не сомневаюсь в аксиоме выделения, я не сомневаюсь в том, что пустота $B$ несовместима (противоречит) не пустоте $f_2$, в нашем примере $f_2: 1 \to \{\}$. Но я сомневаюсь, что пустота $B$ противоречит не пустоте $f_1: 1 \to \{1\}$. Т.е. из пустоты $B$ (отсутствия прообраза $f$) может следовать :
1) $f$ не содержит элемента $x \in f(x)$;
2) $f$ не биективна;
В случае, если $f=f_2$ и то и другое одновременно верно.
В случае $f_1$ верно только второе (причем это мне очевидно, т.к. можно независимо проверить тупым перебором или по индукции).
Когда $A$ бесконечно, я не могу тупым перебором (или по индукции) проверить, что следует из противоречия (пустоты $B$), что $f$ не содержит элемента $x \in f(x)$ или что $f$ не биективна или и то и другое одновременно.


-- 03.10.2013, 00:36 --

Someone в сообщении #770142 писал(а):

Вообще, теорему, о которой идёт речь, следует формулировать и доказывать в таком виде: для любого множества $A$ не существует сюръективного отображения множества $A$ на множество $2^A$. Никакой инъективности предполагать не надо.

Кажется это понятней.
Доказывая пустоту$B$, т.е. отсутствие элементов $x\in f(x)$, мы доказываем невозможность "сюрьекции" (простите мой вспомогательный нестандартный термин), из которой следует отсутствие сюръекции (стандартный термин), а уже из этого следует отсутствие биекции, т.к. сюръекция является ее обязательным условием. Ну, наверно, как-то так.

[arseniiv]

В общем случае $B$ не обязательно пустое. Пустота $B$ никак в доказательстве не упоминается.