Нерекурсивный порядковый номер

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

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

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

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

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

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

Рекурсивно порядковые номера

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

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

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

Порядковый номер $\alpha$ называется рекурсивно гипердоступным, если он рекурсивно недоступен и есть предел рекурсивно недоступных, или где $\alpha$ это $\alpha$ рекурсивно недоступен. Как и в случае с «сверхнедоступным кардиналом», разные авторы спорят по поводу этой терминологии.

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

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

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

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д Д. Мадор, Зоопарк ординалов (2017). По состоянию на сентябрь 2021 г.
^ Jump up to: ^а ^б ^с ^д В. Рихтер, П. Аксель, Индуктивные определения и отражающие свойства допустимых ординалов (1973, стр.15). По состоянию на 28 октября 2021 г.
^ Сакс, Джеральд Э. (1976), «Счетные допустимые ординалы и гиперстепени», Успехи в математике , 19 (2): 213–262, doi : 10.1016/0001-8708(76)90187-0
^ П.Г. Хинман, Теоретико-рекурсивные иерархии (1978), стр.419–420. Перспективы математической логики, ISBN 3-540-07904-1.
^ Jump up to: ^а ^б Дж. Барвайз, Допустимые множества и структуры (1976), стр. 174–176. Перспективы логики, издательство Кембриджского университета, ISBN 3-540-07451-1.
^ Jump up to: ^а ^б ^с Ратьен, Майкл (1994), «Теория доказательства отражения» (PDF) , Анналы чистой и прикладной логики , 68 (2): 181–224, doi : 10.1016/0168-0072(94)90074-4
^ М. Ратьен, «Сфера порядкового анализа» (2006). Архивировано 7 декабря 2023 года.
^ В. Марек, Некоторые комментарии к статье Артига, Исамберта, Перрена и Залька (1976), ICM. По состоянию на 19 мая 2023 г.
^ Дж. Барвайз, Допустимые множества и структуры (1976), Издательство Кембриджского университета, Перспективы логики.
^ В. Марек, К. Расмуссен, Спектр L в библиотеках ( WorldCat каталог EuDML ) ( страница ), Państwowe Wydawn. Доступ 01 декабря 2022 г.
^ Т. Араи, Краткий обзор теории доказательства ординалов (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. амер. Математика. Соц. , 44 (4): 224–232, doi : 10.1090/S0002-9904-1938-06720-1
Клини, SC (1938), «Об обозначениях порядковых чисел», Журнал символической логики , 3 (4), Vol. 3, № 4: 150–155, doi : 10.2307/2267778 , JSTOR 2267778 , S2CID 34314018.
Роджерс, Хартли (1987) [1967], Теория рекурсивных функций и эффективная вычислимость , Первое издание MIT в мягкой обложке, ISBN 978-0-262-68052-3
Симпсон, Стивен Г. (2009) [1999], Подсистемы арифметики второго порядка , Перспективы логики, том. 2, Издательство Кембриджского университета, стр. 246, 267, 292–293, ISBN. 978-0-521-88439-6
Рихтер, Уэйн; Аксель, Питер (1974), Индуктивные определения и отражающие свойства допустимых ординалов , стр. 312–313, 333, ISBN 0-7204-2276-0

[Zoo-1] Jump up to: ^а ^б ^с ^д Д. Мадор, Зоопарк ординалов (2017). По состоянию на сентябрь 2021 г.

[RichterAczel73-2] Jump up to: ^а ^б ^с ^д В. Рихтер, П. Аксель, Индуктивные определения и отражающие свойства допустимых ординалов (1973, стр.15). По состоянию на 28 октября 2021 г.

[3] Сакс, Джеральд Э. (1976), «Счетные допустимые ординалы и гиперстепени», Успехи в математике , 19 (2): 213–262, doi : 10.1016/0001-8708(76)90187-0

[4] П.Г. Хинман, Теоретико-рекурсивные иерархии (1978), стр.419–420. Перспективы математической логики, ISBN 3-540-07904-1.

[Barwise76-5] Jump up to: ^а ^б Дж. Барвайз, Допустимые множества и структуры (1976), стр. 174–176. Перспективы логики, издательство Кембриджского университета, ISBN 3-540-07451-1.

[Rathjen93-6] Jump up to: ^а ^б ^с Ратьен, Майкл (1994), «Теория доказательства отражения» (PDF) , Анналы чистой и прикладной логики , 68 (2): 181–224, doi : 10.1016/0168-0072(94)90074-4

[7] М. Ратьен, «Сфера порядкового анализа» (2006). Архивировано 7 декабря 2023 года.

[8] В. Марек, Некоторые комментарии к статье Артига, Исамберта, Перрена и Залька (1976), ICM. По состоянию на 19 мая 2023 г.

[9] Дж. Барвайз, Допустимые множества и структуры (1976), Издательство Кембриджского университета, Перспективы логики.

[10] В. Марек, К. Расмуссен, Спектр L в библиотеках ( WorldCat каталог EuDML ) ( страница ), Państwowe Wydawn. Доступ 01 декабря 2022 г.

[11] Т. Араи, Краткий обзор теории доказательства ординалов (1997, стр.17). По состоянию на 28 октября 2021 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]