帰納的可算集合
形式的定義
自然数の集合 S について、定義域が S と正確に一致するような何らかの部分再帰関数（部分計算可能関数）f が存在するとき、S は帰納的可算であると言う。つまり f が定義される必要十分条件は、f への入力が S の元であることである。
この定義は任意の可算集合 A に拡張できる。そのためには、A の元をゲーデル数で表し、もし対応するゲーデル数の集合が帰納的可算ならば A の何らかの部分集合が帰納的可算になることを言えば良い。
特性
A と B が共に帰納的可算集合なら、A ∩ B 、 A ∪ B 、 A × B も帰納的可算集合である。部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である。
ある集合が帰納的可算である必要十分条件は、それが算術的階層のレベル  にあることである。
集合  の補集合  が帰納的可算である場合、 は co-r.e. と呼ばれる。同様に、ある集合が co-r.e. である必要十分条件は、それが算術的階層のレベル  にあることである。
集合 A が帰納的（計算可能）である必要十分条件は、A と A の補集合が共に帰納的可算集合であることである。これは帰納的可算集合の束に於いて帰納的関数のクラスが定義可能であることを示す。（すなわち補元を持つ元が帰納的可算集合である。）ある集合が帰納的である必要十分条件は、その集合が何らかの単調増加な全域再帰関数の値域になっているか、または有限なことである。
互いに素な帰納的可算集合同士の対を取ると、あるものは帰納的分離可能であり、あるものは帰納的分離不可能である。対照的に、任意の互いに素な co-r.e. 集合対が帰納的分離可能であることが、次の性質から示される。
任意の帰納的可算集合  に対して、互いに素な帰納的可算集合  で , ,  なるものが存在する。 の元を  と交互に枚挙していく。 がそれより前に現れないなら  に置く。また  がそれより前に現れないなら  に置く。このとき  は所望の性質を満たす。
任意の帰納的でない帰納的可算集合は2つの互いに素な帰納的でない帰納的可算集合に直和分解できる。
注意
チャーチ＝チューリングのテーゼによれば、実効的に計算可能な関数は全てチューリングマシンで計算可能であり、従って集合 S が帰納的可算である必要十分条件は、何らかのアルゴリズムで S の枚挙ができることである。しかしこれを形式的な定義とすることはできない。何故ならチャーチ＝チューリングのテーゼは形式的な公理ではなく、非形式的な予想だからである。
最近の文献では、帰納的可算集合を全体再帰関数の「値域」ではなく、部分関数の「定義域」として定義する方が一般的である。この理由は、例えばα-再帰理論(en)のような一般化された再帰理論では、定義域を用いた定義の方が自然だと判ったためである。他の文献では枚挙を使った定義がよく使われるが、これも帰納的可算集合に同値である。