創造的集合と生産的集合

生産的集合(せいさんてきしゅうごう、英: productive set)と創造的集合(そうぞうてきしゅうごう、英: creative set)とは、自然数の集合の類型であり、数理論理学において重要な応用を持つ。これらはSoare (1987)やRogers (1987)などの数理論理学のテキストにおける標準的なトピックである。

以下では ${\displaystyle \varphi _{i}}${\displaystyle \varphi _{i}} は計算可能関数のアクセプタブル・ナンバリング、${\displaystyle W_{i}}${\displaystyle W_{i}} は対応する帰納的可算集合のナンバリングとする。

自然数の集合 ${\displaystyle P}${\displaystyle P} が生産的とは、帰納的(計算可能)関数 ${\displaystyle f}${\displaystyle f} が存在して、任意の ${\displaystyle i}${\displaystyle i} に対して

${\displaystyle W_{i}\subseteq P}${\displaystyle W_{i}\subseteq P} ならば ${\displaystyle f(i)\downarrow }${\displaystyle f(i)\downarrow } かつ ${\displaystyle f(i)\in P\setminus W_{i}}${\displaystyle f(i)\in P\setminus W_{i}}

が成り立つことをいう。このとき関数 ${\displaystyle f}${\displaystyle f} を ${\displaystyle P}${\displaystyle P} の生産的関数という。

自然数の集合 ${\displaystyle C}${\displaystyle C} が創造的とは、${\displaystyle C}${\displaystyle C} が帰納的可算であり、補集合 ${\displaystyle \mathbb {N} \setminus C}${\displaystyle \mathbb {N} \setminus C} が生産的であることをいう。後で述べるように創造的集合は帰納的可算な補集合を持たない。すなわち創造的集合は帰納的でない。

典型的な創造的集合に ${\displaystyle K=\{i\mid i\in W_{i}\}}${\displaystyle K=\{i\mid i\in W_{i}\}} がある。この集合は停止性問題の対角線を表している。この補集合 ${\displaystyle {\bar {K}}=\{i\mid i\notin W_{i}\}}${\displaystyle {\bar {K}}=\{i\mid i\notin W_{i}\}} は生産的関数 ${\displaystyle f(i)=i}${\displaystyle f(i)=i} を持つ生産的集合である: ${\displaystyle W_{i}\subseteq {\bar {K}}}${\displaystyle W_{i}\subseteq {\bar {K}}} と仮定する。このとき ${\displaystyle i\in W_{i}}${\displaystyle i\in W_{i}} ならば ${\displaystyle i\in K}${\displaystyle i\in K} かつ ${\displaystyle i\in {\bar {K}}}${\displaystyle i\in {\bar {K}}} となって不合理。すなわち ${\displaystyle i\notin W_{i}}${\displaystyle i\notin W_{i}}。それゆえ ${\displaystyle i\in {\bar {K}}}${\displaystyle i\in {\bar {K}}}。

生産的集合 ${\displaystyle A}${\displaystyle A} は帰納的可算でない。というのも ${\displaystyle A}${\displaystyle A} が ${\displaystyle W_{i}}${\displaystyle W_{i}} を含むならば、 ${\displaystyle A}${\displaystyle A} は ${\displaystyle W_{i}}${\displaystyle W_{i}} に属さない数を要素として持つからである。もっといえばそのような数は ${\displaystyle i}${\displaystyle i} から実効的に計算できる。同様に、創造的集合は決定可能ではない。なぜならそれの補集合は生産的集合ゆえ帰納的可算でないからである。

任意の生産的集合は単射・全域的な生産的関数を持つ。

Myhill (1955)による次の定理により、ある意味で任意の創造的集合は ${\displaystyle K}${\displaystyle K} に類似しており、任意の生産的集合は ${\displaystyle {\bar {K}}}${\displaystyle {\bar {K}}} に類似している。^[1]

定理. いま ${\displaystyle P}${\displaystyle P} を自然数の集合とする。次は同値:

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

定理. いま ${\displaystyle C}${\displaystyle C} を自然数の集合とする。次は同値:

• ${\displaystyle C}${\displaystyle C} は創造的。
• ${\displaystyle C}${\displaystyle C} は1-完全。
• ${\displaystyle C}${\displaystyle C} は ${\displaystyle K}${\displaystyle K} に再帰同型である。すなわち、全域計算可能な全単射 ${\displaystyle f}${\displaystyle f} が存在して ${\displaystyle f(C)=K}${\displaystyle f(C)=K} が成り立つ。

生産的集合は帰納的可算な無限集合を含むことが分かる。 ${\displaystyle P}${\displaystyle P} を生産的集合、${\displaystyle f}${\displaystyle f} を ${\displaystyle P}${\displaystyle P} の全域的な生産的関数とする。まず帰納的可算集合の指標 ${\displaystyle e_{n}}${\displaystyle e_{n}} を帰納的に

• ${\displaystyle W_{e_{0}}=\varnothing }${\displaystyle W_{e_{0}}=\varnothing }
• ${\displaystyle W_{e_{n+1}}=W_{e_{n}}\cup \{f(e_{n})\}}${\displaystyle W_{e_{n+1}}=W_{e_{n}}\cup \{f(e_{n})\}}

となるように選ぶ。Smn定理よりこの指標の列は(原始)帰納的に取れるので、そのようにしておく。${\displaystyle W_{e_{n}}}${\displaystyle W_{e_{n}}} の構成に関する帰納法により ${\displaystyle W_{e_{n}}\subseteq P}${\displaystyle W_{e_{n}}\subseteq P} が分かる。またここから ${\displaystyle f(e_{n})\notin W_{e_{n}}}${\displaystyle f(e_{n})\notin W_{e_{n}}} が分かる。ゆえに ${\displaystyle W_{e_{n}}}${\displaystyle W_{e_{n}}} はn元集合であり、

${\displaystyle A:=\bigcup _{n\in \mathbb {N} }W_{e_{n}}=\{f(e_{n})|n\in \mathbb {N} \}}${\displaystyle A:=\bigcup _{n\in \mathbb {N} }W_{e_{n}}=\{f(e_{n})|n\in \mathbb {N} \}}

は ${\displaystyle P}${\displaystyle P} に含まれる無限集合である。ところで帰納的集合の帰納的関数による像は帰納的可算であるから、${\displaystyle A}${\displaystyle A} は帰納的可算である。ここから単純集合は創造的でないことが分かる。

算術の標準模型で真な文のコード全体の集合 ${\displaystyle T}${\displaystyle T} は生産的である。というのも第1不完全性定理の系によれば、${\displaystyle W}${\displaystyle W} が ${\displaystyle T}${\displaystyle T} に含まれる帰納的可算集合ならば、${\displaystyle T\setminus W}${\displaystyle T\setminus W} は少なくともひとつ要素(標準模型で真だが証明不能な文)を持ち、それを帰納的に計算できるからである。ところで ${\displaystyle T}${\displaystyle T} の補集合は帰納的可算でない。すなわち ${\displaystyle T}${\displaystyle T} は補集合が創造的でない生産的集合の例となっている。

${\displaystyle T}${\displaystyle T} をロビンソン算術の帰納的拡大で無矛盾とする。すると ${\displaystyle T}${\displaystyle T} で証明可能な文の集合 ${\displaystyle \mathrm {Th} (T)}${\displaystyle \mathrm {Th} (T)} は帰納的可算である。帰納的可算集合 ${\displaystyle A\subseteq \mathbb {N} }${\displaystyle A\subseteq \mathbb {N} } を任意に取る。するとΣ₁集合の数値別表現可能性より、論理式 ${\displaystyle \varphi (x)}${\displaystyle \varphi (x)} が存在して、次が成り立つ:

${\displaystyle n\in A\iff T\vdash \varphi ({\overline {n}})\iff \ulcorner \varphi ({\overline {n}})\urcorner \in \mathrm {Th} (T)}${\displaystyle n\in A\iff T\vdash \varphi ({\overline {n}})\iff \ulcorner \varphi ({\overline {n}})\urcorner \in \mathrm {Th} (T)}

したがって ${\displaystyle f(n)=\ulcorner \varphi ({\overline {n}})\urcorner }${\displaystyle f(n)=\ulcorner \varphi ({\overline {n}})\urcorner } によって ${\displaystyle A}${\displaystyle A} は ${\displaystyle \mathrm {Th} (T)}${\displaystyle \mathrm {Th} (T)} に多対一還元できる。すなわち ${\displaystyle \mathrm {Th} (T)}${\displaystyle \mathrm {Th} (T)} は創造的である。

一般にこのような性質を持つ理論は創造的理論と呼ばれる。Σ₁-弱表現可能性を持つ理論は創造的である。例えばロビンソン算術やZFC集合論は創造的理論である。前述の結果により創造的理論(の定理集合)の間には計算可能な全単射が存在する。この全単射は論理結合子や演繹を保存しない。プール=エルとクリプキはPour-El and Kripke (1967)において任意の創造的理論の間に論理結合子と演繹を保存する計算可能な全単射が存在することを示した。

エミール・ポストの重要な論文Post (1944)において創造的集合と呼ばれる概念が定義された。繰り返しになるが、上で述べた集合 ${\displaystyle K}${\displaystyle K} は創造的集合の例を与える。^[2] この集合は1変数部分計算可能関数の枚挙の対角線 ${\displaystyle d(x)=\varphi _{x}(x)+1}${\displaystyle d(x)=\varphi _{x}(x)+1} の定義域として定義できる。ポストは創造的集合を用いたゲーデルの不完全性定理の版を与えた。元々の証明において、ゲーデルは大雑把にいえば "私はこの理論からは証明不能である" ことを意味する文を構成し、これが証明も反証もできないことを証明した。ポストは彼の不完全性定理に次のことを付け加えた:

"数学的命題の本体を固定したとしても、数学的思考は本質的に創造的なままであり、これを避けることができないということを結論付ける。"^[2]

対角線関数 ${\displaystyle d}${\displaystyle d} を用いて定義された基本的な創造的集合 ${\displaystyle K}${\displaystyle K} は独自の歴史的発展を持つ。アラン・チューリングのチューリング機械に関する1936年の論文は ${\displaystyle \Phi }${\displaystyle \Phi } 関数を計算する万能チューリング計算機の存在を示した。関数 ${\displaystyle \Phi }${\displaystyle \Phi } は ${\displaystyle \Phi (e,x)=}${\displaystyle \Phi (e,x)=} (コード e を持つチューリング機械に入力 x を与えて実行した結果) と定義される。万能という意味は、任意の計算可能な関数 ${\displaystyle f}${\displaystyle f} は ${\displaystyle f(x)=\Phi (e,x)}${\displaystyle f(x)=\Phi (e,x)} の形で書くことができるということである。ここで ${\displaystyle e}${\displaystyle e} は ${\displaystyle f}${\displaystyle f} を計算するチューリング機械のコードである。上の記法によれば ${\displaystyle \Phi (e,x)=\varphi _{e}(x)}${\displaystyle \Phi (e,x)=\varphi _{e}(x)} であり、対角線関数は自然に ${\displaystyle d(x)=\varphi _{x}(x)+1}${\displaystyle d(x)=\varphi _{x}(x)+1} と現れてくる。いま ${\displaystyle K}${\displaystyle K} が計算可能だと仮定しよう。すると ${\displaystyle K}${\displaystyle K} 上では ${\displaystyle d}${\displaystyle d} に一致し、${\displaystyle K}${\displaystyle K} の外側ではゼロであるような全域計算可能関数 ${\displaystyle {\tilde {d}}}${\displaystyle {\tilde {d}}} が考えられる。ところが ${\displaystyle {\tilde {d}}}${\displaystyle {\tilde {d}}} はどの部分計算可能関数とも対角線で異なっている。これは ${\displaystyle {\tilde {d}}}${\displaystyle {\tilde {d}}} が計算可能ということと矛盾する。したがって ${\displaystyle K}${\displaystyle K} は計算可能でない。このことは停止性問題の決定不可能性を示す。究極的にはこれらのアイデアはチャーチ・チューリングのテーゼに関係する。このテーゼは計算可能関数の概念が直観的な意味で実効的に計算可能な関数の概念の正確な形式化であることを述べる。このことは証明や反証のできる事柄ではない。チャーチのラムダ計算、チューリングの理想化された計算機、後のポストのアプローチなどは全て同値である。

• 単純集合
• 帰納的可算集合
• 多対一還元

• Davis, Martin (1958), Computability and unsolvability, Series in Information Processing and Computers, New York: McGraw-Hill, MR 0124208  . Reprinted in 1982 by Dover Publications.
• Enderton, Herbert B. (2010), Computability Theory: An Introduction to Recursion Theory, Academic Press, ISBN 978-0-12-384958-8  .
• Kleene, Stephen Cole (2002), Mathematical logic, Mineola, NY: Dover Publications Inc., ISBN 0-486-42533-9, MR 1950307  . Reprint of the 1967 original, Wiley, MR 0216930.
• Myhill, John (1955), "Creative sets", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 1: 97–108, doi:10.1002/malq.19550010205, MR 0071379  .
• Post, Emil L. (1944), "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society 50 (5): 284–316, doi:10.1090/S0002-9904-1944-08111-1, MR 0010514  
• Rogers, Hartley, Jr. (1987), Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, MR 886890  .
• Soare, Robert I. (1987), Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Berlin: Springer-Verlag, ISBN 3-540-15299-7, MR 882921  .
• Pour-El, Marian B.; Kripke, Saul (1967), "Deduction-preserving "recursive isomorphisms" between theories", Bulletin of the American Mathematical Society 73 (1): 145-148, doi:10.1090/S0002-9904-1967-11689-6, MR 0215713  .

• 計算可能性理論
• 数学に関する記事