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

[Mikhail_K]

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

Биекция это взаимно-однозначное отображение. Разве

$f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ...

это не взаимно-однозначное отображение?

А почему это взаимно однозначное отображение?
Чему равны здесь эти $b$-шки, $c$-шки и т.д.? Где у Вас гарантия, что все возможные последовательности нулей и единиц у Вас получаются с помощью такой функции?

Впрочем, неважно, чему они равны. К той функции, которую Вы построили, тоже можно применить диагональный процесс. Убедитесь, что последовательность $(1-a_1, b_2, 1-b_3, 1-c_4, 1-d_5, \ldots)$ не совпадает с $f(n)$ ни при каком натуральном $n$.

Наверное, Ваша ошибка вот в чём: Вы почему-то решили, что последовательность $(1-a_1, 1-b_2, 1-c_3, …)$ единственная неучтённая, и если её добавить (например как $f(2)$), то получится биекция. Но это не так.

[mihaild]

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

это будет означать признание $n=\infty.$

Что это вообще значит?
Нам принесли функцию $f$, и мы из неё делаем последовательность.

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

Разве $f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ... это не взаимно-однозначное отображение?

Это вообще не конкретное отображение - для разных $a_i$, $b_i$ и т.д. будут разные функции.
И ни одна из них не будет биекцией. Диагональный метод выдаст последовательность $(1 - a_1, b_2, 1 - b_3, 1 - c_4, \ldots)$, которая образу этой функции не принадлежит.

[xagiwo]

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

$f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ...

У вас $f(2) = (1-a_1, 1-b_2, 1-c_3, …)$? Странно. У меня $f(2) = (b_1, b_2, b_3, …)$, они не совпадают.

[Vladimir Pliassov]

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

А почему это взаимно однозначное отображение?

Бесконечные последовательности нулей и единиц -- в том числе и $(1-a_1, 1-b_2, 1-c_3, …)$, -- каждая из которых взаимно-однозначно соответствует единственному натуральному числу -- разве это не взаимно-однозначное отображение?

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

Чему равны здесь эти $b$-шки, $c$-шки и т.д.?

Я не понимаю, что вы имеете в виду: $a, b, c \ldots$ с индексами это члены последовательностей. И здесь тоже:

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

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

Разве $f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ... это не взаимно-однозначное отображение?

Это вообще не конкретное отображение - для разных $a_i$, $b_i$ и т.д. будут разные функции.

Если взять выражение $f(1) = (a_1, a_2, a_3, …)$, то оно означает, что единице взаимно-однозначно соответствует последовательность $(a_1, a_2, a_3, …)$, и разве здесь имеет значение то, что члены последовательности не выписаны конкретными числами?

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

Где у Вас гарантия, что все возможные последовательности нулей и единиц у Вас получаются с помощью такой функции?

Я и не говорю, что есть такая гарантия, здесь речь идет не обо всех последовательностях, а об этих: $f(1) = (a_1, a_2, a_3, …)$; $f(2) = (b_1, b_2, b_3, …);$ $f(3) = (c_1, c_2, c_3, …);$ ... плюс еще одна.

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

Убедитесь, что последовательность $(1-a_1, b_2, 1-b_3, 1-c_4, 1-d_5, \ldots)$ не совпадает с $f(n)$ ни при каком натуральном $n$.

Я сначала подумал, что Вы имеете в виду $(1-a_1, 1-b_2, 1-c_3, …)$, но теперь смотрю и не пойму, что это за последовательность: $(1-a_1, b_2, 1-b_3, 1-c_4, 1-d_5, \ldots)$.

Но если бы Вы имели в виду $(1-a_1, 1-b_2, 1-c_3, …)$, то я бы сказал, что я в этом убеждался много раз, но мне кажется, что главный вопрос здесь не тот, отличается ли она от всех других указанных последовательностей (это само собой), а тот, может ли быть биекция между натуральными числами и последовательностями, привлеченными к доказательству, приведенному в начале темы. Этими последовательностями являются все те, которые в этом доказательстве представлены как строки таблицы, то есть $f(1) = (a_1, a_2, a_3, …)$; $f(2) = (b_1, b_2, b_3, …);$ $f(3) = (c_1, c_2, c_3, …);$ ... -- и, кажется, никто не спорит с тем, что они находятся в биекции с натуральными числами, -- плюс еще одна, то есть $(1-a_1, 1-b_2, 1-c_3, …)$.

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

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

Наверное, Ваша ошибка вот в чём: Вы почему-то решили, что последовательность $(1-a_1, 1-b_2, 1-c_3, …)$ единственная неучтённая,

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

(Я употребляю термины "таблица", "строка", "диагональ", потому что так мне гораздо легче выразить мысль, и к тому же в разбираемом доказательстве они тоже употребляются.)

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

и если её добавить (например как $f(2)$), то получится биекция. Но это не так.

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

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

Что это вообще значит?

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

Если кто-то возразит, что последовательность $(1-a_1, 1-b_2, 1-c_3, …)$ следует определять только после того, как определены последовательности $(a_1, a_2, a_3, …)$; $(b_1, b_2, b_3, …)$; $(c_1, c_2, c_3, …);$ ... , это будет означать признание $n=\infty.$

Здесь я имел в виду, что полностью определить какую-то бесконечную последовательность, то есть определить все ее члены, так же невозможно, как взять $n=\infty$.

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

И ни одна из них не будет биекцией. Диагональный метод выдаст последовательность $(1 - a_1, b_2, 1 - b_3, 1 - c_4, \ldots)$, которая образу этой функции не принадлежит.

Здесь опять эта последовательность. Может быть, Вы имели в виду $(1-a_1, 1-b_2, 1-c_3, …)$? Если так, то:

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

$f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ... .

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

У вас $f(2) = (1-a_1, 1-b_2, 1-c_3, …)$? Странно. У меня $f(2) = (b_1, b_2, b_3, …)$, они не совпадают.

Я это сделал, чтобы, так сказать, "внести эту последовательность в список."

[Mikhail_K]

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

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

Никто не спорит, что такая биекция возможна. И что? Вопрос-то был о существовании биекции

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

между $\mathbb N$ и всем множеством $\{0, 1\}^\mathbb N$

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

Может быть, Вы имели в виду $(1-a_1, 1-b_2, 1-c_3, …)$?

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

[xagiwo]

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

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

Ага, значит, Вы согласны с доказательством того, что моя $f$ не является биекцией, но считаете, что можно построить какую-то другую функцию, которая это доказательство как-то обходит? Но тогда эта другая функция не будет возвращать уже свою инвертированную диагональ, то есть она тоже не биекция. Вы указали на какую-то функцию (давайте обозначим её $g$, потому что всё же $f(2) = (b_1, b_2, …)$) с $g(2) = (1-a_1, 1-b_2, …)$, а Вам показали, что она не возвращает свою инвертированную диагональ, которая выглядит как $(1 - a_1, b_2, 1 - b_3, 1 - c_4, \ldots)$

Короче говоря, доказательство работает для всех функций, включая те, которые Вы строите, чтобы его обойти.

-- 09.08.2021, 03:02 --

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

Здесь я имел в виду, что полностью определить какую-то бесконечную последовательность, то есть определить все ее члены, так же невозможно, как взять $n=\infty$.

В каком смысле? Формула $a_n = n^2$, например, задаёт сразу все члены последовательности $a_n$

[Vladimir Pliassov]

Кажется, понял.

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

$$\begin {matrix} \alpha_1=&\alpha_{11}&\alpha_{12}&\alpha_{13}&\ldots\\ \alpha_2=&\alpha_{21}&\alpha_{22}&\alpha_{23}&\ldots\\ \alpha_3=&\alpha_{31}&\alpha_{32}&\alpha_{33}&\ldots\\ \hdotsfor [1.5] {5} \\ \end {matrix}\eqno {(1)}$$

при этом элементы $A$ будут поставлены во взаимно-однозначное соответствие с $\mathbb N$ (с множеством всех натуральных чисел), то есть будет задана биекция $f\colon \mathbb N\to A$.

В $\{0, 1\}^\mathbb N$, кроме элементов подмножества $A$, имеется, по крайней мере, один элемент, которого нет в $A$ , а именно, последовательность $\beta$ (полученная инвертированием последовательности $\alpha_ {11}, \alpha_ {22}, \alpha_ {33}, \ldots$), которой не может быть в таблице, следовательно, биекции между $\mathbb N$ и $\{0, 1\}^\mathbb N$ быть не может.

Спасибо всем!

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

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

Здесь я имел в виду, что полностью определить какую-то бесконечную последовательность, то есть определить все ее члены, так же невозможно, как взять $n=\infty$.

В каком смысле? Формула $a_n = n^2$, например, задаёт сразу все члены последовательности $a_n$

Я опять неправильно выразился: невозможно не определить полностью какую-то бесконечную последовательность, а, например, всю ее записать (то есть выписать все ее члены).

[Someone]

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

Если взять выражение $f(1) = (a_1, a_2, a_3, …)$, то оно означает, что единице взаимно-однозначно соответствует последовательность $(a_1, a_2, a_3, …)$, и разве здесь имеет значение то, что члены последовательности не выписаны конкретными числами?

Откуда здесь взялось взаимно однозначное соответствие? Процитированное равенство означает, что функция $f$ натуральному числу $1$ сопоставляет указанную последовательность. Вполне возможно, что и $f(2)=(a_1, a_2, a_3, …)$.

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

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

Неучтённые последовательности находятся в биекции с натуральными числами? С какой стати? Где эта биекция? Вы её не предъявили.

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

Я это сделал, чтобы, так сказать, "внести эту последовательность в список."

А какой в этом смысл? Мы взяли произвольный список последовательностей (последовательность последовательностей) и показали, что список не полон, так как мы смогли указать последовательность, не входящую в него. Наше рассуждение работает для всех списков. В том числе и для того, который Вы получите в результате добавления новой последовательности. Следовательно, полных списков не существует. Поэтому множество всех последовательностей нулей и единиц несчётно.

-- Пн авг 09, 2021 18:56:54 --

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

Я опять неправильно выразился: невозможно не определить полностью какую-то бесконечную последовательность, а, например, всю ее записать (то есть выписать все ее члены)

А зачем её всю записывать "на бумаге"? Она каким-то способом определена, и мы как-то можем найти любой её член. Нам неважно, как именно.

[Vladimir Pliassov]

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

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

Если взять выражение $f(1) = (a_1, a_2, a_3, …)$, то оно означает, что единице взаимно-однозначно соответствует последовательность $(a_1, a_2, a_3, …)$, и разве здесь имеет значение то, что члены последовательности не выписаны конкретными числами?

Откуда здесь взялось взаимно однозначное соответствие? Процитированное равенство означает, что функция $f$ натуральному числу $1$ сопоставляет указанную последовательность. Вполне возможно, что и $f(2)=(a_1, a_2, a_3, …)$.

Да, это я не подумал.

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

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

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

Неучтённые последовательности находятся в биекции с натуральными числами? С какой стати? Где эта биекция? Вы её не предъявили.

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

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

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

Я это сделал, чтобы, так сказать, "внести эту последовательность в список."

А какой в этом смысл? Мы взяли произвольный список последовательностей (последовательность последовательностей) и показали, что список не полон, так как мы смогли указать последовательность, не входящую в него. Наше рассуждение работает для всех списков. В том числе и для того, который Вы получите в результате добавления новой последовательности. Следовательно, полных списков не существует. Поэтому множество всех последовательностей нулей и единиц несчётно.

Да, теперь я это понимаю.

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

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

Я опять неправильно выразился: невозможно не определить полностью какую-то бесконечную последовательность, а, например, всю ее записать (то есть выписать все ее члены)

А зачем её всю записывать "на бумаге"? Она каким-то способом определена, и мы как-то можем найти любой её член. Нам неважно, как именно.

Да, и теперь я понимаю это лучше, чем раньше, спасибо.