L211 数学と論理学 第１回

L211

数学と論理学

第１回

プライニング　ノルベルト preining@jaist.ac.jp http://www.preining.info/jaist/l211/2015j/

数学と論理学

目的

数学的な考え方は現代の科学技術の奥深くまで浸透している。そ して高度な抽象性を持つ数学の概念が思いもかけない形で応用さ れることもある。数学と論理学の発展を振り返りこれらのことを 明らかにするとともに、現代の数学の流れについてもふれてみ たい。 　　　 数学と論理学の基本的な概念の理解を目標とする。

内容

(1) 数学の基本概念の形成、(2) 数学的真理をどのように考える か、(3) 数理論理学の誕生、(4) 現代数学の流れとその課題、な どについて概説する。

講義スケジュール

月５時限 水５時限 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 世紀の数学、まとめ

評価

I 課題 I レポート (80%) I 講義における議論への貢献 (20%)

連絡など

質問がある場合は下記へ連絡下さい。 プライニング　ノルベルト preining@jaist.ac.jp 総合研究実験棟　３F C2-302a Office Hour 火曜日 3時限

学生のバック･グラウンド

数学と論理学に対しての考え

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

本日の目的

I 20世紀の発見 I 数学の便利さ I 歴史

第一例

フェルマーの最終定理

a b c ピタゴラスの定理 a2 + b2 = c2

ピタゴラスの定理の解

a = 1, b = 2 → c = √5 = 2.23607 . . . 特別の解　a = 3, b = 4 → c = ? 5 整数の解

フェルマーの最終定理

ピエール ド フェルマー

Pierre de Fermat

I フランス人、1607/8–1665 I 整数論、解析学、特に解析幾何学 I 素人の数学者 (?) 証明があまりないか 証明を伝えていない Source: Wikipedia

ディオファントスの算術 Source: Wikipedia

ディオファントス方程式

I 整係数 I 多変数 I 高次不定方程式

一次方程式

ax + by = c かつ a, b, c は整数　_{(∈ Z)} a, b, c の条件は？ – c はaとb の最大公約数の倍数

ピタゴラスの定理

2次方程式 x2 + y2 = z2 ディオファントス方程式ならば、可解である：(3, 4, 5)等 3次方程式 x3 + y3 = z3 ??? n 次方程式 xn + yn = zn ???

フェルマーの推測

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つの冪乗数の 和に分けることはできない。この定理に関して、私は真に 驚くべき証明を見つけたが、この余白はそれを書くには狭 すぎる。

フェルマーの推測

その意味は

推測

n > 2の場合は、xn + yn = zn の方程式は整数の解がない。 1995 年やっとアンドリュー・ワイルズ（Andrew Wiles）は証明 を見つけた。

フェルマーの推測の証明の歴史

xn + yn = zn 証明のためn は素数が足りる I n = 4: Fermat I n = 3: Euler (1770) I n = 5: Legendre, Dirichlet (∼1825) I n = 7: Lam (1839) I 1993年まで全ての素数 < ∼ 4.000.000 I . . . Wiles

ワイルズの証明

I 1955年：谷山・志村予想

I 1984年：ellliptic curve の関係

I 1986年：Ken Ribet, epsilon conjecture

I 1986年からワイルズは一人で証明を探している

I 1993年6月：Issac Newton Institute for Mathematical Sciencesで3日間のうちに発表 I 1993年8月：いろんな間違いが見つけられた I 1993–1995: Richard Taylorと一緒に修正 I 1995年5月：Annals of Mathematics フェルマーから 358年。。。

現在における影響

暗号化

I 楕円曲線暗号（elliptic curve cryptography）

I ECDSA – 楕円曲線DSA (elliptic curve digital signature algorithm)

I Dual EC DRBG Dual Elliptic Curve Deterministic Random Bit Generator

フェルマーとワイルズ

Source: Wikipedia

第二例

四色定理

いかなる地図も、隣接する領域が異なる色になるように塗るには 4色あれば十分だという定理である。

四色定理の歴史

I 1840年：M¨obius 推測 I 1890年：Heawood 五色定理 I 1870-1890年：いろんな正しくない証明

I 1976年：Appel and Haken コンピューター用な証明 初めて数学の定理の証明でコンピュータが使われていた！

証明の方法

Step 1

全ての地図を有限の種類に分割（最初 1936個） 伝統的な数学

Step 2

一つの代表が四色で色がぬれるならば、この分類の全ての個々の 地図が四色で色がぬれる。 伝統的な数学

Step 3

一つずつ代表を選んで、四色で塗る。 コンピューター・プログラム

その後

I いろんな間違いが発生したから、1989年修正してまた出版 された I 1996年：もっと早いアルゴリズム I 種類の減量 I 2005年：Coq 定理証明支援系　ー　検証 I まだ数学者は不満である

現在における影響

定理証明支援系言語の開発

第三例

ダフィット・ヒルベルト

David Hilbert I 1862–1943 I ドイツ数学者 I ヒルベルトの23の問題 I 1920年：ヒルベルト・プログラム 数学におけるすべての普遍妥当な論理式を機械的に導出可 能とする公理系と推論法則を構築する計画をいう。ヒルベル ト計画とも呼ばれる。

クルト・ゲーデル

Kurt G¨odel I 1906–1978 I オーストリア・ハンガリー帝国 I ヒルベルトの講義 一階述語論理の完全性の問題 I 1930年：一階述語論理の完全性定理の証明（24歳） I 1931年：不完全性定理の証明（25歳） I 1939-40年：ロシアー日本ー北米のPrinceton

不完全性定理のアイディア

このスライドの枠の中の文は正しくない

もう少し公式的に

I G は一階述語論理のは命題 I G の意味「G は証明できない」という I G の証明はできるかできないかどちらだろう？ I G は証明できるとしたら、G は正しい。 I G は正しいとしたら、 「G は証明できない」というのは正しい I 矛盾、 だから、G は証明できない。

不完全性定理の結論

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

まとめ

I 数学はまだ生きている I 20世紀はよく「数学の世紀」と言われている I 簡単な問題なのに、深い数学が現れる I 影響が強い I 楽しい！

次の講義

学校と大学の数学 ー 計算から証明まで

課題

「証明」の言葉が一杯の意味を持っている。 社会的、公法的、数学以外の科学等