L211 数学と論理学 第１回

Transcription

1 L211 数学と論理学第 1 回 プライニングノルベルト preining@jaist.ac.jp 数学と論理学 目的数学的な考え方は現代の科学技術の奥深くまで浸透している そして高度な抽象性を持つ数学の概念が思いもかけない形で応用されることもある 数学と論理学の発展を振り返りこれらのことを明らかにするとともに 現代の数学の流れについてもふれてみたい 数学と論理学の基本的な概念の理解を目標とする 内容 (1) 数学の基本概念の形成 (2) 数学的真理をどのように考えるか (3) 数理論理学の誕生 (4) 現代数学の流れとその課題 などについて概説する

2 講義スケジュール 月 5 時限 水 5 時限 4/09 数学の例 4/13 数学とは何 4/15 証明とは何 4/20 帰納法 4/22 帰納法 2 4/27 整数論 数体系 4/29 GW 5/04 GW 5/06 GW 5/11 無限集合 集合論 5/13 集合論論理学 5/18 論理学 5/20 幾何学 公理的方法 5/25 級数と関数 5/27 グラフ理論 6/01 計算モデル 6/03 ソフトウェア検証 6/05 21 世紀の数学 まとめ 評価 課題 レポート (80%) 講義における議論への貢献 (20%)

3 連絡など 質問がある場合は下記へ連絡下さい プライニングノルベルト 総合研究実験棟 3 F C2-302a Office Hour 火曜日 3 時限 学生のバック グラウンド

4 数学と論理学に対しての考え 中高学校時代を思い出しながら 数学に対しての最初の思い出とは何か下記の陳述から 2 つを選んで下さい 1. 数学は面白い 2. 数学はつまらない 3. これから数学はもっと大切になる 4. 今日この頃 新しい発見がない 5. 見えなくても 数学はどこでも使われている 6. 数学は要らない 役に立たない 本日の目的 20 世紀の発見 数学の便利さ 歴史

5 第一例 フェルマーの最終定理 ピタゴラスの定理 a 2 + b 2 = c 2 c b a

6 ピタゴラスの定理の解 a = 1, b = 2 c = 5 = 特別の解 a = 3, b = 4 c =? 5 整数の解 フェルマーの最終定理 ピエールドフェルマー Pierre de Fermat フランス人 1607/ 整数論 解析学 特に解析幾何学 素人の数学者 (?) 証明があまりないか証明を伝えていない Source: Wikipedia

7 ディオファントスの算術 Source: Wikipedia ディオファントス方程式 整係数 多変数 高次不定方程式 一次方程式 ax + by = c かつ a, b, c は整数 ( Z) a, b, c の条件は? c は a と b の最大公約数の倍数

8 ピタゴラスの定理 2 次方程式 x 2 + y 2 = z 2 ディオファントス方程式ならば 可解である :(3, 4, 5) 等 3 次方程式 n 次方程式 x 3 + y 3 = z 3??? x n + y n = z n??? フェルマーの推測 1637 年フェルマーはディオファントスの算術の余白に Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et generaliter nullam in infinitum ultra quadratum potestatem in duos eiusdem nominis fas est dividere cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet. 立方数を 2 つの立方数の和に分けることはできない 4 乗数を 2 つの 4 乗数の和に分けることはできない 一般に 冪 ( べき ) が 2 より大きいとき その冪乗数を 2 つの冪乗数の和に分けることはできない この定理に関して 私は真に驚くべき証明を見つけたが この余白はそれを書くには狭すぎる

9 フェルマーの推測 その意味は 推測 n > 2 の場合は x n + y n = z n の方程式は整数の解がない 1995 年やっとアンドリュー ワイルズ (Andrew Wiles) は証明を見つけた フェルマーの推測の証明の歴史 x n + y n = z n 証明のため n は素数が足りる n = 4: Fermat n = 3: Euler (1770) n = 5: Legendre, Dirichlet ( 1825) n = 7: Lam (1839) 1993 年まで全ての素数 < Wiles

10 ワイルズの証明 1955 年 : 谷山 志村予想 1984 年 :ellliptic curve の関係 1986 年 :Ken Ribet, epsilon conjecture 1986 年からワイルズは一人で証明を探している 1993 年 6 月 :Issac Newton Institute for Mathematical Sciences で 3 日間のうちに発表 1993 年 8 月 : いろんな間違いが見つけられた : Richard Taylor と一緒に修正 1995 年 5 月 :Annals of Mathematics フェルマーから 358 年 現在における影響 暗号化 楕円曲線暗号 (elliptic curve cryptography) ECDSA 楕円曲線 DSA (elliptic curve digital signature algorithm) Dual EC DRBG Dual Elliptic Curve Deterministic Random Bit Generator 因数分解

11 フェルマーとワイルズ Source: Wikipedia 第二例 四色定理

12 いかなる地図も 隣接する領域が異なる色になるように塗るには 4 色あれば十分だという定理である 四色定理の歴史 1840 年 :Möbius 推測 1890 年 :Heawood 五色定理 年 : いろんな正しくない証明 1976 年 :Appel and Haken コンピューター用な証明 初めて数学の定理の証明でコンピュータが使われていた!

13 証明の方法 Step 1 全ての地図を有限の種類に分割 ( 最初 1936 個 ) 伝統的な数学 Step 2 一つの代表が四色で色がぬれるならば この分類の全ての個々の地図が四色で色がぬれる 伝統的な数学 Step 3 一つずつ代表を選んで 四色で塗る コンピューター プログラム その後 いろんな間違いが発生したから 1989 年修正してまた出版された 1996 年 : もっと早いアルゴリズム 種類の減量 2005 年 :Coq 定理証明支援系ー検証 まだ数学者は不満である

14 現在における影響 定理証明支援系言語の開発 第三例 ゲーデルの不完全性定理

15 ダフィット ヒルベルト David Hilbert ドイツ数学者 ヒルベルトの 23 の問題 1920 年 : ヒルベルト プログラム数学におけるすべての普遍妥当な論理式を機械的に導出可能とする公理系と推論法則を構築する計画をいう ヒルベルト計画とも呼ばれる クルト ゲーデル Kurt Gödel オーストリア ハンガリー帝国 ヒルベルトの講義一階述語論理の完全性の問題 1930 年 : 一階述語論理の完全性定理の証明 (24 歳 ) 1931 年 : 不完全性定理の証明 (25 歳 ) 年 : ロシアー日本ー北米の Princeton

16 不完全性定理のアイディア このスライドの枠の中の文は正しくない もう少し公式的に G は一階述語論理のは命題 G の意味 G は証明できない という G の証明はできるかできないかどちらだろう? G は証明できるとしたら G は正しい G は正しいとしたら G は証明できない というのは正しい 矛盾 だから G は証明できない

17 不完全性定理の結論 停止性問題 Halting problem ヒルベルト プログラムの終了自動的に証明できない paraconsistent logics いろんな独立の公理 推測 定理 数学論理学者がまだ必要!

18 まとめ 数学はまだ生きている 20 世紀はよく 数学の世紀 と言われている 簡単な問題なのに 深い数学が現れる 影響が強い 楽しい! 次の講義 学校と大学の数学ー計算から証明まで 課題 証明 の言葉が一杯の意味を持っている 社会的 公法的 数学以外の科学等