証明法しょうめいほう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は、仮定かていから定義ていぎを順じゅんに使つかって結論けつろんを導みちびく方法ほうほうである。

次つぎの例れいは集合しゅうごうを先取さきどりする。ここでは $$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 である。

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

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

The following example previews sets. We use only the minimal definitions: $$x\in A$$x\in A means that $$x$$x is an element of $$A$$A, and $$A\subseteq B$$A\subseteq B means that, for every $$x$$x, $$x\in A$$x\in A implies $$x\in B$$x\in B.

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\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では、結論けつろんの否定ひていを仮定かていし、既知きちの定義ていぎや仮定かていと両立りょうりつしない矛盾むじゅんを導みちびく。結論けつろんそのものを仮定かていしてしまうと証明しょうめいにならない。

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. Negate the conclusion and suppose a partially ordered set半順序集合はんじゅんじょしゅうごう $$P$$P has distinct greatest elements $$a$$a and $$b$$b, so $$a\ne b$$a\ne 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, contradicting $$a\ne b$$a\ne 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は、対象たいしょうが有限ゆうげん個この型かたに分わかれるときに使つかう。集合演算しゅうごうえんざんでは、元げんがどの集合しゅうごうに属ぞくするかで場合分ばあいわけすることが多おおい。

次つぎの例れいも後続こうぞくの集合演算しゅうごうえんざんを先取さきどりする。$$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 である。したがって両辺りょうへんは等ひとしい。

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.

The next example also previews set operations. Read $$A\cup B$$A\cup B as the set of elements in $$A$$A or $$B$$B, and $$A\cap B$$A\cap B as the set of elements in both.

For example, to prove

take an arbitrary $$x$$x in the left side. Then $$x\in A$$x\in A and $$x\in B\cup C$$x\in B\cup C. If $$x\in B$$x\in B, then $$x\in A\cap B$$x\in A\cap B. If $$x\notin B$$x\notin B, membership in $$B\cup C$$B\cup C gives $$x\in C$$x\in C, so $$x\in A\cap C$$x\in A\cap C. Thus either case puts $$x$$x in the right side. Conversely, an $$x$$x in the right side lies in either $$A\cap B$$A\cap B or $$A\cap C$$A\cap C; in both cases $$x\in A$$x\in A and $$x\in B\cup C$$x\in B\cup C. Therefore the two sides are equal.

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

5Counterexample反例はんれい

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

The claim “for every integer $$n$$n, $$n^2>n$$n^2>n” is false. The integer $$n=1$$n=1 does not satisfy the conclusion because $$1^2=1$$1^2=1. This single example disproves the universal proposition.

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.