創造的集合と生産的集合

生産的集合（せいさんてきしゅうごう、）と創造的集合（そうぞうてきしゅうごう、）とは、自然数の集合の類型であり、数理論理学において重要な応用を持つ。これらはやなどの数理論理学のテキストにおける標準的なトピックである。
定義と例.
以下では formula_1 は計算可能関数のアクセプタブル・ナンバリング、formula_2 は対応する帰納的可算集合のナンバリングとする。
自然数の集合 formula_3 が生産的とは、帰納的（計算可能）関数 formula_4 が存在して、任意の formula_5 に対して
が成り立つことをいう。このとき関数 formula_4 を formula_3 の生産的関数という。
自然数の集合 formula_11 が創造的とは、formula_11 が帰納的可算であり、補集合 formula_13 が生産的であることをいう。後で述べるように創造的集合は帰納的可算な補集合を持たない。すなわち創造的集合は帰納的でない。
典型的な創造的集合に formula_14 がある。この集合は停止性問題の対角線を表している。この補集合 formula_15 は生産的関数 formula_16 を持つ生産的集合である： formula_17 と仮定する。このとき formula_18 ならば formula_19 かつ formula_20 となって不合理。すなわち formula_21。それゆえ formula_20。
性質.
生産的集合 formula_23 は帰納的可算でない。というのも formula_23 が formula_2 を含むならば、 formula_26 は formula_2 に属さない数を要素として持つからである。もっといえばそのような数は formula_5 から実効的に計算できる。同様に、創造的集合は決定可能ではない。なぜならそれの補集合は生産的集合ゆえ帰納的可算でないからである。
任意の生産的集合は単射・全域的な生産的関数を持つ。
による次の定理により、ある意味で任意の創造的集合は formula_29 に類似しており、任意の生産的集合は formula_30 に類似している。
定理. いま formula_3 を自然数の集合とする。次は同値：
定理. いま formula_11 を自然数の集合とする。次は同値：
生産的集合は帰納的可算な無限集合を含むことが分かる。 formula_3 を生産的集合、formula_4 を formula_3 の全域的な生産的関数とする。まず帰納的可算集合の指標 formula_47 を帰納的に
となるように選ぶ。Smn定理よりこの指標の列は（原始）帰納的に取れるので、そのようにしておく。formula_50 の構成に関する帰納法により formula_51 が分かる。またここから formula_52 が分かる。ゆえに formula_50 はn元集合であり、
は formula_3 に含まれる無限集合である。ところで帰納的集合の帰納的関数による像は帰納的可算であるから、formula_23 は帰納的可算である。ここから単純集合は創造的でないことが分かる。
数理論理学における応用.
算術の標準模型で真な文のコード全体の集合 formula_57 は生産的である。というのも第1不完全性定理の系によれば、formula_58 が formula_57 に含まれる帰納的可算集合ならば、formula_60 は少なくともひとつ要素（標準模型で真だが証明不能な文）を持ち、それを帰納的に計算できるからである。ところで formula_57 の補集合は帰納的可算でない。すなわち formula_57 は補集合が創造的でない生産的集合の例となっている。
formula_57 をロビンソン算術の帰納的拡大で無矛盾とする。すると formula_57 で証明可能な文の集合 formula_65 は帰納的可算である。帰納的可算集合 formula_66 を任意に取る。するとΣ1集合の数値別表現可能性より、論理式 formula_67 が存在して、次が成り立つ：
したがって formula_69 によって formula_23 は formula_65 に多対一還元できる。すなわち formula_65 は創造的である。
一般にこのような性質を持つ理論は創造的理論と呼ばれる。Σ1-弱表現可能性を持つ理論は創造的である。例えばロビンソン算術やZFC集合論は創造的理論である。前述の結果により創造的理論(の定理集合)の間には計算可能な全単射が存在する。この全単射は論理結合子や演繹を保存しない。プール＝エルとクリプキはにおいて任意の創造的理論の間に論理結合子と演繹を保存する計算可能な全単射が存在することを示した。
歴史.
エミール・ポストの重要な論文において創造的集合と呼ばれる概念が定義された。繰り返しになるが、上で述べた集合 formula_29 は創造的集合の例を与える。この集合は1変数部分計算可能関数の枚挙の対角線 formula_74 の定義域として定義できる。ポストは創造的集合を用いたゲーデルの不完全性定理の版を与えた。元々の証明において、ゲーデルは大雑把にいえば "私はこの理論からは証明不能である" ことを意味する文を構成し、これが証明も反証もできないことを証明した。ポストは彼の不完全性定理に次のことを付け加えた：
"数学的命題の本体を固定したとしても、数学的思考は本質的に創造的なままであり、これを避けることができないということを結論付ける。"
対角線関数 formula_75 を用いて定義された基本的な創造的集合 formula_76 は独自の歴史的発展を持つ。アラン・チューリングのチューリング機械に関する1936年の論文は formula_77 関数を計算する万能チューリング計算機の存在を示した。関数 formula_77 は formula_79 (コード "e" を持つチューリング機械に入力 "x" を与えて実行した結果) と定義される。万能という意味は、任意の計算可能な関数 formula_4 は formula_81 の形で書くことができるということである。ここで formula_82 は formula_4 を計算するチューリング機械のコードである。上の記法によれば formula_84 であり、対角線関数は自然に formula_74 と現れてくる。いま formula_29 が計算可能だと仮定しよう。すると formula_29 上では formula_75 に一致し、formula_29 の外側ではゼロであるような全域計算可能関数 formula_90 が考えられる。ところが formula_90 はどの部分計算可能関数とも対角線で異なっている。これは formula_90 が計算可能ということと矛盾する。したがって formula_29 は計算可能でない。このことは停止性問題の決定不可能性を示す。究極的にはこれらのアイデアはチャーチ・チューリングのテーゼに関係する。このテーゼは計算可能関数の概念が直観的な意味で実効的に計算可能な関数の概念の正確な形式化であることを述べる。このことは証明や反証のできる事柄ではない。チャーチのラムダ計算、チューリングの理想化された計算機、後のポストのアプローチなどは全て同値である。