ゲーデルの完全性定理

Posted on by
before-content-x4

この記事またはセクションには、認定された出版物に表示される参照が必要です。

この通知は2017年7月11日に配置されました。

after-content-x4

ゲーデルの完全性定理式。

彼 ゲーデルの完全性定理 これは数学論理の重要な定理であり、1929年にカート・ゲーデルによって最初に実証され、その最もよく知られている形で次のようになりました。

「実証可能」という言葉は、フォーミュラの正式な控除があることを意味します。控除は、基本的な推論ルールを通じて、各ステップまたは公理を呼び出すか、以前の手順から取得するステップの有限リストで構成されています。この控除から、各ステップがアルゴリズムによって正しいかどうかを確認することができます（たとえば、コンピューターまたは手で）。

フォーミュラはです 論理的に有効です 式で使用される言語のすべてのモデルでそれが真である場合。 Gödelの完全性定理を正式に表現するには、単語の意味を定義する必要があります モデル この文脈で。これは、モデル理論の基本的な定義です。

Gödelの定理は、一次ロジックにおける意味的真実と構文の確率との対応を確立します。異なるモデルで真のものを扱うモデルの理論と、特定の正式なシステムで正式に証明できるものを研究するデモンストレーション理論との間にリンクを作成します。 Gödelは完全性定理を使用してコンパクトさの定理をテストし、論理的結果のオペレーターの有限性を実証しました。これらの結果は、現在の数学における支配的なロジックのタイプとして、最初の注文論理を確立するのに役立ちました。

その後、1947年にレオン・ヘンキンが博士論文で、テストの困難な部分を存在の定理モデルとして提示できることを観察したときに単純化されました（1949年に公開）。次に、ヘンキンのテストは、1953年にGisbert Hasenjaegerによって簡素化されました。

after-content-x4

定理声明 [ 編集します ]

序章 [ 編集します ]

式の言語（つまり、式の変数への値の割り当て）に対して各構造で真である場合、最初の順序式は論理的に有効と呼ばれます。整合性定理を正式に宣言し、それを実証するには、演ductive的なシステムを定義することも必要です。論理的に有効な式が正式な控除の結論である場合、演ductiveシステムは完全なものと呼ばれ、特定の演ductiveシステムの完全性定理は、この点で完全な定理です。したがって、ある意味では、各演ductiveシステムに異なる完全性定理があります。整合性と一緒に重要なことは堅実さです。これは、論理的に有効な式のみが演ductiveシステムで実証可能であるという事実です。

一次ロジックの特定の演ductiveシステムが固体で完全である場合、それは「完全」（公理の意味的な結果である場合にのみフォーミュラが実証可能です）であり、同じ品質を持つ他の演ductiveシステムに相当します（あるシステムのテストは他のシステムになります）。

Gödelの元の定式化 [ 編集します ]

整合性定理は、式が論理的に有効である場合、式の有限控除（正式なテスト）があると言います。

Gödel完全性定理は、すべての論理的に有効な式をテストするために追加の推論ルールが必要ないという意味で、最初の順序述語の計算の演ductive的なシステムは「完全」であると述べています。整合性とともに、堅牢性を考慮に入れる必要があります。これは、論理的に有効な式のみが演ductiveシステムで実証可能であるという事実です。堅実さ（その検証が容易な）とともに、この定理は、正式な控除の結論である場合にのみ、式が論理的に有効であることを意味します。

モデルの存在の定理 [ 編集します ]

この定理の最も単純なバージョンは、ほとんどのニーズに合わせて実際に十分であり、Löwenheim-Skolem定理とつながりがあると言います。

それぞれの最初の秩序の一貫性と会計理論には、有限または会計モデルがあります。

より一般的なバージョンは、次のように表現できます。

よく注文された言語を使用したすべての最初の注文コヒーレント理論には、モデルがあります。

ここでは、一貫した理論は、「F」と「f」の両方が証明できる「F」と式の「F」なしで定義されています。一貫性、構文定義を参照してください。この文脈では、セマンティックな定義は並外れたものになります。

このヘンキンの定理は、最も単純なテストで完全性定理から得られる最も直接的なバージョンです。

ヘンキンの定理を考えると、完全性定理のデモンストレーションは次のとおりです。

ファイ ⊨ a {displaystylephiモデルa}

その場合、それは有効です

ファイ ∪ ¬ a {displaystyle non -cup lnot a}

モデルはありません。ヘンキンのコントラストのために

¬ a {displaystyle lnot a}

それは一貫性のないフォーミュラです。しかし、一貫性の定義のために、if

ファイ ∪ ¬ a {displaystyle non -cup lnot a}

それは矛盾しているので、のテストを作成することが可能です

ファイ ⊢ a {displaystylephi vdash a}

。

デモンストレーション [ 編集します ]

オリジナルのデモンストレーション [ 編集します ]

1930年、ゲーデルは最初のオーダー定量ロジックの完全性を実証しました。文字通り、Gödelの完全性定理は、「Aが論理的に真である場合、最初の順な定量的ロジックのすべての式aについて、控除可能です。」正式に：「aの場合、├a」。これは、定量的ロジックの正式なシステムが、システム内で正式に控除可能であるすべての式が完全に完了することを意味します。

完全性定理テストは、次の施設を委託するために削減されます

  1. Aは論理的に真実です：a a
  2. aが論理的に真実である場合、¬Aは不満です
  3. ¬が満足していない場合、¬Aは一貫していません
  4. ¬Aが一貫性がない場合、それは矛盾を引き起こします：¬a├bおよび¬a├¬b
  5. ¬a├bおよび¬a├¬bの場合、├a

これらの施設の正当化は次のとおりです

  1. それは完全性定理の仮説です
  2. その後、論理的に真の式の概念の定義が続きます。その否定は不満でなければなりません
  3. それはヘンキンの定理のコントラストです
  4. それは矛盾の定義の単なる分析です
  5. It is based on the deduction theorem, which allows to go from ¬a ├ B and ¬a ├ ¬b a ├ ¬a ^ B and ├ ¬a ^ ¬B, respectively, and in modus Ponens, which allows, with the help of these last two formulas, eliminating the background in the law of reduction to the absurd (├ (¬a ^ b) ® ((¬ ^ ├ ¬¬A is passed to ├ A through an application of MP to the double denial law ├ ¬¬a ^ a

これらの施設を受け入れて、MPルールは（2）および（1）で始まり、（3）と（2）などの結果に続く（5）：├aから、まさにゲーデルの理論の論文であり、したがって、実証されています。

現代のデモンストレーション [ 編集します ]

現代の論理書では、ゲーデルの完全性定理は通常、ヘンキンをデモンストレーションすることによって実証されますが、ヘルブランドのデモもゲーデルの最初のデモではなく使用されます。

参照してください [ 編集します ]

参照 [ 編集します ]

書誌 [ 編集します ]

  • Gödel、K（1929）。 ロジック計算の完全性について 。博士論文。ウィーン大学。 この論文は、完全性定理のデモンストレーションの元の情報源です。
  • Gödel、K（1930）。 「論理機能計算の公理の完全性」。 数学のための毎月の小冊子 （ドイツ語で） 37 ：349-360。 doi： 10.1007/BF01696781 。 JFM 56.0046.04 。 この記事には、略語形式の博士論文と同じ資料が含まれています。デモンストレーションは短く、最も簡潔な説明があり、広範な紹介は省略されています。

外部リンク [ 編集します ]

after-content-x4