帰納的可算集合
全ての帰納的集合は帰納的可算だが、全ての帰納的可算集合が帰納的(集合)とは言えない。
帰納的可算言語は形式言語の帰納的可算な部分集合である。
帰納的可算な公理系から導かれる全ての文の集合は帰納的可算集合である。
マチャセビッチの定理によれば、全ての帰納的可算集合はディオファントス集合である(逆も明らかに真)。
単純集合は帰納的可算だが帰納的でない。
創造的集合は帰納的可算だが帰納的でない。
生産的集合は帰納的可算ではない。
ある計算可能関数にゲーデル数 φ {\displaystyle \phi } が与えられたとき、集合 { ⟨ i , x ⟩ ∣ φ i ( x ) ↓ } {\displaystyle \{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}} は帰納的可算である(ここで、 ⟨ i , x ⟩ {\displaystyle \langle i,x\rangle } は対関数であり、 φ i ( x ) ↓ {\displaystyle \phi _{i}(x)\downarrow } は φ i ( x ) {\displaystyle \phi _{i}(x)} が定義されていることを示す)。