スライド

L211 数学と論理学第９回
プライニング　ノルベルト
[email protected]
http://www.preining.info/L211/
2014年5月14日
月曜日の講義
集合論
大事な点
冪集合 ℘(A) = {S : S は A の部分集合}
A ≺ ℘(A)
N, ℘(N), R, 連続体仮説
外延性の公理
内包公理
ラッセルのパラドックス a ∈ a ⇔ a ∈ a
制限な内包公集合の C の存在するならば、
{x ∈ C : P(x)} の集合が存在する
演習問題
論理学
集合論のパラドックス
制限な内包公で全てのパラドックスがなくなる？
他のパラドックス？新しいパラドックス？
どうやって無矛盾性を確かめる？
数学の真と物理の真の差？
数学基礎論
数学基礎論
形式主義 (Formalism)：Hilbert, x, ∀, ∃, =, ↔, 無定義な観
念
数学的直観主義 (Intuitionism): Brouwer, 無限
論理主義 (Logicism): Russel
形式主義の進め方
世界にの存在の関係なくて、数学的な理論を作れる。
一つの条件がある：無矛盾な論理！
パラドックス？
無矛盾性の「証明」が必要
無矛盾性の証明
理論 T は無矛盾である
矛盾な式を証明ができない
(例：a ∧ ¬a)
命題 a は証明可能であると確かめのため、具体的な証明
を出す。
命題 a は証明不可能であると確かめのため、どうする？
無限数の証明をチェックする？
チェス
0Z0Z0Z0Z
7
j0Z0Z0Z0
6
0Z0o0Z0Z
5
o0ZPZpZ0
4
PZ0O0O0Z
3
Z0Z0Z0Z0
2
0Z0Z0Z0Z
1
J0Z0Z0Z0
8
a
b
c
d
e
f
g
h
Lasker-Reichhelm Position
理論の形式化
Kb1 すると、白は勝てる。
証明のため、チェスの規則をはっきり記述する
無矛盾性を確かめのため、理論を記号的に書く上、数学
公理と論理学の公理を記述が必要である。
数学論理学の形式化：Hilbert, Gentzen
数学の論理の形式化（集合論、整数論等）：Zermelo,
Fraenkel, Peano
数学論理学
数学の言葉：
全ての二等辺三角形は等しい角が２つある。
この三角形の角が全て違う。
従って、二等辺三角形じゃない。
晴れたら、先週末絶対にクライミング行きたかった。
けど、行かなかった。
従った、晴れていなかった。
P ならば Q。Q は成り立たないから、P も成り立たない。
内容と形
「推論」の正確性は内容の関係なくて、形で決定されてい
る。
全ての学生は休暇が好きである。
数学が好きな学生がいる。
従って、数学と休暇が両方好きな学生がいる。
全ての多項方程式に対して、複素数の根がある。
ある多項方程式に対して、実数の根がない。
従って、ある多項方程式に対して、全ての根が複素数で
ある。
論理学の言語
論理演算： ∧, ∨, →, ¬
量化記号： ∀, ∃
変数：x, y , . . .
関数記号：f , g , . . .
関係記号：P, Q, . . .
例
B(x, y ) の意味は「x と y は兄弟である。」
S(z) の意味は「z は JAIST の学生である。」
「x の兄弟は JAIST の学生である。」
¬∀y (B(x, y ) → S(y ))
意味の差とは何である？
∀x∃yQ(x, y )
∃x∀yQ(x, y )
大学の生活
全ての学生は休暇が好きである。数学が好きな学生がいる。
従って、数学と休暇が両方好きな学生がいる。
S(x) 学生、H(x) 休暇が好き、M(x) 数学が好き
[∀x(S(x) → H(x))∧∃x(S(x)∧M(x))] → ∃x(S(x)∧H(x)∧M(x))
整数論の公理化
0 は最初の自然数である。
x は自然数ならば、s(x) も自然数である。
x と y は自然数ならば、x + y と x × y も自然数である。
それで本当に N になる？
条件：全ての自然数 n を 0 と s(x) で作成されている。
数学の帰納法
[0 ∈ A ∧ ∀x(x ∈ A → s(x) ∈ A)] → ∀x(x ∈ N → x ∈ A)
ペアノの公理
ジュゼッペ・ペアノ
Giuseppe Peano
イタリアの数学者
1858–1932
Russel — Peano
ペアノの公理
s(x) = 0, s(x) = s(y ) → x = y
x + 0 = x, x + s(y ) = s(x + y )
x × 0 = 0, x × s(y ) = (x × y ) + x
[φ(0) ∧ ∀x(φ(x) → φ(s(x)))] → ∀xφ(x)
問題：ペアノ公理系は無矛盾である？ — 証明？
無矛盾とは 0 = 1 は証明できないという。
証明のため、集合論を使っていい？ — ダメ
基本的な定理
ゲーデルの完全性定理 (Gödel’s completeness theorem,
1929)
一階述語論理における意味論的真理と統語論的立証性の
対応
チャーチのテーゼ (Church’s thesis, 1936)
式の真を決めるアルゴリズム（プログラム）は存在して
いない
ペアノ公理系 — ゲーデルの不完全性定理
Gödel’s Incompleteness Theorem
自然数論を含む帰納的に記述できる公理系が、ω無
矛盾であれば、
証明も反証もできない命題が存在する。
条件：ω無矛盾であれば
結論
ペアノ公理系が、証明も反証もできない命題が存在する。
Sources
Wikipedia

Download Report