Философская интерпретация вычислимости конечной математической задачи

Я думаю, что существует довольно много недоразумений в используемых терминах.

Есть некоторые математики, которые не думают, что числа, превышающие определенный размер, не существуют. Физически вселенная, по-видимому, состоит из конечного числа частиц, поэтому существует реальная верхняя граница размера чисел, которые мы когда-либо можем записать в десятичной системе счисления . Возможно, мы даже не сможем выразить верхнюю границу, но она есть. Если это критерий «знания числа», то даже Бог не может записать ответ, не увеличив сначала количество частиц во Вселенной. Но это не значит, что ответ не определен, это другое понятие. Наибольшее простое число меньше 2^1000, безусловно, не записывается в десятичном виде, но я только что определил его, и каждый математик согласен с тем, что такое число существует, за исключением ультрафинитистов, которые считают, что число существует только в том случае, если его можно записать цифра за цифрой. . Последовательность, на которую вы ссылаетесь, является одним из примеров этого типа, поэтому заявление доктора Z должно быть чем-то вроде шутки, если только он не ультрафинитист, как Дорон Зейлбергер.

Тем не менее, существуют определенные утверждения, выраженные в арифметике Пеано (PA), которые независимы от PA в том смысле, что существуют разные модели PA, в которых эти утверждения имеют разное истинностное значение. (Модель PA — это мир, который удовлетворяет всем аксиомам PA.) Можно принять теорию множеств Цермело-Франкеля (ZF), которая является более сильной теорией, в которой существует только одна модель PA из-за аксиомы индукция. Обратите внимание, что «теория» здесь не имеет ничего общего с научными «теориями».

Проблема в том, что ZF по-прежнему является теорией первого порядка (количественно определяющей только отдельные объекты в своей области), и, следовательно, по теореме Гёделя логическое следствие в ZF эквивалентно доказуемости в ZF. Поскольку утверждения в ZF могут быть закодированы с использованием натуральных чисел, а этапы доказательства могут быть закодированы с помощью определенных элементарных свойств теории чисел, таких как делимость, а затем может быть закодировано существование доказательства, мы можем затем закодировать утверждение о непротиворечивости самого ZF. как один оператор в PA. Но это утверждение будет независимым из-за аналогичного кодирования предложения, которое должно означать «Это утверждение недоказуемо». (Самоссылка разрешена кодировкой.) Если это доказуемо, то оно противоречит самому себе. Если его отрицание доказуемо, то оно доказуемо и, таким образом, возникает то же самое противоречие.

Таким образом, в математике нет конкурирующих гипотез, в отличие от науки. Каждое утверждение в его полном контексте либо истинно, либо ложно, либо независимо. Можно выбрать разные рамки, которые могут изменить истинностное значение утверждения, но конфликта не будет. Это просто означает, что у нас могут быть три схемы A, B, C, такие, что утверждение истинно в A, ложно в B и независимо в C. Если вы платоник, вы можете сказать, что не более одной из рамок верна. .

Обратите внимание, что мы не можем ввести Бога во все это, не уточнив, что именно мы подразумеваем под его знанием. Просто нелепо предполагать, что ZF может смоделировать весь мир, и даже натуральные числа являются идеализированными понятиями, которых на самом деле не существует в реальном мире. Но если вы говорите, что хотите, чтобы Бог сказал вам, является ли какое-то утверждение истинным или ложным или неразрешимым в какой-либо теории, тогда, если Бог знает все, тогда, безусловно, он сможет ответить на этот вопрос. Но если вам нужно точное числовое значение, о котором вы спрашивали, то как вы ожидаете, что он передаст ответ?

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

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