ω無矛盾

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

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

定義

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

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

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

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

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

ある公理系が矛盾している場合、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 はω無矛盾であるからΣ₁健全性により PA から ¬Con(PA) は証明不能である。そこで PA に ¬Con(PA) を付け加えた理論 T を考える。不完全性定理により PA は Con(PA) を証明できないから T は無矛盾である。T では、PA の標準モデルにおいて偽であるΣ₁論理式 ¬Con(PA) を証明できる。すなわち T はΣ₁健全でない。ω無矛盾性はΣ₁健全性を含意するので、したがって T はω矛盾している。

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

参考文献

• Gödel, K. (1931). “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”. Monatshefte für Mathematik und Physik 38: 173–198. doi:10.1007/BF01700692.  - ゲーデルの原論文
• 田中 一之、角田 法也、鹿島 亮、菊池 誠『数学基礎論講義―不完全性定理とその発展』日本評論社、1997年。ISBN 978-4535782419。 
• 菊池 誠『不完全性定理』共立出版、2014年。ISBN 978-4320110960。 

関連項目

• 無矛盾
• 不完全性定理
• 超準モデル