Direct proof and proof by cases

Knowing exactly what a statement claims does not tell you how to establish it, and most statements worth proving are conditionals about every number of some kind.

The previous lesson gave the language: "for all", "there exists", and the rules for negating them. It closed on a claim it could state but not prove, that the square of every odd integer is one more than a multiple of $8$. This lesson supplies the method, the direct proof, and proves that claim along the way. Along the way it proves the division algorithm, which settles a question the first lesson left open (every integer is even or odd, and none is both), and it covers proofs by cases, inequalities, "if and only if", existence with and without a witness, and disproof by counterexample. It assumes the definitions of parity from the first lesson: an integer $n$ is even when $n=2k$ for some integer $k$, and odd when $n=2k+1$ for some integer $k$.

Assume the hypothesis, reach the conclusion

A conditional $P\Rightarrow Q$ is false in exactly one situation: $P$ true and $Q$ false. So to prove it, there is only one situation to rule out. Assume $P$, and derive $Q$ from it, using definitions, axioms and results already proved. If $P$ happens to be false, the conditional is true anyway, which is why a proof never has to say anything about that case. This is a direct proof: it starts at the hypothesis and walks forward to the conclusion.

Most theorems are also universal. "If an integer is divisible by $4$, it is even" means $\forall n\in \mathbb{Z}(4\text{divides}n\Rightarrow n\text{is even})$, and no list of cases can cover every $n$. The move that does is to let $n$ be arbitrary: name an integer $n$, assume nothing about it except the hypothesis, and reason about it. Whatever follows then follows for every integer, because nothing in the argument depended on which one was named. The proofs in the previous lesson that ended "as $x$ was arbitrary, the statement holds" used exactly this.

Together these fix the opening and closing lines of almost every proof in this course. The first sentence names the arbitrary object and states the hypothesis: "Let $n$ be an integer divisible by $4$." The last sentence states the conclusion and says which definition it satisfies: "so $n$ is even." Everything in between is the work, and each line of it must be justified by what came before. In outline, a proof of $\forall x(P(x)\Rightarrow Q(x))$ reads: let $x$ be arbitrary and suppose $P(x)$; then a chain of justified steps; therefore $Q(x)$; since $x$ was arbitrary, the statement holds for every $x$.

Once $n$ is named, the proof may not quietly assume it is positive, or prime, or small, unless the hypothesis says so. Checking $n=4$, $8$ and $12$ is not a proof about an arbitrary $n$; it is three examples. Nor may two objects share a letter they have not earned. If $a$ and $b$ are both even, then $a=2k$ and $b=2m$ for some integers $k$ and $m$; writing $a=2k$ and $b=2k$ would prove the claim only for $a=b$.

Finding a proof usually runs the other way. On scrap paper, write the conclusion out by its definition, so that "$n$ is even" becomes "$n=2\times$ (some integer)", and ask what would produce that expression. Then write the argument forwards, from hypothesis to conclusion, for the reader. The scrap paper is how you found the route; the proof is the route. A later section shows what goes wrong when the scrap paper is handed in as the proof.

Divisibility

For integers $a$ and $b$, $a$ divides $b$, written $a\mid b$, if there is an integer $k$ with $b=ak$. Equivalent phrasings are "$a$ is a divisor (or factor) of $b$" and "$b$ is a multiple of $a$". So $3\mid 12$ because $12=3\times 4$, and $-4\mid 12$ because $12=(-4)(-3)$. Every integer divides $0$, since $0=a\times 0$, and $1$ divides every integer. On the other hand $0\mid b$ only when $b=0$, since $0\times k$ is always $0$.

Two points about the notation catch almost everyone once. First, $a\mid b$ is a statement, true or false, while $\frac{b}{a}$ is a number: "$3\mid 12$" is true, and writing "$3\mid 12=4$" mixes a sentence with a calculation. Second, the order matters: $3\mid 12$ is true and $12\mid 3$ is false, because no integer $k$ gives $3=12k$. The definition avoids division on purpose: it uses only multiplication of integers, so it makes sense even for $a=0$.

The definition has the same shape as the definitions of even and odd, a "there is an integer $k$", and it is used in the same two ways. To use $a\mid b$, name the $k$ and write $b=ak$. To prove $a\mid b$, produce an integer $k$ with $b=ak$. Parity is a special case: an integer $n$ is even exactly when $2\mid n$.

Example. Prove that for all integers $a$, $b$ and $c$, if $a\mid b$ and $b\mid c$, then $a\mid c$.

Let $a$, $b$ and $c$ be integers with $a\mid b$ and $b\mid c$. By the definition of divisibility, there is an integer $k$ with $b=ak$, and there is an integer $m$ with $c=bm$. Substituting the first equation into the second gives $c=(ak)m=a(km)$. Since $k$ and $m$ are integers, $km$ is an integer. So $c$ is $a$ times an integer, and by the definition of divisibility, $a\mid c$.

The two quotients get different letters, $k$ and $m$, because nothing says they are equal. The scrap-paper route was short: the goal asked for $c$ in terms of $a$, and the hypotheses chain $c$ to $b$ and $b$ to $a$. This property, transitivity, lets divisibility pass along a chain: from $3\mid 12$ and $12\mid 60$, without any division, $3\mid 60$.

Now you. Prove that for all integers $a$, $b$ and $c$, if $a\mid b$ and $a\mid c$, then $a\mid (bx+cy)$ for all integers $x$ and $y$.

An expression $bx+cy$ with integer $x$ and $y$ is called an integer linear combination of $b$ and $c$, and the Now you says that a common divisor of two numbers divides every such combination. It is the most used fact about divisibility. Here it is at work: if $d$ divides both $n$ and $n+1$, then $d$ divides $(n+1)-n=1$, so $d$ is $1$ or $-1$. Two consecutive integers share no factor greater than $1$.

Divisibility also controls size. The next two facts are used constantly, and the second needs a small case split.

Proposition. Let $a$ and $b$ be integers.

(i) If $a\mid b$ and $b\ne 0$, then $|a|\le |b|$.

(ii) If $a\mid b$ and $b\mid a$, then $a=b$ or $a=-b$.

Proof. (i) Suppose $a\mid b$ and $b\ne 0$, so $b=ak$ for some integer $k$. If $k$ were $0$ then $b$ would be $0$, so $k\ne 0$, and a non-zero integer has $|k|\ge 1$. Therefore $|b|=|a||k|\ge |a|$. (The rule $|ak|=|a||k|$ is proved in the section on absolute value below.)

(ii) Suppose $a\mid b$ and $b\mid a$. If $a=0$, then $b\mid 0$ tells us nothing, but $a\mid b$ says $b=0\times k=0$, so $a=b$. If $a\ne 0$, then $b\ne 0$ as well, since $0\mid a$ would force $a=0$. Now (i) applies both ways: $|a|\le |b|$ and $|b|\le |a|$, so $|a|=|b|$, which means $a=b$ or $a=-b$. $\square$

Part (i) is the reason no integer greater than $1$ divides $1$, a fact the next lesson leans on in Euclid's proof that the primes never run out. Part (ii) shows why the sign needs care: $3\mid -3$ and $-3\mid 3$, and $3\ne -3$.

Three things divisibility does not do are worth knowing before they are needed. It does not cancel freely: $4\mid 2\times 6$ does not give $4\mid 6$. It does not distribute over sums in reverse: $a\mid b+c$ does not give $a\mid b$. And "$a\mid b$" is not "$a\le b$": $5\mid -10$ and $5\mid 0$ although $5$ exceeds both.

Working backwards, writing forwards

Inequalities show the gap between finding a proof and writing one most sharply. Take the claim that $x^2+y^2\ge 2xy$ for all real numbers $x$ and $y$. The natural scrap work starts from the goal: $x^2+y^2\ge 2xy$, so $x^2-2xy+y^2\ge 0$, so $(x-y{)}^2\ge 0$, which is true because squares are never negative. Every line is correct algebra and the claim is true. But as written, the argument runs from the claim to a known fact, so what it proves is the conditional "if $x^2+y^2\ge 2xy$, then $(x-y{)}^2\ge 0$", which is the wrong way round.

To see that an argument of this shape proves nothing, run it on a false claim. "Claim: $-2=2$. Proof: squaring both sides gives $4=4$, which is true." The algebra is flawless and the claim is false. The truth table of the conditional explains it: $P\Rightarrow Q$ is true when $P$ is false and $Q$ is true, so a false statement can imply a true one. Truth travels forwards along an implication, from hypothesis to conclusion, and never backwards. Reaching a true statement from the claim says nothing about the claim.

The repair is to run the scrap work in reverse. Let $x$ and $y$ be real numbers. The square of a real number is non-negative, so $(x-y{)}^2\ge 0$. Expanding, $x^2-2xy+y^2\ge 0$, and adding $2xy$ to both sides gives $x^2+y^2\ge 2xy$. Now each line follows from the one before, and the chain starts at a known fact. The reversal worked because every step of the scrap work could be undone; if one of them cannot, the scrap work has found no proof at all.

Example. Prove that for all non-negative real numbers $x$ and $y$, $\sqrt{xy}\le \frac{x+y}{2}$, with equality exactly when $x=y$.

The two sides are the geometric mean and the arithmetic mean of $x$ and $y$. On scrap paper: the goal is $2\sqrt{xy}\le x+y$, that is, $0\le x-2\sqrt{xy}+y$. Since $x$ and $y$ are non-negative, $x=(\sqrt{x}{)}^2$, $y=(\sqrt{y}{)}^2$ and $\sqrt{xy}=\sqrt{x}\sqrt{y}$, so the right-hand side is $(\sqrt{x}-\sqrt{y}{)}^2$. That suggests where the written proof should start.

Let $x$ and $y$ be non-negative real numbers. Then $\sqrt{x}$ and $\sqrt{y}$ are real numbers with $(\sqrt{x}{)}^2=x$, $(\sqrt{y}{)}^2=y$ and $\sqrt{x}\sqrt{y}=\sqrt{xy}$ (that square roots exist is proved in the lesson on the real numbers). The square of the real number $\sqrt{x}-\sqrt{y}$ is non-negative, so

Adding $2\sqrt{xy}$ to both sides and dividing by $2$ gives $\sqrt{xy}\le \frac{x+y}{2}$. Equality holds exactly when $(\sqrt{x}-\sqrt{y}{)}^2=0$, that is, when $\sqrt{x}=\sqrt{y}$, and since the square root of a non-negative number determines the number, that is exactly when $x=y$.

The hypothesis earned its place: for $x=y=-1$ the left side is $\sqrt{1}=1$ and the right side is $-1$. Geometrically, a rectangle with sides $x$ and $y$ has area $xy$, and the square with the same perimeter has side $\frac{x+y}{2}$, so the inequality says that the square encloses at least as much.

Now you. Prove that $x+\frac{1}{x}\ge 2$ for every positive real number $x$, and find when equality holds. Where does the proof use that $x$ is positive?

Division with remainder

Dividing $17$ by $5$ gives quotient $3$ and remainder $2$, since $17=5\times 3+2$. School arithmetic takes for granted that such a pair always exists and that there is only one. Both halves need proof, and both are needed here: existence gives every integer a remainder, and uniqueness makes the remainder a label that can be relied on.

The existence proof rests on one property of the natural numbers, which this course takes as basic.

The well-ordering principle. Every non-empty set of natural numbers has a least element.

It is not true of every number system. The integers have no least element, and neither do the positive rationals, since half of any positive rational is a smaller one. The principle holds equally for sets of non-negative integers: add $1$ to every member of such a set, take the least element of the resulting set of natural numbers, and subtract $1$ again. The induction lesson shows that well-ordering and the principle of induction are two forms of the same fact about $\mathbb{N}$.

Theorem (the division algorithm). Let $a$ and $b$ be integers with $b>0$. There are unique integers $q$ and $r$ with $a=bq+r$ and $0\le r<b$.

The number $q$ is the quotient and $r$ the remainder on dividing $a$ by $b$, and the remainder is written $a\text{mod}b$. Despite its traditional name, the result is a theorem, not a procedure, and its two parts, existence and uniqueness, get separate proofs.

Proof of existence. Let $S$ be the set of all non-negative integers of the form $a-bk$, where $k$ is an integer. First, $S$ is not empty. Take $k=-|a|$. Then $a-bk=a+b|a|\ge a+|a|\ge 0$, using $b\ge 1$ for the first inequality and $|a|\ge -a$ for the second. So by the well-ordering principle, $S$ has a least element $r$, and since $r$ is in $S$, $r=a-bq$ for some integer $q$. Then $a=bq+r$ and $r\ge 0$.

It remains to show $r<b$. Consider $r-b=a-b(q+1)$. It has the form $a-bk$, and it is smaller than $r$ because $b>0$. Since $r$ is the least element of $S$, the number $r-b$ is not in $S$, and a number of the form $a-bk$ can be missing from $S$ only by being negative. So $r-b<0$, that is, $r<b$.

Proof of uniqueness. Suppose $a=bq+r$ and $a=bq\prime +r\prime$, where $q$, $q\prime$, $r$, $r\prime$ are integers with $0\le r<b$ and $0\le r\prime <b$. The two representations play identical roles, so we may name them so that $r\le r\prime$. Then $0\le r\prime -r<b$, since $r\prime <b$ and $r\ge 0$. Subtracting the two equations gives $r\prime -r=b(q-q\prime )$, so $0\le b(q-q\prime )<b$, and dividing by the positive number $b$ gives $0\le q-q\prime <1$. The only integer in that range is $0$, so $q=q\prime$, and then $r=a-bq=a-bq\prime =r\prime$. $\square$

The condition $0\le r<b$ decides what happens for negative $a$: $-17=5\times (-4)+3$, so $-17\text{mod}5=3$. The pair $q=-3$, $r=-2$ also satisfies $-17=5q+r$, but $r$ is out of range, and uniqueness says $3$ is the only remainder in range.

Uniqueness gives a test for divisibility: $b\mid a$ exactly when $a\text{mod}b=0$. If the remainder is $0$, then $a=bq$. Conversely, if $a=bk$ for some integer $k$, then $a=bk+0$ is a representation with remainder in range, so by uniqueness the remainder is $0$.

It also pays the debt from the first lesson.

Corollary. Every integer is even or odd, and no integer is both.

Proof. Let $n$ be an integer. Dividing by $2$ gives $n=2q+r$ with $0\le r<2$, so $r=0$ or $r=1$. If $r=0$ then $n=2q$ is even, and if $r=1$ then $n=2q+1$ is odd. Now suppose $n=2k$ and $n=2m+1$ for integers $k$ and $m$. These are two representations $n=2q+r$ with remainders $0$ and $1$, both in range, so uniqueness would make $0=1$. Hence no integer is both. $\square$

The same argument with $b=3$ shows that every integer has exactly one of the forms $3k$, $3k+1$, $3k+2$, and in general, for $b>0$, every integer has exactly one of the forms $bk$, $bk+1$, and so on up to $bk+(b-1)$. That splits the integers into $b$ classes, and a proof about all integers can take them one at a time.

Proof by cases

Sometimes no single argument covers every value, but a few arguments do, each covering part. A proof by cases splits the hypothesis into possibilities that together exhaust it, and gives a direct proof in each. Its logic is the rule for "or": if $P_1\vee P_2$ holds, and $P_1\Rightarrow Q$ and $P_2\Rightarrow Q$ both hold, then $Q$ holds.

The commonest split is by parity, which the corollary above has now made legitimate. Take the claim that $n^2+n$ is even for every integer $n$.

Let $n$ be an integer. If $n$ is even, then $n=2k$ for some integer $k$, and $n^2+n=4k^2+2k=2(2k^2+k)$, which is even. If $n$ is odd, then $n=2k+1$ for some integer $k$, and $n^2+n=(4k^2+4k+1)+(2k+1)=2(2k^2+3k+1)$, which is even. Since every integer is even or odd, $n^2+n$ is even in every case.

A result once proved becomes a tool. Here is the previous lesson's open claim. Let $n$ be an odd integer, so $n=2k+1$ for some integer $k$. Then $n^2=4k^2+4k+1=4(k^2+k)+1$. By the result just proved, applied to the integer $k$, there is an integer $m$ with $k^2+k=2m$. So $n^2=8m+1$, and $8\mid (n^2-1)$. For $n=7$ that is $49=8\times 6+1$, and for $n=11$ it is $121=8\times 15+1$. No case split was needed in this proof; the one inside the lemma did the work.

Two things make a case split sound. The cases must between them cover everything: a proof about all integers that treats $n=3k$ and $n=3k+1$ has proved nothing about $5$. And each case must be proved using only what that case supplies, plus what was assumed for all of them. The cases may overlap harmlessly, for instance "$x\ge 0$" and "$x\le 0$" share $x=0$, but none may be missing.

Parity is division by $2$, and the division algorithm allows division by anything. Splitting by the remainder on division by $4$, or $3$, or $10$, is how most facts about squares and powers are proved.

Example. Prove that no integer of the form $4k+3$ is a sum of two squares of integers.

The claim says a certain thing does not exist, and the previous lesson turned such a claim into a universal one: $\neg \exists$ is $\forall \neg$. So the claim is that for all integers $x$ and $y$, the sum $x^2+y^2$ does not leave remainder $3$ on division by $4$, and that has a direct proof. First a lemma about single squares.

Lemma. The square of every integer has the form $4m$ or $4m+1$ for some integer $m$. Let $n$ be an integer. If $n$ is even, $n=2k$, and $n^2=4k^2$, which has the form $4m$ with $m=k^2$. If $n$ is odd, $n=2k+1$, and $n^2=4k^2+4k+1=4(k^2+k)+1$, which has the form $4m+1$.

Now let $x$ and $y$ be integers. By the lemma, $x^2=4s+e$ and $y^2=4t+f$ for some integers $s$ and $t$, where each of $e$ and $f$ is $0$ or $1$. Then $x^2+y^2=4(s+t)+(e+f)$, and $e+f$ is $0$, $1$ or $2$. In every case this writes $x^2+y^2=4q+r$ with $0\le r<4$ and $r\ne 3$. By the uniqueness of the remainder, the remainder of $x^2+y^2$ on division by $4$ is not $3$, so $x^2+y^2$ is not of the form $4k+3$.

So $3$, $7$, $11$, $15$, $19$ and every fourth number after them are never sums of two squares, a fact about infinitely many numbers and all pairs of integers, settled by four small cases. The converse fails: $21=4\times 5+1$ is not a sum of two squares, since none of $21-0$, $21-1$, $21-4$, $21-9$, $21-16$ is a square. Remainders give a necessary condition, not a sufficient one. For primes the full answer is a famous theorem: Fermat claimed in a letter to Marin Mersenne on Christmas Day 1640 that an odd prime is a sum of two squares exactly when it has the form $4k+1$, as $5=1+4$, $13=4+9$ and $29=4+25$ do. The Example is the easy half; Euler proved the hard half more than a century later.

Now you. Prove that the square of every integer has the form $3m$ or $3m+1$, and deduce that no integer of the form $3k+2$ is a perfect square.

Absolute value and the triangle inequality

The absolute value of a real number is itself defined by cases: $|x|=x$ if $x\ge 0$, and $|x|=-x$ if $x<0$. So $|5|=5$ and $|-5|=-(-5)=5$. Geometrically, $|x|$ is the distance from $x$ to $0$ on the number line, and $|x-y|$ is the distance between $x$ and $y$. Any claim about absolute values invites a proof by cases on signs, because in each case the bars can be replaced by something plain. The basic facts come first.

Lemma. For all real numbers $x$, $y$ and $a$:

(i) $|x|\ge 0$, with $|x|=0$ only when $x=0$;

(ii) $|-x|=|x|$ and $|xy|=|x||y|$;

(iii) $-|x|\le x\le |x|$;

(iv) $|x|\le a$ if and only if $-a\le x\le a$.

Proof. (i) If $x\ge 0$, then $|x|=x\ge 0$, and $|x|=0$ means $x=0$. If $x<0$, then $|x|=-x>0$.

(ii) For $|xy|=|x||y|$, split on signs. If $x\ge 0$ and $y\ge 0$, then $xy\ge 0$, so $|xy|=xy=|x||y|$. If $x<0$ and $y<0$, then $xy>0$, so $|xy|=xy=(-x)(-y)=|x||y|$. If $x\ge 0$ and $y<0$, then $xy\le 0$, so $|xy|=-xy=x(-y)=|x||y|$; here, when $xy=0$, both readings of $|xy|$ give $0$, so the formula $|xy|=-xy$ is still right. The case $x<0\le y$ is the same with $x$ and $y$ exchanged. Taking $y=-1$ gives $|-x|=|x||-1|=|x|$.

(iii) If $x\ge 0$, then $x=|x|$, and $-|x|=-x\le 0\le x$. If $x<0$, then $|x|=-x$, so $-|x|=x$, and $x<0<|x|$.

(iv) Suppose $|x|\le a$. By (iii), $x\le |x|\le a$ and $-a\le -|x|\le x$. Conversely, suppose $-a\le x\le a$. If $x\ge 0$, then $|x|=x\le a$. If $x<0$, then $|x|=-x\le a$, because $-a\le x$. $\square$

Part (iv) says that $|x|\le a$ means "$x$ lies within $a$ of $0$", and it is how inequalities with absolute values are unpacked in practice. The same proof with strict inequalities shows that $|x|<a$ exactly when $-a<x<a$.

Theorem (the triangle inequality). For all real numbers $x$ and $y$, $|x+y|\le |x|+|y|$.

First proof, by cases. Let $x$ and $y$ be real numbers. There are three cases, according to their signs.

If $x\ge 0$ and $y\ge 0$, then $x+y\ge 0$, so $|x+y|=x+y=|x|+|y|$.

If $x<0$ and $y<0$, then $x+y<0$, so $|x+y|=-(x+y)=(-x)+(-y)=|x|+|y|$.

If one is non-negative and the other negative, the claim is symmetric in $x$ and $y$, so we may suppose $x\ge 0>y$. Then $|x|=x$ and $|y|=-y$. Now $|x+y|$ is either $x+y$ or $-(x+y)$. In the first event, $x+y<x\le x-y=|x|+|y|$, since $y<0$. In the second, $-(x+y)=-x-y\le -y\le x-y=|x|+|y|$, since $x\ge 0$.

The three cases exhaust all pairs of real numbers, and the inequality holds in each. $\square$

Checking only the first two cases would prove nothing about $x=3$, $y=-5$, and that is where the inequality is strict: $|3+(-5)|=2$, while $|3|+|-5|=8$.

Second proof, from the lemma. Let $x$ and $y$ be real numbers. By (iii), $-|x|\le x\le |x|$ and $-|y|\le y\le |y|$. Adding these inequalities gives $-(|x|+|y|)\le x+y\le |x|+|y|$, and by (iv), with $a=|x|+|y|$, this says $|x+y|\le |x|+|y|$. $\square$

The second proof is shorter because the cases were paid for once, in the lemma, and then reused. That is the usual pattern: a case split belongs at the lowest level where it is needed, inside a lemma that is proved once, rather than repeated in every theorem that uses it.

The name comes from geometry. Replace $x$ by $x-y$ and $y$ by $y-z$, and the inequality becomes

for all real $x$, $y$ and $z$: the distance from $x$ to $z$ is at most the distance travelled by going through $y$. In the plane, it says that one side of a triangle is no longer than the other two together. Rearranged, it also gives a lower bound.

Corollary (the reverse triangle inequality). For all real numbers $x$ and $y$, $||x|-|y||\le |x-y|$.

Proof. Let $x$ and $y$ be real. Since $x=(x-y)+y$, the triangle inequality gives $|x|\le |x-y|+|y|$, so $|x|-|y|\le |x-y|$. Exchanging the roles of $x$ and $y$ gives $|y|-|x|\le |y-x|$, and $|y-x|=|x-y|$ by (ii), so $-|x-y|\le |x|-|y|$. Together, $-|x-y|\le |x|-|y|\le |x-y|$, and by (iv) this says $||x|-|y||\le |x-y|$. $\square$

These two inequalities are the everyday tools of analysis. The lesson on limits uses the triangle inequality to prove that a sequence cannot converge to two different limits and that the limit of a sum is the sum of the limits, and the reverse form shows that if $a_n\to L$ then $|a_n|\to |L|$.

Without loss of generality

The first proof of the triangle inequality treated the case $x\ge 0>y$ and skipped the case $y\ge 0>x$. That was honest because the statement is symmetric in $x$ and $y$: exchanging the two letters turns $|x+y|\le |x|+|y|$ into $|y+x|\le |y|+|x|$, which says the same thing. So the written argument for $x\ge 0>y$, with the letters exchanged throughout, is an argument for $y\ge 0>x$, and writing it out again would add nothing. The phrase for this move is without loss of generality, often shortened to WLOG: "without loss of generality, $x\ge 0>y$". The uniqueness half of the division algorithm used it too, when it named the two remainders so that $r\le r\prime$.

The phrase is a promise that the omitted cases follow from the treated one by a symmetry, and a reader is entitled to ask which symmetry. The test is mechanical: apply the symmetry to the whole statement, hypotheses included, and check that the same statement comes back. Good writing names it: "the statement is symmetric in $x$ and $y$, so we may assume $x\le y$."

Here is what failing the test looks like. "Claim: for all real numbers $x$ and $y$, $y-x\ge 0$. Proof: without loss of generality $x\le y$, and then $y-x\ge 0$." Exchanging $x$ and $y$ turns the claim into $x-y\ge 0$, a different statement, so the case $x>y$ was lost, not saved; the claim fails at $x=1$, $y=0$. Hypotheses must survive the exchange too. In "let $a$ be even and $b$ odd; without loss of generality $a\le b$", the exchange would make $b$ the even one, so the assumption is not free.

Used properly, the move saves a great deal. A statement symmetric in three variables allows "without loss of generality $x\le y\le z$", one ordering in place of six, and a statement unchanged when $n$ is replaced by $-n$ allows "without loss of generality $n\ge 0$". When the symmetry is not obvious, write the second case out.

If and only if

A biconditional $P⟺Q$ is the conjunction of two conditionals, $P\Rightarrow Q$ and $Q\Rightarrow P$, so a proof of it is two proofs. Label them, so the reader knows which is which: the forward direction ($\Rightarrow$) assumes $P$ and reaches $Q$, and the backward direction ($\Leftarrow$) assumes $Q$ and reaches $P$. The two may need quite different arguments, and either may be proved by any method, including a contrapositive, which proves $Q\Rightarrow P$ in the form $\neg P\Rightarrow \neg Q$.

The classic mistake is to prove one direction and believe both are done, usually because the easy direction was proved and the other looked like "the same thing backwards". Take "an integer $n$ is even if and only if $n^2$ is even". The forward direction is one line: $n=2k$ gives $n^2=2(2k^2)$. The backward direction is the claim this lesson cannot yet prove, as its last section explains.

A convention to know: definitions are written with "if" but mean "if and only if". "An integer is even if it is twice an integer" also means that an integer that is not twice an integer is not even. Theorems do not get this licence; in a theorem, "if" means only "if".

Example. Prove that for every integer $n$, $6\mid n$ if and only if $2\mid n$ and $3\mid n$.

Let $n$ be an integer.

($\Rightarrow$) Suppose $6\mid n$, so $n=6k$ for some integer $k$. Then $n=2(3k)$ and $n=3(2k)$, and $3k$ and $2k$ are integers, so $2\mid n$ and $3\mid n$.

($\Leftarrow$) Suppose $2\mid n$ and $3\mid n$, so $n=2k$ and $n=3m$ for some integers $k$ and $m$. The goal is a factor of $6$, and $6$ appears if each expression for $n$ is multiplied by the other divisor. Since $n=3n-2n$,

and $k-m$ is an integer, so $6\mid n$.

The backward direction is not a formality, and it does not hold for every pair of divisors: $2\mid 4$ and $4\mid 4$, but $8$ does not divide $4$. It worked because $3\times 1-2\times 1=1$, an integer combination of $2$ and $3$ equal to $1$. The same trick shows that whenever $ax+by=1$ for some integers $x$ and $y$, a number divisible by both $a$ and $b$ is divisible by $ab$. For $2$ and $4$ no such combination exists, since $2x+4y$ is always even.

Now you. Prove that for all integers $a$ and $b$, $a-b$ is even if and only if $a$ and $b$ have the same parity (both even or both odd).

Longer lists of equivalent statements are proved in a cycle. To show that $P$, $Q$ and $R$ are all equivalent, it is enough to prove $P\Rightarrow Q$, $Q\Rightarrow R$ and $R\Rightarrow P$: three proofs instead of six, since any one of the statements leads round the cycle to each of the others. Textbooks announce this as "the following are equivalent", and the order of the cycle is chosen to make each step easy.

Proving that something exists

A claim $\exists xP(x)$ is proved most plainly by producing an $x$ and checking $P(x)$. Such a proof is constructive. When the claim is $\forall k\exists n$, the $n$ may depend on $k$, so the proof must give a recipe that turns each $k$ into a suitable $n$.

Take the claim that for every natural number $k$ there are $k$ consecutive natural numbers, none of them prime. Let $k$ be a natural number and write $N=(k+1)!$, the product $1\times 2\times \cdots \times (k+1)$. Consider the $k$ numbers $N+2,N+3,\dots ,N+(k+1)$. Each has the form $N+j$ with $2\le j\le k+1$. Then $j\mid N$, since $j$ is one of the factors of $N$, and $j\mid j$, so $j\mid (N+j)$ because a common divisor divides a sum. As $2\le j<N+j$, the number $N+j$ has a divisor other than $1$ and itself, so it is not prime.

For $k=5$ the recipe gives $N=720$ and the run $722$ to $726$. It is far from the first such run, which is $24$ to $28$. A constructive proof must produce a witness, not the best one. The result also says something that sounds like the opposite of the next lesson's theorem that the primes never run out: there are gaps between consecutive primes as long as you like.

Many theorems claim more than existence: there is exactly one such object. That is two claims, and each needs its own proof. Existence is proved as above. Uniqueness is a universal claim, "any two objects with the property are equal", and is proved by letting two such objects be arbitrary and showing they coincide, as the division algorithm did with $(q,r)$ and $(q\prime ,r\prime )$. Showing that one candidate works and that no other one comes to mind proves existence only.

Some existence proofs never say which object works. Here is the classic, which assumes that $\sqrt{2}$ is irrational (the next lesson proves it).

Example. Prove that there are irrational numbers $a$ and $b$ with $a^b$ rational.

Consider the real number ${\sqrt{2}}^{\sqrt{2}}$. It is either rational or irrational. If it is rational, take $a=b=\sqrt{2}$: both are irrational and $a^b={\sqrt{2}}^{\sqrt{2}}$ is rational. If it is irrational, take $a={\sqrt{2}}^{\sqrt{2}}$ and $b=\sqrt{2}$, both irrational, and then $a^b=({\sqrt{2}}^{\sqrt{2}}{)}^{\sqrt{2}}={\sqrt{2}}^{\sqrt{2}\cdot \sqrt{2}}={\sqrt{2}}^2=2$, which is rational. In either case a suitable pair exists.

This is a proof by cases in which the cases are never resolved. It establishes that one of two pairs works without saying which, so it is non-constructive. The argument was published by Dov Jarden in 1953. The answer is known from outside the proof: a theorem proved independently by Aleksandr Gelfond and Theodor Schneider in 1934 implies that ${\sqrt{2}}^{\sqrt{2}}$ is irrational (indeed not the root of any polynomial with integer coefficients), so the second pair is the one.

Now you. Given that $\sqrt{2}$ and ${\log }_{2}9$ are irrational, give a constructive proof of the same claim.

Some mathematicians, the constructivists, reject non-constructive proofs, because they rest on the claim that every statement is true or false even when nobody can say which.

Examples, counterexamples and finite checks

A universal claim over an infinite domain is proved only by an argument about an arbitrary element, and no number of examples will do. It is disproved by a single counterexample: one value that satisfies the hypothesis and fails the conclusion. A disproof should state the counterexample and verify it, since a value that fails the hypothesis refutes nothing.

Many exercises, and most real questions, say "prove or disprove", and the first job is to decide which. Try examples first, and choose them to be awkward: $0$, $1$ and $-1$, negative numbers, equal values, the smallest case the hypothesis allows. If a counterexample appears, the question is settled. If none does, attempt a proof and watch where it strains: a step that fails usually points to the values where the claim fails.

Example. Prove or disprove each claim. (a) The sum of any three consecutive integers is divisible by $3$. (b) The sum of any four consecutive integers is divisible by $4$.

(a) Examples: $1+2+3=6$, $4+5+6=15$, $-1+0+1=0$, all divisible by $3$. So attempt a proof. Let $n$ be an integer; the three consecutive integers starting at $n$ are $n$, $n+1$ and $n+2$, and their sum is $3n+3=3(n+1)$. Since $n+1$ is an integer, $3$ divides the sum. The claim is true.

(b) The first example, $1+2+3+4=10$, already fails: $10=4\times 2+2$, so $4$ does not divide it. The claim is false, and this one counterexample disproves it. The attempted proof shows more. The sum $n+(n+1)+(n+2)+(n+3)=4n+6=4(n+1)+2$ always leaves remainder $2$, so the sum of four consecutive integers is never divisible by $4$. A counterexample settles the question; the algebra explains it.

Now you. Prove or disprove each claim, for all integers $a$, $b$ and $c$. (a) If $a\mid b+c$ and $a\mid b-c$, then $a\mid 2b$. (b) If $a\mid b+c$ and $a\mid b-c$, then $a\mid b$.

Checking examples is a proof in one situation: when the domain is finite, and every element is checked. The division algorithm can make an infinite domain finite. Take the claim that the last digit of every perfect square is $0$, $1$, $4$, $5$, $6$ or $9$. Let $n$ be an integer, and divide by $10$: $n=10q+r$ with $0\le r\le 9$. Then

so $n^2$ and $r^2$ leave the same remainder on division by $10$ (write $r^2=10t+s$ with $0\le s\le 9$ and apply uniqueness), and the remainder of a non-negative integer on division by $10$ is its last digit. So the last digit of $n^2$ is the last digit of one of $0,1,4,9,16,25,36,49,64,81$, which is one of $0,1,4,9,6,5,6,9,4,1$. That is ten checks, and they settle every integer, because the division algorithm proves that the ten remainders are all there are. So $1234567$ is not a square, and no search was needed to see it.

Where the direct route stalls

Every proof above ran forwards: unpack the hypothesis by its definition, then rearrange, split into cases or construct, until the conclusion's definition appears. Try the same on "for every integer $n$, if $n^2$ is even then $n$ is even". Let $n$ be an integer with $n^2$ even, so $n^2=2k$ for some integer $k$. The goal is $n=2\times$ (an integer), and all the hypothesis offers is $n=\pm \sqrt{2k}$, which is not visibly twice anything.

The hypothesis is about $n^2$ and the conclusion is about $n$, and information does not flow backwards through squaring. Cases on the parity of $n$ only help by ruling the odd case out, which is a different method in disguise. The statement is true, and the next lesson proves it by turning the conditional round, the same move that proves $\sqrt{2}$ irrational.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. Using only the definition of divisibility, decide which of these are true: $-6\mid 42$, $42\mid -6$, $0\mid 0$, $0\mid 5$, $11\mid 0$.

2. For each pair, find the integers $q$ and $r$ given by the division algorithm, so that $a=bq+r$ and $0\le r<b$: (a) $a=100$, $b=7$; (b) $a=-100$, $b=7$; (c) $a=5$, $b=12$; (d) $a=-1$, $b=12$.