帰納的可算集合

帰納的可算集合（きのうてきかさんしゅうごう、）は、計算理論または再帰理論におけるある種の集合に付与された名前。自然数の集合 "S" について以下が成り立つ場合、その集合を指して帰納的可算、計算可枚挙、半決定可能、証明可能、チューリング-認識可能などと称する。
あるいは、これと同値だが、
これが半決定可能集合 (semidecidable set) と時に呼ばれるのは前者の条件に由来する。また、計算可枚挙集合（computably enumerable set）という用語は後者の条件に由来する。略して r.e. あるいは c.e. と書くが、これは出版物にもよく出現する。
計算複雑性理論において、全ての帰納的可算集合を包含する複雑性クラスを RE と呼ぶ。再帰理論においては、 包含関係に基づく r.e. 集合の束 (lattice) を formula_1 と書く。
形式的定義.
自然数の集合 "S" について、定義域が "S" と正確に一致するような何らかの部分再帰関数（部分計算可能関数）"f" が存在するとき、"S" は帰納的可算であると言う。つまり "f" が定義される必要十分条件は、"f" への入力が "S" の元であることである。
この定義は任意の可算集合 A に拡張できる。そのためには、A の元をゲーデル数で表し、もし対応するゲーデル数の集合が帰納的可算ならば A の何らかの部分集合が帰納的可算になることを言えば良い。
等価な定式化.
以下は、自然数の集合 "S" について同じ特性を表現したものである。
最後の性質は、最初の定義から単純に導かれるものではないが、ヒルベルトの第10問題を否定的に解決する過程でユーリ・マチャセビッチが発見した。ディオファントス集合は再帰理論に先行しているため、歴史的にはこれが帰納的可算集合の最初の定義であった（ただし、これらが同じものを表していると分かったのは帰納的可算集合が登場してから30年以上も後のことである）。上記の式における束縛変数の個数は、これまでのところ最小とされているもので、もっと少ない個数でディオファントス集合を表せる可能性はある。
特性.
"A" と "B" が共に帰納的可算集合なら、"A" ∩ "B" 、 "A" ∪ "B" 、 "A" × "B" も帰納的可算集合である。部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である。
ある集合が帰納的可算である必要十分条件は、それが算術的階層のレベル formula_12 にあることである。
集合 formula_13 の補集合 formula_14 が帰納的可算である場合、formula_13 は co-r.e. と呼ばれる。同様に、ある集合が co-r.e. である必要十分条件は、それが算術的階層のレベル formula_16 にあることである。
集合 "A" が帰納的（計算可能）である必要十分条件は、"A" と "A" の補集合が共に帰納的可算集合であることである。これは帰納的可算集合の束に於いて帰納的関数のクラスが定義可能であることを示す。（すなわち補元を持つ元が帰納的可算集合である。）ある集合が帰納的である必要十分条件は、その集合が何らかの単調増加な全域再帰関数の値域になっているか、または有限なことである。
互いに素な帰納的可算集合同士の対を取ると、あるものは帰納的分離可能であり、あるものは帰納的分離不可能である。対照的に、任意の互いに素な co-r.e. 集合対が帰納的分離可能であることが、次の性質から示される。
任意の帰納的可算集合 formula_17 に対して、互いに素な帰納的可算集合 formula_18 で formula_19, formula_20, formula_21 なるものが存在する。formula_17 の元を formula_23 と交互に枚挙していく。formula_24 がそれより前に現れないなら formula_25 に置く。また formula_26 がそれより前に現れないなら formula_27 に置く。このとき formula_18 は所望の性質を満たす。
任意の帰納的でない帰納的可算集合は2つの互いに素な帰納的でない帰納的可算集合に直和分解できる。
注意.
チャーチ＝チューリングのテーゼによれば、実効的に計算可能な関数は全てチューリングマシンで計算可能であり、従って集合 "S" が帰納的可算である必要十分条件は、何らかのアルゴリズムで "S" の枚挙ができることである。しかしこれを形式的な定義とすることはできない。何故ならチャーチ＝チューリングのテーゼは形式的な公理ではなく、非形式的な予想だからである。
最近の文献では、帰納的可算集合を全体再帰関数の「値域」ではなく、部分関数の「定義域」として定義する方が一般的である。この理由は、例えばα-再帰理論()のような一般化された再帰理論では、定義域を用いた定義の方が自然だと判ったためである。他の文献では枚挙を使った定義がよく使われるが、これも帰納的可算集合に同値である。