帰納的可算であることをいう。計算可能であることをいう。ナンバリングの間には「計算可能関数によって変換できるか」によって擬順序を定めることができる。成り立つことと定める。この還元可能性に関してナンバリングの全体は擬順序集合を成す。計算可能ナンバリングの全体について半順序反映を取ったものをRogers半束という。名前の通りRogers半束は(空でなければ)上半束の構造を成す。ナンバリングまたはゲーデル数化と言う。ナンバリング(発見者の名に因む)は計算可能な一対一ナンバリングである。ナンバリングではない。ある帰納的可算集合のクラスを発見し、そのナンバリングの全体が再帰同型の観点から見て正確に二つのクラスに分類されることを示した。そのクラスのRogers半束の濃度が2であることを証明した。優先度法[編集]ポストの問題は優先度法という技法を用いて解決された。この技法を用いる証明は優先度論法と呼ばれる。これは第一義的には特別な性質を備えた帰納的可算集合を構成することを目的とする。やり方としては、まずその帰納的可算集合が備えるべき性質を無限個の「要件」に分解し、全ての要件を満足すれば目的の集合は自ずと所期の性質を獲得する、という形を作る。個々の要件には優先度を表す自然数を付与しておく。...という具合である。以後、目的の集合を「段階」を踏んで構築して行く。個々の段階は、一つ以上の要件を満たすように、目的の集合に対して数を追加または削除することから成る。一つの要件を満たすと他の要件に反してしまう場合が有り得るが、その際は優先度を参照して処理方法を決定する。複雑な優先度論法はテクニカルかつ難解になりがちなので、伝統的に出来れば優先度論法は使わずに証明することが望ましいとされ、また優先度論法を用いた証明があればそれ抜きの別証明が模索されてきた。包含関係を研究し始めた。今日では詳細に研究された構造となっている。ある集合が帰納的である必要十分条件は、集合とその補集合が共に帰納的可算であることである。帰納的集合を上位集合として持たない。ポスト(1944)は既に超単純集合と超々単純集合を導入していた。あるような帰納的可算集合である。ポストがこの束を研究した元々の動機は、この性質を満たす全ての集合のチューリング次数が、帰納的集合と停止問題の何れのチューリング次数とも異なるということを構造的に示せないかという点にあった。そのような性質をついに発見した。保型性問題[編集]もう一つの重要な問題は再帰理論の構造物における保型性の存在である。有限であることである。(前節で定義したような)極大集合は、非極大集合に対して保型的にはなれないという性質がある。今しがた述べたような構造の下で帰納的可算集合に保型性が存在するのなら、如何なる極大集合も他の極大集合に写像できる。この逆も成り立つこと、即ち任意の二つの極大集合は保型的であることを示した。従って極大集合は軌道を成す。全ての保型性は自ずと極大性を保ち、如何なる二つの極大集合も何らかの保型性によって互いに変換し合うことができる。集合(en)も、保型的な性質を有する。帰納的可算集合の束論の傍らで、全ての集合のチューリング次数の構造や或いは帰納的可算集合のチューリング次数の構造についても、保型性は研究されている。幾つかの次数を他の次数に写像するような自明でない保型性を構成したと主張している。