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

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

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

Ординал α называется допустимым, если . ${\ Displaystyle L _ {\ альфа} \ модели {\ mathsf {КП}}}$

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

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

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