Sokratesさんの備忘録ないし雑記帳

思考の流し台. 駄文注意.

【備忘録】人生で一度は証明を追いたい命題一覧

 だいぶ前にTwitterで「人生で一度は証明を追いたい定理」とかいう話題が盛り上がっていた. もとツイートを探そうかお思ったんだが, 見つからなかった(←探し方が悪い)ので誰が言い始めたのかはわからないのだが, 「なるほど, 確かにそういう定理・命題・補題はいくつかあるな」と思ったのを覚えている. 

 ふと, そういうものをまとめてみようかという気分になったので, ここに一覧を晒すことにした. これは自分のモチベーション維持*1と「この命題の証明もかっこいいで」という情報が入ってくることを期待してのものである. 難易度がバラバラだったり分野に偏りがあるがご容赦願おう. どうせこの後どんどん増えていくし. 

整数論

・Fermatの最終定理 

  どうあがいても追いたい証明一位だった. ここが原点の数学徒は多いのでは. 

・Gelfond-Schneider の定理

  超越数論の一里塚のはず. 超越数論でとてもでかい結果と聞いているので興味はある. 

Logic

・Gödelの不完全性定理(特に第二の方)

  概略を追ったことはあるはず(ホントに追えてたかも怪しい)だが, やっぱりよくわかっていないのでもう一度追いたい. 主張はよく使うのにね. 

・Presburger arithmetic が否定完全であること

 これも結果はよく使うのに証明をよく知らない. Quantifier freeの形に変形するらしいのだがよくわかっとらん. 

Lindstrom Theorem

 最近知った定理で一階述語論理は「コンパクト性定理」と「Löwenheim–Skolem theorem」で特徴づけられるというものらしい. すさまじくきれいな定理である. 

・Getzen の算術の無矛盾性証明

Set Theory

・ZFCと連続体仮説の独立性. 

  Forcing わかりません案件.

・ZFのモデルで$\mathbb{R}$の任意の部分集合が Lebesgue 可測であるものが存在する. 

・Diaconescu's theorem

Category Theory

・米田の補題

 追ったんだよ, 一回. でも理解できてない感がすごいし, 定理の主張の内容も明らかによくわかってない. 圏論力を高めて再チャレンジしたい. 

*1:「えー, まだこの証明追っていないのぉ」という数学徒からの煽りとも言う. あまり言われると心折れるのでほどほどにネ.

数学と比喩~CR性は崇徳院である~

 数学をやっているとすごいレベルの比喩でもって数学的な概念を説明してくれる人に出会う. 最近自分の中でヒットしたのは「CR性は崇徳院」というものだ. 

 

 CR性というのは"Church Rosser 性" というものである種の順序集合の性質のことである. 正確には次のような性質である. 

定義 CR性

 $S$を集合, $>$を$S$上の二項関係とする. 

 $S$上の列で$s_0 > s_1 > \cdots > s_n $(ただし, $n \in \mathbb{N}$)というものがあったとき, $s_0 >\!\!\!> s_n$と書くことにする. 

 任意の$s, s_1, s_2 \in S$に対して$s >\!\!\!> s_i  \, \,  (i=1, 2)$ ならば, ある $s' \in S$ で $s_i >\!\!\!> s'$ を満たすものが存在するとする. 

 このとき, $\left(S, > \right)$はChurch Rosser 性(略してCR性)を持つと言う. 

 要は列が必ずどこかで合流するという性質である.  

 

 崇徳院というのは第75代天皇歌人として有名な方である(日本史弱者並みの紹介. 詳しくは 崇徳天皇 - Wikipedia を見てくれ). この方の和歌に次のようなものがある.

瀬を早(はや)み 岩にせかるる 滝川(たきがは)の

   われても末(すゑ)に 逢はむとぞ思ふ

小倉百人一首の77番目の詩として有名なこの歌だが, 意味としては次のようになる(と思う). 

水の流れが早くて, 岩によって流れが二つに分かれてしまう川であっても, (下流のほうで)最終的には合流する.  (そのように一度別れたとしても)あなたともう一度会いたいものだなぁ.  

 「CR性は崇徳院」というのはこの川の流れの合流性がCR性というものを表しているではないかということである. なんともロマンチックなたとえである. こういうのがサラッと言える大人はかっこいい. とある勉強会で聞いたたとえだが, こういうことを一度でいいから素で言ってみたいものである. 

 

参考文献

[1]高橋正子, 計算論, 近代科学社

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

 

 CR性の定義の参照に使っただけだけど一応......

 型なしλ計算の定番の教科書である. 

 [2] 

【百人一首講座】瀬をはやみ岩にせかるる滝川の われても末に逢はむとぞ思ふ─崇徳院 京都せんべい おかき専門店【長岡京小倉山荘】

崇徳院のほうはgoogle先生で「崇徳院 百人一首」検索したら, 一番頭に出てきたこちらを参照した. 訳は著作権的なチョメチョメが怖かったので自分で考えた(ので, 厳密には間違ってるかも). 

文章を書くときに好きな文字数

 なんか, 眠れないので久々にブログを書いてみることにする. 半年ぶりらしいけど, そんなこと気にせず書く. 

 

 文章にはひとそれぞれ向いている長さがある気がする. 基本的にTwitterに張り付いていることが多いのだが, この時のつぶやきは50文字くらいが心地よい. ほぼ脊髄反射*1で打てる量だからだ. 

 これ以上長い発言をしようとすると, 140文字では足らない. 連ツイの傾向を思い出す限り, 500文字くらいは欲しい気がする(もしかするともう少し短いかも). 

 さらに長い発言をしようとすると, 結果的に2500文字くらいは行く気がする.

 

 50, 500, 2500という中途半端な刻みだが, 大体僕の書く文章は大体この数字の周辺の周りに固まっている気がする(統計を取ったわけではない).

 

 逆にこれらの周辺の数字でない, 1500文字くらいで書けと言われるととても苦労する. 院試の時に書いた書類が確かそのくらいの長さで求められていて, 内容自体は1時間くらいでできたものの1500文字付近に文字数を持っていくために2, 3時間かかった気がする. 

 

 これはどのくらいあるあるな感覚なのだろうか? そういえば, 大学入試の時もこんな文字数調整で苦労をしていた気がする(特に英文要約).  

 

 なんかこの話のオチを思いついて書き始めたはずなんだが, オチを忘れてしまったのともう一度考えてもっていくのが面倒になったので中途半端だがここで終わりにする. あるあるネタだといいなぁ. 

 

 

 

 

 

 

 

 

 

あ、 ほんとにオチないよ. 

*1:本当に脊髄反射で打っているわけではない(何かに対する防衛). 打った後, 言っても大丈夫かどうか誤字脱字がないか, 確認してから送信ボタンを押すようにしてはいる. 

人工知能全能説―—シリーズ認知の歪み1―—

 最近, 「人の認知」に対する興味が日に日に増してきている. 我々は常に「認知の歪み」を受けて生きているためになかなか「ありのままの現実」ないし「ナマの真実」とでもいうべきものを知覚できない. 

 「認知の歪み」は思い込み, 勘違い, 錯覚etc. さまざまな原因で起こる. それはどんな賢者であれ聖者であれ, 「人*1」である限り逃れることのできない「人間の業」もしくは「人間の本質」とでも言うべきものであるように思う(これ自体も認知の歪みである可能性はある).  

 そのような認知の歪みに対してたまにテキトーな思考を垂れ流す場が欲しくなった. せっかくブログの存在を認知したのでここで垂れ流すことにする. 

 今回のテーマは「人工知能全能説」である. キチンと取材した話ではないのでこの記事自体が「認知の歪み」を強く受けていることに注意されたい. 

 

 

 近頃人工知能に対する世間一般の興味が高まっているようである. 某放送局が「自前の人工知能を作りました」というので蓋を開けてみたら疑似相関を大量に検出するための箱ものにすぎず, 「人工知能」というには程遠い何かであったという心温まる出来事があったのは記憶に新しい. 

 また, 人工知能の開発をやっていた——少なくとも上記の放送局よりは真剣に―—会社の社長が良くわからない理由で逮捕されたという悲しすぎる事件があったことは読者諸氏もご存知のことであろうと思う. 

 

 人工知能に関することでよく聞かれる認知の歪みは「人工知能全能説」だ. 誰が言い出したのか知らないが曰く「人工知能は全ての問題を解決してくれる」らしい. また, いつの日か「人工知能は人類の知能」を超え「人類の仕事を奪い生存を脅かす」ようになるらしい. そもそも人類自身の「知能」がどうなっているのかわからない——だいぶわかってきたことも増えてきたらしいが——のにすごい発想である.  まぁ, 後者については元々「ロボット」という言葉が初めて用いられたKarel Čapekの戯曲"Rossumovi univerzální roboti"以来の伝統*2のような気もするが......

 

 現在の人工知能と実際の人類の知能の隔たりは大きい. 

 第一に人工知能は「問題・課題の発見」は本質的にはできない. あくまでも彼らは人類が設定した「課題設定」に乗っ取って業務をこなしているだけである. 人類が課題設定をした範囲内においてであれば「問題」の発見自体は可能かもしれないが——故障個所の発見など——一番最大の目的の設定はあくまでも人類が行わなくてはならない. これは課題設定を行うために必要な「価値」という概念自体が, 人工知能が扱うには曖昧過ぎることが原因のように思う*3

 第二に人工知能は「アブダクション」ができない. 我々人類は課題解決や問題の設定において「仮説形成」ということを行う. 「きっとこれは○○が原因で起きているのだろう」であるとか,  「これはこういう原理で動いているのであろう」などの「仮説」を考え, それを帰納法なり演繹法なりを使って検証することによって人類の思考は進む. しかし, 人工知能は「仮説の検証」ということは行えるかもしれないが, そもそも「仮説」を考案すること自体はできていない. 某放送局の作った人工知能も「相関」の発見・提示までは行えていたようだが, そこからの仮説提示自体は人間が行っていた.

 少なくとも現行の人工知能の理論では「仮説形成」を行うには無理があるように思う. 

 

 ともあれ, 人工知能は我々人類に対して有用であることは間違いなさそうである. しかしあくまでも人工知能は道具である. 道具を使いこなすためには道具の特性を正確に把握する必要がある. どこまでのことが人工知能には「できて」「できない」のか. そこの見極めをすることが今後重要な課題となっていくであろう. 

 

AI vs. 教科書が読めない子どもたち

AI vs. 教科書が読めない子どもたち

 

  

ロボット (岩波文庫)

ロボット (岩波文庫)

 

  

フランケンシュタイン (光文社古典新訳文庫)

フランケンシュタイン (光文社古典新訳文庫)

 

 

*1:そういった認知の歪みから解放された者が「仏」と呼ばれるのかもしれない. しかし, 思うに「仏」になるための必要条件くらいのものなのであろう. 「仏」はさらに「認知の歪み」から解放されたうえで「問題解決」という視野も必要ではないかと思う. 

*2:この伝統も一種の認知の歪みなのかもしれぬ. もっと根源的には「造物主への反乱」という"Frankenstein: or The Modern Prometheus"などでも用いられたものなのであろう. 我々人類自身が「神の創造物」であるとする欧米社会キリスト教社会ではその欲求自体が自然なのだろう.

*3:結局のところ「人の幸福」という共通する基盤はあるのであるが, そもそも幸福と言うもの自体が曖昧模糊なところがある. すべての科学であれ宗教であれそこに指向を持っているはずだが, その定義はなかなかに難しい. 卑近な例として, おそらくこの記事を読んでいる人間の多くは「真理の発見」にこそ幸福を覚えるが, 残念なことにそれに価値を見出すことのできる人間と言うのは限られている. 「真理」に価値を置くのが間違っているという哲学者も出ている始末なので「幸福」というモノを論じるには人類はまだ未熟なのかもしれない.

お久しぶりです

 一億年ぶり(体感)に戻ってきました. お久しぶりです. 

 

 前回の更新が2016/12/07の記事らしいのでまるまる一年間更新をしていなかったみたいですね. ヤヴァイ. 去年の3月くらいに起こった変化のバタフライエフェクトで転職したり, 学生に戻ることになったりとぶっちゃけブログなんぞ(と言うと刺されそう)を更新する余裕がなかったものでそもそも存在自体忘れてました. 存在を思い出したので帰ってきました. 

 

 ブログが存在している⇒ブログの存在を認知している

 

 認知論理っぽい. けど, それについて書くと時間がかかるので, また今度. 

 ひとまず存在を認知したというご報告まで. ぼつぼつネタを思いついたら更新する予定です(ただ, 予定は未定と言うからなぁ......). 

水素水騒動を見て思うこと ——疑似科学を科学と認識する認識障害について——

 今回は雑記です. まとまりのない文章になりますがご了承ください. 

 

 水素水の効能がないことが公的機関によっても保証されたようですね. 

容器入り及び生成器で作る、飲む「水素水」−「水素水」には公的な定義等はなく、溶存水素濃度は様々です−(発表情報)_国民生活センター

 

 国民生活センターがこういった問題において, どの程度発言力を持つのかは知りませんが, あからさまな疑似科学に対して鉄槌が下される日も遠くないようです. 

 

 さて, 正直この問題についてそこまで僕自身はさほど興味ありません. 騙されそうになっている方に

疑似科学とされるものの科学性評定サイト

みたいなホームページを紹介することはありますが, 撲滅しようと熱心に活動しているわけではありません. 

 一番の興味は「なぜ, 人は疑似科学を『科学』と思い込むのか」ということです. もう少し正確にいうと「どうすれば, (手遅れな人たちはいったん置いといて)子供たちに疑似科学を見抜く力を備えさせられるか」ということです. 

 

 こう見えても教育関係に身を置いているので, 子供たちと話す機会が他の人よりも多いです. 小学校低学年の子たちと話していると, 彼らは今まで生きていた世界から「科学らしきもの」を得ようとしている(もしくはすでに得ている)ことがわかります. 

 そういった「科学らしきもの」は大人たちの目から見ると明らかに「科学」の段階に至っていないことが多いです(当たり前ですが). 

 特に多くて, その誤解を解くのが大変な「科学らしきもの」の片鱗の一つが「物体が運動するときその物体には力が働いている」というものです. これは実際には「力が働いていない(もしくは釣り合っている)物体は等速直線運動をする」という「慣性の法則」を知っている大人にとっては明らかな誤りであることがすぐにわかります*1

 よくよく考えてみたら, この誤解はそれほどおかしなことではありません. なぜって, アリストテレス的世界観(ニュートン以前)に生きていた昔の人々はそういった価値観の下で生きていたのですから. これは, 「昔の人々がアホだった」ということではなく, 単純にそういった思弁が「それほど重要でなかった」ので, 誤っていても誰も気にしなかったということなのでしょう*2

 

 さて, 問題はこの誤解がなぜ起こるのかということです. これは「力が働いていないと動かない」という事象をたくさん見ているからでしょう.

 たとえば, 「エンジンがかからないと動かない車」「押さないと動かないスーパーのカート」「投げないと動かないボール*3」などなど......

 

 我々は身の回りの世界で感じ取ることができる事象から「科学のような法則」を無意識のうちに作り出しています. しかし, その多くは誤りです. なぜなら, 一人の人間の感じられる世界はかなり狭いからです. また, 同じ事象を観察したところで正しい「科学法則」にたどり着けるのはほんの一握りで——認識障害とバシュラールなどは呼んでいます——多くの場合間違った推測をしてしまうからです. 

 科学の世界ではこういったことを防ぐために正しいと思われる「科学のような法則」が正しいかどうかを判定する「実験」を行うわけですが, ほとんどの人はそのようなことはしません. そして, 多くの場合最初の「科学のような法則」を「正しい」と思い込んでいます. 

 

 我々にとって大事なのは「最初の直観を疑う」ことかもしれません. 子供たちが「疑似科学」に騙されないようにするためにはそのことを教えるのが一番なのかなぁと思う今日この頃であります. 

 

 特にオチはありません. 乱文失礼しました. 

 

 

 ↓文中で出てきたバシュラールの本です. 今, 読んでますが, とても面白いです.  

 

*1:と思ってたんだけど, この前, 飲み会でこの話と似たようなことを話したら, 「え?何それ?気持ち悪い!」と言われました. おいおい, 大丈夫か?!となったのは内緒です.

*2:それ以外にも当時の権威たるキリスト教との兼ね合いもありそうですが.

*3:一番最後の例はよくよく考えてみると「飛んでいる最中は力が(重力以外)働いていない」ので「慣性の法則」に気付ける一つの事象ではありますが, そこまで考えが及ばないのが普通の小学生でしょう.

今日が一周年らしい~小曲36の不思議~

 このブログをはじめて今日で一周年らしい. はてなブログからの通知で知った. 

 最近, 引っ越しやら他の雑務でドタバタしていてこのブログの存在を忘れ始めていた. なんかごめんなさい. 

 

 ドタバタが収まっていないので, あまり長文は書けないが小曲として, "$36$"という数字について簡単に書こうと思う. 特にオチもないので, 読み流していただければ幸いです. 

 

 遠い昔, 小学生の頃に読んだ本——題名は忘れてしまった——によると"$36$"は「聖なる数」らしい. 曰くいろんな分解ができるからだそうだ. 覚えている限りでも少し並べてみよう. 

 

\begin{align*}36&=1+2+3+4+5+6+7+8 \\ &=1+3+5+7+9+11 \\ &=1^2\times 2^2 \times 3^2 \\ &=1^3+2^3+3^3 \\ &=(1+2+3)^2 \\ &=(1\times 2 \times 3)^2 \end{align*}

 ふむ, 他にもありそうだが, こんなものか. うろ覚えでもこれだけ覚えている限り, 子供心にかなりの衝撃を与えたようである. 自分の数学好きの原点はここにあるのかもしれない. 

 

 分解がきれいだから「聖なる数」という感覚*1はよくわからないが, とてもおもしろい. いったい何の本で読んだのだろうか?

 他にも似たような分解できる数がないかと思いを巡らしてみるが, $1+2+3=1\times 2\times 3$というのがかなり効いているので, なかなか見つからない. うーん, 難しいなぁ. 

*1:もしかすると, 完全数$6$の二乗だからかもしれない. これまたうろ覚えだが, ピタゴラスの提唱らしいのでその可能性は高い.

数を数えて遊ぼっ! ~その0(前提知識編)~

今日の話はこちら! 

wreck1214.hatenablog.com

 「伝道師になろう」というイベントがあります. 変な名前ですが, 宗教系のイベントではありません*1. 中身は「好きな趣味の話をして, 自分の趣味を伝道しようぜ」というオタクのオタクによるオタクのための会です. 

 

 ここで, 「数を数えて遊ぼっ~It is very dangerous to think about infinity as well as about finite.~」という発表させていただきました.「連続体仮説」について簡単に話したつもりだったのですが, 上の記事にあるようにかなり駆け足で説明したので, 「中学生にわかる」とした割にわからなかった人が多かったようです. 

 

 そこで, 今回から数回に渡って, 高校生にわかるように(高校数学の「集合」の単元の知識は仮定する)その講演で話したかった内容の説明を丁寧にしていきたいと思います*2.

 目標は「連続体仮説の主張を理解する」ことです.  そして, もう一つの目標は「気分」と「厳密な議論」にわけて数学の議論を理解することです*3

 長い旅になると思いますが, 最後までごゆるりとお付き合いいただければ幸いです.  

0.商集合

 今回は本論の下準備として同値関係の話から始めましょう. 

 同値関係というのは次のような「関係」をです. ここでいう「関係」とは集合の元と元同士の何らかの関係のことです*4

定義0.1[同値関係] 

 集合$X$上の関係$\sim$で次のi), ii), iii)を満たすものを同値関係と言う. 

i) すべての$a\in X$に対して$a\sim a$.

ii) すべての$a, b\in X$に対して「$a\sim b$ならば$b\sim a$.」

iii) すべての$a, b, c\in X$に対して「$a\sim b$かつ$b\sim c$ならば$a\sim c$.」

 「なんだこれは?」となったかもしれません. こういった抽象的な定義なり定理なりを見た場合, 「具体例を見せろや」となるのが世の常(?)ですが, 見通しが良くなることを鑑みて, 具体例を見せるのはもう少し後にします. もうしばらく抽象論にお付き合いください. 

 さて, 「同値関係」というのは「同じ」とみなすことのできる「関係」の持つ共通の特徴です. 「ホンマかいな?」となるかと思いますが, そのことを厳密に議論するために次のような集合を考えます. 

定義0.2[同値類]

$X$を集合, $\sim$を$X$上の同値関係とする. 

$x\in X$について, 

\[C_{\sim}\left(x\right):=\left\{y\in X\left|y\sim x\right.\right\}\]

という集合$C_{\sim}\left(x\right)$を$x$についての同値類と言う. 

 つまり, $x$についての同値類とは関係$\sim$で「関係する」元の集合です. 

 さて, 同値類に対して次のような重要な定理があります. 

定理0.3[同値類の性質]

 集合$X$上の同値関係$\sim$について, $C_{\sim}\left(x\right)$を$x\in X$の同値類とする. 

 このとき, 次のI)-III)が成立する. 

I) $y, z\in C_{\sim}\left(x\right)$ならば, $y\sim z$.

II) $y\in C_{\sim}\left(x\right)$ならば, $C_{\sim}\left(y\right)=C_{\sim}\left(x\right)$.

III) $x, y\in X$について$C_{\sim}\left(x\right)\cap C_{\sim}\left(y\right)\neq\emptyset$ならば, $C_{\sim}\left(x\right)=C_{\sim}\left(y\right)$.

 この定理は同値類によって, 集合$X$の元がグループ分けできることを示しています.

 グループ分けとはそこにあるものを(細かい違いを除いて)同一視することです. ある政党の一人が不正を犯すとその政党全体が白眼視されるのと同じことです. 

 それを踏まえたとき, 定理のそれぞれの番号の主張の気分は次の通りです. 

I) $C_{\sim}\left(x\right)$に属する元同士は関係$\sim$で結ばれる. 

II) $x$を代表とする$C_{\sim}\left(x\right)$に属する元$y$について, $y$を代表とする$C_{\sim}\left(y\right)$というグループは(当然)$C_{\sim}\left(x\right)$と一致する. アイドルグループで言うなら, A$\bigcirc$Bというグループのセンターがじゃんけんで交代しようとも, A$\bigcirc$BはA$\bigcirc$Bということです*5

III) 2つ以上のグループに属する元は存在しないということです. ジャニ$\bigcirc$ズ事務所とはシステムが違います. 

 イメージはこんな感じです. 

f:id:Sokrates7Chaos:20161013014344j:plain

  線を結んであるのが「関係している」元同士です. それぞれの図形(っぽく見えているもの)が, 同値類になります. 

  さて, 同値類は$X$の元をグループ分けするものであると言いましたが, 「グループ分け」というものは一種の「割り算」とみなすことができます. 

 たとえば, 小学校のころの割り算を扱った問題として, 次のような問題があります. 

もんだい.

 りんごが30こあります. このりんごを5にんで, おなじかずづつわけました.  ひとりあたりはなんこですか? 

  この問題の答えは次のようになります. 

こたえ. 

\[30\div 5=6\]

6こ

  これを絵にすると次のようになります(急いで作ったので絵のしょぼさには目をつぶってください). 

 

f:id:Sokrates7Chaos:20161013014508p:plain

 この絵は「りんご」をお皿でグループ分けしているように見えます. 

 そういった気持ちの下で「グループ分け」された集合のことを「商」集合といいます. 

定義0.4[商集合]

 集合$X$とその上の同値関係$\sim$について, その同値類全体の集合を商集合と言い$X/\sim$と書く. 

 気持ちの上で割り算であることから, 商集合$X/\sim$を定義することを「同値関係$\sim$で割る」と言います*6

 さてさて, 長々とした抽象論お疲れ様でした. そろそろ約束通り具体例を見てみましょう. 上の定義たちと見比べながら下の文章を読んでみてください. 

例1(分数の"=")

 $X$を$a/b$(ただし, $a, b$は整数で, $b\neq 0$とする)という形をしたものの集まりとしよう*7 . これは(形の上では)いわゆる分数の集まりであるように見える. さて, 我々は分数の"="をどのように"定義"したであろうか? 

\[\frac{1}{2}=\frac{2}{4}=\frac{3}{6}=\frac{4}{8}\] 

と「通分」「約分」 で移りあえるモノ同士を「同じ」とした. 

 つまり, $a/b$と$c/d$が"同じ"であるとはある整数$n$が存在し\begin{align*}an&=c\\bn&=d\end{align*}となることである. 

 この$1/2$と$2/4$のように見た目が違うモノを「同じ」とみなすことに当たるのが「同値関係で割る」という行為である. 

 もう少しフォーマルにこの辺りの議論をしよう. $X$の元と$a/b$と$c/d$が関係$\sim$にあるとは, ある整数$n$が存在し\begin{align*}an&=c\\bn&=d\end{align*}となるかある整数$m$が存在し\begin{align*}a&=cm\\b&=dm\end{align*}となることである. 

 これは同値関係になっている(各自確かめてください). この同値関係$\sim$で$X$を割ることで, 有理数全体の集合$\mathbb{Q}=X/\sim$を得ることができる. 

 分数の"="も一種の同値関係であったのである.  

例2(余りによる分類)

 もう一つ有名な例を挙げておこう. $\mathbb{Z}$を整数全体の集合とする. 

 $\mathbb{Z}$上の関係$\sim$として「$a\sim b$とは$3$で割ったときのあまりが一致する」こととする. これは同値関係になっている. 

 実際, 次のように確認できる. 

i) 当然, 任意の$a\in\mathbb{Z}$について$a\sim a$である. 

ii) $a\sim b$であるとき, これも当然$b\sim a$. 

iii) $a\sim b, b\sim c$であるとき, 

\[\left(\text{$a$を$3$で割った余り}\right)=\left(\text{$b$を3で割った余り}\right)=\left(\text{$c$を$3$で割った余り}\right)\]

となるから, $a\sim c$となる. 

 この同値関係で割った$\mathbb{Z}/\sim$を普通$\mathbb{Z}/3\mathbb{Z}$と書く. こういって作った対象は整数論などで主要な役割を果たす(詳しいことは整数論の本などで). 

 

 最後に定理0.3を証明しましょう. この定理の証明で同値関係の性質のみが用いられていることに注意をしてください. 

定理0.3の証明

I) $y, z\in C_{\sim}\left(x\right)$とする. 

 このとき, $y\sim x, z\sim x$である. 

 $z\sim x$から同値関係に性質ii)より$x\sim z$. これと$y\sim x$および同値関係の性質iii)を使えば$y\sim z$.

II) $y\in C_{\sim}\left(x\right)$とする. 

このとき$y\sim x$である. 

$C_{\sim}\left(y\right)$とすると, $z\sim y$である. よって同値類の性質iii)より$z\sim x$であるから, $z\in C_{\sim}\left(x\right)$. よって, $C_{\sim}\left(y\right)\subset C_{\sim}\left(x\right)$.

 同様にして, $C_{\sim}\left(x\right)\subset C_{\sim}\left(y\right)$も示せる. 

 ゆえに$C_{\sim}\left(y\right)=C_{\sim}\left(x\right)$.

III) $x, y\in X$について$C_{\sim}\left(x\right)\cap C_{\sim}\left(y\right)\neq\emptyset$とする. 

$C_{\sim}\left(x\right)\cap C_{\sim}\left(y\right)\neq\emptyset$であるから, $z\in C_{\sim}\left(x\right)\cap C_{\sim}\left(y\right)$が存在する. 

 よって, II)より$C_{\sim}\left(x\right)=C_{\sim}\left(z\right)$かつ$C_{\sim}\left(y\right)=C_{\sim}\left(z\right)$である. 

ゆえに$C_{\sim}\left(x\right)=C_{\sim}\left(y\right)$. 

$\blacksquare$

 

 さて, ここまでいかがだったでしょうか? 商集合は現代数学において基本的な武器の一つです. 理解の手助けにこの記事がなれば幸いです. より詳しく知りたい方は下の参考文献をしっかり読んでいただければと思います. 

参考文献

1. 松坂和夫『集合・位相入門』岩波書店

集合・位相入門

集合・位相入門

 

2. 内田伏一『集合と位相』裳華房

集合と位相 (数学シリーズ)

集合と位相 (数学シリーズ)

 

 

追記(10/14)

 数式の表示バグを修正. その他, 誤字脱字も気が付いた範囲で修正. 

*1:端的に言ってネーミングミスだと思う.  異分野オタク交流会というのが正しい. 

*2:中学生はいったんあきらめます. 中学生にわかるようにはそのうちします......たぶん

*3:どこかの数学者が「数学で最も大事なのは情緒だ」と言っていましたが, 数学的証明・議論を理解することと同じくらいその「気分」を理解することは大事です. 同時にその二つを分けて考えることも非常に大事です. あくまでも「気分」なので, 厳密に正しい説明になっているとは限りません. むしろ, 歴史的にみると, それまで「気分」で捕らえきれていなかったところにこそ, 数学の偉大な発見のカギが落ちていることが多いのです.

*4:もう少しフォーマルに定義をするならば, 積集合$X\times X$の部分集合と言うことができます. 積集合$X\times X$とは「座標」みたいなもので$(a, b)$(ただし, $a, b\in X$)という形をしたもの全体の集合です. 詳しいことは今回は避けることにしますが, 詳しく知りたい人は参考文献を覗いてください.

*5:僕はあのグループについてそれほど詳しいわけではないので, 間違っていたら間違っていると言ってください.

*6:それ以外にも「同値関係でつぶす」ということもあります. これは「例外を一点につぶす」ように見えることがあるからです.

*7:高校生向けという態なので, 数学的に大事というよりも身近な例にしております. また気持ちを前面に押し出し, かなりインフォーマルに説明しています. ご了承ください.

【備忘録】数理論理学・数学基礎論の本

 論理学・数学基礎論の本を並べてみた. たぶん, 有名どころはほとんど網羅できているはず(2016年10月4日最終更新). 

0. 一般書

 一般書と書いたが, 数理論理学の一般書ってあまりない. 強いてあげるならというニュアンス.

共立出版の人とお話をする機会があってその時に目を通してみてと言われた本. かんどころシリーズのコンセプトとして「入門書の入門」みたいなものを作りたいらしく, まさにそんな感じの本.

「これだけじゃ(素人目に見ても)圧倒的に足りない. でも何を勉強したらよいかの道しるべにはなる」というのがざっと目を通した感想. 詳しいことは他書に譲りまくっているので, この本だけ読んでも数理論理学は全然わからない(「わかる」とは何かという話もあるが)と思う. 漠然と「数理論理学」がやりたいと思う人が道しるべに読んで「ここを深く知りたい!」となった話題を参考文献で詳しくやるという使い方が最適解だと思う.

こういう本, 自分がB1のときに欲しかった......

新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

 

  みんな大好き, 竹内先生の集合論の入門書. 最初の方は初学者にもわかりやすく丁寧に書いてくれている.

 だが, 最終章周辺は明らかにテンションの上がった竹内先生の高度な思考が垂れ流されているので, その辺りの話題を初学者は理解しようと思って読んではいけない(最初の方の優しかった竹内先生はどこ? ってなる). その辺りは完全にタイトル詐欺である.

 第4章までこの本を理解出来たら, 下の集合論の入門書のどれかを一冊読んで, 戻ってこの本を読むのが良い気がする. 

  • 照井一成『コンピュータは数学者になれるのか?』青土社 

  一般書のくくりにしたけど, 明らかに一般書の範疇を超えた内容を扱っている. これどの層を想定して書いたのかわからないけれど, 好きです//////

  •  Σ. χ. 『日曜数学者のための命題論理入門C0H』暗黒通信団 
日曜数学者のための命題論理入門C O H

日曜数学者のための命題論理入門C O H

 

 例の怪しげな出版団体から出ている本. たぶんこの世で一番安い論理学の本.  

 著者名は「すーひ」と読むらしい(たぶん, Xはギリシャ文字χのつもりなんだろう). 

 一応, 数学的にはキチンとしている気がするが, 変な本なので一般書のくくりにしておく.  

1. 入門書

  • 鹿島亮『数理論理学』朝倉書店
数理論理学 (現代基礎数学)

数理論理学 (現代基礎数学)

 

  概説をつかむのにはちょうど良い本. 最初に手に取ったLogicの本だった気がする. いろいろなLogicの話題のおいしいところをつまみ食いできる. ただ, 数学の人が読むには読みにくいところがちらほらあるかも. 

数理論理学

数理論理学

 

  和書では一番, 1階述語論理の形式体系周りの話題が豊富な本. ヒルベルト体系と自然演繹体系とシークエント体系の関係がこれほどコンパクトにまとまっている本はこの本以外知らない. 

ゲーデルと20世紀の論理学(ロジック)〈1〉ゲーデルの20世紀

ゲーデルと20世紀の論理学(ロジック)〈1〉ゲーデルの20世紀

 

 

ゲーデルと20世紀の論理学(ロジック)〈2〉完全性定理とモデル理論

ゲーデルと20世紀の論理学(ロジック)〈2〉完全性定理とモデル理論

 

 

ゲーデルと20世紀の論理学 3 不完全性定理と算術の体系

ゲーデルと20世紀の論理学 3 不完全性定理と算術の体系

 

 

ゲーデルと20世紀の論理学 4 集合論とプラトニズム

ゲーデルと20世紀の論理学 4 集合論とプラトニズム

 

   通称4色ゲーデル. いろいろコンパクトにまとまっている. 1階述語論理の完全性定理の証明が独特なので, 入門書として適確かは不明. コンパクト性定理の証明を完全性定理を経由しないで証明しているのをこのシリーズで初めて見た. 

 2018/03/11 こっそり追記 この本最初は入門書に配置しちゃったけど入門書としては行間が広くて重過ぎる章もある. わかるとことから読むのが正解の本である. 

  • Joseph R. Shoenfield, ``Mathematical Logic'', CRC Press
Mathematical Logic

Mathematical Logic

 

 古い本. Set theoryらへんはもう使い物にならないって聞いた. でも, おぉってなること多いからじっくり読んでる. 後, 田中一之先生はこの本がものすごい好きらしい. 

  • H.Enderton, ``A Mathematical Introduction to Logic''
A Mathematical Introduction to Logic

A Mathematical Introduction to Logic

 

  アメリカの標準的なLogicの教科書らしい. それ以上詳しくは知らない(誰か誕生日プレゼントにくれ).

  •  Kenneth Kunen, "The Foundation of Mathematics", IfColog
The Foundations of Mathematics (Studies in Logic: Mathematical Logic and Foundations)

The Foundations of Mathematics (Studies in Logic: Mathematical Logic and Foundations)

  • 作者: Kenneth Kunen
  • 出版社/メーカー: College Publications
  • 発売日: 2009/09/08
  • メディア: ペーパーバック
  • 購入: 2人 クリック: 5回
  • この商品を含むブログを見る
 

 数学基礎論って要は数理論理学のことじゃないかと思っているので, ここに. 

 ベットで横になりながらだらだら読んでいる. 

 また, この講演のタイトルの元ネタが載っている. 

sokrates7chaos.hatenablog.com

  最近, 日本語訳も出た. 

キューネン数学基礎論講義

キューネン数学基礎論講義

 

 

2. 不完全性定理

 不完全性定理周りは悪書がともかく多い. 

 ひどすぎるわりに有名なやつはいくつか晒していくことにする(まじめな初学者の混乱を防ぐため). 

 不完全性定理周り悪書リスト(2016年10月4日最終更新)

  • 竹内薫不完全性定理とはなにか』講談社
    • 明らかに必要最低限のことも理解できていないまま書いている. ベン図をわざわざ書いてストラクチャを定めず真偽を議論し始めた瞬間, この本をぶん投げた. 有名なサイエンスライターの本だが, こういう悪質な本を書くのはいかがなものかと思う. 

 以上

以下はまともな本. 

不完全性定理

不完全性定理

 

  不完全性定理周りの決定版らしい. 著者と話したことがあるがいい人でした. いろいろあって, 手に入れそびれている(誕生日ry).

3. モデル理論

 かなり重要な分野のはずだが, 僕の不勉強で一冊ぐらいしか知らない......

 (申し訳ない

  •  David Marker, "Model Theory", Springer New York
Model Theory : An Introduction (Graduate Texts in Mathematics)

Model Theory : An Introduction (Graduate Texts in Mathematics)

 

  モデル理論の定評のある教科書らしい. 

4. 集合論

  • K.Kunen, ``Set Theory'', IfColog
Set Theory (Studies in Logic: Mathematical Logic and Foundations)

Set Theory (Studies in Logic: Mathematical Logic and Foundations)

 

  公理的集合論の本. または, 強制法(Forcing)の本. 最近版が変わって内容がいくつか入れ替えられたらしい. 

 旧版は日本語訳が出ている. 

集合論―独立性証明への案内

集合論―独立性証明への案内

 

 誰かこの本のゼミ一緒にやろ♡

4. 様相論理

数学における証明と真理: 様相論理と数学基礎論

数学における証明と真理: 様相論理と数学基礎論

 

 通称「黒い本」. 数学基礎論サマースクール2015の講演内容をまとめた本. 「エキサイティングなModal Logicの世界にようこそ!」という空気を感じられる. 真理論周りが特に面白かった. 

  •  M. J. Cresswell, G. E. Hughes, "A New Introduction to Modal Logic", Routledge
A New Introduction to Modal Logic

A New Introduction to Modal Logic

 

  様相論理の教科書. 読まなきゃ......

5. 周辺領域

 

おまけ

 この記事を以下の記事で紹介していただきました*1. ここに書いてある本以外にもいくつか論理学の本が上がっているので, 興味がある方は覗いてみるとよいと思います. 

mathcafe-japan.hatenadiary.com

*1:というか, この記事自体, 数学カフェさんのTwitterでのつぶやきをきっかけに書くことを思い立ちました.

数を構成して遊ぼっ~All concrete mathematical objects are specific sets. ~ 資料公開

皆さん, こんにちは. 

一か月ほど前ですが, 次のような発表をしてきました.  

www.nicovideo.jp

 迷ったのですが, このときに使ったスライドのデータ(に少しだけ手を加えたもの)を公開します. 

www.dropbox.com

 正直もっと良いpdfや本が他にある中で, 公開する意味があるのか微妙ですが, 誰かのためにはなるだろうと思い直し公開します. 誤りがありましたら, コメントなどでご指摘いただけますと幸いです. 

 

 参考文献に挙げた本のAmazonへのリンクを下に張っておきます. ご活用ください. 

 

数 上 (シュプリンガー数学リーディングス)

数 上 (シュプリンガー数学リーディングス)

 

 

数 下 (シュプリンガー数学リーディングス)

数 下 (シュプリンガー数学リーディングス)

 

 

Zahlen (Grundwissen Mathematik)

Zahlen (Grundwissen Mathematik)

  • 作者: H.-D. Ebbinghaus,H. Hermes,F. Hirzebruch,M. Koecher,K. Mainzer,A. Prestel,R. Remmert,K. Lamotke
  • 出版社/メーカー: Springer
  • 発売日: 1983/12/01
  • メディア: ペーパーバック
  • この商品を含むブログを見る
 

 

軽装版 解析入門〈1〉

軽装版 解析入門〈1〉

 

 

解析入門 (1)

解析入門 (1)

 

  

集合と位相 (数学シリーズ)

集合と位相 (数学シリーズ)

 

 

集合・位相入門

集合・位相入門

 

 

代数学2 環と体とガロア理論

代数学2 環と体とガロア理論

 

 

The Foundations of Mathematics (Studies in Logic: Mathematical Logic and Foundations)

The Foundations of Mathematics (Studies in Logic: Mathematical Logic and Foundations)

  • 作者: Kenneth Kunen
  • 出版社/メーカー: College Publications
  • 発売日: 2009/09/08
  • メディア: ペーパーバック
  • 購入: 2人 クリック: 5回
  • この商品を含むブログを見る
 

 ↑タイトルの元ネタはこの本から