Вычислимое ординальное

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

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

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

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

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

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

Ссылки

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