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

[Nxx]

Цитата:

Функция $f$, естественно, не вычислима (это можно доказать. сведя к ней проблему остановки или проблему равенства конструктивных действительных чисел). Однако в рамках классической математики она построена совершенно законными методами (и даже без использования аксиомы выбора). Какие тут могут быть вопросы, не понимаю!

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

[ИСН]

(продолжая своё)
Альтернатива состоит в том, чтобы не трогать Кантора, а учить сразу конструктивизм, ибо все практически важные результаты, кажется, в нём будут, эээ, эквивалентны. Но тогда это надо было начинать не здесь, а раньше, с логики. Они же осьминоги, у них логика состоит из "Да", "Нет" и "Хрен построишь".
Upd. Вот и понятие вычислимости - оно из той, из осьминожьей вселенной, а Вы его тянете в эту.

[PAV]

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

так как он в неявном виде предполагает, что данная биекция - вычислимая.

Нет, не предполагает.

[Профессор Снэйп]

ИСН писал(а):

Upd. Вот и понятие вычислимости - оно из той, из осьминожьей вселенной, а Вы его тянете в эту.

Не совсем верно. Понятие вычислимости вполне уютно существует в нормальной вселенной, как некоторая её часть. А вот когда мы замыкаемся только на вычислимом и отказываемся признавать то, что невычислимое имеет право на существование, вот тогда вселенная становится "осьминожьей"

Добавлено спустя 2 минуты 23 секунды:

PAV писал(а):

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

так как он в неявном виде предполагает, что данная биекция - вычислимая.

Нет, не предполагает.

+1 Действительно не предполагает.

Добавлено спустя 7 минут 27 секунд:

Вообще, если вдуматься, то у конструктивистов все множества исчерпываются подмножествами натурального ряда. При этом, конечно, натуральные числа могут пониматься как "коды" более сложных объектов, например, как номера программ для машины Тьюринга и т. п.

В этом плане актуально бесконечное множество = рекурсивное бесконечное множество и потенциально бесконечное множество = бесконечное рекурсивно перечислимое множество.

Я когда-то очень давно (ещё на 4-ом курсе) писал реферат по конструктивизму и работам Маркова. Мысли у меня тогда были очень незрелые, сейчас бы я написал всё по другому. Но кое-что я тогда, как мне кажется, всё-таки ухватил. Если кому-то интересно, могу выложить реферат в сеть.

[Nxx]

Цитата:

+1 Действительно не предполагает.

Но ведь он использует результаты, полученные через применение этой невычислимой функции. Он предполагает, если множества равномощны, то можно построить биекцию. Но ведь мы знаем, что это не всегда так!

Цитата:

Если кому-то интересно, могу выложить реферат в сеть.

Конечно, интересно!

[PAV]

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

Он предполагает, если множества равномощны, то можно построить биекцию.

Еще раз повторяю:

"равномощны" $=$ "существует биекция"

"существует" $\ne$ "можно построить".

[Nxx]

Цитата:

"равномощны" $=$ "существует биекция"

"существует" $\ne$ "можно построить".

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

[PAV]

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

Ведь она используется в построении числа-контрпримера

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

[Профессор Снэйп]

Nxx писал(а):

Конечно, интересно!

http://www.nsu.ru/education/podzorov/Referat1.doc
http://www.nsu.ru/education/podzorov/Referat2.doc

Наслаждайтесь. Первый мне нравится больше, хотя и был написан раньше.

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

[Nxx]

Кстати, по-моему, логика "да", "нет" и "недоказуемо" вполне естественна, особенно учитывая наличие теоремы Гёделя. Разве не так? Как можно париписывать истинность или ложность утверждениям, про которые доказано, что их истинность никогда не будет ни доказана, ни опровергнута?

[ИСН]

Снова здоро́во. "Розу белую с чёрной жабой я хотел на земле повенчать".
А сама эта теорема, по-вашему, в какой логике доказана? А?

[Nxx]

ИСН писал(а):

Снова здоро́во. "Розу белую с чёрной жабой я хотел на земле повенчать".
А сама эта теорема, по-вашему, в какой логике доказана? А?

Понятия не имею. А что, чтобы допустить, что бывают принципиально недоказумые утверждения, связанные с бесконечными множествами, про которые нельзя сказать ни "да", ни "нет", нужна какая-то особая логика?

[Профессор Снэйп]

PAV писал(а):

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

На мой взгляд PAV, как всегда, очень точно ухватил суть.

Рассмотрим это на наиболее выпуклом примере: теореме Кантора. Под $\mathcal{P}(X)$ понимается множество всех подмножеств множества $X$.

Теорема $|X| \neq |\mathcal{P}(X)|$ для любого множества $X$.

Доказательство Предположим, что $|X| = |\mathcal{P}(X)|$. Тогда, по определению, существует некоторая биекция $f$ их $X$ на $\mathcal{P}(X)$. Рассмотрим множество

$$ R = \{ x \in X : x \not\in f(x) \}, $$

являющееся подмножеством $X$, то есть элементом $\mathcal{P}(X)$, и существующее по аксиоме выделения. Так как $f$ биекция, то $R = f(r)$ для некоторого $r \in X$. Теперь если $r \in R$, то $r \in f(r)$ и $r \not\in R$ по определению $R$. Если же $r \not\in R$, то $r \not\in f(r)$ и $r \in R$ опять же по определению $R$. Противоречие. $\square$

Здесь мы, конечно, "строим" в некотором смысле множество $R$, но это "построение" опирается на аксиоматику теории множеств и не привлекает никаких эффективных методов. Просто выписываем некоторую последовательность математических символов, задающую множество в стандартной нотации, а затем, ссылаясь на аксиомы теории множеств, выводим из них, что эта запись действительно задаёт множество корректным образом. О вычислимости или невычислимости не идёт никакой речи!

А теперь, если вдуматься, то можно понять, что это доказательство в случае $X = \mathbb{N}$ фактически доказывает несчётность отрезка $[0,1]$ действительных чисел самым что ни на есть классическим диагональным методом, заключающемся в выписывании пронумерованного списка действительных чисел и построении числа, $n$-ый разряд которого отличается от $n$-го разряда в числе под номером $n$. Действительно, каждое число из $[0,1]$ можно задать в виде бесконечной двоичной дроби, то есть в виде последовательности нулей и единиц, а последовательность нулей и единиц можно отождествлять с подмножеством натурального ряда, состоящим в точности из таких натуральных $n$, что на $n$-ом месте бесконечной двоичной последовательности стоит единица. Когда мы устанавливаем $n$-ый разряд строящегося числа отличным от $n$-го разряда числа под номером $n$, мы фактически включаем число $n$ в строящееся подмножество тогда и только тогда, когда оно не включено в $n$-ое подмножество.

Добавлено спустя 6 минут 19 секунд:

Nxx писал(а):

Кстати, по-моему, логика "да", "нет" и "недоказуемо" вполне естественна, особенно учитывая наличие теоремы Гёделя.

Да отстаньте Вы уже от теоремы Гёделя. Она вообще не про то. Понимаете: НЕ ПРО ТО! Не имеет никакого отношения к предмету данной дискуссии!

Цитата:

А сама эта теорема, по-вашему, в какой логике доказана? А?

Замечательный вопрос. Я бы добавил к нему следующее: и про какую логику она доказана? А?

[Nxx]

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

То есть, я не хочу сказать, что такая аксиоматика неправомерна, просто она имеет нулевую практическую ценность

[PAV]

Математика не является наукой о природе. Математика изучает абстрактные конструкции.