命題と論理

この章の目標

• 命題と論理結合子の意味を真理値表で説明でき、「ならば」が前提が偽のときに真となる理由を理解する
• 量化子 $\forall$, $\exists$ を含む命題を正しく読み書きし、量化子の順序による意味の違いを説明できる
• 量化子を含む命題の否定を機械的に作れる
• 直接証明・対偶・背理法・場合分け・数学的帰納法・存在証明・反例を使い分けられる
• 「何を仮定し、何を示せば終わりか」を意識して証明を書き、答案の誤りを自分で見つけられる

前提：高校数学（「集合と命題」「数学的帰納法」を一度学んでいれば十分）

高校までの数学では、計算して答えを出すことが中心であった。大学の数学では主役が証明 (proof) に移る。証明とは、仮定・定義・すでに正しいとわかっている事実から、誰が読んでも納得せざるをえない手順で結論を導く文章である。そのためには「かつ」「または」「ならば」「すべての」「ある」といった日常語を、日常よりずっと厳密な意味で使わなければならない。本章ではこの「数学の言葉」の文法を整理し、それを使って証明を書く練習をする。

本章の内容は後のすべての科目で毎日のように使う。特に 1.5 節と 1.6 節の量化子の扱いは、微分積分学 の $\varepsilon$-$\delta$ 論法をはじめ、あらゆる分野の定義を読むための鍵になる。

1.1 命題

数学の文章は「〜である」という主張の積み重ねである。まず、どのような主張を扱うのかをはっきりさせる。

定義 1.1（命題, proposition）正しいか正しくないかが客観的に定まる主張を命題 (proposition) という。命題が正しいとき真 (true)、正しくないとき偽 (false) であるといい、真・偽を命題の真理値 (truth value) という。

例 1.2

• 「$2$ は素数である」は真の命題である。
• 「$3 > 5$」は偽の命題である。偽であっても命題である。
• 「$100$ は大きい数である」は、何を「大きい」とするかが決まっていないので命題ではない。
• 「$x^2 - 1 = 0$」は、$x$ が何であるかによって真偽が変わるので、このままでは命題ではない。$x$ に具体的な数を代入すると命題になる。このようなものを 1.4 節で条件と呼ぶ。

注意 1.3 真偽が「定まっている」ことと、真偽が「わかっている」ことは別である。「$4$ 以上のすべての偶数は $2$ つの素数の和で表せる」（ゴールドバッハ予想）は、本書執筆時点で真偽が知られていないが、真か偽のどちらか一方であることは決まっているので命題である。

1.2 論理結合子と真理値表

いくつかの命題を組み合わせて新しい命題を作る操作を考える。組み合わせた命題の真偽は、もとの命題の真偽だけから決まるように約束する。

定義 1.4（否定・連言・選言）$P, Q$ を命題とする。

• 否定 (negation) $\neg P$（「$P$ でない」）は、$P$ が偽のとき真、$P$ が真のとき偽である命題である。
• 連言 (conjunction) $P \land Q$（「$P$ かつ $Q$」）は、$P$ と $Q$ がともに真のときだけ真である命題である。
• 選言 (disjunction) $P \lor Q$（「$P$ または $Q$」）は、$P$ と $Q$ の少なくとも一方が真のとき真である命題である。

$\neg, \land, \lor$ や後で導入する $\Rightarrow, \Leftrightarrow$ を論理結合子 (logical connective) という。記号は順に「ノット」「アンド」「オア」と読む。本によっては否定を $\overline{P}$ と書くこともある。真偽のすべての組合せを表にしたものを真理値表 (truth table) という。以下 T は真、F は偽を表す。

注意 1.5（「または」は両方でもよい）数学の「$P$ または $Q$」は、$P$ と $Q$ がともに真である場合も含む。日常語の「コーヒーまたは紅茶がつきます」はどちらか一方だけを意味することが多いが、数学ではそうではない。たとえば実数 $x$ について「$x \geq 0$ または $x \leq 0$」は $x = 0$ のときも真である。

定義 1.6（論理的同値・恒真式）命題 $P, Q, R, \dots$ を論理結合子で組み合わせた二つの式 $A, B$ が、$P, Q, R, \dots$ の真理値のすべての組合せに対して同じ真理値をとるとき、$A$ と $B$ は論理的に同値 (logically equivalent) であるといい、$A \equiv B$ と書く。どの組合せに対しても真になる式を恒真式 (tautology) という。

定理 1.7（論理の基本法則）命題 $P, Q, R$ について次が成り立つ。

1. （二重否定）$\neg(\neg P) \equiv P$
2. （交換法則）$P \land Q \equiv Q \land P$、$P \lor Q \equiv Q \lor P$
3. （結合法則）$(P \land Q) \land R \equiv P \land (Q \land R)$、$(P \lor Q) \lor R \equiv P \lor (Q \lor R)$
4. （分配法則）$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$、$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$
5. （ド・モルガンの法則, De Morgan's laws）$\neg(P \land Q) \equiv \neg P \lor \neg Q$、$\neg(P \lor Q) \equiv \neg P \land \neg Q$
6. （排中律）$P \lor \neg P$ は恒真式である。

証明. どれも真理値表を書けば確かめられる。ド・モルガンの法則の前半を示す。

第 4 列と第 7 列が一致するので $\neg(P \land Q) \equiv \neg P \lor \neg Q$ である。後半は、前半を $\neg P, \neg Q$ に適用して二重否定を使うと $\neg(\neg P \land \neg Q) \equiv P \lor Q$ となり、両辺を否定すれば得られる。分配法則は $P, Q, R$ の真理値の組合せ 8 通りを調べればよい（問題 1.1）。残りも同様である。$\square$

例 1.8 実数 $x, y$ についての「$x > 0$ かつ $y > 0$」の否定は、ド・モルガンの法則により「$x \leq 0$ または $y \leq 0$」である。「$x \leq 0$ かつ $y \leq 0$」ではない。実際 $(x, y) = (1, -1)$ のとき、「$x > 0$ かつ $y > 0$」も「$x \leq 0$ かつ $y \leq 0$」もともに偽であり、一方が他方の否定になっていない。否定とは、どの場合にも真偽が逆になるものである。

1.3 「ならば」と「同値」

数学の定理のほとんどは「$P$ ならば $Q$」の形をしている。この「ならば」の真偽を次のように定める。

定義 1.9（含意, implication）命題 $P, Q$ に対し、「$P$ ならば $Q$」という命題を $P \Rightarrow Q$ と書き、$P$ が真で $Q$ が偽のときだけ偽、それ以外のときは真と定める。$P$ を仮定（前提, hypothesis）、$Q$ を結論 (conclusion) という。

下の 2 行、つまり「前提が偽ならば $P \Rightarrow Q$ は $Q$ の真偽によらず真」という約束は、はじめは奇妙に見える。二つの見方で納得しておこう。

一つ目は約束のたとえである。「晴れたら君を遊園地に連れて行く」と約束したとする。約束が破られたと言えるのは「晴れたのに連れて行かなかった」ときだけである。雨が降った日は、連れて行っても行かなくても約束を破ったことにはならない。$P \Rightarrow Q$ が真であるとは、「$P$ なのに $Q$ でない」ということが起こっていない、という意味なのである。

二つ目のほうが数学的には重要である。

例 1.10 「すべての実数 $x$ について、$x > 2$ ならば $x^2 > 4$」は、誰もが真と認めたい命題である。これは各実数 $x$ について $x > 2 \Rightarrow x^2 > 4$ が真であるという意味だから、いろいろな $x$ で調べてみる。

• $x = 3$：前提 $3 > 2$ は真、結論 $9 > 4$ も真。
• $x = -3$：前提は偽、結論 $9 > 4$ は真。
• $x = 0$：前提は偽、結論 $0 > 4$ も偽。

上の命題を真とするには、「偽 $\Rightarrow$ 真」も「偽 $\Rightarrow$ 偽」も真と約束しておくしかない。「前提が真なのに結論が偽」となる $x$ が一つもないこと、それがこの命題の内容そのものである。

このように、前提が偽であるために真となる含意を空虚な真 (vacuous truth) ということがある。単独で見ると「$1 = 2$ ならば私は月にいる」のように無意味に見えるが、「すべての $x$ について」と組み合わせたときに本領を発揮する。また、$P \Rightarrow Q$ は $P$ と $Q$ の間の因果関係を要求しない。「$2 + 2 = 4$ ならば $7$ は素数」も真の命題である。

定理 1.11 命題 $P, Q$ について次が成り立つ。

1. $P \Rightarrow Q \equiv \neg P \lor Q$
2. $\neg(P \Rightarrow Q) \equiv P \land \neg Q$

証明. (1) $\neg P \lor Q$ が偽になるのは $\neg P$ も $Q$ も偽のとき、つまり $P$ が真で $Q$ が偽のときだけである。これは $P \Rightarrow Q$ が偽になる場合と一致する。(2) (1) とド・モルガンの法則、二重否定より $\neg(\neg P \lor Q) \equiv \neg\neg P \land \neg Q \equiv P \land \neg Q$ である。$\square$

定義 1.12（同値・必要条件・十分条件）$(P \Rightarrow Q) \land (Q \Rightarrow P)$ を $P \Leftrightarrow Q$ と書き、「$P$ と $Q$ は同値 (equivalent) である」という。$P \Leftrightarrow Q$ は $P$ と $Q$ の真理値が一致するとき真である。$P \Rightarrow Q$ が真のとき、$P$ は $Q$ であるための十分条件 (sufficient condition)、$Q$ は $P$ であるための必要条件 (necessary condition) であるという。

英語の文献を読むときのために、読み方をまとめておく。

「$P$ only if $Q$」は「$Q$ のときに限って $P$」、つまり「$Q$ でなければ $P$ でない」という意味であり、$P \Rightarrow Q$ を表す。

定義 1.13（逆・裏・対偶）命題 $P \Rightarrow Q$ に対して、$Q \Rightarrow P$ を逆 (converse)、$\neg P \Rightarrow \neg Q$ を裏 (inverse)、$\neg Q \Rightarrow \neg P$ を対偶 (contrapositive) という。

定理 1.14 $P \Rightarrow Q$ とその対偶 $\neg Q \Rightarrow \neg P$ は論理的に同値である。逆と裏も互いに同値である。しかし $P \Rightarrow Q$ と逆 $Q \Rightarrow P$ は一般には同値でない。

証明. 定理 1.11 と二重否定・交換法則より

である。裏 $\neg P \Rightarrow \neg Q$ は逆 $Q \Rightarrow P$ の対偶なので、いま示したことから両者は同値である。最後に、$P$ が偽で $Q$ が真のとき、$P \Rightarrow Q$ は真だが $Q \Rightarrow P$ は偽なので、両者は同値でない。$\square$

例 1.15 実数 $x$ についての命題「$x = 1$ ならば $x^2 = 1$」は（すべての $x$ で）真である。その逆「$x^2 = 1$ ならば $x = 1$」と裏「$x \neq 1$ ならば $x^2 \neq 1$」は $x = -1$ で成り立たないので偽である。対偶「$x^2 \neq 1$ ならば $x \neq 1$」は真である。

1.4 条件と量化子

「$x^2 - 1 = 0$」は $x$ を決めるまで命題ではなかった。このような変数を含む主張と、それから命題を作る方法を考える。

定義 1.16（条件）変数 $x$ を含む主張で、$x$ に集合 $X$ の元を代入するごとに命題になるものを、$X$ 上の条件（述語, predicate）といい、$P(x)$ のように書く。変数が二つ以上ある条件 $P(x, y)$ なども同様である。

ここで「集合」は、ものの集まりという素朴な意味で使っている（正確な扱いは第2章）。たとえば $X = \mathbb{R}$ 上の条件 $P(x)$：「$x^2 - 1 = 0$」について、$P(1)$ は真、$P(2)$ は偽である。

定義 1.17（量化子, quantifier）$P(x)$ を集合 $X$ 上の条件とする。

• 「$X$ のすべての元 $x$ について $P(x)$ が成り立つ」という命題を $\forall x \in X,\ P(x)$ と書く。
• 「$P(x)$ を満たす $X$ の元 $x$ が（少なくとも一つ）存在する」という命題を $\exists x \in X,\ P(x)$ と書く。
• 「$P(x)$ を満たす $X$ の元 $x$ がただ一つ存在する」という命題を $\exists ! x \in X,\ P(x)$ と書く。

$\forall$ を全称量化子 (universal quantifier)、$\exists$ を存在量化子 (existential quantifier) という。

$\forall$ は All の A を、$\exists$ は Exists の E をひっくり返した記号である。$\forall x \in X,\ P(x)$ は「任意の $x \in X$ に対して $P(x)$」「すべての $x \in X$ について $P(x)$」と読み、$\exists x \in X,\ P(x)$ は「ある $x \in X$ が存在して $P(x)$」「$P(x)$ となる $x \in X$ が存在する」と読む。数学の「任意の」は「どれをとっても」という意味であり、日常語の「任意（自由意思）」とは異なる。

本によっては「$P(x) \ (\forall x \in X)$」のように量化子を後ろに書くこともあるが、量化子が複数あると順序が読みとりにくくなるので、本教材では量化子を常に前に書く。

例 1.18

1. $\forall x \in \mathbb{R},\ x^2 \geq 0$ は真である。
2. $\exists x \in \mathbb{R},\ x^2 = 2$ は真である（$x = \sqrt{2}$）。
3. $\exists x \in \mathbb{Q},\ x^2 = 2$ は偽である（定理 1.36）。量化する範囲が変わると真偽が変わりうる。
4. $\forall n \in \mathbb{N},\ n \geq 1$ は真、$\forall n \in \mathbb{Z},\ n \geq 1$ は偽である。
5. $\exists ! x \in \mathbb{R},\ x^3 = 8$ は真である（注意 1.41）。$\exists ! x \in \mathbb{R},\ x^2 = 4$ は偽である。解は存在するが二つある。

注意 1.19

1. （束縛変数）$\forall x \in X,\ P(x)$ の $x$ は、積分 $\int_0^1 f(x)\ dx$ の $x$ と同じく仮の名前であり、$\forall y \in X,\ P(y)$ と書いても同じ命題である。量化子で縛られた変数を束縛変数 (bound variable)、縛られていない変数を自由変数 (free variable) という。自由変数が残っているものは命題ではなく条件である。たとえば「$\exists y \in \mathbb{R},\ x = y^2$」は $x$ についての条件であり、「$x \geq 0$」と同じ意味である。
2. （範囲つき量化子の意味）$\forall x \in X,\ P(x)$ は「$\forall x,\ (x \in X \Rightarrow P(x))$」の、$\exists x \in X,\ P(x)$ は「$\exists x,\ (x \in X \land P(x))$」の略記である。$\exists$ のほうは「$\Rightarrow$」ではなく「$\land$」であることに注意する。
3. （空の範囲）$X$ が元を一つももたないとき、$\forall x \in X,\ P(x)$ は真（反例がないので）、$\exists x \in X,\ P(x)$ は偽である。前者は (2) の書き換えと空虚な真から理解できる。
4. $X = \lbrace a_1, \dots, a_n \rbrace$ が有限個の元からなるときは、$\forall x \in X,\ P(x)$ は $P(a_1) \land \cdots \land P(a_n)$、$\exists x \in X,\ P(x)$ は $P(a_1) \lor \cdots \lor P(a_n)$ と同じ意味である。量化子は「無限個の『かつ』『または』」だと思うこともできる。

1.5 量化子の順序

量化子が二つ以上並ぶと、その順序が決定的な意味をもつ。

例 1.20 実数上の条件「$x < y$」について、次の二つの命題を比べる。

• (a) $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ x < y$：「どんな実数 $x$ に対しても、それより大きい実数 $y$ がある」。これは真である（$y = x + 1$ とすればよい）。
• (b) $\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ x < y$：「ある実数 $y$ があって、それはすべての実数 $x$ より大きい」。これは偽である（どんな $y$ に対しても、$x = y$ とすると $x < y$ が成り立たない）。

(a) では $y$ を $x$ に応じて選んでよいが、(b) ではただ一つの $y$ ですべての $x$ に対応しなければならない。

量化子を含む命題は、証明者と反論者のゲームとして読むとわかりやすい。左から順に、$\forall$ のところでは反論者が、$\exists$ のところでは証明者が値を選び、最後の条件が成り立てば証明者の勝ちである。命題が真であるとは、反論者がどう選んでも証明者が勝てる（必勝法がある）ことをいう。(a) では反論者が先に $x$ を出し、証明者はそれを見てから $y = x + 1$ と答えればよい。(b) では証明者が先に $y$ を決めなければならず、反論者に $x = y$ と返されて負ける。後から選ぶ変数は、前に選ばれた変数に依存してよい、というのが要点である。

定理 1.21 $P(x, y)$ を $X, Y$ 上の条件とする。

$$\bigl( \exists y \in Y,\ \forall x \in X,\ P(x, y) \bigr) \Rightarrow \bigl( \forall x \in X,\ \exists y \in Y,\ P(x, y) \bigr)$$

は常に真である。一方、逆向きの含意は一般には成り立たない。なお、同じ種類の量化子どうしは入れ替えてよい：$\forall x \in X,\ \forall y \in Y,\ P(x, y)$ と $\forall y \in Y,\ \forall x \in X,\ P(x, y)$ は同値であり、$\exists$ についても同様である。

証明. 左辺を仮定し、$\forall x \in X,\ P(x, y_0)$ を満たす $y_0 \in Y$ を一つとる。$x \in X$ を任意にとると $P(x, y_0)$ が成り立つので、$y = y_0$ とすれば「$\exists y \in Y,\ P(x, y)$」が成り立つ。$x$ は任意だったから右辺が成り立つ。逆向きが成り立たない例は例 1.20 である。同じ種類の量化子の入れ替えは、「すべての組 $(x, y)$ について」「ある組 $(x, y)$ について」という意味から明らかである。$\square$

量化子の順序の違いが本質的に効いてくる典型例が、関数の連続性と一様連続性である。

定義 1.22（連続性と一様連続性）$I \subset \mathbb{R}$ を区間、$f\colon I \to \mathbb{R}$ を関数とする。

(1) $f$ が $I$ 上で連続 (continuous) であるとは、次が成り立つことをいう。

$$\forall a \in I,\ \forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in I,\ \bigl( \lvert x - a \rvert < \delta \Rightarrow \lvert f(x) - f(a) \rvert < \varepsilon \bigr)$$

(2) $f$ が $I$ 上で一様連続 (uniformly continuous) であるとは、次が成り立つことをいう。

$$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall a \in I,\ \forall x \in I,\ \bigl( \lvert x - a \rvert < \delta \Rightarrow \lvert f(x) - f(a) \rvert < \varepsilon \bigr)$$

ここで $\forall \varepsilon > 0$ は「$\varepsilon > 0$ を満たすすべての実数 $\varepsilon$ について」の略である。二つの定義の違いは「$\forall a \in I$」の位置だけである。連続性では $\delta$ は $\exists \delta$ より前にある $a$ と $\varepsilon$ の両方に依存してよいが、一様連続性では $\delta$ は $\varepsilon$ だけから決まり、$I$ のすべての点 $a$ で同じ $\delta$ が使える。定理 1.21 により一様連続ならば連続である。

例 1.23 $f(x) = x^2$ は $\mathbb{R}$ 上で連続である。実際、$a \in \mathbb{R}$ と $\varepsilon > 0$ を任意にとり、$\delta := \min \lbrace 1, \varepsilon / (2\lvert a \rvert + 1) \rbrace$ とおく。$\lvert x - a \rvert < \delta$ ならば $\lvert x + a \rvert \leq \lvert x - a \rvert + 2\lvert a \rvert < 1 + 2\lvert a \rvert$ なので

となる。この $\delta$ は $a$ に依存しており、$\lvert a \rvert$ が大きいほど小さくとらねばならない。グラフが遠くほど急になるからである。実際、どの $a$ でも通用する $\delta$ は存在せず、$f$ は一様連続でない（例 1.27）。一様連続性は微分積分学 第3章で詳しく扱う。

1.6 量化子を含む命題の否定

「収束しない」「一様連続でない」ことを証明するには、定義の否定を正確に書き下す必要がある。

定理 1.24（量化子の否定）$P(x)$ を集合 $X$ 上の条件とする。

$$\neg \bigl( \forall x \in X,\ P(x) \bigr) \equiv \exists x \in X,\ \neg P(x), \qquad \neg \bigl( \exists x \in X,\ P(x) \bigr) \equiv \forall x \in X,\ \neg P(x)$$

証明. 前者：「すべての $x$ で $P(x)$」が偽であることは、$P(x)$ が成り立たない $x$ が少なくとも一つあることにほかならない。後者：「$P(x)$ を満たす $x$ がある」が偽であることは、$P(x)$ を満たす $x$ が一つもない、つまりすべての $x$ で $\neg P(x)$ であることにほかならない。これらは $\forall, \exists$ の意味そのものであり、$X$ が有限集合のときはド・モルガンの法則（定理 1.7）の言いかえである（注意 1.19 (4)）。$\square$

この定理を繰り返し使うと、否定は次の手順で機械的に作れる。

1. 命題を「量化子の列、最後に条件」の形に書く。
2. $\forall$ と $\exists$ をすべて入れ替える。範囲の指定（「$\in X$」「$> 0$」など）はそのまま残す。
3. 最後の条件を否定し、定理 1.7・定理 1.11 で整理する。特に $\neg(P \Rightarrow Q) \equiv P \land \neg Q$、$\neg(a < b) \equiv a \geq b$ を使う。

手順 2 で範囲指定を変えない理由は注意 1.19 (2) にある。$\forall \varepsilon > 0,\ Q(\varepsilon)$ は $\forall \varepsilon,\ (\varepsilon > 0 \Rightarrow Q(\varepsilon))$ のことだから、その否定は $\exists \varepsilon,\ (\varepsilon > 0 \land \neg Q(\varepsilon))$、すなわち $\exists \varepsilon > 0,\ \neg Q(\varepsilon)$ である。「$\varepsilon \leq 0$」にはならない。

例 1.25（収束の否定）数列 $(a_n)$ が実数 $\alpha$ に収束する (converge) とは

が成り立つことである（微分積分学 第2章）。手順どおりに否定すると

となる。言葉にすれば「ある $\varepsilon > 0$ があって、どんなに先の番号 $N$ を指定しても、それ以降に $\alpha$ から $\varepsilon$ 以上離れた項が現れる」である。

例 1.26 $a_n = (-1)^n$ は $1$ に収束しない。否定の形に沿って証明する。$\varepsilon = 1$ とする。$N \in \mathbb{N}$ を任意にとり、$n := 2N + 1$ とおくと $n \geq N$ であり、$n$ は奇数なので $\lvert a_n - 1 \rvert = \lvert -1 - 1 \rvert = 2 \geq 1$ である。$\square$

証明の骨組み「$\varepsilon$ を具体的に選ぶ → $N$ を任意にとる → $n$ を（$N$ に応じて）具体的に選ぶ」が、否定の量化子の列 $\exists \varepsilon \ \forall N \ \exists n$ にそのまま対応していることに注意しよう。

例 1.27（例 1.23 の続き）$f(x) = x^2$ は $\mathbb{R}$ 上で一様連続でない。定義 1.22 (2) を否定すると

であるから、これを示す。$\varepsilon = 1$ とする。$\delta > 0$ を任意にとり、$a := 1/\delta$、$x := a + \delta/2$ とおく。すると $\lvert x - a \rvert = \delta/2 < \delta$ であり、

である。$\square$ ここで $a$ は $\delta$ に依存して選んでいる。$\exists a$ が $\forall \delta$ の後ろにあるので、これは許される。

1.7 証明の骨組み：何を仮定し、何を示すか

証明を書くときに最初に決めるべきことは、「何を仮定してよく、何を示せば終わりか」である。これは示したい命題の論理的な形だけから決まる。中身を考える前に、まず骨組みを書くとよい。

仮定として手元にある命題の使い方も、その形で決まる。

「任意にとった $x$」は、反論者が選んだ値である。証明者はその値について何も知らないので、$x$ について $x \in X$ 以外の性質を勝手に仮定してはならない。逆に「存在する」を示すときは、証明者が値を自由に選んでよい。

以下、整数 $n$ が偶数 (even) であるとは $n = 2k$ となる整数 $k$ が存在すること、奇数 (odd) であるとは $n = 2k + 1$ となる整数 $k$ が存在することと定める。どの整数も偶数か奇数のどちらか一方だけであること（2 で割った余りが一意に決まること）は既知とする。

例 1.28（骨組みを意識した証明）「任意の整数 $m, n$ について、$m$ と $n$ がともに奇数ならば $mn$ は奇数である」を示す。形は $\forall m \ \forall n \ (P \Rightarrow Q)$ であり、結論 $Q$ は「$\exists j \in \mathbb{Z},\ mn = 2j + 1$」という存在命題である。

証明. $m, n \in \mathbb{Z}$ を任意にとり、ともに奇数であると仮定する。奇数の定義より、$m = 2k + 1$、$n = 2l + 1$ を満たす整数 $k, l$ がとれる。このとき

である。$j := 2kl + k + l$ とおくと $j$ は整数であり $mn = 2j + 1$ となるから、$mn$ は奇数である。$\square$

「任意にとり」が $\forall$ に、「仮定する」が $\Rightarrow$ に、「とれる」が仮定の $\exists$ の使用に、「$j := \cdots$ とおく」が結論の $\exists$ の証明に対応している。$k$ と $l$ に別の文字を使ったことも重要である（1.9 節の添削 3）。

1.8 証明の技法

直接証明と対偶による証明

$P \Rightarrow Q$ を、$P$ から出発して $Q$ に到達することで示すのが直接証明 (direct proof) である。例 1.28 はその例である。直接証明が難しいときは、定理 1.14 により対偶 $\neg Q \Rightarrow \neg P$ を示してもよい。これを対偶による証明 (proof by contraposition) という。

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

証明. 対偶「$n$ が奇数ならば $n^2$ は奇数」を示せばよい。これは例 1.28 で $m = n$ とした場合である。$\square$

直接示そうとすると「$n^2 = 2k$ から $n = \sqrt{2k}$ が偶数」という見込みのない道に入る。「偶数である」という仮定より「奇数である」という仮定のほうが式にしやすいので、対偶が有効なのである。

場合分け

仮定が $P \lor Q$ の形のときや、考える対象がいくつかの種類に分かれるときは、場合分け (proof by cases) を使う。場合がすべてを尽くしていることを必ず確認する。

例 1.30 任意の整数 $n$ について、$n^2$ を $4$ で割った余りは $0$ か $1$ である。したがって $4k + 3$（$k \in \mathbb{Z}$）の形の整数は二つの整数の平方の和で表せない。

証明. $n$ は偶数か奇数である。偶数のとき $n = 2k$ と書けて $n^2 = 4k^2$、余りは $0$ である。奇数のとき $n = 2k + 1$ と書けて $n^2 = 4(k^2 + k) + 1$、余りは $1$ である。後半：$a^2 + b^2$ を $4$ で割った余りは、前半より $0 + 0$、$0 + 1$、$1 + 1$ のいずれかで $0, 1, 2$ のどれかになり、$3$ にはならない。$\square$

数学的帰納法と完全帰納法

自然数 $\mathbb{N} = \lbrace 1, 2, 3, \dots \rbrace$ 全体についての命題を示す基本的な道具が帰納法である。

定理 1.31（数学的帰納法, mathematical induction）$P(n)$ を $\mathbb{N}$ 上の条件とする。$P(1)$ が真であり、かつ、すべての $n \in \mathbb{N}$ について $P(n) \Rightarrow P(n + 1)$ が真ならば、すべての $n \in \mathbb{N}$ について $P(n)$ は真である。

これは自然数の最も基本的な性質であり、第7章では自然数を特徴づける公理（ペアノの公理）の一つとして採用する。ここでは証明せずに認めて使う。$P(1)$ の確認を基礎段階 (base case)、$P(n) \Rightarrow P(n+1)$ の証明を帰納段階 (inductive step) といい、帰納段階での仮定 $P(n)$ を帰納法の仮定 (induction hypothesis) という。

例 1.32（ベルヌーイの不等式）$h \geq -1$ を満たす実数 $h$ と $n \in \mathbb{N}$ について $(1 + h)^n \geq 1 + nh$ が成り立つ。

証明. $h \geq -1$ を固定し、$n$ についての帰納法で示す。$n = 1$ のとき両辺は $1 + h$ で等しい。ある $n$ で $(1 + h)^n \geq 1 + nh$ が成り立つと仮定する。$1 + h \geq 0$ なので、両辺に $1 + h$ を掛けても不等号の向きは変わらず

を得る。よって帰納法により、すべての $n \in \mathbb{N}$ で成り立つ。$\square$

仮定 $h \geq -1$ がどこで使われたか（不等式に $1 + h$ を掛けるところ）を確認しておこう。仮定をどこで使ったかを把握することは、証明を理解することの一部である。

注意 1.33 (1) 基礎段階を $n = n_0$ から始めれば、$n \geq n_0$ を満たすすべての整数 $n$ について示せる。(2) 基礎段階と帰納段階のどちらを欠いても証明にならない。たとえば $P(n)$：「$n = n + 1$」について、$P(n)$ を仮定すると両辺に $1$ を足して $P(n + 1)$ が得られるので帰納段階は正しいが、$P(1)$ が偽なので何も示されない（問題 1.9）。

$P(n+1)$ を示すのに $P(n)$ だけでなく、それより前のすべての $P(k)$ を使いたいことがある。

定理 1.34（完全帰納法, strong induction）$P(n)$ を $\mathbb{N}$ 上の条件とし、次を仮定する。

$$\forall n \in \mathbb{N},\ \Bigl[ \bigl( \forall k \in \mathbb{N},\ k < n \Rightarrow P(k) \bigr) \Rightarrow P(n) \Bigr]$$

このとき、すべての $n \in \mathbb{N}$ について $P(n)$ が成り立つ。

証明. 条件 $Q(n)$ を「$k \leq n$ を満たすすべての $k \in \mathbb{N}$ について $P(k)$」と定め、$Q(n)$ がすべての $n$ で成り立つことを通常の帰納法で示す。

$n = 1$ のとき：$k < 1$ を満たす自然数 $k$ は存在しないので、「$\forall k \in \mathbb{N},\ k < 1 \Rightarrow P(k)$」は空虚に真である。よって仮定を $n = 1$ に適用して $P(1)$ が成り立つ。$k \leq 1$ を満たす自然数は $k = 1$ だけなので $Q(1)$ が成り立つ。

$Q(n) \Rightarrow Q(n+1)$：$Q(n)$ を仮定する。自然数 $k$ について $k < n + 1$ と $k \leq n$ は同値なので、$Q(n)$ は「$k < n + 1$ を満たすすべての $k$ で $P(k)$」を意味する。よって仮定を $n + 1$ に適用して $P(n + 1)$ が成り立つ。これと $Q(n)$ を合わせて $Q(n + 1)$ が成り立つ。

帰納法によりすべての $n$ で $Q(n)$ が成り立ち、特に（$k = n$ として）$P(n)$ が成り立つ。$\square$

仮定の中に基礎段階が含まれていることに注意しよう（$n = 1$ のとき、何の助けもなしに $P(1)$ を示さねばならない）。実際の証明では「$n = 1$ の場合」と「$n \geq 2$ の場合」に分けて書くことが多い。

整数 $p \geq 2$ で、正の約数が $1$ と $p$ だけであるものを素数 (prime number) という。

例 1.35 $2$ 以上のすべての整数 $n$ は、有限個の素数の積で表せる（素数自身は 1 個の素数の積とみなす）。

証明. $n \geq 2$ とし、$2 \leq k < n$ を満たすすべての整数 $k$ が素数の積で表せると仮定する（完全帰納法の仮定）。$n$ が素数ならばそれ自身が素数の積である。素数でなければ、$1 < a < n$ を満たす約数 $a$ があり、$n = ab$ と書くと $1 < b < n$ でもある。仮定より $a$ と $b$ はそれぞれ素数の積なので、$n = ab$ も素数の積である。完全帰納法により（基点を $2$ とした形で）主張が従う。$\square$

表し方の一意性（素因数分解の一意性）は代数学 第1章で示す。

背理法

命題 $P$ を示すのに、$\neg P$ を仮定して矛盾（ある命題 $R$ とその否定 $\neg R$ がともに成り立つこと）を導く方法を背理法 (proof by contradiction) という。$R \land \neg R$ は常に偽なので、$\neg P \Rightarrow (R \land \neg R)$ が真ならば、定理 1.11 より $\neg\neg P \lor (R \land \neg R)$、すなわち $P$ が真である。

定理 1.36 $\sqrt{2}$ は無理数である。すなわち、$x^2 = 2$ を満たす有理数 $x$ は存在しない。

証明. $x^2 = 2$ を満たす有理数 $x$ が存在すると仮定する。$-x$ も同じ式を満たすので $x > 0$ としてよい。$x$ を既約分数で $x = m/n$（$m, n \in \mathbb{N}$ は $1$ 以外の正の公約数をもたない）と表すと、$m^2 = 2n^2$ である。よって $m^2$ は偶数であり、例 1.29 より $m$ は偶数である。$m = 2k$ と書くと $4k^2 = 2n^2$、すなわち $n^2 = 2k^2$ となり、同様に $n$ も偶数である。これは $m, n$ が公約数 $2$ をもたないことに矛盾する。$\square$

第7章では、既約分数を使わない別証明を与える。

定理 1.37（ユークリッド）素数は無限個存在する。

証明. 素数が有限個しかないと仮定し、それらを $p_1, \dots, p_r$ とする。$N := p_1 p_2 \cdots p_r + 1$ とおくと $N \geq 3$ であり、例 1.35 より $N$ を割り切る素数 $p$ が存在する。仮定より $p = p_i$ となる $i$ がある。すると $p$ は $N$ と $p_1 \cdots p_r$ の両方を割り切るので、その差 $1$ も割り切る。これは $p \geq 2$ に矛盾する。$\square$

注意 1.38（対偶と背理法）$P \Rightarrow Q$ を背理法で示すときは、$P$ と $\neg Q$ を仮定して何らかの矛盾を導く。対偶による証明では $\neg Q$ だけを仮定して $\neg P$ を導く。背理法で書いた証明で、到達した矛盾がちょうど「$P$ に反する」ものならば、それは対偶による証明に書き直せる。そのほうが読みやすいことが多い。また、定理 1.37 の証明は「素数の有限個のリストが与えられたら、それに含まれない素数が存在する」という直接証明に書き直せる。背理法の中の議論は偽の仮定の上に立っているため、途中の式の正しさを読者が確かめにくい。背理法は必要なときだけ使うのがよい。

存在の証明と反例

$\exists x,\ P(x)$ を示すには、条件を満たす $x$ を具体的に作ってみせるのが最も明快である。これを構成的証明 (constructive proof) という。

例 1.39 任意の $n \in \mathbb{N}$ に対して、連続する $n$ 個の合成数（$2$ 以上の素数でない整数）が存在する。実際、$(n+1)! + 2,\ (n+1)! + 3,\ \dots,\ (n+1)! + (n+1)$ がその例である。$2 \leq j \leq n + 1$ ならば $j$ は $(n+1)!$ を割り切るので $(n+1)! + j$ も割り切り、しかも $1 < j < (n+1)! + j$ だから $(n+1)! + j$ は合成数である。

一方、存在することはわかるが、どれが条件を満たすかは特定しない証明もある。これを非構成的証明 (non-constructive proof) という。

例 1.40 無理数 $a, b$ で、$a^b$ が有理数となるものが存在する。

証明. $c := \sqrt{2}^{\sqrt{2}}$ を考える。$c$ が有理数ならば $a = b = \sqrt{2}$ とすればよい（定理 1.36）。$c$ が無理数ならば $a = c$、$b = \sqrt{2}$ とすると、$a^b = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} = \sqrt{2}^2 = 2$ は有理数である。どちらの場合も条件を満たす $a, b$ が存在する。$\square$

この証明は、二つの候補のどちらが正しいかを教えてくれない（実は $c$ は無理数であることが知られているが、その証明ははるかに難しい）。

注意 1.41（一意性の証明）$\exists ! x \in X,\ P(x)$ を示すには、存在（$P(x)$ を満たす $x$ がある）と一意性（$P(x)$ と $P(x')$ がともに成り立てば $x = x'$）の両方を示す。たとえば $\exists ! x \in \mathbb{R},\ x^3 = 8$ について、存在は $x = 2$ で確かめられる。一意性：$x^3 = 8$ ならば $0 = x^3 - 8 = (x - 2)(x^2 + 2x + 4)$ であり、$x^2 + 2x + 4 = (x + 1)^2 + 3 > 0$ なので $x = 2$ である。したがって解はどれも $2$ に等しい。