Вычислимый порядковый номер

---

В математике , особенно в теории вычислимости и теории множеств , порядковый номер называется вычислимым или рекурсивным , если существует вычислимое упорядочение подмножества натуральных чисел , имеющих тип порядка .${\ Displaystyle \ альфа}$ ${\ Displaystyle \ альфа}$

Легко проверить, что оно вычислимо. Преемник вычислимого ординала вычислим, и множество всех вычислимых ординалов замкнуто вниз. ${\ Displaystyle \ омега}$

Супремум всех вычислимых ординалов называется ординалом Черча -Клине , первым нерекурсивным ординалом и обозначается . Порядковый номер Черча-Клине является предельным порядковым номером . Порядковый номер вычислим тогда и только тогда, когда он меньше . Поскольку существует только счетное число вычислимых отношений, существует также только счетное число вычислимых ординалов. Таким образом, счетно.${\ Displaystyle \ омега _ {1} ^ {CK}}$${\ Displaystyle \ омега _ {1} ^ {CK}}$${\ Displaystyle \ омега _ {1} ^ {CK}}$

Вычислимыми ординалами являются именно те ординалы, которые имеют порядковые обозначения в системе Клини${\ displaystyle {\ mathcal {O}}}$ .

---