ロビンソン算術

数理論理学においてロビンソン算術(英: Robinson arithmetic)あるいはQとはペアノ算術(PA)の有限部分理論であり、Robinson (1950)において最初に導入された。Qは本質的にはPAから帰納法の公理図式を取り除いたものである。それゆえQはPAよりも弱いが同一の言語を持つ不完全な理論である。Qは重要かつ興味深い対象である。というのもQは本質的決定不能かつ有限公理化可能なPAの部分理論だからである。

公理

Qの基盤となる理論は等号付き一階述語論理である。言語は次の構成要素からなる：

• 単項関数記号: 後者 [math]S[/math]
• 二項関数記号: 加法 [math]+[/math] と乗法 [math]\cdot[/math]

次に示すQ'の公理(Q1)–(Q7)はBurgess (2005)による。束縛されていない変数記号は暗黙的に全称量化されているものと考える。すなわちQは以下に示す論理式の全称閉包を公理とする：

1. [math]Sx \neq 0[/math]
   • 0 は他の数の後者ではない。
2. [math]Sx=Sy \to x=y[/math]
   • もし [math]x[/math] と [math]y[/math] の後者が等しいならば [math]x[/math] と [math]y[/math] も等しい。すなわち [math]S[/math] (の解釈)は単射である。(1)と(2)より [math]S[/math] (の解釈)はドメインから [math]0[/math] (の解釈)を除いた集合への単射である。すなわちドメインはデデキント無限である。
3. [math]y = 0 \vee \exists x (Sx=y)[/math]
   • 任意の数は [math]0[/math] であるか別の数の後者である。PAではこの公理は数学的帰納法の公理図式から導くことができるが、Qはこれを持たないので公理として採用しなければならない。
4. [math]x+0=x[/math]
5. [math]x+Sy=S(x+y)[/math]
   • (4)と(5)は加法の再帰的定義である。
6. [math]x\cdot 0 = 0[/math]
7. [math]x \cdot Sy = x\cdot y + x[/math]
   • (6)と(7)は乗法の再帰的定義である。

別の公理化

Robinsonによる公理化(Robinson (1950))ではQは公理(Q1)–(Q13)からなる(Mendelson (1997: 201))。最初の6つの公理は基盤となる公理が等号を含まないことから要求されるものである。Machoverによる公理化では前述の公理(Q3)を次のように分割する(Machover and Moshe (1996))。

通常の狭義の全順序 [math]\lt [/math] は加法を用いて次のように形式的には定義できる(Burgess (2005)) （全順序性が証明できるわけではない）：

[math]x \lt y \leftrightarrow \exists z(x+Sz = y)[/math]

上のようにして定義された [math]\lt [/math] について次の基本的な要請を公理として(Q1)–(Q7)の後に加える：

• [math] \neg x \lt 0[/math]
• [math]0 = x \vee 0 \lt x[/math]
• [math]x \lt y \leftrightarrow Sx \lt y \vee Sx = y[/math]
• [math]x \lt Sy \leftrightarrow x \lt y \vee x = y[/math]

別の公理化で [math]\lt [/math] を用いたものは Shoenfield (1967: 22) において見られる。

不完全性

Qにおいて加法の交換法則 [math]\forall x\forall y (x+y=y+x)[/math] が証明不能であることを証明する。これによりQが不完全であることを示せる。それにはQのモデルで加法の交換法則が不成立であるようなものを構成すればよい。まずドメインとして

[math]\mathbb{N} \cup \{a, b\}[/math]

を取る。ここで [math]a,b[/math] は相異なる不定元である。関数記号の解釈は [math]\mathbb N[/math] 上では通常通りに定める。ただし [math]a,b[/math] に対しては次のように定める。まず後者関数の解釈を

[math]Sa = b[/math]

[math]Sb = a[/math]

で定める。この解釈のもとで(Q1)–(Q3)を満たす。あとは(Q4)–(Q7)を満たすように加法と乗法を適当に解釈すればよい。例えば加法は次のように解釈する（ここで [math]n[/math] は任意の自然数とする）：

[math]a + n = \begin{cases} a & \mbox{if }n\equiv 0 \mod 2 \\ b & \mbox{if }n \equiv 1 \mod 2 \end{cases} [/math]

[math]b + n = \begin{cases} b & \mbox{if }n\equiv 0 \mod 2 \\ a & \mbox{if }n \equiv 1 \mod 2 \end{cases} [/math]

[math]n + a = a[/math]

[math]n + b = b[/math]

[math]a + a = a[/math]

[math]a + b = b[/math]

[math]b + a = a[/math]

[math]b + b = b[/math]

その他、積を定義することによりQのモデルが得られるが、ここでは加法の交換法則が成立しない。例えば [math]a + b = b \neq a = b + a[/math] である。したがって健全性定理によりQにおいては加法の交換法則が証明できない。

超数学

超数学におけるQについてはBoolos (2002), Tarski et al. (1953), Smullyan (1991), Mendelson (1997), Burgess (2005)などを見よ。Qの標準的な解釈は自然数に通常の算術を考えたものである。すなわちテンプレート:Clarify加法と乗法は通常の意味を持ち、等号は同値性を意味する。また定数記号 [math]0[/math] は自然数のゼロに、 [math]S[/math] は [math]+1[/math] にそれぞれ解釈される。

QはPAと同様に任意の無限濃度の超準モデルを持つ。しかしながらQはPAと異なりテンネンバウムの定理を適用することができない。すなわちQは計算可能な超準モデルを持つ。例えば、計算可能なQの超準モデルとして最高次係数が正である整数係数多項式の全体に通常の演算を入れたものが考えられる。

Qの特徴は帰納法の公理図式の不在にある。すなわちQはしばしば個々の具体的な自然数に対する事実を証明することが可能であるが、任意の自然数に対する普遍的な事実の多くを証明できない。正確にいえばQは量化子を持たない真な論理式、真な有界論理式、真なΣ₁論理式は証明できるが、真なΠ₁論理式は必ずしも証明できない。例えば 5 + 7 = 7 + 5 はQで証明可能だが、一般的な言明 x + y = y + x は証明できない。同様に Sx ≠ x は証明できない(Burgess (2005))。

Qは公理系ZFCのある部分理論で解釈できる。詳しくいえば外延性の公理、空集合の公理、対の公理を持てばよい。この公理はS'(Tarski et al. (1953))やST(Burgess (2005))などという。詳しくは一般集合論を見よ。

Qの状況は非常に複雑である。QはPAよりも弱い有限公理化可能な一階の理論と考えられ、それらの公理は存在量化をただひとつ持ち、PAが不完全であるのと同様にゲーデルの不完全性定理の意味で不完全であり、本質的に決定不能である。ロビンソンは(Robinson (1950))において、任意の計算可能関数が表現可能ならしめるPAの公理が何であるかを考えることにより、Qの公理(Q1)–(Q7)を導き出した。PAの帰納法の公理図式は上記(Q3)の証明にのみ必要であり、表現可能性の証明の他の部分には全く必要がない。それゆえ任意の計算可能関数はQにおいて表現可能である(Mendelson (1997): Th 3.33, Rautenberg (2010): 246})。

ゲーデルの第二不完全性定理の結論はQにおいても成り立つ：無矛盾なQの帰納的拡大で自身の無矛盾性が証明可能であるものは存在せず、証明図のゲーデル数をdefinable cutに制限したとしても同様である(Bezboruah and Shepherdson (1976), Pudlák (1985), Hájek and Pudlák (1993):387)。ただし第二不完全性定理の通常の証明にはΣ₁帰納法が必要となるから、PAにおける証明をそのままQに対して適用することはできない。

第一不完全性定理は形式的体系をコーディングしてその基本的性質を証明できるような形式的体系にのみ適用できる。Qの公理はこの目的に十分な強さとなるように選ばれている。したがって第一不完全性定理の通常の証明はQが不完全で決定不能であることを示すのに使える。このことはPAの不完全性と決定不可能性は帰納法の公理図式によるものではないということを示唆している。

ゲーデルの定理はQの7つの公理のどれかひとつを落とすと成立しなくなる。ただしこのことはQよりも弱い理論ではゲーデルの定理が成立しないということを意味しない。これらQの切片は決定不能である。しかし本質的決定不能ではない; すなわち無矛盾かつ決定可能な拡大が存在する。

関連項目

• 一般集合論
• ゲンツェンの無矛盾性証明
• ゲーデルの不完全性定理
• 自然数
• 二階算術
• ペアノ算術

参考文献

• A. Bezboruah; John C. Shepherdson (1976), Gödel's Second Incompleteness Theorem for Q, 41, pp. 503-512 
• George Boolos; Richard Jeffrey (2002), Computability and Logic (4th ed.), Cambridge University Press 
• John P. Burgess (2005), Fixing Frege, Princeton University Press 
• Petr Hájek; Pavel Pudlák (1998), Metamathematics of first-order arithmetic (2nd ed.), Springer-Verlag 
• Lucas, J. R., 1999. Conceptual Roots of Mathematics. Routledge.
• Machover; Moshe (1996), Set Theory, Logic, and Their Limitation, Cambridge University Press 
• E. Mendelson (1997), Introduction to Mathematical Logic (4th ed.), Chapman & Hall 
• Pavel Pudlák, 1985. "Cuts, consistency statements and interpretations". Journal of Symbolic Logic v. 50 n. 2, pp. 423–441.
• W. Rautenberg (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6, http://www.springerlink.com/content/978-1-4419-1220-6/ .
• R. M. Robinson (1950), “An Essentially Undecidable Axiom System”, Proceedings of the International Congress of Mathematics: 729-730 
• Joseph R. Shoenfield, 1967. Mathematical logic. Addison Wesley. (Reprinted by Association for Symbolic Logic and A K Peters in 2000.)
• R. M. Smullyan (1991), Gödel's Incompleteness Theorems, Oxford University Press 
• Alfred Tarski; A. Mostowski; R. M. Robinson (1953), Undecidable theories, North Holland