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

[Mikhail_K]

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

Пытаюсь это понять.

Воспринимайте это как задачу: построить биекцию между множеством подмножеств $\mathbb{N}$ и множеством бесконечных последовательностей из нулей и единиц. Это несложная задача, но над ней нужно какое-то время подумать.

То есть Вам нужно и множеству $\{1,2\}$, и множеству $\{1,2,3\}$, и множеству всех чётных натуральных чисел, и множеству всех простых чисел, и любому другому подмножеству $\mathbb{N}$ поставить в соответствие какую-то последовательность только из нулей и единиц. Каждому - свою, т.е. взаимно однозначно. Подумайте, как это можно сделать.

[Vladimir Pliassov]

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

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

Подмножеству $\{0,1\}$ (в данном случае) биективно соответствует не какая-то одна последовательность нулей и единиц, а множество всех бесконечных последовательностей нулей и единиц

Это вы что-то странное написали. Что вообще значит "подмножеству что-то биективно соответствует"?

Есть подмножество $\{0,1\}$, есть подмножество $\{0,1,2\}$. Подмножеству $\{0,1\}$ соответствует множество всех бесконечных последовательностей нулей и единиц, и наоборот (в том отношении, что это множество производится по формуле $f: \mathbb N \to \{0, 1\}$). Подмножеству $\{0,1,2\}$ соответствует множество всех бесконечных последовательностей нулей, единиц и двоек, и наоборот (оно производится по формуле $f: \mathbb N \to \{0, 1, 2\}$). И так далее, то есть каждому подмножеству $\mathbb N$ биективно соответствует некоторое (бесконечное) множество бесконечных последовательностей. Поэтому как же может быть, что

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

существует биекция между множеством всех подмножеств натуральных чисел, и множеством всех последовательностей из нулей и единиц

? Причем тут вообще все другие подмножества, кроме $\{0,1\}$? Ведь все бесконечные последовательности нулей и единиц производятся по формуле $f: \mathbb N \to \{0, 1\}$, разве нет?

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

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

Таким образом, я вижу биекцию между $\mathcal P(\mathbb N)$ и множеством всех множеств бесконечных последовательностей

А вот такой биекции уже не существует. Множеств бесконечных последовательностей больше, чем подмножеств $\mathbb N$.

И это тоже странно, ведь каждому подмножеству $\mathbb N$ (например, $\{0,1\},\; \{0,1,2\}$) --

(правда, за исключением пустого множества -- может быть, в этом дело? Но нет, тогда должно быть наоборот: подмножеств $\mathbb N$ больше, чем множеств бесконечных последовательностей.) --

каждому подмножеству $\mathbb N$ соответствует свое (бесконечное) множество бесконечных последовательностей, то есть отображение подмножеств $\mathbb N$ в множества бесконечных последовательностей инъективно, и, как я полагал, сюръективно, то есть множеств последовательностей не больше, чем подмножеств $\mathbb N$.

Или бесконечные последовательности могут строиться не только по функции $f: \mathbb N \to A$, где $A$ это общее обозначение для подмножества $\mathbb N$? Неужели это возможно?

-- 22.07.2021, 23:55 --

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

То есть Вам нужно и множеству $\{1,2\}$, и множеству $\{1,2,3\}$, и множеству всех чётных натуральных чисел, и множеству всех простых чисел, и любому другому подмножеству $\mathbb{N}$ поставить в соответствие какую-то последовательность только из нулей и единиц. Каждому - свою, т.е. взаимно однозначно. Подумайте, как это можно сделать.

Ну вот, теперь прояснилось! А я-то думал, что последовательность из нулей и единиц может сопоставляться только множеству $\{1,2\}$, потому что она производится при помощи этого множества.

Спасибо!

[mihaild]

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

Подмножеству $\{0,1\}$ соответствует множество всех бесконечных последовательностей нулей и единиц, и наоборот

Что значит "подмножеству соответствуют"? Обычно так говорят, когда уже задана какая-то биекция, а тут её нет.

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

оно производится по формуле $f: \mathbb N \to \{0, 1, 2\}$

Это не формула. Это компактный способ записи утверждения "$f$ - функция из $\mathbb N$ в $\{0, 1, 2\}$". Если вас это путает - давайте вообще не использовать такую запись со стрелкой.

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

Причем тут вообще все другие подмножества, кроме $\{0,1\}$?

То, что $\{0, 1\}$ (область значений функции) является подмножеством $\mathbb N$, в данном случае вообще неважно.

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

[Vladimir Pliassov]

Я там, в конце прошлого сообщения дописал, что недоразумение разъяснилось: я думал, что последовательность из нулей и единиц сопоставляется только множеству $\{1,2\}$ (потому что она производится при помощи этого множества).

Теперь попробую идти дальше.

[Vladimir Pliassov]

Выразим каждое натуральное число в двоичной системе (вообще, в какой-то системе счисления -- например, в двоичной, десятичной, $47$-ичной, $37485947363521419576$-ичной, -- они должны быть выражены, поскольку проблематично иметь неограниченное число цифр).

Например, $5$ выразится как $101$, $14$ как $1110$, $107$ как $1101011$.

То есть каждому натуральному числу будет сопоставлена конечная последовательность нулей и единиц.

Тогда произвольное подмножество $A$ множества $\mathbb N$ можно представить как множество конечных последовательностей нулей и единиц.

Упорядочим каждое подмножество $A$.

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

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

Таким образом, каждому подмножеству $A$ множества $\mathbb N$ будет сопоставлена своя собственная, то есть уникальная, бесконечная последовательность нулей и единиц. (Ее уникальность следует из единственности представления каждого натурального числа в двоичной системе, уникальности каждого множества и из того, что строя последовательность для каждого подмножества $A$, мы его упорядочивали единственным образом).

Другими словами, отображение $\mathcal P(\mathbb N)$ в $\{0, 1\}^\mathbb N$ инъективно.

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

Биекция доказана (конструктивно?).

[mihaild]

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

Чтобы сделать из нее бесконечную, припишем перед ней бесконечное число нулей

Может быть после? Последовательности обычно бесконечны вправо.

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

Таким образом, каждому подмножеству $A$ множества $\mathbb N$ будет сопоставлена своя собственная, то есть уникальная, бесконечная последовательность нулей и единиц

Нет, не уникальная. Например, множествам $\{1, 3, 7, 15, \ldots, 2^{n - 1}, \ldots\}$ и $\{3, 7, 15, \ldots, 2^{n - 1}\}$ будет сопоставлена одна и та же последовательность - состоящая из одних единиц.

[Vladimir Pliassov]

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

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

Чтобы сделать из нее бесконечную, припишем перед ней бесконечное число нулей

Может быть после? Последовательности обычно бесконечны вправо.

Нет, перед, чтобы последовательность соответствовала числу -- если к числу приписать любое количество нулей слева, оно не изменится, а если справа, то изменится.

Хотя, наверное, можно и после, потому что это ведь не число, а соответствующая ему последовательность?

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

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

Таким образом, каждому подмножеству $A$ множества $\mathbb N$ будет сопоставлена своя собственная, то есть уникальная, бесконечная последовательность нулей и единиц

Нет, не уникальная. Например, множествам $\{1, 3, 7, 15, \ldots, 2^{n - 1}, \ldots\}$ и $\{3, 7, 15, \ldots, 2^{n - 1}\}$ будет сопоставлена одна и та же последовательность - состоящая из одних единиц.

Почему $2$ в степени $n - 1$, а не $n $? И почему в $\{3, 7, 15, \ldots, 2^{n - 1}\}$ после $2^{n - 1}$ нет запятой и многоточия?

[mihaild]

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

Нет, перед, чтобы последовательность соответствовала числу -- если к числу приписать любое количество нулей слева, оно не изменится, а если справа, то изменится.

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

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

Почему $2$ в степени $n - 1$, а не $n $? И почему в $\{3, 7, 15, \ldots, 2^{n - 1}\}$ после $2^{n - 1}$ нет запятой и многоточия?

Потому что опечатки. Должно быть $\{1, 3, 7, 15, \ldots, 2^n - 1, \ldots\}$ и $\{3, 7, 15, \ldots, 2^n - 1, \ldots\}$.

[Someone]

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

думал, что последовательность из нулей и единиц сопоставляется только множеству $\{1,2\}$ (потому что она производится при помощи этого множества).

Что это значит — "последовательность производится при помощи множества"?

[Vladimir Pliassov]

Да, принцип, который я взял, здесь не работает, и не только для бесконечных, но и для конечных последовательностей.

Выразим множества $\{1,3,4\}$ и $\{1,28\}$ в двоичной форме, получим $\{1, 11, 100\}$ и $\{1, 11100\}$ соответственно.

Объединим последовательности $(1), (11), (100)$, соответствующие элементам первого множества, в одну, получим $(111 100)$.

Объединим последовательности $(1), (11100)$, соответствующие элементам второго множества, получим то же самое -- $(111 100)$.

То есть разным множествам соответствует одна и та же последовательность.

Но ничего другого пока не придумал.

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

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

думал, что последовательность из нулей и единиц сопоставляется только множеству $\{1,2\}$ (потому что она производится при помощи этого множества).

Что это значит — "последовательность производится при помощи множества"?

По утверждению $f: \mathbb N \to \{0, 1\}$ (то есть при помощи множества $\{0, 1\}$) строятся все бесконечные последовательности нулей и единиц.

[mihaild]

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

Но ничего другого пока не придумал

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

[Mikhail_K]

Vladimir Pliassov
Подсказка: никакой двоичной системы не надо.

[Vladimir Pliassov]

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

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

У множества $\{a, b, c\}$ восемь подмножеств: $\{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}, \varnothing$.

Функций из $\{a, b, c\}$ в $\{0, 1\}$ тоже восемь, то есть $2^3$.

Так что в отношении мощностей биекция между $\mathcal P(\{a, b, c\})$ и $f: \{a, b, c\} \to \{0, 1\}$ возможна. Но по какому принципу ее установить, не вижу.

[mihaild]

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

Но по какому принципу ее установить, не вижу

Мы хотим из функций делать подмножества, причем из разных функций разные подмножества. Нам принесли функцию $f$ и просят от нас подмножество. Давайте скажем, что это подмножество будет включать в себя $a$, если $f(a) = 1$, и не будет, если $f(a) = 0$. Аналогично с $b$ и $c$.
Какое подмножество по этому правилу получится для функции $f(a) = f(c) = 1$, $f(b) = 0$?
Верно ли, что это правило сопоставляет разным функциям разные подмножества? (докажите или приведите контрпример)
Верно ли, что это правило каждое подмножество сопоставляет некоторой функции? (докажите, не опираясь на мощности - в бесконечном случае у нас независимого способа оценить их не будет)

[Dan B-Yallay]

(Оффтоп)

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

Давайте скажем, что это подмножество будет включать в себя $a$, если $f(a) = 1$, и не будет, если $f(a) = 0$. Аналогично с $b$ и $c$.

Мне кажется, что такая дискуссия гораздо более соответствует уровню ТС, нежели беседы о конструктивизме.