В математической логике и теории множеств , порядковое коллапса функции (или функции проекции ) представляет собой метод для определения ( обозначений для) некоторых рекурсивных больших счетных порядковых , принцип которого давать имена некоторому порядковым гораздо больше , чем тот , который определяется, возможно , даже большие кардиналы (хотя их можно заменить рекурсивно большими порядковыми числами за счет дополнительных технических трудностей), а затем «свернуть» их до системы обозначений для искомого порядкового числа. По этой причине функции свертывания порядковых номеров описываются как непредсказуемый способ именования порядковых номеров.
Детали определения порядковых функций сворачивания различаются и усложняются по мере определения больших порядковых номеров, но типичная идея состоит в том, что всякий раз, когда в системе обозначений «заканчивается топливо» и не может быть назван определенный порядковый номер, используется гораздо больший порядковый номер принесено «сверху», чтобы дать название этой критической точке. Пример того, как это работает, будет подробно описан ниже для порядковой функции сворачивания, определяющей порядковый номер Бахмана – Ховарда (т. Е. Определяющей систему обозначений вплоть до порядкового номера Бахмана – Ховарда).
Использование и определение порядковых функций схлопывания неразрывно связано с теорией порядкового анализа , поскольку большие счетные порядковые числа, определенные и обозначаемые данным коллапсом, используются для описания теоретико-порядковой силы некоторых формальных систем , обычно [1] [2 ] ] подсистема анализа (такие , как те, в свете обратной математики ), расширение теории множеств Крипки-Platek , Bishop -Style систем конструктивной математики или Мартин-LOF -Style систем теории интуиционистском типа .
Порядковые функции сворачивания обычно обозначаются с использованием некоторой вариации греческой буквы ( psi ) или( тета ).
Пример, ведущий к порядковому номеру Бахмана – Ховарда
Выбор порядковой функции сворачивания, приведенный в качестве примера ниже, в значительной степени имитирует систему, введенную Бухгольцем [3], но для ясности изложения ограничивается сворачиванием одного кардинала. Подробнее о связи этого примера с системой Бухгольца будет сказано ниже .
Определение
Позволять стоять для первого несчетного порядкового номера , или, фактически, любой порядковый номер, который является ( -число и) гарантированно больше, чем все счетные ординалы, которые будут построены (например, порядковый номер Черча-Клини подходит для наших целей; но мы будем работать спотому что это позволяет удобно использовать слово countable в определениях).
Определим функцию (который будет неубывающим и непрерывным ), взяв произвольный порядковый к счетному порядковому номеру , рекурсивно на , следующим образом:
- Предполагать был определен для всех , и мы хотим определить .
- Позволять - набор порядковых номеров, сгенерированный, начиная с , , а также рекурсивно применяя следующие функции: порядковое сложение, умножение и возведение в степень, а также функцию , т. е. ограничение к ординалам . (Формально мы определяем и индуктивно для всех натуральных чисел и мы позволяем быть союзом для всех .)
- потом определяется как наименьший порядковый номер, не принадлежащий .
Более кратко (хотя и неясно):
- это наименьший порядковый номер, который не может быть выражен из , , а также используя суммы, произведения, экспоненты и сама функция (к ранее созданным порядковым номерам меньше, чем ).
Вот попытка объяснить мотивацию определения в интуитивно понятных терминах: поскольку обычных операций сложения, умножения и возведения в степень недостаточно для обозначения порядковых чисел очень далеко, мы пытаемся систематически создавать новые имена для порядковых чисел, выбирая первое, у которого еще нет имени, и всякий раз, когда у нас заканчивается имен, вместо того, чтобы придумывать их специальным образом или с использованием диагональных схем , мы ищем их в порядковых числах далеко за пределами тех, которые мы строим (за пределами, это); поэтому мы даем имена бесчисленным ординалам, и, поскольку в конце список имен обязательно является счетным, «свернет» их до счетных порядковых чисел.
Расчет значений
Чтобы уточнить, как функция может создавать обозначения для определенных порядковых чисел, теперь мы вычисляем его первые значения.
Предикативный старт
Сначала рассмотрим . Он содержит порядковые номера, , , , , , , , , , , , и так далее. Он также содержит такие порядковые номера, как, , , . Первый порядковый номер, которого он не содержит, - (что является пределом , , и так далее - меньше чем по предположению). Верхняя граница содержащихся в нем ординалов равна (предел , , и так далее), но это не так важно. Это показывает, что.
По аналогии, содержит порядковые числа, которые могут быть образованы из , , , и на этот раз также , используя сложение, умножение и возведение в степень. Он содержит все порядковые номера до но не последнее, так что . Таким образом, мы доказываем, что индуктивно на : доказательство работает, однако, только до тех пор, пока . Таким образом, у нас есть:
- для всех , где наименьшая фиксированная точка .
(Здесь функции - это функции Веблена, определенные начиная с.)
Сейчас но не больше, так как не могут быть построены с использованием конечных приложений и поэтому никогда не принадлежит набор для , а функция остается «застрявшим» на на некоторое время:
- для всех .
Первые предварительные значения
Очередной раз, . Однако когда мы переходим к вычислениям, что-то изменилось: с был («искусственно») добавлен ко всем , нам разрешено принимать значение в процессе. Так содержит все порядковые числа, которые могут быть построены из , , , , то функционировать до и на этот раз также сам, используя сложение, умножение и возведение в степень. Наименьший порядковый номер не в является (наименьший -число после ).
Мы говорим, что определение и следующие значения функции такой как являются непредсказуемыми, потому что в них используются порядковые числа (здесь) больше, чем определяемые (здесь ).
Ценности до порядкового номера Фефермана – Шютте
Дело в том, что остается верным для всех (отметим, в частности, что : но с тех пор порядковый был построен, ничто не мешает выйти за рамки этого). Однако на (первая фиксированная точка вне ), построение снова останавливается, так как не может быть построен из меньших порядковых чисел и конечным применением функция. Итак, у нас есть.
Те же рассуждения показывают, что для всех , где перечисляет неподвижные точки а также первая неподвижная точка . Тогда у нас есть.
Опять же, мы видим, что в течение некоторого времени: это остается верным до первой фиксированной точки из , который является порядковым номером Фефермана – Шютте . Таким образом, - порядковый номер Фефермана – Шютте.
За пределами порядкового номера Фефермана – Шютте
У нас есть для всех где следующая фиксированная точка . Так что если перечисляет рассматриваемые неподвижные точки (которые также можно отметить используя многозначные функции Веблена) имеем , до первой фиксированной точки принадлежащий сам, который будет (и первая фиксированная точка принадлежащий функции будут ). Таким образом:
- - порядковый номер Аккермана (диапазон обозначений определяется предикативно),
- - «малый» ординал Веблена (диапазон обозначений предикативно с использованием конечного числа переменных),
- - «большой» ординал Веблена (диапазон обозначений предикативно с использованием трансгранично-но-предикативно-многих переменных),
- Лимит из , , и т. д., это порядковый номер Бахмана – Ховарда : после этого наша функция является константой, и мы не можем идти дальше данного определения.
Порядковые обозначения до порядкового номера Бахмана – Ховарда
Теперь мы более систематически объясним, как Функция определяет обозначения для ординалов вплоть до ординала Бахмана – Ховарда.
Замечание о базовых представлениях
Напомним, что если порядковый номер, который является степенью (Например сам, или , или же ), любой порядковый можно однозначно выразить в виде , где натуральное число, ненулевые порядковые числа меньше, чем , а также являются порядковыми числами (мы допускаем ). Эта «базапредставление »является очевидным обобщением нормальной формы Кантора (что имеет место). Конечно, вполне может быть, что это выражение неинтересно, т. Е., но в любом другом случае все должно быть меньше ; также может быть случай, что выражение тривиально (т. е., в таком случае а также ).
Если порядковый номер меньше, чем , то его база представление имеет коэффициенты (по определению) и показатели (из-за предположения ): следовательно, можно переписать эти показатели в базе и повторяйте операцию до тех пор, пока процесс не завершится (любая убывающая последовательность порядковых номеров конечна). Полученное выражение назовем повторяющейся базойпредставление ои различные коэффициенты, участвующие (в том числе в качестве показателей), части представления (все они), или, для краткости, - кусочки .
Некоторые свойства
- Функция неубывающая и непрерывная (это более или менее очевидно из ее определения).
- Если с участием тогда обязательно . Действительно, нет порядкового номера с участием может принадлежать (в противном случае его изображение , который будет принадлежать - невозможно); так закрыто всем, под чем это закрытие, поэтому они равны.
- Любое значение взято является -число (т. е. фиксированная точка ). В самом деле, если бы это было не так, то, записав его в нормальной форме Кантора , его можно было бы выразить с помощью сумм, произведений и возведения в степень от элементов, меньших его, следовательно, в, так что это было бы в Противоречие.
- Лемма: Предположим является -число и порядковый номер такой, что для всех : тогда -частей (определенных выше ) любого элемента меньше чем . Действительно, пусть быть набором ординалов, все из которых - штук меньше, чем . потом закрывается при сложении, умножении и возведении в степень (потому что является -число, поэтому порядковые числа меньше его закрываются при сложении, умножении и возведении в степень). А также также содержит все для по предположению, и он содержит , , , . Так, который должен был быть показан.
- В предположении предыдущей леммы (действительно, лемма показывает, что ).
- Любой -число меньше некоторого элемента в диапазоне сам находится в диапазоне (это, не пропускает нет -номер). Действительно: если является -число не больше диапазона , позволять - точная верхняя граница такой, что : тогда по вышеизложенному мы имеем , но противоречило бы тому факту, что является не менее верхняя граница - так.
- В любое время , набор состоит именно из этих порядковых номеров (меньше, чем ) все чьи - штук меньше, чем . В самом деле, мы знаем, что все порядковые числа меньше, чем, следовательно, все ординалы (меньше, чем ) чей - штук меньше, чем , находятся в . Наоборот, если мы предположим для всех (другими словами, если наименее возможно с ) лемма дает желаемое свойство. С другой стороны, если для некоторых , то мы уже отмечали и мы можем заменить по крайней мере с .
Порядковые обозначения
Используя приведенные выше факты, мы можем определить (канонические) порядковые обозначения для каждого меньше порядкового номера Бахмана – Ховарда. Сделаем это индукцией по.
Если меньше чем , мы используем итеративную нормальную форму Кантора . В противном случае существует наибольшая-номер меньше или равно (это потому, что набор -числа закрывается): если то по индукции мы определили обозначение для и база представление дает один для Итак, мы закончили.
Остается разобраться со случаем, когда является -число: мы утверждали, что в этом случае мы можем написать для некоторых (возможно, бесчисленных) порядковых : позволять - максимально возможный такой порядковый номер (который существует снепрерывно). Используем итеративную базу представление : осталось показать, что каждый кусок этого представления меньше, чем (поэтому мы уже определили для него обозначения). Если это не так, то по показанным нами свойствам не содержит ; но потом (они закрываются при тех же операциях, так как значение в никогда не могут быть взяты), так что , что противоречит максимальности .
Примечание . На самом деле, мы определили канонические обозначения не только для ординалов ниже ординала Бахмана – Ховарда, но и для некоторых несчетных ординалов, а именно тех, чьи-пьесы меньше порядкового номера Бахмана – Ховарда (а именно: записать их в повторяющейся базе представление и использовать каноническое представление для каждого произведения). Это каноническое обозначение используется для аргументов функция (которая может быть бесчисленной).
Примеры
Для порядковых номеров меньше , определенное каноническое порядковое обозначение совпадает с повторной нормальной формой Кантора (по определению).
Для порядковых номеров меньше , обозначение совпадает с повторяющейся базой обозначение (сами пьесы записываются в повторяющейся нормальной форме Кантора): например, будет написано , или, точнее, . Для порядковых номеров меньше, аналогично пишем в повторяющейся базе а затем напишите части в повторяющейся базе (и запишите части этого в повторяющейся нормальной форме Кантора): так написано , или, точнее, . Таким образом, до, мы всегда используем максимально возможные -числовая база, дающая нетривиальное представление.
Помимо этого, нам может потребоваться выразить порядковые номера за пределами : это всегда выполняется в повторяющемся -базу, а сами части должны быть выражены с использованием максимально возможного -числовая база, дающая нетривиальное представление.
Обратите внимание, что пока равно порядковому номеру Бахмана – Ховарда, это не «каноническая нотация» в том смысле, который мы определили (канонические обозначения определены только для ординалов, меньших, чем ординал Бахмана – Ховарда).
Условия каноничности
Определенные таким образом обозначения обладают тем свойством, что всякий раз, когда они вкладываются функции, аргументы «внутреннего» функции всегда меньше, чем у «внешней» (это следствие того, что - кусочки , где максимально возможное такое, что для некоторых -номер , все меньше, чем , как мы показали выше). Например, не встречается в качестве обозначения: это четко определенное выражение (и оно равно поскольку постоянно между а также ), но это не обозначение, полученное с помощью описанного нами индуктивного алгоритма.
Каноничность можно проверить рекурсивно: выражение является каноническим тогда и только тогда, когда оно является повторной канторовской нормальной формой ординала, меньшего, чем , или итерированная база представление, все части которого каноничны, для некоторых где сам написан в повторяющейся базе представление, все части которого каноничны и меньше . Порядок проверяется лексикографической проверкой на всех уровнях (с учетом того, что больше любого выражения, полученного , а для канонических значений больше всегда превосходит меньшие или даже произвольные суммы, произведения и экспоненты меньшего).
Например, является каноническим обозначением ординала, который меньше ординала Фефермана – Шютте: он может быть записан с использованием функций Веблена как .
Что касается порядка, можно отметить, что (порядковый номер Фефермана – Шютте) намного больше, чем (так как больше, чем ничего), и сам по себе намного больше, чем (так как больше, чем , поэтому любое выражение сумма-произведение или экспоненциальное, включающее и меньшее значение останется меньше, чем ). По факту, уже меньше чем .
Стандартные последовательности для порядковых обозначений
Чтобы засвидетельствовать тот факт, что мы определили обозначения для ординалов ниже ординала Бахмана – Ховарда (которые все имеют счетную конфинальность ), мы могли бы определить стандартные последовательности, сходящиеся к любой из них (конечно, при условии, что это предельный ординал). Фактически, мы также определим канонические последовательности для некоторых несчетных ординалов, а именно для бесчисленных ординалов счетной конфинальности (если мы надеемся определить сходящуюся к ним последовательность ...), которые представимы (то есть все чьи-пьесы меньше порядкового номера Бахмана – Ховарда).
Более-менее очевидны следующие правила, кроме последнего:
- Во-первых, избавьтесь от (итерированной) базы представления: для определения стандартной последовательности, сходящейся к , где либо или же (или же , но см. ниже):
- если равно нулю, тогда и ничего не поделаешь;
- если равен нулю и преемник, то является преемником и ничего не поделаешь;
- если является пределом, возьмем стандартную последовательность, сходящуюся к и заменить в выражении элементами этой последовательности;
- если является преемником и это предел, перепишите последний член в виде и заменим экспоненту в последнем члене сходящимися к нему элементами фундаментальной последовательности;
- если является преемником и также перепишите последний член в виде и заменить последний в этом выражении сходящимися к нему элементами фундаментальной последовательности.
- Если является , затем возьмем очевидное , , , … Как фундаментальная последовательность для .
- Если тогда возьмем за фундаментальную последовательность для последовательность , , …
- Если тогда возьмем за фундаментальную последовательность для последовательность , , …
- Если где является предельным ординалом счетной конфинальности, определим стандартную последовательность для быть полученным путем применения к стандартной последовательности для (Напомним, что здесь непрерывно и возрастает).
- Остается разобраться со случаем, когда с участием порядковый номер неисчислимой cofinality (например,сам). Очевидно, нет смысла определять последовательность, сходящуюся кв таком случае; однако мы можем определить последовательность, сходящуюся к некоторому со счетной конфинальностью и такой, что постоянно между а также . Этот будет первой фиксированной точкой некоторой (непрерывной и неубывающей) функции . Чтобы его найти, примените те же правила (из базового представление ) как найти каноническую последовательность , за исключением того, что всякий раз, когда последовательность сходится к требуется (то, чего не может существовать), замените в вопросе, в выражении , автор (где является переменной) и выполнить повторную итерацию (начиная с скажем) функции : это дает последовательность , , … стремясь к , а каноническая последовательность для является , , … Если мы позволим th элемент (начиная с ) фундаментальной последовательности для обозначается как , то мы можем более четко сформулировать это с помощью рекурсии. Используя эти обозначения, мы видим, чтодовольно легко. Мы можем определить остальную часть последовательности с помощью рекурсии:. (Примеры ниже должны прояснить это.)
Вот несколько примеров из последнего (и наиболее интересного) случая:
- Каноническая последовательность для является: , , … Это действительно сходится к после которого постоянно до тех пор, пока .
- Каноническая последовательность для является: , , … Это действительно соответствует значению в после которого постоянно до тех пор, пока .
- Каноническая последовательность для является: , , … Это сходится к значению в .
- Каноническая последовательность для является , , … Это сходится к значению в .
- Каноническая последовательность для является: , , … Это сходится к значению в .
- Каноническая последовательность для является: , , … Это сходится к значению в .
- Каноническая последовательность для является: , , … Это сходится к значению в .
- Каноническая последовательность для является: , , …
Вот несколько примеров других случаев:
- Каноническая последовательность для является: , , , …
- Каноническая последовательность для является: , , , …
- Каноническая последовательность для является: , , , …
- Каноническая последовательность для является: , , …
- Каноническая последовательность для является: , , , …
- Каноническая последовательность для является: , , , …
- Каноническая последовательность для является: , , , …
- Каноническая последовательность для является: , , … (Это получено из фундаментальной последовательности для ).
- Каноническая последовательность для является: , , … (Это получено из фундаментальной последовательности для , который был приведен выше).
Хотя порядковый номер Бахмана – Ховарда сам по себе не имеет канонической нотации, также полезно определить для него каноническую последовательность: это , , …
Завершающий процесс
Начните с любого порядкового номера, меньшего или равного порядковому номеру Бахмана – Ховарда, и повторите следующий процесс, пока он не равен нулю:
- если порядковый номер является преемником, вычтите единицу (то есть замените его предыдущим),
- если это предел, замените его некоторым элементом определенной для него канонической последовательности.
Тогда верно, что этот процесс всегда завершается (поскольку любая убывающая последовательность порядковых чисел конечна); впрочем, как (но даже больше, чем для) игры Hydra :
- это может занять очень много времени,
- доказательство прекращения может быть недоступно для некоторых слабых систем арифметики.
Чтобы дать некоторое представление о том, как выглядит процесс, вот несколько его этапов: начиная с (маленький порядковый номер Веблена), мы могли бы спуститься к , оттуда до , тогда тогда тогда тогда тогда тогда тогда и так далее. Похоже, что выражения становятся все более сложными, тогда как на самом деле порядковые номера всегда уменьшаются.
Что касается первого утверждения, то для любого порядкового номера можно ввести меньше или равно порядковому номеру Бахмана – Ховарда , целочисленная функция который подсчитывает количество шагов процесса до завершения, если всегда выбирается 'й элемент из канонической последовательности (эта функция удовлетворяет тождеству ). потом может быть очень быстрорастущей функцией: уже по сути , функция сравнимо с функцией Аккермана , а также сравнимо с функцией Гудштейна . Если вместо этого мы создадим функцию, удовлетворяющую тождеству, поэтому индекс функции увеличивается, она применяется, затем мы создаем гораздо более быстрорастущую функцию: уже сопоставима с функцией Гудштейна, а сравнимо с функцией ДЕРЕВО .
Что касается второго утверждения, точную версию дает порядковый анализ : например, теория множеств Крипке – Платека может доказать [4], что процесс завершается для любого заданногоменьше, чем порядковый номер Бахмана – Ховарда, но он не может делать это равномерно, т. е. не может доказать завершение, начиная с порядкового номера Бахмана – Ховарда. Некоторые теории, такие как арифметика Пеано , ограничиваются гораздо меньшими порядковыми числами ( в случае арифметики Пеано).
Вариации на примере
Делаем функцию менее мощной
Поучительно (хотя и не совсем полезно) сделать менее мощный.
Если мы изменим определение выше, чтобы исключить возведение в степень из репертуара, из которого построено, то получаем (поскольку это наименьший порядковый номер, который не может быть построен из , а также используя только сложение и умножение), то и аналогично , пока мы не придем к фиксированной точке, которая будет нашим . Тогда у нас есть и так до тех пор, пока . Поскольку умножениеразрешено, мы все еще можем формировать а также и так далее, но наша конструкция на этом заканчивается, так как нет возможности добраться до или за : поэтому диапазон этой ослабленной системы обозначений составляет (значение то же самое в нашей более слабой системе, что и в нашей исходной системе, за исключением того, что теперь мы не можем выйти за ее пределы). Это даже не доходит до порядкового номера Фефермана – Шютте.
Если мы изменим определение еще несколько, чтобы разрешить только сложение в качестве примитива для построения, мы получаем а также и так до тех пор, пока И еще . Этот раз, и так до тех пор, пока и аналогично . Но на этот раз мы не можем идти дальше: поскольку мы можем только добавитьs, диапазон нашей системы составляет .
В обоих случаях мы обнаруживаем, что ограничение на ослабленную функция происходит не столько из операций, разрешенных для счетных ординалов, сколько из-за несчетных ординалов, которые мы позволяем себе обозначать.
Выходя за рамки порядкового номера Бахмана – Ховарда
Мы знаем это - порядковый номер Бахмана – Ховарда. Причина почему не больше, с нашими определениями, состоит в том, что нет обозначений для (не принадлежит для любой , это всегда его наименьшая верхняя граница). Можно попробовать добавитьфункция (или функции Веблена от такого количества переменных) к разрешенным примитивам, помимо сложения, умножения и возведения в степень, но это не уведет нас очень далеко. Чтобы создать более систематические обозначения для счетных ординалов, нам нужны более систематические обозначения для несчетных ординалов: мы не можем использовать сама функция, потому что она дает только счетные порядковые номера (например, является, конечно нет ), поэтому идея состоит в следующем:
- Позволять быть наименьшим порядковым номером, который не может быть выражен из всех счетных порядковых чисел, а также используя суммы, произведения, экспоненты и сама функция (к ранее созданным порядковым номерам меньше, чем ).
Здесь, - это новый порядковый номер, который гарантированно больше всех порядковых номеров, которые будут построены с использованием : опять же, давая а также работает.
Например, , и в более общем плане для всех счетных ординалов и даже за их пределами ( а также ): это справедливо до первой фиксированной точки вне принадлежащий функция, которая является пределом , и так далее. Помимо этого, у нас есть и это остается верным до тех пор, пока : точно так же, как и в случае , у нас есть а также .
В функция дает нам систему обозначений ( при условии, что мы можем каким-то образом записать все счетные ординалы!) для несчетных ординалов ниже, что является пределом , и так далее.
Теперь мы можем повторно ввести эти обозначения в исходный текст. функция, измененная следующим образом:
- это наименьший порядковый номер, который не может быть выражен из , , , а также используя суммы, произведения, экспоненты, функция, а сама функция (к ранее созданным порядковым номерам меньше, чем ).
Эта модифицированная функция совпадает с предыдущим до (включительно) - порядковый номер Бахмана – Ховарда. Но теперь мы можем выйти за рамки этого, и является (следующий -число после порядкового номера Бахмана – Ховарда). Мы сделали нашу систему вдвойне предикативной: для создания обозначений для счетных ординалов мы используем обозначения для определенных ординалов между а также которые сами определяются с помощью определенных порядковых номеров за пределами .
Вариант этой схемы, который не имеет большого значения при использовании только двух (или конечного числа) схлопывающихся функций, но становится важным для бесконечно многих из них, состоит в определении
- это наименьший порядковый номер, который не может быть выражен из , , , а также используя суммы, произведения, экспоненты и а также функция (для ранее построенных порядковых номеров меньше, чем ).
т.е. разрешить использование только для аргументов меньше чем сам. С этим определением мы должны написать вместо (хотя он по-прежнему равен , конечно, но теперь он постоянен, пока ). Это изменение несущественно, потому что, интуитивно говоря, функция сворачивает именованные порядковые номера за пределами ниже последнего, поэтому не имеет значения, вызывается непосредственно для порядковых номеров за пределами или на их изображении . Но позволяет определить а также путем одновременной (а не «нисходящей») индукции, и это важно, если мы собираемся использовать бесконечно много коллапсирующих функций.
В самом деле, нет причин останавливаться на двух уровнях: использование новые кардиналы таким образом, , мы получаем систему, по существу эквивалентную системе, введенной Бухгольцем [3], несущественная разница в том, что, поскольку Бухгольц используетпорядковые с самого начала, ему не нужно разрешать умножение или возведение в степень; также Бухгольц не вводит числа или же в системе, поскольку они также будут производиться функции: это делает всю схему более элегантной и лаконичной для определения, хотя и более сложной для понимания. Эта система также разумно эквивалентна более ранним (и гораздо более сложным для понимания) «порядковым диаграммам» Такеути [5] и функции Фефермана: их диапазон одинаковый (, Который можно было бы назвать порядковое Такеути-Феферман-Буххольц, и который описывает силу из Π 1 1 {\ displaystyle \ Pi _ {1} ^ {1}} -понимание плюс индукция стержня ).
"Нормальный" вариант
Большинство определений порядковых функций сворачивания, найденных в недавней литературе, отличаются от тех, которые мы дали, одним техническим, но важным способом, который делает их технически более удобными, хотя интуитивно менее прозрачными. Теперь объясним это.
Следующее определение (индукцией по ) полностью эквивалентна функции выше :
- Позволять - набор порядковых номеров, сгенерированный, начиная с , , , и все порядковые числа меньше рекурсивно применяя следующие функции: порядковое сложение, умножение и возведение в степень, а также функцию . потом определяется как наименьший порядковый номер такой, что .
(Это эквивалентно, потому что если наименьший порядковый номер не в , как мы изначально определили , то это также наименьший порядковый номер не в , а также описанные нами свойства подразумевают, что нет порядкового номера между инклюзивный и эксклюзивный принадлежит .)
Теперь мы можем внести изменения в определение, которое немного изменит его:
- Позволять - набор порядковых номеров, сгенерированный, начиная с , , , и все порядковые числа меньше рекурсивно применяя следующие функции: порядковое сложение, умножение и возведение в степень, а также функцию . потом определяется как наименьший порядковый номер такой, что а также .
Первые значения совпадают с таковыми из : а именно для всех где , у нас есть потому что дополнительное предложение всегда доволен. Но тут функции начинают различаться: в то время как функция «застревает» на для всех , функция удовлетворяет потому что новое состояние навязывает . С другой стороны, у нас все еще есть (так как для всех так что дополнительное условие не играет роли). Отметим, в частности, что, в отличие , не является ни монотонным, ни непрерывным.
Несмотря на эти изменения, функция также определяет систему порядковых обозначений вплоть до порядкового номера Бахмана – Ховарда: обозначения и условия каноничности немного отличаются (например, для всех меньше, чем обычное значение ).
Падение больших кардиналов
Как отмечалось во введении, использование и определение порядковых коллапсирующих функций тесно связано с теорией порядкового анализа , поэтому коллапс того или иного большого кардинала должен упоминаться одновременно с теорией, для которой он обеспечивает теоретико-доказательный анализ.
- Герхард Йегер и Вольфрам Полерс [6] описали коллапс недоступного кардинала, чтобы описать теоретико-порядковую силу теории множеств Крипке – Платека, дополненную рекурсивной недоступностью класса ординалов ( KPi ), которая также является теоретически эквивалентной [ 1] в-понимание плюс индукция стержня . Грубо говоря, этот коллапс можно получить, добавив саму функцию в список конструкций, к которым применяется сворачивающаяся система.
- Затем Майкл Ратьен [7] описал крах кардинала Мало, чтобы описать теоретико-порядковую силу теории множеств Крипке – Платека, дополненную рекурсивным махлонизмом класса ординалов ( KPM ).
- Ратьен [8] позже описал коллапс слабо компактного кардинала, чтобы описать теоретико-порядковую силу теории множеств Крипке – Платека, дополненную некоторыми принципами отражения (сосредоточив внимание на случае-отражение). Грубо говоря, это происходит путем введения первого кардинального который -гипер-Мало и добавление сама функция к разрушающейся системе.
- Ратьен начался [ когда? ] [9] расследование краха еще более крупных кардиналов с конечной целью достижения порядкового анализа-понимание (которое теоретически эквивалентно дополнению Крипке – Платека с помощью -разделение).
Заметки
- ^ a b Rathjen, 1995 (Булл. Символическая логика)
- ^ Каль, 2002 (синтезированный)
- ^ a b Бухгольц, 1986 (Ann. Pure Appl. Logic)
- ^ Rathjen, 2005 (Fischbachau слайды)
- ^ Такеути, 1967 (Ann. Math.)
- ↑ Jäger & Pohlers, 1983 (Bayer. Akad. Wiss. Math.-Natur. Kl. Sitzungsber.)
- ^ Rathjen, 1991 (Arch. Math. Логика)
- ^ Rathjen, 1994 (Ann. Pure Appl. Логика)
- ^ Rathjen, 2005 (Arch. Math. Логика)
Рекомендации
- Такеути, Гаиси (1967). «Доказательства непротиворечивости подсистем классического анализа». Анналы математики . 86 (2): 299–348. DOI : 10.2307 / 1970691 . JSTOR 1970691 .
- Егер, Герхард; Pohlers, Вольфрам (1983). "Eine beweistheoretische Untersuchung von (-CA) + (BI) und verwandter Systeme ». Bayerische Akademie der Wissenschaften. Mathematisch-Naturwissenschaftliche Klasse Sitzungsberichte . 1982 : 1–28.
- Бухгольц, Вильфрид (1986). "Новая система порядковых функций в теории доказательства" . Летопись чистой и прикладной логики . 32 : 195–207. DOI : 10.1016 / 0168-0072 (86) 90052-7 .
- Ратьен, Майкл (1991). "Теоретико-доказательный анализ КПМ". Архив математической логики . 30 (5–6): 377–403. DOI : 10.1007 / BF01621475 . S2CID 9376863 .
- Ратиен, Майкл (1994). "Теория доказательств отражения" (PDF) . Летопись чистой и прикладной логики . 68 (2): 181–224. DOI : 10.1016 / 0168-0072 (94) 90074-4 .
- Ратиен, Майкл (1995). «Последние достижения в порядковом анализе: Π 2 1 {\ displaystyle \ Pi _ {2} ^ {1}} -Ca и соответствующие системы» . Бюллетень символической логики . 1 (4): 468-485. DOI : 10,2307 / 421132 . JSTOR 421132 .
- Кале, Рейнхард (2002). «Математическая теория доказательств в свете порядкового анализа». Synthese . 133 : 237–255. DOI : 10,1023 / A: 1020892011851 . S2CID 45695465 .
- Ратиен, Майкл (2005). «Порядковый анализ устойчивости» . Архив математической логики . 44 : 1–62. CiteSeerX 10.1.1.15.9786 . DOI : 10.1007 / s00153-004-0226-2 . S2CID 2686302 .
- Ратиен, Майкл (август 2005 г.). "Теория доказательств: Часть III, Теория множеств Крипке – Платека" (PDF) . Архивировано из оригинального (PDF) 12 июня 2007 года . Проверено 17 апреля 2008 .(слайды выступления на Фишбахау)