再帰理論
もう一つの重要な問題は再帰理論の構造物における保型性の存在である。このような構造の一つとして、有限な差を除いて包含関係が成り立つような帰納的可算集合同士の関係がある。この構造においては、A が B に含まれる必要十分条件は差集合 B - A が有限であることである。(前節で定義したような)極大集合は、非極大集合に対して保型的にはなれないという性質がある。つまり、今しがた述べたような構造の下で帰納的可算集合に保型性が存在するのなら、如何なる極大集合も他の極大集合に写像できる。Soare (1974) はこの逆も成り立つこと、即ち任意の二つの極大集合は保型的であることを示した。従って極大集合は軌道を成す。つまり全ての保型性は自ずと極大性を保ち、如何なる二つの極大集合も何らかの保型性によって互いに変換し合うことができる。その他の例として、Harrington が得た停止問題に多対一同値な creative 集合(en)も、保型的な性質を有する。
帰納的可算集合の束論の傍らで、全ての集合のチューリング次数の構造や或いは帰納的可算集合のチューリング次数の構造についても、保型性は研究されている。何れについても、Cooper は幾つかの次数を他の次数に写像するような自明でない保型性を構成したと主張している。しかしながらこの構成法は確かめられておらず、一部の研究者によると誤りがあり、従ってチューリング次数に自明でない保型性が存在するか否かは依然としてこの分野の主たる未解決問題の一つだという (Slaman and Woodin 1986, Ambos-Spies and Fejer 2006)。
ライスの定理は、すべての自明でないクラス C(帰納的可算集合からなるクラスであって空でも全体でもないもの)において、インデックス集合 E = {e: e番目の帰納的可算集合 We が C に含まれる} を考えると、停止問題かその補問題が E に多対一還元可能という属性を持つことを示す。しかし、このようなインデックス集合の多くは停止問題以上に複雑である。このような集合は算術的階層によって分類される。例えば、すべての有限集合のクラスのインデックス集合 FIN の階層レベルは Σ2、すべての帰納的集合のクラスのインデックス集合 REC の階層レベルは Σ3、すべての補有限集合のクラスのインデックス集合 COFIN の階層レベルは Σ3、すべてのチューリング完全な集合のクラスのインデックス集合 COMP の階層レベルは Σ4 である。
ナンバリングとは関数や集合に対する番号付けである。より一般には自然数の集合から集合 A {\displaystyle A} への全射を A {\displaystyle A} のナンバリングという。
A {\displaystyle A} が関数や集合からなる集合である場合には、 A {\displaystyle A} のナンバリングの計算可能性・実効性を考えることができる。例えば A {\displaystyle A} が帰納的可算集合からなる集合のとき、 A {\displaystyle A} のナンバリング ν {\displaystyle \nu } が計算可能であるとは、述語 x ∈ ν ( i ) {\displaystyle x\in \nu (i)} が帰納的可算であることをいう。また A {\displaystyle A} が計算可能(部分)関数からなる集合のとき、 A {\displaystyle A} のナンバリング ν {\displaystyle \nu } が計算可能であるとは、部分関数 ( i , x ) ↦ ν ( i ) ( x ) {\displaystyle (i,x)\mapsto \nu (i)(x)} が計算可能であることをいう。
ナンバリングの間には「計算可能関数によって変換できるか」によって擬順序を定めることができる。