Большой счетный порядковый номер

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

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

Поскольку существует только счетное число обозначений, все ординалы с обозначениями исчерпываются значительно ниже первого несчетного ординала ω ₁ ; их верхняя грань называется Чёрч – Клини ω ₁ или ω ₁ ^CK (не путать с первым несчетным порядковым номером ω ₁ ), описанным ниже . Порядковые номера ниже ω ₁ ^CK являются рекурсивными порядковыми числами (см. Ниже ). Счетные порядковые числа большего размера могут быть определены, но не имеют обозначений.

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

Общие сведения о рекурсивных ординалах [ править ]

Порядковые обозначения [ править ]

Рекурсивные ординалы (или вычислимые ординалы) - это определенные счетные ординалы: грубо говоря, те, которые представлены вычислимой функцией . Есть несколько эквивалентных определений этого: самое простое - сказать, что вычислимый ординал является порядковым типом некоторого рекурсивного (т. Е. Вычислимого) хорошего упорядочения натуральных чисел; так что, по сути, порядковый номер является рекурсивным, когда мы можем представить набор меньших порядковых чисел таким образом, чтобы компьютер (например, машина Тьюринга ) мог манипулировать ими (и, по сути, сравнивать их).

Другое определение использует систему порядковых обозначений Клини . Вкратце, порядковая нотация - это либо имя ноль (описывающее порядковый номер 0), либо преемник порядковой нотации (описывающее преемника порядкового номера, описываемого этой нотацией), либо машина Тьюринга (вычислимая функция), которая производит возрастающую последовательность порядковых обозначений (которые описывают порядковый номер, являющийся пределом последовательности), и порядковые обозначения (частично) упорядочены так, чтобы сделать преемник o больше, чем o, и сделать предел больше, чем любой член последовательности (это порядок вычислим, но множество Oпорядковых обозначений сама по себе в высшей степени нерекурсивна из-за невозможности решить, действительно ли данная машина Тьюринга производит последовательность обозначений); рекурсивный ординал тогда является ординалом, описываемым некоторой порядковой нотацией.

Любой ординал, меньший, чем рекурсивный ординал, сам по себе является рекурсивным, поэтому набор всех рекурсивных ординалов образует определенный (счетный) ординал, ординал Черча – Клини (см. Ниже).

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

Отношение к системам арифметики [ править ]

Существует связь между вычислимыми ординалами и некоторыми формальными системами (содержащими арифметику , то есть, по крайней мере, разумный фрагмент арифметики Пеано ).

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

Например, обычные аксиомы Пеано первого порядка не доказывают трансфинитную индукцию для (или выше) ε ₀ : в то время как ординал ε ₀ можно легко арифметически описать (он счетный), аксиомы Пеано недостаточно сильны, чтобы показать, что он действительно порядковый номер; на самом деле трансфинитная индукция по ε ₀ доказывает непротиворечивость аксиом Пеано (теорема Генцена ), поэтому по второй теореме Гёделя о неполноте аксиомы Пеано не могут формализовать эти рассуждения. (Это на основе теоремы Кирби-Париж на Гудстейна последовательности .) Будем говорить , что е ₀ измеряет доказательство теоретико-прочностные аксиом Пеано.

Но мы можем сделать это для систем, далеко выходящих за рамки аксиом Пеано. Например, теоретической силой теории множеств Крипке – Платека является ординал Бахмана – Ховарда , и фактически достаточно простого добавления к аксиомам Пеано аксиом, которые утверждают, что порядок всех ординалов ниже ординала Бахмана – Ховарда является достаточным. получить все арифметические следствия теории множеств Крипке – Платека.

Конкретные рекурсивные порядковые числа [ править ]

Предикативные определения и иерархия Веблена [ править ]

Мы уже упоминали (см Cantor нормальная форма ) порядкового е 0 , который является самым маленьким , удовлетворяющий уравнению , так что предел последовательности 0, 1, , , и т.д. На следующий порядковый номер, удовлетворяющий этому уравнению, называется ε ₁ : это предел последовательности${\ displaystyle \ omega ^ {\ alpha} = \ alpha}$${\ displaystyle \ omega}$${\ displaystyle \ omega ^ {\ omega}}$${\ displaystyle \ omega ^ {\ omega ^ {\ omega}}}$

${\ displaystyle \ varepsilon _ {0} +1, \ qquad \ omega ^ {\ varepsilon _ {0} +1} = \ varepsilon _ {0} \ cdot \ omega, \ qquad \ omega ^ {\ omega ^ {\ varepsilon _ {0} +1}} = (\ varepsilon _ {0}) ^ {\ omega}, \ qquad {\ text {и т. д.}}}$

В более общем смысле, -й порядковый номер такой, что называется . Мы могли бы определить как наименьший порядковый номер такой, что , но поскольку греческий алфавит не имеет трансфинитного числа букв, лучше использовать более устойчивую запись: определить ординалы с помощью трансфинитной индукции следующим образом: пусть и пусть будут -й фиксированной точкой ( т. е. -й порядковый номер такой, что ; например, ), а когда является предельным порядковым номером, определить как -ю общую фиксированную точку для всех . Это семейство функций известно как иерархия Веблена.${\ displaystyle \ iota}$${\ displaystyle \ omega ^ {\ alpha} = \ alpha}$${\ displaystyle \ varepsilon _ {\ iota}}$${\ displaystyle \ zeta _ {0}}$${\ Displaystyle \ varepsilon _ {\ alpha} = \ alpha}$${\ Displaystyle \ varphi _ {\ gamma} (\ бета)}$${\ displaystyle \ varphi _ {0} (\ beta) = \ omega ^ {\ beta}}$${\ displaystyle \ varphi _ {\ gamma +1} (\ beta)}$${\ displaystyle \ beta}$${\ displaystyle \ varphi _ {\ gamma}}$${\ displaystyle \ beta}$${\ Displaystyle \ varphi _ {\ gamma} (\ альфа) = \ альфа}$${\ Displaystyle \ varphi _ {1} (\ beta) = \ varepsilon _ {\ beta}}$${\displaystyle \delta }$${\displaystyle \varphi _{\delta }(\alpha )}$${\displaystyle \alpha }$${\displaystyle \varphi _{\gamma }}$${\displaystyle \gamma <\delta }$ (есть несущественные вариации в определении, такие как разрешение для предельного порядкового номера быть пределом для : это по существу просто сдвигает индексы на 1, что безвредно). называется функцией Веблена (до основания ).${\displaystyle \delta }$${\displaystyle \varphi _{\delta }(\alpha )}$${\displaystyle \varphi _{\gamma }(\alpha )}$${\displaystyle \gamma <\delta }$${\displaystyle \varphi _{\gamma }}$${\displaystyle \gamma ^{th}}$ ${\displaystyle \omega }$

Порядок: тогда и только тогда, когда либо ( и ), либо ( и ), либо ( и ).${\displaystyle \varphi _{\alpha }(\beta )<\varphi _{\gamma }(\delta )}$${\displaystyle \alpha =\gamma }$${\displaystyle \beta <\delta }$${\displaystyle \alpha <\gamma }$${\displaystyle \beta <\varphi _{\gamma }(\delta )}$${\displaystyle \alpha >\gamma }$${\displaystyle \varphi _{\alpha }(\beta )<\delta }$

Порядковый номер Фефермана – Шютте и не только [ править ]

Наименьший порядковый номер, известный как порядковый номер Фефермана-Шютте и обычно пишущийся . Его можно описать как набор всех ординалов, которые можно записать в виде конечных выражений, начиная с нуля, используя только иерархию Веблена и сложение. Порядковый номер Фефермана – Шютте важен, потому что в смысле, который сложно уточнить, это наименьший (бесконечный) порядковый номер, который нельзя (« предикативно ») описать с помощью более мелких порядковых номеров. Он измеряет силу таких систем, как « арифметическая трансфинитная рекурсия ».${\displaystyle \varphi _{\alpha }(0)=\alpha }$${\displaystyle \Gamma _{0}}$

В более общем смысле, Γ _α перечисляет ординалы, которые не могут быть получены из меньших ординалов с помощью сложения и функций Веблена.

Конечно, можно описывать ординалы помимо ординала Фефермана – Шютте. Можно продолжить поиск неподвижных точек все более и более сложным образом: перечислить неподвижные точки , затем перечислить неподвижные точки этого и т. Д., А затем искать первый ординал α такой, что α получается за α шагов этого процесса и продолжайте диагонализацию этим специальным образом. Это приводит к определению « малых » и « больших » ординалов Веблена.${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$

Непредикативные порядковые числа [ править ]

Чтобы выйти за рамки порядкового номера Фефермана – Шютте, необходимо ввести новые методы. К сожалению, пока нет стандартного способа сделать это: кажется, что каждый автор предмета изобрел свою собственную систему обозначений, и ее довольно сложно переводить между разными системами. Первая такая система была введена Бахманном в 1950 г. ( специальным образом), а различные ее расширения и вариации были описаны Бухгольцем, Такеути (порядковые диаграммы), Феферманом (θ-системы), Акцелем, Бриджем, Шютте и Полерсом. . Однако большинство систем используют ту же основную идею построения новых счетных ординалов, используя существование некоторых несчетных ординалов. Вот пример такого определения, более подробно описанного в статье о функции порядкового сворачивания :

• ψ (α) определяется как наименьший ординал, который нельзя построить, начиная с 0, 1, ω и Ω, и многократно применяя сложение, умножение и возведение в степень, а также ψ к ранее построенным ординалам (за исключением того, что ψ может применяться только к аргументы меньше, чем α, чтобы убедиться, что он правильно определен).

Здесь Ω = ω ₁ - первый несчетный ординал. Он вставлен, потому что в противном случае функция ψ «застревает» на наименьшем ординале σ, таком что ε _σ = σ: в частности, ψ (α) = σ для любого ординала α, удовлетворяющего σ≤α≤Ω. Однако тот факт, что мы включили Ω, позволяет нам обойти эту точку: ψ (Ω + 1) больше σ. Ключевое свойство Ω, которое мы использовали, состоит в том, что оно больше любого ординала, производимого ψ.

Чтобы построить еще более крупные ординалы, мы можем расширить определение ψ, добавив больше способов построения несчетных ординалов. Есть несколько способов сделать это, в некоторой степени описанные в статье о функции порядкового сворачивания .

Bachmann-Говард порядковый (иногда просто называют Говардом порядковое , ψ ( & epsi ; _{Омы + 1} ) с выше обозначениями) является важным, так как он описывает доказательства теоретико-сила теории множеств Крипки Платека . Действительно, главное значение этих больших порядковых чисел и причина их описания - это их связь с определенными формальными системами, как объяснено выше. Однако такие мощные формальные системы, как полная арифметика второго порядка , не говоря уже о теории множеств Цермело – Френкеля , на данный момент кажутся недосягаемыми.

«Невозможные» рекурсивные порядковые числа [ править ]

Отказавшись от требования иметь полезное описание, можно получить еще более крупные рекурсивные счетные ординалы в качестве ординалов, измеряющих силу различных сильных теорий; грубо говоря, эти порядковые числа являются наименьшими порядковыми числами, которые теории не могут доказать, что они хорошо упорядочены. Принимая сильнее и сильнее теорий , таких как второго порядка арифметики , теории множеств Цермело , теории множеств Цермело-Френкеля , или теории множеств Цермело-Френкеля с различным большим кардиналуаксиом, получаются очень большие рекурсивные ординалы. (Строго говоря, неизвестно, действительно ли все они являются ординалами: по построению, порядковая сила теории может быть доказана только как ординал из еще более сильной теории. Так что для аксиом больших кардиналов это становится совершенно неясным.)

Помимо рекурсивных ординалов [ править ]

Порядковый номер Чёрча-Клини [ править ]

Верхняя грань набора рекурсивных ординалов - это наименьший ординал, который не может быть описан рекурсивным образом. (Это не тип ордера любого рекурсивного полного упорядочения целых чисел.) То есть порядковый счетный порядковый называется церковно-Клини порядкового , . Таким образом, это наименьший нерекурсивный ординал, и с этого момента нет никакой надежды на точное «описание» каких-либо ординалов - мы можем только их определить . Но он по - прежнему намного меньше , чем первый несчетный, . Однако, как следует из его символа, во многом он ведет себя так же, как . ^{[ необходим пример ]}${\displaystyle \omega _{1}^{\mathrm {CK} }}$${\displaystyle \omega _{1}^{\mathrm {CK} }}$${\displaystyle \omega _{1}}$${\displaystyle \omega _{1}}$

Допустимые порядковые номера [ править ]

Ординал Чёрча – Клини снова связан с теорией множеств Крипке – Платека , но теперь по-другому: в то время как ординал Бахмана – Ховарда (описанный выше ) был наименьшим ординалом, для которого КП не доказывает трансфинитную индукцию, ординал Чёрча – Клини является наименьшим α таким образом, что построение вселенной Гёделя , L , вплоть до стадии а, дает модель КП. Такие ординалы называются допустимыми , т.е. это наименьший допустимый ординал (помимо ω в случае, если аксиома бесконечности не входит в KP).${\displaystyle L_{\alpha }}$${\displaystyle \omega _{1}^{\mathrm {CK} }}$

По теореме Сакса счетные допустимые ординалы - это в точности те, которые построены аналогично ординалу Черча – Клини, но для машин Тьюринга с оракулами . Иногда пишут для -го порядкового номера, который является допустимым или пределом допустимых.${\displaystyle \omega _{\alpha }^{\mathrm {CK} }}$${\displaystyle \alpha }$

За пределами допустимых порядковых номеров [ править ]

Ординал, который является одновременно допустимым и пределом допустимых, или, что то же самое , является -м допустимым порядковым номером, называется рекурсивно недоступным . Таким образом, существует теория больших ординалов, которая очень похожа на теорию (малых) больших кардиналов . Например, мы можем определить рекурсивно ординалы Mahlo : это такие, что каждое -рекурсивное замкнутое неограниченное подмножество содержит допустимый ординал (рекурсивный аналог определения кардинала Mahlo ). Но обратите внимание, что здесь мы все еще говорим о возможно счетных ординалах. (Хотя существование недоступных или мало кардиналов не может быть доказано в${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$Теория множеств Цермело – Френкеля, теория рекурсивно недоступных или рекурсивно Mahlo ординалов является теоремой ZFC: на самом деле, любой регулярный кардинал рекурсивно Mahlo и более, но даже если мы ограничимся счетными ординалами, ZFC доказывает существование рекурсивно Mahlo ординалов . Однако они находятся за пределами досягаемости теории множеств Крипке – Платека.)

Отражение и невосприимчивость [ править ]

Для набора формул предельный порядковый номер называется -отражающим, если ранг удовлетворяет определенному свойству отражения для каждой -формулы . ^[1] Эти порядковые появляются в порядковом анализе теорий , такие как КП + П ₃ -REF , теории увеличивающих теорий множеств Крипки-Platek по -отражению схемы. Их также можно считать «рекурсивными аналогами» некоторых несчетных кардиналов, таких как слабо компактные кардиналы и неописуемые кардиналы . ^[2]${\displaystyle \Gamma }$${\displaystyle \alpha }$${\displaystyle \Gamma }$${\displaystyle L_{\alpha }}$${\displaystyle \Gamma }$${\displaystyle \phi }$${\displaystyle \Pi _{3}}$

Допустимый ординал называется непроектируемым, если нет тотально- рекурсивного инъективного отображения функции в меньший ординал. (Это тривиально верно для обычных кардиналов; однако нас в основном интересуют счетные ординалы.) Непроектируемость - гораздо более сильное условие, чем быть допустимым, рекурсивно недоступным или даже рекурсивно Mahlo. Это эквивалентно утверждению о том , что Вселенная Гедель , л , вплоть до стадии а, дает модель КП + -separation.${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle L_{\alpha }}$${\displaystyle \Sigma _{1}}$

«Недоказуемые» порядковые числа [ править ]

Мы можем представить себе даже более крупные порядковые числа, которые все еще можно считать. Например, если ZFC имеет транзитивную модель (гипотеза, более сильная, чем простая гипотеза согласованности, и подразумеваемая существованием недоступного кардинала), то существует счетное число, такое, что является моделью ZFC. Такие ординалы выходят за рамки возможностей ZFC в том смысле, что он не может (по построению) доказать их существование.${\displaystyle \alpha }$${\displaystyle L_{\alpha }}$

Даже более крупный счетные порядковые, называемый стабильными ординалами , которые могут быть определены условиями неописуемости или как те , таким образом, что является 1-элементарной подмоделью из L ; существование этих ординалов может быть доказано в ZFC, ^[3], и они тесно связаны с непроецируемыми ординалами .${\displaystyle \alpha }$${\displaystyle L_{\alpha }}$

Псевдо-хороший порядок [ править ]

В схеме обозначений Клини некоторые представляют собой ординалы, а некоторые - нет. Можно определить рекурсивный общий порядок, который является подмножеством обозначений Клини и имеет начальный сегмент, который хорошо упорядочен с типом порядка . Каждое рекурсивно перечислимое (или даже гиперарифметическое) непустое подмножество этого полного порядка имеет наименьший элемент. Так что в некоторых отношениях он напоминает хороший порядок. Например, над ним можно определить арифметические операции. Однако невозможно точно определить, где заканчивается начальная упорядоченная часть и начинается часть, в которой отсутствует наименьший элемент.${\displaystyle \omega _{1}^{\mathrm {CK} }}$

В качестве примера рекурсивного псевдопорядка, пусть S будет ATR 0 или другой рекурсивно аксиоматизируемой теорией, которая имеет ω-модель, но не имеет гиперарифметических ω-моделей, и (при необходимости) консервативно расширяет S с помощью функций Сколема . Пусть T - дерево (по существу) конечных частичных ω-моделей S: последовательность натуральных чисел находится в T тогда и только тогда, когда S плюс m φ (m) ⇒ φ (x _⌈φ⌉ ) (для первых n формул φ с одна числовая свободная переменная; ⌈φ⌉ - число Гёделя) не имеет доказательства противоречивости короче n. Тогда порядок Клини – Брауэра оператора T является рекурсивным псевдопорядком.${\displaystyle x_{1},x_{2},...,x_{n}}$

Ссылки [ править ]

Большинство книг, описывающих большие счетные порядковые числа, относятся к теории доказательств и, к сожалению, не печатаются.

О рекурсивных ординалах [ править ]

• Вольфрам Полерс , Теория доказательства , Springer 1989 ISBN  0-387-51842-8 (для иерархии Веблена и некоторых возможных порядковых номеров). Это, вероятно, самая читаемая книга по большим счетным порядковым числам (что мало о чем говорит).
• Гаиси Такеути , Теория доказательств , 2-е издание 1987 ISBN 0-444-10492-5 (для порядковых диаграмм) 
• Курт Шютте , теория доказательств , Springer 1977 ISBN 0-387-07911-4 (для иерархии Веблена и некоторых возможных порядковых номеров) 
• Крейг Сморински , Разновидности древесного опыта Math. Intelligencer 4 (1982), нет. 4, 182–189; содержит неформальное описание иерархии Веблена.
• Хартли Роджерс младший , Теория рекурсивных функций и эффективной вычислимости McGraw-Hill (1967) ISBN 0-262-68052-1 (описывает рекурсивные ординалы и ординал Черча-Клини) 
• Ларри В. Миллер , Нормальные функции и конструктивные порядковые обозначения , Журнал символической логики , том 41, номер 2, июнь 1976 г., страницы 439–459 , JSTOR  2272243 ,
• Гильберт Левитц , Трансфинитные порядковые числа и их обозначения: для непосвященных , пояснительная статья (8 страниц, в PostScript )
• Герман Руге Джервелл , Истина и доказуемость , рукопись в процессе.

Помимо рекурсивных ординалов [ править ]

• Барвайз, Джон (1976). Допустимые множества и структуры: подход к теории определимости . Перспективы математической логики. Springer-Verlag. ISBN 3-540-07451-1.
• Хинман, Питер Г. (1978). Теоретико-рекурсивные иерархии . Перспективы математической логики. Springer-Verlag.

И рекурсивные, и нерекурсивные порядковые числа [ править ]

• Майкл Ратьен , « Царство порядкового анализа». в С. Купер и Дж. Трасс (ред.): Наборы и доказательства . (Издательство Кембриджского университета, 1999) 219–279. В файле Postscript .

Встроенные ссылки [ править ]