コンテンツにスキップ

ω無矛盾

出典: フリー百科事典『ウィキペディア(Wikipedia)』

数学基礎論においてω無矛盾(オメガむむじゅん、: ω-consistent)とは、公理系の性質を表す概念のひとつである。不完全性定理を示すためにクルト・ゲーデルによって導入された。ω無矛盾性は、通常の無矛盾性よりも強い性質である[1]

20世紀初頭にはヒルベルト・プログラムの下、数学の完全性と無矛盾性を示そうとする試みがなされていたが、1931年にゲーデルの発表した不完全性定理は、ある意味でそのふたつが両立することは不可能であるというものであった。ゲーデルは1931年の時点では「公理系が無矛盾ならば不完全であること」を示そうとしたが果たせず、それよりも弱い主張である「公理系がω無矛盾ならば不完全であること」を示した。さらに1936年アメリカの論理学者ジョン・バークリー・ロッサーによって、ゲーデルの当初の目的である「無矛盾ならば不完全」が示された。今日では、ゲーデルによるω無矛盾性を用いた前者の定理を「第1不完全性定理」と呼ぶ[1]

定義

[編集]

ある公理系が通常の意味で矛盾 (inconsistent) しているとは、ある論理式 P が存在して、P¬P とがともに証明可能であることを意味する。これに対し、公理系がω矛盾 (ω-inconsistent) するとは、自然数 n によって定まる論理式 Q(n) が存在して、次を満たすことをいう:

Q(0), Q(1), Q(2), … が全て証明可能であるが、「n : ¬Q(n)」も証明可能である。

そして、矛盾していない公理系を無矛盾 (consistent)) であるといい、ω矛盾していない公理系をω無矛盾 (ω-consistent) であるという[2]

無矛盾性とω無矛盾性の関係

[編集]

ω無矛盾性は無矛盾性よりも強い概念である。

ある公理系が矛盾している場合、P¬P がともに証明可能であるような P が存在し、したがって前述の Q(n) として P をとれば、その公理系がω矛盾している事が分かる。その対偶を取れば、公理系がω無矛盾ならば無矛盾である。よって特に、ロッサーの結果はゲーデルの結果の拡張とみなされる。

一方で、無矛盾だがω矛盾した理論の例がある。すなわち、Q(0), Q(1), Q(2), … と「n : ¬Q(n)」が全て証明可能であり、しかも無矛盾な公理系が存在する。

通常の感覚ではQ(0), Q(1), Q(2), … が全て証明可能であれば当然「n : Q(n)」も証明可能であり、矛盾が生じざるを得ないように思える。しかし、公理系においてある命題が証明可能であるとは、その公理系における(有限長の)証明が存在するということであり、Q(0), Q(1), Q(2), … の(無限個の)証明があるという事実から、「n : Q(n)」の証明が存在することを導くことは一般にはできない。

無矛盾だがω矛盾した理論の例

[編集]

ペアノ算術 PA はω無矛盾であるからΣ1健全性により PA から ¬Con(PA) は証明不能である。そこで PA¬Con(PA) を付け加えた理論 T を考える。不完全性定理により PACon(PA) を証明できないから T は無矛盾である。T では、PA の標準モデルにおいて偽であるΣ1論理式 ¬Con(PA) を証明できる。すなわち T はΣ1健全でない。ω無矛盾性はΣ1健全性を含意する[3]ので、したがって T はω矛盾している[4][5]

上述の理論 T のモデルは矛盾に至る PA の証明図のゲーデル数を持つ。これは標準的自然数ではありえないので超準的自然数である。すなわち T のモデルはペアノ算術の超準モデルになっている。

脚注

[編集]
  1. ^ a b 田中 一之 編『ゲーデルと20世紀の論理学 1 ゲーデルの20世紀』東京大学出版会、2006年、24–25頁。ISBN 978-4130640954 
  2. ^ 田中 et al. 1997, pp. 84–85.
  3. ^ 菊池 2014, p. 209.
  4. ^ 田中 et al. 1997, p. 91.
  5. ^ 田中 一之 編『ゲーデルと20世紀の論理学 3 不完全性定理と算術の体系』東京大学出版会、2007年、86–84頁。ISBN 978-4130640978 

参考文献

[編集]

関連項目

[編集]