証明の技術：数学的帰納法と背理法はなぜ正しいのか、不変量の原理

0. この記事の要点

「1 から $n$ までの和の公式は、どの $n$ でも正しい」と言い切るには、$n$ を一つずつ確かめるだけでは終わりません。この記事は、無限にある場合を有限の紙で押さえる「数学的帰納法」と、「そうだとしたら変だ」と言って示す「背理法」が、なぜ正しい証明として通用するのかを順に確かめます。読み終えると、誤った帰納法を見抜けるようになり、$\sqrt2$ が分数で書けないことを自分で証明できるようになります。

• 数学的帰納法の帰納ステップが証明しているのは「$P(n)$ が正しい」ではなく「$P(n)$ ならば $P(n+1)$」という含意です。ここを取り違えると、帰納法は循環論法に見えてしまいます。
• 帰納法の正しさは自然数の整列性から従い、逆に整列性も帰納法から従います。ペアノの公理系では帰納法は第 5 公理、つまり自然数の定義の一部です。証明すべき定理なのか、置くべき公理なのかは、どこから出発するかの問題です。
• 基底ステップを落とすと、帰納ステップが完璧でも結論はすべて偽になりえます。逆に「すべての馬は同じ色」の誤証明では、基底は正しく、帰納ステップが $n = 1$ でだけ破れています。
• 背理法は「$\lnot P$ を仮定して何らかの矛盾を導く」、対偶証明は「$\lnot Q$ を仮定して $\lnot P$ を導く」。後者は前者の特殊な形であり、書き直せるなら対偶で書いたほうが読みやすくなります。
• $x^2 = 2$ を満たす有理数が存在しないことは、既約分数を使う証明と無限降下法による証明の二通りで示せます。後者は整列性、つまり帰納法を裏返した形をそのまま使います。
• 操作をくり返しても変わらない量（不変量）が違えば到達できず、操作のたびに必ず減る量（単調量）があれば必ず止まる、という不変量の原理（§8）は、盤面の敷き詰めや互除法の正しさを一行で示す証明の型です。

この記事で使う事前知識

• 含意: 「$P$ ならば $Q$」という形の主張。$P$ が偽なら、$Q$ が何であっても真とみなす。→ 論理結合子
• 量化子: 「すべての」「ある」を表す記号 $\forall$, $\exists$。→ 数学の国語
• 部分集合: ある集合の中から一部の元を集めてできる集合。→ 部分集合
• 順序体: 足し算・掛け算と大小関係が自然にそろった数の集まり。有理数や実数がその例。→ 順序体
• 単射と最大公約数: 単射は、異なる元を異なる元へ送る写像。最大公約数 $\gcd(p,q)$ は、$p$ と $q$ を両方割り切る最大の自然数。

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}$ が 順序体（定義 2.1）［数とは何か］ であること）については 数とは何か？ を、論理記号の扱い（論理結合子（定義 2.3）［数学の国語］ や量化子）については 数学の国語 - 集合と論理 を参照してください。

命題 $P$ と $Q$ に対し、$P \Rightarrow Q$（「$P$ ならば $Q$」）の真偽は次の表で定めます。とくに、$P$ が偽であれば $Q$ の真偽によらず $P \Rightarrow Q$ は真です。この規約は後で何度も効いてきます。

定義 2.1（逆・裏・対偶）↗

命題 $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. 数学的帰納法とその正しさ

自然数の集合には、実数や有理数にはない次の性質があります。

公理 3.1（整列性）↗

$\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$ はより小さい正の有理数だからです。「これ以上小さくできない」が保証されるのは、自然数が離散的に並んでいることの帰結です。

定理 3.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)$ は真である。

証明（定理 3.2）

反例の集合

$$S = \{\, n \in \mathbb{N} : P(n) \text{ は偽} \,\}$$

を考えます。示したい結論は $S = \emptyset$ にほかなりません。

そこで $S \ne \emptyset$ と仮定します（ここで背理法を使います。背理法の正当化は 命題 6.2 で行いますが、ここでは既知の論理として使わせてください）。$S$ は $\mathbb{N}$ の空でない部分集合ですから、整列性（公理 3.1） により最小元 $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)$ は真です。

∎

基底ステップが 1 枚目を倒し、帰納ステップが隣へ伝える

注意 3.3（なぜ循環論法ではないのか）

帰納法にはじめて触れた人がほぼ必ず抱く疑問は、「$P(n)$ を仮定して $P(n+1)$ を示すのなら、示したいことを仮定していることにならないか」というものです。

なりません。帰納ステップで証明しているのは $P(n)$ ではなく、$P(n) \Rightarrow P(n+1)$ という含意だからです。この含意は、$P(n)$ が偽である場合には §2 の真理値表によって自動的に真になります。つまり帰納ステップだけを証明しても、$P$ が真である $n$ が一つでも存在することは保証されません。実際 例 5.1 は、帰納ステップが完全に正しいのにすべての $n$ で $P(n)$ が偽である例です。

「$P(n)$ を仮定する」という言い回しは、「もし $P(n)$ が真である世界にいるならば」という条件付きの議論の合図であって、$P(n)$ を認めているわけではありません。

例 3.4（1 から 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)$ が成り立ちます。

定理 3.2 により、すべての $n$ で $P(n)$ が成り立ちます。

例 3.5（ベルヌーイの不等式と、仮定を落としたときの反例）

$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. ペアノの公理：帰納法は定理か公理か

定理 3.2 は整列性から証明されました。では整列性はどこから来るのでしょうか。実は整列性も帰納法から証明できます。両者は同値な性質であり、どちらか一方を自然数の性質として認めれば他方が従います。

そうすると「自然数とは何か」という問いに戻らざるをえません。19 世紀末にペアノが与えた答えが次の公理系です。$s(n)$ は $n$ の後者（次の数）を表します。

公理 4.1（ペアノの公理）↗

集合 $\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 公理は 定理 3.2 そのものです。$S$ として「$P(n)$ が真であるような $n$ の集合」を取れば、条件は基底ステップと帰納ステップに、結論は「すべての $n$ で $P(n)$」に翻訳されます。つまりペアノの立場では、帰納法は証明すべき定理ではなく、自然数がどういうものかを定める規定の一部です。

なお、ペアノ自身の 1889 年の原論文では出発点の数は $1$ でした。今日の教科書では $0$ から始める流儀が多く、どちらでも理論は同じように展開できます。

次の注は、5 つの公理がそれぞれ何のために置かれているかを、「その公理だけを外した例」で確かめるものです。公理 3 の例は 3 個だけの輪、公理 5 の例は、普通の自然数の列とは別に、整数のように両側へ延びる列がもう一本ついたもの、と思って読んでください。

注意 4.2（どの公理が何を担っているか）

公理を一つ落とすと何が壊れるかを見ると、各公理の役割がわかります。

公理 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$ を繰り返して届く範囲より外に余計な元はない」という要請なのです。

この「余計な元がついた自然数」は非標準モデルと呼ばれ、形式的な体系が意図した対象を一意に定めきれるかという問題につながります。この方向の話題は 数学基礎論への招待 - 不完全性定理、とくに 例 5.4［ゲーデルの不完全性定理］ を参照してください。

定理 4.3（完全帰納法）✓

各 $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)$ は真である。

証明（定理 4.3）

$Q(n)$ を「$n$ 以下のすべての $k \in \mathbb{N}$ について $P(k)$ が真である」という命題とし、$Q$ に 定理 3.2 を適用します。

基底ステップ。 仮定を $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)$ が成り立ちます。

定理 3.2 により、すべての $n$ で $Q(n)$ が真です。とくに $P(n)$ が真です。

∎

証明中の「空虚に真」とは、調べる対象が一つもないので、条件を破る例が出てきようがない、ということです。たとえば「$1$ より小さいすべての自然数は偶数である」は、$1$ より小さい自然数がそもそもないので、反例を挙げられず真と扱います。

ヒント

完全帰納法には基底ステップが書かれていないように見えますが、消えたわけではありません。上の証明が示すとおり、$n = 1$ の場合が「前提が空虚に真」という形で帰納ステップの中に吸収されています。実際に完全帰納法を使うときは、$n = 1$ で本当に議論が通るかを必ず確認してください。ここを飛ばすのが完全帰納法でいちばん多い誤りです。

例 4.4（素因数分解の存在）

$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)$ が成り立つので、定理 4.3 よりすべての $n$ で $P(n)$ が真です。

ここで通常の帰納法が使えないことに注意してください。$n$ の分解 $n = ab$ に現れる $a, b$ は $n-1$ とは限らず、$2$ から $n-1$ のどこに現れるか予測できません。「一つ前」ではなく「それより小さいものすべて」を仮定できることが、完全帰納法の値打ちです。

5. 帰納法が壊れるとき

5.1. 基底ステップを忘れる

例 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$」であり偽です。例 3.4 によって正しい和は $n(n+1)/2$ ですから、$P(n)$ はすべての $n$ で偽です。

倒れる仕組みだけが整っていて、最初の 1 枚を倒す人がいないドミノ列——それが基底ステップを欠いた帰納法です。注意 3.3 で述べたとおり、帰納ステップは含意しか主張していないので、単独では何も生みません。

5.2. 帰納ステップに穴がある

例 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. 数値実験は証明ではない

注意 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$ と分解して見せました。

次のコードで両方を確かめられます。

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. 対偶証明

命題 6.1（対偶の同値性）✓

任意の命題 $P, Q$ について、$P \Rightarrow Q$ が真であることと、その対偶 $\lnot Q \Rightarrow \lnot P$ が真であることは同値である。

証明（命題 6.1）

§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$ の向きで二重否定除去を使ったことに注意してください。「対偶を示せばもとの命題が示せる」という、実際に使うほうの向きこそが、古典論理に固有の規則に依存しています。

二重否定除去とは、「$Q$ でない、ということはない」と分かったら「$Q$ である」と結論してよい、という規則です。真理値表では $Q$ は真か偽のどちらかと決めてあるので当たり前に見えますが、証明の中で「何を根拠に使ってよいか」を数えるときには、独立した一つの規則として数えます。この規則を認めない論理の流儀もあり、§6.3 の注で触れます。

6.2. 背理法

命題 6.2（背理法の正当性）✓

命題 $P$ について、$\lnot P$ を仮定するとある命題 $R$ に対して $R$ と $\lnot R$ の両方が導かれるならば、$P$ は真である。

証明（命題 6.2）

仮定は $\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 \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$ と決まっている対偶証明のほうが、議論の行き先がはっきりします。

注意 6.3（どこまでが古典論理に固有か）

「$P$ を仮定して矛盾を導き、$\lnot P$ を結論する」のは、否定という記号の意味そのものであり、直観主義論理でも認められます。古典論理に固有なのは、その裏返し、つまり「$\lnot P$ を仮定して矛盾を導き、$P$ を結論する」ほうです。ここで使う $\lnot\lnot P \Rightarrow P$ は、直観主義論理では証明できません。

この違いは「存在する」を主張するときに表面化します。「$x$ が存在しないと矛盾する」から「$x$ が存在する」を導く証明は、その $x$ を一つも作ってくれません。具体的な作り方まで与える証明を構成的証明と呼び、区別します。無限集合の大小を比べるカントールの対角線論法も、形の上では背理法ですが、実際には「与えられた列に入らない元を作る手続き」を与えている点で構成的です。詳しくは 濃度と無限 - 無限にも大小がある、とくに 定理 6.3［濃度と無限］ を参照してください。

注意 6.4（背理法で書かなくてよいものを背理法で書かない）

「素数は無限に存在する」は背理法の例として紹介されることが多い命題です。背理法版はこうなります。素数が有限個 $p_1, \ldots, p_r$ しかないと仮定し、$N = p_1 p_2 \cdots p_r + 1$ を考えます。$N \ge 2$ なので 例 4.4 より $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. 準備

定義 7.1（有理数と無理数）↗

実数 $x$ が有理数であるとは、整数 $p$ と $0$ でない整数 $q$ を用いて $x = p/q$ と書けることをいう。有理数全体を $\mathbb{Q}$ と書く。実数であって有理数でないものを無理数という。

定義 7.2（偶数と奇数）↗

整数 $n$ が偶数であるとは、ある整数 $m$ を用いて $n = 2m$ と書けることをいう。$n$ が奇数であるとは、ある整数 $m$ を用いて $n = 2m+1$ と書けることをいう。

任意の整数は偶数か奇数のいずれか一方であり、両方であることはありません。前半は $2$ による除法の定理（余りが $0$ か $1$）から、後半は $2m = 2m'+1$ から $2(m-m') = 1$ となり、左辺が偶数で右辺が $2$ で割り切れないことから従います。

補題 7.3（既約分数表示の存在）✓

任意の有理数 $x$ に対し、整数 $p$ と自然数 $q$ で、$x = p/q$ かつ $\gcd(p, q) = 1$ を満たすものが存在する。

証明（補題 7.3）

定義 7.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$ です。整列性（公理 3.1） により $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$）。有理数を「整数の組を適切な同値関係で割ったもの」として定義する立場については 関係と同値関係 - 「同じ」とは何か、とくに 命題 6.1［関係と同値関係］ を参照してください。上の補題は、その同値類の中に「分母が最小の代表元」が必ずあると言っています。

補題 7.4（平方が偶数なら元も偶数）✓

整数 $n$ について、$n^2$ が偶数ならば $n$ は偶数である。

証明（補題 7.4）

対偶「$n$ が奇数ならば $n^2$ は奇数である」を示します。命題 6.1 により、これでもとの主張が従います。

$n$ を奇数とすると、定義 7.2 よりある整数 $m$ で $n = 2m+1$ と書けます。このとき

$$n^2 = (2m+1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1 .$$

$2m^2 + 2m$ は整数なので、$n^2$ は 定義 7.2 の意味で奇数です。

∎

この補題を直接示そうとすると難儀します。「$n^2 = 2k$」という等式から $n$ の形を取り出すには、素因数分解のような重い道具が要るからです。対偶を取ると、仮定される側が「$n = 2m+1$」という形の情報に変わり、あとは展開するだけで済みます。仮定と結論のうち、形の情報を持っているのがどちらかを見て、それを仮定側に回す——これが対偶証明を使う判断基準です。

7.2. 証明

定理 7.5（平方根 2 の無理性）✓

$x^2 = 2$ を満たす有理数 $x$ は存在しない。したがって、実数として $\sqrt2$（$\sqrt2 > 0$ かつ $(\sqrt2)^2 = 2$ を満たす実数）が存在するならば、それは無理数である。

証明（定理 7.5）

$x^2 = 2$ を満たす有理数 $x$ が存在すると仮定します（背理法）。

補題 7.3 により、整数 $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{整数})$ の形なので、定義 7.2 より $p^2$ は偶数です。補題 7.4 により $p$ は偶数であり、ある整数 $r$ で $p = 2r$ と書けます。

これを (A) に代入すると $4r^2 = 2q^2$、両辺を $2$ で割って

$$q^2 = 2 r^2$$

を得ます。右辺はやはり $2 \times (\text{整数})$ の形なので $q^2$ は偶数です。ふたたび 補題 7.4 により $q$ も偶数です。

こうして $p$ と $q$ はともに $2$ で割り切れることになり、$\gcd(p, q) \ge 2$ です。これは $\gcd(p,q) = 1$ に矛盾します。

したがって $x^2 = 2$ を満たす有理数は存在しません。

∎

どこで何を使ったかを整理しておきます。

• 「既約分数に取れる」ことは 補題 7.3、その根拠は 整列性（公理 3.1） です。
• 「$p^2$ が偶数なら $p$ が偶数」は 補題 7.4、これは対偶証明でした。
• 最後の一撃、既約性との衝突が背理法の部分です。

定理の主張を「$\sqrt2$ は無理数である」ではなく「$x^2 = 2$ なる有理数は存在しない」の形で述べたのには理由があります。前者を主張するには、まず $\sqrt2$ という実数の存在（定理 5.6［数とは何か］）を知っていなければなりません。その存在は実数の連続性（完備性、上限性質（公理 5.1）［数とは何か］）に依存する、有理数だけの世界では言えない事実です。ここで証明したのは有理数の世界の中で完結する主張であり、実数の性質を一切使っていません。

7.3. 無限降下法による別証明

例 7.6（既約性を使わない証明）

$p^2 = 2q^2$ を満たす自然数の組 $(p, q)$ が存在すると仮定します。そこで

$$U = \{\, p \in \mathbb{N} : \text{ある } q \in \mathbb{N} \text{ が存在して } p^2 = 2q^2 \,\}$$

とおくと $U \ne \emptyset$ です。整列性（公理 3.1） により $U$ は最小元 $p_0$ をもちます。$p_0$ に対応する $q_0 \in \mathbb{N}$ を一つ取ると $p_0^2 = 2q_0^2$ です。

定理 7.5 の証明と同じ計算で、$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$ の符号を調整して自然数の組が作れるからです）。

この形の議論を無限降下法といいます。「解があるとすれば、そこからより小さい解が作れる。しかし正の整数は無限に小さくなり続けられない」という論法で、フェルマーが好んで用いました。

注目してほしいのは、ここで使った道具が 整列性（公理 3.1） だけだという点です。整列性は 定理 3.2 の証明でも使われました。**数学的帰納法と無限降下法は、同じ「自然数は下に無限に続かない」という性質の表と裏です。**帰納法は下から積み上げ、降下法は上から降りてきて底がないことに矛盾する——向きが違うだけで、根は一つです。

7.4. 一般化

系 7.7（平方数でない自然数の平方根）✓

自然数 $n$ が平方数でない（すなわち $n = m^2$ を満たす自然数 $m$ が存在しない）ならば、$x^2 = n$ を満たす有理数 $x$ は存在しない。

次の証明の方針は、各素数 $\ell$ が $n$ に何回含まれるかを数え、$n$ が $x^2 = n$ の形のときはどの素数についてもその回数が偶数になることを見る、というものです。そのため、素数 $\ell$ で何回割り切れるかを表す記号 $v_\ell$ を導入します。

証明（系 7.7）

素因数分解の存在と一意性（算術の基本定理、定理 5.2［整除と素因数分解］）を使います。

素数 $\ell$ と $0$ でない整数 $a$ に対し、$\ell^{e}$ が $a$ を割り切るような最大の $e \ge 0$ を $v_\ell(a)$ と書きます。素因数分解の一意性から（命題 5.3［整除と素因数分解］ の 1 を $|a|, |b|$ に適用）、$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$ に対してまねしようとすると、補題 7.4 にあたる主張が偽になって議論が止まります（演習 9.4 の (3) を参照してください）。

8. 不変量の原理と単調量

帰納法・背理法に並ぶもう一つの基本的な証明の型が、「操作をくり返しても変わらない量（不変量）」と「操作のたびに必ず減る量（単調量）」を見つけることです。前者は「そこには到達できない」ことを、後者は「必ず止まる」ことを示します。

たとえば盤面にドミノを置いていく、黒板の数を書き換えていく、といった「一歩ずつ状態が変わっていく状況」を、「状態」と「操作」という言葉で一般的に書いたものが次の定義です。状態の間の「1 回の操作で移れる」という関係は、二項関係の一つです。まず具体例を先に見たい場合は、定義を飛ばして例（盤面の敷き詰め）から読んでも構いません。

定義 8.1（状態遷移・不変量・単調量）↗

集合 $X$（状態の全体）と、$X$ 上の二項関係 $x\to x'$（1 回の操作で $x$ から $x'$ に移れる）を考える。有限回の操作で $x$ から $x'$ に移れること（$n\ge0$ 回の連鎖 $x=x_0\to x_1\to\cdots\to x_n=x'$ があること）を $x\to^*x'$ と書き、$x'$ は $x$ から到達可能という。関数 $I:X\to Y$ が不変量であるとは、$x\to x'$ ならば $I(x)=I(x')$ であることをいう。関数 $V:X\to\mathbb{N}_0$ が単調量であるとは、$x\to x'$ ならば $V(x')<V(x)$ であることをいう。

定理 8.2（不変量の原理）✓

1. $I$ が不変量で $x\to^*x'$ ならば $I(x)=I(x')$ である。したがって $I(a)\ne I(b)$ なら、$b$ は $a$ から到達できない。
2. $V$ が単調量ならば、操作を無限にくり返せる状態列 $x_0\to x_1\to x_2\to\cdots$ は存在しない。とくに、$x_0$ から始めて操作を続けると、必ず $V(x_0)$ 回以内に、これ以上操作できない状態に行き着く。

証明（定理 8.2）

1: 連鎖の長さ $n$ についての帰納法です。$n=0$ は自明で、$n\ge1$ では $I(x_0)=I(x_{n-1})$（帰納法の仮定）と $I(x_{n-1})=I(x_n)$（不変量の定義）をつなぎます。

2: 無限の列があるとすると、$S=\{V(x_n):n\ge0\}\subseteq\mathbb{N}_0$ は空でなく、整列性（公理 3.1、$\mathbb{N}_0$ でも同じ）により最小元 $V(x_m)$ をもちます。しかし $V(x_{m+1})<V(x_m)$ で $V(x_{m+1})\in S$ となり、最小性に反します。後半：$V$ は 1 回の操作ごとに少なくとも 1 減るので、$V(x_0)$ 回を超えて操作を続けると $V<0$ となってしまい、それ以前に操作できなくなります。

∎

不変量が示せるのは「到達できない」ことだけで、$I(a)=I(b)$ だからといって $b$ に到達できるとは限りません。「到達できる」ことの証明には、実際に操作の列を構成する必要があります。

例 8.3（対角の 2 隅を除いた盤面のドミノ敷き詰め）

$8\times8$ の盤面を市松模様に白黒に塗り、対角の 2 隅（同じ色、たとえば白）を除いた 62 マスを、$1\times2$ のドミノ 31 枚で隙間も重なりもなく敷き詰められるか。答えは「できない」です。状態を「すでにドミノで覆ったマスの集合」、操作を「ドミノを 1 枚置く」とし、$I=(\text{覆った黒マス数})-(\text{覆った白マス数})$ とします。ドミノは隣り合う 2 マスを覆うので黒 1・白 1 を覆い、$I$ は不変量で、空の盤面で $0$ です。ところが目標の状態では黒 $32$、白 $30$ で $I=2\ne0$ です。定理 8.2 の 1 により到達できません。

対角の 2 隅（点線の×）を除いた盤面。白マスは 30、黒マス（塗りつぶし）は 32 で、ドミノは白 1・黒 1 を覆うので、全部は覆えない

例 8.4（黒板の数の操作と偶奇）

黒板に $1,2,\dots,10$ が書かれていて、操作は「2 つの数 $a,b$ を消して $|a-b|$ を書く」です。9 回の操作の後に残る 1 つの数は奇数です。実際、書かれた数の総和の偶奇 $I$ は不変量です。$a+b$ が $|a-b|$ に変わると、総和の変化は $(a+b)-|a-b|=2\min(a,b)$ で偶数だからです。最初の総和は $55$（奇数）なので、最後の数は奇数で、とくに $0$ にはなりません。

例 8.5（隣り合う逆順の交換は必ず止まる）

実数の列 $a_1,\dots,a_n$ に、「$a_i>a_{i+1}$ となる隣り合う 2 項を入れ替える」という操作をくり返します。逆順対（$i<j$ かつ $a_i>a_j$ となる添字の組）の個数を $V$ とします。隣り合う項を入れ替えると、その 2 項の間の逆順対が 1 個解消され、他の対の大小関係は変わらないので $V$ はちょうど 1 減ります。したがって 定理 8.2 の 2 により、操作は有限回で止まり、止まった列は、どの隣り合う項も $a_i\le a_{i+1}$、つまり昇順です。ここから、バブルソートの操作回数が $n(n-1)/2$ 以下であることも分かります。

例 8.6（ユークリッドの互除法）

状態を整数の組 $(a,b)$（$a\ge b\ge0$、$a>0$）、操作を $b>0$ のときの $(a,b)\to(b,r)$（$a=qb+r$、$0\le r<b$）とします（$b=0$ の状態からは操作できません）。$a$ と $b$ の公約数は $b$ と $r=a-qb$ の公約数と一致するので、$\gcd$ は不変量です。$b\to r<b$ なので、2 番目の成分 $V(a,b)=b$ は単調量で、定理 8.2 により有限回で $(g,0)$ に行き着き、$g=\gcd(g,0)$ が最初の $\gcd(a,b)$ に等しい、というのが互除法の正しさの証明のすべてです。

9. 演習

演習 9.1標準

黒板に $1,2,\dots,10$ が書かれていて、操作は「2 つの数 $a,b$ を消して $a+b+ab$ を書く」です。最後に残る数は、操作の順序によらずに決まることを示し、その値を求めよ。

解答

$a+b+ab+1=(a+1)(b+1)$ なので、黒板の数 $x_i$ について $I=\prod_i(x_i+1)$ は不変量です。最初は $I=2\cdot3\cdots11=11!$ です。最後の 1 つの数 $x$ では $x+1=11!$、したがって $x=11!-1=39916799$ で、操作の順序によりません。

演習 9.2易

$a, b$ を実数とする。$a + b \ge 2$ ならば、$a \ge 1$ または $b \ge 1$ であることを示せ。

解答

対偶を示します。「$a \ge 1$ または $b \ge 1$」の否定は、ド・モルガンの法則（補題 4.3）［数学の国語］ により「$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$ が従います。

命題 6.1 により、もとの主張が成り立ちます。

この問題を直接証明しようとすると、「$a + b \ge 2$」から $a$ と $b$ のどちらが $1$ 以上かを選ばねばならず、場合分けが必要になります。否定を取ると結論の「または」が仮定の「かつ」に変わり、$a$ と $b$ の両方の情報を同時に使えるようになります。結論が「または」の形をしているときは対偶を疑ってください。

演習 9.3標準

すべての $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$ の場合の主張が得られました。定理 3.2 より、すべての $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)$ を持っています。より強い主張のほうが帰納法では証明しやすいことがある——これを帰納法の仮定を強めるといい、帰納法を使う際の基本的な技術です。

演習 9.4標準

(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$ の倍数ではありません。命題 6.1 よりもとの主張が従います。

(2) $x^2 = 3$ なる有理数 $x$ が存在すると仮定します。補題 7.3 により、整数 $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$ を満たす有理数なので、示そうとしている結論自体が偽だからです。系 7.7 の言葉でいえば、$4 = 2^2$ は平方数だということです。証明が通らないときは、まず結論が本当に正しいかを疑ってください。

演習 9.5難

$\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$ なので、定義 7.1 の表示で分子分母の符号をそろえれば、自然数 $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$$

となり奇数です。定理 3.2 よりすべての $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 — 古典論理と直観主義論理の違い、二重否定除去と排中律の位置づけ。