В какой степени математика Реалов может быть применена к вычислимым Реалам?

16

Существует ли общая теорема, которая при надлежащей дезинфекции утверждает, что наиболее известные результаты, касающиеся использования действительных чисел, могут фактически использоваться при рассмотрении только вычислимых вещественных чисел? Или существует правильная характеристика результатов, которые остаются действительными при рассмотрении только вычислимых действительных значений? Дополнительный вопрос заключается в том, можно ли доказать результаты, касающиеся вычислимых вещественных чисел, не считая все действительные или что-либо, что не вычислимо. Я имею в виду конкретно исчисление и математический анализ, но мой вопрос никоим образом не ограничен этим.

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

Тогда мой вопрос, возможно, можно сформулировать так: есть ли характеристика результатов, которая будет применяться в абстрактной теории действительных веществ, когда они доказаны для традиционных действительных чисел. И могут ли эти результаты быть доказаны непосредственно в абстрактной теории, без учета традиционных истин.

Я также заинтересован в понимании того, как и когда эти теории истин расходятся.

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

Babou
источник

Ответы:

16

Вещественные числа могут быть охарактеризованы несколькими способами, давайте поработаем с полем Коши, полностью упорядоченным по Архимеду . (Мы должны быть немного осторожны, как именно мы это говорим, см. Определение 11.2.7 и определение 11.2.10 книги HoTT .)

Следующая теорема справедлива в любом топосе (модель интуиционистской логики высшего порядка):

Теорема: существует полное по Коши архимедово упорядоченное поле, и фактически любые два таких поля канонически изоморфны.

Более того, в интуиционистской логике (не путать с интуиционизмом ) мы можем провести большой реальный анализ (последовательности и пределы, производные, интегралы, непрерывность, равномерная непрерывность и т. Д.), Который применим в любом топосе. Если мы возьмем топос множеств, мы получим обычный реальный анализ. Взяв другой топос, мы получаем другой вид реального анализа - и есть топос, который дает точно вычислимый реал и вычислимый реальный анализ.

Это, конечно, эффективный топос , в котором действительные числа являются вычислимыми действительными числами (говоря неопределенно, причина этого в том, что эффективный топос построен таким образом, что все в нем автоматически вычислимо). Ответ на ваш вопрос

Определения, конструкции и теоремы в интуитивистском реальном анализе автоматически переводятся в определения, конструкции и теоремы о вычислимых вещественных числах, когда мы интерпретируем их в эффективном топосе.

е:[0,1]р

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

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

Я пытался объяснить это однажды в заметках «Реализуемость как связь между вычислимой и конструктивной математикой» , а до этого - в моей докторской диссертации. тезис .

Андрей Бауэр
источник
[0,1]
3
Нет, нет, нужно различать интуиционистскую логику и интуиционизм Брауэра[0,1][0,1][0,1]
Андрей Бауэр
1
[0,1][0,1]
Я добавил примечание о том факте, что интуиционистская логика - это не то же самое, что интуиционизм. Кроме того, страница Википедии об интуиционистской логике ужасна.
Андрей Бауэр
1
@Kaveh: да, мы могли бы пожелать лучшей терминологии ...
Андрей Бауэр