証明法しょうめいほうproof methodと反例はんれいcounterexample

離散数学りさんすうがくdiscrete mathematicsでは、定義ていぎから結論けつろんまでの距離きょりをできるだけ短みじかくすることが重要じゅうようである。式しき変形へんけいよりも、「どの定義ていぎを開ひらけばよいか」を選えらぶ力ちからが問とわれる。そこで、基本きほん的てきな証明しょうめいproofの型かたを整理せいりする。

1直接証明ちょくせつしょうめいdirect proof

直接証明ちょくせつしょうめいdirect proofは、仮定かていから定義ていぎを順じゅんに使つかって結論けつろんを導みちびく方法ほうほうである。

次つぎの例れいは集合しゅうごうを先取さきどりする。ここでは $$x\in A$$x\in A を「$$x$$x は $$A$$A の元げん」、$$A\subseteq B$$A\subseteq B を「任意にんいの $$x$$x について、$$x\in A$$x\in A ならば $$x\in B$$x\in B」と読よむための最小限さいしょうげんの定義ていぎだけを使つかう。

たとえば $$A\subseteq B$$A\subseteq B と $$B\subseteq C$$B\subseteq C から $$A\subseteq C$$A\subseteq C を示しめすには、包含関係ほうがんかんけいinclusion relationの定義ていぎを開ひらく。任意にんいの $$x$$x を取とり、$$x\in A$$x\in A と仮定かていする。すると $$A\subseteq B$$A\subseteq B より $$x\in B$$x\in B、さらに $$B\subseteq C$$B\subseteq C より $$x\in C$$x\in C である。したがって $$A\subseteq C$$A\subseteq C である。

2対偶証明たいぐうしょうめいproof by contraposition

対偶証明たいぐうしょうめいproof by contrapositionは、

の代かわりに

を示しめす方法ほうほうである。両者りょうしゃは同値どうちである。

ここでの単射たんしゃinjectionは、後あとの写像しゃぞうmapの章しょうを先取さきどりする例れいである。この段階だんかいでは、対偶たいぐうの形かたちを見みるために「$$f\left(x\right)=f\left(y\right)$$f(x)=f(y) なら $$x=y$$x=y」という条件じょうけんだけを使つかう。

単射たんしゃinjectionの証明しょうめいでは、対偶たいぐうが自然しぜんに使つかえることが多おおい。$$f:A\to B$$f:A\to B が単射たんしゃinjectionであることは $$f\left(x\right)=f\left(y\right)\Rightarrow x=y$$f(x)=f(y)\Rightarrow x=y であり、その対偶たいぐうは $$x\ne y\Rightarrow f\left(x\right)\ne f\left(y\right)$$x\ne y\Rightarrow f(x)\ne f(y) である。

3背理法はいりほうproof by contradiction

背理法はいりほうproof by contradictionは、結論けつろんの否定ひていを仮定かていして矛盾むじゅんを導みちびく方法ほうほうである。

次つぎの例れいは、後続こうぞくの半順序関係はんじゅんじょかんけいpartial orderの先取さきどりである。ここでは、半順序集合はんじゅんじょしゅうごうpartially ordered setの全体理論ぜんたいりろんは使つかわず、必要ひつような仮定かていだけを明示めいじして使つかう。すなわち、最大元さいだいげんgreatest elementとは任意にんいの $$x\in P$$x\in P に対たいして $$x\text{[PARSE ERROR: Undefined("Command("le")")]}a$$x\le a を満みたす元げん $$a$$a であり、反対称性はんたいしょうせいantisymmetryとは $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b かつ $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a なら $$a=b$$a=b となる性質せいしつである。

たとえば「最大元さいだいげんが存在そんざいすれば、それは一意いちいである」を示しめす。結論けつろんを否定ひていし、半順序集合はんじゅんじょしゅうごうpartially ordered set $$P$$P に異ことなる最大元さいだいげん $$a$$a と $$b$$b、すなわち $$a\ne b$$a\ne b があると仮定かていする。最大元さいだいげんの定義ていぎより、$$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b かつ $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a である。反対称性はんたいしょうせいantisymmetryより $$a=b$$a=b となり、$$a\ne b$$a\ne b と矛盾むじゅんする。したがって異ことなる 2 つの最大元さいだいげんは存在そんざいしない。

背理法はいりほうproof by contradictionでは、結論けつろんの否定ひていを仮定かていし、既知きちの定義ていぎや仮定かていと両立りょうりつしない矛盾むじゅんを導みちびく。結論けつろんそのものを仮定かていしてしまうと証明しょうめいにならない。

4場合分ばあいわけproof by cases

場合分ばあいわけproof by casesは、対象たいしょうが有限ゆうげん個この型かたに分わかれるときに使つかう。集合演算しゅうごうえんざんでは、元げんがどの集合しゅうごうに属ぞくするかで場合分ばあいわけすることが多おおい。

次つぎの例れいも後続こうぞくの集合演算しゅうごうえんざんを先取さきどりする。$$A\cup B$$A\cup B は $$A$$A または $$B$$B に属ぞくする元げんの集合しゅうごう、$$A\cap B$$A\cap B は両方りょうほうに属ぞくする元げんの集合しゅうごうと読よむ。

たとえば

を示しめす。左辺さへんの任意にんいの元げん $$x$$x をとると $$x\in A$$x\in A かつ $$x\in B\cup C$$x\in B\cup C である。$$x\in B$$x\in B の場合ばあいは $$x\in A\cap B$$x\in A\cap B、$$x\notin B$$x\notin B の場合ばあいは $$x\in C$$x\in C なので $$x\in A\cap C$$x\in A\cap C となり、どちらも右辺うへんに属ぞくする。逆ぎゃくに右辺うへんの $$x$$x は、$$x\in A\cap B$$x\in A\cap B または $$x\in A\cap C$$x\in A\cap C のどちらの場合ばあいも $$x\in A$$x\in A かつ $$x\in B\cup C$$x\in B\cup C である。したがって両辺りょうへんは等ひとしい。

5反例はんれいcounterexample

反例はんれいcounterexampleは、全称ぜんしょう命題めいだいを否定ひていするための 1 つの例れいである。

「すべての整数せいすう $$n$$n について $$n^2>n$$n^2>n」という主張しゅちょうは偽ぎである。$$n=1$$n=1 は整数せいすうだが、$$1^2=1$$1^2=1 なので $$1^2>1$$1^2>1 を満みたさない。この 1 つの例れいで全称命題ぜんしょうめいだいを否定ひていできる。

反例はんれいでは、対象たいしょうが定義ていぎの条件じょうけんを満みたしていることと、結論けつろんが壊こわれていることを両方りょうほう明示めいじする必要ひつようがある。

反例はんれいcounterexampleは、仮定かていをすべて満みたしながら結論けつろんを破やぶる具体例ぐたいれいでなければならない。仮定かていを満みたさない例れいは、主張しゅちょうの失敗しっぱいを示しめさない。

6演習えんしゅうリンクとまとめ

証明しょうめいproofでは、定義ていぎを開ひらき、必要ひつような量化りょうかを明確めいかくにし、どの型かたの議論ぎろんを使つかうかを選えらぶ。反例はんれいcounterexampleは「成立せいりつしない」ことを示しめす強力きょうりょくな方法ほうほうだが、反例はんれいの条件じょうけん確認かくにんを省略しょうりゃくしてはいけない。

演習えんしゅうでは、直接証明ちょくせつしょうめい、対偶たいぐうcontrapositive、背理法はいりほうproof by contradiction、場合分ばあいわけproof by cases、反例はんれいcounterexampleのどれを使つかっているかを明示めいじすると、仮定かていと結論けつろんの対応たいおうを追おいやすい。