2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

Изображение

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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 19:57 
Аватара пользователя
AlexeyM в сообщении #756697 писал(а):
Подскажите, пожалуйста, где ошибка в этих рассуждениях? Почему диагональный метод Кантора в случае рациональных дробей будет неприменим?
Потому что полученная в тоге бесконечная дробь не обязательно будет рациональным числом.

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 19:59 
Xaositect в сообщении #756699 писал(а):
AlexeyM в сообщении #756697 писал(а):
Подскажите, пожалуйста, где ошибка в этих рассуждениях? Почему диагональный метод Кантора в случае рациональных дробей будет неприменим?
Потому что полученная в тоге бесконечная дробь не обязательно будет рациональным числом.


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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 20:01 
Аватара пользователя
Не понимаю вопроса. Бесконечная дробь по определению может не быть рациональной, а может быть. Вот если она не рациональная, то противоречия не получается, и доказательство от противного не проходит.

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 20:14 
Xaositect

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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 20:32 
Аватара пользователя
Исходное доказательство не полно - при верной конструкции, где нумеруются все числа, а не "дроби".
Но в конце автор пользуется неверным подразумеваемым утверждением, что дроби, различающиеся в одном регистре, выражают разные числа - он забыл про два "имени" для десятично-рациональных чисел.

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

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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 21:31 
Аватара пользователя
Someone в сообщении #756732 писал(а):
Да. А всего-то надо было уточнить, что в качестве $b_k$ мы выбираем $1$, если $a_{kk}\neq 1$, и $2$, если $a_{kk}=1$. В результате полученная дробь $0{,}b_1b_2b_3\ldots$ заведомо не будет десятично-рациональным числом и потому не может оказаться вторым "именем" какого-нибудь числа, присутствующего в списке.

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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 22:31 
nikvic в сообщении #756712 писал(а):
Исходное доказательство не полно - при верной конструкции, где нумеруются все числа, а не "дроби".
Но в конце автор пользуется неверным подразумеваемым утверждением, что дроби, различающиеся в одном регистре, выражают разные числа - он забыл про два "имени" для десятично-рациональных чисел.


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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 23:04 
Аватара пользователя
nikvic в сообщении #756734 писал(а):
Удобнее всего сдвиг на 5 (по модулю 10), и тогда расстояние гарантированно не меньше, чем
Расстояние здесь не играет роли, а проблему десятично-рациональных чисел это не решает.

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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 16:17 
Аватара пользователя
Someone в сообщении #756765 писал(а):
nikvic в сообщении #756734 писал(а):
Удобнее всего сдвиг на 5 (по модулю 10), и тогда расстояние гарантированно не меньше, чем
Расстояние здесь не играет роли, а проблему десятично-рациональных чисел это не решает.

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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 17:00 
nikvic в сообщении #756712 писал(а):
неверным подразумеваемым утверждением, что дроби, различающиеся в одном регистре, выражают разные числа - он забыл про два "имени" для десятично-рациональных чисел.

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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 17:05 
Аватара пользователя
ewert в сообщении #757340 писал(а):
nikvic в сообщении #756712 писал(а):
неверным подразумеваемым утверждением, что дроби, различающиеся в одном регистре, выражают разные числа - он забыл про два "имени" для десятично-рациональных чисел.

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

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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 17:15 
nikvic в сообщении #757342 писал(а):
Как насчёт единицы в виде кучи девяток после запятой? Есть регистр, где они отличаются.
В моей фразе не предполагается единственность регистра с различием.

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

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

 
 
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 19:03 
Аватара пользователя
ewert в сообщении #757347 писал(а):
Дело в том, что перед переходом к диагональному методу дублирующие комбинации (пресловутые девятки) заранее должны быть исключены (иначе о какой проверке биективности может идти речь).

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

 
 
 [ Сообщений: 59 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group