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

[AlexeyM]

В теореме Кантора о несчетности множества всех действительных чисел отрезка [0;1] используется следующая логическая цепочка (картинка из книги "Дискретная математика для инженера", авт. Кузнецов):



Однако те же рассуждения можно применить к рациональным числам отрезка [0;1], представив их бесконечными десятичными дробями. Точно так же предположить, что существует нумерация и записать бесконечные десятичные дроби в порядке этой нумерации. А потом, рассуждая так же, как и в диагональном методе Кантора (т.е., повторяя рассуждения второго абзаца текста на картинке), получим, что множество рациональных чисел отрезка [0;1] не является счетным. Подскажите, пожалуйста, где ошибка в этих рассуждениях? Почему диагональный метод Кантора в случае рациональных дробей будет неприменим?

[Xaositect]

AlexeyM в сообщении #756697 писал(а):

Подскажите, пожалуйста, где ошибка в этих рассуждениях? Почему диагональный метод Кантора в случае рациональных дробей будет неприменим?

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

[AlexeyM]

Xaositect в сообщении #756699 писал(а):

AlexeyM в сообщении #756697 писал(а):

Подскажите, пожалуйста, где ошибка в этих рассуждениях? Почему диагональный метод Кантора в случае рациональных дробей будет неприменим?

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

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

[Xaositect]

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

[AlexeyM]

Xaositect

Вроде дошло, спасибо :)

[nikvic]

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

[Someone]

Да. А всего-то надо было уточнить, что в качестве $b_k$ мы выбираем $1$, если $a_{kk}\neq 1$, и $2$, если $a_{kk}=1$. В результате полученная дробь $0{,}b_1b_2b_3\ldots$ заведомо не будет десятично-рациональным числом и потому не может оказаться вторым "именем" какого-нибудь числа, присутствующего в списке.

AlexeyM в сообщении #756700 писал(а):

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

Как-как... У Вас же в списке были все рациональные числа, а полученная дробь ни с одним из них не совпадает. Поэтому заведомо не является рациональным числом. Список всех рациональных чисел нетрудно составить (в смысле — определить алгоритм составления такого списка).

[nikvic]

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

Да. А всего-то надо было уточнить, что в качестве $b_k$ мы выбираем $1$, если $a_{kk}\neq 1$, и $2$, если $a_{kk}=1$. В результате полученная дробь $0{,}b_1b_2b_3\ldots$ заведомо не будет десятично-рациональным числом и потому не может оказаться вторым "именем" какого-нибудь числа, присутствующего в списке.

Это потребовало дополнительных рассуждений про "хвост", которые можно избежать. Удобнее всего сдвиг на 5 (по модулю 10), и тогда расстояние гарантированно не меньше, чем

[AlexeyM]

nikvic в сообщении #756712 писал(а):

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

Когда Вы говорили про "два имени", Вы имели в виду соответствующие числа с периодом (9) и периодом (0)?

[Someone]

nikvic в сообщении #756734 писал(а):

Удобнее всего сдвиг на 5 (по модулю 10), и тогда расстояние гарантированно не меньше, чем

Расстояние здесь не играет роли, а проблему десятично-рациональных чисел это не решает.

AlexeyM в сообщении #756756 писал(а):

имели в виду соответствующие числа с периодом (9) и периодом (0)?

Да. Некоторые числа имеют две записи, из которых одна имеет период $(9)$, а другая — $(0)$. Если в списке есть только одна из этих записей, то случайно может получиться другая. Простейший способ избежать этого — при выборе $b_k$ запретить $0$ и $9$.

[nikvic]

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

nikvic в сообщении #756734 писал(а):

Удобнее всего сдвиг на 5 (по модулю 10), и тогда расстояние гарантированно не меньше, чем

Расстояние здесь не играет роли, а проблему десятично-рациональных чисел это не решает.

Наверное, у Вас наготове контрпример?

[ewert]

nikvic в сообщении #756712 писал(а):

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

Это как раз верное утверждение. Хотя у Кузнецова сформулировано действительно неаккуратно. Однако проблема отнюдь не в возможном совпадении. Если под числами понимать (как это обычно принято) лишь дроби, не оканчивающиеся на девятки, то проблема в том, что после неаккуратной замены может получиться запрещённая комбинация.

[nikvic]

ewert в сообщении #757340 писал(а):

nikvic в сообщении #756712 писал(а):

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

Это как раз верное утверждение.

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

[ewert]

nikvic в сообщении #757342 писал(а):

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

В Вашей фразе -- как раз предполагалась. Во всяком случае, сказалось буквально так.

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

[nikvic]

ewert в сообщении #757347 писал(а):

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

Не обязательно. Сдвиг по модулю 10 на 5 - один из приёмов. Годитсья и для бинарного случая - брать парами