ロビンソン算術

Summarize Timeline Fact Check

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

• 定項記号: 0
• 単項関数記号: 後者 ${\displaystyle S}$
• 二項関数記号: 加法 ${\displaystyle +}$ と乗法 ${\displaystyle \cdot }$

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

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

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

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

${\displaystyle x<y\leftrightarrow \exists z(x+Sz=y)}$

上のようにして定義された ${\displaystyle <}$ について次の基本的な要請を公理として(Q1)–(Q7)の後に加える：

• ${\displaystyle \neg x<0}$
• ${\displaystyle 0=x\vee 0<x}$
• ${\displaystyle x<y\leftrightarrow Sx<y\vee Sx=y}$
• ${\displaystyle x<Sy\leftrightarrow x<y\vee x=y}$

別の公理化で ${\displaystyle <}$ を用いたものは Shoenfield (1967: 22) において見られる。

Summarize Timeline Fact Check

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

${\displaystyle \mathbb {N} \cup \{a,b\}}$

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

${\displaystyle Sa=b}$

${\displaystyle Sb=a}$

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

${\displaystyle a+n={\begin{cases}a&{\mbox{if }}n\equiv 0\mod 2\\b&{\mbox{if }}n\equiv 1\mod 2\end{cases}}}$

${\displaystyle b+n={\begin{cases}b&{\mbox{if }}n\equiv 0\mod 2\\a&{\mbox{if }}n\equiv 1\mod 2\end{cases}}}$

${\displaystyle n+a=a}$

${\displaystyle n+b=b}$

${\displaystyle a+a=a}$

${\displaystyle a+b=b}$

${\displaystyle b+a=a}$

${\displaystyle b+b=b}$

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