黒夜行

左脇のプロフィールにある「サイト全体の索引」から読みたい記事を探して下さい。

四色問題(ロビン・ウィルソン)

数学というのは奇妙な学問だと思う。
まずは数学以外の学問について考えよう。
例えば物理。物理というのは、小学校の頃なんかは科学と呼ばれるけれども、初めの内は身近なものを扱う。天体だとか火だとか氷だとか、そう言ったものである。身近で出来る実験なんかもやる。
しかし次第に身近なことからかけ離れた問題が出てくる。分子や原子なんかは既に身近とは言えないし、モーメントなんて言葉は普通使わない。さらに進むと、相対性理論だとかクオークだとか量子論だとかってものが出てきて、そもそも何をやっているのか、何を扱っているのか素人にはさっぱり分からなくなってくる。
国語はどうだろう。
初めの内は、文章を読んでどう感じるか、なんてことをやる。評論を読んで何を言いたいのかを考えたりする。その内古文だの漢文だのなんてものが出てきて、その後どうなるかはちゃんとは知らないけど、恐らく普通の人には何をしているのか全然分からないようなことをやることになるのだろう。
さて数学の話だが、基本的に物理や国語といったものとあまり変わることはない。初めの内は足し算だの掛け算だのと言ったことをやり、その内関数だの複素数だのわけの分からないものが出てきて、最後には幾何代数学だのトポロジーだのと言ったさっぱり意味不明のことをやるようになる。
しかし数学の面白いところは、突き抜けて難しい問題というのは、問題を理解するだけなら容易になる、ということである。
例えばつい最近解かれたが、350年以上も数学者を悩ませ続けたフェルマーの最終定理がある。これは

nが3以上の自然数の時、(xのn乗)+(yのn乗)=(zのn乗)を満たす自然数の組(x,y,z)は存在しない

というものである。
この問題は、問題自体を理解することは容易い。恐らく中学生にだって理解できるだろう。しかし、これを証明することは容易ではなかったのだ。最終的にはワイルズという数学者が、数百ページもの論文を発表してようやく証明された。
また、未だ解決されていない問題の一つに、ゴールドバッハ予想、というものがある。これも、問題自体を理解することは容易い。

2以上の偶数はすべて、二つの素数の和として表すことが出来る。

この問題も、素数と偶数という言葉さえ知っていれば誰でも理解できる。素数というのは、1とそれ自身以外の約数を持たない数であり、2、3、5、7、11、13、17…と続いていく。
さて上記の問題だが、ちょっと確かめてみると、
4=2+2、6=3+3、8=3+5、という風に表すことが出来る、ということだ。
これも問題自体は呆れるほど易しいが、しかし未だ証明はされていない。
このように、数学というのはちょっと変わった分野である。レベルが上がるに従って何をしているのかさえ部外者にはわからなくなってしまうのが学問であるのに、数学の場合はあまりに突き抜けた難問は、問題自体は容易に理解できてしまう。この他にも、問題を理解するだけなら誰でも出来るが、しかし未だ証明がされていない難問がいくつもある。こういうところが数学の面白いところだし、アマチュア数学者というものが生まれる要因でもあるのだと思う。
さて、本書で取り上げられている四色問題というのもまた、問題を理解することは容易い。四色問題の場合、問題の理解のために数学的な知識は一切不要なので、問題を理解するだけであれば幼稚園児でも可能かもしれない。四色問題というのはこういう問題である。

この世の中にあるすべての地図を、隣り合う国同士を別の色で塗り分ける際、最低限必要な色は何色か。

どうだろうか。問題自体は異様に簡単ではないだろうか。
要するに、どんな地図でもいい。実際の国や県のある地図でもいいし、いくつかの図形を組み合わせた独自の地図でもいい。とにかくどんなものでもいいから(多少の制約はあるが)ありとあらゆる地図を塗るのに何色必要かというのが問題である。
これは、経験的に四色あれば十分であるということがそもそも知られていた。だからこそこの問題は、四色あればどんな地図でも塗り分けることが出来るか、という風に言い換えることが出来る。これが四色問題であり、長いこと数学者たちを苦しめた難問だった。
この問題についてのアプローチについて書く前に、この問題が最終的にどう解決されたのかを書こう。この四色問題の証明は、なんとコンピューターが使われたのである。数学の証明といえばながらく、ペンと紙さえあれば出来るものであり、今でもそれが正しい証明のあり方であると多くの数学者が考えている。しかし、この四色問題の場合、そういうこれまでの証明のやり方ではどうにも太刀打ちできないようだったのだ。この証明をした二人は、とにかく力技で、コンピューターの力を借りてこの問題を解いたのである。その余波は今でも健在で、コンピューターを使った証明が証明として認められるのだろうか、という疑念は未だに拭いきれていないようである。
本書では、四色定理がどのようにして生まれたのか、そしてその問題がどのように扱われてきたのかについて初めに触れているが、とりあえずその部分については省こう。
まずこの四色問題を解くにあたり、非常に重要な定理があるのでまずそれを書こう。それが、「隣国は五つだけ」定理、というあまりパッとしない名前の定理である。この定理は次のように説明される。

どんな地図にも、五個以下の隣国しか持たない国が少なくとも一つ含まれている

ちょっと分かり難い文章である。以下、二つの辺を持つ国を二辺国、という形で表現をすることにしよう。そうすると、この「隣国は五つだけ」定理というのはこのように表現される。

どんな地図にも、二辺国・三辺国・四辺国・五辺国のうち少なくとも一つは含む

さらに四色問題の証明にはもう一つ重要な概念が存在する。それが、「最小反例」である。
もし四色問題が間違っていると仮定してみる。即ち、五色以上の色を使わなくては塗り分け出来ない地図が存在すると仮定するのだ。その際、その五色以上の色を使わなくてはいけない地図の内、最小の国を有する地図を「最小反例」と呼ぶのである。この時、最小反例は四色では塗り分けることが出来ないが、最小反例より少ない国を持つすべての地図は四色で塗り分けることが出来る、という点が重要である。
さてここで、ケンプという数学者が登場する。このケンプという数学者は、ある時期四色問題を解いたと考えられた数学者である。11年後に致命的な欠陥が見つかり、証明が不完全であったことが分かるのだが、しかしこのケンプが生み出した方法は後の四色問題の攻略に大きな進展を見せたのである。
さてではケンプはどんな考え方をしたのか。ケンプは、最小反例を用いて証明をしたのである。
基本的な考えはこうである。
まず四色で塗り分けることの出来ない最小反例が存在すると仮定する。この最小反例は四色では塗り分けることは出来ないが、この最小反例より少ない国を持つすべての地図は四色で塗り分けることが出来る。
さて次に、「隣国は五つだけ」定理を用いる。この定理は、どんな地図であっても、二辺国から五辺国のうち少なくとも一つはあることを保証しているわけで、つまり最小反例にも二辺国から五辺国のうちどれか一つは必ずあるはずである。
ケンプが取った方法は、最小反例に二辺国から五辺国それぞれがあった場合の四種類のパターンを考え、それぞれについて緻密に検証を進めていくことで、最終的にどのパターンも四色で塗り分けられることを示す、というものであった。つまりどういうことかと言えば、初めの前提で最小反例が存在すると仮定した。最小反例が存在すると仮定して論証を進めたのに、最終的にその最終反例が四色で塗り分けられることが示された。これは矛盾である。この矛盾はどこから来たかと言えば、初めの前提、つまり最小反例が存在したという前提がおかしかったのである。つまり最小反例は存在しないのであり、最小反例が存在しないということは五色でしか塗り分けられない地図が存在しないということであり、よって四色問題は証明された、という論証である。
ケンプのこの証明は「ケンプ鎖」というアイデアを使った独創的なもので、誰もがこれで証明が出来たと考えたのだが、しかし11年後に間違いが指摘された。
さてその後も様々なアプローチが試みられたが、どうもうまくいかない。しかし19世紀末事態は大きく動き、新しく提唱された二つの概念を導入することで解決が見込まれるのではないか、と期待された。
その概念というのが、「不可避集合」と「可約配置」である。
「不可避集合」というのは、少しだけ「隣国は五つだけ」定理に似ている。「不可避集合」というのはつまり、地図を書く上でどうしてもさけることが出来ない形の集合のことである。「隣国は五つだけ」定理により、二辺国から五辺国までのどれか一つは必ず入るということは示されたわけだが、それ以外にも、地図を書く上で避けることが出来ないパターンというものがいくつも発見された。
もう一つの「可約集合」はというと、最小反例には含まれない国々の配置のことである。二辺国から四辺国まではすべて可約配置であり、こちらも他に様々なパターンが見つかっている。
四色問題の最終的なアプローチは、「可約配置の不可避集合」を見つける、ということに焦点が絞られた。この「可約配置の不可避集合」が一つでも見つかれば四色問題は証明されたことになるのだが、その理屈が分かるだろうか。
「可約配置の不可避集合」は不可避集合であるので、この世の中に存在するすべての地図にその配置が存在するということである。さらに一方で、「可約配置の不可避集合」は可約であるので、最小反例には含まれない。つまり「可約配置の不可避集合」というのは、この世の中のすべての地図に含まれ、かつ最小反例には含まれない配置であり、これが見つかるということは即ち、最小反例が存在しないということなのである。最小反例が存在しなければ四色問題は示されたことになる。
問題はいかにしてこの「可約配置の不可避集合」を探すか、ということである。そのためには、ありとあらゆる可約配置を調べ、ありとあらゆる不可避集合を調べなくてはいけない。そのためにコンピューターが使われたのである。
四色問題を証明した二人は、コンピューターにプログラムを走らせ、またありとあらゆる効率化を駆使して、どうにかこの力技を終わらせた。そして、四色問題を証明するという栄誉を勝ち得たのである。
しかし先ほども言ったが、数学界の反応は割れた。コンピューターはミスをしないのだから信頼できるという意見もあれば、感覚的には否定したいけど彼らが四色問題を証明したことは事実だろうという立場もある。また数学者によっては、彼らは何一つとして証明していない、という立場を取る人もいた。しかし、コンピューターを使った証明の仕方が受け入れられているかどうかは別として、以下の二つの点についてはほとんどの数学者で共通している。一つは、四色問題は証明されたということ、そしてもう一つは、その証明はまったく美しくないということである。
数学はこれまで、その美しさを余すところなく垣間見せてきた。まさにこれこそ真理であると思わせる何かがそこには潜んでいると僕も思う。しかし、四色問題の証明は、その真理には程遠いように僕にも思える。
数学者の一人は、【なぜ】四色問題が正しいのかを説明で来ていない点が不満だ、と指摘する。彼らの証明は、「可約配置の不可避集合」が存在することは示したが(しかもコンピューターによって!)、しかしそれが何故存在するのかを示せていない。それが不健全であるように思えて欲求不満に陥ると言っている。
じゃあ誰かがコンピューターを使わない形で証明できたのかと言えば、それは出来ていない。だから納得するしかないのだが、という微妙なところで数学者たちは揺れているのである。
というようなところで本作の概略の説明は大体終わりである。
僕は、改めて図形的な問題は苦手だなと思いました。学生の頃から、幾何全般はあまり得意ではなくて、この本を理解するにもなかなか大変でした。四色問題は決して幾何の問題というわけではないのですけど、でも図形を扱っているという点では似ています。計算式がほとんどないのに理解するのにここまで苦労するとは思いませんでした。
特に後半の「可約配置の不可避集合」という話が出て以降は、もはや何がなんだかさっぱりという感じでした。証明をした二人が、結局コンピューターで何をしたのか、という部分が全然分かりませんでした。最終的に「可約配置の不可避集合」を見つけたのだろうということは分かりましたが、その過程が全然分からなかったですね。難しかったです。
ただ前半の方の話は面白かったです。「最小反例」を用いる証明の進め方であるとか、ケンプが考案した「ケンプ鎖」なんかの発想は素晴らしいな、と思いました。また、国を色で塗るのではなく境界線を塗るであるとか、あるいは点にそれぞれ数字を振るだとか、同値の様々な問題を生み出しては新たなやり方を模索したりするような発想も素晴らしいと思いました。
数学上の難問が解決されるとメディアなんかでも結構話題になったりしますけど、この四色問題は、「数学の証明とは何か?」という別の哲学的問題を新たに生み出したという点でも注目されました。コンピューターを使った証明という前代未聞のやり方で証明されたわけですが、今後もこの証明の是非が議論されていくのだろうな、という気はします。
個人的には、コンピューターに頼らない形での証明というのを見てみたい気がします。そんなことが果たして可能なのかわかりませんが。
全体的には読みやすい感じの作品でしたが、最後まで読みとおすとなるとなかなか難しいところがあるような気がします。全体の3分の2はいいですけど、後半の3分の1はなかなかハードルが高いです。ただ、いろんな人のエピソードなんかを交えているので、数学的な部分以外でも面白いので、オススメです。僕としては、これまで四色問題についてのみ書かれた本を読んだことはなかったので、そういう意味では満足ですが、ちょっと読むのに結構疲れたなという感じです。

ロビン・ウィルソン「四色問題」



関連記事

Comment

コメントの投稿


管理者にだけ表示を許可する

Trackback

http://blacknightgo.blog.fc2.com/tb.php/947-20407b2d

 | ホーム | 

プロフィール

通りすがり

Author:通りすがり
災害エバノ(災害時に役立ちそうな情報をまとめたサイト)

サイト全体の索引
--------------------------
著者名で記事を分けています

あ行
か行
さ行
た行
な行
は行
ま行
や行~わ行

乃木坂46関係の記事をまとめました
(「Nogizaka Journal」様に記事を掲載させていただいています)

本の感想以外の文章の索引(映画の感想もここにあります)

この本は、こんな人に読んで欲しい!!part1
この本は、こんな人に読んで欲しい!!part2

BL作品の感想をまとめました

管理人自身が選ぶ良記事リスト

アクセス数ランキングトップ50

TOEICの勉強を一切せずに、7ヶ月で485点から710点に上げた勉強法

一年間の勉強で、宅建・簿記2級を含む8つの資格に合格する勉強法

国語の授業が嫌いで仕方なかった僕が考える、「本の読み方・本屋の使い方」

2014の短歌まとめ



------------------------

本をたくさん読みます。
映画もたまに見ます。
短歌をやってた時期もあります。
資格を取りまくったこともあります。
英語を勉強してます。













下のバナーをクリックしていただけると、ブログのランキングが上がるっぽいです。気が向いた方、ご協力お願いします。
にほんブログ村 本ブログへ
にほんブログ村

アフィリエイトです

アクセスランキング

[ジャンルランキング]
本・雑誌
2位
アクセスランキングを見る>>

[サブジャンルランキング]
和書
1位
アクセスランキングを見る>>

アフィリエイトです

最新記事

サイト内検索 作家名・作品名等を入れてみてくださいな

メールフォーム

名前:
メール:
件名:
本文:

月別アーカイブ

Powered By FC2ブログ

今すぐブログを作ろう!

Powered By FC2ブログ

ブロとも申請フォーム

この人とブロともになる

QRコード

QR

カウンター

2013年ベスト

2013年の個人的ベストです。

小説

1位 宮部みゆき「ソロモンの偽証
2位 雛倉さりえ「ジェリー・フィッシュ
3位 山下卓「ノーサイドじゃ終わらない
4位 野崎まど「know
5位 笹本稜平「遺産
6位 島田荘司「写楽 閉じた国の幻
7位 須賀しのぶ「北の舞姫 永遠の曠野 <芙蓉千里>シリーズ」
8位 舞城王太郎「ディスコ探偵水曜日
9位 松家仁之「火山のふもとで
10位 辻村深月「島はぼくらと
11位 彩瀬まる「あのひとは蜘蛛を潰せない
12位 浅田次郎「一路
13位 森博嗣「喜嶋先生の静かな世界
14位 朝井リョウ「世界地図の下書き
15位 花村萬月「ウエストサイドソウル 西方之魂
16位 藤谷治「世界でいちばん美しい
17位 神林長平「言壺
18位 中脇初枝「わたしを見つけて
19位 奥泉光「黄色い水着の謎
20位 福澤徹三「東京難民


新書

1位 森博嗣「「やりがいのある仕事」という幻想
2位 青木薫「宇宙はなぜこのような宇宙なのか 人間原理と宇宙論」 3位 梅原大吾「勝ち続ける意志力
4位 平田オリザ「わかりあえないことから
5位 山田真哉+花輪陽子「手取り10万円台の俺でも安心するマネー話4つください
6位 小阪裕司「「心の時代」にモノを売る方法
7位 渡邉十絲子「今を生きるための現代詩
8位 更科功「化石の分子生物学
9位 坂口恭平「モバイルハウス 三万円で家をつくる
10位 山崎亮「コミュニティデザインの時代


小説・新書以外

1位 門田隆将「死の淵を見た男 吉田昌郎と福島第一原発の五〇〇日
2位 沢木耕太郎「キャパの十字架
3位 高野秀行「謎の独立国家ソマリランド
4位 綾瀬まる「暗い夜、星を数えて 3.11被災鉄道からの脱出
5位 朝日新聞特別報道部「プロメテウスの罠 3巻 4巻 5巻
6位 二村ヒトシ「恋とセックスで幸せになる秘密
7位 芦田宏直「努力する人間になってはいけない 学校と仕事と社会の新人論
8位 チャールズ・C・マン「1491 先コロンブス期アメリカ大陸をめぐる新発見
9位 マーカス・ラトレル「アフガン、たった一人の生還
10位 エイドリアン・べジャン+J・ペタ―・ゼイン「流れとかたち 万物のデザインを決める新たな物理法則
11位 内田樹「下流志向 学ばない子どもたち 働かない若者たち
12位 NHKクローズアップ現代取材班「助けてと言えない 孤立する三十代
13位 梅田望夫「羽生善治と現代 だれにも見えない未来をつくる
14位 湯谷昇羊「「いらっしゃいませ」と言えない国 中国で最も成功した外資・イトーヨーカ堂
15位 国分拓「ヤノマミ
16位 百田尚樹「「黄金のバンタム」を破った男
17位 山田ズーニー「半年で職場の星になる!働くためのコミュニケーション力
18位 大崎善生「赦す人」 19位 橋爪大三郎+大澤真幸「ふしぎなキリスト教
20位 奥野修司「ねじれた絆 赤ちゃん取り違え事件の十七年


コミック

1位 古谷実「ヒミズ
2位 浅野いにお「世界の終わりと夜明け前
3位 浅野いにお「うみべの女の子
4位 久保ミツロウ「モテキ
5位 ニコ・ニコルソン「ナガサレール イエタテール

番外

感想は書いてないのですけど、実はこれがコミックのダントツ1位

水城せとな「チーズは窮鼠の夢を見る」「俎上の鯉は二度跳ねる」

2012年ベスト

2012年の個人的ベストです
小説

1位 横山秀夫「64
2位 百田尚樹「海賊とよばれた男
3位 朝井リョウ「少女は卒業しない
4位 千早茜「森の家
5位 窪美澄「晴天の迷いクジラ
6位 朝井リョウ「もういちど生まれる
7位 小田雅久仁「本にだって雄と雌があります
8位 池井戸潤「下町ロケット
9位 山本弘「詩羽のいる街
10位 須賀しのぶ「芙蓉千里
11位 中脇初枝「きみはいい子
12位 久坂部羊「神の手
13位 金原ひとみ「マザーズ
14位 森博嗣「実験的経験 EXPERIMENTAL EXPERIENCE
15位 宮下奈都「終わらない歌
16位 朝井リョウ「何者
17位 有川浩「空飛ぶ広報室
18位 池井戸潤「ルーズベルト・ゲーム
19位 原田マハ「楽園のカンヴァス
20位 相沢沙呼「ココロ・ファインダ

新書

1位 倉本圭造「21世紀の薩長同盟を結べ
2位 木暮太一「僕たちはいつまでこんな働き方を続けるのか?
3位 瀧本哲史「武器としての交渉思考
4位 坂口恭平「独立国家のつくりかた
5位 古賀史健「20歳の自分に受けさせたい文章講義
6位 新雅史「商店街はなぜ滅びるのか
7位 瀬名秀明「科学の栞 世界とつながる本棚
8位 イケダハヤト「年収150万円で僕らは自由に生きていく
9位 速水健朗「ラーメンと愛国
10位 倉山満「検証 財務省の近現代史

小説以外

1位 朝日新聞特別報道部「プロメテウスの罠」「プロメテウスの罠2
2位 森達也「A」「A3
3位 デヴィッド・フィッシャー「スエズ運河を消せ
4位 國分功一郎「暇と退屈の倫理学
5位 クリストファー・チャブリス+ダニエル・シモンズ「錯覚の科学
6位 卯月妙子「人間仮免中
7位 ジュディ・ダットン「理系の子
8位 笹原瑠似子「おもかげ復元師
9位 古市憲寿「絶望の国の幸福な若者たち
10位 ヨリス・ライエンダイク「こうして世界は誤解する
11位 石井光太「遺体
12位 佐野眞一「あんぽん 孫正義伝
13位 結城浩「数学ガール ガロア理論
14位 雨宮まみ「女子をこじらせて
15位 ミチオ・カク「2100年の科学ライフ
16位 鹿島圭介「警察庁長官を撃った男
17位 白戸圭一「ルポ 資源大陸アフリカ
18位 高瀬毅「ナガサキ―消えたもう一つの「原爆ドーム」
19位 二村ヒトシ「すべてはモテるためである
20位 平川克美「株式会社という病

2011年ベスト

2011年の個人的ベストです
小説
1位 千早茜「からまる
2位 朝井リョウ「星やどりの声
3位 高野和明「ジェノサイド
4位 三浦しをん「舟を編む
5位 百田尚樹「錨を上げよ
6位 今村夏子「こちらあみ子
7位 辻村深月「オーダーメイド殺人クラブ
8位 笹本稜平「天空への回廊
9位 地下沢中也「預言者ピッピ1巻預言者ピッピ2巻」(コミック)
10位 原田マハ「キネマの神様
11位 有川浩「県庁おもてなし課
12位 西加奈子「円卓
13位 宮下奈都「太陽のパスタ 豆のスープ
14位 辻村深月「水底フェスタ
15位 山田深夜「ロンツーは終わらない
16位 小川洋子「人質の朗読会
17位 長澤樹「消失グラデーション
18位 飛鳥井千砂「アシンメトリー
19位 松崎有理「あがり
20位 大沼紀子「てのひらの父

新書
1位 「「科学的思考」のレッスン
2位 「武器としての決断思考
3位 「街場のメディア論
4位 「デフレの正体
5位 「明日のコミュニケーション
6位 「もうダマされないための「科学」講義
7位 「自分探しと楽しさについて
8位 「ゲーテの警告
9位 「メディア・バイアス
10位 「量子力学の哲学

小説以外
1位 「死のテレビ実験
2位 「ピンポンさん
3位 「数学ガール 乱択アルゴリズム
4位 「消された一家
5位 「マネーボール
6位 「バタス 刑務所の掟
7位 「ぐろぐろ
8位 「自閉症裁判
9位 「孤独と不安のレッスン
10位 「月3万円ビジネス
番外 「困ってるひと」(諸事情あって実は感想を書いてないのでランキングからは外したけど、素晴らしい作品)