Счетность множества натуральных чисел

[Aleksei Korolev]

Проверим, а является ли множество натуральных чисел счётным, при помощи диагонального метода.
Чтобы использовать диагональный метод необходимо, чтобы числа были бесконечные. Для этого с левой стороны числа подставим нули.

Рассмотрим матрицу цифр бесконечной последовательности различных натуральных чисел:
$ \begin{matrix} ... & a_1_3 & a_1_2 & a_1_1 \\ ... & a_2_3 & a_2_2 & a_2_1 \\ ... & a_3_3 & a_3_2 & a_3_1 \\ ... & ... & ... & ... \end{matrix} $

Тем самым мы допускаем, что множество этих чисел - счетное.

Построим число. Для цифры $n$-го разряда будем писать 0, если $a_n_n$ не равно 0. В противно случае 1.
Каков бы ни был перечень чисел, можно построить новое натуральное число, не входящее в этот перечень.

Построенное разложение представляет некоторое натуральное число, расположенное между 0 и ∞, но оно должно отличаться, по крайней мере, одним десятичным знаком от каждого числа входящего в перечень. Следовательно, такую последовательность построить невозможно, т.е. невозможно пронумеровать бесконечную последовательность натуральных чисел, следовательно множество натуральных чисел не счетно.



Могли бы Вы подсказать, где здесь ошибка в рассуждениях?

[Pphantom]

Выделено из «Вопрос по диагональному методу Кантора»

[Pphantom]

Тема перемещена из форума «Мат. логика, основания математики, теория алгоритмов» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[gris]

А почему бесконечная последовательность цифр должна представлять натуральное число? В любом натуральном числе конечное число ненулевых цифр. То есть, начиная с некоторого $n$ на диагонали должны стоять ненулевые цифры. Тогда нужно доказать, что в такую решётку можно расставить числа из любого вашего списка, а для надёжности — все натуральные числа.

[Sicker]

Aleksei Korolev в сообщении #1401076 писал(а):

Могли бы Вы подсказать, где здесь ошибка в рассуждениях?

Ошибка в том, что получившаяся последовательность не будет описывать натуральное число, т.к. не существует номера, с которого влево шли бы одни нули

[podih]

Да тут никаких диагоналей Кантора не нужно. Любое $N$ мы пересчитываем на $N$-м шаге. - Просто тупо считая по порядку: $1, 2, 3, 4, 5, ...$
А раз один метод множество пересчитывает, то иной, не пересчитывающий, просто недостаточно эффективный или мы его неправильно понимаем.

[Aleksei Korolev]

Sicker в сообщении #1401102 писал(а):

Aleksei Korolev в сообщении #1401076 писал(а):

Могли бы Вы подсказать, где здесь ошибка в рассуждениях?

Ошибка в том, что получившаяся последовательность не будет описывать натуральное число, т.к. не существует номера, с которого влево шли бы одни нули

Могли бы Вы уточнить, о какой именно последовательности идет речь?

-- 24.06.2019, 00:47 --

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

А почему бесконечная последовательность цифр должна представлять натуральное число? В любом натуральном числе конечное число ненулевых цифр. То есть, начиная с некоторого $n$ на диагонали должны стоять ненулевые цифры. Тогда нужно доказать, что в такую решётку можно расставить числа из любого вашего списка, а для надёжности — все натуральные числа.

т.е. в такой формулировке доказывается, что множество бесконечных комбинаций цифр 0-9 несчетно?

-- 24.06.2019, 00:51 --

podih в сообщении #1401105 писал(а):

Да тут никаких диагоналей Кантора не нужно. Любое $N$ мы пересчитываем на $N$-м шаге. - Просто тупо считая по порядку: $1, 2, 3, 4, 5, ...$
А раз один метод множество пересчитывает, то иной, не пересчитывающий, просто недостаточно эффективный или мы его неправильно понимаем.

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

[Connector]

Цитата:

Могли бы Вы уточнить, о какой именно последовательности идет речь?

об этой:

Aleksei Korolev в сообщении #1401076 писал(а):

Построим число. Для цифры $n$-го разряда будем писать 0, если $a_n_n$ не равно 0. В противном случае 1.

[Someone]

Aleksei Korolev в сообщении #1401116 писал(а):

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

Aleksei Korolev в сообщении #1401076 писал(а):

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

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

Aleksei Korolev в сообщении #1401076 писал(а):

Построенное разложение представляет некоторое натуральное число

Доказательство предъявите, пожалуйста.

[gris]

Aleksei Korolev в сообщении #1401116 писал(а):

т.е. в такой формулировке доказывается, что множество бесконечных комбинаций цифр 0-9 несчетно?

Нет. Множество всех бесконечных последовательностей <из> десяти цифр действительно несчётно. И это можно доказать, используя диагональный метод. Но вы рассматриваете все бесконечные последовательности с конечным числом ненулевых цифр. Это множество счётно.
Ошибка в применении диагонального метода состоит в том, что вашим способом нельзя построить последовательность с конечным числом ненулевых цифр. Разве что из подмножества натуральных чисел.
Ни при какой нумерации нельзя так расставить все натуральные числа в вашей таблице, что на диагонали будет стоять лишь конечное число нулей. Это как раз следует из того, что множество всех натуральных чисел всё-таки счётно.

Приснилось бытовое объяснение. Вы думаете, что существует некоторый перечень всех натуральных чисел, который с помощью таблицы, а конкретно диагонали, даст натуральное число, отличающееся от всех чисел из перечня, то есть в него не входящее. Для этого диагональ должна содержать конечное число нулей, чтобы в искомом числе появилось конечное число ненулевых цифр. Но при любом перечне однозначные числа принесут в диагональ не менее $9$ нулей, двузначные не менее $88$ нулей, трёхзначные не менее $897$ и так далее. То есть чисто интуитивно видно, что в диагонали всегда будет бесконечное число нулей, в соответствующей последовательности — бесконечное число ненулевых цифр, и она не может представлять натуральное число.

[Munin]

Aleksei Korolev в сообщении #1401076 писал(а):

Могли бы Вы подсказать, где здесь ошибка в рассуждениях?

Построено $p$-адическое число, а не натуральное. $p$-адических чисел действительно более чем счётное множество, тут ошибки нет.

https://en.wikipedia.org/wiki/P-adic_number
https://ru.wikipedia.org/wiki/P-адическое_число

[Aleksei Korolev]

Спасибо всем, за помощь и указание на ошибки.