数理論理学における応用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/02/16 15:39 UTC 版)
「創造的集合と生産的集合」の記事における「数理論理学における応用」の解説
算術の標準模型で真な文のコード全体の集合 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)} が存在して、次が成り立つ： n ∈ A ⟺ T ⊢ φ ( n ¯ ) ⟺ ⌜ φ ( n ¯ ) ⌝ ∈ T h ( T ) {\displaystyle n\in A\iff T\vdash \varphi ({\overline {n}})\iff \ulcorner \varphi ({\overline {n}})\urcorner \in \mathrm {Th} (T)} したがって f ( n ) = ⌜ φ ( n ¯ ) ⌝ {\displaystyle f(n)=\ulcorner \varphi ({\overline {n}})\urcorner } によって A {\displaystyle A} は T h ( T ) {\displaystyle \mathrm {Th} (T)} に多対一還元できる。すなわち T h ( T ) {\displaystyle \mathrm {Th} (T)} は創造的である。 一般にこのような性質を持つ理論は創造的理論と呼ばれる。Σ1-弱表現可能性を持つ理論は創造的である。例えばロビンソン算術やZFC集合論は創造的理論である。前述の結果により創造的理論(の定理集合)の間には計算可能な全単射が存在する。この全単射は論理結合子や演繹を保存しない。プール＝エルとクリプキはPour-El and Kripke (1967)において任意の創造的理論の間に論理結合子と演繹を保存する計算可能な全単射が存在することを示した。
※この「数理論理学における応用」の解説は、「創造的集合と生産的集合」の解説の一部です。
「数理論理学における応用」を含む「創造的集合と生産的集合」の記事については、「創造的集合と生産的集合」の概要を参照ください。
- 数理論理学における応用のページへのリンク
