--- 古典論理を学んでいたということですが はい。論理学の基本ですね。アリストテレスの時代から進歩がなかった学問ですが、19世紀末から20世紀で一気に開花した学問です。数学基礎論とか数理論理学と呼ばれている分野です。 ---数学と論理学に関係があるの…

モデル・値付けw(wα=1)を充足関係 w|=α と捉えなおす。論理式φ∈Fはモデルによって充足したり、しなかったりするが、任意のモデルに対して充足する論理式があり、トートロジーと呼ぶ。任意のモデルに対して充足しない論理式があり、矛盾と呼ぶ。αを充足する任…

n個の原子命題からなる論理式は、#Bn = 2^2^n 個あるf: 2^n → 2 なる関数と同一視できる。この同一視（意味論的同値関係）は、数学でいうところの同値関係（同一律、反射律、推移律を満たす）であるため、n個の原子命題からなる論理式全体からなる集合 Fn は…

統語論に関するいくつかのメモ 命題論理の論理式は帰納的に定義できる/命題論理の式全体をFとする. π ∈ F で、 α,β ∈ F ⇒ ￢α , α∧β , α∨β ∈F 。部分集合 Sf も帰納的に定義できる Sf π = {π}, Sf ￢α = {￢α}∪Sf α, Sf α○β = {α○β}∪Sf α ∪ Sf β n個の変数か…

10章 ゲーデル述語 前章からの続き。ロッサー文およびゲーデル文に出てくる述語を数値的に表現する。その際、自身のゲーデル数を自身に代入するという事情のため、ゲーデルナンバリング自体が数論的操作であることを示す必要があり、じっさいにそれを示す。 …

9章 証明の数値的表現 これまでの議論において、「xは公理である⇔Axiom(x)」や「xは証明列である⇔Proof(x)」といった、ゲーデル数を引数にとる述語を、自然数論の体系 N において再帰的に構成できると述べてきた。それを示している。 なお、「xは証明可能で…

8章 証明の再帰性 本書では、ロッサー文を使った証明でゲーデルの不完全性定理を導いた。その際に前提となっている再帰性/帰納性を議論する。 まず、再帰的関数の定義を行い、これを用いると、再帰的述語および再帰的関係を定義することができる。実際、「普…

なんか色々誤解をしてそうなのでWikipedia(en) も読むことにしたい。 Gödel's incompleteness theorems - Wikipedia これからも追記予定 二つの完全性 syntactically complete: Aもしくは￢Aが証明できる semantically complete: 全ての恒真式が証明可能 ・…

7章 ゲーデルナンバリング 項・式・証明列が与えられた時、それらを一意に自然数にエンコードすることが可能である。このエンコードの規則をゲーデルナンバリングと呼ぶ（その実装には任意性がある）。その自然数を体系内の自然数と同一視し、変数x にその自…

5章 述語計算の無矛盾性 今度は述語計算。統語論を定め、推論規則を3つ(MP, GEN, SPEC)提示し、命題論理の公理系11こを引き継ぎ、新たに4つの公理を追加する。 真理値の付与は命題論理の場合よりやや複雑になる。すなわち命題の真理値は、述語関数の意味と、…

4章 命題計算の完全性 拡張命題論理と称するモノから完全性に迫る。すなわち命題式の論理式に対して、命題変数の閉包をとる操作を行うと、（自然数論では変数記号に関する閉包をとる限りこのような事情は発生しない）、任意の式は真理値1か0のみをとるように…

3章 命題計算の無矛盾性 いったん命題理論から始める。しかし本書では一貫して自然数論Sを前提に置いているため、命題変数は自然数論における命題と同一視する。命題論理自身もSの影としてみる立場のようだ。 統語論、推論規則（MP１つ）、公理系(11こ）を提…

今日からしばらく以下のテキストブックでゲーデル不完全性定理を勉強する 「理系への数学」に連載していたものをまとめたもののようだ。ぱっと見たところ、メタな議論をすることに特化している模様。日本語が多いので読みやすい。ゲーデルナンバリングの振り…

ゲーデルの不完全性定理の概観。なぞっても面白くないので自分なりに再構成。 自然数論を含む公理系Nは、矛盾しているか、不完全である（ゲーデルの第一の不完全性定理）。そして、Nの無矛盾性は、有限の立場では証明することができない（ゲーデルの第二の不…

直観論理についての概説。排中律が否定されるとともに、古典論理では妥当であったいくつかの定理が成り立たないことを示す。例えば、次のものは直観論理では成立しない：否定除去型の背理法（￢Aを仮定して矛盾を示せば、Aが示せる）、二重否定除去（￢￢Aか…

ラッセルのパラドクスが生まれる歴史を振り返る。パラドクスが起きるのは二階論理に相当することをしていることを示し、論理学と数学は異なることを強調。パラドクスに対して、３つの反応があることを示す。つまり、論理主義・直観主義・形式主義。 直観主義…

アリストテレスのオルガノンの概説。256通りの三段論法のうち、24の正しいものを、4の正しいと思われる論法から証明したとのこと。一方、多重量子化や固有名、関係文を扱う上で問題があることを提示し、フレーゲの開発した述語論理へと話をつなげていく。述…

命題論理の意味論と構文論。意味論は真理値分析をやって、あとシェファーの縦棒をやって、トートロジーの説明をして、推論をやった。ならばに「⊃」、意味論の推論に「→」を使っているのが特徴的。まぁ別にいいけど。構文論はLPと呼ばれる、公理４つと導出規…