Нерекурсивный порядковый - Nonrecursive ordinal

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

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

Наименьший нерекурсивный порядковый номер - это порядковый номер Черча Клини , названный в честь Алонзо Черча и С. К. Клини ; его тип заказа - это набор всех рекурсивных ординалов . Поскольку последователь рекурсивного ординала является рекурсивным, ординал Черча – Клини является предельным ординалом . Это также наименьший порядковый номер, который не является гиперарифметическим , и наименьший допустимый порядковый номер после ω . Обозначения относятся к ω${\ displaystyle \ omega _ {1} ^ {\ mathsf {CK}}}$${\ displaystyle \ omega _ {1} ^ {\ mathsf {CK}}}$
₁, первый несчетный порядковый номер , который представляет собой набор всех счетных порядковых номеров. В -recursive подмножества со в точности подмножества со . ${\ displaystyle \ omega _ {1} ^ {\ mathsf {CK}}}$${\ displaystyle \ Delta _ {1} ^ {1}}$

Ординал α называется допустимым, если . ${\ displaystyle L _ {\ alpha} \ models {\ mathsf {KP}}}$

Релятивизированный ординал Черча – Клини - это верхняя грань x-вычислимых ординалов. ${\ displaystyle \ omega _ {1} ^ {x}}$

${\ displaystyle \ omega _ {\ omega} ^ {\ mathsf {CK}}}$, впервые определенная Стивеном Симпсоном и получившая название «Великая Церковь – Клини ординал», является расширением ординала Черча – Клини. Это наименьший предел допустимых порядковых номеров, но этот порядковый номер недопустим. В качестве альтернативы, его наименьшее значение α, которое является моделью -понимания . ${\ Displaystyle L _ {\ alpha} \ cap {\ mathsf {P}} (\ omega)}$${\ displaystyle \ Pi _ {1} ^ {1}}$

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

Рекурсивные порядковые числа x , не путать с рекурсивными порядковыми числами, являются разновидностями нерекурсивных порядковых чисел.

Ординал α называется рекурсивно недоступным, если он допустим и предел допустимых (α - α-й допустимый). С другой стороны, это рекурсивно недоступно, если расширение теории множеств Крипке – Платека, основанное на недоступном кардинале; или, наконец, с арифметической стороны, которая является моделью понимания . ${\ displaystyle L _ {\ alpha} \ models {\ mathsf {KPi}}}$${\ Displaystyle L _ {\ alpha} \ cap {\ mathsf {P}} (\ omega)}$${\ displaystyle \ Delta _ {2} ^ {1}}$

Ординал α называется рекурсивно гипердоступным, если он рекурсивно недоступен и является пределом рекурсивно недоступных (α - это α-й рекурсивно недоступный).

Порядковое & alpha ; , называется рекурсивно Мало , если это допустимо , и для любого альфа -recursive функции F : & alpha ; → & alpha ; существует допустимый & beta ;  <  & alpha ; , что { F ( & gamma ):  & gamma  ∈  & beta ; } ⊆  & beta ; (то есть, & beta ; является закрыто под  f ).

Ординал α называется рекурсивно слабо компактным, если он -отражающий (2-допустимый). ${\ displaystyle \ Pi _ {3}}$

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

Стабильные порядковые числа - одни из самых больших нерекурсивных порядковых чисел. Существуют различные ослабления конюшен:

• Счетный ординал называется -стабильным тогда и только тогда . Наименьший -стабильный ординал больше самого маленького рекурсивно слабо компактного ординала. ${\ displaystyle \ alpha}$${\ displaystyle (+1)}$ ${\ Displaystyle L _ {\ alpha} \ prevq _ {1} L _ {\ alpha +1}}$${\ displaystyle (+1)}$
  • В общем случае счетный ординал называется -стабильным
  тогда и только тогда .${\ displaystyle \ alpha}$${\ Displaystyle (+ \ бета)}$ ${\ Displaystyle L _ {\ альфа} \ prevq _ {1} L _ {\ альфа + \ бета}}$

Счетный ординал называется -стабильным тогда и только тогда , когда - наименьший допустимый ординал . Самый маленький -стабильный порядковый номер больше самого маленького -стабильного порядкового номера .${\ displaystyle \ alpha}$${\ displaystyle (^ {+})}$ ${\ Displaystyle L _ {\ alpha} \ prevq _ {1} L _ {\ alpha ^ {+}}}$${\ displaystyle \ beta ^ {+}}$${\ displaystyle> \ beta}$${\ displaystyle (^ {+})}$${\ displaystyle (+1)}$

Счетный ординал называется -стабильным тогда и только тогда , когда и - два наименьших допустимых ординала . Наименьший -устойчивый порядковый номер больше самого маленького -отражающего.${\ displaystyle \ alpha}$${\ displaystyle (^ {++})}$ ${\ Displaystyle L _ {\ alpha} \ prevq _ {1} L _ {\ alpha ^ {++}}}$${\ displaystyle \ beta ^ {+}}$${\ displaystyle \ beta ^ {++}}$${\ displaystyle> \ beta}$${\ displaystyle (^ {++})}$${\ displaystyle \ Sigma _ {1} ^ {1}}$

Счетный ординал называется недоступно-устойчивым тогда и только тогда , когда - наименьший рекурсивно недоступный ординал . Наименьший недоступно-стабильный порядковый номер больше наименьшего -стабильного.${\ displaystyle \ alpha}$ ${\ Displaystyle L _ {\ alpha} \ prevq _ {1} L _ {\ beta}}$${\ displaystyle \ beta}$${\ displaystyle> \ alpha}$${\ displaystyle (^ {++})}$

Счетный ординал называется малостабильным тогда и только тогда , когда - наименьший рекурсивный ординал Мало . Наименьший порядковый номер малостабильности больше наименьшего недоступно-стабильного.${\ displaystyle \ alpha}$ ${\ Displaystyle L _ {\ alpha} \ prevq _ {1} L _ {\ beta}}$${\ displaystyle \ beta}$${\ displaystyle> \ alpha}$

Счетный ординал называется дважды -стабильным тогда и только тогда . Наименьший двустабильный порядковый номер больше наименьшего Малоустойчивого.${\ displaystyle \ alpha}$${\ displaystyle (+1)}$ ${\ Displaystyle L _ {\ альфа} \ prevq _ {1} L _ {\ beta} \ prevq _ {1} L _ {\ beta +1}}$${\ displaystyle (+1)}$

Наибольшие рекурсивные порядковые числа

• Порядковое является полу-nonprojectible , если где β является наименьшим порядковым nonprojectible.${\ displaystyle \ alpha}$${\ Displaystyle L _ {\ alpha} \ prevq _ {1} L _ {\ beta}}$
• Ординал не проецируется, если α является пределом α- стабильных порядковых чисел , или; если множество неограничено по  α .${\ displaystyle \ alpha}$${\ Displaystyle X = \ {\ beta <\ alpha | L _ {\ beta} \ Prec _ {\ Sigma _ {1}} L _ {\ alpha} \}}$
• Порядковый номер разветвленного анализа, часто обозначаемый как , является наименьшим из таких, что является моделью понимания второго порядка, и .${\ displaystyle \ beta _ {0}}$${\ displaystyle \ beta}$${\ Displaystyle L _ {\ beta} \ cap {\ mathsf {P}} (\ omega)}$${\ displaystyle L _ {\ beta} \ models ZFC ^ {-}}$
• «Порядковый номер Девлина – Джеха» - это наименьший порядковый номер α, такой что .${\ displaystyle L _ {\ alpha} \ models {\ mathsf {KP}} + '\ omega _ {1} exists'}$
• Наименьший порядковый номер α такой, что .${\ displaystyle L _ {\ alpha} \ models {\ mathsf {ZFC ^ {-}}} + '\ omega _ {1} exists'}$
• Наименьший стабильный порядковый номер. Счетный ординал называется стабильным тогда и только тогда .${\ Displaystyle L _ {\ alpha} \ Prec _ {\ Sigma _ {1}} L}$

использованная литература

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