数学的帰納法と背理法
著者:梅谷 武
語句:パスカル,パルメニデス,ゼノン,算術三角形論,自然数の公理,公理,数学的帰納法,排中律,背理法,無限降下法
数学的帰納法と背理法について述べる。
作成:2006-04-20
更新:2013-06-14
 ここまででいろいろな数列の和の公式が得られました。これらの公式が正しいことはこれまでの説明で十分わかりますが、これがさらに複雑になっていったときにうまく図で表現できなかったり、うまい式変形が見つからなかったりするような状況が発生してきます。そのような場合でも、ある特定の手順にしたがって式を計算していくだけで公式を証明する手段があります。それがパスカルPascal, Blaise, 1623-1662が1654年に発表した『算術三角形論Traité du Triangle arithmétique』において初めて明確に述べられた数学的帰納法の原理です。これはさまざまな問題の証明において強力な道具となりますのでここで導入しておくことにしましょう。
 自然数全体の集合ℕ={0,1,2,3,⋯}自然数の公理しぜんすうのこうり, axiom of natural numberによって特徴付けられます。公理こうり, axiomとは証明無しで認められる基本的な命題であると考えてください。

公理1.9.3 自然数の公理

 自然数は次の性質をもつ。
(N1) 任意の自然数n,mについてn≠m ⇒ n+1≠m+1
(N2) 任意の自然数nについてn+1≠0
(N3) 0を含む任意の部分集合A⊂ℕについて、もしA+1={n+1|n∈A}⊂Aが成り立つならばA=ℕである。
 この公理から数学的帰納法すうがくてききのうほう, mathematical inductionの原理を証明することができます。

定理1.9.5 数学的帰納法I

P(n)を自然数nに関する命題とする。このとき、
(1) P(0)が成り立つ。
(2) P(n)が成り立つならばP(n+1)も成り立つ。
が成り立てば、すべてのn∈ℕについてP(n)は成り立つ。

証明

A={n∈ℕ|P(n)が成り立つ}とおくと(1)より0∈Aであり、(2)よりA+1⊂Aである。したがって(N3)からA=ℕである。■
 パスカルによる数学的帰納法の発見によって、すべての自然数に対して成り立つ命題を証明する手段を獲得することになりました。この数学的帰納法にはさまざまなバリエーションがありますので、問題によってそれらの中から適切なものを選択することになります。
 数学的帰納法は自然数全体ではなく任意の自然数aに対して{n∈ℕ|n≧a}なる部分集合に対して適用することができます。

定理1.9.9 数学的帰納法II

P(n){n∈ℕ|n≧a}に関する命題とする。このとき、
(1) P(a)が成り立つ。
(2) n≧aなるnについてP(n)が成り立つならばP(n+1)も成り立つ。
が成り立てば、すべてのn≧aについてP(n)は成り立つ。

証明

A={n∈ℕ|n≧a, P(n)が成り立つ}とし、B=A-aとおくと(1)より0∈Bであり、(2)よりB+1⊂Bである。したがって(N3)からB=ℕとなりA=B+a={n∈ℕ|n≧a}であることがわかる。■
 次のような変形もよく使います。

定理1.9.12 数学的帰納法III

P(n){n∈ℕ|n≧a}に関する命題とする。
(1) P(a)が成り立つ。
(2) a≦k≦nなるkについてP(k)が成り立つならばP(n+1)も成り立つ。
が成り立てば、すべてのn≧aについてP(n)は成り立つ。

証明

 演習とする。■
 次に数学的帰納法と同じように数学の証明における重要な技術である背理法について説明しましょう。背理法は数学ではなく論理学に属するものです。数学と論理学は密接に関係していて、論理学は数学の一分野とみなされやすいのですが、歴史的にみても数学と論理学は別々に発生し、発展してきており、現代においては論理学は数学と哲学にまたがるような学問領域になっています。
 論理学を創始したのは南イタリアのエレア出身のパルメニデスParmenides, BC515頃-445頃であるとされています。論理学から見たパルメニデスの最大の功績は排中律はいちゅうりつ, law of excluded middleと呼ばれる重要な規則を発見したことにあります。パルメニデスの残した著作の断片*1にそのことが明確に書かれています。
すなわち、あるか、あらぬかである。
これを現代的な記号論理学で表現すると
A ∨ ¬A
となります。これはどのような命題AについてもAが正しいか(真)、¬A(Aの否定)が正しい、すなわちAが正しくないか(偽)のどちらかであるということです。この排中律から間接証明(背理法)という強力な証明の道具が生み出され、パルメニデスの弟子ゼノンZenon, BC490頃-435頃はこれを使って当時のさまざまな知識人達の素朴な論理をあざやかに論破していきます。プラトンは『パルメニデスParmenides』において若き日のソクラテスがパルメニデスとゼノンに打ち負かされる様子を描いています。
背理法はいりほう, reduction to absurdityというのは命題Aが正しいことを証明するために、まず命題Aが間違っている、すなわち¬Aが正しいと仮定します。そしてその前提のもとで議論を進めると矛盾に至ることを示します。そうするとその矛盾は命題Aが間違っていると仮定したから生じたものなので、その仮定が間違っていたことがわかります。したがって排中律から命題Aが正しいことが証明されるわけです。
 この背理法と数学的帰納法を使って自然数の整列性と整数における除法の原理という2つの基本的な性質を証明しておくことにしましょう。

定理1.9.18 自然数の整列性

 自然数の任意の空でない部分集合は最小元をもつ。

証明

∅≠S⊂ℕとする。T={n∈ℕ|任意のx∈Sについてn≦x}とおくと0∈T,T≠ℕである。ここでもしT+1⊂Tであると仮定すると自然数の公理(N3)に矛盾する。したがって排中律からm∈T,m+1∉Tなるmが存在することがいえる。m∈Tより、任意のx∈Sについてm≦xであるが、もしm∉Sであれば任意のx∈Sについてm<xとなる。x-m∈ℕ11より大きいかのどちらか、すなわちm+1=xまたはm+1<xである。したがってm+1≦xとなり、m+1∉Tであることに矛盾する。ゆえに排中律からm∈Sであり、Sの最小元である。■

定理1.9.20 除法の原理

a,bを任意の整数とし、b≠0とする。このとき
a = bq + r, 0≦r<|b|
を成り立たせる整数q,rがただ一組だけ存在する。

証明

A={a-bn|n∈ℤ}∩ℕの最小元をrとするとr=a-bqと書けていて、0≦r<|b|を満たしている。■
 また数学的帰納法と同じような使われ方をするものとしてフェルマーが発見した無限降下法むげんこうかほう, inifinite descentというものがあります。状況によっては数学的帰納法よりも便利ですのでこれも導入しておくことにしましょう。

定理1.9.23 無限降下法

P(n)を自然数nに関する命題とする。このとき、
(1) ある自然数kについてP(k)が成り立つ。
(2) k>1ならば、あるk'<kがあってP(k')が成り立つ。
ならばP(1)が成り立つ。

証明

A={n∈ℕ|P(n)が成り立つ}とおくと(1)よりk∈Aであり、自然数の整列性から最小元aが存在する。a=1ならば証明が終わる。a>1ならば(2)よりn<aが存在してP(n)が成り立つ。これはaが最小元であることに矛盾する。■

参考文献

[1] 彌永 昌吉, 数の体系(上) (岩波新書), 岩波書店, 1972
[2] 彌永 昌吉, 数の体系(下) (岩波新書), 岩波書店, 1978
[3] 齋藤 正彦, 数学の基礎―集合・数・位相 (基礎数学), 東京大学出版会, 2002
img
 
 
[4] デーデキント, 数について―連続性と数の本質 (岩波文庫), 岩波書店, 1961
[5] 藤沢 令夫, プラトンの哲学 (岩波新書), 岩波書店, 1998
img
 
 
[6] 荻野 弘之, 哲学の原風景 (NHKライブラリー), 日本放送出版協会, 1999
img
 
 
[8] ア・ヤ ヒンチン (蟹江幸博訳), 数論の3つの真珠, 日本評論社, 2000
img
 
 
[9] アンドレ ヴェイユ(足立恒雄,三宅克哉訳), 数論―歴史からのアプローチ, 日本評論社, 1987
img
 
 
註  釈
*1Hermann Diels, Walther Kranz, "Die Fragmente der Vorsokratiker"/日下部 吉信編訳, 初期ギリシア自然哲学者断片集1/2/3(ちくま学芸文庫), 筑摩書房, 2000
人  物
パスカル Pascal, Blaise, 1623-1662
フランスの数学者・物理学者。
パルメニデス Parmenides, BC515頃-445頃
ゼノン Zenon, BC490頃-435頃
 
物  品
算術三角形論 Traité du Triangle arithmétique
第4章4.2節 パスカルの算術三角形論を参照のこと。
パルメニデス Parmenides
プラトン全集4 パルメニデス・ピレボス, 田中美知太郎訳, 岩波書店, 1986
 
数  学
自然数の公理 しぜんすうのこうり, axiom of natural number
デデキント(J.W.R.Dedekind,1831-1916)が『数とは何か、何であるべきか』で自然数がこの公理により完全に特徴付けられることを示した。ペアノ(G.Peano,1858-1932)の公理と呼ばれることが多い。
公理 こうり, axiom
数学的帰納法 すうがくてききのうほう, mathematical induction
排中律 はいちゅうりつ, law of excluded middle
ブラウワー(1881-1966)は排中律を認めない直観論理を提唱した。その意味で排中律を公理として認める論理は古典論理と呼ばれている。現代の多くの数学者は古典論理に基づいて数学を行なっている。
背理法 はいりほう, reduction to absurdity
無限降下法 むげんこうかほう, inifinite descent
フェルマーが1659年にホイヘンス(Christiaan Huygens, 1629-1695 オランダの数学者、物理学者、天文学者)に宛てた書簡に無限降下法を発見するに至った経緯が説明されている。
 
Published by SANENSYA Co.,Ltd.