Теорема Кантора о несчетности последовательностей 1 и 0

[Vladimir Pliassov]

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

Есть "диагональное" доказательство этой теоремы, оно обсуждалось здесь topic146697.html, но оно мне по-прежнему не кажется убедительным.

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

на два класса (то есть на $2^1$ классов), таких, что последовательности одного и того же класса имеют одинаковое начало, состоящее из одного элемента,

на четыре класса (то есть на $2^2$ классов), таких, что последовательности одного и того же класса имеют одинаковое начало, состоящее из двух элементов,

и так далее, при начале, состоящем из $n$ элементов, число классов равно $2^n$.

(Под классами здесь я понимаю непересекающиеся множества.)

Таким образом, каждому натуральному числу $n$ ставится в соответствие более одного класса. К тому же в каждом классе имеется более одной последовательности, так что каждому натуральному числу ставится в соответствие более одной последовательности. Поэтому это соответствие не является даже функцией и, тем более, не является биекцией.

Доказал или нет?

[Null]

Нет. Ничего не понятно.

[Vladimir Pliassov]

Null в сообщении #1567445 писал(а):

Нет. Ничего не понятно.

Каждая последовательность имеет начало, две последовательности могут иметь одно и то же начало, например, последовательности $5, 7, 3, 4, 9, 1, \ldots$ и $5, 7, 3, 1, 8, 2, \ldots$ имеют одно и то же начало $5, 7, 3$ состоящее из трех элементов.

[warlock66613]

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

Доказал или нет?

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

[Null]

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

Каждая последовательность имеет начало, две последовательности могут иметь одно и то же начало, например, последовательности $5, 7, 3, 4, 9, 1, \ldots$ и $5, 7, 3, 1, 8, 2, \ldots$ имеют одно и то же начало $5, 7, 3$ состоящее из трех элементов.

Не надо писать очевидные факты, нужно доказательство. У Вас даже отображения нет. Как можно что-то доказать не упоминая это что-то.

[Vladimir Pliassov]

Null в сообщении #1567450 писал(а):

У Вас даже отображения нет.

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

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

warlock66613 в сообщении #1567449 писал(а):

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

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

[Dan B-Yallay]

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

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

Теорема Кантора: построить биекцию между всевозможными бесконечными последовательностями из {0, 1} и натуральными числами могут не только лишь все, мало кто может это сделать.

Доказательство: участник форума dxdy не смог. ЧТД.

[gris]

Можно и вот такое отображение построить:
$1 \to (1,0,0,0,0....)$
$2 \to (0,1,0,0,0....)$
$3 \to (1,1,0,0,0....)$
$4 \to (0,0,1,0,0....)$
тоже не биекция, а очень естественно.

[Null]

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

Если имеется построение, из которого видно

У вас такого построения нет. Доказательство - последовательность утверждений. Выпишите их по порядку.

[Mikhail_K]

Vladimir Pliassov
А давайте я попробую "доказать" несчётность множества целых чисел $\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$.
Докажу так.
Я построю отображение $f:\,\mathbb{N}\to\mathbb{Z}$, действующее по формуле $f(n)=n$.
То есть $f(1)=1,\,f(2)=2,\,f(3)=3,\,\ldots$.
Это отображение $f$ не является биекцией (потому что $\mathbb{Z}$ включает ещё и отрицательные числа). Значит, множество $\mathbb{Z}$ несчётно.

Что не так в этом моём "доказательстве"? Потому что на самом деле множество $\mathbb{Z}$ счётно.

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

Есть "диагональное" доказательство этой теоремы, оно обсуждалось здесь topic146697.html , но оно мне по-прежнему не кажется убедительным.

Напрасно. Это значит, что что-то не так в Вашем чувстве "убедительности". С этим надо разбираться.

[Vladimir Pliassov]

gris в сообщении #1567461 писал(а):

Можно и вот такое отображение построить:
$1 \to (1,0,0,0,0....)$
$2 \to (0,1,0,0,0....)$
$3 \to (1,1,0,0,0....)$
$4 \to (0,0,1,0,0....)$
тоже не биекция, а очень естественно.

Должен признаться, что я не вижу, почему это не биекция. Но, если это не биекция, то тем более не будет биекции между натуральными числами и всеми последовательностями нулей и единиц (у Вас ведь не все?).

[Mikhail_K]

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

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

В том-то и дело, что это так не работает. Смотрите моё предыдущее сообщение.

[Vladimir Pliassov]

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

А давайте я попробую "доказать" несчётность множества целых чисел $\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$.
Докажу так.
Я построю отображение $f:\,\mathbb{N}\to\mathbb{Z}$, действующее по формуле $f(n)=n$.
То есть $f(1)=1,\,f(2)=2,\,f(3)=3,\,\ldots$.
Это отображение $f$ не является биекцией (потому что $\mathbb{Z}$ включает ещё и отрицательные числа). Значит, множество $\mathbb{Z}$ несчётно.

Что не так в этом моём "доказательстве"? Потому что на самом деле множество $\mathbb{Z}$ счётно.

В Вашем "доказательстве" из области значений функции $f(n)=n$ исключены отрицательные числа и ноль, так что она не может "претендовать" на отображение взаимоотношений между $\mathbb N$ и всем $\mathbb Z$. У меня же все возможные последовательности разбиты на классы, и даже эти классы не находятся в биекции с $\mathbb N$, не говоря о последовательностях.

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

Напрасно. Это значит, что что-то не так в Вашем чувстве "убедительности".

Буду еще стараться "убедиться".

[Mikhail_K]

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

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

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

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

[Vladimir Pliassov]

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

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

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

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

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

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

Null в сообщении #1567463 писал(а):

У вас такого построения нет. Доказательство - последовательность утверждений. Выпишите их по порядку.

Попытаюсь сделать это на свежую голову.

Dan B-Yallay в сообщении #1567459 писал(а):

Теорема Кантора: построить биекцию между всевозможными бесконечными последовательностями из {0, 1} и натуральными числами могут не только лишь все, мало кто может это сделать.

Доказательство: участник форума dxdy не смог. ЧТД.