計算可能な順序数

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

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

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

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

参照

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

参考文献

• ハートリー・ロジャース・ジュニア著 『再帰関数と実効計算可能性の理論』1967年。1987年再版、MIT Press、ISBN 0-262-68052-1（ペーパーバック）、ISBN 0-07-053522-1
• ジェラルド・サックス著 『高次再帰理論』数理論理学の展望、シュプリンガー・フェアラーク、1990年。ISBN 0-387-19305-7