ロビンソン算術

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ロビンソン算術(英 Robinson arithmetic)とは自然数の演算に関する第一階の理論(first order theory)の一つである。ロビンソン算術は標準モデルで真である全てのΣ1文を証明可能であり、ロビンソン算術の任意の再帰的拡大で不完全性定理が成立する。

公理[編集]

引数関数Sと二項演算子+,×を用いて次の7つの公理を置く。

  1. ∀a∀b(a≠b→S(a)≠S(b))
  2. ∀a(0≠S(a))
  3. ∀a(a≠0→∃b(a=S(b)))
  4. ∀a(a+0=a)
  5. ∀a∀b(a+S(b)=S(a+b))
  6. ∀a(a×0=0)
  7. ∀a∀b(a×S(b)=((a×b)+b))

モデル[編集]

この公理に対し、自然数がモデルの一つとなる。つまり、議論領域を自然数全体の集合とし、a+b,a×bを通常の自然数のとし、S(n)をn+1を返す関数とするモデルはロビンソン算術のモデルである。 ただし、(自然数のモデルと同型なモデルもロビンソン算術のモデルとなるが)自然数と同型でないモデルにもロビンソン算術のモデルとなってしまうものがあるため、この理論は厳密には自然数を定義できていない。すなわちロビンソン算術は範疇的でない。このような現象は一階述語論理上の理論に共通であり、ロビンソン算術に特有な現象ではない。レーヴェンハイム-スコーレムの定理により無限濃度のモデルを持つ任意の理論は同型でない無数のモデルを持つからである。ロビンソン算術を二階述語論理上の理論と考えた場合が本質的である。二階のペアノ算術は範疇的であるが、二階のロビンソン算術は依然として範疇的でないからである。

参考文献[編集]

戸田山和久『論理学をつくる』pp329-338 名古屋大学出版会、2012年 ISBN 978-4-8158-0390-2