2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 26  След.
 
 Существует ли биекция между вычислимыми числами и нат.?
Сообщение26.01.2009, 07:28 


20/07/07
834
Помогите пожалуйста, разобраться.

Итак, что мы имеем в курсе матана?

- Рациональные числа вводятся как числа, выражаемые оношением двух целых чисел.

- Вещественные числа вводятся как множество пределов последовательностей рациональных чисел.

Но ведь множество возможных последовательностей рациональных чисел счетно! Значит, и множество вещественных чисел счетно?

Или следует полагать, что множество всех последовательностей несчетно?

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

 Профиль  
                  
 
 
Сообщение26.01.2009, 07:47 


13/09/08
3
Nxx в сообщении #181245 писал(а):
Но ведь множество возможных последовательностей рациональных чисел счетно!

Почему?

Множество всех возможных последовательностей несчетно как множество всех подмножеств.

 Профиль  
                  
 
 
Сообщение26.01.2009, 08:20 


20/07/07
834
Цитата:
Множество всех возможных последовательностей несчетно как множество всех подмножеств.

Как это доказать?

Собственно, все последовательности делятся на два класса:

- Рекурсивные, для которых существует алгоритм - их множество счетно, так как множество алгоритмов счетно.

- Нерекурсивные - для их получения необходим генератор случайных чисел.

Если не использовать понятие случайности, то все последовательности - рекурсивные, а значит, их множество счетно. Верно? Возможность же существования случайных (а не псевдослучайных) величин - далеко не очевидна.

 Профиль  
                  
 
 
Сообщение26.01.2009, 08:32 
Заслуженный участник
Аватара пользователя


21/12/05
5904
Новосибирск
Nxx в сообщении #181250 писал(а):
Если не использовать понятие случайности, то все последовательности - рекурсивные, а значит, их множество счетно.


Если не использовать понятие иррациональности, то все числа рациональны. :D

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

Если уж речь зашла о рекурсивности, то можете посмотреть также в статье об Алане Тьюринге:

В ней найдёте строку КАНТОРОВСКИЙ ДИАГОНАЛЬНЫЙ ПРОЦЕСС

 Профиль  
                  
 
 
Сообщение26.01.2009, 09:14 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Nxx в сообщении #181245 писал(а):
Если так, то как построить такое множество без генератора случайных чисел - не представляю.
А с генератором - представляете, провокационный Вы наш?

 Профиль  
                  
 
 
Сообщение26.01.2009, 09:32 


13/09/08
3
Nxx в сообщении #181250 писал(а):
Как это доказать?

Предположим, что множество X всех подмножеств бесконечного множества N счетно. Тогда существует биекция между X и N.

Рассмотрим множество A, состоящее из всех элементов из N, которые не содержатся в сопоставленном им подмножестве X. Так как $A\subset X$, то существует $a\in N$, сопоставленный A. Зададимся вопросом: $a\in A$ или $a\notin A$? Оба случая невозможны по определению A. Противоречие (если принимаем закон исключенного третьего, конечно).

 Профиль  
                  
 
 
Сообщение26.01.2009, 09:32 
Заслуженный участник


05/06/08
1097
Какая все-таки зловредная тема, эта "счетность" множества вещественных чисел... :(

 Профиль  
                  
 
 
Сообщение26.01.2009, 09:33 


20/07/07
834
Так. Вот тут упомянули диагональный процесс Кантора.

В частности, он описан тут: http://www.ega-math.narod.ru/Singh/Cantor.htm

Но с этим процессом возникает новый вопрос.

==========

Кантор предполагает, что если мы пронумеровали все действительные числа, у нас каждому номеру соответствует какое-то число. Но на самом деле ситуация такова:

1. Мы можем пронумеровать все алгоритмы - их множество счетно.

2. Некоторые алгоритмы задают числа - мощность множества таких чисел явно меньше или равна мощности множества алгоритмов.

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

Какие из этого выводы?
1. Количество вычислимых чисел меньше или равно количеству всвозможных алгоритмов, то есть, количеству натуральных чисел.
2. Но мощность натуральных чисел не больше мощности вычислимых чисел, так как любое натуральное число является вычислимым.
3. Значит, мощности этих множеств равны.
4. Но сделать взаимно-однозначное соответствие между натуральными числами и вычислимыми числами мы не можем, так как не знаем заранее, какие из алгоритмов расходятся.
5. Соответственно, не можем и применить диагональный процесс Кантора.

Таким образом, мощность множества вычислимых чисел и мощность множества натуральных чисел равны, но взаимно-однозначного соответствия сделать невозможно, я прав? Если не прав, поправьте. Раз взаимно-однозначного соответствия сделать нельзя, то и построить канторовский контрпример тоже нельзя.

 Профиль  
                  
 
 
Сообщение26.01.2009, 09:45 
Заслуженный участник
Аватара пользователя


21/12/05
5904
Новосибирск
Nxx в сообщении #181269 писал(а):
Таким образом, мощность множества вычислимых чисел и мощность множества натуральных чисел равны

Равны.
Nxx в сообщении #181269 писал(а):
но взаимно-однозначного соответствия сделать невозможно

А это ещё почему? Как раз напротив - можно.
Скорее всего где-то на это уже отвечали.
Множество всех действительных чисел и множество вычислимых чисел - это у Вас одно и то же?
Что в таком случае означает термин вычислимое число?

 Профиль  
                  
 
 
Сообщение26.01.2009, 09:46 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Nxx писал(а):
то и построить канторовский контрпример тоже нельзя.

Что подразумеваете под "канторовский контрпример построить нельзя"?

Можно предположить, что вещественных чисел счетное множество? Можно!
Можно показать, что такое предположение противоречиво? Можно!

Так чего же нельзя? Если Вам чего-то не хватает, то как эта нехватка подрывает доказательство Кантора?

 Профиль  
                  
 
 
Сообщение26.01.2009, 09:55 


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

Цитата:
Что в таком случае означает термин вычислимое число?

По-английски это называется computable number: http://en.wikipedia.org/wiki/Computable_number . Синоним - рекурсивное.

Цитата:
А это ещё почему? Как раз напротив - можно.
Скорее всего где-то на это уже отвечали.


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

 Профиль  
                  
 
 
Сообщение26.01.2009, 10:15 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Nxx, у Вас какая-то изумительная каша в голове. Кантор не знал слов "вычислимость", "алгоритм", "генератор случайных чисел". Вот и Вы их тоже пока отложите в сторону.

 Профиль  
                  
 
 
Сообщение26.01.2009, 10:16 


20/07/07
834
Цитата:
Можно предположить, что вещественных чисел счетное множество? Можно!
Можно показать, что такое предположение противоречиво? Можно!


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

Что ж, из этого следует, что взаимно однозначного соответствия сделать нельзя, тем не менее, мощность множества вычислимых чисел не превосходит мощность множества натуральных чисел, так как все алгоритмы (даже "плохие") можно пронумеровать.

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

 Профиль  
                  
 
 
Сообщение26.01.2009, 10:24 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Зачем Вы устраиваете ПРОВОКАЦИИ? Пробуете себя в роли тролля, или тролльскую квалификацию повышаете? В заголовке Вы пишете: "Множество вещественных чисел счетно?".
А потом плавненько подменяете тему на обсуждение конструктивизма.
Нехорошо...с....

 Профиль  
                  
 
 
Сообщение26.01.2009, 10:25 
Заслуженный участник
Аватара пользователя


21/12/05
5904
Новосибирск
Nxx в сообщении #181283 писал(а):
И нет никакого доказательства, что могут существовать невычислимые вещественные числа, если не использовать оракул/генератор случайных чисел (возможность существования которого неинтуитивна).

Как раз теорема Кантора и указывает на их существование. А какое иное доказательство Вы примете - явный алгоритм, вычисляющий невычислимое число?

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

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



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

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


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

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