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

[Alex17]

Хорошо известно доказательство несчётности множества действительных чисел (0;1). Нужно представить каждое действительное число из интервала (0;1) в виде бесконечной десятичной дроби, предположить что это множество можно перенумеровать и предложить число из (0;1), которое не будет содержаться в занумерованных числах. Это число строиться как "диагональ" занумерованных чисел с небольшой коррекцией на "9".

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

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

Спасибо за ответ.

[iifat]

Вопрос какой-то туманный. Один алгоритм (я про действительные числа) пропускает одно число, другой другое. Это число вполне может быть перечислено неким другим алгоритмом — ну и что?

[Mikhail_K]

Alex17
То есть Вы предлагаете применить диагональный метод для "доказательства несчётности" рациональных чисел, и спрашиваете, что там не получится?

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

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

[Sinoid]

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

потому что любая бесконечная десятичная дробь представляет собой действительное число.

Вообще говоря, в рамках конкретного доказательства это зависит от договоренности.

[Pphantom]

Sinoid в сообщении #1522754 писал(а):

Вообще говоря, в рамках конкретного доказательства это зависит от договоренности.

Кажется, вы что-то не так поняли. Сделанное Mikhail_K утверждение ни от какой договоренности не зависит.

[Sinoid]

Pphantom в сообщении #1522757 писал(а):

Кажется, вы что-то не так поняли. Сделанное Mikhail_K утверждение ни от какой договоренности не зависит.

Я имею ввиду, что запрещено в периоде: 0 или 9.

[Mikhail_K]

Sinoid в сообщении #1522762 писал(а):

Я имею ввиду, что запрещено в периоде: 0 или 9.

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

[Someone]

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

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

Можно просто пополнить список: если встретилась запись рационального числа с периодом $(9)$, то сразу за ней включить запись того же числа с периодом $(0)$, и наоборот.

[Geen]

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

Можно просто пополнить список

Но тогда надо доказать, что новый "список" "не хуже" старого...?

[Someone]

Geen в сообщении #1523051 писал(а):

Но тогда надо доказать, что новый "список" "не хуже" старого...?

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

[Dan B-Yallay]

Geen в сообщении #1523051 писал(а):

Но тогда надо доказать, что новый "список" "не хуже" старого...?

1) oн максимум вдвое длиннее старого, то есть, счётен;
2) eсли числа, построенного с помощью диагонального метода, нет в пополненном списке, то его не окажется и в первоначальном.

[ewert]

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

Можно просто пополнить список: если встретилась запись рационального числа с периодом $(9)$, то сразу за ней включить запись того же числа с периодом $(0)$, и наоборот.

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

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

[Geen]

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

Он занумерован натуральными числами

Как именно? Нам разрешены "алгоритмы" из счётного числа шагов?

[Someone]

Geen в сообщении #1523099 писал(а):

Нам разрешены "алгоритмы" из счётного числа шагов?

Э-э-э… Что за алгоритмы? В классическом математическом анализе нет алгоритмов. В теории множеств — тоже.

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

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

Собственно, для всех систем счисления, кроме двоичной и троичной, годится такое правило: если рассматриваемая цифра не равна $1$, то пишем $1$, а в противном случае пишем $2$.

Для двоичной и троичной систем цифры группируем в пары.
Правило построения: если рассматриваемая пара не есть $01$, то пишем $01$, а в противном случае пишем $10$.
Кстати, это правило годится и для остальных систем счисления.