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

[Someone]

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

По утверждению $f: \mathbb N \to \{0, 1\}$ (то есть при помощи множества $\{0, 1\}$)

Что значит — "при помощи"? Каким образом?
Текст "$f: \mathbb N \to \{0, 1\}$" означает, что отображение (= функция) $f$ определено на множестве $\mathbb N$ и принимает значения в множестве $\{0,1\}$. Здесь нет никакого "при помощи".

[Vladimir Pliassov]

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

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

$\{a, c\}.$

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

Верно ли, что это правило сопоставляет разным функциям разные подмножества? (докажите или приведите контрпример)

Верно. Возьмем одномерную таблицу из трех клеток, на первом месте которой может находиться либо $a$, либо ничто, на втором месте либо $b$, либо ничто, на третьем месте либо $c$, либо ничто. Возьмем произвольную из имеющихся у нас восьми последовательностей и расположим в таблице соответствующее ей подмножество (при этом в таблице может помещаться также и пустое множество). Инвертируем произвольный член взятой последовательности и при этом в таблице в соответствующей клетке либо поместим соответствующий элемент, которого там не было, либо уберем элемент, который там был, в любом случае подмножество изменится. То же самое произойдет, если инвертировать более одного элемента одновременно.

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

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

Верно. По этому правилу функция $f$ определяет подмножество $A$ (в которое она отображается):

$f(a) = 1\to a\in A$,

$f(a) = 0\to a\notin A$,

Вместе с тем подмножество $A$ определяет функцию $f$. В самом деле, пусть $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$.

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

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

По утверждению $f: \mathbb N \to \{0, 1\}$ (то есть при помощи множества $\{0, 1\}$)

Что значит — "при помощи"? Каким образом?
Текст "$f: \mathbb N \to \{0, 1\}$" означает, что отображение (= функция) $f$ определено на множестве $\mathbb N$ и принимает значения в множестве $\{0,1\}$. Здесь нет никакого "при помощи".

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

[mihaild]

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

(Оффтоп)

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

[Dan B-Yallay]

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

Так "при помощи" множества $\{0,1\}$ мы строим последовательность нулей и единиц.

А теперь обратная задача: задана какая-то последовательность из нулей и единиц. Сможете построить соответствующее ей подмножество $\mathbb N$?

-- Пт июл 23, 2021 16:28:05 --

Oпередили...

[Someone]

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

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

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

[Vladimir Pliassov]

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

$\rhd$ В самом деле, каждый элемент $\mathbb N$ отображается либо в ноль, либо в единицу, и таким образом участвует в построении каждой последовательности. Таким образом, имеется естественное соответствие каждого элемента $\mathbb N$ сразу всем последовательностям. Это соответствие не является отображением и потому не может быть биективным.$\lhd$

Цитата:

Отображением множества $X$ в множество $Y$ называется всякое правило $f$, по которому каждому элементу множества сопоставляется вполне определенный (единственный) элемент множества. https://studopedia.ru/10_41365_otobrazh ... hestv.html

[В https://habr.com/ru/post/232987/ есть изображение "дерева" бесконечных последовательностей нулей и единиц (рассматривать его, начиная с дробной части, то есть после $0,$).

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

[mihaild]

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

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

Что значит "участвует в построении последовательности"? И чтобы говорить что что-то куда-то отображается - нам уже нужно отображение, а о нем ни слова.

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

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

Это вообще непонятно что значит.

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

[В https://habr.com/ru/post/232987

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

[Vladimir Pliassov]

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

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

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

Что значит "участвует в построении последовательности"? И чтобы говорить что что-то куда-то отображается - нам уже нужно отображение, а о нем ни слова.

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

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

Это вообще непонятно что значит.

Конечно, доказательство не такое, как следует, так что его, вероятно, нельзя считать доказательством, но идея стоящая? Если ее обработать, получится доказательство?

Над заданными доказательствами работаю.

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

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

[В https://habr.com/ru/post/232987

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

Но разве рисунок "дерева" -- сам по себе, безотносительно к остальному содержанию статьи, мусор?

[mihaild]

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

Если ее обработать, получится доказательство?

Я пока не понимаю, в чем идея.
Если в том, чтобы построить инъекцию из натуральных чисел в последовательности, не являющуюся сюръекцией - то не получится. Потому что такое бывает и для равномощных бесконечных множеств.

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

Но разве рисунок "дерева" -- сам по себе, безотносительно к остальному содержанию статьи, мусор?

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

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

каждый элемент $\mathbb N$ отображается в каждую последовательность

- совершенно непонятно.

[Vladimir Pliassov]

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

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

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

каждый элемент $\mathbb N$ отображается в каждую последовательность

- совершенно непонятно.

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

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

[mihaild]

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

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

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

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

[Vladimir Pliassov]

Если так:

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

?

[mihaild]

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

[xagiwo]

(Оффтоп)

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

любая функция, действующая из множества натуральных чисел в множество (функций из натуральных чисел в $\{0, 1\}$), не сюръективна

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

[mihaild]

(Оффтоп)

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

Не биективна

Обычно (и в данном случае тоже) под "несчетно" понимают "более чем счетно".