今、シリーズでオートマトンと言語に関する話を書いている。
初回は以下だ。
さて、前回は証明の解説の準備として、命題と論理を解説した。
改めて言葉で見るとなかなかに難しそうだが、適宜真偽関係を見ながら進めてもらえればと思う。
前回の記事は以下だ。
…というわけで、今回はようやく証明というやつに入っていく、のだが。
先に書いてしまうが、今回の記事はかなり自信がない。
というのも、私自身、証明は例を読み漁って理解したので、改めて言葉で説明するのに非常に苦労してしまっている。
厳密な説明を期待されていたら申し訳ないのだが、実例を使ってこんな感じで進めていく、という解説に留めさせてもらう。
今回の流れとしては、まずそもそもどんな対象について証明する必要があるのか、という部分に触れる。
次に、実際に証明を行う流れ、そしてよく使われる証明手法、という感じだ。
また、本編でよく使っている内容についても軽く触れようと思う。
ちなみに、今回は参考書の紹介はしない。
前回紹介した参考書にも一応証明の解説は載っているのだが、1ページだけ軽く触れられているという程度。
そこでは用語と手法が言葉で軽く紹介されているくらいなので、わざわざそれを参照するためだけに買う必要はないだろう、ということだ。
もし、証明について参考書が欲しい方は、自分で調べて欲しい。
証明が必要な対象
証明自体の解説に入る前に、これを解説しておこう。
そもそもの話ではあるが、一体どんな対象について証明すればいいのだろうか。
これを理解してもらうために、定義、定理、補題という三つの用語を解説する。
定義
まず定義とは、簡単に言ってしまうと約束事のことだ。
数学系の本で、「～と呼ぶ」とか、「～という」とか、あるいは「～と定義する」などのような形で書かれていれば、それが定義というやつになる。
主には、名前をつけていることが多い。
例えば…
- 1, 2, 3, …と続く数を自然数と呼ぶ。
- 1とその数自身でしか割り切れないような数を、素数という。
- \(n\)で割り切れる整数を、\(n\)の倍数と定義する。
といったものが、定義の例になる。
これらは約束事であり、それが正しいかどうか、といったことは考えない。
つまり、この定義に対しては証明は不要だ。
定理
次に、定理とは、定義や他の定理から成り立つことが証明された命題のこと。
というわけで、これに対しては証明が必要だ。
簡単に言ってしまうと、「こう約束したら、結局はこうなるよね」という主張だと思ってもらっていいだろう。
で、前回の内容を思い出してほしい。
「こう約束したら」の部分は前提、「結局はこうなるよね」の部分は結論だ。
つまり、定理は基本的に条件付き命題の形になっている。
あるいは、同値関係になっていることも多い。
同値関係の場合は、「～は、…と同値である」とか、「～と…は必要十分条件である」とかで書き表されることが多い。
必要十分条件とは、前回省略してしまった内容なのだが、ここでは同値をそうとも言うくらいの認識でいてもらえれば十分だ。
詳しくは解説しないので、気になる方は調べてみよう。
例えば…
- 整数の各桁の総和が3の倍数であれば、元の数は3の倍数である。
- 直角三角形の斜辺以外の長さを\(a, b\)、斜辺の長さを\(c\)とすると、\(a^2 + b^2 = c^2\)が成り立つ。
- 素数は無数に存在する。(前提は素数の定義)
などが、定理の例だ。
この書き方は全部単なる条件付き命題のもので、同値関係だと「整数の各桁の総和が3の倍数であることと、元の数が3の倍数であることは同値である」という感じ。
補題
補題も定理の一種なのだが、定理というほど重要ではない性質を表すような命題を補題と呼ぶ。
定理の一種なので、やはり証明は必要だ。
これは、他の定理の証明時に使うことを目的としていることが多い。
例えば、上の定理の例で挙げたうち、「素数は無数に存在する」ことを証明したいとする。
その時には、「\(n\)を2以上の自然数として、\(n\)の倍数に1加算した数は、\(n\)の倍数ではない」という補題を使うと証明が非常に簡単になる。
ちょっと、後で手法を解説する際に、これも実際に証明してみよう。
ちなみに、どこまでが補題で、どこからが定理なのかについては…はっきりした線引きはないように思っている。
まあ、使う目的が異なるだけで、証明しなければいけないことや、他の証明に使えることは一緒なので、どちらなのかは深くは考えない方がいいかもしれない。
証明
さて、上で書いたように、定理や補題に対してはこの証明というやつをしなければいけない。
感覚的に証明とは何かを掴んでもらおう。
例えば、さっき出した定理の例のうち一つ、「整数の各桁の総和が3の倍数であれば、元の数は3の倍数である」を…そのままだと文字が複雑になるので、ちょっと変えさせてもらう。
「999以下の自然数の各桁の総和が3の倍数であれば、元の数は3の倍数である」を示すとする。
範囲を狭めて、3桁以下にした。
さて、証明をするときは、例えばそれを知らない子どもに説明することを想像してみよう。
その子はとても注意深い子で、気になることがあるとどんどん突っ込んでくる。
では、説明をするのだが…例えば、幾つか具体例を挙げて成り立つことを説明してみよう。
- 一桁の3, 6, 9では成り立っている。
- 二桁で、12, 36, 54は成り立っている。
- 三桁で、123, 444, 501は成り立っている。
これで納得してもらえるかというと…無理だ。
その子は、「じゃあ他の数は？」と突っ込んでくる。
で、今回は限りがあるので、全部挙げ切れば納得はしてくれるだろう。
実際、範囲が有限であるような場合には、コンピュータで全パターン網羅して証明した、という実例もあるらしい。
しかし、範囲を狭める前の内容で見ると、前提を満たす数は無限に存在する。
つまり、範囲によってはこの方法だけだとその子を完全に納得させることができないのだ。
ではどうするかというと、あくまで一例だが…今回の場合は前提について文字を使って一般化というものを行う。
文字を使って表現することで、今回注目したい範囲の中でどんな数でも扱えるようにするのだ。
今回は3桁以下の自然数なので、その100の位を\(a\)、10の位を\(b\)、1の位を\(c\)と置いてみよう。
すると、今注目している3桁以下の自然数を例えば\(n\)と置くと、以下の形で書き表すことができる。
$$n = 100a + 10b + c$$
これは自然数の10進法の決まりからこう置けるので、その子も納得してくれる。
この\(a, b, c\)に具体的な数を代入することで、どんな3桁以下の自然数も表せることがポイントだ。
ちなみに、この\(a, b, c\)は全て0以上9以下の整数であることを覚えておいて欲しい。
次に、前提と3の倍数の定義から、別の整数\(k\)というやつを使って、各桁の和を表せる。
$$a + b + c = 3k$$
ここも、突っ込まれることはない。
というように、すでに分かっていること…前提や定義、あるいはすでに証明された他の定理から言えることを積み重ねていく、というのが証明だ。
続けていこう。
最初に注目していた\(n\)を、式変形していく。
$$\begin{eqnarray}
n & = & 100a + 10b + c \\
& = & 99a + 9b + (a + b + c) \\
& = & 99a + 9b + 3k \\
& = & 3(33a + 3b + k)
\end{eqnarray}$$
ここまで。
さて、今上で置いた\(a, b, k\)はそれぞれが整数になっている。
整数同士の乗算、加算の結果も必ず整数なので、\(33a + 3b + k\)は整数だ。
つまり、式変形の最後は3と整数の乗算…3の倍数だ。
これが\(n\)とイコールなので、\(n\)も3の倍数ということになる。
で、この\(n\)が何者だったかというと、前提を満たす数だ。
よって、前提を満たせばその数が3の倍数になったので、示したいことが言えた、証明完了だ。
ここまでやれば、その子も十分納得してくれるだろう。
こんな感じで、すでに分かっていることから言えることを積み重ねていくことで、証明というものが進んでいく。
さて、証明の中で説明した一般化について少し補足を。
改めて、一般化とは性質を保ったまま定式化すること。
今回の例では、3桁以下の自然数を三つの文字で表した部分と、各桁の総和が3の倍数だということを表した部分。
こうすることで、性質が保たれたまま議論を進めていくことができる。
なぜこれをするかというと、前提を満たすパターン全てを一括で扱いたいから。
最初に例を出したように、実際の値を幾つか試すだけでは証明にはならない。
かといって、範囲の全パターンを試せるとも限らない。
だから、性質を反映した文字を含む式に変形することで、そのパターン全てを一括で扱えるようになる。
これが必ず必要というわけではないが、非常によく使うものなので覚えておこう。
ちなみにだが、上の例で「各桁の和が3の倍数でない数はどうなのか」という疑問があるかもしれない。
今回の場合は、そこについては触れる必要はない。
なぜなら、今回は証明したかった内容が単純な条件付き命題だからだ。
前回の復習で、条件付き命題\(A_1 \Rightarrow A_2\)については、\(A_1\)が偽の場合は全体が常に真となる。
今回で言うと、「各桁の和が3の倍数でない数」が3の倍数であろうとなかろうと、全体は真なのだ。
だから、そちらは証明する必要がない。
ただし、証明したい内容が同値関係だった場合は話が変わる。
同値関係では、片方を前提、もう片方を結論とした二つの条件付き命題両方を示す必要がある。
実際、今回の前提「999以下の自然数\(n\)の各桁の総和が3の倍数である」と結論「\(n\)が3の倍数である」は同値関係。
なので、そちらも要求された場合は「999以下の自然数\(n\)が3の倍数なら、\(n\)の各桁の総和が3の倍数である」も証明する必要が出てくるので気を付けよう。
これの対偶を取ると、「999以下の自然数\(n\)の各桁の総和が3の倍数でないなら、\(n\)は3の倍数でない」となるので、気になる部分の証明だと分かってもらえると思う。
…なんとなく、証明の流れは分かっただろうか。
とにかく、誰にも突っ込まれないような議論を進めることを意識しておこう。
証明の手法
さて、単に証明とはいっても、そのまま議論を進めるだけではない。
幾つか、証明をする際に使える論法があるので、それを紹介していこう。
対偶を証明する
ちょっと上でも出してしまったが、元の内容の対偶を取り、それを証明するという方法がある。
前回やった通り、元の条件付き命題とその対偶は必ず真偽が一致する。
そのため、対偶が真だと分かれば、元も真だと分かるのだ。
具体例として、「\(n^3 + n^2 + n\)が奇数ならば\(n\)も奇数である」を示してみよう。
ただし、このさらに前提として、\(n\)は整数だとする。
形としては、命題\(A \Rightarrow (\)命題\(B \Rightarrow \)命題\(C)\)となっている。
このとき、命題\(B \Rightarrow \)命題\(C\)が示したい部分だ。
で、この対偶を取ると、「\(n\)が偶数ならば、\(n^3 + n^2 + n\)も偶数である」となる。
上の括弧内の部分を対偶にした、という感じ。
こうすれば、非常に簡単だ。
先に、結論の式を一つ式変形しておく。
$$n^3 + n^2 + n = n(n^2 + n + 1)$$
全体を\(n\)で括っただけだ。
さて、前提から\(n\)は偶数…言い換えると2の倍数なので、ある整数\(k\)を使って、以下のように書き表せる。
$$n = 2k$$
これを、上で変形した式の一つだけに代入してみよう。
$$n(n^2 + n + 1) = 2k(n^2 + n + 1)$$
これで、結論に入っている式が2の倍数、つまり偶数だと分かった。
よって、対偶が真であるので、元の命題も真、これで証明完了。
このように、対偶に変換することで証明しやすくなる場合があるので、行き詰まったら対偶を見てみるといいかもしれない。
背理法
これはトリッキーな方法なので、抵抗がある人も少なくないと思う。
背理法とは、主張をあえて否定してから議論を進めていく方法だ。
条件付き命題「\(A\)ならば\(B\)」の否定は、前回やった通り「\(A\)かつ\(B\)ではない」。
それを前提として議論を進め、矛盾というものを発生させるのだ。
矛盾とは、ある命題について、それが真であることと偽であることが両方同時に成り立つこと。
これは起こりえないので、前提としていた否定が偽だと分かる。
で、これまた前回の復習だが、否定は真偽が逆転するので、元の命題が真だと証明できる、という流れ。
これも実際にやってみよう。
上で出した定理「素数は無数に存在する」を示す。
…のだが、上で書いた通りこれには補題を使った方が楽に証明できるので、ちょっと横道に逸れてその補題を示していこう。
補題とその証明
補題は、「\(n\)を2以上の自然数として、\(n\)の倍数に1加算した数は、\(n\)の倍数ではない」だ。
これを示していこう。
まず、\(n\)の倍数を一般化し、ある整数\(k\)を使って\(nk\)と表す。
そして、それに1加算した数は\(nk + 1\)だ。
ここで、この\(nk + 1\)を\(n\)で割ってみよう。
$$\begin{eqnarray}
\frac{nk + 1}{n} & = & \frac{nk}{n} + \frac{1}{n} \\
& = & k + \frac{1}{n}
\end{eqnarray}$$
ここで、\(k\)は上で置いた通り整数だ。
そして、\(n\)は2以上の自然数なので、1を\(n\)で割ると必ず小数になる。
つまり、この数は\(n\)では割り切れないので、\(n\)の倍数ではない。
以上で、補題の証明が完了、元の証明で使えるようになった。
定理の証明
では、寄り道から戻ってきて…「素数は無数に存在する」を背理法で証明していこう。
これを否定すると、「素数は有限個しか存在しない」となる。
これを前提として、議論を進めていく。
まず、有限個なので全部で\(n\)個あるとして、それを全部列挙しよう。
素数はよく\(p\)で表されるので、区別するために添え字をつけて、以下のように列挙できたとする。
$$p_1, p_2, …, p_n$$
この中には素数全部が登場していることを覚えておいて欲しい。
では、この素数全てを1回ずつ掛け合わせる。
$$p_1p_2…p_n$$
今、全ての\(p\)は素数より整数なので、この数は全ての素数の倍数となっている。
で、これに1を足そう。
$$p_1p_2…p_n + 1$$
上で示した補題より、この数はどの素数の倍数にもなっていない。
ということは、この数を割り切るのは、1とこの数自身、あるいはここに出てきていない素数を約数に持つような数のいずれか。
だが、素数は全て列挙されているはずなので、三つ目のパターンは存在せず、1とこの数自身しか割り切ることができない。
つまり、これも素数で、しかも上に挙げた中には含まれていない。
…何かおかしい点がないだろうか。
さっき列挙した際は、全ての素数が登場していたのではなかっただろうか。
しかし、今それ以外に素数が作れてしまった。
これが、数学における矛盾だ。
何がまずかったかというと、素数が有限個だと勝手に仮定した部分。
つまり、元の内容「素数は無数に存在する」が示せた、証明完了だ。
ちなみに、一つ注意。
証明内で、\(p_1p_2…p_n + 1\)は新しい素数だと言っているが、これはあくまで今回の仮定において言えることだ、ということに注意しておいてほしい。
何を言っているかというと、「小さい素数から順番に掛け合わせ、それに1を足したら素数になる」が成り立つわけではない、ということ。
これは実際反例があり、2, 3, 5, 7, 11, 13を掛け合わせ、それに1を足すと30031となる。
30031 = 59 × 509であり、素数ではないのだ。
数学的帰納法
これもトリッキーな方法の一つ。
これは、命題に下限のある整数が含まれている場合によく使う手法だ。
一般的には自然数で使うことが多いが、自然数も下限が1の整数と捉えれば、上の説明で問題ない。
で、これは含まれている下限のある整数について以下二つのパターンを示すことにより証明を行う。
- 下限で成り立つことを示す
- ある時点で成り立つことを仮定し(!?)、その次でも成り立つことを示す
ということで、なんと示したいことが成り立つと仮定してしまう。
…と捉えると混乱するので気を付けよう。
元の命題は、範囲内の全てで成り立つという主張。
二つ目のパターンで成り立つと仮定するのは、範囲内のある一つで成り立つという主張。
この違いに気を付けていただきたい。
これでなんで証明できるかというと…具体例で見た方が早いと思うので、先に一回証明してしまおう。
\(n\)を自然数としたとき、以下の等式が成り立つことを示す。
$$1 + 2 + … + n = \frac{1}{2}n(n + 1)$$
左辺は、1から\(n\)までの総和を表している。
では、証明していこう。
まずパターン1、今回は下限が1なので、\(n = 1\)で成り立つことを示す。
左辺は、計算するまでもなく1だ。
右辺を計算すると…
$$\frac{1}{2} \times 1 \times (1 + 1) = 1$$
より、両辺1となったので成立。
次にパターン2、ある自然数\(k\)について、\(n = k\)の時に等式が成り立つと仮定する。
$$1 + 2 + … + k = \frac{1}{2}k(k + 1)$$
上にも書いた通り、現時点では少なくともこの\(k\)については成り立っているという仮定だ。
このとき、\(n = k + 1\)でも等式が成り立つか…要するに、以下の式が成り立つかを見ていく。
$$1 + 2 + … + k + (k + 1) = \frac{1}{2}(k + 1)(k + 2)$$
左辺から出発して、右辺の形に持っていこう。
帰納法の仮定から、左辺の\(k + 1\)以外は置き換えることができる。
$$1 + 2 + … + k + (k + 1) = \frac{1}{2}k(k + 1) + (k + 1)$$
\(k + 1\)で括って整理しよう。
$$\begin{eqnarray}
\frac{1}{2}k(k + 1) + (k + 1) & = & (k + 1)(\frac{1}{2}k + 1) \\
& = & \frac{1}{2}(k + 1)(k + 2)
\end{eqnarray}$$
ということで、示したい式の右辺に変形することができたので、こちらのパターンもOK。
以上から、元の式がどんな自然数でも成り立つことが示せた、ということになる。
さて、なぜこれでいいかだが、以下のように考えればいい。
- \(n = 1\)のとき成り立つ
- \(n = k = 1\)のとき成り立てば、\(n = k + 1 = 2\)のとき成り立つ
- \(n = k = 2\)のとき成り立てば、\(n = k + 1 = 3\)のとき成り立つ
- …
このように、ある時点で成り立てばその次に成り立つことが言えているので、それを最小の数から順番に適用してあげればいい。
これで、無限に続く自然数全てで成り立つことが言えるのだ。
もちろん、最小が1以外ならまずその時に成り立つことを言って、あとは同じ流れ。
本編では0以上の整数でやっていることの方が多い。
本編で使っている内容の補足
忘れかけているかもしれないが、一応この記事の立ち位置は、オートマトンや言語について解説しているシリーズの補足だ。
ということで、その本編でよく使っている内容を一つだけ補足しておこう。
何かというと、集合のイコールを証明するパターン。
このとき、イコールを示したい二つの集合を\(A, B\)として、以下の形で証明していることが多い。
- 任意の\(a \in A\)について、\(a \in B\)であることを示す
- 任意の\(b \in B\)について、\(b \in A\)であることを示す
こうしている理由だが、集合のイコールの定義からだ。
復習しよう。
二つの集合\(A, B\)がイコールであるとは、以下の二つの条件を両方とも満たすこと。
- \(A \subset B\)である
- \(B \subset A\)である
そして、この部分集合について、\(A \subset B\)であるとは、以下の条件を満たすこと。
- 任意の\(a \in A\)について、\(a \in B\)である
これらを組み合わせると、上に書いた二つを示すことになるのだ。
これは一般的にもよく使われるので、是非覚えておいて欲しい。
おわりに
今回は、証明を解説してきた。
慣れないうちは非常に難しいのだが、こればっかりは経験値を増やさないとどうしようもない。
私のように、色々な証明を読み漁って勉強するのも一つの手だろう。
今やネットで調べれば色々な証明が出てくるので、是非参考にしていただきたい。
…ちなみにだが、今回あえて説明を避けた用語で、「公理」というものがある。
省略した理由は二つで、まず本編には必要ないから、そして説明すると混乱を招きかねないから。
重要な概念ではあるので、余力があれば調べてみよう。
さて、次回は話が集合に戻る。
そこで、写像というものを考えることができるので、それを解説していこう。
2020/12/24追記
気づけばクリスマスイブだが、一緒に過ごす相手がいるわけでもなく平常運転だ。
予告通り、写像についての解説を投稿した。
後半駆け足だが、基本的な定義が分かれば本編には問題ないかと思うので、よかったら目を通してみて欲しい。
コメント