創造的集合と生産的集合のソースを表示

'''生産的集合'''（せいさんてきしゅうごう、{{Lang-en-short|productive set}}）と'''創造的集合'''（そうぞうてきしゅうごう、{{Lang-en-short|creative set}}）とは、[[自然数]]の集合の類型であり、[[数理論理学]]において重要な応用を持つ。これらは{{harvtxt|Soare|1987}}や{{harvtxt|Rogers|1987}}などの数理論理学のテキストにおける標準的なトピックである。

==定義と例==

以下では <math>\varphi_i</math> は[[計算可能関数]]の[[ナンバリング_(計算可能性理論)|アクセプタブル・ナンバリング]]、<math>W_i</math> は対応する[[帰納的可算]]集合のナンバリングとする。

自然数の集合 <math>P</math> が'''生産的'''とは、帰納的（計算可能）関数 <math>f</math> が存在して、任意の <math>i</math> に対して
:<math>W_i \subseteq P</math> ならば <math>f(i)\downarrow</math> かつ <math>f(i) \in P \setminus W_i</math>
が成り立つことをいう。このとき関数 <math>f</math> を <math>P</math> の'''生産的関数'''という。

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

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

== 性質 ==

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

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

{{harvtxt|Myhill|1955}}による次の定理により、ある意味で任意の創造的集合は <math>K</math> に類似しており、任意の生産的集合は <math>\bar{K}</math> に類似している。<ref>{{harvtxt|Soare|1987}}; {{harvtxt|Rogers|1987}}.</ref>

'''定理.''' いま <math>P</math> を自然数の集合とする。次は同値：
*<math>P</math> は生産的。
*<math>\bar{K}</math> は <math>P</math> に[[多対一還元|1-還元]]可能。
*<math>\bar{K}</math> は <math>P</math> に[[多対一還元|m-還元]]可能。

'''定理.'''  いま <math>C</math> を自然数の集合とする。次は同値：
*<math>C</math> は創造的。
*<math>C</math> は[[多対一還元|1-完全]]。
*<math>C</math> は <math>K</math> に[[再帰同型]]である。すなわち、全域計算可能な[[全単射]] <math>f</math> が存在して <math>f(C)=K</math> が成り立つ。

生産的集合は帰納的可算な無限集合を含むことが分かる。 <math>P</math> を生産的集合、<math>f</math> を <math>P</math> の全域的な生産的関数とする。まず帰納的可算集合の指標 <math>e_n</math> を帰納的に
*<math>W_{e_0}=\varnothing</math>
*<math>W_{e_{n+1}}=W_{e_n} \cup \{ f(e_n) \} </math>
となるように選ぶ。[[Smn定理]]よりこの指標の列は（原始）帰納的に取れるので、そのようにしておく。<math>W_{e_n}</math> の構成に関する帰納法により <math>W_{e_n}\subseteq P</math> が分かる。またここから <math>f(e_n) \notin W_{e_n}</math> が分かる。ゆえに <math>W_{e_n}</math> はn元集合であり、
:<math>A := \bigcup_{n \in \mathbb{N}}W_{e_n} = \{ f(e_n) | n \in \mathbb{N} \}</math>
は <math>P</math> に含まれる無限集合である。ところで帰納的集合の帰納的関数による像は帰納的可算であるから、<math>A</math> は帰納的可算である。ここから[[単純集合]]は創造的でないことが分かる。

== 数理論理学における応用 ==

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

<math>T</math> を[[ロビンソン算術]]の帰納的拡大で無矛盾とする。すると <math>T</math> で証明可能な文の集合 <math>\mathrm{Th}(T)</math> は帰納的可算である。帰納的可算集合 <math>A \subseteq \mathbb{N}</math> を任意に取る。すると&Sigma;<sub>1</sub>集合の数値別表現可能性より、論理式 <math>\varphi(x)</math> が存在して、次が成り立つ：
: <math>n \in A \iff T \vdash \varphi(\overline{n}) \iff \ulcorner \varphi(\overline{n}) \urcorner \in \mathrm{Th}(T)</math>
したがって <math>f(n) = \ulcorner \varphi(\overline{n}) \urcorner</math> によって <math>A</math> は <math>\mathrm{Th}(T)</math> に多対一還元できる。すなわち <math>\mathrm{Th}(T)</math> は創造的である。

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

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

"数学的命題の本体を固定したとしても、数学的思考は本質的に創造的なままであり、これを避けることができないということを結論付ける。"<ref name = "test" />

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

==関連項目==
*[[単純集合]]
*[[帰納的可算集合]]
*[[多対一還元]]

== 注釈 ==
{{reflist}}

== 参考文献 ==
*{{citation
 | last = Davis | first = Martin | authorlink = Martin Davis
 | location = New York
 | mr = 0124208
 | publisher = McGraw-Hill
 | series = Series in Information Processing and Computers
 | title = Computability and unsolvability
 | year = 1958}}. Reprinted in 1982 by Dover Publications.
*{{citation
 | last = Enderton | first = Herbert B. | author-link = Herbert Enderton
 | isbn = 978-0-12-384958-8
 | publisher = Academic Press
 | title = Computability Theory: An Introduction to Recursion Theory
 | year = 2010}}.
*{{citation
 | last = Kleene | first = Stephen Cole | authorlink = Stephen Cole Kleene
 | isbn = 0-486-42533-9
 | location = Mineola, NY
 | mr = 1950307
 | publisher = Dover Publications Inc.
 | title = Mathematical logic
 | year = 2002}}. Reprint of the 1967 original, Wiley, {{MR|0216930}}.
*{{citation
 | last = Myhill | first = John | authorlink = John Myhill
 | doi = 10.1002/malq.19550010205
 | journal = Zeitschrift für Mathematische Logik und Grundlagen der Mathematik
 | mr = 0071379
 | pages = 97–108
 | title = Creative sets
 | volume = 1
 | year = 1955}}.
*{{Citation
| last  = Post
| first = Emil L.
| authorlink = Emil Leon Post
| title = Recursively enumerable sets of positive integers and their decision problems
| journal = Bulletin of the American Mathematical Society
| volume  = 50
| issue   = 5
| year    = 1944
| pages   = 284–316
| doi = 10.1090/S0002-9904-1944-08111-1
| mr = 0010514
}}
*{{citation
 | last = Rogers | first = Hartley, Jr. | author-link = Hartley Rogers, Jr.
 | edition = 2nd
 | isbn = 0-262-68052-1
 | location = Cambridge, MA
 | mr = 886890
 | publisher = MIT Press
 | title = Theory of recursive functions and effective computability
 | year = 1987}}. 
*{{citation
 | last = Soare | first = Robert I. | author-link = Robert I. Soare
 | isbn = 3-540-15299-7
 | location = Berlin
 | mr = 882921
 | publisher = Springer-Verlag
 | series = Perspectives in Mathematical Logic
 | title = Recursively enumerable sets and degrees: A study of computable functions and computably generated sets
 | year = 1987}}.
*{{citation
 | last1 = Pour-El | first1 = Marian B. | author-link = Marian Boykan Pour-El
 | last2 = Kripke | first2 = Saul | author2-link = Saul Kripke
 | title = Deduction-preserving “recursive isomorphisms” between theories
 | journal = Bulletin of the American Mathematical Society
 | volume  = 73
 | issue = 1
 | year = 1967
 | pages = 145-148
 | doi = 10.1090/S0002-9904-1967-11689-6 
 | mr = 0215713}}.

{{DEFAULTSORT:そうそうてきしゆうこうとせいさんてきしゆうこう}}
[[Category:計算可能性理論]]
[[Category:数学に関する記事]]