ロビンソン算術
数理論理学においてロビンソン算術(英: Robinson arithmetic)あるいはQとはペアノ算術(PA)の有限部分理論であり、Robinson (1950)において最初に導入された。Qは本質的にはPAから帰納法の公理図式を取り除いたものである。それゆえQはPAよりも弱いが同一の言語を持つ不完全な理論である。Qは重要かつ興味深い対象である。というのもQは本質的決定不能かつ有限公理化可能なPAの部分理論だからである。
超数学
超数学におけるQについてはBoolos (2002), Tarski et al. (1953), Smullyan (1991), Mendelson (1997), Burgess (2005)などを見よ。Qの標準的な解釈は自然数に通常の算術を考えたものである。すなわち加法と乗法は通常の意味を持ち、等号は同値性を意味する。また定数記号 0 は自然数のゼロに、 S は +1 にそれぞれ解釈される。
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の切片は決定不能である。しかし本質的決定不能ではない; すなわち無矛盾かつ決定可能な拡大が存在する。