# 証明の技術：数学的帰納法と背理法はなぜ正しいのか > 数学的帰納法が正しい理由を整列性とペアノの公理から説明し、基底ステップを欠いた誤証明や「すべての馬は同じ色」の穴を解剖する。背理法と対偶証明の違いを整理し、平方根 2 が無理数であることを二通りに証明する。 > https://rikai.mugen-giken.com/mathematics/foundations/proof-techniques ## 0. この記事の要点 - 数学的帰納法の帰納ステップが証明しているのは「$P(n)$ が正しい」ではなく「$P(n)$ ならば $P(n+1)$」という**含意**です。ここを取り違えると、帰納法は循環論法に見えてしまいます。 - 帰納法の正しさは自然数の整列性から従い、逆に整列性も帰納法から従います。ペアノの公理系では帰納法は第 5 公理、つまり自然数の定義の一部です。証明すべき定理なのか、置くべき公理なのかは、どこから出発するかの問題です。 - 基底ステップを落とすと、帰納ステップが完璧でも結論はすべて偽になりえます。逆に「すべての馬は同じ色」の誤証明では、基底は正しく、帰納ステップが $n = 1$ でだけ破れています。 - 背理法は「$\lnot P$ を仮定して何らかの矛盾を導く」、対偶証明は「$\lnot Q$ を仮定して $\lnot P$ を導く」。後者は前者の特殊な形であり、書き直せるなら対偶で書いたほうが読みやすくなります。 - $x^2 = 2$ を満たす有理数が存在しないことは、既約分数を使う証明と無限降下法による証明の二通りで示せます。後者は整列性、つまり帰納法を裏返した形をそのまま使います。 ## 1. 動機：無限個の主張を有限の紙に書く 数学の主張の多くは「すべての自然数 $n$ について〜」という形をしています。たとえば $$ 1 + 2 + \cdots + n = \frac{n(n+1)}{2} $$ これは $n = 1$ の主張、$n = 2$ の主張、$n = 3$ の主張……という無限個の主張を一度に述べたものです。$n = 1$ から順に確かめていけば $n = 100$ までは有限時間で片づきます。しかしそこで止めた人は、「では $n = 101$ は」と聞かれて答えられません。確認を積み上げる方針では、いつまでたっても終わりません。 有限の紙に無限個の主張の証明を書くには、質的に違う仕掛けが要ります。数学的帰納法はその代表です。着想は単純で、「1 枚目を倒す」ことと「どの 1 枚が倒れても次が倒れる」ことの 2 つだけを示せば、ドミノは無限に倒れていくというものです。無限回の確認を、有限個（この場合 2 つ）の証明に圧縮しているわけです。 一方、示したい命題の中身を直接組み立てられない場合もあります。「$\sqrt2$ は分数で書けない」という主張は、書けないことを示すのですから、何かを作って見せる方向では手が出ません。こういうときは「書けたとしたら何が起きるか」を追いかけて、破綻を探します。これが背理法です。 歴史的には、どちらも古い技術です。通約不可能量（共通の物差しで測れない二つの量）の発見は紀元前 5 世紀のピタゴラス学派にさかのぼり、正方形の対角線と辺が通約不可能であることは背理法によって示されました。数学的帰納法の明示的な使用は 16 世紀のマウロリコ、17 世紀のパスカル『算術三角形論』に見られ、19 世紀末にペアノが自然数の公理系の一部としてこれを定式化します。 使い方を覚えるだけなら 1 ページで済みます。この記事が「なぜ正しいのか」に紙面を割くのは、根拠を知らないと誤った帰納法を見抜けないからです。誤った帰納法は実在しますし、しかも見た目は正しい帰納法とほとんど区別がつきません。 ## 2. 準備：含意と、その逆・裏・対偶 自然数全体を $\mathbb{N} = \{1, 2, 3, \ldots\}$ と書きます。この記事では $0$ を自然数に含めません。整数全体を $\mathbb{Z}$、有理数全体を $\mathbb{Q}$、実数全体を $\mathbb{R}$ と書きます。数の体系そのもの（$\mathbb{Q}$ や $\mathbb{R}$ が であること）については [数とは何か？](/mathematics/foundations/what-is-a-number) を、論理記号の扱い（ や量化子）については [数学の国語 - 集合と論理](/mathematics/foundations/sets-and-logic) を参照してください。 命題 $P$ と $Q$ に対し、$P \Rightarrow Q$（「$P$ ならば $Q$」）の真偽は次の表で定めます。とくに、**$P$ が偽であれば $Q$ の真偽によらず $P \Rightarrow Q$ は真**です。この規約は後で何度も効いてきます。 命題 $P \Rightarrow Q$ に対して、 - $Q \Rightarrow P$ をその**逆**、 - $\lnot P \Rightarrow \lnot Q$ をその**裏**、 - $\lnot Q \Rightarrow \lnot P$ をその**対偶** といいます。 真偽の対応は次のとおりです。 | $P$ | $Q$ | $P \Rightarrow Q$ | 対偶 $\lnot Q \Rightarrow \lnot P$ | 逆 $Q \Rightarrow P$ | |---|---|---|---|---| | 真 | 真 | 真 | 真 | 真 | | 真 | 偽 | 偽 | 偽 | 真 | | 偽 | 真 | 真 | 真 | 偽 | | 偽 | 偽 | 真 | 真 | 真 | 第 3 列と第 4 列が完全に一致し、第 5 列は一致しません。もとの命題と対偶は同じことを言っており、逆は別のことを言っている、というのがこの表の読み方です。 ## 3. 数学的帰納法とその正しさ 自然数の集合には、実数や有理数にはない次の性質があります。 $\mathbb{N}$ の空でない任意の部分集合は、最小元をもつ。すなわち $S \subseteq \mathbb{N}$ かつ $S \ne \emptyset$ ならば、ある $m \in S$ が存在して、すべての $n \in S$ に対し $m \le n$ が成り立つ。 この性質が自明でないことは、有理数と比べればわかります。集合 $\{x \in \mathbb{Q} : x > 0\}$ は空でない $\mathbb{Q}$ の部分集合ですが、最小元をもちません。正の有理数 $x$ を一つ取れば $x/2$ はより小さい正の有理数だからです。「これ以上小さくできない」が保証されるのは、自然数が離散的に並んでいることの帰結です。 各 $n \in \mathbb{N}$ に対して命題 $P(n)$ が定まっているとする。次の 2 条件を仮定する。 1. （基底ステップ）$P(1)$ は真である。 2. （帰納ステップ）任意の $n \in \mathbb{N}$ に対して、「$P(n)$ が真ならば $P(n+1)$ も真である」が成り立つ。 このとき、すべての $n \in \mathbb{N}$ に対して $P(n)$ は真である。 反例の集合 $$ S = \{\, n \in \mathbb{N} : P(n) \text{ は偽} \,\} $$ を考えます。示したい結論は $S = \emptyset$ にほかなりません。 そこで $S \ne \emptyset$ と仮定します（ここで背理法を使います。背理法の正当化は で行いますが、ここでは既知の論理として使わせてください）。$S$ は $\mathbb{N}$ の空でない部分集合ですから、 により最小元 $m \in S$ をもちます。 まず $m \ne 1$ です。実際、仮定 1 より $P(1)$ は真なので $1 \notin S$ であり、$m \in S$ だからです。$m \in \mathbb{N}$ かつ $m \ne 1$ なので $m \ge 2$、したがって $m - 1$ もまた自然数です。 次に $m - 1 \notin S$ です。なぜなら $m - 1 < m$ であり、$m$ は $S$ の最小元だからです。$m-1 \notin S$ とは $P(m-1)$ が真だということです。 ここで仮定 2 を $n = m - 1$ に適用します。$P(m-1)$ が真なので $P((m-1)+1) = P(m)$ も真です。ところが $m \in S$ とは $P(m)$ が偽だということでした。$P(m)$ が真かつ偽となり矛盾します。 したがって $S \ne \emptyset$ という仮定は誤りで、$S = \emptyset$、すなわちすべての $n$ で $P(n)$ は真です。
A["P(1)"] A -->|"帰納ステップ (n=1)"| B["P(2)"] B -->|"帰納ステップ (n=2)"| C["P(3)"] C -->|"帰納ステップ (n=3)"| D["P(4)"] D -->|"以下同様"| E["…"]`} />
帰納法にはじめて触れた人がほぼ必ず抱く疑問は、「$P(n)$ を仮定して $P(n+1)$ を示すのなら、示したいことを仮定していることにならないか」というものです。 なりません。帰納ステップで証明しているのは $P(n)$ ではなく、$P(n) \Rightarrow P(n+1)$ という**含意**だからです。この含意は、$P(n)$ が偽である場合には §2 の真理値表によって自動的に真になります。つまり帰納ステップだけを証明しても、$P$ が真である $n$ が一つでも存在することは保証されません。実際 は、帰納ステップが完全に正しいのにすべての $n$ で $P(n)$ が偽である例です。 「$P(n)$ を仮定する」という言い回しは、「もし $P(n)$ が真である世界にいるならば」という条件付きの議論の合図であって、$P(n)$ を認めているわけではありません。 すべての $n \in \mathbb{N}$ に対し $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ が成り立ちます。 $P(n)$ をこの等式とします。 **基底ステップ。** $n = 1$ のとき、左辺は $1$、右辺は $\dfrac{1 \cdot 2}{2} = 1$ です。一致するので $P(1)$ は真です。 **帰納ステップ。** $n \in \mathbb{N}$ を任意に取り、$P(n)$、すなわち $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ を仮定します。このとき $$ \begin{aligned} \sum_{k=1}^{n+1} k &= \left(\sum_{k=1}^{n} k\right) + (n+1) \\ &= \frac{n(n+1)}{2} + (n+1) && \text{（帰納法の仮定を使用）} \\ &= (n+1)\left(\frac{n}{2} + 1\right) \\ &= \frac{(n+1)(n+2)}{2}. \end{aligned} $$ 最後の式は $\dfrac{(n+1)\bigl((n+1)+1\bigr)}{2}$ そのものですから、$P(n+1)$ が成り立ちます。 により、すべての $n$ で $P(n)$ が成り立ちます。 $x$ を $x \ge -1$ を満たす実数、$n \in \mathbb{N}$ とすると $(1+x)^n \ge 1 + nx$ が成り立ちます。 **基底ステップ。** $n = 1$ のとき、両辺とも $1 + x$ で等号が成り立ちます。 **帰納ステップ。** $(1+x)^n \ge 1 + nx$ を仮定します。仮定 $x \ge -1$ より $1 + x \ge 0$ ですから、不等式の両辺に $1+x$ を掛けても不等号の向きは変わりません。よって $$ (1+x)^{n+1} = (1+x)^n (1+x) \ge (1+nx)(1+x) = 1 + (n+1)x + n x^2 \ge 1 + (n+1)x . $$ 最後の不等号は $n x^2 \ge 0$ からです。 **仮定 $x \ge -1$ を落とすとどうなるか。** 帰納ステップで $1+x \ge 0$ を使ったのですから、そこが壊れます。実際 $x = -4$, $n = 3$ とすると、左辺は $(1-4)^3 = -27$、右辺は $1 + 3 \cdot (-4) = -11$ で、$-27 \ge -11$ は成り立ちません。仮定は飾りではなく、証明のどこかで必ず使われています。 ## 4. ペアノの公理：帰納法は定理か公理か は整列性から証明されました。では整列性はどこから来るのでしょうか。実は整列性も帰納法から証明できます。両者は同値な性質であり、どちらか一方を自然数の性質として認めれば他方が従います。 そうすると「自然数とは何か」という問いに戻らざるをえません。19 世紀末にペアノが与えた答えが次の公理系です。$s(n)$ は $n$ の**後者**（次の数）を表します。 集合 $\mathbb{N}$、その元 $1$、および写像 $s : \mathbb{N} \to \mathbb{N}$ が次を満たすとする。 1. $1 \in \mathbb{N}$。 2. 任意の $n \in \mathbb{N}$ に対し $s(n) \in \mathbb{N}$。 3. 任意の $n \in \mathbb{N}$ に対し $s(n) \ne 1$（$1$ はどの数の後者でもない）。 4. 任意の $m, n \in \mathbb{N}$ に対し、$s(m) = s(n)$ ならば $m = n$（$s$ は単射）。 5. （帰納法の公理）$S \subseteq \mathbb{N}$ が「$1 \in S$」かつ「$n \in S$ ならば $s(n) \in S$」を満たすならば、$S = \mathbb{N}$ である。 このとき $(\mathbb{N}, 1, s)$ を自然数の体系という。 第 5 公理は そのものです。$S$ として「$P(n)$ が真であるような $n$ の集合」を取れば、条件は基底ステップと帰納ステップに、結論は「すべての $n$ で $P(n)$」に翻訳されます。つまりペアノの立場では、帰納法は証明すべき定理ではなく、**自然数がどういうものかを定める規定の一部**です。 なお、ペアノ自身の 1889 年の原論文では出発点の数は $1$ でした。今日の教科書では $0$ から始める流儀が多く、どちらでも理論は同じように展開できます。 公理を一つ落とすと何が壊れるかを見ると、各公理の役割がわかります。 **公理 3 を落とす。** $\mathbb{N}' = \{1, 2, 3\}$ とし、$s(1) = 2$, $s(2) = 3$, $s(3) = 1$ と定めます。$s$ は $\mathbb{N}'$ 上の全単射なので公理 4 は成立します。公理 5 も成立します。実際、$1 \in S$ かつ $s$ で閉じている $S$ は $1, 2, 3$ をすべて含むので $S = \mathbb{N}'$ です。しかし $s(3) = 1$ なので公理 3 が破れています。つまり公理 3 がないと、有限個しか元をもたない「自然数もどき」が許されてしまいます。帰納法だけでは無限性は出てこないのです。 **公理 5 を落とす。** $\mathbb{N}$ に、整数と同じ形に並んだ元の列 $\ldots, a_{-1}, a_0, a_1, \ldots$ を付け加えた集合を $\mathbb{N}^{*}$ とし、$s(a_k) = a_{k+1}$ と定めます。$a_k$ は $1$ でも $s(n)$（$n$ は普通の自然数）でもないので公理 1 から 4 はすべて成立します。ところが $S = \mathbb{N}$ は $1$ を含み $s$ で閉じているのに $\mathbb{N}^{*}$ 全体と一致しません。公理 5 は「$1$ から $s$ を繰り返して届く範囲より外に余計な元はない」という要請なのです。 この「余計な元がついた自然数」は非標準モデルと呼ばれ、形式的な体系が意図した対象を一意に定めきれるかという問題につながります。この方向の話題は [数学基礎論への招待 - 不完全性定理](/mathematics/foundations/incompleteness-theorems)、とくに を参照してください。 各 $n \in \mathbb{N}$ に対して命題 $P(n)$ が定まっているとする。 - 任意の $n \in \mathbb{N}$ に対して、「$n$ より小さいすべての $k \in \mathbb{N}$ について $P(k)$ が真」ならば「$P(n)$ が真」 が成り立つとする。このとき、すべての $n \in \mathbb{N}$ に対して $P(n)$ は真である。 $Q(n)$ を「$n$ 以下のすべての $k \in \mathbb{N}$ について $P(k)$ が真である」という命題とし、$Q$ に を適用します。 **基底ステップ。** 仮定を $n = 1$ に適用します。$1$ より小さい自然数は存在しないので、「$1$ より小さいすべての $k$ について $P(k)$ が真」は空虚に真です（すべての $k$ について言うべきことが何もありません）。よって仮定より $P(1)$ は真です。$1$ 以下の自然数は $1$ だけなので、$Q(1)$ が成り立ちます。 **帰納ステップ。** $Q(n)$ を仮定します。すなわち $k \le n$ なるすべての $k$ で $P(k)$ は真です。自然数について $k < n+1$ と $k \le n$ は同値ですから、これは「$n+1$ より小さいすべての $k$ で $P(k)$ が真」ということです。そこで仮定を $n+1$ に適用すると $P(n+1)$ が真になります。あわせて $k \le n+1$ なるすべての $k$ で $P(k)$ が真、すなわち $Q(n+1)$ が成り立ちます。 により、すべての $n$ で $Q(n)$ が真です。とくに $P(n)$ が真です。 $2$ 以上のすべての自然数は、素数の積として表せます（素数 $1$ 個だけの積も認めます）。 $P(n)$ を「$n \ge 2$ ならば $n$ は素数の積として表せる」とします。$n = 1$ のときは前提が偽なので $P(1)$ は真です（§2 の真理値表）。 $n \ge 2$ とし、$n$ より小さいすべての自然数 $k$ で $P(k)$ が真だと仮定します。 - $n$ が素数のとき。$n$ 自身が素数 $1$ 個の積なので $P(n)$ が成り立ちます。 - $n$ が素数でないとき。$n \ge 2$ で素数でないので、$n = ab$ かつ $1 < a < n$、$1 < b < n$ を満たす自然数 $a, b$ が存在します（これが合成数の定義です）。$1 < a$ と $a$ が自然数であることから $a \ge 2$、同様に $b \ge 2$ です。また $a < n$、$b < n$ なので、帰納法の仮定が $a$ と $b$ の両方に使えて、$a$ も $b$ も素数の積に書けます。それらを並べれば $n = ab$ も素数の積です。 いずれの場合も $P(n)$ が成り立つので、 よりすべての $n$ で $P(n)$ が真です。 ここで通常の帰納法が使えないことに注意してください。$n$ の分解 $n = ab$ に現れる $a, b$ は $n-1$ とは限らず、$2$ から $n-1$ のどこに現れるか予測できません。「一つ前」ではなく「それより小さいものすべて」を仮定できることが、完全帰納法の値打ちです。 ## 5. 帰納法が壊れるとき ### 5.1. 基底ステップを忘れる $P(n)$ を次の等式とします。 $$ \sum_{k=1}^{n} k = \frac{n(n+1)}{2} + 7 . $$ 帰納ステップを確かめてみます。$P(n)$ を仮定すると $$ \sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) + (n+1) = \frac{n(n+1)}{2} + 7 + (n+1) = \frac{(n+1)(n+2)}{2} + 7 $$ となり、これは $P(n+1)$ そのものです。帰納ステップは完全に正しく、どこにも誤りがありません。 ところが $P(1)$ は「$1 = 1 + 7$」であり偽です。 によって正しい和は $n(n+1)/2$ ですから、$P(n)$ はすべての $n$ で偽です。 倒れる仕組みだけが整っていて、最初の 1 枚を倒す人がいないドミノ列——それが基底ステップを欠いた帰納法です。 で述べたとおり、帰納ステップは含意しか主張していないので、単独では何も生みません。 ### 5.2. 帰納ステップに穴がある $P(n)$ を「馬の任意の $n$ 頭の集まりについて、それらはすべて同じ色である」とします。 **基底ステップ。** $P(1)$ は真です。馬 $1$ 頭だけの集まりは、その馬自身と同じ色なのですから。 **帰納ステップ（と称するもの）。** $P(n)$ を仮定し、馬 $n+1$ 頭 $h_1, h_2, \ldots, h_{n+1}$ を取ります。 $$ A = \{h_1, \ldots, h_n\}, \qquad B = \{h_2, \ldots, h_{n+1}\} $$ はどちらも $n$ 頭の集まりなので、帰納法の仮定より $A$ の中の馬はすべて同色、$B$ の中の馬もすべて同色です。$A \cap B = \{h_2, \ldots, h_n\}$ に属する馬を一頭取れば、その色は $A$ 全体の色でも $B$ 全体の色でもあるので、$A$ の色と $B$ の色は一致します。$A \cup B$ は $n+1$ 頭全体ですから、$P(n+1)$ が成り立ちます。 **穴はどこか。** 最後の議論は $A \cap B \ne \emptyset$ を前提にしています。$A \cap B = \{h_2, \ldots, h_n\}$ が空でないのは $n \ge 2$ のときだけです。$n = 1$ のときは $A = \{h_1\}$、$B = \{h_2\}$ で共通の馬がおらず、$A$ の色と $B$ の色を結びつける根拠がありません。 つまり $P(1) \Rightarrow P(2)$ が示せていません。そして $P(2)$ は偽です（色の違う馬は実在します）。ドミノは 1 枚目と 2 枚目の間で切れており、そこから先は一枚も倒れません。 教訓は、帰納ステップは**すべての** $n$ について示さねばならない、ということです。「一般の $n$ について」と書いた議論が、小さい $n$ で暗黙の前提を使っていないかを必ず点検してください。とくに「二つの部分集合の共通部分を取る」「$n-1$ を考える」「二つに分ける」といった操作が出てきたら要注意です。 ### 5.3. 数値実験は証明ではない 「$n = 1$ から $n = 5$ まで確かめたので一般に正しい」は証明ではありません。反例が現れるのがずっと先だという例は、いくらでもあります。 - オイラーが 1772 年ごろに注目した多項式 $f(n) = n^2 + n + 41$ は、$n = 0, 1, \ldots, 39$ という $40$ 個の整数すべてに対して素数の値を取ります。しかし $f(40) = 1600 + 40 + 41 = 1681 = 41^2$ は素数ではありません。 - フェルマー数 $F_n = 2^{2^n} + 1$ は $n = 0, 1, 2, 3, 4$ に対して $3, 5, 17, 257, 65537$ となり、すべて素数です。フェルマーはすべての $n$ で素数になると予想しましたが、1732 年にオイラーが $F_5 = 4294967297 = 641 \times 6700417$ と分解して見せました。 次のコードで両方を確かめられます。 ```python def is_prime(m): if m < 2: return False d = 2 while d * d <= m: if m % d == 0: return False d += 1 return True # n^2 + n + 41 が素数でない最小の n（0 以上） print([n for n in range(41) if not is_prime(n * n + n + 41)]) # -> [40] # フェルマー数 F_5 の分解 print(2**32 + 1 == 641 * 6700417) # -> True ``` 数値実験は、何を証明すべきかを見つけるためには有用です。しかしそれ自体は証明ではありません。「$n$ から $n+1$ へ渡す論理」を書いてはじめて、無限個の主張が保証されます。 ## 6. 背理法と対偶証明 ### 6.1. 対偶証明 任意の命題 $P, Q$ について、$P \Rightarrow Q$ が真であることと、その対偶 $\lnot Q \Rightarrow \lnot P$ が真であることは同値である。 §2 の真理値表で第 3 列と第 4 列が一致していることからも読み取れますが、意味を追う形でも示しておきます。 （$\Rightarrow$ の向き）$P \Rightarrow Q$ が真だとします。$\lnot Q$ を仮定します。もし $P$ が真だとすると、$P \Rightarrow Q$ より $Q$ が真になり、仮定 $\lnot Q$ と両立しません。よって $P$ は偽、すなわち $\lnot P$ が真です。$\lnot Q$ から $\lnot P$ が導けたので $\lnot Q \Rightarrow \lnot P$ が真です。 （$\Leftarrow$ の向き）$\lnot Q \Rightarrow \lnot P$ が真だとします。$P$ を仮定します。もし $Q$ が偽、つまり $\lnot Q$ が真だとすると、仮定より $\lnot P$ が真になり、$P$ と両立しません。よって $\lnot Q$ は偽、すなわち $\lnot \lnot Q$ が真です。ここで二重否定除去 $\lnot\lnot Q \Rightarrow Q$ を使うと $Q$ が真です。$P$ から $Q$ が導けたので $P \Rightarrow Q$ が真です。 $\Leftarrow$ の向きで二重否定除去を使ったことに注意してください。「対偶を示せばもとの命題が示せる」という、実際に使うほうの向きこそが、古典論理に固有の規則に依存しています。 ### 6.2. 背理法 命題 $P$ について、$\lnot P$ を仮定するとある命題 $R$ に対して $R$ と $\lnot R$ の両方が導かれるならば、$P$ は真である。 仮定は $\lnot P \Rightarrow (R \wedge \lnot R)$ が真だということです。$R \wedge \lnot R$ は $R$ の真偽にかかわらず偽です（$R$ が真なら $\lnot R$ が偽、$R$ が偽なら $R$ が偽で、いずれにせよ連言は偽）。 いま $\lnot P$ が真だと仮定すると、真である含意の前件が真なので後件 $R \wedge \lnot R$ も真になります。これは $R \wedge \lnot R$ が偽であることに反します。よって $\lnot P$ は偽、すなわち $\lnot\lnot P$ が真です。二重否定除去（同じことですが排中律 $P \vee \lnot P$）により $P$ が真です。 ### 6.3. 二つはどう違い、どう重なるか
直接証明 P ならば Q を示す 対偶証明 P ならば Q を示す 背理法 P を示す P を仮定する ¬Q を仮定する ¬P を仮定する Q に到達する ¬P に到達する 何らかの矛盾に到達する 上二つはゴールが決まっている。背理法だけは、どんな矛盾を出してもよい。
表にまとめます。 | | 直接証明 | 対偶証明 | 背理法 | |---|---|---|---| | 示したい形 | $P \Rightarrow Q$ | $P \Rightarrow Q$ | $P$（含意でなくてよい） | | 仮定として置くもの | $P$ | $\lnot Q$ | $\lnot P$ | | 目指すゴール | $Q$ | $\lnot P$ | 任意の矛盾 | | ゴールは決まっているか | 決まっている | 決まっている | 決まっていない | | 依存する論理規則 | なし | 二重否定除去 | 排中律（二重否定除去） | 二つは無関係ではありません。$P \Rightarrow Q$ を背理法で示すとは、$P$ かつ $\lnot Q$ を仮定して矛盾を導くことです。その矛盾として特に「$\lnot P$ と $P$」を選べば、それは $\lnot Q$ から $\lnot P$ を導いたということ、つまり対偶証明にほかなりません。**対偶証明は背理法の特殊な場合**です。 逆に、背理法で書かれた証明の多くは対偶証明に書き直せます。書き直せるなら、そうしたほうが読みやすくなります。「矛盾が出ました」で終わる証明は、どの仮定がどこで効いたのかを読者が追いにくいからです。ゴールが最初から $\lnot P$ と決まっている対偶証明のほうが、議論の行き先がはっきりします。 「$P$ を仮定して矛盾を導き、$\lnot P$ を結論する」のは、否定という記号の意味そのものであり、直観主義論理でも認められます。古典論理に固有なのは、その裏返し、つまり「$\lnot P$ を仮定して矛盾を導き、$P$ を結論する」ほうです。ここで使う $\lnot\lnot P \Rightarrow P$ は、直観主義論理では証明できません。 この違いは「存在する」を主張するときに表面化します。「$x$ が存在しないと矛盾する」から「$x$ が存在する」を導く証明は、その $x$ を一つも作ってくれません。具体的な作り方まで与える証明を構成的証明と呼び、区別します。無限集合の大小を比べるカントールの対角線論法も、形の上では背理法ですが、実際には「与えられた列に入らない元を作る手続き」を与えている点で構成的です。詳しくは [濃度と無限 - 無限にも大小がある](/mathematics/foundations/cardinality-and-infinity)、とくに を参照してください。 「素数は無限に存在する」は背理法の例として紹介されることが多い命題です。背理法版はこうなります。素数が有限個 $p_1, \ldots, p_r$ しかないと仮定し、$N = p_1 p_2 \cdots p_r + 1$ を考えます。$N \ge 2$ なので より $N$ は素因数 $q$ をもちます。仮定よりこの $q$ はどれかの $p_i$ に等しいはずです。しかし $p_i$ は積 $p_1 \cdots p_r$ を割り切るので、$N$ を $p_i$ で割った余りは $1$ であり、$p_i$ は $N$ を割りません。矛盾です。 ところが、この議論は背理法を使わずにそのまま書けます。任意に有限個の素数 $p_1, \ldots, p_r$ を取ったとき、$N = p_1 \cdots p_r + 1$ の素因数 $q$ はどの $p_i$ とも異なります（同じ理由で $p_i$ は $N$ を割らないからです）。つまり、どんな有限リストに対しても、そこに載っていない素数を実際に一つ作ることができます。ゆえに素数は無限個です。 こちらの書き方は、$r$ 個の素数から $r+1$ 個目を作る手続きを与えており、内容が多い分だけ有用です。ユークリッド『原論』第 IX 巻命題 20 の議論も、この直接的な形に近いものです。仮定を置いて矛盾を出すのは強力ですが、必要のないところで使うと情報を捨てることになります。 ## 7. 平方根 2 は無理数である ### 7.1. 準備 実数 $x$ が**有理数**であるとは、整数 $p$ と $0$ でない整数 $q$ を用いて $x = p/q$ と書けることをいう。有理数全体を $\mathbb{Q}$ と書く。実数であって有理数でないものを**無理数**という。 整数 $n$ が**偶数**であるとは、ある整数 $m$ を用いて $n = 2m$ と書けることをいう。$n$ が**奇数**であるとは、ある整数 $m$ を用いて $n = 2m+1$ と書けることをいう。 任意の整数は偶数か奇数のいずれか一方であり、両方であることはありません。前半は $2$ による除法の定理（余りが $0$ か $1$）から、後半は $2m = 2m'+1$ から $2(m-m') = 1$ となり、左辺が偶数で右辺が $2$ で割り切れないことから従います。 任意の有理数 $x$ に対し、整数 $p$ と自然数 $q$ で、$x = p/q$ かつ $\gcd(p, q) = 1$ を満たすものが存在する。 より $x = a/b$（$a$ は整数、$b$ は $0$ でない整数）と書けます。$b < 0$ ならば分子分母の符号を同時に変えて $x = (-a)/(-b)$ とすればよいので、はじめから $b \ge 1$、すなわち $b \in \mathbb{N}$ としてよいとします。 集合 $$ T = \{\, b' \in \mathbb{N} : \text{ある整数 } a' \text{ が存在して } x = a'/b' \,\} $$ を考えます。$b \in T$ なので $T \ne \emptyset$ です。 により $T$ は最小元 $q$ をもちます。$q \in T$ なので、ある整数 $p$ で $x = p/q$ と書けます。 この $p, q$ が $\gcd(p,q) = 1$ を満たすことを示します。$d = \gcd(p, q)$ とおき、$d > 1$ と仮定します。$p = d p'$, $q = d q'$ を満たす整数 $p', q'$ が取れて、$q' = q/d$ は自然数であり $1 \le q' < q$ です（$d > 1$ かつ $q \ge 1$ より）。また $$ \frac{p'}{q'} = \frac{dp'}{dq'} = \frac{p}{q} = x $$ なので $q' \in T$ です。これは $q$ が $T$ の最小元であることに反します。よって $d = 1$ です。 なお、$p/q$ という表示は一意ではありません（$1/2 = 2/4 = 3/6 = \cdots$）。有理数を「整数の組を適切な同値関係で割ったもの」として定義する立場については [関係と同値関係 - 「同じ」とは何か](/mathematics/foundations/equivalence-relations)、とくに を参照してください。上の補題は、その同値類の中に「分母が最小の代表元」が必ずあると言っています。 整数 $n$ について、$n^2$ が偶数ならば $n$ は偶数である。 対偶「$n$ が奇数ならば $n^2$ は奇数である」を示します。 により、これでもとの主張が従います。 $n$ を奇数とすると、 よりある整数 $m$ で $n = 2m+1$ と書けます。このとき $$ n^2 = (2m+1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1 . $$ $2m^2 + 2m$ は整数なので、$n^2$ は の意味で奇数です。 この補題を直接示そうとすると難儀します。「$n^2 = 2k$」という等式から $n$ の形を取り出すには、素因数分解のような重い道具が要るからです。対偶を取ると、仮定される側が「$n = 2m+1$」という**形の情報**に変わり、あとは展開するだけで済みます。仮定と結論のうち、形の情報を持っているのがどちらかを見て、それを仮定側に回す——これが対偶証明を使う判断基準です。 ### 7.2. 証明 $x^2 = 2$ を満たす有理数 $x$ は存在しない。したがって、実数として $\sqrt2$（$\sqrt2 > 0$ かつ $(\sqrt2)^2 = 2$ を満たす実数）が存在するならば、それは無理数である。 $x^2 = 2$ を満たす有理数 $x$ が存在すると仮定します（背理法）。 により、整数 $p$ と自然数 $q$ で $$ x = \frac{p}{q}, \qquad \gcd(p, q) = 1 $$ を満たすものが取れます。両辺を $2$ 乗すると $p^2/q^2 = 2$ であり、$q^2 \ne 0$ なので両辺に $q^2$ を掛けて $$ p^2 = 2 q^2 . $$ この式を式 (A) と呼ぶことにします。(A) の右辺は $2 \times (\text{整数})$ の形なので、 より $p^2$ は偶数です。 により $p$ は偶数であり、ある整数 $r$ で $p = 2r$ と書けます。 これを (A) に代入すると $4r^2 = 2q^2$、両辺を $2$ で割って $$ q^2 = 2 r^2 $$ を得ます。右辺はやはり $2 \times (\text{整数})$ の形なので $q^2$ は偶数です。ふたたび により $q$ も偶数です。 こうして $p$ と $q$ はともに $2$ で割り切れることになり、$\gcd(p, q) \ge 2$ です。これは $\gcd(p,q) = 1$ に矛盾します。 したがって $x^2 = 2$ を満たす有理数は存在しません。 どこで何を使ったかを整理しておきます。 - 「既約分数に取れる」ことは 、その根拠は です。 - 「$p^2$ が偶数なら $p$ が偶数」は 、これは**対偶証明**でした。 - 最後の一撃、既約性との衝突が**背理法**の部分です。 定理の主張を「$\sqrt2$ は無理数である」ではなく「$x^2 = 2$ なる有理数は存在しない」の形で述べたのには理由があります。前者を主張するには、まず $\sqrt2$ という実数の存在（）を知っていなければなりません。その存在は実数の連続性（完備性、）に依存する、有理数だけの世界では言えない事実です。ここで証明したのは有理数の世界の中で完結する主張であり、実数の性質を一切使っていません。 ### 7.3. 無限降下法による別証明 $p^2 = 2q^2$ を満たす自然数の組 $(p, q)$ が存在すると仮定します。そこで $$ U = \{\, p \in \mathbb{N} : \text{ある } q \in \mathbb{N} \text{ が存在して } p^2 = 2q^2 \,\} $$ とおくと $U \ne \emptyset$ です。 により $U$ は最小元 $p_0$ をもちます。$p_0$ に対応する $q_0 \in \mathbb{N}$ を一つ取ると $p_0^2 = 2q_0^2$ です。 の証明と同じ計算で、$p_0$ は偶数なので $p_0 = 2r$（$r$ は整数）と書け、代入して $q_0^2 = 2r^2$ を得ます。$p_0 \ge 1$ と $p_0 = 2r$ から $r \ge 1$、すなわち $r \in \mathbb{N}$ です。したがって $q_0 \in U$ です。 一方、$q_0 \ge 1$ より $p_0^2 = 2q_0^2 > q_0^2$ であり、$p_0, q_0$ はともに正なので $p_0 > q_0$ です。$q_0 \in U$ かつ $q_0 < p_0$ は、$p_0$ が $U$ の最小元であることに反します。 よって $p^2 = 2q^2$ を満たす自然数の組は存在せず、とくに $x^2 = 2$ なる有理数もありません（$x = p/q$ とすれば $p, q$ の符号を調整して自然数の組が作れるからです）。 この形の議論を**無限降下法**といいます。「解があるとすれば、そこからより小さい解が作れる。しかし正の整数は無限に小さくなり続けられない」という論法で、フェルマーが好んで用いました。 注目してほしいのは、ここで使った道具が だけだという点です。整列性は の証明でも使われました。**数学的帰納法と無限降下法は、同じ「自然数は下に無限に続かない」という性質の表と裏です。**帰納法は下から積み上げ、降下法は上から降りてきて底がないことに矛盾する——向きが違うだけで、根は一つです。 ### 7.4. 一般化 自然数 $n$ が平方数でない（すなわち $n = m^2$ を満たす自然数 $m$ が存在しない）ならば、$x^2 = n$ を満たす有理数 $x$ は存在しない。 素因数分解の一意性（算術の基本定理）を使います。分解の存在は で完全帰納法により示しました。一意性の証明は本記事では扱いませんが、参考文献の高木『初等整数論講義』第 1 章にあります。 素数 $\ell$ と $0$ でない整数 $a$ に対し、$\ell^{e}$ が $a$ を割り切るような最大の $e \ge 0$ を $v_\ell(a)$ と書きます。素因数分解の一意性から、$0$ でない整数 $a, b$ に対して $$ v_\ell(ab) = v_\ell(a) + v_\ell(b) $$ が成り立ちます。とくに $v_\ell(a^2) = 2 v_\ell(a)$ は偶数です。 さて、$x^2 = n$ を満たす有理数 $x$ が存在したとします。$x = p/q$（$p$ は整数、$q$ は $0$ でない整数）と書くと $p^2 = n q^2$ です。$n \ge 1$ かつ $q \ne 0$ なので $p \ne 0$ です。任意の素数 $\ell$ について両辺の $v_\ell$ を取ると $$ 2 v_\ell(p) = v_\ell(n) + 2 v_\ell(q), \qquad \text{すなわち} \qquad v_\ell(n) = 2\bigl(v_\ell(p) - v_\ell(q)\bigr) . $$ したがって $v_\ell(n)$ はすべての素数 $\ell$ について偶数です。そこで $m = \prod_{\ell} \ell^{\,v_\ell(n)/2}$（積は $v_\ell(n) > 0$ なる有限個の素数にわたる）とおくと、指数がすべて整数なので $m$ は自然数であり、 $$ m^2 = \prod_{\ell} \ell^{\,v_\ell(n)} = n $$ となって $n$ は平方数です。対偶を取れば主張を得ます。 $n = 2, 3, 5, 6, 7, 8, 10, \ldots$ はいずれも平方数ではないので、これらの平方根はすべて無理数です。逆に $n = 4$ では $x = 2$ という有理数の解があります。§7.2 の証明を $n = 4$ に対してまねしようとすると、 にあたる主張が偽になって議論が止まります（ の (3) を参照してください）。 ## 8. 演習 $a, b$ を実数とする。$a + b \ge 2$ ならば、$a \ge 1$ または $b \ge 1$ であることを示せ。 対偶を示します。「$a \ge 1$ または $b \ge 1$」の否定は、 により「$a < 1$ かつ $b < 1$」です。したがって示すべき対偶は 「$a < 1$ かつ $b < 1$ ならば $a + b < 2$」 です。$a < 1$ の両辺に $b$ を足して $a + b < 1 + b$、また $b < 1$ の両辺に $1$ を足して $1 + b < 2$ です。不等号の推移律より $a + b < 2$ が従います。 により、もとの主張が成り立ちます。 この問題を直接証明しようとすると、「$a + b \ge 2$」から $a$ と $b$ のどちらが $1$ 以上かを選ばねばならず、場合分けが必要になります。否定を取ると結論の「または」が仮定の「かつ」に変わり、$a$ と $b$ の両方の情報を同時に使えるようになります。結論が「または」の形をしているときは対偶を疑ってください。 すべての $n \in \mathbb{N}$ に対して $$ \sum_{k=1}^{n} \frac{1}{k^2} \le 2 - \frac{1}{n} $$ が成り立つことを数学的帰納法で示せ。また、同じ方法で $\sum_{k=1}^{n} 1/k^2 \le 2$ を直接示そうとするとうまくいかない理由を説明せよ。 **基底ステップ。** $n = 1$ のとき、左辺は $1$、右辺は $2 - 1 = 1$ です。等号が成り立つので主張は真です。 **帰納ステップ。** $\sum_{k=1}^{n} 1/k^2 \le 2 - 1/n$ を仮定します。両辺に $1/(n+1)^2$ を加えて $$ \sum_{k=1}^{n+1} \frac{1}{k^2} \le 2 - \frac{1}{n} + \frac{1}{(n+1)^2} $$ を得ます。ここで $(n+1)^2 = (n+1)(n+1) \ge (n+1) n$（$n + 1 \ge n$ かつ $n+1 > 0$ より）なので $$ \frac{1}{(n+1)^2} \le \frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1} $$ です（最後の等号は通分すれば $\frac{(n+1) - n}{n(n+1)} = \frac{1}{n(n+1)}$ で確かめられます）。これを代入して $$ \sum_{k=1}^{n+1} \frac{1}{k^2} \le 2 - \frac{1}{n} + \frac{1}{n} - \frac{1}{n+1} = 2 - \frac{1}{n+1} $$ となり、$n+1$ の場合の主張が得られました。 より、すべての $n$ で成立します。 **なぜ $\le 2$ では回らないか。** $P'(n)$ を「$\sum_{k=1}^n 1/k^2 \le 2$」とすると、$P'(n)$ を仮定して得られるのは $$ \sum_{k=1}^{n+1} \frac{1}{k^2} \le 2 + \frac{1}{(n+1)^2} $$ だけで、右辺は $2$ を超えています。$P'(n+1)$ は結論できません。仮定が弱すぎて、加えた分を吸収する余裕がないのです。 $2 - 1/n$ という形は $2$ より強い主張ですが、そのぶん帰納法の仮定も強くなり、$1/(n+1)^2$ を吸収する「のりしろ」$1/n - 1/(n+1)$ を持っています。**より強い主張のほうが帰納法では証明しやすいことがある**——これを帰納法の仮定を強めるといい、帰納法を使う際の基本的な技術です。 (1) 整数 $n$ について、「$n^2$ が $3$ の倍数ならば $n$ は $3$ の倍数」を対偶を用いて示せ。 (2) (1) を使って、$x^2 = 3$ を満たす有理数 $x$ が存在しないことを示せ。 (3) 同じ論法を $x^2 = 4$ に適用しようとすると、どこで破れるかを述べよ。 **(1)** 対偶「$n$ が $3$ の倍数でないならば $n^2$ も $3$ の倍数でない」を示します。$3$ による除法の定理より、整数 $n$ はある整数 $m$ を用いて $n = 3m$, $n = 3m+1$, $n = 3m+2$ のいずれか一つの形に書けます。$3$ の倍数でないのは後の 2 つの場合です。 $n = 3m+1$ のとき $$ n^2 = 9m^2 + 6m + 1 = 3(3m^2 + 2m) + 1 $$ となり、$3$ で割った余りは $1$ です。 $n = 3m+2$ のとき $$ n^2 = 9m^2 + 12m + 4 = 3(3m^2 + 4m + 1) + 1 $$ となり、やはり余りは $1$ です。 いずれの場合も $n^2$ は $3$ の倍数ではありません。 よりもとの主張が従います。 **(2)** $x^2 = 3$ なる有理数 $x$ が存在すると仮定します。 により、整数 $p$ と自然数 $q$ で $x = p/q$ かつ $\gcd(p,q) = 1$ なるものが取れます。両辺を $2$ 乗して $q^2$ を掛けると $p^2 = 3q^2$ です。 右辺は $3$ の倍数なので $p^2$ は $3$ の倍数、(1) より $p$ は $3$ の倍数で、$p = 3r$（$r$ は整数）と書けます。代入して $9r^2 = 3q^2$、両辺を $3$ で割って $q^2 = 3r^2$ を得ます。右辺は $3$ の倍数なので $q^2$ も $3$ の倍数、再び (1) より $q$ も $3$ の倍数です。 すると $\gcd(p,q) \ge 3$ となり、$\gcd(p,q) = 1$ に矛盾します。よってそのような有理数は存在しません。 **(3)** (1) にあたる主張は「$n^2$ が $4$ の倍数ならば $n$ は $4$ の倍数」ですが、これは偽です。$n = 2$ が反例で、$n^2 = 4$ は $4$ の倍数ですが $n = 2$ は $4$ の倍数ではありません。したがって $p^2 = 4q^2$ から「$p$ は $4$ の倍数」を導く段階で議論が止まります。 止まって当然です。$x = 2$ は $x^2 = 4$ を満たす有理数なので、示そうとしている結論自体が偽だからです。 の言葉でいえば、$4 = 2^2$ は平方数だということです。証明が通らないときは、まず結論が本当に正しいかを疑ってください。 $\log_2 3$ が無理数であることを示せ。ここで $\log_2 3$ は $2^x = 3$ を満たす実数 $x$ である。 $x = \log_2 3$ とおきます。$2^0 = 1 < 3$ であり $t \mapsto 2^t$ は狭義単調増加なので $x > 0$ です。 $x$ が有理数だと仮定します（背理法）。$x > 0$ なので、 の表示で分子分母の符号をそろえれば、自然数 $p, q$ を用いて $x = p/q$ と書けます。すると $2^{p/q} = 3$ であり、両辺を $q$ 乗して $$ 2^p = 3^q $$ を得ます。 左辺について。$p \ge 1$ なので $2^p = 2 \cdot 2^{p-1}$ であり、$2^{p-1}$ は整数ですから $2^p$ は偶数です。 右辺について。$3^q$ が奇数であることを $q$ に関する帰納法で示します。$q = 1$ のとき $3^1 = 3 = 2\cdot 1 + 1$ は奇数です。$3^q$ が奇数、つまり $3^q = 2m+1$（$m$ は整数）と仮定すると $$ 3^{q+1} = 3(2m+1) = 6m + 3 = 2(3m+1) + 1 $$ となり奇数です。 よりすべての $q \in \mathbb{N}$ で $3^q$ は奇数です。 こうして同じ整数 $2^p = 3^q$ が偶数かつ奇数になりますが、§7.1 で見たとおりそのような整数は存在しません。矛盾です。 したがって $\log_2 3$ は無理数です。 この証明は素因数分解の一意性を使っていない点が特徴です。$2^p = 3^q$ の両辺を偶奇だけで区別できたので、それ以上の道具が要りませんでした。使う道具は少ないほどよく、どこまで軽い道具で足りるかを見積もるのも証明の技術のうちです。 ## 参考文献 - 松坂和夫『集合・位相入門』岩波書店、1968 — 自然数の構成、ペアノの公理、数学的帰納法の扱い。 - 高木貞治『初等整数論講義 第 2 版』共立出版、1971 — 第 1 章（整数の除法、素数、素因数分解の一意性）。 - G. ポリア『いかにして問題をとくか』柿内賢信訳、丸善、1954 — 「帰納と数学的帰納法」の項。帰納法を使う前の「推測の作り方」について。 - G. H. Hardy and E. M. Wright, *An Introduction to the Theory of Numbers*, Oxford University Press — Chapter IV「Irrational Numbers」。平方根の無理性の各種証明。 - ユークリッド『ユークリッド原論』中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵 訳・解説、共立出版 — 第 IX 巻 命題 20（素数が無限に存在すること）。 - 前原昭二『数学基礎論入門』朝倉書店、1977 — 古典論理と直観主義論理の違い、二重否定除去と排中律の位置づけ。