P4.1 - Proof

A proof by contradiction begins by assuming the exact negation of the statement to be proved. If valid deductions from that assumption force an impossibility or conflict with a given condition, the assumption is false and the original statement must be true.

Use four explicit moves: (1) state the contradictory assumption; (2) translate it into algebra, parity, factors or an inequality; (3) derive a named contradiction; (4) reject the assumption and state the original conclusion. For an implication ‘if P, then Q’, assume P is true and Q is false—not merely that P is false.

For $\sqrt2$, assume $\sqrt2=a/b$ where integers $a,b$ have no common factor. Then $a^2=2b^2$, so $a$ is even; write $a=2k$. Now $4k^2=2b^2$, hence $b^2=2k^2$ and $b$ is even. Thus $a$ and $b$ share factor 2, contradicting lowest terms. Therefore $\sqrt2$ is irrational.

For infinitely many primes, assume the complete list is $p_1,\ldots,p_n$ and form $N$ above. Dividing $N$ by any listed prime leaves remainder 1. Yet $N>1$ has a prime divisor, which is therefore absent from the supposedly complete list. This contradiction proves that there are infinitely many primes.