Нерекурсивный ординал

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

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

Наименьшим нерекурсивным ординалом является ординал Чёрча-Клина, , названный в честь Алонзо Чёрча и SC Kleene ; его тип порядка — множество всех рекурсивных ординалов . Поскольку преемник рекурсивного ординала рекурсивен, ординал Чёрча-Клина является предельным ординалом . Это также наименьший ординал, который не является гиперарифметическим , и наименьший допустимый ординал после (ординал называется допустимым, если .) -рекурсивные подмножества являются в точности подмножествами . ^[1] ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ ${\displaystyle \omega }$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {KP}}}$ ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ ${\displaystyle \omega }$ ${\displaystyle \Delta _{1}^{1}}$ ${\displaystyle \omega }$

Обозначение относится к , первому несчетному ординалу , который является множеством всех счетных ординалов, аналогично тому, как ординал Чёрча-Клина является множеством всех рекурсивных ординалов. Некоторые старые источники используют для обозначения ординала Чёрча-Клина. ^[2] ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{1}}$

Для множества множество является -вычислимым, если оно вычислимо из машины Тьюринга с состоянием оракула, которое запрашивает . Релятивизированный ординал Чёрча-Клини является супремумом порядковых типов -вычислимых отношений. Теорема Фридмана-Йенсена-Сакса утверждает, что для каждого счётного допустимого ординала существует множество такое, что . ^[3] ${\displaystyle x\subseteq \mathbb {N} }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \omega _{1}^{x}}$ ${\displaystyle x}$ ${\displaystyle \alpha }$ ${\displaystyle x}$ ${\displaystyle \alpha =\omega _{1}^{x}}$

${\displaystyle \omega _{\omega }^{\mathsf {CK}}}$, впервые определённый Стивеном Г. Симпсоном ^{[ требуется ссылка ]} является расширением ординала Чёрча-Клина. Это наименьший предел допустимых ординалов, однако этот ординал не является допустимым. С другой стороны, это наименьшее α, такое что является моделью -понимания . ^[1] ${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$ ${\displaystyle \Pi _{1}^{1}}$

Рекурсивно ординалы

Допустимый ординал иногда обозначается как . ^{[4] [5]} ${\displaystyle \alpha }$ ${\displaystyle \tau _{\alpha }}$

Рекурсивно « x» ординалы, где «x» обычно представляет большое кардинальное свойство, являются видами нерекурсивных ординалов. ^[6] Ратьен назвал эти ординалы «рекурсивно большими аналогами» x , ^[7] однако использование здесь термина «рекурсивно большой» не следует путать с понятием рекурсивности ординала.

Ординал называется рекурсивно недоступным, если он допустим и является пределом допустимых. Альтернативно, является рекурсивно недоступным, если и только если является -м допустимым ординалом, ^[5] или если и только если , расширение теории множеств Крипке–Платека, утверждающее, что каждое множество содержится в модели теории множеств Крипке–Платека. При условии, что («каждое множество наследственно счетно »), является рекурсивно недоступным, если и только если является моделью -понимания . ^[8] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {KPi}}}$ ${\displaystyle L_{\alpha }\vDash {\textrm {V=HC}}}$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$ ${\displaystyle \Delta _{2}^{1}}$

Ординал называется рекурсивно гипернедоступным, если он рекурсивно недоступен и является пределом рекурсивно недоступных, или где th рекурсивно недоступен. Как и в случае с «гипернедоступным кардиналом», разные авторы конфликтуют по поводу этой терминологии. ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Ординал называется рекурсивно Мало, если он допустим и для любой -рекурсивной функции существует допустимый такой, что (то есть замкнут относительно ). ^[2] Зеркально отображая иерархию Малонесса , является рекурсивно -Мало для ординала , если он допустим и для любой -рекурсивной функции существует допустимый ординал такой, что замкнут относительно , ​​и является рекурсивно -Мало для всех . ^[6] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle f:\alpha \rightarrow \alpha }$ ${\displaystyle \beta <\alpha }$ ${\displaystyle \left\{f(\gamma )\mid \gamma \in \beta \right\}\subseteq \beta }$ ${\displaystyle \beta }$ ${\displaystyle f}$ ${\displaystyle \alpha }$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$ ${\displaystyle \alpha }$ ${\displaystyle f:\alpha \rightarrow \alpha }$ ${\displaystyle \beta <\alpha }$ ${\displaystyle \beta }$ ${\displaystyle f}$ ${\displaystyle \beta }$ ${\displaystyle \delta }$ ${\displaystyle \delta <\gamma }$

Ординал называется рекурсивно слабо компактным , если он является -отражающим, или, что эквивалентно, ^[2] 2-допустимым. Эти ординалы обладают сильными рекурсивными свойствами Малонесса, если α является -отражающим, то рекурсивно -Мало. ^[6] ${\displaystyle \alpha }$ ${\displaystyle \Pi _{3}}$ ${\displaystyle \Pi _{3}}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Ослабления стабильных порядковых чисел

Ординал является стабильным, если является - элементарной подструктурой , обозначаемой . ^[9] Это некоторые из самых больших именованных нерекурсивных ординалов, появляющихся в модельно-теоретическом контексте, например, больше, чем для любой вычислимо аксиоматизируемой теории . ^{[10] Предложение 0.7} . Существуют различные ослабления стабильных ординалов: ^[1] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle L}$ ${\displaystyle L_{\alpha }\preceq _{1}L}$ ${\displaystyle \min\{\alpha :L_{\alpha }\models T\}}$ ${\displaystyle T}$

• Счётный ординал называется -устойчивым тогда и только тогда . ${\displaystyle \alpha }$ ${\displaystyle (+1)}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha +1}}$
  • Наименьший -стабильный ординал намного больше наименьшего рекурсивно слабо компактного ординала: было показано, что наименьший -стабильный ординал является -отражающим для всех конечных . ^[2] ${\displaystyle (+1)}$ ${\displaystyle (+1)}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle n}$
  • В общем случае счетный ординал называется -устойчивым тогда и только тогда . ${\displaystyle \alpha }$ ${\displaystyle (+\beta )}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha +\beta }}$
• Счётный ординал называется -стабильным тогда и только тогда , когда , где - наименьший допустимый ординал . Наименьший -стабильный ординал снова намного больше наименьшего -стабильного или наименьшего -стабильного для любой константы . ${\displaystyle \alpha }$ ${\displaystyle (^{+})}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha ^{+}}}$ ${\displaystyle \beta ^{+}}$ ${\displaystyle >\beta }$ ${\displaystyle (^{+})}$ ${\displaystyle (+1)}$ ${\displaystyle (+\beta )}$ ${\displaystyle \beta }$
• Счётный ординал называется -устойчивым тогда и только тогда , когда , где - два наименьших допустимых ординала . Наименьший -устойчивый ординал больше наименьшего -отражающего. ${\displaystyle \alpha }$ ${\displaystyle (^{++})}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha ^{++}}}$ ${\displaystyle \beta ^{++}}$ ${\displaystyle >\beta }$ ${\displaystyle (^{++})}$ ${\displaystyle \Sigma _{1}^{1}}$
• Счётный ординал называется недостижимо-устойчивым тогда и только тогда , когда , где — наименьший рекурсивно недостижимый ординал . Наименьший недостижимо-устойчивый ординал больше наименьшего -устойчивого. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle >\alpha }$ ${\displaystyle (^{++})}$
• Счётный ординал называется Mahlo-устойчивым тогда и только тогда , когда , где — наименьший рекурсивно Mahlo-устойчивый ординал . Наименьший Mahlo-устойчивый ординал больше наименьшего недостижимо-устойчивого. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle >\alpha }$
• Счётный ординал называется дважды устойчивым тогда и только тогда, когда . Наименьший дважды устойчивый ординал больше наименьшего Мало-устойчивого. ${\displaystyle \alpha }$ ${\displaystyle (+1)}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }\preceq _{1}L_{\beta +1}}$ ${\displaystyle (+1)}$

Большие нерекурсивные ординалы

Еще более крупные нерекурсивные ординалы включают в себя: ^[1]

• Наименьший порядковый номер такой, что где — наименьший непроектируемый порядковый номер. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$ ${\displaystyle \beta }$
• Ординал непроектируем, если является пределом -устойчивых ординалов, или; если множество неограничено в . ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle X=\left\{\beta <\alpha \mid L_{\beta }\preceq _{1}L_{\alpha }\right\}}$ ${\displaystyle \alpha }$
• Порядковый номер разветвленного анализа, часто записываемый как . Это наименьший такой, который является моделью понимания второго порядка , или , которая не имеет аксиомы степенного множества . ${\displaystyle \beta _{0}}$ ${\displaystyle \beta }$ ${\displaystyle L_{\beta }\cap {\mathsf {P}}(\omega )}$ ${\displaystyle L_{\beta }\models {\mathsf {ZFC^{-}}}}$ ${\displaystyle {\mathsf {ZFC}}}$
• Наименьший порядковый номер такой, что . Этот порядковый номер был охарактеризован Тошиясу Араи. ^[11] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {KP}}+{\text{'}}\omega _{1}{\text{ exists'}}}$
• Наименьший порядковый номер такой, что . ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {ZFC^{-}}}+{\text{'}}\omega _{1}{\text{ exists'}}}$
• Наименее стабильный порядковый номер.

Ссылки

1. Д. Мадор, Зоопарк ординалов (2017). По состоянию на сентябрь 2021 г.
2. W. Richter, P. Aczel, Inductive Definitions and Reflecting Properties of Admissible Ordinals (1973, стр. 15). Доступ 28 октября 2021 г.
3. Сакс, Джеральд Э. (1976), «Счетные допустимые ординалы и гиперстепени», Успехи в математике , 19 (2): 213–262, doi :10.1016/0001-8708(76)90187-0
4. PG Hinman, Recursion-Theoretic Hierarchies (1978), стр. 419--420. Перспективы в математической логике, ISBN 3-540-07904-1.
5. J. Barwise, Admissible Sets and Structures (1976), стр. 174--176. Perspectives in Logic, Cambridge University Press, ISBN 3-540-07451-1.
6. Rathjen, Michael (1994), "Теория доказательства отражения" (PDF) , Annals of Pure and Applied Logic , 68 (2): 181–224, doi : 10.1016/0168-0072(94)90074-4
7. М. Ратьен, «The Realm of Ordinal Analysis» (2006). Архивировано 7 декабря 2023 г.
8. W. Marek, Некоторые комментарии к статье Artigue, Isambert, Perrin и Zalc (1976), ICM. Доступ 19 мая 2023 г.
9. Дж. Барвайз, Допустимые множества и структуры (1976), Издательство Кембриджского университета, Перспективы в логике.
10. В. Марек, К. Расмуссен, Спектр L в библиотеках ( каталог WorldCat ) (страница EuDML), Państwowe Wydawn. Доступ 01 декабря 2022 г.
11. T. Arai, A Sneak Preview of Proof Theory of Ordinals (1997, стр. 17). Доступ 28 октября 2021 г.

• Чёрч, Алонзо ; Клини, SC (1937), «Формальные определения в теории порядковых чисел», Fundamenta Mathematicae , 28 : 11–21, doi : 10.4064/fm-28-1-11-21 , JFM  63.0029.02
• Чёрч, Алонзо (1938), «Конструктивный второй числовой класс», Bull. Amer. Math. Soc. , 44 (4): 224–232, doi : 10.1090/S0002-9904-1938-06720-1
• Клини, СК (1938), «О нотации порядковых чисел», Журнал символической логики , 3 (4), том 3, № 4: 150–155, doi : 10.2307/2267778, JSTOR  2267778, S2CID  34314018
• Роджерс, Хартли (1987) [1967], Теория рекурсивных функций и эффективная вычислимость , Первое издание в мягкой обложке MIT, ISBN 978-0-262-68052-3
• Симпсон, Стивен Г. (2009) [1999], Подсистемы арифметики второго порядка , Перспективы в логике, т. 2, Cambridge University Press, стр. 246, 267, 292–293, ISBN 978-0-521-88439-6
• Рихтер, Уэйн; Ацель, Питер (1974), Индуктивные определения и отражающие свойства допустимых ординалов , стр. 312–313, 333, ISBN 0-7204-2276-0