Существует ли биекция между вычислимыми числами и нат.?

[Nxx]

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

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

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

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

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

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

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

[code248]

Nxx в сообщении #181245 писал(а):

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

Почему?

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

[Nxx]

Цитата:

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

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

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

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

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

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

[bot]

Nxx в сообщении #181250 писал(а):

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

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

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

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

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

[Brukvalub]

Nxx в сообщении #181245 писал(а):

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

А с генератором - представляете, провокационный Вы наш?

[code248]

Nxx в сообщении #181250 писал(а):

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

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

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

[id]

Какая все-таки зловредная тема, эта "счетность" множества вещественных чисел...

[Nxx]

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

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

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

==========

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

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

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

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

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

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

[bot]

Nxx в сообщении #181269 писал(а):

Таким образом, мощность множества вычислимых чисел и мощность множества натуральных чисел равны

Равны.

Nxx в сообщении #181269 писал(а):

но взаимно-однозначного соответствия сделать невозможно

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

[TOTAL]

Nxx писал(а):

то и построить канторовский контрпример тоже нельзя.

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

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

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

[Nxx]

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

Цитата:

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

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

Цитата:

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

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

[ИСН]

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

[Nxx]

Цитата:

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

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

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

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

[Brukvalub]

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

[bot]

Nxx в сообщении #181283 писал(а):

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

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