2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

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



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 19:50 


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

Изображение

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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 19:57 
Заслуженный участник
Аватара пользователя


06/10/08
6422
AlexeyM в сообщении #756697 писал(а):
Подскажите, пожалуйста, где ошибка в этих рассуждениях? Почему диагональный метод Кантора в случае рациональных дробей будет неприменим?
Потому что полученная в тоге бесконечная дробь не обязательно будет рациональным числом.

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 19:59 


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


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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 20:01 
Заслуженный участник
Аватара пользователя


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

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


19/04/11
69
Xaositect

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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 20:32 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 21:19 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Да. А всего-то надо было уточнить, что в качестве $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 
Заслуженный участник
Аватара пользователя


06/04/10
3152
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 


19/04/11
69
nikvic в сообщении #756712 писал(а):
Исходное доказательство не полно - при верной конструкции, где нумеруются все числа, а не "дроби".
Но в конце автор пользуется неверным подразумеваемым утверждением, что дроби, различающиеся в одном регистре, выражают разные числа - он забыл про два "имени" для десятично-рациональных чисел.


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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение22.08.2013, 23:04 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
nikvic в сообщении #756734 писал(а):
Удобнее всего сдвиг на 5 (по модулю 10), и тогда расстояние гарантированно не меньше, чем
Расстояние здесь не играет роли, а проблему десятично-рациональных чисел это не решает.

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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 16:17 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Someone в сообщении #756765 писал(а):
nikvic в сообщении #756734 писал(а):
Удобнее всего сдвиг на 5 (по модулю 10), и тогда расстояние гарантированно не меньше, чем
Расстояние здесь не играет роли, а проблему десятично-рациональных чисел это не решает.

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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 17:00 
Заслуженный участник


11/05/08
32166
nikvic в сообщении #756712 писал(а):
неверным подразумеваемым утверждением, что дроби, различающиеся в одном регистре, выражают разные числа - он забыл про два "имени" для десятично-рациональных чисел.

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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 17:05 
Заслуженный участник
Аватара пользователя


06/04/10
3152
ewert в сообщении #757340 писал(а):
nikvic в сообщении #756712 писал(а):
неверным подразумеваемым утверждением, что дроби, различающиеся в одном регистре, выражают разные числа - он забыл про два "имени" для десятично-рациональных чисел.

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

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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 17:15 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Вопрос по диагональному методу Кантора
Сообщение24.08.2013, 19:03 
Заслуженный участник
Аватара пользователя


06/04/10
3152
ewert в сообщении #757347 писал(а):
Дело в том, что перед переходом к диагональному методу дублирующие комбинации (пресловутые девятки) заранее должны быть исключены (иначе о какой проверке биективности может идти речь).

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 59 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group