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

[xagiwo]

(Оффтоп)

Понял.

[Vladimir Pliassov]

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

Что такое "общее обозначение для каждой последовательности" - непонятно. Есть множество последовательностей, есть его элементы.
Можно, конечно, построить функцию из $\mathbb N$ в $\mathcal P(\{0, 1\}^\mathbb N)$, такое что $f(1) = \{0, 1\}^\mathbb N$, но зачем?

Я там, в своем предыдущем сообщении, переправил "отображение $f$" на "соответствие $f$".

Отображение это соответствие, при котором одному элементу-прообразу соответствует не более одного элемента-образа. А в рассматриваемом случае (как я на него смотрю) каждому элементу $\mathbb N$ соответствует более, чем одна последовательность, то есть это соответствие, но не отображение.

Поэтому я говорю об общем обозначении $S$ для каждой последовательности.

Когда переправил, получилось: "... то есть этот выбор (между нулем и единицей) для числа $1$ имеет место для каждой последовательности, таким образом, имеется соответствие $f$, заданное на множестве $\mathbb N$, содержащем $1$, и $f(1) = S$, где $S$ это общее обозначение для каждой из последовательностей."

Но хотя мне кажется, что и так можно, потому что это соответствие не только одного элемента из $\mathbb N$ всем последовательностям, но и соответствие одного элемента из $\mathbb N$ каждой из последовательностей, наверное, лучше, как у Вас, то есть для $1$ это будет функция $f(1) = \{0, 1\}^\mathbb N$. (Причем эта функция имеет одно и то же значение от любого натурального числа.)

И в самой этой функции и заключается информация об отсутствии биекции между $\mathbb N$ и $\{0, 1\}^\mathbb N$, потому что по ней видно, что каждому натуральному числу соответствует не какая-то одна последовательность, а сразу все.

[Mikhail_K]

Vladimir Pliassov
Давайте я докажу, что якобы не существует биекции между множествами $\{1,2,3\}$ и $\{4,5,6\}$.
Для этого я построю такое, как Вы говорите, "не отображение, а соответствие" $f$: пусть $f(1)=\{4,5,6\}$, $f(2)=\{4,5,6\}$ и $f(3)=\{4,5,6\}$ тоже.
И дальше скажу: и в самой этой функции и заключается информация об отсутствии биекции между $\{1,2,3\}$ и $\{4,5,6\}$, потому что по ней видно, что каждому числу из множества $\{1,2,3\}$ соответствует не какое-то одно число из множества $\{4,5,6\}$, а сразу все.
Хорошее доказательство?

[Vladimir Pliassov]

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

[Mikhail_K]

Vladimir Pliassov
Ну то есть Вы разобрались, что не так в Вашем доказательстве.
Избегайте в своих рассуждениях всяких невнятностей типа "в функции содержится информация".
У каждого утверждения должен быть точный и строгий смысл.

[Vladimir Pliassov]

Спасибо! Постараюсь.

[Vladimir Pliassov]

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

Мы построили биекцию между $\mathcal P(\{a, b, c\})$ и множеством функций из $\{a, b, c\}$ в $\{0, 1\}$. Можете ли вы аналогично построить биекцию между $\mathcal P(\mathbb N)$ и множеством функций из $\mathbb N$ в $\{0, 1\}$?

(Оффтоп)

А потом вспомнить, зачем это было нужно.

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

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

где $a\in \mathbb N, \; A\subseteq \mathbb N$. Тогда имеется биекция $g\colon \mathcal P(\mathbb N)\leftrightarrow \{0, 1\}^\mathbb N$.

$\rhd$ В самом деле, по правилу (1) функция $f$ определяет единственное подмножество $A$, то есть имеется инъективное отображение $\{0, 1\}^\mathbb N\rightarrow\mathcal P(\mathbb N)$.

Вместе с тем имеется инъективное отображение $\mathcal P(\mathbb N)\rightarrow \{0, 1\}^\mathbb N$, для доказательства этого предположим, что $a\in A$, тогда $f(a) \ne 0$, поскольку $f(a) = 0\to a\notin A$, то есть $f(a)=1$.

И наоборот, пусть $a\notin A$, тогда $f(a)= 0$, поскольку $f(a) \ne 0\to a\in A$.

Таким образом, биекция $g\colon \mathcal P(\mathbb N)\leftrightarrow \{0, 1\}^\mathbb N$ доказана.$\lhd$

Далее, опираясь на проведенное доказательство и доказательство

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$ не существует.

делаем вывод, что биекция $\mathbb N\leftrightarrow \{0, 1\}^\mathbb N$ не существует.

Таким образом, теорема "Множество бесконечных последовательностей нулей и единиц несчётно" доказана.

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

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

берем первый элемент множества $\mathbb N$ и решаем, куда его отобразить: в ноль или в единицу, -- затем берем второй элемент множества $\mathbb N$ и решаем, куда его отобразить, и так далее. Так "при помощи" множества $\{0,1\}$

Не вижу здесь никакой "помощи".

Да, терминология оставляет желать лучшего. Буду стараться ее исправить.

Ivan_B в сообщении #1526628 писал(а):

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

Ivan_B Мне кажется, Вы правы, так оно и есть: доказательство начинается со слов "Предположим, что оно счётно... Составим бесконечную вниз таблицу, строками которой будут наши последовательности", -- а заканчивается словами: "Это противоречит нашему предположению о том, что таблица включает в себя все последовательности."

[mihaild]

Vladimir Pliassov, примерно так, только слова немного другие. Ваше рассуждение создает впечатление, что речь о какой-то конкретной последовательности $f$, хотя на самом деле мы определяем биекцию на множестве последовательностей. И выражения вида "функция определяет подмножество", "биекция доказана", хотя и можно догадаться, что значат, но являются синтаксически некорректными.
Лучше так:
Определим отображение $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$ - биекция.

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

[Vladimir Pliassov]

Спасибо! Понятно.

[Someone]

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

Ivan_B в сообщении #1526628 писал(а):

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

Ivan_B Мне кажется, Вы правы, так оно и есть: доказательство начинается со слов "Предположим, что оно счётно... Составим бесконечную вниз таблицу, строками которой будут наши последовательности", -- а заканчивается словами: "Это противоречит нашему предположению о том, что таблица включает в себя все последовательности."

Нет здесь доказательства от противного просто потому, что первоначальное предположение "предположим, что оно счётно…" нигде в доказательстве по-настоящему не используется, кроме последней фразы "итак, мы доказали, что оно несчётно, что противоречит первоначальному предположению".

[Vladimir Pliassov]

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

Нет здесь доказательства от противного просто потому, что первоначальное предположение "предположим, что оно счётно…" нигде в доказательстве по-настоящему не используется, кроме последней фразы "итак, мы доказали, что оно несчётно, что противоречит первоначальному предположению".

В этом доказательстве, по-моему, вообще непонятно, что используется, потому что используются какие-то мистические представления о бесконечности -- я имею в виду представление о матрице, которая при любом конечном $n$ не квадратная, да еще и с ростом $n$ все больше вытягивается по вертикали, а при бесконечном $n$ (еще один мистический момент -- $n=\infty$) вдруг становится квадратной. По этому вопросу мне мало что остается прибавить к тому, что я написал в первоначальном сообщении темы (не знаю, Вы читали или нет).

Я склоняюсь к мнению, что

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

таблица тут для красоты, главное - у нас есть функция $\mathbb N \to (\mathbb N \to \{0, 1\})$ - т.е. из натуральных чисел в последовательности

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

[xagiwo]

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

[Mikhail_K]

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

и мне странно, что эта таблица всюду представляется как доказательство

Дело в том, что при должном опыте (который авторы учебников обычно предполагают у читателя), когда читаешь "бесконечная таблица из нулей и единиц", в уме сразу понимаешь, что автор хотел сказать "функция $\mathbb N \to (\mathbb N \to \{0, 1\})$".

[xagiwo]

(Оффтоп)

А ТС пытался решать задачи хотя бы из Виленкина, или он их игнорирует?

[Vladimir Pliassov]

Mikhail_K в сообщении #1527123 писал(а):

Дело в том, что при должном опыте (который авторы учебников обычно предполагают у читателя), когда читаешь "бесконечная таблица из нулей и единиц", в уме сразу понимаешь, что автор хотел сказать "функция $\mathbb N \to (\mathbb N \to \{0, 1\})$".

Но доказательство опирается на понятие диагонали, возможно ли усмотреть это понятие в доказательстве

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$ не существует.

(когда уже доказана биекция $\mathcal P(\mathbb N)\leftrightarrow \{0, 1\}^\mathbb N$ или, может быть, в этом доказательстве вместе с доказательством биекции $\mathcal P(\mathbb N)\leftrightarrow \{0, 1\}^\mathbb N$)?