数学をするための基本事項　～証明の流れ～

数学の理論は命題の積み重ねによって出来上がります．なので，これまで命題について説明してきたわけですが，最も困難なことの1つはその命題が真なのか偽なのかを判断することです．証明の方法について解説します．

次の記事の続きです：

量化子の証明の流れ
「ならば」の証明方法
よく使う証明方法
まとめ
参考書

量化子の証明の流れ

全称命題

条件 $p(x)$ が与えられたときに $\forall$ をつけることにより，全称命題 $\forall x (p(x))$ を作ることができました．この命題が真であるとは，すべての $x$ に対して $p(x)$ が真となることですが，果たしてそれはどのようにすればよいのでしょうか．例えば変数 $x$ の動く範囲が $\{-1,2.5, 10\}$ という集合だとすると，それぞれを $p(x)$ に代入して $p(-1),p(2.5),p(10)$ がすべて真であることを言えばよいのでした．しかし，この $x$ の動く範囲が自然数全体や，実数全体のように無限個の元からなる集合だとしたら，先のように1つずつ $p(x)$ に代入して確かめることは不可能です．だから証明できない，というわけではなくて次のように証明します．例えば $x$ の動く範囲が実数全体であるときを考えてみましょう．このようなときは $x$ として具体的な実数を取ることをやめて，文字 $x$ によって実数を代表して表します．つまり $x$ は実数なら備えているはずの性質をすべて備えているものだとします．このとき注意しないといけないのは，すべての実数が備えているような性質以外は持っているとしてはいけないということです．つまり， $x$ は無理数である，とか奇数である，とか特別な性質は持ち合わせてはいけないということです．あくまでも $x$ は実数としての性質しか持っていない対象として扱います．このようにして $x$ が実数の性質を持っているとすれば， $p(x)$ は真となることが証明できたとしましょう．そうすれば例えば $x=3.12$ のように具体的な数字を代入したとしても，もちろん $3.14$ は実数としての性質をすべて持っているわけですから， $p(3.14)$ は真であることが分かるのです．ほかの具体的な数字を代入したって，実数の性質さえ満たしていれば真となることが分かるのです．このようにして「すべての実数に対して～が成り立つ」のような全称命題は証明が完了したことになります．

$p(x)$ として次のような条件を考えます：

「 $|x|\ge 0$ である．」

そしてこの条件から全称命題

「すべての実数 $x$ に対して， $|x|\ge 0$ である．」

を作り出します．これが真であることを証明するには $x$ を実数の性質をすべて備えたものとして取ってきたときに， $|x|\ge 0$ が成り立てばよいのです．

これが全称命題 $\forall x (p(x))$ の示し方です．

例1

次の命題を考える：

「すべての実数 $x$ に対して， $x^2>0$ である．」

これが真であることを示すには， $x$ を実数の持つ性質を備えているものとして，その性質だけから $x^2>0$ が真であることを証明できれば良い．しかし， $x$ を実数とするだけでは，この不等式は成り立たない．なぜなら $x=0$ とすると $0>0$ となってしまうからである．

数学書の証明を読むと見かけると思うのですが，全称命題を証明する際には，1行目などに「実数 $\varepsilon$ を任意にとる．」や「 $n$ を整数とする．」のような文が書いてあるのが分かると思います．それはこれらの文字が実数や整数の性質を満たす一般的な対象ですよ，と言っているのに過ぎないのです．

存在命題

全称命題ときたら，次は存在命題 $\exist x(p(x))$ です．存在命題の場合も，もし変数 $x$ が動く範囲が $\{-1,2.5, 10\}$ のような有限集合であれば， $p(-1),p(2.5),p(10)$ のどれか1つでも真となっていればよいのです．それでは $x$ の動く範囲が，整数全体や実数全体のように無限個の元を含む集合の場合はどうでしょうか．全称命題のときは有限集合を動くのか，無限集合を動くのかで若干アプローチが違っていましたが，存在命題は基本的に同じです． $x$ の取りうる値が無限通りあったとしても，その中からドンピシャで $p(x)$ を満たすようなものを見つけてくればよいのです．このようにすれば，「 $p(x)$ を満たす $x$ はこれです！」という具合に言えるわけですから， $\exist x(p(x))$ を示せたことになります．

次の存在命題を考えてみましょう：

「実数 $x$ で $2^x-x^2=0$ を満たすものが存在する．」

この命題が真であることを言いたければ，具体的な実数を $x$ に代入して条件 $2^x-x^2=0$ が満たされるようなものを見つければよいのです．

例えば $x=1$ を代入してみましょう．このとき左辺は $2^1-1^2=1$ となり右辺に一致しません．それでは $x=2$ を代入してみるとどうでしょうか．そうすると左辺は $2^2-2^2=0$ となるのでちょうど右辺に一致します．よって条件 $2^x-x^2=0$ を満たす具体的な実数として $2$ を見つけたので，上の存在命題は真であることが分かります．

例2

次の命題を考える：

「実数 $x$ で $x^2+1=0$ を満たすものが存在する．」

これは偽の命題である．なぜなら実数は2乗すると $0$ 以上になるので，左辺は常に $1$ 以上だからである．

このようにして存在命題は条件を満たすようなものを取ってくればいいのです．実際目にする命題はここで紹介したものほど簡単なものではありません．ですが，注意深く証明を読むと，ある条件を満たす $x$ が存在するのを証明するのに，「このように $x$ を構成すれば，この条件は満たされる」のような文言があるはずです．この文がまさに $x$ の存在を示しているのです．

量化子を含む命題の証明の難しさ

これらの証明において困難な部分について述べようと思います．まず全称命題ですが，これは $x$ が動く集合の元がすべて備えている性質から，条件が真となることを言えればよいわけでした．ですから， $x$ が動く集合が備えている性質が極端に少ないと，証明で使うことができる道具が極端に少なくなります．逆に $x$ が備えている性質が多ければ多いほど証明は簡単になります．例えばすべての整数に対して条件 $p(x)$ が成り立つことを示すのと，すべての実数に対して条件 $p(x)$ が成り立つのとでは，前者のほうがより簡単になります．なぜなら実数が備えている性質はすべて整数は備えていて，整数はさらに整数のみが持つ独特な性質があるので，より使える道具が増えるからです．ですが，示すことができて嬉しいのは後者の場合です．なぜなら，実数全体で成り立っているほうが整数全体で成り立つより多くの $x$ に対して $p(x)$ が真であることが分かるからです．なのでより多くのものに対してある条件が成り立ちますよ，ということは嬉しいことなのですが，証明するのはより難しくなってしまうのです．

全称命題には上のような難しさがあるのですが，存在命題はまた別の難しさがあります．条件 $p(x)$ が真となるような $x$ を持ってくれば，存在命題が真であることを示せたことになるのですが，この条件 $p(x)$ が真となるような $x$ を探すのが難しい場合が多いです．例えばこの記事の例として述べた存在命題の場合はそこまで難しくありませんでしたが，実際はもう少し条件が複雑になることが多いです．いくつもの条件を同時に満たす $x$ を探してくるのはなかなか困難なことが多く，実際に存在命題の証明を読んでみるとこんなの良く見つけられたなと思うことはよくあります．もちろん，存在命題の証明の仕方はちょうど条件を満たすような $x$ を見つけてくるだけではありません．すでに証明された存在命題を使うことも多々あります．例えば中間値の定理の主張は「～を満たす実数が存在する」という存在命題なのですが，この定理が保証する存在を別の存在命題の証明で使ったりもします（中間値の定理はその条件を満たすような実数を実際に構成して証明します．）．なので，存在命題は存在命題を証明するためにも重要なのです（ややこしいですが）．

「ならば」の証明方法

$p(x),q(x)$ を条件とします．命題 $p(x)\Longrightarrow q(x)$ はどのようにしたら真であることが言えたことになるのでしょうか．この命題は次の命題を表しているのでした：

$\forall x(p(x)\longrightarrow q(x))$

これは全称命題の一種なので，基本的には上で解説した全称命題の証明の仕方で証明します．この場合， $p(x)$ が偽となる $x$ については考えなくてもよかったので（数学をするための基本事項　～最もよく見る命題～を参照してください．） $p(x)$ という性質を $x$ は既に持っているものとして， $q(x)$ が真であることを示せばよいのです．例えば， $x$ は元から実数全体を動くものだとすると，実数の持つすべての性質に $p(x)$ という性質を $x$ が持っているものだとして $q(x)$ が真であることを言えれば，この命題が真であることが言えたことになる，という具合です．

例3

次の命題を証明する：

「すべての整数 $x$ に対して $x$ が奇数であるならば $x^2$ は奇数である」

上で説明したように， $x$ は整数であることに加えて，奇数であるという性質を持っているとして， $x^2$ が奇数になることを示せばいい． $x$ は奇数だから，ある整数 $n$ によって

$x=2n+1$

と書くことができる（これは $x$ が整数であるという条件だけでは得られない表式であることに注意する．）．これを2乗すると

$x^2=2(2n^2+2n)+1$

と書けるので， $x^2$ は奇数であることが分かる．よって，上の命題が示された．

よく使う証明方法

高校数学でもなじみのある対偶法と背理法について解説します．

対偶法

対偶法は $p(x)\Longrightarrow q(x)$ のような命題を示すのに使える方法です． $\neg q(x)\Longrightarrow \neg p(x)$ を $p(x)\Longrightarrow q(x)$ の対偶と言います．実は $p(x)\Longrightarrow q(x)$ の真偽は，その対偶 $\neg q(x)\Longrightarrow \neg p(x)$ に一致します．なので $\neg q(x)\Longrightarrow \neg p(x)$ の真偽を確かめることにより， $p(x)\Longrightarrow q(x)$ の真偽が分かります．この「元の命題の対偶を示す」という方法を対偶法と言います．

まずは $p(x)\Longrightarrow q(x)$ の真偽が $\neg q(x)\Longrightarrow \neg p(x)$ の真偽と一致することを確認しましょう．そのために命題 $p,q$ があったときに $p\rightarrow q$ と $\neg q\rightarrow \neg p$ の真偽がどうなるかを見てみましょう．真理表を書いてみると

$p$	$q$	$\neg p$	$\neg q$	$p\rightarrow q$	$\neg q\rightarrow \neg p$
T	T	F	F	T	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

となります．この表から $p\rightarrow q$ と $\neg q\rightarrow \neg p$ の真偽は一致することが分かります．このことから， $p(x),q(x)$ を条件として次の2つの条件

$p(x)\rightarrow q(x)$
$\neg q(x)\rightarrow \neg p(x)$

の $x$ に何かしらを代入して得られる2つの命題は真偽が一致するものとなります．よって次の2つの命題

$\forall x(p(x)\rightarrow q(x))$
$\forall x(\neg q(x)\rightarrow \neg p(x))$

の真偽は一致することが分かります．これらはそれぞれ $p(x)\Longrightarrow q(x)$ と $\neg q(x)\Longrightarrow \neg p(x)$ のことだったので，元の命題とその対偶の真偽が一致することが分かりました．

例4

$n$ を整数として次の命題を考える：

「 $n^2$ が偶数ならば $n$ は偶数である．」

これの対偶は

「 $n$ が奇数ならば $n^2$ は奇数である．」

である．この命題は例3で真であることが示されている．よって対偶が真であることが分かったので，元の命題

「 $n^2$ が偶数ならば $n$ は偶数である．」

が真であることが示された．

背理法

数学書を読んでいてよく出てくる証明方法として背理法というものがあります．次のような手順で行われます．まず示したい命題 $p$ を否定した命題 $\neg p$ が真だと仮定するところから始めます．そこから何かしらの結論として，必ず偽になるはずの命題が真であると得られることを示します．これは初めに $\neg p$ が真であると仮定したことにより起こった不都合ですから， $\neg p$ は実は偽でないといけないということです． $\neg p$ が偽ということは $\neg (\neg p)$ は真，つまり元の命題 $p$ が真であるということです．この「必ず偽になるはずの命題が真である」ことを矛盾と言います．

例5

次の命題を背理法で証明する：

「 $\sqrt{2}$ は無理数である．」

この命題の否定は次のようになる：

「 $\sqrt{2}$ は有理数である．」

この命題が真だとすると $\sqrt{2}$ は有理数なので， $a,b$ を整数として

$\sqrt{2}=\dfrac{a}{b}$

と書ける（ただし $b\neq 0$ です．）．このとき $a,b$ に共通の約数があるなら約分して，どちらかは偶数ではないとできる．上の式の両辺を2乗して

$2=\dfrac{a^2}{b^2}$

となり，両辺に $b^2$ をかれば

$2b^2=a^2$

と変形できる。例3より $a^2$ が偶数なので， $a$ は偶数であるから，ある整数 $n$ を使って

$a=2n$

と書ける．これを $2b^2=a^2$ に代入すると

$2b^2=4n^2$

となり， $2$ で両辺を割れば

$b^2=2n^2$

となる．再び例3より， $b^2$ が偶数だから， $b$ が偶数であることが分かる．今 $a,b$ が両方偶数であることが結論付けられたが， $a,b$ のどちらか一方は奇数でなければならないので，これは矛盾である．よって

「 $\sqrt{2}$ は有理数である．」

が偽であることが分かったので，元の命題である

「 $\sqrt{2}$ は無理数である．」

が真であることが証明された．

この証明をもう一度振り返ってみると，「 $\sqrt{2}$ は有理数である．」からスタートした場合，次のような命題が真であることが示されたことになります：

「整数 $a,b$ でどちらか一方は奇数であり，かつどちらも偶数であるものが存在する．」

しかし，これは明らかに偽の命題です．ここで矛盾が起きたので，初めに真であると仮定した「 $\sqrt{2}$ は有理数である．」は偽でなければならないということが分かるのです．

背理法の難しさは，どこで矛盾する部分が出てくるかは分からないということです．簡単なものであれば，すぐに分かるかもしれませんが，多くの場合数学的におかしいところは先天的に分かるわけではないのです．

背理法は命題の否定を作るところから始まります。否定の作り方は数学をするための基本事項　～否定のいろいろ～を参照してください．

背理法と対偶法の関係

実は対偶法は背理法の特別な場合です．上の例3を背理法で証明してみましょう．

$n$ を $n^2$ が偶数であるような整数とします．今示したいのは， $n$ 自身も偶数であるということです．そこで，これを否定して $n$ は奇数であるとしてみましょう．すると，例3とまったく同様にして $n^2$ が奇数であることが分かります．これが $n^2$ が偶数であることと矛盾します．よって $n$ 自身も偶数であることが示されました．

このように $p(x)\Longrightarrow q(x)$ を背理法で示すときに，次のようにできます． $p(x)$ を満たす $x$ が，さらに結論部分を否定した条件を満たしていると仮定して， $\neg p(x)$ を満たしていることを示すことで矛盾を導きます．この構造は対偶法とまったく同じです．ですから，背理法を用いても対偶法を用いてもどちらでもよいのです．

まとめ

よくある証明の流れについて解説しました．数学書を読む際に参考にしてみてください．

参考書

証明の読み方・考え方〔原著第6版〕: 数学的思考過程への手引き（Daniel Solow著　西村康一・服部久美子訳）：https://amzn.to/4aCrGFm

この記事と似たようなことをテーマに書かれている本です．数学をする上ではこの記事で解説したことを最低限知っていれば問題ないと思います（少なくとも私はこの記事で書いたことしか意識していません．）が，より細かいことが書いてあったり，面白い本なので気になった人は読んでみてください．