一貫性

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

古典的な 演繹論理では一貫した 理論は論理的な矛盾を引き起こさないものです。[1]矛盾の欠如は、意味論的用語または構文的用語のいずれかで定義できます意味論的定義は、理論がモデルを持っている場合、つまり理論のすべての公式が真であるという解釈が存在する場合、理論は一貫していると述べています。これは、従来のアリストテレス論理で使用されている意味ですが、現代の数理論理では、代わりに充足可能という用語が使用されています。構文上の定義は理論を述べていますがない場合は一貫性があります 両方のようにとその否定の一連の結果の要素ですさせて閉じた文(非公式には「公理」)のセットであり、から証明可能な閉じた文のセットいくつかの(指定された、おそらく暗黙的に)形式的な演繹システムの下で。公理のセット一貫しているとき数式なし[2]

これらの意味論的および統語論的定義が特定の演繹論理で定式化された理論と同等である演繹システムが存在する場合、その論理は完全と呼ばれます。[要出典] 1918年にPaulBernays [出典] [3]1921年にEmil Post [4]によって、命題論理の完全性が証明されました。一方、命題論理の完全性は、1930年にKurtGödelによって証明されました[5]。およびに関して制限された算術の一貫性の証明帰納法公理スキーマは、Ackermann(1924)、von Neumann(1927)、およびHerbrand(1931)によって証明されました。[6]二階述語論理などのより強力な論理は完全ではありません。

一貫性の証明、特定の理論が一貫していることの数学的証明です。[7]数学的証明論の初期の発展は、ヒルベルトのプログラムの一部としてすべての数学に有限の一貫性の証明を提供したいという願望によって推進されましたヒルベルトのプログラムは、不完全性定理の影響を強く受けました。これは、十分に強力な証明論では、それ自体の一貫性を証明できないことを示しています(実際に一貫している場合)。

一貫性はモデル理論によって証明できますが、論理のモデルを参照する必要なしに、純粋に構文的な方法で行われることがよくあります。カット除去(または、基礎となる微積分がある場合はそれと同等の正規化)は、微積分の一貫性を意味します。カットフリーの偽りの証拠がないため、一般に矛盾はありません。

算術と集合論の一貫性と完全性

ペアノ算術などの算術理論では、理論の一貫性とその完全性の間に複雑な関係があります。その言語のすべての式φについて、φまたは¬φの少なくとも1つが理論の論理的帰結である場合、理論は完全です。

プレスバーガー算術は、加算中の自然数の公理システムです。それは一貫性があり、完全です。

ゲーデルの不完全性定理は、十分に強力な帰納的可算算術理論は完全で一貫性のあるものではないことを示しています。ゲーデルの定理は、ペアノ算術(PA)と原始帰納的算術(PRA)の理論に適用されますが、プレスバーガー算術には適用されません。

さらに、ゲーデルの2番目の不完全性定理は、十分に強力な帰納的可算理論の一貫性を特定の方法でテストできることを示しています。そのような理論は、理論が実際に一貫しているという主張の形式化されたステートメントである、理論のゲーデル文と呼ばれる特定の文を証明しない場合にのみ一貫しています。したがって、十分に強力で、帰納的可算で、一貫性のある算術理論の一貫性は、そのシステム自体では決して証明できません。同じ結果は、ツェルメロフレンケル集合論などの集合論を含む、十分に強力な算術の断片を記述できる帰納的可算理論にも当てはまります。(ZF)。これらの集合論は、それらが一貫しているという条件で、独自のゲーデルの文を証明することはできません。これは一般的に信じられています。

ZFの一貫性はZFで証明できないため、より弱い概念相対的一貫性は、集合論(および他の十分に表現力のある公理システム)では興味深いものです。T理論であり、Aが追加の公理場合Tが一貫T+Aしていることが証明できる場合T+ATに対してている(または単にATAと¬A両方T一致しているA独立しいると言われますT。 _

一階述語論理

表記

(回転式改札口記号)次の数理論理学の文脈では、「から証明可能」を意味します。あれは、読み取り:bはaから証明可能です(特定の形式システムで)。論理記号のリストを参照してくださいその他の場合、回転式改札口の記号は意味するかもしれません。の派生を許可します。参照:数学記号のリスト

定義

  • 数式のセット 一階述語論理では一貫性があります(書かれています)式がない場合そのようなさもないと一貫性がない(書かれている)。
  • 式がない場合、単純に一貫していると言われます、 両方否定の定理です[説明が必要]
  • の言語で少なくとも1つの式があれば、完全に一貫している、または投稿が一貫していると言われますの定理ではありません
  • すべての式について、最大限に一貫していると言われています、 もしも示す
  • フォームのすべての式について、証人が含まれていると言われています用語があります そのような、 どこそれぞれの置換を示しますによって; 一階述語論理も参照してください[要出典]

基本的な結果

  1. 以下は同等です。
    1. すべてのために
  2. 充足可能な数式のセットはすべて一貫しており、数式のセットは一貫していますモデルが存在する場合にのみ充足可能そのような
  3. すべてのために
    1. そうでない場合、 それから;
    2. もしも、 それから;
    3. もしも、 それからまた
  4. させて最大限に一貫性のある数式のセットであり、証人が含まれていると仮定します。すべてのために
    1. もしも、 それから
    2. またまた
    3. 場合に限りまた
    4. もしも、 それから
    5. 用語がある場合のみそのような[要出典]

ヘンキンの定理

させて記号のセットであるさせて最大限に一貫したセットである-目撃者を含む公式

同値関係を定義する のセットで-用語もしも、 どこ平等を示します。させてを含む用語の同値類を示す; そしてしましょうどこ記号のセットに基づく用語のセットです

を定義する-構造 以上、用語に対応する構造とも呼ばれます、 に:

  1. それぞれについて-関係記号、 定義もしも[8]
  2. それぞれについて-ary関数記号、 定義
  3. 定数記号ごとに、 定義

変数の割り当てを定義する変数ごとにさせて関連する用語の解釈である

次に、それぞれについて-方式

場合に限り[要出典]

証明のスケッチ

確認することがいくつかあります。まず、それ実際には同値関係です。次に、(1)、(2)、および(3)が明確に定義されていることを確認する必要があります。これは、は同値関係であり、(1)と(2)が選択に依存しないという証明も必要です。クラスの代表者。ついに、式の誘導によって検証することができます。

モデル理論

古典的な一階述語論理を用いたZFC集合論では[9]一貫性のない理論閉じた文が存在するようなものですそのような両方が含まれていますとその否定一貫性のある理論とは、次の論理的に同等の条件が成り立つ ような理論です

  1. [10]

も参照してください

脚注

  1. ^ Tarski 1946は、次のように述べています。「この理論の2つの主張されたステートメントが互いに矛盾しない場合、つまり、2つの矛盾する文のいずれかが…少なくとも1つを証明できない場合、推論理論は一貫性または非矛盾性と呼ばれます。 " (p。135)ここで、Tarskiは矛盾ように定義しています。。20)。この定義には、「証明」の概念が必要です。ゲーデル1931は、この概念を次のように定義しています公理を含み、「即時の結果」の関係の下で閉じられる式の最小クラスとして定義されます。つまり、aとbの式cモーダスポネンスまたは置換観点から即時の結果として定義されます。ゲーデル1931年、ファン・ハイエノールト1967年、p。601.タルスキは、「証明」を非公式に「言明は特定の原則に従って明確な順序で互いに続く…そしてそれらの有効性を確立することを目的とした考慮事項を伴う[すべての真の前提に対する真の結論– Reichenbach 1947、p.68]」と定義している。 1946年、p。3. Kleene 1952誘導または言い換えのいずれかに関する概念を定義します)シーケンス内の各式が前の式の公理または「即時の結果」のいずれかになるように、式の有限シーケンス。証明その最後の公式の証明であると言われ、この公式は(正式に)証明可能であるか、(正式な)定理であると言われています」cf Kleene 1952、p。83。
  2. ^ ホッジス、ウィルフリッド(1997)。より短いモデル理論ニューヨーク:ケンブリッジ大学出版局。p。37.しましょう署名する、の理論の文私たちはそれを言います結果です、 またはその を伴う 、記号で、すべてのモデルの場合のモデルです(特にその時モデルはありませんを伴う。)
    警告:次の場合は必要ありませんその後、の証拠がありますからいずれにせよ、無限論理では、何が証明を構成するかが常に明確であるとは限りません。一部の作家はそれを意味するから推論可能ですいくつかの特定の正式な証明計算で、彼らは書いています私たちの含意の概念(私たちと衝突する表記法)のために)。一階述語論理の場合、2種類の含意は、問題の証明微積分の完全性定理と一致します。
    私たちはそれを言いますシンボルで有効である、または論理定理である、 もしもすべてに当てはまります-構造。私たちはそれを言います一貫している場合一部の人に当てはまります-構造。同様に、私たちは理論と言いますモデルがある場合一貫性があります。
    L無限オメガの2つの理論SとTは、同じモデルを持っている場合、つまりMod(S)= Mod(T)の場合、同等であると言います。
    (30ページのMod(T)の定義に注意してください...)
  3. ^ van Heijenoort 1967、p。265は、バーネイズがプリンシピアMathematicaの公理の独立性を決定したと述べており、その結果は1926年まで公表されていませんが、バーネイズがその一貫性を証明していることについては何も述べていません。
  4. ^ Postは、PMの命題論理の一貫性と完全性の両方を証明しています。vanHeijenoortの解説とPostの1931年のvan Heijenoort 1967の基本命題の一般理論の紹介、 264ページ以降を参照してください。また、タルスキ1946年、134ページ以降。
  5. ^ cf vanHeijenoortの解説とGödelの1930年vanHeijenoort 1967、pp。582ffにおける論理の汎関数計算の公理の完全性。
  6. ^ cf vanHeijenoortの解説とHerbrandの1930van Heijenoort 1967、pp。618ffの算術の一貫性について
  7. ^ 非公式には、ツェルメロフレンケル集合論が通常想定されています。非公式の数学のいくつかの方言は、慣習的に、選択公理に加えて仮定します。
  8. ^ この定義は、の選択とは無関係ですの代替特性によるとの最大の一貫性
  9. ^ 数学の他の分野への多くのアプリケーション、および微積分学における非公式の数学の推論の通常のモード、および物理学、化学、工学へ
  10. ^ ドモルガンの法則によると

参考文献

外部リンク