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

Proof methods証明法しょうめいほう and counterexamples反例はんれい

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

In discrete mathematics離散数学りさんすうがく, it is important to keep the path from definition to conclusion short. More than algebraic manipulation, the central skill is choosing which definition to expand. This page organizes basic types of proof証明しょうめい.

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

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

たとえば $$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 である。

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

A direct proof直接証明ちょくせつしょうめい starts from the assumptions, uses definitions in order, and derives the conclusion.

For example, to prove $$A\subseteq C$$A\subseteq C from $$A\subseteq B$$A\subseteq B and $$B\subseteq C$$B\subseteq C, expand the definition of the inclusion relation包含関係ほうがんかんけい. Take arbitrary $$x$$x and assume $$x\in A$$x\in A. Then $$x\in B$$x\in B by $$A\subseteq B$$A\subseteq B, and $$x\in C$$x\in C by $$B\subseteq C$$B\subseteq C. Therefore $$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) である。

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

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

instead of

The two statements are equivalent.

The injection単射たんしゃ example below previews the later chapter on maps写像しゃぞう. At this point, only the condition “if $$f\left(x\right)=f\left(y\right)$$f(x)=f(y), then $$x=y$$x=y” is being used in order to see the form of a contrapositive.

This method is often natural for proving injectivity単射性たんしゃせい. Saying that $$f:A\to B$$f:A\to B is an injection単射たんしゃ means $$f\left(x\right)=f\left(y\right)\Rightarrow x=y$$f(x)=f(y)\Rightarrow x=y; its contrapositive is $$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\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 である。したがって異ことなる 2 つの最大元さいだいげんは存在そんざいしない。

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

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

A proof by contradiction背理法はいりほう assumes the negation of the desired conclusion and derives a contradiction.

The next example previews partial orders半順序関係はんじゅんじょかんけい. It does not use the full later theory; it only uses the assumptions needed for this proof. A greatest element最大元さいだいげん is an element $$a$$a such that $$x\text{[PARSE ERROR: Undefined("Command("le")")]}a$$x\le a for every $$x\in P$$x\in P, and antisymmetry反対称性はんたいしょうせい means that $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b and $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a imply $$a=b$$a=b.

For example, prove that if a greatest element exists, it is unique. Suppose a partially ordered set半順序集合はんじゅんじょしゅうごう $$P$$P has greatest elements $$a$$a and $$b$$b. By the definition of greatest element, $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b and $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a. By antisymmetry反対称性はんたいしょうせい, $$a=b$$a=b. Hence two distinct greatest elements cannot exist.

In a proof by contradiction, assume the negation of the conclusion and derive a contradiction with known definitions or assumptions. If one assumes the conclusion itself, that is not a proof.

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

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

たとえば

を示しめすには、任意にんいの $$x$$x について $$x\in A$$x\in A、$$x\in B$$x\in B、$$x\in C$$x\in C の真偽しんぎを追おう。左辺さへんに属ぞくすることは $$x\in A\text{and}(x\in B\text{or}x\in C)$$x\in A\ \text{and}\ (x\in B\ \text{or}\ x\in C) であり、これは $$(x\in A\text{and}x\in B)\text{or}(x\in A\text{and}x\in C)$$(x\in A\ \text{and}\ x\in B)\ \text{or}\ (x\in A\ \text{and}\ x\in C) と同値どうちである。

4Proof by cases場合分け

A proof by cases場合分け is used when the object splits into finitely many exhaustive types. In set operations集合演算しゅうごうえんざん, cases often come from which sets an element元げん belongs to.

For example, to prove

track, for arbitrary $$x$$x, the truth values of $$x\in A$$x\in A, $$x\in B$$x\in B, and $$x\in C$$x\in C. Membership in the left side is $$x\in A\text{and}(x\in B\text{or}x\in C)$$x\in A\ \text{and}\ (x\in B\ \text{or}\ x\in C), which is equivalent to $$(x\in A\text{and}x\in B)\text{or}(x\in A\text{and}x\in C)$$(x\in A\ \text{and}\ x\in B)\ \text{or}\ (x\in A\ \text{and}\ x\in C).

5反例はんれいcounterexample

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

「すべての関係かんけいは対称たいしょうである」という主張しゅちょうは偽ぎである。$$A=\{1,2\}$$A=\{1,2\} 上うえの関係かんけい

を考かんがえると、$$(1,2)\in R$$(1,2)\in R だが $$(2,1)\notin R$$(2,1)\notin R である。したがって $$R$$R は対称性たいしょうせいsymmetryを持もたない。

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

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

5Counterexample反例はんれい

A counterexample反例はんれい is one example that disproves a universal proposition.

The claim “every relation関係かんけい is symmetric対称たいしょう” is false. Consider the relation on $$A=\{1,2\}$$A=\{1,2\}

Then $$(1,2)\in R$$(1,2)\in R but $$(2,1)\notin R$$(2,1)\notin R. Therefore $$R$$R does not have symmetry対称性たいしょうせい.

For a counterexample, explicitly check both that the object satisfies the assumptions and that the conclusion fails.

A counterexample反例はんれい must satisfy all assumptions while breaking the conclusion. An example that does not satisfy the assumptions does not show that the claim fails.

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

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

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

6Exercise link and summary

In a proof証明しょうめい, expand definitions, make the necessary quantifiers量化りょうか explicit, and choose the right proof pattern. A counterexample反例はんれい is a powerful way to show that something fails, but the counterexample must still be checked against the assumptions.

In exercises, explicitly name whether you are using a direct proof, a contrapositive対偶たいぐう, proof by contradiction背理法はいりほう, proof by cases場合分け, or a counterexample反例はんれい. This makes the relation between assumptions and conclusion easier to follow.