"Диагональное" доказательство теоремы Кантора

[mihaild]

Vladimir Pliassov, а вы попробуйте переписать это доказательство. У нас есть выше определенная биекция $g: \mathcal P(\mathbb N) \to \{0, 1\}^\mathbb N$, везде вместо $\mathcal P(\mathbb N)$ подставьте $\{0, 1\}^\mathbb N$, вместо $f(x)$ - $g(f(x))$, распишите, что значит $x \notin g(f(x))$ и т.д.

[Someone]

xagiwo в сообщении #1527120 писал(а):

Someone
Так доказать $\lnot \varphi$ можно только если предположить $\varphi$ и вывести из этого противоречие

Извините, это какая-то ерунда (не обижайтесь). Особенно если учесть, что в классической логике любая формула может быть записана в виде $\neg\varphi$.

xagiwo в сообщении #1527120 писал(а):

можно сначала диагональным методом доказать $\forall x: \mathbb{N} \to \mathcal P(\mathbb N)\, \lnot (x \text{ — биекция})$, но после этого всё равно придётся предполагать счётность и выводить противоречие, чтобы вывести $\lnot \exists x: \mathbb{N} \to \mathcal P(\mathbb N)\, (x \text{ — биекция})$

Зачем делать такое предположение, если мы уже доказали, что никакое отображение $\mathbb N\to 2^{\mathbb N}$ не является биекцией?

У Вас неправильное представление о доказательствах "от противного". Если следовать вашей логике, то все доказательства являются доказательствами "от противного".
На самом деле доказательство "от противного" имеет место только в том случае, когда сделанное предположение необходимо для построения противоречия. Например, в доказательстве иррациональности числа $\sqrt{2}$ делается противоположное предположение, что это число рационально, то есть, может быть записано в виде дроби $\sqrt{2}=\frac mn$, где $m$ и $n$ — натуральные числа; если дробь сократимая, её сокращаем на наибольший общий делитель $m$ и $n$, чтобы дробь стала несократимой, после чего выясняется, что полученная после сокращения дробь сократима на $2$ (в этом и состоит противоречие). Здесь предположение о рациональности $\sqrt{2}$ существенно используется в построении противоречия.
В доказательстве теоремы Кантора предположение о равномощности множеств $X$ и $2^X$ никак не используется. Мы сначала замечаем, что $\lvert X\rvert\leqslant\lvert 2^X\rvert$, так как существует очевидная инъекция $X\to 2^X$, а затем показываем, что никакое отображение $f\colon X\to 2^X$ не является сюръекцией (и тем более не является биекцией), поэтому $\lvert X\rvert<\lvert 2^X\rvert$. Никаких предположений об отображении $f$ делать не нужно, рассуждение работает для любого отображения. В частности, не требуется предполагать, что $f$ — биекция. Поэтому доказательства "от противного" здесь нет.

[Vladimir Pliassov]

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

а вы попробуйте переписать это доказательство. У нас есть выше определенная биекция $g: \mathcal P(\mathbb N) \to \{0, 1\}^\mathbb N$, везде вместо $\mathcal P(\mathbb N)$ подставьте $\{0, 1\}^\mathbb N$, вместо $f(x)$ - $g(f(x))$, распишите, что значит $x \notin g(f(x))$ и т.д.

Я сейчас этим и занимаюсь, но пока стараюсь получше его изучить. По-моему, пункт (3) можно убрать, потому что, исходя из пунктов (1), (2), $y$ не может принадлежать $Y$:

Цитата:

$\eqno (0.1)$ Пусть $X$ --- произвольное множество, $\mathcal{P}(X)$ --- множество всех подмножеств $X$.
$\eqno (0.2)$ Пусть $f$ --- биекция $X$ на $\mathcal{P}(X)$. Требуется доказать или опровергнуть её существование.
$\eqno (1)$ Пусть $Y = \{ x \in X : x \not\in f(x) \} $.
$\eqno (2)$ $f$ --- биекция, потому $Y = f(y)$ для некоторого $y \in X$.
$\eqno (3)$ Если $y \in Y$, то $y \in f(y)$ и $y \not\in Y$.
$\eqno (4)$ Если $y \not\in Y$, то $y \not\in f(y)$ и $y \in Y$.
$\eqno (5)$ Противоречие --- $f$ не существует.

Хотя, конечно, если бы не это, с третьим пунктом было бы красивее.

[xagiwo]

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

Извините, это какая-то ерунда (не обижайтесь). Особенно если учесть, что в классической логике любая формула может быть записана в виде $\neg\varphi$.

Я про то, что единственная логическая аксиома (в какой-то акисоматике), позволяющая доказать $\lnot \varphi$ это $((A \rightarrow B) \land (A \to \lnot B)) \to \lnot A$. А $\varphi \rightarrow \lnot \lnot \varphi$ тоже доказывается от противного. И $\forall x \, \lnot \varphi \leftrightarrow \lnot \exists x \,\varphi$ тоже, как и $\forall x\, \lnot(x \text{— биекция}) \leftrightarrow \lnot \exists x\, (x \text{— биекция})$ , а утверждение о несчётности множества — именно последнее утверждение. Но если такие тавтологии не считать "противными", то не от противного.

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

Например, в доказательстве иррациональности числа $\sqrt{2}$

Здесь тоже можно сказать, что для любого рационального числа $p\; p \neq \sqrt{2}$ и док-во этого утверждения не использует предположение о рациональности $\sqrt{2}$, "рассуждение работает для любого рационального числа". Конечно, $p \neq \sqrt{2}$ само доказывается от противного (хотя предположение другое), но и в теореме Кантора тоже "$f$ — не биекция, ибо иначе она содержала бы инвертированную последовательность на диагонали", что есть рассуждение от противного

-- 26.07.2021, 06:49 --

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

Если следовать вашей логике, то все доказательства являются доказательствами "от противного".

Любые доказательства отрицания некоторого утверждения — да (кроме аксиом вроде $\lnot \exists x\; S(x) = 0$)

[Vladimir Pliassov]

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

Множеству $Y \subseteq \mathbb N$ сопоставляется последовательность $y$, определенная как

$$y(n) = \begin{cases} 1,\ n \in Y\\ 0,\ n \notin Y \end{cases}$$

то есть последовательность $y$ может сопоставляться одному из двух множеств: $Y$ и $\overline Y$, где $\overline Y=\mathbb N\setminus Y$. Но мы выбираем только одно из этих двух сопоставлений, в данном случае, сопоставление множеству $Y$.

При этом $Y$ состоит из всех тех значений $n$ (из всех тех аргументов), от которых функция $y$ равна $1$. В частности, если при всех значениях $n$ $y(n)=1$, то $Y=\mathbb N$, а если при всех значениях $n$ $y(n)=0$, то $Y=\varnothing$.

(Оффтоп)

Такой синтаксический вопрос: в предложении "при всех значениях $n$ $y(n)=1$" хорошо было бы сделать как-то, чтобы $n$ и $y(n)=1$ не сливались в один массив обозначений. Я обычно стараюсь в таких случаях поставить между выражениями, которые хотелось бы отделить друг от друга, какое-нибудь слово, но не всегда это хорошо получается, например, можно было бы написать: "при всех значениях $n$ функция $y(n)=1$", но тогда получается смешение слов и знаков, так что пришлось бы написать скорее "при всех значениях $n$ функция $y(n)$ равна $1$", а хотелось бы написать формулой.

По-моему, кто-то в таких случаях употребляет двоеточие: "при всех значениях $n\colon y(n)=1$", но не знаю, хорошо ли это.

[mihaild]

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

то есть последовательность $y$ сопоставляется сразу двум множествам: $Y$ и $\overline Y$, где $\overline Y=\mathbb N\setminus Y$

Нет, одному. То, что очень похожим образом можно написать другую биекцию, к делу не относится.

[Vladimir Pliassov]

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

Нет, одному.

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

[epros]

xagiwo в сообщении #1527120 писал(а):

Так доказать $\lnot \varphi$ можно только если предположить $\varphi$ и вывести из этого противоречие

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

[Vladimir Pliassov]

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

Лучше так:
Определим отображение $g: \{0, 1\}^\mathbb N \to \mathcal P(\mathbb N)$: $g(f) = A$, где $a \in A \leftrightarrow f(a) = 1$. Докажем его инъективность и сюръективность.
Инъективность: если $g(f_1) = g(f_2)$ распишем определение и получим $f_1 = f_2$.
Сюръективность: пусть дано некоторое множество $A$, определим $f$ понятно как и получим что $g(f) = A$.
Следовательно, $g$ - биекция.

Пусть дана функция $f: \mathbb N \to \{0, 1\}$ и при этом для $A\subseteq \mathbb N$ дано правило:

$$ \begin{cases} f(a) = 1\to a\in A\\ f(a) = 0\to a\notin A \end{cases}. \eqno {(1)}$$

Правило (1) является определением функции $f$. Оно равносильно двусторонней импликации $a \in A \leftrightarrow f(a) = 1$ (которая, таким образом, является равносильным определением функции $f$).

В самом деле, пусть $a\in A$, тогда $f(a) \ne 0$, поскольку $f(a) = 0\to a\notin A$, то есть $f(a)=1$.

Определим отображение $g: \{0, 1\}^\mathbb N \to \mathcal P(\mathbb N)$: $g(f) = A$, где $f\colon a \in A \leftrightarrow f(a) = 1$. Докажем его инъективность и сюръективность.

Инъективность: пусть $g(f_1) = g(f_2)=A$, тогда $f_1(a)=f_2(a)=1, \; a\in A$, таким образом, $f_1 = f_2$.

Сюръективность: пусть дано некоторое множество $A$ и функция $f\colon a \in A \leftrightarrow f(a) = 1$, тогда по определению $g$ имеем $g(f) = A$.

Следовательно, $g$ - биекция.

[Vladimir Pliassov]

Снова к доказательству

Nemiroff в сообщении #1526677 писал(а):

Цитата:

$\eqno (0.1)$ Пусть $X$ --- произвольное множество, $\mathcal{P}(X)$ --- множество всех подмножеств $X$.
$\eqno (0.2)$ Пусть $f$ --- биекция $X$ на $\mathcal{P}(X)$. Требуется доказать или опровергнуть её существование.
$\eqno (1)$ Пусть $Y = \{ x \in X : x \not\in f(x) \} $.
$\eqno (2)$ $f$ --- биекция, потому $Y = f(y)$ для некоторого $y \in X$.
$\eqno (3)$ Если $y \in Y$, то $y \in f(y)$ и $y \not\in Y$.
$\eqno (4)$ Если $y \not\in Y$, то $y \not\in f(y)$ и $y \in Y$.
$\eqno (5)$ Противоречие --- $f$ не существует.

[Кстати, доказательство существования множества $Y$: поскольку $f$ -- биекция, необходимо существование некоторого элемента $z$, отображающегося в подмножество $\varnothing$, а оно не имеет ни одного элемента, значит, элемент $z$ отображается в множество, которому не принадлежит.

Кроме того, как я уже писал, по-моему, пункт (3) можно убрать, потому что, исходя из пункта (1) $y$ не может принадлежать $Y$.]

Это доказательство от противного (предполагается, что биекция есть, и это приводит к противоречию)?

Если да, то, может быть, поэтому оно не очень очевидное (так же как доказательство об иррациональности числа $\sqrt {2}$, хотя там вообще трудно говорить об очевидности)?

Мне кажется, я нашел более очевидное (и простое) доказательство несчетности всех подмножеств множества $\mathbb N$ (но, может быть, мне опять так только кажется?).

Пусть дано $\mathbb N$ -- множество натуральных чисел и $\mathcal{P}(\mathbb N)$ -- множество всех подмножеств $\mathbb N$. Доказать, что не существует биекции $f\colon \mathbb N\leftrightarrow \mathcal{P}(\mathbb N).$

$\rhd$ Пусть $f$ -- инъекция из $\mathbb N$ в $\mathcal{P}(\mathbb N)\colon f(a)=\{a\}, \; a=1, 2, \ldots\; .$ Это возможно, так как, очевидно, существует биекция между $\mathbb N$ и всеми одноэлементными подмножествами $\mathbb N\colon \{1\}, \{2\}, \ldots\; .$ При этом не остается свободных элементов $\mathbb N$, которые могли бы быть поставлены в соответствие остальным подмножествам $\mathbb N$, таким образом, $f$ не является сюръекцией и потому не является биекцией. $\lhd$

[svv]

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

Пусть дано $\mathbb N$ -- множество натуральных чисел и $\mathcal{P}(\mathbb N)$ -- множество всех подмножеств $\mathbb N$. Доказать, что не существует биекции $f\colon \mathbb N\leftrightarrow \mathcal{P}(\mathbb N).$

$\rhd$ Пусть $f$ -- инъекция из $\mathbb N$ в $\mathcal{P}(\mathbb N)\colon f(a)=\{a\}, \; a=1, 2, \ldots\; .$ Это возможно, так как, очевидно, существует биекция между $\mathbb N$ и всеми одноэлементными подмножествами $\mathbb N\colon \{1\}, \{2\}, \ldots\; .$ При этом не остается свободных элементов $\mathbb N$, которые могли бы быть поставлены в соответствие остальным подмножествам $\mathbb N$, таким образом, $f$ не является сюръекцией и потому не является биекцией. $\lhd$

Рассуждая аналогично, можно прийти к выводу, что не существует биекции между множеством чётных натуральных чисел и $\mathbb N$. Но она существует.

Вы показали, что сюръекцией не является Ваша $f$, но не любая инъекция из $\mathbb N$ в $\mathcal{P}(\mathbb N)$.

[Vladimir Pliassov]

Я могу ошибаться, но, по-моему, $ f(a)=\{a\}, \; a=1, 2, \ldots$ является биекцией:

инъекция: $f(a)=f(b)\to a=b$, сюръекция: пусть дано некоторое одноэлементное подмножество $\{a\}$, тогда для него имеется натуральное число $a$.

Другое дело, что несмотря на то, что имеется биекция между $\mathbb N$ и некоторой совокупностью $B$ его подмножеств, которая не равна всему $\mathcal{P}(\mathbb N),$ каким-то образом можно предположить, что при этом имеется также биекция между некоторыми элементами $\mathbb N$ и подмножествами совокупности $\mathcal{P}(\mathbb N)\setminus B,$ но каким образом можно это предположить, когда все элементы $\mathbb N$ уже поставлены в соответствие элементам $B$, особенно, учитывая, что $B=\{ \{1\}, \{2\}, \ldots \}\; ?$

Мне кажется, что нельзя предположить даже, что имеется хотя бы один элемент $\mathbb N$, остающийся свободным после биекции $ f(a)=\{a\}, \; a=1, 2, \ldots\; ,$ чтобы его можно было поставить в соответствие какому-нибудь не одноэлементному подмножеству $\mathbb N$.

[mihaild]

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

Кстати, доказательство существования множества $Y$: поскольку $f$ -- биекция, необходимо существование некоторого элемента $z$, отображающегося в подмножество $\varnothing$, а оно не имеет ни одного элемента, значит, элемент $z$ отображается в множество, которому не принадлежит

Это доказательство непустоты $Y$, а не его существования. Но его непустота нам неважна.
Существование же $Y$ следует из аксиомы выделения: мы выделяем из множества $X$ элементы, удовлетворяющие некоторому условию.

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

но каким образом можно это предположить, когда все элементы $\mathbb N$ уже поставлены в соответствие элементам $B$,

Всё то же самое, что и с биекцией между четными и всеми натуральными числами.
Если $X$ конечно, то существование инъекции из $X$ в $Y$, не являющейся биекцией, означает что мощность $Y$ больше мощности $X$. Для бесконечных множеств это очень сильно неверно.

Еще вам может оказаться полезным наблюдение, что ваше рассуждение так же работает для множества всех конечных подмножеств $\mathbb N$, которое тем не менее счетно.

[Vladimir Pliassov]

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

Всё то же самое, что и с биекцией между четными и всеми натуральными числами.

Биекция между четными и всеми натуральными числами существует.

Согласны ли Вы, существует биекция $ f(a)=\{a\}, \; a=1, 2, \ldots\; ?$

Если да, то какое натуральное число можно поставить в соответствие какому-нибудь не одноэлементному подмножеству $\mathbb N$ после того, как биекция $ f(a)=\{a\}, \; a=1, 2, \ldots$ уже задана?

[mihaild]

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

какое натуральное число можно поставить в соответствие какому-нибудь не одноэлементному подмножеству $\mathbb N$ после того, как биекция $ f(a)=\{a\}, \; a=1, 2, \ldots$ уже задана?

А что значит "после того, как биекция уже задана"? Задали какую-то функцию, но от нас же никто не требует её расширить.
Аналогично: существует биекция между четными натуральными числами и четными натуральными числами, $f(a) = a$. Какое четное число можно поставить в соответствие какому-нибудь нечетному числу после того, как биекция $f(a) = a$ уже задана?