創造的で生産性の高いセット

計算可能性理論において、生成集合と創造集合は、数理論理学において重要な応用を持つ自然数の集合の一種である。これらは、Soare (1987) や Rogers (1987) などの数理論理学の教科書の標準的なトピックである。

この記事の残りの部分では、 が計算可能関数の許容される番号付けであり、W _{i が}再帰的に列挙可能な集合の対応する番号付けであると仮定します。 ${\displaystyle \varphi_{i}}$

自然数の集合Aが生産的であるとは、すべての に対して となる全再帰的（計算可能）関数が存在するときである。 となる関数はに対して生産的関数と呼ばれる。${\displaystyle f}$${\displaystyle i\in \mathbb {N} }$${\displaystyle W_{i}\subseteq A}$${\displaystyle f(i)\in A\setminus W_{i}.}$${\displaystyle f}$${\displaystyle A.}$

自然数の集合A は、 Aが再帰的に列挙可能であり、その補集合が生成的である場合に創造的であると呼ばれます。ただし、以下に示すように、すべての生成集合に再帰的に列挙可能な補集合があるわけではありません。 ${\displaystyle \mathbb {N} \setminus A}$

典型的な創造的集合は、停止問題 を表す集合である。その補集合は生産的であり、生産関数f ( i ) = i (恒等関数) を持つ。 ${\displaystyle K=\{i\mid i\in W_{i}\}}$${\displaystyle {\bar {K}}=\{i\mid i\not \in W_{i}\}}$

これを理解するために、生産関数の定義を適用し、と を別々に示します。 ${\displaystyle i\in {\bar {K}}}$${\displaystyle i\not \in W_{i}}$

• ${\displaystyle i\in {\bar {K}}}$: と仮定すると、 となるので、これは矛盾を生じます。したがって。${\displaystyle i\in K}$${\displaystyle i\in W_{i}}$${\displaystyle W_{i}\subseteq {\bar {K}}}$${\displaystyle i\in {\bar {K}}}$${\displaystyle i\in {\bar {K}}}$
• ${\displaystyle i\not \in W_{i}}$: 実際、 であれば が真になりますが、前のポイントでその逆を実証しました。つまり です。${\displaystyle i\in W_{i}}$${\displaystyle i\in K}$${\displaystyle i\not \in W_{i}}$

生成集合A は再帰的に列挙できません。なぜなら、A が再集合W _iのすべての数を含んでいるときはいつでも、他の数も含まれており、さらに、インデックスiからそのような数の例を生成する効果的な手順があるからです。同様に、創造集合は決定可能ではありません。なぜなら、決定可能だとすると、その補集合である生成集合が再帰的に列挙可能であることを意味するからです。

任意の生成集合は、単射かつ全である生成関数を持ちます。

マイヒル（1955）による以下の定理は、ある意味ですべての創造集合は似ており、すべての生産集合は似ていることを示しています。^[1]${\displaystyle K}$${\displaystyle {\bar {K}}}$

定理。Pを自然数の集合と します。以下は同値です。

• Pは生産的です。
• ${\displaystyle {\bar {K}}}$はPに1 還元可能である。
• ${\displaystyle {\bar {K}}}$はPにm 還元可能である。

定理。Cを自然数の集合と します。以下は同値です。

• Cは創造的です。
• Cは1完全である
• C はKと再帰的に同型です。つまり、f ( C ) = Kとなるような自然数上の全計算可能な一対一写像fが存在します。

有効な公理系におけるすべての証明可能文の集合は、常に再帰的に可算な集合である。系が一階算術のように適度に複雑であれば、系内の真の文のゲーデル数の集合Tは生成的集合となる。つまり、W が真の文の再帰的に可算な集合である場合はいつでも、 Wに含まれない真の文が少なくとも 1 つ存在する。再帰的に可算な集合は生成的ではないため、これを使用してゲーデルの第 1 不完全性定理を厳密に証明できる。集合Tの補集合は再帰的に可算ではないため、T は補集合が創造的ではない生成的集合の例である。

ポストの独創的な論文 (1944) は、彼が創造集合と呼ぶ概念を定義しました。繰り返しになりますが、上で参照され、列挙されたすべての 1 位計算可能部分関数の対角線を取り、それらに 1 を加える関数のドメインとして定義される集合は、創造集合の例です。^[2]ポストは、ゲーデルの不完全性定理のバージョンを彼の創造集合を使用して示しました。ここで、もともとゲーデルは、ある意味で「私はこの公理理論では証明不可能である」と自由に翻訳できる文を構築していました。しかし、ゲーデルの証明は真の文の概念からではなく、むしろ無矛盾な理論の概念を使用しており、これが第2 の不完全性定理につながりました。ポストは、不完全性の彼自身のバージョンを完成させた後、次のことを付け加えました。 ${\displaystyle K}$${\displaystyle d(x)=[[x]](x)+1}$

「数学的命題のこのように固定され、明確に定義された集合体であっても、数学的思考は本質的に創造的であり、そしてそうあり続けなければならないという結論は避けられない。」^[2]

対角関数を使用して定義される通常の創造的なセットには、独自の歴史的発展があります。アラン・チューリングは、1936 年のチューリング マシンに関する記事で、関数を計算する汎用コンピュータの存在を示しました。関数 は、 (によってコード化された命令を入力 に適用した結果)となるように定義され 、 の命令をコード化するすべての に対して、計算可能な部分関数がすべてで与えられるという意味で汎用的です。上記の表記 、および を使用すると、対角関数 はごく自然に として生じます。最終的に、これらのアイデアは、計算可能な部分関数という数学的概念は、証明も反証もできない、実質的に計算可能な部分関数の正しい形式化であるというチャーチのテーゼにつながります。チャーチはラムダ計算、チューリングは理想化されたコンピュータ 、後にエミール・ポストはそのアプローチで使用しましたが、これらはすべて同等です。 ${\displaystyle K}$${\displaystyle d(x)}$${\displaystyle \Phi}$${\displaystyle \Phi}$${\displaystyle \Phi (w,x)=}$ ${\displaystyle w}$ ${\displaystyle x}$${\displaystyle f}$${\displaystyle f(x)=\Phi (e,x)}$${\displaystyle x}$${\displaystyle e}$${\displaystyle f}$${\displaystyle \Phi (e,x)=[[e]](x)}$${\displaystyle d(x)=[[x]](x)+1}$

デボラ・ジョセフとポール・ヤング（1985）は、計算複雑性理論において類似の概念である多項式創造性を定式化し、それを用いてNP完全集合の同型性に関するバーマン・ハルトマニス予想に対する潜在的な反例を提供した。

• デイビス、マーティン（1958）、計算可能性と解決不可能性、情報処理とコンピュータシリーズ、ニューヨーク：マグロウヒル、MR  01242081982年にDover Publicationsから再版されました。
• エンダートン、ハーバート B. (2010)、計算可能性理論：再帰理論入門、アカデミック プレス、ISBN 978-0-12-384958-8。
• ジョセフ、デボラ; ヤング、ポール (1985)、「NP における非多項式および非完全集合の証人関数に関するいくつかのコメント」、理論計算機科学、39 (2–3): 225–237、doi : 10.1016/0304-3975(85)90140-9、MR  0821203
• クリーネ、スティーブン・コール（2002）、数学論理、ミネオラ、ニューヨーク州：ドーバー出版、ISBN 0-486-42533-9、MR  19503071967 年のオリジナルの再版、Wiley、MR 0216930。
• Myhill、John (1955)、「クリエイティブ セット」、Zeitschrift für Mathematische Logik und Grundlagen der Mathematik、1 (2): 97–108、doi :10.1002/malq.19550010205、MR  0071379。
• ポスト、エミール L. (1944)、「正の整数の再帰的に列挙可能な集合とその決定問題」、アメリカ数学会誌、50 (5): 284–316、doi : 10.1090/S0002-9904-1944-08111-1、MR  0010514
• ロジャース、ハートリー・ジュニア（1987）、再帰関数と実効計算可能性の理論（第2版）、ケンブリッジ、マサチューセッツ州：MITプレス、ISBN 0-262-68052-1、MR  0886890。
• Soare, Robert I. (1987)、「再帰的に列挙可能な集合と次数：計算可能関数と計算可能生成集合の研究」、Perspectives in Mathematical Logic、ベルリン：Springer-Verlag、ISBN 3-540-15299-7、MR  0882921。