Прямые доказательства теоремы Кантора

[Odysseus]

Хотел бы высказать некоторые соображения по вопросам, которые часто поднимались как на этом форуме, так и в принципе являются довольно популярными:
1) Можно ли доказать теорему Кантора (мощность любого множества меньше, чем мощность множества его подмножеств) только от противного?
2) (Когда признается, что есть и прямой метод) Являются ли прямые способы этого доказательства более простыми и логичными?

Ответ на второй вопрос может быть субъективным, но на этом форуме было так много тем с вопросами о данной теореме, и значение этой теоремы в математике настолько велико, что, как минимум, стоит рассмотреть и альтернативные доказательства.

Наиболее популярное доказательство теоремы Кантора использует предположение о наличии биекции (или сюрьекции, чего в данном случае достаточно) $A\to 2^A$, из которого затем выводится противоречие. Практически во всех русскоязычных учебниках которые я видел, а также в русскоязычной и англоязычной Википедии, оно звучит примерно следующим образом:

Теорема Кантора. Для произвольного множества $A$ и множества всех его подмножеств $2^A$ верно $\lvert A\rvert<\lvert 2^A\rvert$

Стандартное доказательство от противного. Во-первых, существует инъекция, сопоставляющая каждому элементу $x \in A$ одноэлементное подмножество $\{x\}\in 2^A$, значит $\lvert A\rvert\leqslant\lvert 2^A\rvert$

Теперь рассмотрим отображение $f:A \to 2^A$ и построим множество $B = \{x \in A : x \notin f(x)\}$, состоящее из всех элементов $A$, не принадлежащих своим образам при отображении $f$.
Предположим, что $f$ это сюръекция. Тогда существует $y\in A$ такой, что $f(y)=B$.
Далее в обоих случаях возникают противоречия:
- Если $y\in B$, то поскольку $f(y)=B$, должно быть $y\in f(y)$, но тогда по определению $B$, $y\notin B$
- Если $y\notin B$, то поскольку $f(y)=B$, должно быть $y\notin f(y)$, но тогда по определению $B$, $y\in B$
Следовательно, предположение о наличии сюръекции ложно, и значит $\lvert A\rvert<\lvert 2^A\rvert$

С этим доказательством, как мне кажется, есть ряд проблем:
1. В нем используется доказательство от противного без которого, на самом деле, можно обойтись (что часто предпочтительнее). Это уже не раз обсуждалось на этом форуме, последний раз в Доказательство теоремы о мощности множества подмножеств.
2. Конструкция "если $y\in B$, то ... $y\notin B$, а если $y\notin B$, то ... $y\in B$", хотя и достаточная для доказательства, не кажется слишком прозрачной. Возникает аналогия (пусть и неверная, но психологически близкая) с брадобреем, который бреет всех кроме самого себя, с парадоксом лжеца и т.д. Как минимум, не очень хорошо понимаешь "что здесь происходит". Теорема доказалась и ложки нашлись, но осадок остался.
3. Диагональный метод Кантора, который он придумал впервые для доказательства именно этой теоремы, при таком методе доказательства довольно завуалирован. Для сравнения, при доказательстве того, что $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$ он используется более явно: для любого отображения $\mathbb{N}\to \mathbb{R}$ по диагонали строится вещественное число, которое не совпадает ни с каким образом при данном отображении. Иногда при этом тоже говорят "предположим, что существует сюръекция", но в данном случае эти слова точно лишние.

Главная проблема здесь в конструкции противоречия из п.2. Если использовать ее, то приходится доказывать от противного, поскольку сам аргумент этой конструкции заключается в сведении к противоречию. А чтобы доказывать не от противного, то конструкция главного аргумента должна быть другой.

Есть другой метод доказательства, который я встречал только в двух источниках: оригинальное доказательство Кантора в его "Трудах по теории множеств" (статья "Об одном элементарном вопросе учения о многообразиях", стр. 170-171) и оно же, но в более современных терминах, у Александрова во "Введении в теорию множеств и общую топологию" (глава 1, § 6, теоремы 15 и 16). В них вместо множества всех подмножеств $2^A$ рассматривается множество всех отображений $A\to \{0, 1\}$. Конечно, при этом доказывается то же самое, поскольку мощность последнего равна мощности $2^A$, но ход доказательства несколько другой. При этом намного более явно используется диагональный метод Кантора, и все доказательство практически идентично доказательству того, что $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$ (если ограничиться вещественными числами на интервале $[0, 1]$ записанными в двоичной системе счисления, далее я эту оговорку уже не повторяю). Единственная разница будет в том, что множество $A$ может быть несчетным, но это в сути доказательства ничего не меняет.

Подозреваю, что составителю большинства учебников этот метод доказательства теоремы Кантора не нравится потому, что формально он более длинный. Однако логически и "визуально" он настолько же простой как и доказательство $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$ с которым, вроде, ни у кого проблем нет.

ОДНАКО, и стандартное доказательство можно немного модифицировать так, чтобы 1) не было необходимости доказывать от противного и 2) доказательство стало несколько проще и яснее, и не использовало рефлексивных конструкций "если $y\in B$, то ... $y\notin B$, а если $y\notin B$, то ... $y\in B$". Эта модификация элементарна, поэтому я уверен, что где-то она приводится. Но лично я ее не встречал, поэтому опишу ее ниже (как прямое доказательство под номером 1, поскольку оно по конструкции ближе к стандартному методу). После этого приведу также оригинальный вариант доказательства Кантора (под номером 2) и в нем буду приводить параллели с прямым доказательством #1 и с доказательством $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$, которые мне кажется тоже будут полезны.

Прямое доказательство #1 (модификация стандартного доказательства). Первая часть такая же, как и в доказательстве выше от противного. Существует инъекция сопоставляющая каждому элементу $x \in A$ одноэлементное подмножество $\{x\}\in 2^A$, значит $\lvert A\rvert\leqslant\lvert 2^A\rvert$

Далее, тоже как и раньше, рассмотрим отображение $f:A \to 2^A$ и множество $B = \{x \in A : x \notin f(x)\}$.
Но теперь не будем предполагать, что $f$ это сюръекция, т.е. не будем предполагать, что существует $y\in A$ такой, что $f(y)=B$
Вместо этого сразу напрямую покажем, что не существует $y \in A$ такого, что $f(y)=B$.
- Если $y\in B$, то по определению $B$, $y \notin f(y)$, значит $f(y)\neq B$.
- Если $y\notin B$, то по определению $B$, $y\in f(y)$, и значит тоже $f(y)\neq B$.
Значит $f$ это не сюръекция. С учетом произвольности $f$, сюръекции между $X$ и $2^A$ не существует вообще, значит $\lvert A\rvert<\lvert 2^A\rvert$

---

Также приведу терминологию и визуальный прием, которые помогают мне представить эти импликации на таком уровне, что они становятся еще более естественными и интуитивными. Возможно, кто-то еще найдет эти образы полезными.
- Подмножество $B\in 2^A$ назовем "своим" для элемента $y\in A$, если $y$ принадлежит этому подмножеству. Элемент назовем "верным" (относительно отображения $f$), если при отображении $f:A \to 2^A$ он переходит в свое подмножество, т.е. для верных элементов $y \in f(y)$.
- Аналогично, подмножество назовем "чужим" для элемента $y$, если $y$ не принадлежит этому подмножеству. Элемент назовем "неверным", если при отображении $f$ он переходит в чужое подмножество, т.е. для неверных элементов $y \notin f(y)$.
- Очевидно, что любой элемент или верный, или неверный.
- Теперь можно просто описать словами почему в $B = \{x \in A : x \notin f(x)\}$ не переходит ни один из элементов $A$. Подмножество $B$ состоит только из неверных элементов, значит туда не могут переходить верные элементы (поскольку не встретят там себя). И при этом в $B$ все неверные элементы, значит туда не могут переходить неверные элементы (поскольку встретят там себя).
- Я при этом также представляю верные элементы зеленым цветом, а неверные - красным. Зеленые могут переходить только в те подмножества, где есть хотя бы один зеленый элемент. А красные не могут переходят в подмножества где есть все красные элементы. А значит в подмножество $B$ где есть все красные и ни одного зеленого - никто переходить не может.
- Еще может быть, когда у данного $f$ красных элементов нет вообще, например когда это описанная выше инъекция из $A$ в одноэлементные подмножества $2^A$. Тогда $B$ это пустое множество и все зеленые элементы в него тоже не могут переходить.
- Кодирование разных элементов цветами, диаграммами и формами мне было полезно и в других ситуациях. ИМХО это хорошо стимулирует ассоциации и привыкание к новым понятиям.

Другой визуальный прием напрямую связан со вторым методом прямого доказательства описанным ниже. В нем элементы уже не разбиваются на "верные" и "неверные", и даже не разбиваются на группы $y\in B$ или $y\notin B$, а просто для каждого элемента $A$ по отдельности доказывается, что он не может перейти в $B$.

----

Прямое доказательство #2 (более явное использование диагонального метода Кантора).
Это доказательство несколько длиннее, но построение здесь "более конструктивное" и практически такое же, как и при стандартном доказательстве диагональным методом $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$ Поэтому идеологически оно не менее простое, чем первое.

Сначала напомним известное доказательство того, что мощность $2^A$ равна мощности множества отображений $A\to \{0, 1\}$. Здесь все очевидно: каждому отображению $\lambda :A \to \{0, 1\}$ соответствует разбиение $A$ на два непересекающиеся подмножества: $A_1 = \{x \in A : \lambda (x)=1\}$ и $A_0 = \{x \in A : \lambda (x)=0\}$. Рассматривая $\lambda$ как характеристическую функцию подмножества $A_1$, выделяющую его из $A$, можно сказать, что каждому $\lambda$ соответствует какое-то подмножество $A$ и наоборот.

Значит далее можно сравнивать $\lvert A\rvert$ не с $\lvert 2^A\rvert$, а с мощностью множества характеристических функций на $A$, которое будем далее обозначать как $\{0, 1\}^A$. Но для того, чтобы проводить параллели с предыдущим прямым доказательством полезно все время держать в голове как каждая характеристическая функция связана с ее подмножеством $A$, т.е. мы не отказываемся от картинок подмножеств, а просто переводим эти картинки "на алгебраический язык". (Я буду ниже приводить мелким шрифтом такие параллели, а также параллели с доказательством $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$)

Через $f$ будем обозначать $f:A \to \{0, 1\}^A$, через $f_x$ - конкретную функцию из $A\to \{0, 1\}$, которая в силу этого соответствия отвечает элементу $x$, а через $f_x(y)$ - значение этой функции на элементе $y$. Это главные понятия, которые нужно понять в данном доказательстве, после этого все строится уже автоматически.
- При доказательстве $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$, аналогом $f$ будет конкретная инъекция $\mathbb{N}\to \mathbb{R}$, аналогом $f_x$ - вещественное число в которое переходит натуральное число $x$, а $f_x(y)$ - разряд этого числа под номером $y$.
- В случае подмножеств, аналогом $f$ будут отображение $A \to 2^A$, аналогом $f_x$ - подмножество, в которое переходит элемент $x$, а $f_x(y)$ - характеристикой того, входит ли элемент $y$ в это подмножество: если $f_x(y)=1$, то входит, а если $f_x(y)=0$, то не входит.

Наличие инъективности $A\to \{0, 1\}^A$ очевидно как и в предыдущих методах доказательства. Для каждого элемента $x \inA$ построим $g_x:A \to \{0, 1\}$ таким образом, что $g_x(x)=1$ и $g_x(y)=0$ $\forall y\ne x$.
- В случае подмножеств, аналогом будет сопоставление каждому элементу $x \in A$ одноэлементного подмножества $\{x\}\in 2^A$.

Теперь, как и в первом прямом доказательстве, рассмотрим произвольное отображение $f:A \to \{0, 1\}^A$ и докажем, что оно не может быть сюръективным. Т.е. докажем, что существует функция $\lambda \in \{0, 1\}^A$, которая не равна ни одному $f_x$.
- При доказательстве $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$, аналогом будет построение вещественного числа, в которое не переходит ни одно натуральное.
- В случае подмножеств, аналогом будет построение подмножества, в которое не переходит ни один элемент $x$.

Построим такую функцию $\lambda \in \{0, 1\}^A$ по следующему правило: $\lambda(x) = 1-f_x(x)$, т.е. если $f_x(x)=1$, то $\lambda(x)=0$ и если $f_x(x)=0$, то $\lambda(x)=1$
- При доказательстве $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$, аналогом будет построение по диагонали вещественного числа, которое в каждом разряде $x$ отличается от образа соответствующего натурального числа $x$ в этом разряде.
- В случае подмножеств, аналогом будет построения подмножества $B = \{x \in A : x \notin f(x)\}$, поскольку те элементы, которые принадлежат своему образу мы в него не включаем (меняем в них $1$ на $0$), а те, которые не принадлежат своему образу - включаем (меняем в них $0$ на $1$).

И теперь, даже проще чем в первом прямом доказательстве, видно, что $\forall x$ $\lambda \neq f_x$, поскольку их значения отличаются на элементе $x$: $\lambda(x) \neq f_x(x)$.
- При доказательстве $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$, будет полный аналог.
- В случае подмножеств, аналогом будет доказательство того, что в $B$ не переходит ни один элемент $A$ поскольку все элементы там "неверные".

Получилось в итоге довольно длинно, но, мне кажется, достаточно прозрачно и может заслуживать внимания с методической точки зрения.

Выводы (все ИМХО)
- Наиболее популярное доказательство теоремы Кантора использует метод доказательства от противного, без которого можно обойтись за счет небольшой модификации этого доказательства. Кроме того, прямое доказательство будет использовать более ясную конструкцию для главного аргумента, чем конструкция из противоречий в стандартном доказательстве от противного.
-- Для дополнительных аналогий кому-то может быть также полезна предложенная выше терминология "своих/чужих" множеств и "верных/неверных" элементов вместе с их цветовой маркировкой, но это уже дело вкуса.
- Есть еще одно прямое доказательство (оригинальное доказательство Кантора), которое более явно использует диагональный метод. По свой логике, оно очень близко как к доказательству того, что $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$, так и к прямому доказательству полученному модификацией стандартного доказательства от противного.
- Оба прямых доказательства, как минимум, заслуживают упоминаний как альтернативные методы (намного большего, чем у них есть сейчас). Возможно даже, одно из них должно рассматриваться как основной метод доказательства по сравнению с текущим стандартным методом. Для тех, кто будет предпочитать более короткий способ - можно использовать прямое доказательство #1, близкое к стандартному. Для тех, кто будет предпочитать лучше понять логику диагональному метода и связи этого доказательства с $\lvert \mathbb{N}\rvert<\lvert \mathbb{R}\rvert$ - можно использовать прямое доказательство #2.

[Padawan]

Odysseus в сообщении #1499455 писал(а):

Построим такую функцию $\lambda \in \{0, 1\}^A$ по следующему правило: $\lambda(x) = 1-f_x(x)$, т.е. если $f_x(x)=1$, то $\lambda(x)=0$ и если $f_x(x)=0$, то $\lambda(x)=1$.

Я именно так и доказываю теорему Кантора. Только слова "от противного" все-таки использую, хотя это явно лишнее. Мне кажется это связано с тем, что понятие биекции оно более фундаментальное. И психологически проще предположить, что есть биекция, и потом уже думать, что из этого можно получить.

[Odysseus]

Padawan в сообщении #1499460 писал(а):

Только слова "от противного" все-таки использую

И не только вы :) У Александрова в этом же методе доказательстве тоже в начале присутствуют слова "предположим, что биекция существует" хотя они там не нужны. Добавлять их или нет в таких случаях это не очень принципиально и, скорее, дело вкуса. Более того, не так принципиально даже является ли какое-то доказательство по своей сути доказательством от противного или нет. Важнее насколько естественные и понятные структуры, логические переходы и заключения в нем используются. И главная проблема стандартного доказательства теоремы Кантора в том, что переходы и заключения в нем ИМХО не вполне естественные и более сложные, чем нужно.

Т.е. если какое-то доказательство более естественное и понятное, когда доказывается от противного - значит пусть так и доказывается. Но при равных условиях, и тем более когда прямое доказательство более естественное, как в данном случае с теоремой Кантора, лучше выбирать прямое. Или, как минимум, знакомить и с прямым доказательством, поскольку для многих оно может быть понятнее.

Кстати, в приведенном выше прямом доказательстве #1

Odysseus в сообщении #1499455 писал(а):

Далее, тоже как и раньше, рассмотрим отображение $f:A \to 2^A$ и множество $B = \{x \in A : x \notin f(x)\}$.
Но теперь не будем предполагать, что $f$ это сюръекция, т.е. не будем предполагать, что существует $y\in A$ такой, что $f(y)=B$
Вместо этого сразу напрямую покажем, что не существует $y \in A$ такого, что $f(y)=B$.
- Если $y\in B$, то по определению $B$, $y \notin f(y)$, значит $f(y)\neq B$.
- Если $y\notin B$, то по определению $B$, $y\in f(y)$, и значит тоже $f(y)\neq B$.

главные логические переходы можно еще упростить. В каждом из них вместо двух импликаций $\Rightarrow$ достаточно одной:
- Если $y \notin f(y)$, то $f(y)\neq B$.
- Если $y\in f(y)$, то тоже $f(y)\neq B$.

Первая импликация была нужна только для того, чтобы из дихотомии $(y\in B) \vee (y\notin B)$ перейти к $(y\in f(y)) \vee (y\notin f(y))$. Но последняя очевидна и сама по себе, т.е. можно начинать сразу с нее. Заодно так будет лучше соответствовать последующим аналогиям с "верными" и "неверными" элементами. Нам важны именно свойства $y\in f(y)$ и $y\notin f(y)$ элементов $A$, а не принадлежность их к множеству $B$.

В стандартном доказательстве тоже можно начинать с дихотомии $(y\in f(y)) \vee (y\notin f(y))$, но все равно придется делать два импликации $\Rightarrow$ в каждой из цепочки переходов, чтобы прийти к противоречию (в данном случае к $(y\in f(y)) \wedge (y\notin f(y))$). Это еще один довод в пользу прямого доказательства теоремы Кантора #1 по сравнению со стандартным доказательством от противного.