ddn писал(а):
А Вы занимаетесь вычислимостью на трансфинитных ординалах, или только на
? Меня интересует вопрос
категоричности вычислений на таких ординалах (без оракулов, конечно), а именно, категоричности
результатов доказательств в тех или иных теориях. Например, вопрос о непротиворечивости арифметики второго порядка и, скажем, теории
будет конечно разрешим на трансфинитных ординалах (перебором счетного числа всех доказательств), но будет ли результат
независим от выбранного ординала и модели вычислений? (не используя оракулы)
Честно говоря, плохо понял, что Вы от меня хотите услышать.
Классическую вычислимость (машины Тьюринга с оракулами и без, частично рекурсивные функции и т. п.) знаю, это как раз то, чем я занимаюсь. Если Вы это понимали под вычислимостью только на
, то да, я занимаюсь вычислимостью на
. Хотя в рамках именно этой самой вычислимости введено понятие конструктивного ординала, ординала
, так что мы имеем дело не только с
Есть ещё вычислимость на допустимых множествах (вычислимость задаётся через
-определимость). Этот подход и классический тесно связаны, но сигма-определимость позволяет задавать понятие вычислимости на произвольных структурах. В частности, на произвольных ординалах. Но боюсь, что Вас интересует не это.
Есть ещё различные подходы к вычислимости на
, на различных топологических пространствах. Довольно популярная тема... Но боюсь, что Вы что-то совершенно другое имели в виду.
Что такое "категоричность вычислений" и "категоричность результатов доказательств" я не знаю. Никогда не встречался с этими терминами. В теории моделей есть такое понятие, как категоричная теория, но это, как мне кажется, совсем не то, что Вас интересует.
Что касается арифметики второго порядка --- тоже не понял вопроса. Исчисление второго порядка не полно и принципиально не пополняемо (по крайней мере, эффективным способом), так что неясно, что там понимать под противоречивостью.
Есть доказательства непротиворечивости некоторой подтеории в арифметике
первого порядка, использующие трансфинитную индукцию по ординалу
. Я в подобные вещи никогда не углублялся, но боюсь, с исчислениями второго порядка и с вычислимостью это слабо связано. Хотя, возможно, и ошибаюсь.
В-общем, буду благодарен, если Вы зададите более конкретные вопросы.
Добавлено спустя 12 минут 1 секунду:Someone писал(а):
Хочется Вам называть конечные ординалы натуральными числами - на здоровье. Но не требуйте этого от специалиста в теории чисел, которому, может быть, удобнее не считать ноль натуральным числом.
Да я и не требую
На самом деле я сам не сторонник оголтелого формализма. Но всё же, если аппелировать к нему...
Все объекты в математике суть множества. Математика работает только с множествами, ничего другого у них просто нет. Числа вводятся так:
Сначала определяем натуральные числа как конечные ординалы. Затем доказываем для них (в ZFC) принцип индукции. Вводим по индукции сложение и умножение. Определяем через эти операции одно отношение эквивалентности на натуральных числах, классы эквивалентности называем целыми числами. На целых числах вводим операции через операции над натуральными. Определяем на
отношение эквивалентности, получаем
. На
вводим "сечения" (по Дедекинду или чуть улучшенным способом), определяем
. И так далее.
По моему, это всё бурбаки аккуратно проделали и где-то у них это есть. Или даже это было всё сделано до бурбаков.
Если есть желание, я все эти конструкции могу подробно расписать. Но это долго... Я это сделаю, если для Вас это действительно важно. Если нет, то предлагаю спор завершить. Вопрос, с какого числа следует начинать натуральный ряд не столь уж принципиален, тут об этом, по-моему, все мало-мальски продвинутые люди твердят.