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

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

Это легко проверить $\omega$ является вычислимым. Последователь замкнуто вычислимого ординала вычислим, а множество всех вычислимых ординалов вниз .

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

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

См. также

• Арифметическая иерархия
• Большой счетный порядковый номер
• Порядковый анализ
• Порядковое обозначение

Ссылки

• Хартли Роджерс младший. Теория рекурсивных функций и эффективная вычислимость , 1967. Перепечатано в 1987 году, MIT Press, ISBN   0-262-68052-1 (мягкая обложка), ISBN   0-07-053522-1
• Джеральд Сакс . Теория высшей рекурсии . Перспективы математической логики, Springer-Verlag, 1990. ISBN   0-387-19305-7