Contrapositive and Contradiction

Prove: if $n^2$ is odd then $n$ is odd. Directly, "$n^2$ odd" gives $n^2 = 2k + 1$ — and then what? Contrapositive: if $n$ is even, $n = 2m$, then $n^2 = 4m^2 = 2(2m^2)$ is even. Done. $\blacksquare$

Prove: if $xy$ is irrational, then $x$ is irrational or $y$ is irrational. The contrapositive negates both sides, and the negation of "$x$ irrational or $y$ irrational" is "$x$ rational AND $y$ rational". So we prove: if $x = p/q$ and $y = r/s$ are rational, then $xy = \dfrac{pr}{qs}$ is rational (with $qs \ne 0$). $\blacksquare$ The contrapositive turned a statement about an unknown irrational into a computation with fractions.

Prove: if $n^2 - 6n + 5$ is even, then $n$ is odd. Contrapositive: if $n$ is even, then $n^2 - 6n + 5$ is odd. With $n = 2k$: $n^2 - 6n + 5 = 4k^2 - 12k + 5 = 2(2k^2 - 6k + 2) + 1$, odd. $\blacksquare$

Suppose $\sqrt2 = p/q$ in lowest terms. Then $p^2 = 2q^2$, so $p^2$ is even, so $p$ is even (proved in What a Proof Is), $p = 2r$. Then $4r^2 = 2q^2$, $q^2 = 2r^2$, so $q$ is even too. Both even contradicts lowest terms. $\blacksquare$

Suppose there are finitely many: $p_1, \ldots, p_k$. Let $N = p_1\cdots p_k + 1$. $N > 1$ has a prime factor $p$; $p$ is some $p_i$; but $N$ leaves remainder $1$ on division by $p_i$, so $p_i \nmid N$. Contradiction. $\blacksquare$

Suppose $\log_2 3 = p/q$ with positive integers $p, q$ (it is positive since $3 > 1$). Then $2^{p/q} = 3$, and raising to the power $q$ gives $2^p = 3^q$. The left side is even (as $p \ge 1$) and the right side is odd. Contradiction. $\blacksquare$

Prove there are no integers $x, y$ with $x^2 - y^2 = 10$. Suppose there were. Then $(x - y)(x + y) = 10$. The two factors differ by $2y$, an even number, so they have the same parity. They cannot both be odd, since their product is even; so both are even, and then their product is divisible by $4$. But $4 \nmid 10$. Contradiction. $\blacksquare$

Suppose $\sqrt2 + \sqrt3 = t$ with $t$ rational. Squaring, $5 + 2\sqrt6 = t^2$, so $\sqrt6 = \dfrac{t^2 - 5}{2}$ is rational. Now show $\sqrt6$ is not: if $\sqrt6 = p/q$ in lowest terms, then $p^2 = 6q^2$ is even, so $p = 2a$; then $4a^2 = 6q^2$, so $2a^2 = 3q^2$, which makes $3q^2$ even and hence $q$ even. Both $p$ and $q$ even contradicts lowest terms. $\blacksquare$

Claim: if $5n + 4$ is odd, then $n$ is odd.

Direct. $n = (5n + 4) - 4n - 4 = (5n + 4) - 2(2n + 2)$, an odd number minus an even one, so odd.

Contrapositive. If $n = 2k$ then $5n + 4 = 10k + 4 = 2(5k + 2)$ is even.

Contradiction. Suppose $5n + 4$ is odd and $n = 2k$ is even. Then $5n + 4 = 2(5k + 2)$ is even — impossible.

The third is the second with extra words; when a contradiction proof never uses $P$ until the last line, rewrite it as a contrapositive.

Claim: there is no smallest positive rational number. Suppose $r$ were one. Then $r/2$ is rational, positive, and smaller than $r$. Contradiction. $\blacksquare$ The negation handed us a specific object, the supposed smallest one, and we broke it by halving; neither a direct proof nor a contrapositive has anything to start from.