記号論理学(数学基礎論の基礎of基礎?)

「授業(記号論理学)」

記号論理学の基礎

記号論理の体系として現在最も標準的となっている、Ｇ・ゲンツェンが開発した「自然演繹の体系（ＮＪ／ＮＫ）」を、初歩から丁寧に学び、実際の証明構成を行えるようにする。命題論理、述語論理と順を追って検討し,正規化・健全性・完全性など、メタ論理の基本的話題を学んだ後、実際的な数学的応用（公理的集合論，順序集合論の初歩など）をいくつか見た上で、形式的自然数論（ハイティング算術／ペアノ算術）に進み、数学的帰納法を含む証明構成を詳しく分析する。論理学、哲学、計算機科学に関心のある人、またより一般的に、数学の論理的構造をよく理解したい人にとって、様々に有用な事項や興味ある情報が提供されるだろう。

（０）導入：　記号論理の一般概念　　　　　　（第１回）

（１）ＮＪ／ＮＫの命題論理の証明構成　

１－１　連言・選言・含意の概念　　　　　　（第２回）

１－２　否定の概念－－ＮＪとＮＫの対比　　（第３回）

１－３　命題論理の代表的諸定理　　　　　　（第４回）

１－４ 命題論理のモデル論的意味論 (第５回)

（２）ＮＪ／ＮＫの述語論理の証明構成

２－１　変項と量化の概念　　　　　　　　　（第６回）

２－２　述語論理の代表的定理　　　　　　　（第７回）

２－３　述語論理のモデル論的意味論　　　　（第８、９回）

（３）ＮＪ／ＮＫベースの一階理論の具体的事例

３－１　公理的集合論の初歩　　　　　　　　（第10回）

３－２　順序集合論入門　　　　　　　　　 （第11回）　　　　　

３－３ 形式的自然数論－証明構成　　　　　（第12回）

３－４　形式的自然数論－数学的帰納法　　 （第13回）

数学には一体何ができて何ができないのかを知るために、数学を数学的に分析するのがメタ数学、ないしは数学基礎論である

ゲーデルの不完全性定理が示すのは確固たる土台の日存在であると同時に、諸理論が織りなす空間の豊潤さである

記号論理学は数学の数学の標準語とも言える存在

記号論理の証明システム・自然演繹 NJ/NK

(1)命題論理

仮定された事柄、論証済みとなっている事柄、導き出された事柄をひとまとめにして命題と呼ぶ

記号論理の体系は普通２つの部門に区別される

基本的な命題論理(∧、∨、⇒、¬)と述語論理（＋∀、∃）である

論証は、大まかに２つの観点から研究することができる

１つ目は証明論であり、これは判定を可能にさせてくれるアルゴリズムが存在しているかどうかについて興味がある

２つ目は意味論であり、それぞれの命題は何を意味しているのかに興味を持つ

証明論としては３つの代表的なものがあり、「ラッセル＝ヒルベルト系」「自然演繹」「シークエント計算」

とりあえず、自然演繹について取り上げる

自然演繹については２つのものNJとNKがある

直観主義論理（排中律を除いた）を体系化したものがNJで古典論理を体系化したものがNKである

NKとNJの論理規則は（¬の除去則）の有無だけが差である

「数学基礎論とは」

数学基礎論とは、数学の基礎づけを目指す過程で生まれた数学一分野

-公理的集合論

-モデル理論

-証明論

-再帰理論

の４つに分けられる

ここでは、いくつかの当たり前に思える決まり事を決めて、そこから理論を展開していく

例 ユークリッド幾何学

・ユークリッドの公準

1 点と点を直線で結ぶことができる

2 線分は両側に延長して直線にできる

3 1点を中心にして任意の半径の円を描くことができる

4 全ての直角は等しい

5 1つの直線が2角直線に交わり同じ側の内閣の輪を2つの直角より小さくするならばこの２つの直線は限りなく延長されると、２つの直角より小さい角のある側に置いて交わる

これらの公準を認めることで、証明できる！

現代の数学はほとんどの場合において、「集合論」という枠組みの中で議論が行われている

NやR、群、環、体などの代数的構造や関数などの解析的な構造も全て集合論の中で行われている

集合論の世界

集合論はものの集まりの集合を呼び、それらの関係を書き下すような理論である

集合論でもユークリッド幾何学と同じように当たり前のことから出発して全ての集合論的事実を確かめることはできないか？

→大体できる！

ZFCと呼ばれる9つの公理を当たり前だとすると、集合論の多くの定理をそこから導くことができる

1. 集合の存在 (何か集合がある)

2. 外延性

3. 内包 ({|}は集合)

4. 対 (X,Yが集合ならば{X,Yも集合})

5. 和集合 (X,Yが集合ならX∪Yも集合)

6. 冪

7. 置換

8. 無限 (無限集合がある)

9. 選択

自然数全体の集合Nを構成する

まず内包性公理より、空集合が定義される

また、この集合がただ一つしかないことも外延性公理から導ける

これを0とする

0を作ったので、次の数の作り方を定義する

次の数は、対集合の存在公理から作ることができる

どの無限集合にも自然数が部分集合として現れる

通常帰納法の原理というものがある

集合論は大方の数学的概念を記述できる理論である

集合論はZFCという公理系により正当化できる

ZFCから自然数全体の集合っぽいωを作れる

———————————————————-

「理論理学をゲーデルの不完全性定理を例にざっくりと理解する」

人間の証明を論理式で置き換えれば、数学的に扱えるのでは？

———————————————————————

「何もないところから数を作る」

コーシーとワイエルシュトラウスによって無限小や極限が定式化される（ε-δ論法）

コーシーは幾何学のような、定義・公理から出発し、論理的な手続きのみによって理論を展開していく方法を目指した

実数の公理

1. 四則演算ができる

2. 実数同士で大小が比較できる

3. 実数全体がつながっている

この3つ目が実数と有理数の違いである

連続性の定式化として、

・Rの空でない有界な部分集合は上限を持つ

・R上に有界な単勝増加数列は収束する

・Rの有界な数列は収束部分列を持つ

・中間値の定理、最大値の定理が成り立つ

などがあり、これらは全て同値である

つまりこれらは公理である

実数とはこういうものだとして、さらに極限や連続なども粛々と定義していけば、解析学は曖昧さや矛盾なく作り上げられる

公理です、と言われても納得できた気がしないので、有理数から完備化して作る

空集合→自然数→整数→有理数→実数のように作っていく

自然数に順序と演算をいれる

包含関係を順序にすれば順序が入る

同じルールを使うことで、足し算や掛け算が定義できる

つまり、自然数はアルゴリズムで構成できる

作れた後は0が空集合だとか忘れて普通の自然数として扱えば良い

（プログラムの透過性的な）

これから整数を定義する

直積をとって同値関係で割れば、一対一対応が作れて整数を定義できる

こうすることで、演算が定まる

Zはタス引く✖️で閉じた環となる

次に有理数を構成する

分母と分子をとって、(0,0)と(p,q)を結んだものを有理数と定義すると

有理数は四則演算で閉じた体となる

限りなく密に分布しているがまだ無理数の穴が空いている

次はこの穴を埋めて実数を作ることを考える

Qの中で、目標に近づいている数列を考えて、その極限として定義する

例えば、Taylor展開の極限などの有限部分わを考える

これはずるそう

全ての無理数はこのような級数で書けるかどうかはわからない

超越的な方法があり、このような有理数列全体を考え、いろいろな近づき方でも同じとこに行き着くものをまとめたものを一つの実数ということにする

カントールの実数論

コーシーが定めた連続・極限の概念をもとに、コーシーれつの極限として実数を定式化した

もう１つ方法があり、デデキントカットと呼ばれる

Qの切断１つ１つを実数ということにする

有理数に切断が当たらなかった実数ということにする

これはとても難しい

なぜかというと、実数全体がつながっているという性質がそれだけ特別だからである！

Rから複素数を作るのは簡単である

軸を入れて、掛け算を入れるだけでCが作れる

QとRの間には離散と連続の間の超えられない壁がある

空集合は公理的集合論の公理から導かれる

19世紀以降の数学が公理化されていったのは、数学の自由のためかも

前提条件を徹底的に明確にする代わりに何を前提とするかを選べる権利を得た

公理は自由に採択してもいい

ユークリッドの公理を満たさない非ユークリッド幾何学も19世紀に確立された

——————————————————-

「公理的集合論とモデル理論」

pdf：logic３を参照

第1章 公理的集合論の基礎

1.集合論の公理

モノの集まりを集合と呼びたいが、あまりいろいろなものを集合とすると、簡単に矛盾が出てしまう

例：ラッセルのパラドックス

このような矛盾が出ないように集合に関する理論を作りたい

基本的な述語としては、∈だけである

∈と論理記号(∧、∨、¬、⇒、⇔、∀、∃、=)で公理を表現する

(1) 集合の存在定理

(2)外延性公理

(3)内包性公理

(4)対の存在公理

(5)和の公理

(6)置換公理

(7)冪集合公理

(8)選択公理

(9)無限公理

(10)基礎の公理(正則性公理)

2.数学的対象と集合

通常の数学的対象の存在がこの集合論の公理から保証される

関係、直積、関数、順序数、順序数上の再帰的定義、基数など

第2章 モデル理論の基礎

1.構造と同型

同型写像

コンパクト性定理

公理の完全性

定義可能集合

応用例

———————————————————————

「論理学入門 講義ノート」

第1章 はじめに

標準的な命題論理・述語論理の構文論と意味論に加えて、多値論理や直感論理などの非標準的な論理を系統的に扱っているのが１つの特徴

科学的な本では、途中をスキップすると意味が理解できなくなる

完全にその章が理解できるまでは次の章には進んじゃいけない

わからない部分に出くわしたらそこをもう一度読む

体を使って練習を十分行うこと

第2章 論理学とは何か

論理学は思考の道筋を真理という概念を用いて説明する学問

そこでは真理と真理との関係が問題とされる

「〜が真であるならば、〜は真である」という真理関係とはいかなるものかを研究している

１つとして真理表がある

記号論理学は論理的真を探求するという性格上、文の形式のみを問題とすることから、具体的な分を用いず、それを表すものとしてA,Bなどの記号を用いる

記号は日常言語に比べて曖昧さがなく、真偽が言えるから

第3章 命題論理

3.1 命題論理の形式言語

命題論理の形式言語のボキャブラリーには

論理記号、論理変項、命題定項の３つがある

命題変項および命題定項は単文を表し、論理記号は文と文を繋ぐ接続しの役割

言語はその記号の意味が与えられるまでは無意味なものとして取り扱われる

とりあえず、次のように読むとする

次に、命題論理における論理式を定義する

3.2 命題論理の意味論

命題論理の対象である論理式は真または偽という真理値を持つ

上で与えられた言語にはこの真理値をもとにした意味が与えられる

ここで与えた意味と、日常の意味は一致するとは限らない

3.3 命題論理の証明論

本節では、命題論理に対する文章を考える

ここで命題論理言語における文章とは論証のことである

論理的形式言語上での証明概念は、日常言語で行われている論証の論理構造を抽象的に表したものだと考えられる

任意の論理式に対して、開いた前提を持つAの証明構造という概念を定義する

内容的には「PはB1,B2,,,という前提からAという結論を導く証明である」ことを表す

また、B1,B2が同じであってもそれは考えている証明構造の中で異なる場所に現れているので、場所も含めて論理式を同定することにすると、B1とB2は異なると考えられる

自然演繹体系NKの証明構造

開いた前提が１つも現れないAの証明構造はAの証明と呼ばれる

証明構造という概念が開いた前提のもとで終論理式が証明できることを表しているのに対し、証明概念は何の前提も仮定することなく終論理式が証明できることを表している

第4章 述語論理

全章の命題論理の言語を拡張して一階述語論理を展開する

命題論理では、命題を基本単位として取り扱ったが、述語論理では命題を個体名とそれに関係する述語に分解し、それらの関係について探求する

命題を個体記号と述語記号とによって記号かすることによって命題論理では扱えなかった領域を扱えるようになる

その１つが、対象とその対象が持つ性質との関係である

さらに複数の個体間の関係も取り扱えるようになる

さらに、最大の特徴は「全ての〜」や「ある〜」を取り扱えるようになるということである

∀xBのBはこの∀xのスコープと呼ばれる

ある論理式Aに現れているある個体変数xに対してこの現れが自由に現れていると呼ばれるのは、このxがどんな∀xまたは∃xのスコープにも現れていない時である

特に上のAにおけるxの現れが∀xのスコープBには現れているが、Bに現れるどんな∀xおよび∃xのスコープにも現れていない時、このxの現れはこの∀xまたは、、によって束縛されていると言われる

ある量子化記号により束縛されている個体変項は束縛変更と呼ばれる

また、どんな量化記号によっても束縛されていない個体変項は自由変項と呼ばれる

与えられた論理式Aに対して全ての束縛関係を変えることなく、束縛変項記号を置き換えることにより得られる論理式Bは元の論理式Aと同一視される

自由に現れているxを他の変項記号で置き換えるのは無理

4.1 述語論理の構文論

命題論理の全ての推論規則に量化記号に対する推論規則を加えたものが述語論理の推論規則となる

日常的な推論に当てはめることできちんと確認できる

これは特定のxについての言及を含んでいない、すなわちC(x)が何か特定のxについての結論でなければそれから∀xをつけられるということを示している

4.2 述語論理の意味論

論理的意味論の基本的な考え方は、ある言語に属する表現の意味をその表現によって指示される対象と同一視することに存する

そこで、この意味論はしばしば表示的意味論と呼ばれる

命題論理の意味論では、意味対象として、命題論理における論理式の真理性だけを考えた

一階述語論理では、これまでのような論理式の相対としてのt,fという対象領域の他に、一階の項に指示対象領域、すなわち、個体の値の領域をも考えることとなる

まず意味領域から定義する

論理式の値域としてtとf、一階述語論理の項の値域としてある集合Dを与える

与えられた個体領域Dに対して、述語論理言語表現の意味は次のように与えられる

第5章 証明可能性、充足可能性、可能世界モデル

5.1 命題論理

5.2 述語論理