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

В теории множеств порядковое число α является допустимым ординалом , если L α — допустимое множество (т. е. транзитивная модель теории множеств Крипке–Платека ); другими словами, α допустимо, когда α — предельный ординал и L _α ⊧ Σ ₀ -набор. ^{[1] [2]} Этот термин был придуман Ричардом Платеком в 1966 году. ^[3]

Первые два допустимых ординала — это ω и (наименее нерекурсивный ординал , также называемый ординалом Чёрча-Клин ). ^[2] Любой правильный неисчисляемый кардинал является допустимым порядковым. ${\displaystyle \omega _{1}^{\mathrm {CK} }}$

По теореме Сакса счетные допустимые ординалы — это в точности те , которые построены аналогично ординалу Чёрча-Клин, но для машин Тьюринга с оракулами . ^[1] Иногда пишут, что --й порядковый номер является либо допустимым, либо пределом допустимых; порядковый номер, который является и тем, и другим, называется рекурсивно недоступным . ^[4] Существует теория больших ординалов таким образом, которая во многом параллельна теории (малых) больших кардиналов ( например, можно рекурсивно определить ординалы Мало ). ^[5] Но все эти ординалы по-прежнему счетны. Следовательно, допустимые ординалы кажутся рекурсивным аналогом обычных кардинальных чисел . ${\displaystyle \omega _{\alpha }^{\mathrm {CK} }}$ ${\displaystyle \alpha }$

Заметим, что α является допустимым ординалом тогда и только тогда, когда α является предельным ординалом и не существует γ < α , для которого существует Σ ₁ (L _α ) отображение γ на α . ^[6] является допустимым ординалом тогда и только тогда, когда существует стандартная модель КП, набор ординалов которой равен , фактически это можно принять за определение допустимости. ^{[7] [8]} Третий допустимый ординал иногда обозначается как ^{[9] [8] с. 174} или . ^[10] ${\displaystyle \alpha }$ ${\displaystyle M}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \tau _{\alpha }}$ ${\displaystyle \tau _{\alpha }^{0}}$

Теорема Фридмана-Йенсена-Сакса утверждает, что счетность допустима тогда и только тогда, когда существует такой , который является наименьшим порядковым номером, не рекурсивным в . ^[11] ${\displaystyle \alpha }$ ${\displaystyle A\subseteq \omega }$ ${\displaystyle \alpha }$ ${\displaystyle A}$

Смотрите также

• теория α-рекурсии
• Большие счетные ординалы
• Конструируемая вселенная
• Обычный кардинал

Рекомендации

1. Фридман, Си Д. (1985), «Теория тонкой структуры и ее приложения», Теория рекурсии (Итака, Нью-Йорк, 1982) , Proc. Симпозиумы. Чистая математика., вып. 42, амер. Математика. Soc., Провиденс, Род-Айленд, стр. 259–269, номер документа : 10.1090/pspum/042/791062, MR  0791062.. См., в частности, стр. 265.
2. Фиттинг, Мелвин (1981), Основы теории обобщенной рекурсии, Исследования по логике и основам математики, том. 105, издательство North-Holland Publishing Co., Амстердам-Нью-Йорк, с. 238, ISBN 0-444-86171-8, МР  0644315.
3. Дж. Э. Сакс, Теория высшей рекурсии (стр. 151). Ассоциация символической логики, Перспективы логики
4. Фридман, Си Д. (2010), «Конструктивность и принуждение классов», Справочник по теории множеств. Том. 1, 2, 3 , Springer, Дордрехт, стр. 557–604, номер документа : 10.1007/978-1-4020-5764-9_9, MR  2768687.. См., в частности, стр. 560.
5. Кале, Рейнхард; Сетцер, Антон (2010), «Расширенное предикативное определение вселенной Мало», Пути теории доказательств , Ontos Math. Журнал., вып. 2, Ontos Verlag, Heusenstamm, стр. 315–340, MR  2883363..
6. К. Девлин, Введение в тонкую структуру конструктивной иерархии (1974) (стр.38). По состоянию на 6 мая 2021 г.
7. К. Дж. Девлин, Конструктивность (1984), гл. 2, «Конструируемая Вселенная», стр. 95. Перспективы математической логики, Springer-Verlag.
8. Дж. Барвайз, Допустимые множества и структуры (1976). Издательство Кембриджского университета
9. П. Г. Хинман, Теоретико-рекурсивные иерархии (1978), стр. 419–420. Перспективы математической логики, ISBN 3-540-07904-1.
10. С. Крипке, «Трансфинитная рекурсия, конструктивные множества и аналоги кардиналов» (1967), стр.11. Доступ 15 июля 2023 г.
11. В. Марек, М. Сребрный, «Пробелы в конструируемой Вселенной» (1973), стр. 361–362. Анналы математической логики 6