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

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

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

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

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

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

Эта статья по теории множеств — заглушка . Вы можете помочь Википедии, расширив ее.

• в
• т
• е