Comments
Description
Transcript
第 2回講義4月21日資料
情報数学 Ⅰ 配布日時 2014 年 4 月 21 日 自然数に最大限は存在しない。 従って、いくらでも大きな自然数が存在する。 数学的には、巨大数と言っても意味がないが、日常生活において使用される数よりも巨大な数を 巨大数(数学的な定義ではない)と呼ばれる。巨大な数は、数学、天文学、宇宙論、暗号理論、イン ターネットやコンピュータなどの分野でしばしば登場する。天文学的数とも呼ばれることもある。 ただ、数の記述法では幾らでも大きな数は表現できるので、巨大数と言った場合何かの意味が ある巨大な数である必要がある。 自然数に関してペアノの公理を採用するので、数学的帰納法が成立している。 【数学的帰納法】 自然数に関する命題 P(n) が全ての n に対して成り立っている事を証明するためのものである。 1. P(1) が成り立つ事を示す。 2. 任意の自然数 k N に対して、 P(k ) P(k 1) が成り立つ事を示す。 3. 以上の議論から任意の自然数 n N について P(n) が成り立つ事を結論づける。 注) a N にたいして、 n N ( n a) で P(n) が成り立つのも同様である。 例題: 3円の切手と4円の切手だけあれば6円以上の郵便料金を支払えることを証明せよ。 変な帰納法(ネットから参照) ・・・ 貧乏人の帰納法 ●食べ物には賞味期限はない 1)まず、賞味期限が「1秒」過ぎた食べ物があるとしよう。 この食べ物はもう食べられないのか?否、大丈夫だ。 なぜなら、さっきまで大丈夫だった食べ物が たった「1秒」で腐るとは考えられないからだ。 2)次に、賞味期限が「 k 秒」過ぎた食べ物はまだ大丈夫であると仮定する。 では「 k 1 秒」過ぎた食べ物はどうであろうか?大丈夫である。 なぜなら、さっきまで大丈夫だった食べ物が たった「1秒」で腐るとは考えられないからだ 以上より、賞味期限の過ぎた食品の安全は数学的帰納法により証明される。 ●全員ハゲ!? 1)まず、髪の毛が「1本」生えている人がいるとしよう。 この人はハゲなのか?そう、ハゲだ。 百人に聞けば百人がハゲと答えるだろう。 情報数学 Ⅰ 配布日時 2014 年 4 月 21 日 2)次に、髪の毛が「 k 本」生えている人はハゲであると仮定する。 では「 k 1 本」生えている人はハゲであろうか?ハゲである。 なぜなら、1本多いだけでは何も変わらないからだ。 以上より、数学的帰納法から… 全 員 ハ ゲ ってことは無いです。 何処が間違っているか? 「全ての人は貧乏人」 、 ← 貧乏人の帰納法とも呼ばれる。 「巨大数は存在しない」 【大きな数の書き方】 乗算は加算の反復 a b a a a a をb 回 べき乗 a b a a a a をb 回 なお、一部の初期のコンピュータでは、上向き矢印を冪乗演算子に使ったので、それを使うと a b a a a a をb 回 例として、以下に出るグーゴルプレックス ( ) は 10↑10↑100 である。 テトレーション クヌースは、二重矢印をテトレーション(指数計算の反復)を表す演算子として定義した。 a b a a a a をb 回 情報数学 Ⅰ 配布日時 2014 年 4 月 21 日 それ以上・・・クヌース 上向き矢印を沢山導入。 Clifford Pickover による、自然数 n の超階乗(ちょうかいじょう, superfactorial)の表記 法 n $ は、階乗を入れ子に拡張して のように定義される。簡単に言えば、n! の n! 乗を n! 回入れ子にする演算である。上記の式 で 2 つ目及び 3 つ目の等号は、タワー表記による表記の場合である。 例 【組合せ論的数】 組合せ数学において、組合せの場合の数などは急激に大きくなる数で、組合せ爆発といった語も ある。たとえば、一意な要素の集合についての順列の数である階乗関数は、非常に急速に発散す る関数である。それを拡張したものとして、超階乗も考えられている。 ・ 無量大数 - 10 68 、 10 88 とすることも 無量大数は漢字文化圏(漢字圏)における数の単位の一つ。 ・グーゴル – 10100 100 グーゴル (googol) とは、数の単位であり、1 グーゴルは 10 の 100 乗 ( 10 ) である。 グーゴルは 1920 年に誕生したもので、アメリカの数学者エドワード・カスナーの当時 9 歳の甥ミ ルトン・シロッタ (Milton Sirotta) による造語である。カスナーはこの言葉を著書「数学と想 像力」の中で紹介している。 1 グーゴルは 1 の後に 0 が 100 個連なった 101 桁の整数であり、次のように書くことができる。 1 グーゴル = 10100 = 10, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000 この数は 70 の階乗 (70!) に比較的近い。70 の階乗は次のような 101 桁の整数である。 情報数学 Ⅰ 配布日時 2014 年 4 月 21 日 70! = 11, 978, 571, 669, 969, 891, 796, 072, 783, 721, 689, 098, 736, 458, 938, 142, 546, 425, 857, 555, 362, 864, 628, 009, 582, 789, 845, 319, 680, 000, 000, 000, 000, 000 79 81 1 グーゴルは観測可能な範囲の宇宙に存在している原子の数(およそ 10 から 10 個と推算され ている)よりも多い。 多くの関数電卓では 10 進法で指数部が 2 桁までしか表せないので、絶対値が 1 グーゴル以上の数 や途中計算で 1 グーゴルを超える数式は扱えない。 また、グーゴルをもとにしたグーゴルプレックス(10 の 1 グーゴル乗 (10↑googol)、すなわち 10 の 10 の 100 乗 (10↑10↑100))やグーゴルプレックスプレックス(10 の 1 グーゴルプレックス乗 (10↑googolplex)、すなわち 10 の 10 の 10 の 100 乗乗乗 (10↑10↑10↑100))もある。 Google との関係 インターネットの検索エンジンである Google の名前は、命名者ラリー・ペイジによるグーゴル (googol) の綴り間違いに由来する。Google で「googol」を検索すると、Google の計算機機能により 1 グーゴルは 10 の 100 乗である旨が表示される。 ・ センティリオン - 米・加では 10 303 、欧州(英連邦)では 10 600 ・知られている最大の素数 - 2 57885161 1 ≒ 5.8188×1017425169 (2013 年 2 月発見) ・不可説不可説転 - 10^{7\times 2^{122}} ^ = ↑ ・グーゴルプレックス – 10^googol=10^{10^{100}} ・第一スキューズ数 - e^{e^{e^{79}}} ・グーゴルプレックスプレックス - 10googolplex=10^{10^{10^{100}}} ・第二スキューズ数 - 10^{10^{10^{1000}}} ・スタインハウスのメガ ・スタインハウスのメジストン ・モーザー数 ・グラハム数(単なる巨大さ以外で意味のある考察の対象となったことがある最大の有限数) ○計算不可能な手続による巨大数の構成 ビジービーバー関数 Σ は、あらゆる計算可能関数よりも速く増大する関数の一例である。ビジービー バー関数自身は計算不可能である。引数が比較的小さな値であっても巨大な値を返す。n = 1, 2, 3, 4 に対して、Σ(n) の値はそれぞれ 1, 4, 6, 13 である。Σ(5) は未知であるが、4098 以上の値をとる。Σ(6) は少なくとも 1.29×10^865 である。 情報数学 Ⅰ 配布日時 2014 年 4 月 21 日 1.2 整数 自然数と整数の違いは何か? N {1, 2, 3, 4, } Z { , 2, 1, 0, 1, 2, } 整数には0と負の数がある。 負の数 -1 とは何か? 代数的歴史 xn 1 0 x 10 方程式 を考える。 x はどこの元であるかは、不問とする。 x2 1 0 x3 1 0 x4 1 0 数は自然数から始まる。 x N に対して、 x 1 0 となるか? No! 代数的な解決は x 1 0 を満たす解 を導入する。 最終的には を 1 と書く。 x 2 1 0 では、 それを満たす を導入する。 i n では、 n 2 に対して、 x 1 0 はどうでしょうか? ・負の数 負の数について論じた最古の文献は、インドの数学者アリヤバータ (476 - 550) による今日『アーリ ヤバティーヤ』と呼ばれるテキストで、そこでは負数の加法と減法の満たす規則が定められており、ま た負数は負債を表し、正数は収入を表すものとして表れている。数世紀のち、ペルシアの数学者アブ ル・ワファー (940 - 998) は負数同士の積が正数であることを記しているが、しかし依然として数は 何らかの物理的な量に結び付けられており、負数が実存のものとして市民権を得るのは困難な状態で あった。例えばフワーリズミー (783 - 850) は二次方程式を係数に負数が現れぬ六種類に還元帰着す ることによって扱っている。 ヨーロッパで整数の概念が現れるのは遅く、よく知られた二整数の積に対する符号の規則は一般にス テヴィン (1548 - 1620) に帰せられる。またダランベール (1717 - 1783) は、彼の百科全書におい て整数が危うい概念であると述べている。 ダランベール『百科全書』 「負数に関する概念を正すには困難を伴うこと、および幾人かの賢人すらもまさに彼らの与えたいく 情報数学 Ⅰ 配布日時 2014 年 4 月 21 日 つかの概念によって僅かばかり混乱を助長したことを認めねばなりません。負数が単に 0 より小さい 量であると言うためには、負数自身は思い描くことのできぬものとして論を進めねばならないのです。 1 と −1 は比較できないと主張し 1 と −1 との関係は −1 と 1 との関係と異なるものであるとする ことは、二重に誤っています。……」 整数の構成 負の数 1 とは何だろうか? N 2 N N (a, b) | a, b N (a, b) , (c, d ) N 2 にたいして、以下の関係を導入する。 (a, b) ~ (c, d ) a d b c この関係は同値関係であるので、この同値関係による商集合 N /~ を作る。これは、互いに同 2 値なもの全体の集合(同値類)を元とするような集合であり、直観的には互いに同値であるようなもの を同一視する操作である。 元 (a, b) N 2 の属する同値類を [a, b] N /~ と表すことにする。つまり、 [a, b] は 2 [a, b] { (c, d ) N 2 | (a, b) ~(c, d ) } となる集合である。同値類を [a, b] のように表したとき、(a, b) をこの同値類の代表元と呼ぶ。代表 元は同値なものでありさえすれば他のものに取り替えることができる。商集合 N /~ に加法 + と 2 乗法 × を [a, b] [c, d ] [a c, b d ] [a, b] [c, d ] [a c b d , a d b c ] と定義すると、これらは代表元の取り方によらずに、同値類同士の演算としてうまく定義されている ことが確かめられる。 このとき、[a, b] [m, m] [a m, b m ] [a, b] だから、R { (m, m) | m N } は N /~ の加 2 法に関する単位元である。また、自然数 m に対して [m 1, m] を対応させる写像は単射で [m + 1, 1] + [n + 1, 1] = [m + n + 2, 2] = [(m + n) + 1, 1], [m + 1, 1] × [n + 1, 1] = [(m + 1)(n + 1) + 1, (m + 1) + (n + 1)] = [mn + 1, 1] 2 を満たす(準同型)ので N は N /~ に演算まで込めて埋め込める。記号の濫用ではあるが、自然数 m N を埋め込んだ先と同一視して m [m 1,1] と書くことにし、これを(正の)整数 m と呼ぼ う。 自然数 m に対し、新たな記号 m を m [1, m 1] を表すものとして導入し、これを負の整数 m と呼ぼう。負の整数同士の積が正の整数になっていることが確認できる。 このとき、m + (−m) = [m + 1, 1] + [1, m + 1] = [m + 2, m + 2] = R だから、負の整数 −m = [1, m + 1] は N 2 /~ においてはちょうど、正の整数 m = [m + 1, 1] の加法に関する逆元 情報数学 Ⅰ 配布日時 2014 年 4 月 21 日 になっている。R をあらためて 0 と書くことにして、 N 2 /~ { m, 0, m | m N } を整数全体 の集合とよび、あらためて Z と書くことにしよう。 このようにして整数の全体 Z が厳密に定義されたが、なお定義に従えば Z において結合法則 や分配法則などの環の公理が満たされることがきちんと証明できる。 【ピタゴラスの世界】 『第2話 愛と恋』 これから、ピタゴラスの世界観を説明します。きっと解らなくなるから、良く説明を聞いていて下さ い。まず、1は理性を表す。2は女、3は男、4は正義または真理、5は結婚。6は恋愛、霊魂。7は 何を示しているか解るね。 ――幸福。その頃から、ラッキーセヴンがあったのか。 8は本質、愛。ピタゴラスは8を特別な数と考えたようです。さっきの、オクターブの発見から、8に 対して愛着や、意味をもたせていたのだろう。9は色々調べてみたが解らなかった。10は神聖な数。 なんせ、1(最初の数)+2(最初の偶数)+3(最初の奇数)+4(最初の平方数)=10なのだか らだ。 さて、1+2=3だがこの式の意味する所は何か。 ――女を馬鹿にしちゃいけないよ。 誤解の無いようにして欲しいのだが、これは僕の意見ではない。ピタゴラスの考えだからね。 2+3=5 これなんか簡単に解るね。当時、掛け算の方が足し算より高尚だと考えられていた。そこで、同じ事だ が 2×3=恋愛となる。 ――結婚と恋愛は違うの。 古代ギリシャでは、恋愛と愛とは違う物だと考えられていた。恋愛は、動物的なもので、愛は人間だけ が持つもの、だから恋愛より愛の方が優れている。 ――でも、愛人は悪い意味で、恋人は良い意味に使われるんじゃない? ――(笑いながら)3+3=6はどう解釈するの? 当時は、さっきの恋愛と愛の違いと同じ理由で、男と女の愛よりも男同志の愛の方がより優れた愛だ と考えられていた。だから、3+3の方が2+3より値打があると考えたわけだ。 情報数学 Ⅰ 配布日時 2014 年 4 月 21 日 ――これは、ホモじゃないの。 いや、友情と考えた方がいいかもしれない。プラトンの本にそう書いてあるんだ。 ところで、昔の日本によく似たことも引出せる。たとえば、2+5=7 を訳すと、 「女の幸せは結婚 である」なんかは、昔の日本にも当てはまるよう内容だね。古代ギリシャと現代日本とそう変らないわ けだ。 ――私は、結婚が幸せだとは思わないよ。 ――2+2+3=7はどういう意味ですか。 (男子はどっと笑う) 気持は分かるが、これを説明したら女の子から嫌われるからやらない。 ところで、この考え方は、人類が持った始めての体系的な世界観じゃないかなあ。 ――数で人生を表わすなんて、確かに面白い考え方だなあ。 このようにピタゴラスは、世界は数で説明できるし、数からできていると考えていた。数に特別の意味 があるものと考えていた。たとえば、6の約数は? ――2と3と6。 それだけ? ――あっ。1もそうだ。 そう、6はぬいてあとのを全て足してごらん。1+2+3=?。 ――6になる。 このように自分以外の約数を全て足すと自分自身になる数は大変珍しい。こういう数にピタゴラスは 完全数と名前をつけた。完全数はまだある。6が一番小さい完全数だ。では次の完全数はいくつか? ――やってみよう。でも、だいたいいくつぐらい? 20と30の間にある。 ――解った。 ピタゴラスが6を霊魂や恋愛としたのも、こういう意味からだろう。神様が6日間で全てのものを創 ったという神話もここから来ているかもしれない。 参考文献 『数学セミナー100人の数学者』