Training Set Theory & Logic Methods of Proof
4 / 5

Methods of Proof

24 min Set Theory & Logic

Methods of Proof

Direct Proof

To prove $p \to q$: assume $p$ is true, then use definitions and theorems to show $q$ is true.

Proof by Contrapositive

Instead of $p \to q$, prove $\lnot q \to \lnot p$ (logically equivalent).

Proof by Contradiction

Assume $\lnot p$. Derive a contradiction. Conclude $p$ must be true.

Mathematical Induction

To prove $P(n)$ for all $n \geq n_0$:

  1. Base case: Show $P(n_0)$
  2. Inductive step: Assume $P(k)$, prove $P(k+1)$
Example 1 — Direct Proof

Prove: If $n$ is even, then $n^2$ is even.

$n = 2k$ for some integer $k$. Then $n^2 = 4k^2 = 2(2k^2)$, which is even. ∎

Example 2 — Contradiction

Prove: $\sqrt{2}$ is irrational.

Assume $\sqrt{2} = a/b$ in lowest terms. Then $2b^2 = a^2$, so $a$ is even, $a = 2c$, so $2b^2 = 4c^2$, $b^2 = 2c^2$, so $b$ is even. Contradiction: not in lowest terms. ∎

Example 3 — Induction

Prove: $1+2+\cdots+n = \frac{n(n+1)}{2}$.

Base: $n=1$: $1 = 1(2)/2$ ✓. Step: Assume true for $k$. Then $1+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1) = \frac{(k+1)(k+2)}{2}$. ∎

Practice Problems

1. Prove directly: sum of two even integers is even.
2. Prove by contrapositive: if $n^2$ is odd then $n$ is odd.
3. Prove by contradiction: there is no largest integer.
4. Prove by induction: $1+3+5+\cdots+(2n-1) = n^2$.
5. What type of proof: assume $\lnot q$ to show $\lnot p$?
6. Direct proof: if $a \mid b$ and $b \mid c$, then $a \mid c$.
7. Why does induction need a base case?
8. Give a counterexample: "All primes are odd."
9. State the Well-Ordering Principle.
10. What is the inductive hypothesis?
11. Prove: $n^2+n$ is even for all integers $n$.
12. Is "proof by example" valid?
Show Answer Key

1. $2a + 2b = 2(a+b)$, even ∎

2. Contrapositive: $n$ even → $n^2$ even. $n=2k$, $n^2=4k^2=2(2k^2)$ ∎

3. If $N$ largest, then $N+1 > N$, contradiction ∎

4. Base: $1=1^2$. Step: $k^2+(2k+1)=(k+1)^2$ ∎

5. Proof by contrapositive

6. $b = am$, $c = bn = amn$, so $a \mid c$ ∎

7. Without it, the chain of implications has no starting point

8. $2$ is prime and even

9. Every non-empty subset of $\mathbb{N}$ has a least element

10. The assumption that $P(k)$ is true

11. $n^2+n = n(n+1)$; consecutive integers, one is even ∎

12. No — it only shows one case, not all

Quantifiers & Predicate Logic Placement Test Practice — Set Theory & Logic