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

document_iddoc_4169e9e02562651deb1a235b0e19b256title証明法と反例講義type講義content_typelecturedate2026-07-14categorymathdescription直接証明、対偶証明、背理法、場合分け、反例を、集合・関係・写像で使える形で説明する。prerequisites命題・述語と量化

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証明しょうめい.

data/lecture/math/discrete-math/propositions-predicates-and-quantifiers.lecture.n.md

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$ means that $x$ is an element of $A$ , and $A \subseteq B$ means that, for every $x$ , $x \in A$ implies $x \in B$ .

For example, to prove $A \subseteq C$ from $A \subseteq B$ and $B \subseteq C$ , expand the definition of the inclusion relation包含関係ほうがんかんけい. Take arbitrary $x$ and assume $x \in A$ . Then $x \in B$ by $A \subseteq B$ , and $x \in C$ by $B \subseteq C$ . Therefore $A \subseteq C$ .

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

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

\neg Q \Rightarrow \neg P

instead of

P \Rightarrow Q .

The two statements are equivalent.

The injection単射たんしゃ example below previews the later chapter on maps写像しゃぞう. At this point, only the condition “if $f (x) = f (y)$ , then $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$ is an injection単射たんしゃ means $f (x) = f (y) \Rightarrow x = y$ ; its contrapositive is $x \neq y \Rightarrow f (x) \neq f (y)$ .

data/lecture/math/discrete-math/injections-surjections-and-bijections.lecture.n.md

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$ such that $x [PARSE ERROR: Undefined("Command(\"le\")")] a$ for every $x \in P$ , and antisymmetry反対称性はんたいしょうせい means that $a [PARSE ERROR: Undefined("Command(\"le\")")] b$ and $b [PARSE ERROR: Undefined("Command(\"le\")")] a$ imply $a = b$ .

For example, prove that if a greatest element exists, it is unique. Negate the conclusion and suppose a partially ordered set半順序集合はんじゅんじょしゅうごう $P$ has distinct greatest elements $a$ and $b$ , so $a \neq b$ . By the definition of greatest element, $a [PARSE ERROR: Undefined("Command(\"le\")")] b$ and $b [PARSE ERROR: Undefined("Command(\"le\")")] a$ . By antisymmetry反対称性はんたいしょうせい, $a = b$ , contradicting $a \neq 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.

data/lecture/math/discrete-math/partial-and-total-orders.lecture.n.md

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$ as the set of elements in $A$ or $B$ , and $A \cap B$ as the set of elements in both.

For example, to prove

A \cap (B \cup C) = (A \cap B) \cup (A \cap C),

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

5Counterexample反例はんれい

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

The claim “for every integer $n$ , $n^{2} > n$ ” is false. The integer $n = 1$ does not satisfy the conclusion because $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.

6Exercise link and summary

data/exercise/math/discrete-math/logic-and-proof-methods.exercise.n.md

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.