創造的集合と生産的集合
以下では φ i {\displaystyle \varphi _{i}} は計算可能関数のアクセプタブル・ナンバリング、 W i {\displaystyle W_{i}} は対応する帰納的可算集合のナンバリングとする。
自然数の集合 P {\displaystyle P} が生産的とは、帰納的(計算可能)関数 f {\displaystyle f} が存在して、任意の i {\displaystyle i} に対して
W i ⊆ P {\displaystyle W_{i}\subseteq P} ならば f ( i ) ↓ {\displaystyle f(i)\downarrow } かつ f ( i ) ∈ P ∖ W i {\displaystyle f(i)\in P\setminus W_{i}}
が成り立つことをいう。このとき関数 f {\displaystyle f} を P {\displaystyle P} の生産的関数という。
自然数の集合 C {\displaystyle C} が創造的とは、 C {\displaystyle C} が帰納的可算であり、補集合 N ∖ C {\displaystyle \mathbb {N} \setminus C} が生産的であることをいう。
算術の標準模型で真な文のコード全体の集合 T {\displaystyle T} は生産的である。というのも第1不完全性定理の系によれば、 W {\displaystyle W} が T {\displaystyle T} に含まれる帰納的可算集合ならば、 T ∖ W {\displaystyle T\setminus W} は少なくともひとつ要素(標準模型で真だが証明不能な文)を持ち、それを帰納的に計算できるからである。ところで T {\displaystyle T} の補集合は帰納的可算でない。すなわち T {\displaystyle T} は補集合が創造的でない生産的集合の例となっている。
T {\displaystyle T} をロビンソン算術の帰納的拡大で無矛盾とする。すると T {\displaystyle T} で証明可能な文の集合 T h ( T ) {\displaystyle \mathrm {Th} (T)} は帰納的可算である。帰納的可算集合 A ⊆ N {\displaystyle A\subseteq \mathbb {N} } を任意に取る。するとΣ1集合の数値別表現可能性より、論理式 φ ( x ) {\displaystyle \varphi (x)} が存在して、次が成り立つ:
生産的集合(せいさんてきしゅうごう、英: productive set)と創造的集合(そうぞうてきしゅうごう、英: creative set)とは、自然数の集合の類型であり、数理論理学において重要な応用を持つ。これらはSoare (1987)やRogers (1987)などの数理論理学のテキストにおける標準的なトピックである。
エミール・ポストの重要な論文Post (1944)において創造的集合と呼ばれる概念が定義された。繰り返しになるが、上で述べた集合 K {\displaystyle K} は創造的集合の例を与える。この集合は1変数部分計算可能関数の枚挙の対角線 d ( x ) = φ x ( x ) + 1 {\displaystyle d(x)=\varphi _{x}(x)+1} の定義域として定義できる。ポストは創造的集合を用いたゲーデルの不完全性定理の版を与えた。元々の証明において、ゲーデルは大雑把にいえば "私はこの理論からは証明不能である" ことを意味する文を構成し、これが証明も反証もできないことを証明した。ポストは彼の不完全性定理に次のことを付け加えた:
"数学的命題の本体を固定したとしても、数学的思考は本質的に創造的なままであり、これを避けることができないということを結論付ける。"
対角線関数 d {\displaystyle d} を用いて定義された基本的な創造的集合 K {\displaystyle K} は独自の歴史的発展を持つ。