計算可能な順序数

数学、特に計算可能性と集合論において、順序型を持つ自然数の計算可能な部分集合の計算可能な整列が存在する場合、順序数は 計算可能または再帰的であると言われます。 ${\displaystyle \alpha}$ ${\displaystyle \alpha}$

が計算可能であることは簡単に確認できます。計算可能な順序数の後続は計算可能であり、すべての計算可能な順序数の集合は下方向に閉じています。 ${\displaystyle \omega}$

すべての計算可能順序数の上限は、最初の非再帰的順序数であるチャーチ・クリーネ順序数 と呼ばれ、と表記されます。チャーチ・クリーネ順序数は極限順序数です。順序数が計算可能であるのは、 より小さい場合のみです。計算可能な関係は可算個しかないため、計算可能な順序数も可算個しかありません。したがって、は可算です。 ${\displaystyle \omega _{1}^{\mathsf {CK}}}$${\displaystyle \omega _{1}^{\mathsf {CK}}}$${\displaystyle \omega _{1}^{\mathsf {CK}}}$

計算可能順序数は、クリーネの順序表記法を持つ順序数とまったく同じです。 ${\displaystyle {\mathcal {O}}}$

• 算術階層
• 大きな可算順序数
• 順序分析
• 序数表記