Methods of proof
The six ways of proving: direct, by contrapositive, by contradiction, by cases, by counterexample and by induction, with the structure of each.
- 22 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
A few cards from the deck
Direct proof: what is it?
Show the answer
A proof of an implication p ⇒ q that starts from the hypothesis p and chains deductions up to the conclusion q.
It is the default method: if n is even, n = 2k, so n² = 4k² = 2(2k²) is even. One switches only when the direct route stalls.
To prove, for real a and b, "if a + b ≥ 2, then a ≥ 1 or b ≥ 1" by contrapositive, what must be proved?
- If a < 1 and b < 1, then a + b < 2
- If a < 1 or b < 1, then a + b < 2
- If a ≥ 1 or b ≥ 1, then a + b ≥ 2
- If a + b < 2, then a < 1 and b < 1
Show the answer
If a < 1 and b < 1, then a + b < 2
The contrapositive swaps and negates: by De Morgan, the negation of "a ≥ 1 or b ≥ 1" is "a < 1 and b < 1", and that of a + b ≥ 2 is a + b < 2. The proof is then immediate: add the two inequalities. Keeping the "or" forgets De Morgan; the other two sentences are the converse and the inverse.
A proof by induction has three steps: the …, the … and the conclusion.
Show the answer
A proof by induction has three steps: the base case, the inductive step and the conclusion.
The base case checks the starting value, the inductive step goes from n to n + 1 assuming the property for n, the conclusion states that it holds for every n from the starting value on.
Proof by contrapositive: what is it?
Show the answer
A proof of p ⇒ q that proves instead the equivalent implication ¬q ⇒ ¬p.
Useful when the conclusion is easier to negate than the hypothesis is to use: "3 divides n² ⇒ 3 divides n" is shown by assuming n = 3k + 1 or 3k + 2, hence n² = 3(3k² + 2k) + 1 or 3(3k² + 4k + 1) + 1, which is not a multiple of 3.