数学者の常識は 　 世間の非常識 ! ? 守屋　悦朗 早稲田大学　教育学部

あなたの常識度は？ (1) １＋１＝？ 1,2,3,・・・の個数 ＜,＝,＞ -1,-2,-3,・・・の個数 1,2,3,・・・の個数 あなたの常識度は？ (1) １＋１＝？ 1,2,3,・・・の個数 ＜,＝,＞ -1,-2,-3,・・・の個数 1,2,3,・・・の個数 ・・・,-3,-2,-1,0,1,2,3,・・・の個数 「正しくない」は「正しい」の否定。 では、「正しくない」の否定は「・・・」 直径　　　　半径 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　次　 　　？ 　　？

あなたの常識度は？ (2) 「『関数』という名称は、数の増減の変化の様子を表わすことから付けられた」 yes? or no? あなたの常識度は？ (2) 「30世紀には、数学の定理はすべてコンピュータが証明してくれる」　yes? or no? 「『関数』という名称は、数の増減の変化の様子を表わすことから付けられた」　yes? or no? 集合とはものの集まりのことである yes? or no? 平行線は交わらない？　交わる？ 数学は答が必ずきちんと求まるから好きだ! yes? or no? 　　　 　　次

1,2,3,・・・の個数 <,=,> -1,-2,-3,・・・の個数 ＝ みんなの答 「個数」って、何？ 「個数が等しい」⇔１：１, onto の対応が付けられる（全単射） 1 2 3 ・・・ -1 -2 -3 ・・・ ・・・

1,2,3,・・・の個数 <? ・・・,-3,-2,-1,0,1,2,3,・・・の個数 1,2,3,・・・の個数 <? ・・・,-3,-2,-1,0,1,2,3,・・・の個数 ＝ みんなの答 どちらも、1,2,3,・・・と「番号を振る」ことができる それが1:1, ontoな対応(全単射)である 0, 1, -1, 2, -2, 3, -3, ・・・, n, -n, ・・・ 1, 2, 3, 4, 5, 6, 7,・・・,　2n, 2n+1,・・・ 可算無限の個数 自然数、整数、偶数、奇数、有理数はすべて可算無限 実数は？

実数すべてに番号をふることは できない ? つまり、実数は有理数よりもたくさんある！ 対角線論法 x1 = 0.x11x12x13・・・ … xn = 0.xn1xn2xn3・・・xnn・・・ y = 0.y1y2y3・・・ x11 x22 xnn y は ｘ１, ｘ２,・・・のどれとも等しくない! (yi≠xii)

数にもいろいろあって・・・ ものの始まりは自然数 1,2,3,・・・ 自然数1→整数2→有理数3→実数4の順に定義される 1Peanoの公理、2自然数上の同値関係（差を和で定義）、 3整数上の同値関係(整数の比)、4Dedekindの切断など 大学の数学では真っ先に登場します！ 自然数、整数、有理数の個数(濃度)は同じ 実数は有理数よりもたくさんある 実数よりもたくさんある「未知の数?」もある? こういったものとはまったく違う「数」だってある！

「30世紀には、数学の定理はすべて コンピュータが証明してくれる」 みんなの常識 「30世紀には、数学の定理はすべて コンピュータが証明してくれる」　みんなの常識 No! コンピュータでは証明できない命題がある！ ということが数学の定理として証明されている 数学の体系をどうやってコンピュータに教えるの？　 定理って何？　証明って何？ コンピュータの「計算」能力って何？ 　　　　　　　　　　↓ どっちも数学的にきちんと定義する必要がある

大数学者の夢 D.Hilbertのプログラム 数学の形式化 → 数理論理学（19c.中頃から） Next 　大数学者の夢 D.Hilbertのプログラム すべての数学を公理化・記号化して（コンピュータで扱えるようにして）しまおう 　　　　　　　　 （形式主義） 『すべての問題は解を持ち、それを見つける方法があり、すべての定理は証明できる』 数学の形式化 → 数理論理学（19c.中頃から） 公理や定理を文字列で表わす 推論は文字列を書き換えるルール 有限回の推論の結果出てくるものが定理 こういうことはコンピュータでも処理できる 　　　　　　　　　　　　　　　　　　　　　　　　　　Next

命題を文字列で表わす 戻る P(x, y, z) ⇔ x=yz xはyとzの積である とする 命題を文字列で表わす　　　戻る P(x, y, z) ⇔ x=yz　　　　　　　　　　　　 xはyとzの積である とする Q(x,y)　= ∃z P(x,y,z)　 　　　　　　　 xはyで割り切れる S(x) = ∀y［Q(x, y)→ (y=1∨y=x)］　　 xは素数である ∃xS(x)　　　　　　　　　　　　　　　　　　　 素数は存在する ∀x［S(x)→∃y[S(y)∧y>x］　　 　 素数は無限に存在する と、 = ∃x∀y［Q(x, y)→ (y=1∨y=x)］

推論：正しいものから正しいものを導くこと 戻る 推論：正しいものから正しいものを導くこと 　　　　　　　　　　　　　　　　　　　　　　戻る 三段論法 　((A→B)∧(B→C))→(A→C) 対偶 　(A→B)⇔(￢B→￢A) 推論(MP) A A→B ・・・すでに証明されている命題2つ　 　　　 B 　　　　 ・・・導き出した命題

証明の過程　　　　　　　　　　　　戻る 公理１　　　公理５　　　　　　　　　　　　 推論1 公理３ 定理１ 公理２ 推論3 推論1 定理２ 定理３ 推論2 定理４

例： 公理・推論規則・定理の証明 B→C (B→C)→[A→(B→C)] (A→B)→(A→C) A→B 公理1 A→(B→A) 推論規則１ A A→B B 三段論法が正しいことの証明 B→C (B→C)→[A→(B→C)] [(A→(B→C)]→[(A→B)→(A→C)] A→(B→C) (A→B)→(A→C) A→B A→C 　　　　 A→B B→C 仮定 公理１ 推論規則１ 公理２ 推論規則1 仮定 推論規則1 ∴

夢、ついえる 不完全性定理(K.Gödel, 1931年) 　夢、ついえる 不完全性定理(K.Gödel, 1931年) 『自然数論を含み無矛盾な、どんな数学の体系にも、正しいことも正しくないことも証明できないような命題が存在する』 「自分が正しい命題であることを証明できる」と主張する命題は、正しいことも正しくないことも証明できない 絶望？　No! すべての数学の体系を記号化することはできないけど、まだ望みは残っている

まだ望みはある？ もっとやさしい問題だったらコンピュータで計算 できるんじゃないの？ 例えば、 判定する方法（計算の手順）は無さそうだ！ Hilbertの第10問題(1900年、23の数学の問題の10番目） 整数係数の不定方程式が整数解をもつかどうか判定する判別式を求めよ。 整数係数不定方程式 とは：　 3x2y3-7xy2z+5z3+23=0 など 　　公式を求める努力をしてみたけれど・・・ 判定する方法（計算の手順）は無さそうだ！

計算って何なのかを考え直さなくっちゃ 判定する方法（計算の手順）は無さそうだ！ ↓ 　　　　　　　　　↓ 計算の手順（アルゴリズム）とは何かを数学的に定義する必要がある 数学的な定義は1930年代になってから いろんな数学者（A.M.Turing, E.L.Post, A.Church, S.C.Kleene, K.Gödel）がいろんな観点から異なる 定義を提案したがすべて一致した 自然数の上の計算可能関数、コンピュータの数学的モデル、文字列書き換えシステム、等々

オートマトン ＝ 計算モデルの１つ 自動機械の数学モデル 例えば、こんな感じで動作する オートマトンの例 アルゴリズム（計算）の定義 オートマトン　＝　計算モデルの１つ 自動機械の数学モデル 例えば、こんな感じで動作する 　　　オートマトンの例 アルゴリズム（計算）の定義 オートマトンで処理できることが計算できること 他の定義もすべてこの定義と一致する 　　→　今では、すべての数学者が認める定義

答を導く方法が無い問題がある！ Hilbertの第10問題は計算不能！ 他には？ (x1, y1), …, (xn, yn) : 文字列の組 答を出す一般的公式（アルゴリズム）は存在しえない Ju.v.Matijaseviĉ, 1971年 計算不能なことが証明された最初の問題 具体的な問題でなくてもいいなら証明はそれほど難しくない 他には？ (x1, y1), …, (xn, yn) : 文字列の組 xi1xi2・・・xik = yi1yi2・・・yik とできるか？　具体例

Post の対応問題 P1: (01, 011), (11, 1), (100, 00) ∥ ∥ ∥ ∥　　　　∥　　　　　∥ 　 (x1 , y1), (x2, y2), (x3 , y3)　 解の１つは P2: (a, b) 　　解なし P3: (ab, ba), (aab, aa) 　解なし x1 x2 x1 x3 = 01 11 01 100 y1 y2 y1 y3 = 011 1 011 00

やさしい問題ならどうかな？ やさしい問題って何？ 巡回セールスマン問題は∈P？ 問題のサイズを n とするとき nk 時間で解けるもの 多項式時間(polynomial time) →　問題クラス P 巡回セールスマン問題は∈P？ n 個の都市と、都市間の距離が既知 すべての都市をたどる最短経路を求めよ。

セールスマンは、 どういう順路で回るのがベスト？ 辺＝一方通行路（距離はすべて１）、辺のないところは距離∞　 という特別の場合でも・・・ a ｂ ｃ ｄ ｆ ｇ ｅ

答 ・・・ すぐにはわからなかったでしょう？ 答　・・・　すぐにはわからなかったでしょう？ a ｂ ｃ ｄ ｆ ｇ ｅ

多項式時間では解けそうもないけど、 解の検証は多項式時間でできる場合は・・・ そういう問題のクラスが　NP nondeterministic polynomial time 巡回セールスマン問題∈NP P=NP?　 ミレニアム問題：　米国クレイ数学研究所、2000.５.24 懸賞金100万ドル（約一億一千万円） １．Ｐ＝ＮＰ問題、 ２．ホッジ予想、３．ポアンカレ予想、 ４．リーマ ン予想、５．ヤン-ミルズ理論とmass gap、 ６．ナヴィエ-ストークス方程式とsmoothess、 ７．バーチとスウインナートン-ダイアーの予想

NPのどの問題も 解くのに指数関数的時間がかかりそうだ！ → 多項式時間では解け（そうも）ない！ 多項式 nk (k>0 は定数) 指数関数 an (a>1 は定数) どんな k, a でも、n が十分大きいと an>nk. つまり、任意の n に対して an≦nk となる多項式 nk は存在しない。 例えば、n>210=1024 なら 2n>n100. n≧4 なら n!>2n. つまり、n! は上から多項式で押さえることができない。

NP完全問題 次の問題はもっとむずかしい！ 次の問題のどの1つでもPに属すことが示せればP=NPである 巡回セールスマン問題、ナップザック問題 集合分割問題、部分集合和問題 時間割作成問題、ジョブスケジューリング問題 ３彩色問題　　　　　　などなど、何千という問題 次の問題はもっとむずかしい！ 将棋や碁や類似ゲームにおいて、先手必勝法があるか？ 尻取りゲームの先手必勝法

１＋１＝？ どんな代数系（数学の世界）を考えるかによる！ ガロア体では １＋１＝０ 「体」って何？ → 四則演算ができる世界 加減算は？ 　「体」って何？　→　四則演算ができる世界 加減算は？ 0+0=0, 1+0=0+1=1, 1+1=0, 0-0=0, 1-0=1, 0-1=1, 1-1=0 乗除算は？ 1・0=0・1=0, 1・1=1, 1÷1=1, 0÷1=0 加法と乗法の間の関係は？ x・(y+z)=x・y+x・z, x+(y・z)=(x+y)・(x+z) たい

ガロア体あれこれ 0=論理値 「真」、1=「偽」 コンピュータ等の回路設計で重要 暗号の理論でも重要 x+y : 排他的論理和（x,y のどちらか一方だけが成り立つの意） x + yとも書く x・y : 論理積（xかつyが成り立つの意） コンピュータ等の回路設計で重要 暗号の理論でも重要 x + y=(x+y) mod 2 であり、これをもっと一般化して 　 x + y=(x+y) mod p で定義しても体である(pは素数）

「正しくない」は「正しい」の否定。 では、「正しくない」の否定は「正しい」？ 「正しくない」は「正しい」の否定。 では、「正しくない」の否定は「正しい」？ yes ほとんどの数学者はそう考えている(古典主義論理) でも、それを認めない数学者もいる そういう数学もありうる ← 数学は自由だ！ 直感主義論理(20c.初頭)　　 オランダの数学者 L.E.J.Brouwer が代表的 ￢￢A→A は認めず、[(A∨B)∧(￢A)]→B を認める でも、狭い数学の世界になってしまう

『関数』という名称は、数の増減の変化の様子を表わすことから付けられた？ 　　　　　　　　　　　　　　　　　　　　　　　みんなの答 No! 「数」とは無関係 英語名 function を中国語「函数」（ファンスー）に音訳したもの 「写像」、「対応」とも言う function：　意味は「機能」「作用」

集合とはものの集まりのことである？ No X = { x | x は集合で、x∈x } そんなに素朴な定義をすると困ったことが起こる 集合とはものの集まりのことである？　　 No みんなの答 そんなに素朴な定義をすると困ったことが起こる パラドックス（逆理：一般に受け入れられている論に反するのに、 　　　　　　　　　　　　　　　　　 それに反駁することができないような論） 次の X も集合のはずだけど・・・ 　　　　　　　X = { x | x は集合で、x∈x } 　　　　 とすると、 　X∈X ⇒ X∈X 　　　　　X∈X ⇒ X∈X 　　　 いずれにしても矛盾！ →　公理的集合論の導入へ

半径≦直径≦２・半径 みんなの答 次の図形の直径は？半径は？ 径・・・みち → 距離 点 P から最も遠い点は？ 半径≦直径≦２・半径 　　　　　　　　　　　　　　　　　　　　みんなの答　 次の図形の直径は？半径は？ 径・・・みち → 距離 点 P から最も遠い点は？ 「最も遠い点」が最も遠い点は？　最も近い点は？ 　　　　　　　　　　 　　　どの2点？　　　　　　　　　 ・P

半径・直径を考えることが出来るのは円だけじゃない！ いろんな場合を考えるのが数学！ 三角形の場合は？ 外心との関係は？ 四角形の場合は？ グラフだったら？ 連続な図形でなくても、平面図形でなくても 「中心」って、どういう点だろう？ 半径を与える点 一般に言えることは？ 半径≦直径≦２・半径

平行線は交わらない？ 交わる？ みんなの答 平行線の公準 ユークリッドの原論 第5公準は他の公理・公準から導き出せるのでは？ 平行線は交わらない？　交わる？ 　　　　　　　　　　　　　　　　　　　みんなの答 平行線の公準 『平面内に１直線と１点が与えられれば、その点を通り、その直線と交わらない平面内の直線は唯１つ存在する』 ユークリッドの原論 ユークリッド幾何学の集大成 B.C.4c.頃？　ギリシャ プラトン創設のアカデミー 第I巻は定義、公理、公準、定理（ピタゴラスの定理など） 第5公準は他の公理・公準から導き出せるのでは？ 長い歴史 P L

ユークリッドの原論 （定義） 定義（23個） 点は部分をもたないものである. 線とは幅のない長さである. 線の端は点である. ユークリッドの原論　（定義） 定義（23個） 点は部分をもたないものである. 線とは幅のない長さである. 線の端は点である. 直線とはその上にある点について一様な線である. 面は長さと幅のみをもつものである. ・・・

ユークリッドの原論 （公理） 公理 ・・・自明として受け入れるもの 同じものに等しいものは互いに等しい． ユークリッドの原論　（公理） 公理　　・・・自明として受け入れるもの 同じものに等しいものは互いに等しい． a=b, a=c ⇒ b=c 等しいものに等しいものを加えれば，また等しい． a=b, c=d ⇒ a+c=b+d 等しいものから，等しいものを引けば，残りは等しい． a=b, c=d ⇒ a-c=b-d 互いに重なり合うものは互いに等しい． 全体は部分より大きい．

ユークリッドの原論 （公準） 公準 ・・・ 要請ないしは仮定 1. 任意の点から任意の点へ直線を引くこと． ユークリッドの原論　（公準） 公準　・・・　要請ないしは仮定 1. 任意の点から任意の点へ直線を引くこと． 2. 有限な直線を連続的に直線に延長すること． 3. 任意の点を中心とする任意の半径の円を描くこと． 4. すべての直角は互いに等しい． 5. 直線が2直線と交わるとき，同じ側の内角の和が2直角より小さいなら，この2直線は限りなく延長されたとき，内角の和が2直角より小さい側において交わる．

第５公準（平行線の公準） 『直線が2直線と交わるとき，同じ側の内角の和が2直角より小さいなら，この2直線は限りなく延長されたとき，内角の和が2直角より小さい側において交わる． 』

平行線の公準は 他の公理や公準から証明できる？ No! 非ユークリッド幾何学 平行線の公準を否定すれば別の幾何学ができる N.I.ロバチェフスキー (ロシア), 1829年 Y.ボヤイ (ハンガリー), 1831年 K.F.ガウス, もっと以前から知っていたが発表せず 第5公準の変更 『１直線外の１点を通りその直線に平行な直線は１本ではない』

非ユークリッド幾何の具体例 ポアンカレのモデル リーマン幾何 平面に相当するものは円の内部 平行線は無限に存在する 三角形の内角の和は180度より小さい リーマン幾何 平面に相当するものは球面 異なる２直線は２点で交わる 平行線は存在しない 三角形の内角の和は１８０度より大きい

数学の問題は答が必ずきちんと求まる？ No! 決定不能問題、計算不能問題が存在する 不完全性定理 証明できるともできないとも言えない命題さえある

終わり 少しは数学への興味を増してくれたかな？

自然数の定義 S(x)=x+1 ペアノの公理 G.Peano, 1889年 自然数の集合 N とは次の公理を満たすもの： 戻る 公理2. 全単射 S: N→N, 1∈S(n) 公理３(数学的帰納法の原理) 次の(a),(b)を満たせば M= N (a) 1∈M (b) n∈M ⇒ S(x)∈M 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　戻る S(x)=x+1

実数の定義 デデキントの切断 R.Dedekind 有理数の集合を次の条件を満たすA,Bに分ける A∩B=Φ, A∪B=Q, A≠Φ, B≠Φ a∈A, b∈B ⇒ a<b （１） A には最大の数 a が存在するが、B には最小の数がない。 （２） A には最大の数がなく、B には最小の数 b が存在する。 （３） A には最大の数がなく、B には最小の数がない。 （４） A には最大の数 a が存在し、B には最小の数 b が存在する。 A B ×

切断が定義する実数 A B × （１） A には最大の数 a が存在するが、B には最小の数がない。 r2<2 である正の有理数またはの負の有理数の全体 （１） A には最大の数 a が存在するが、B には最小の数がない。 （２） A には最大の数がなく、B には最小の数 b が存在する。 （３） A には最大の数がなく、B には最小の数がない。 （４） A には最大の数 a が存在し、B には最小の数 b が存在する。 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 戻る r2>2 である正の有理数の全体 A B √2 有理数 a を定める 有理数 b を定める 無理数を定める ×

みんなの常識 (1) １＋１＝1 （全員） 1,2,3,・・・の個数 ＝ -1,-2,-3,・・・の個数 みんなの常識　　　　 (1) １＋１＝1 （全員） 1,2,3,・・・の個数 ＝　-1,-2,-3,・・・の個数 1,2,3,・・・の個数 ＜ (多数意見) ・・・,-3,-2,-1,0,1,2,3,・・・の個数 「正しくない」は「正しい」の否定。 では、「正しくない」の否定は　「正しい」 直径　＝ ２× 半径 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　戻る

みんなの常識 (2) 「『関数』という名称は、数の増減の変化の様子を表わすことから付けられた」 わからない みんなの常識　　　　 (2) 「30世紀には、数学の定理はすべてコンピュータが証明してくれる」　 no　（多数意見） 「『関数』という名称は、数の増減の変化の様子を表わすことから付けられた」　わからない 集合とはものの集まりのことである 　yes 平行線は交わらない 数学は答が必ずきちんと求まるから好きだ! 　 no? 　　　 　　戻る