Mathematical Proofs 1

Direct proof. Assume the hypothesis $P$. Apply definitions and known results to derive the conclusion $Q$.

Worked example. Prove: if $n$ is even, then $n^2$ is even.

Let $n = 2k$ for $k \in \mathbb{Z}$. Then $n^2 = 4k^2 = 2(2k^2)$, which is even.

Proof by contradiction. To prove $P$: assume $\neg P$. Derive a contradiction. Conclude $P$ must hold.

Worked example. Prove $\sqrt{2}$ is irrational.

Assume $\sqrt{2} = p/q$ in lowest terms ($p, q$ coprime). Then $2q^2 = p^2$, so $p^2$ is even, hence $p$ is even. Write $p = 2m$: $2q^2 = 4m^2 \Rightarrow q^2 = 2m^2$, so $q^2$ is even, $q$ even. But then $p, q$ share factor 2 — contradicting coprime. $\sqrt{2}$ is irrational.

Worked example. Prove there is no smallest positive rational.

Assume $r > 0$ is smallest. Then $r/2$ is positive and rational with $r/2 < r$ — contradiction.

Contrapositive. $P \Rightarrow Q$ is logically equivalent to $\neg Q \Rightarrow \neg P$. Sometimes the contrapositive is easier.

Worked example. Prove: if $n^2$ is odd, then $n$ is odd.

Contrapositive: if $n$ is even, then $n^2$ is even. Already proved above. Done.

Counterexample. To disprove 'for all $x$, $P(x)$', find ONE $x$ where $P(x)$ fails.

Worked example. Disprove: all primes are odd.

$2$ is prime and even. Counterexample found.

Worked example. Disprove: $n^2 + n + 41$ is prime for all $n \in \mathbb{N}$.

$n = 40$: $40^2 + 40 + 41 = 1681 = 41^2$. Composite. Counterexample.

Important — examples don't prove. Showing $n = 1, 2, 3$ work for a universal claim is NOT a proof. Must give general argument.