Proof and Logic

How mathematics establishes that something is true: the logic of statements and quantifiers, the standard methods of proof, and the sets, functions and relations every later course is written in.

Why prove anything

A pattern that holds in every case anyone has checked feels like a fact, and in mathematics it can still be false.

This lesson starts with three such patterns, each of which survived far longer than anyone would need to be convinced, and each of which failed. They are the reason mathematics settles its claims by proof rather than by evidence. The second half of the lesson says what a proof is, why it starts from definitions, and writes the first few out in full. It assumes school algebra and nothing else.

Forty primes, then a square

In 1772 Euler noticed that the expression $n^{2} + n + 41$ produces primes with remarkable persistence. At $n = 0$ it gives $41$ , then $43$ , $47$ , $53$ , $61$ , $71$ , and every value up to $n = 39$ , where it gives $1601$ , is prime. Forty consecutive successes is more than most people would ask before believing a rule.

At $n = 40$ the value is $1681$ , and $1681 = 41^{2}$ . Once it has happened it is easy to see why. Write the expression at $n = 40$ with the first two terms grouped: $40^{2} + 40 = 40 (40 + 1) = 40 \times 41$ , so the whole thing is $40 \times 41 + 41 = 41 \times 41$ .

The same thought shows that $n = 41$ fails too: every term of $41^{2} + 41 + 41$ is a multiple of $41$ , and the value is $1763 = 41 \times 43$ . The structure that breaks the pattern was visible in the formula from the start. The forty checks established forty facts and said nothing about the forty-first, because nothing in them said why the values were prime. A check tells you what happened, not what must happen.

Doubling that stops at thirty-one

Place points on a circle and join every pair with a straight chord, taking care that no three chords pass through the same interior point. Count the regions the chords cut the disc into. One point makes no chord, so there is $1$ region. Two points give one chord and $2$ regions. Three points give a triangle and $4$ regions, four points give $8$ , and five give $16$ .

The sequence $1, 2, 4, 8, 16$ is as clean a pattern as mathematics offers, and the obvious guess is that six points give $32$ . They give $31$ , and no arrangement of six points does better. (If the six points are the corners of a regular hexagon, the three long diagonals meet at the centre, which breaks the rule about three chords, and the count drops to $30$ .)

Here too the failure makes sense once the right quantity is counted. Add the chords one at a time. A new chord that crosses $k$ chords already drawn passes through $k + 1$ existing regions and splits each of them in two, so it adds $k + 1$ regions. Summing over all the chords, the total is $1$ for the starting disc, plus $1$ for each chord, plus $1$ for each crossing point. With $n$ points there are $(\binom{n}{2})$ chords (one per pair of points, so $n (n - 1) / 2$ ), and every choice of four points produces exactly one crossing (where the diagonals of their quadrilateral meet), so there are $(\binom{n}{4})$ crossings. For six points that is $1 + 15 + 15 = 31$ , and for seven it is $1 + 21 + 35 = 57$ , nowhere near $64$ .

The powers of two were a coincidence of small numbers: $2^{n - 1}$ and $1 + (\binom{n}{2}) + (\binom{n}{4})$ agree up to five points and then part company. The argument rests on the sentence "every choice of four points produces exactly one crossing", and a careful reader should want that sentence justified. Justifying sentences like it is what this course is about.

Nine hundred million confirmations

Perhaps people should simply check more. The third pattern answers that. Count the prime factors of a whole number with repeats, so that $12 = 2 \times 2 \times 3$ has three and $9 = 3 \times 3$ has two, and give $1$ zero. Among the numbers from $1$ to $10$ , five ( $2$ , $3$ , $5$ , $7$ and $8$ ) have an odd number of prime factors, and up to $100$ it is fifty-one.

In 1919 George Pólya conjectured that this always happens: for every $n$ greater than $1$ , at least half of the numbers from $1$ to $n$ have an odd number of prime factors. It was checked by hand and later by machine over enormous ranges, and it held for every $n$ anyone tested.

In 1958 Brian Haselgrove proved that it fails somewhere, by an argument that showed a counterexample exists without producing one. In 1980 Minoru Tanaka found the first one by computer. It is 906,150,257. Up to that number, 453,075,128 have an odd number of prime factors and 453,075,129 have an even number, so the odd ones are outnumbered by one. Every $n$ from $2$ to 906,150,256 obeys the conjecture.

A claim about every natural number is a claim about infinitely many cases, and any finite collection of checks, however large, leaves infinitely many unchecked. Nine hundred million confirmations are exactly as far from infinity as forty. Evidence, which is how the empirical sciences rightly work, cannot establish a mathematical claim of this kind. It can refute one: a single failure, such as $1681$ or Tanaka's number, disposes of a claim about every case completely.

What a proof is

A proof is a finite chain of statements, each of which is justified by one of three things: a definition, an axiom (a statement taken as a starting point and not argued for), or a result that has already been proved. The last statement in the chain is the claim. Because every link is justified, the claim cannot fail in any case the chain covers, and one chain can cover infinitely many cases.

A proof is not an argument that makes the claim plausible, and it is not a picture: the chords on a circle suggested $32$ and delivered $31$ . What a proof offers is checkability. A reader can take each line, ask what justifies it, and find the answer in a definition, an axiom or an earlier theorem. If every line survives that question, the reader has no choice but to accept the conclusion, without needing to trust the writer.

This is the trade mathematics makes. Its conclusions hold only under the stated assumptions, and within them they are permanent. Euclid's proof that there are infinitely many primes, written around 300 BCE, is as correct now as it was then, which no measurement from that century can claim.

Proofs in this course are written in sentences. Symbols appear where they are clearer, but words such as "suppose", "since" and "so" carry the argument, because they say which statement follows from which. A column of bare equations often hides exactly the step that needed justifying.

Definitions do the work

A proof starts from definitions. This is the habit that most separates proof from school mathematics: a word such as "even" stops being something you recognise and becomes an exact statement you can use.

An integer $n$ is even if there is an integer $k$ with $n = 2 k$ . An integer $n$ is odd if there is an integer $k$ with $n = 2 k + 1$ . Everything this lesson proves about parity comes from those two sentences and the ordinary rules of algebra for integers, such as the fact that sums and products of integers are integers and that multiplication distributes over addition.

The definition settles questions that recognition leaves vague. Is $0$ even? Yes, since $0 = 2 \times 0$ . Is $- 3$ odd? Yes, since $- 3 = 2 \times (- 2) + 1$ . The school test "the last digit is $0$ , $2$ , $4$ , $6$ or $8$ " agrees, but it is a fact about base-ten notation and would need its own proof before it could be used.

Notice also what the definitions do not say. Nothing in them states that every integer is even or odd, or that no integer is both. Both are true, but both need proofs of their own, which rest on division with remainder, and a proof that quietly relies on them before they are proved is incomplete.

The word "some" in the definitions matters too. To show a number is even you must produce the $k$ , or show that one exists. To use the fact that a number is even you may name its $k$ and work with it. That is the whole mechanism of the proofs below.

A first proof

The sum $3 + 5 = 8$ is even, and so is $7 + 11 = 18$ , but those are evidence. The goal is an argument that covers every pair at once.

Example. Prove that the sum of two odd integers is even.

Let $a$ and $b$ be odd integers. By the definition of odd, there is an integer $k$ with $a = 2 k + 1$ , and there is an integer $m$ with $b = 2 m + 1$ . Then $a + b = (2 k + 1) + (2 m + 1) = 2 k + 2 m + 2 = 2 (k + m + 1)$ . Since $k$ and $m$ are integers, $k + m + 1$ is an integer. So $a + b$ is twice an integer, and by the definition of even, $a + b$ is even.

Three details are worth copying. It names arbitrary odd integers, so nothing is assumed about them except that they are odd. It uses two different letters, $k$ and $m$ , because $a$ and $b$ need not be equal; one letter would have proved the claim only for a number added to itself. And its last sentence names the definition it has satisfied, so the reader sees the chain close.

Now you. Prove that the sum of an even integer and an odd integer is odd.

Answer

Let $a$ be an even integer and $b$ an odd integer. By the definitions, there is an integer $k$ with $a = 2 k$ and an integer $m$ with $b = 2 m + 1$ . Then $a + b = 2 k + 2 m + 1 = 2 (k + m) + 1$ . Since $k + m$ is an integer, $a + b$ has the form twice an integer plus one, so by the definition of odd, $a + b$ is odd.

Example. Prove that the product of two odd integers is odd.

Let $a$ and $b$ be odd integers, so that $a = 2 k + 1$ and $b = 2 m + 1$ for some integers $k$ and $m$ . Then $a b = (2 k + 1) (2 m + 1) = 4 k m + 2 k + 2 m + 1 = 2 (2 k m + k + m) + 1$ . Since $k$ and $m$ are integers, so is $2 k m + k + m$ . Therefore $a b$ is twice an integer plus one, and by the definition of odd, $a b$ is odd.

Now you. Prove that if $a$ is an even integer and $b$ is any integer, then $a b$ is even.

Answer

Let $a$ be an even integer and $b$ any integer. By the definition of even, there is an integer $k$ with $a = 2 k$ . Then $a b = 2 k b = 2 (k b)$ . Since $k$ and $b$ are integers, $k b$ is an integer, so $a b$ is twice an integer and, by the definition of even, $a b$ is even.

Proving that a pattern fails

Proof can also show that a pattern fails, and why, far beyond a single counterexample. For this the definitions needed are those of prime and composite: an integer greater than $1$ is prime if its only positive divisors are $1$ and itself, and composite if it is the product of two integers each greater than $1$ .

Example. Prove that $n^{2} + n + 41$ is composite whenever $n$ is a positive multiple of $41$ .

Let $n$ be a positive multiple of $41$ , so that $n = 41 m$ for some integer $m \geq 1$ . Then $n^{2} + n + 41 = 41^{2} m^{2} + 41 m + 41 = 41 (41 m^{2} + m + 1)$ . The first factor, $41$ , is greater than $1$ . Since $m \geq 1$ , the second factor is at least $41 + 1 + 1 = 43$ , so it is greater than $1$ as well. Therefore $n^{2} + n + 41$ is a product of two integers each greater than $1$ , and by definition it is composite.

No amount of checking could do this: the proof shows Euler's expression fails at $n = 41$ , $82$ , $123$ and infinitely many other values, and why.

Now you. Prove that $n^{2} + n + 41$ is composite whenever $n = 41 m + 40$ for some integer $m \geq 0$ . (At $m = 0$ this is the failure at $n = 40$ .)

Answer

Let $n = 41 m + 40$ with $m \geq 0$ an integer. Expanding, $n^{2} = 1681 m^{2} + 3280 m + 1600$ , so $n^{2} + n + 41 = 1681 m^{2} + 3321 m + 1681 = 41 (41 m^{2} + 81 m + 41)$ . The factor $41$ is greater than $1$ , and since $m \geq 0$ the second factor is at least $41$ , so it is greater than $1$ too. So $n^{2} + n + 41$ is a product of two integers each greater than $1$ , and is composite.

What the proofs needed

Every proof in this lesson began by working out what its claim actually asserted. "The sum of two odd integers is even" turned out to mean: for any integers $a$ and $b$ , if $a$ is odd and $b$ is odd, then $a + b$ is even. Hidden in that ordinary sentence are an "if ... then" and a "for any", and the proof's shape came from them: take arbitrary $a$ and $b$ , assume they are odd, and reach the conclusion. Refuting Pólya's conjecture needed the same precision in reverse: knowing that one $n$ with fewer than half is enough means knowing exactly what the negation of "for every $n$ " says.

So statements have to be read exactly: "and", "or", "not" and "if ... then" do not always mean in mathematics what they mean in conversation. The next lesson fixes those meanings, and the conditional, the "if ... then" that every theorem is written in, turns out to mean something that surprises almost everyone the first time.

Statements and connectives

The words that build mathematical claims, "not", "and", "or", "if ... then", mean something slightly different in conversation every time they are used, and a proof cannot rest on a word whose meaning moves.

The previous lesson unpacked "the sum of two odd integers is even" into a claim with an "if ... then" inside it, and its proofs worked only because it was clear what that claim asserted. This lesson makes that clarity routine. It says which sentences can be true or false, fixes the meaning of each connective with a truth table, and spends most of its time on the conditional, the connective every theorem is written in. It assumes school algebra and the definitions of even and odd: an integer is even when it equals $2 k$ for some integer $k$ , and odd when it equals $2 k + 1$ .

Statements

A statement is a sentence that is either true or false. " $91$ is prime" is a statement, and a false one, since $91 = 7 \times 13$ . " $2^{10} > 1000$ " is a true one, since $2^{10} = 1024$ . What matters is that the sentence has a truth value, not that anyone knows it. "Every even integer greater than $2$ is the sum of two primes" is Goldbach's conjecture, proposed in a letter to Euler in 1742 and checked by computer for every even number up to $4 \times 10^{18}$ . Nobody knows whether it is true, but it is certainly one or the other, so it is a statement.

Plenty of mathematical sentences are not statements. "Is $91$ prime?" is a question and "Let $n = 91$ " is an instruction. The subtler case is a sentence with a free variable, such as " $x > 3$ ", which is true when $x = 5$ , false when $x = 1$ , and has no truth value until $x$ is pinned down. Such a sentence is an open sentence. Turning open sentences into statements is the job of the next lesson; this one works with statements, or with open sentences read for one value of the variable at a time.

Statements are written with capital letters, $P$ , $Q$ , $R$ , so that the structure of a claim can be seen apart from its content. The rules below depend only on whether each part is true or false, never on what it says.

Not, and, or

Each connective is defined by saying, for every combination of truth values of its parts, whether the compound is true. With two parts there are four combinations, and a truth table lists them, one per row.

Negation, written $\neg P$ and read "not $P$ ", is true exactly when $P$ is false. Conjunction, $P \land Q$ , read " $P$ and $Q$ ", is true exactly when both parts are true. Disjunction, $P \lor Q$ , read " $P$ or $Q$ ", is true when at least one part is true, including when both are.

$P$	$Q$	$\neg P$	$P \land Q$	$P \lor Q$
T	T	F	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	F

The last column is the one that departs from conversation. "Soup or salad" on a menu usually means one but not both. In mathematics "or" is always inclusive, and the sentences mathematicians write show why. The rule "if $a b = 0$ then $a = 0$ or $b = 0$ " must not exclude $a = b = 0$ , and " $n$ is divisible by $2$ or by $3$ " is true of $6$ . When the exclusive sense is wanted it is spelt out: " $P$ or $Q$ but not both", which is $(P \lor Q) \land \neg (P \land Q)$ .

The negation of a statement is whatever is true in exactly the cases where the statement is false, and ordinary language often reaches for an opposite instead. The negation of " $x > 3$ " is " $x \leq 3$ ", not " $x < 3$ ": at $x = 3$ both " $x > 3$ " and " $x < 3$ " are false, so the second cannot be the negation of the first. And " $x \leq 3$ " is itself a disjunction, " $x < 3$ or $x = 3$ ".

Negating a compound statement

Two compound statements are equivalent when they have the same truth value in every row of their truth table. Since the table lists every case, checking the rows is a complete proof. Note that $\neg (P \land Q)$ , which denies the whole conjunction, is a different thing from $\neg P \land Q$ , where $\neg$ applies only to $P$ .

The most useful equivalences say how to negate an "and" or an "or". To deny that two things both hold is to say that at least one fails, and to deny that at least one holds is to say that both fail. These are De Morgan's laws, after Augustus De Morgan, who stated them in 1847, and they are what a proof needs whenever it must say what the failure of a condition looks like.

Example. Show that $\neg (P \land Q)$ and $\neg P \lor \neg Q$ are equivalent, and use this to negate " $x > 0$ and $x < 5$ ".

Compute both columns in each of the four rows.

$P$	$Q$	$P \land Q$	$\neg (P \land Q)$	$\neg P$	$\neg Q$	$\neg P \lor \neg Q$
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

The fourth and seventh columns agree in every row, so the two statements are equivalent. Now let $P$ be " $x > 0$ " and $Q$ be " $x < 5$ ". The negation of $P \land Q$ is $\neg P \lor \neg Q$ , and the negations of the parts are " $x \leq 0$ " and " $x \geq 5$ ". So the negation of " $x > 0$ and $x < 5$ " is " $x \leq 0$ or $x \geq 5$ ".

Now you. Show that $\neg (P \lor Q)$ and $\neg P \land \neg Q$ are equivalent, and use this to negate " $x < 0$ or $x > 1$ ".

Answer

$P \lor Q$ is false only in the row where $P$ and $Q$ are both false, so $\neg (P \lor Q)$ is true in that row and false in the other three. $\neg P \land \neg Q$ is true only when $\neg P$ and $\neg Q$ are both true, which is the same row. The columns agree in all four rows, so the statements are equivalent. The negation of " $x < 0$ or $x > 1$ " is therefore " $x \geq 0$ and $x \leq 1$ ", that is, $0 \leq x \leq 1$ .

The common error is to negate the parts and leave the connective alone. "Not ( $x > 0$ and $x < 5$ )" is not " $x \leq 0$ and $x \geq 5$ ", which no number satisfies. Negating a compound always turns "and" into "or" or the reverse.

The conditional

The fourth connective is the conditional, $P \Rightarrow Q$ , read "if $P$ then $Q$ " or " $P$ implies $Q$ ". $P$ is the hypothesis and $Q$ the conclusion. The fifth is the biconditional, $P ⟺ Q$ , read " $P$ if and only if $Q$ ", which is true when $P$ and $Q$ have the same truth value.

$P$	$Q$	$P \Rightarrow Q$	$P ⟺ Q$
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	T

The first two rows of the conditional need no defence. "If $n$ is divisible by $4$ , then $n$ is even" is kept by a number divisible by $4$ that is even, and would be broken by one divisible by $4$ that is odd: a true hypothesis with a false conclusion is exactly what it means for an implication to fail.

The last two rows are the ones that surprise. Whenever the hypothesis is false, the conditional is true, whatever the conclusion, so "if $2 + 2 = 5$ , then $7$ is even" is a true statement. A conditional true because its hypothesis is false is called vacuously true. It looks like a convention, and slightly at odds with sense, but no other choice would let mathematics state its theorems.

Why a false hypothesis gives a true conditional

Take a theorem nobody doubts: for every integer $n$ , if $n$ is divisible by $4$ , then $n$ is even. It claims something about every integer, so it is true only if each instance, one conditional per integer, is true. At $n = 8$ the instance has a true hypothesis and a true conclusion. At $n = 6$ the hypothesis is false and the conclusion true. At $n = 7$ both are false. If either of the last two instances counted as false, this theorem would be false, and so would nearly every theorem of the form "if ... then", since nearly any hypothesis fails for some values. Those rows have to be true for mathematics to be sayable at all.

Nothing else could go in them either. Making both rows false turns $P \Rightarrow Q$ into $P \land Q$ , so the theorem would assert that $n$ is divisible by $4$ . Making only the false-true row false turns it into $P ⟺ Q$ , so the theorem would claim every even number is divisible by $4$ , which $6$ refutes. Making only the false-false row false gives a column identical to $Q$ , and the hypothesis would do nothing.

The conditional asserts no connection between its parts: "if $2 + 2 = 5$ , then $7$ is even" is true though its halves are unrelated. In mathematics that costs nothing, because the connection is what the proof supplies. The table also tells a proof where to look. A conditional can fail only in the row where $P$ is true, so to prove $P \Rightarrow Q$ it is enough to assume $P$ and show that $Q$ follows, which is what the previous lesson did when it began "let $a$ and $b$ be odd".

That same row gives the negation. Since $P \Rightarrow Q$ is false only when $P$ is true and $Q$ false, its negation is $P \land \neg Q$ . The negation of an implication is not another implication: it says the hypothesis holds and the conclusion fails, which is what a counterexample exhibits.

Example. Negate "if $n$ is prime, then $n$ is odd", decide whether the conditional is true for $n = 2$ , $n = 9$ and $n = 7$ , and say what this shows.

The negation is " $n$ is prime and $n$ is even", since $\neg (P \Rightarrow Q)$ is $P \land \neg Q$ . For $n = 2$ the hypothesis is true and the conclusion false, so the conditional is false, and its negation is true: $2$ is prime and even. For $n = 9$ the hypothesis is false, since $9 = 3 \times 3$ , so the conditional is vacuously true. For $n = 7$ both parts are true and so is the conditional. The claim "every prime is odd" is therefore false, and $n = 2$ is the counterexample: an integer at which the negation holds.

Now you. Negate "if $x > 2$ , then $x^{2} > 4$ ", and decide whether the conditional is true for $x = 3$ , $x = - 3$ and $x = 1$ .

Answer

The negation is " $x > 2$ and $x^{2} \leq 4$ ". At $x = 3$ both $x > 2$ and $x^{2} = 9 > 4$ hold, so the conditional is true. At $x = - 3$ the hypothesis fails, so the conditional is vacuously true, even though $x^{2} = 9 > 4$ . At $x = 1$ the hypothesis and the conclusion both fail, and again the conditional is vacuously true. None of the three makes the negation true.

Converse, inverse and contrapositive

Swapping and negating the parts of $P \Rightarrow Q$ gives three new conditionals: the converse $Q \Rightarrow P$ , the inverse $\neg P \Rightarrow \neg Q$ , and the contrapositive $\neg Q \Rightarrow \neg P$ . Their tables settle which say the same thing as the original.

$P$	$Q$	$P \Rightarrow Q$	$\neg Q \Rightarrow \neg P$	$Q \Rightarrow P$	$\neg P \Rightarrow \neg Q$
T	T	T	T	T	T
T	F	F	F	T	T
F	T	T	T	F	F
F	F	T	T	T	T

The contrapositive agrees with the original in every row, so the two are equivalent. The converse and inverse agree with each other and differ from the original in the middle two rows. So a proof of $\neg Q \Rightarrow \neg P$ is a proof of $P \Rightarrow Q$ , which a later lesson turns into a method, while a proof of $P \Rightarrow Q$ says nothing about $Q \Rightarrow P$ . Treating it as if it did is the commonest logical error in student proofs.

Example. Write the converse, inverse and contrapositive of "if $n$ is divisible by $6$ , then $n$ is divisible by $3$ ", and decide which are true for every integer $n$ .

The statement is true: if $n = 6 k$ for an integer $k$ , then $n = 3 (2 k)$ , and $2 k$ is an integer. The converse is "if $n$ is divisible by $3$ , then $n$ is divisible by $6$ ", which is false, since $n = 3$ is divisible by $3$ and not by $6$ . The inverse is "if $n$ is not divisible by $6$ , then $n$ is not divisible by $3$ ", and $n = 3$ refutes it too, as it must, being equivalent to the converse. The contrapositive is "if $n$ is not divisible by $3$ , then $n$ is not divisible by $6$ ", which is true because it is equivalent to the original.

Now you. For real numbers $x$ , write the converse, inverse and contrapositive of "if $x > 3$ , then $x^{2} > 9$ ", and decide which are true.

Answer

The statement is true: if $x > 3$ then $x$ is positive, so $x^{2} = x \cdot x > 3 x > 3 \cdot 3 = 9$ . The converse, "if $x^{2} > 9$ then $x > 3$ ", is false, since $x = - 4$ gives $x^{2} = 16 > 9$ with $x < 3$ . The inverse, "if $x \leq 3$ then $x^{2} \leq 9$ ", is false by the same $x = - 4$ . The contrapositive, "if $x^{2} \leq 9$ then $x \leq 3$ ", is true, being equivalent to the original.

Necessary, sufficient and only if

When $P \Rightarrow Q$ holds, $P$ is a sufficient condition for $Q$ : having $P$ guarantees $Q$ . And $Q$ is a necessary condition for $P$ : without $Q$ there is no $P$ , which is the contrapositive read aloud. Divisibility by $6$ is sufficient for divisibility by $3$ , and divisibility by $3$ is necessary for divisibility by $6$ . These are one fact seen from its two ends.

" $P$ only if $Q$ " also means $P \Rightarrow Q$ . "Only" marks the necessary condition, which is the conclusion: " $n$ is divisible by $4$ only if $n$ is even" says divisibility by $4$ cannot happen without evenness. By contrast " $P$ if $Q$ " means $Q \Rightarrow P$ . The two are opposite, so together they make "if and only if": $P ⟺ Q$ is the same as $(P \Rightarrow Q) \land (Q \Rightarrow P)$ , a condition both necessary and sufficient. That is why proving an "if and only if" takes two proofs, one per direction.

One convention catches every newcomer. Definitions are written with "if", as in "an integer $n$ is even if $n = 2 k$ for some integer $k$ ", but a definition is always read as "if and only if". The previous lesson used its definitions in both directions, producing a $k$ from an even number and concluding evenness from a $k$ , and was right to.

What connectives cannot say

The five connectives are now fixed, and the negation of each compound can be written down mechanically. Yet the argument for the conditional's table used something no connective contains. "For every integer $n$ , if $n$ is divisible by $4$ , then $n$ is even" is not a conditional between two statements, since " $n$ is divisible by $4$ " is an open sentence; the phrase "for every integer $n$ " is what made the whole a true statement. Refuting "every prime is odd" needed the opposite phrase: there is a prime that is even. Nearly every theorem is about all numbers or some number, and neither "all" nor "some" can be built from the five connectives. The next lesson adds them, with rules for negating them that turn "not every" into "some fails".

Quantifiers

Nearly every theorem is a claim about all numbers of some kind or about at least one of them, and the connectives of the previous lesson have no way to say either.

That lesson fixed the meaning of "not", "and", "or", "implies" and "if and only if", and closed on a sentence they could not build: "for every integer $n$ , if $n$ is divisible by $4$ , then $n$ is even". This lesson adds "for every" and "there exists", gives the rules for negating them, and shows that their order changes what is said. It ends with the definition of a limit, negated symbol by symbol.

Open sentences and the two quantifiers

A sentence such as " $x^{2} > 4$ " has no truth value until $x$ is fixed: it is true when $x = 3$ and false when $x = 1$ . Such an open sentence is written $P (x)$ , so that $P (3)$ is a true statement and $P (1)$ a false one.

Two quantifiers turn an open sentence into a statement. The universal quantifier $\forall x$ , read "for all $x$ ", makes $\forall x P (x)$ , which is true when $P (x)$ is true for every value of $x$ . The existential quantifier $\exists x$ , read "there exists an $x$ ", makes $\exists x P (x)$ , which is true when $P (x)$ is true for at least one value.

"At least one" is the exact reading of $\exists$ . It does not mean exactly one, and it does not hint that not all: "there is an even integer" is true, though there are infinitely many. As with inclusive "or", the weaker reading is the default.

Often the quantifier is not written at all. "If $n$ is divisible by $4$ , then $n$ is even" is printed as a theorem with no "for all", and every reader supplies "for every integer $n$ ". A proof has to put it back, because "every $n$ " and "some $n$ " call for different proofs.

The domain is part of the claim

"For all $x$ " always means all $x$ in some collection, the domain, and changing the domain changes the claim. Take " $x^{2} \geq x$ for every $x$ ". Over the integers it is true: if $x \leq 0$ then $x^{2} \geq 0 \geq x$ , and if $x \geq 1$ then multiplying $x \geq 1$ by the positive number $x$ gives $x^{2} \geq x$ . Over the reals it is false, since $x = \frac{1}{2}$ gives $x^{2} = \frac{1}{4}$ . Likewise "there is an $x$ with $x^{2} = 2$ " is true over the reals and false over the rationals, which a later lesson proves.

So mathematicians write the domain into the quantifier: $\forall x \in ℤ$ , $\exists x \in ℝ$ , with $ℕ$ , $ℤ$ , $ℚ$ and $ℝ$ for the natural numbers, integers, rationals and reals. This course takes $ℕ$ to start at $1$ .

A claim often concerns part of a domain, as in "every prime greater than $2$ is odd", and the two quantifiers restrict in different ways. A restricted universal uses a conditional: $\forall n (n is prime \land n > 2 \Rightarrow n is odd)$ . A value that fails the restriction makes the conditional vacuously true, so it is let through. A restricted existential uses a conjunction: "some prime is even" is $\exists n (n is prime \land n is even)$ , which needs one value with both properties.

Swapping the connectives destroys the claim. $\forall n (n is prime \land n is odd)$ says every integer is an odd prime, which $4$ refutes. $\exists n (n is prime \Rightarrow n is even)$ is made true by $n = 4$ , which is not prime, so it says nothing about primes at all. The shorthands $\forall x > 0$ and $\exists n \geq N$ abbreviate exactly these patterns: $\forall x > 0 P (x)$ means $\forall x (x > 0 \Rightarrow P (x))$ , and $\exists n \geq N P (n)$ means $\exists n (n \geq N \land P (n))$ .

Negating a quantified statement

To deny that every $x$ has a property is to say that some $x$ lacks it, and to deny that some $x$ has it is to say that every $x$ lacks it:

\neg \forall x P (x) \equiv \exists x \neg P (x) \neg \exists x P (x) \equiv \forall x \neg P (x)

These are the previous lesson's De Morgan laws, stretched. Over a domain of three objects $a$ , $b$ and $c$ , $\forall x P (x)$ is $P (a) \land P (b) \land P (c)$ , and De Morgan turns its negation into $\neg P (a) \lor \neg P (b) \lor \neg P (c)$ , which is $\exists x \neg P (x)$ . The quantifier laws say the same holds when the domain is infinite.

Negation is therefore mechanical: move the $\neg$ inwards, and every quantifier it passes changes kind. When it reaches the open sentence at the end, the previous lesson's rules apply: "and" becomes "or", and $\neg (P \Rightarrow Q)$ becomes $P \land \neg Q$ . The domain and the restrictions do not change. The negation of $\forall x > 0 P (x)$ is $\exists x \neg (x > 0 \Rightarrow P (x))$ , which is $\exists x (x > 0 \land \neg P (x))$ , or $\exists x > 0 \neg P (x)$ : the " $> 0$ " rides along untouched.

The mistake this prevents is turning "not every" into "none". "Not every prime is odd" is true, because of $2$ . "No prime is odd" is false, because of $3$ .

Example. Symbolise "every positive real number $x$ satisfies $x^{2} \geq x$ ", negate it, and decide which of the two is true.

Over the reals, the claim is $\forall x (x > 0 \Rightarrow x^{2} \geq x)$ . Passing the negation through the quantifier gives $\exists x \neg (x > 0 \Rightarrow x^{2} \geq x)$ , and negating the conditional gives $\exists x (x > 0 \land x^{2} < x)$ : some positive real number has a square smaller than itself. The negation is true, because $x = \frac{1}{2}$ is positive and $x^{2} = \frac{1}{4} < \frac{1}{2}$ . So the original claim is false.

Now you. Symbolise "every real number $x$ with $x^{2} = x$ satisfies $x = 1$ ", negate it, and decide which of the two is true.

Answer

The claim is $\forall x (x^{2} = x \Rightarrow x = 1)$ . Its negation is $\exists x \neg (x^{2} = x \Rightarrow x = 1)$ , which is $\exists x (x^{2} = x \land x \neq 1)$ : some real number equals its own square without being $1$ . The negation is true, because $0^{2} = 0$ and $0 \neq 1$ . So the original claim is false.

Counterexamples

The negation of $\forall x P (x)$ is $\exists x \neg P (x)$ , and an existential statement is proved by producing one value. So one value at which $P$ fails, a counterexample, refutes a universal claim however many other values it holds for. For a restricted claim $\forall x (P (x) \Rightarrow Q (x))$ , a counterexample must satisfy the hypothesis and fail the conclusion; a value that fails the hypothesis refutes nothing.

In 1640 Pierre de Fermat wrote that every number $2^{2^{n}} + 1$ is prime. The cases $n = 0$ to $4$ give $3$ , $5$ , $17$ , $257$ and $65537$ , all prime. In 1732 Euler showed that the next, $2^{32} + 1 = 4294967297$ , equals $641 \times 6700417$ , and that one line settles the matter.

The other direction has no such shortcut. No number of examples proves a universal claim over an infinite domain: $n^{2} + n + 41$ is prime for every $n$ from $0$ to $39$ and equals $41^{2}$ at $n = 40$ , and Pólya's conjecture about prime factors held for every number below 906,150,257. Existential claims are the mirror image. One example proves "some prime is one more than a square", namely $5 = 2^{2} + 1$ , while refuting an existential claim needs a proof about every value. Knowing which kind of statement is in hand says in advance whether an example will be enough.

The order of quantifiers

An open sentence in two variables, like " $y > x$ ", needs two quantifiers. Two of the same kind can come in either order; when they are mixed, the order is part of the meaning.

Over the integers, "every integer has a larger one" is $\forall x \exists y (y > x)$ , and "some integer is larger than all of them" is $\exists y \forall x (y > x)$ . The first is true and the second false, and the symbols differ only in order. In $\forall x \exists y$ the $y$ is found after $x$ is known, so it may depend on $x$ : for $7$ take $8$ , for $1000$ take $1001$ . In $\exists y \forall x$ the $y$ is fixed first and must then work against every $x$ at once.

It helps to read quantifiers as a game: a sceptic picks the values under $\forall$ and a prover those under $\exists$ , in the order written, and the statement is true when the prover can always win. Committing early is a handicap, so $\exists y \forall x P (x, y)$ implies $\forall x \exists y P (x, y)$ : one $y$ that beats every $x$ answers each $x$ in turn. The integers show the converse fails. Negation still works one quantifier at a time, so $\neg \forall x \exists y P (x, y)$ is $\exists x \forall y \neg P (x, y)$ .

Example. Over the integers, decide whether $\forall x \exists y (y > x)$ and $\exists y \forall x (y > x)$ are true, and prove each answer.

The first is true. Let $x$ be any integer and take $y = x + 1$ . Then $y$ is an integer and $y - x = 1 > 0$ , so $y > x$ . As $x$ was arbitrary, the statement holds.

The second is false, so prove its negation, $\forall y \exists x (y \leq x)$ . Let $y$ be any integer and take $x = y$ . Then $y \leq x$ . As $y$ was arbitrary, no integer is larger than all integers, not even than itself.

Now you. Over the integers, decide whether $\forall x \exists y (x + y = 0)$ and $\exists y \forall x (x + y = 0)$ are true, and prove each answer. Does the first stay true over $ℕ$ ?

Answer

The first is true: for any integer $x$ , the integer $y = - x$ gives $x + y = 0$ .

The second is false. Suppose some integer $y$ had $x + y = 0$ for every integer $x$ . Then $x = 0$ gives $y = 0$ and $x = 1$ gives $y = - 1$ , a contradiction.

Over $ℕ$ the first is false: $x = 1$ would need $y = - 1$ , which is not a natural number.

The limit of a sequence

Quantifier order is the whole content of the definition calculus rests on. A sequence $a_{1}, a_{2}, a_{3}, \dots$ converges to a real number $L$ when

\forall ε > 0 \exists N \in ℕ \forall n \geq N (| a_{n} - L | < ε)

As a game: the sceptic names a tolerance $ε$ , the prover answers with a position $N$ , the sceptic picks any term from position $N$ on, and the prover wins if it lies within $ε$ of $L$ . Since $\exists N$ follows $\forall ε$ , the position may depend on the tolerance, and it must. For $a_{n} = \frac{1}{n}$ and $L = 0$ , the tolerance $0.01$ is met from $N = 101$ , since $\frac{1}{101} < 0.01$ while $\frac{1}{100}$ is not, and $0.001$ needs $N = 1001$ . Swap the first two quantifiers and one $N$ must serve every $ε$ at once. Then each $| a_{n} - L |$ with $n \geq N$ is below every positive number, so it is $0$ , and the sequence equals $L$ exactly from $N$ on. Under that reading $\frac{1}{n}$ would not converge to $0$ .

To negate the definition, move the $\neg$ in one symbol at a time. $\forall ε > 0$ becomes $\exists ε > 0$ , keeping its restriction. $\exists N \in ℕ$ becomes $\forall N \in ℕ$ . $\forall n \geq N$ becomes $\exists n \geq N$ . Finally $| a_{n} - L | < ε$ becomes $| a_{n} - L | \geq ε$ . So $a_{n}$ does not converge to $L$ when

\exists ε > 0 \forall N \in ℕ \exists n \geq N (| a_{n} - L | \geq ε)

that is, some tolerance is broken by a term beyond every starting point. A disproof must therefore supply one $ε$ , and a way to answer every $N$ with a suitable $n$ .

Example. Prove that $a_{n} = (- 1)^{n}$ does not converge to $1$ .

Prove the negation with $L = 1$ . Take $ε = 1$ . Let $N$ be any natural number and take $n = 2 N + 1$ . Then $n \geq N$ and $n$ is odd, so $a_{n} = - 1$ and $| a_{n} - 1 | = 2 \geq 1$ . Since $N$ was arbitrary, the negation holds.

Now you. Prove that $a_{n} = \frac{1}{n}$ does not converge to $1$ .

Answer

Prove the negation with $L = 1$ . Take $ε = \frac{1}{2}$ . Let $N$ be any natural number and take $n = N + 1$ . Then $n \geq N$ and $n \geq 2$ , so $| a_{n} - 1 | = 1 - \frac{1}{n} \geq 1 - \frac{1}{2} = \frac{1}{2}$ . Since $N$ was arbitrary, the negation holds.

From what a claim says to how to prove it

Any statement in this course can now be written with quantifiers over a stated domain, and its negation computed rather than guessed.

The proofs above had shapes dictated by their quantifiers: a "for all" was met by letting the variable be arbitrary, a "there exists" by naming a value. But each step was a line of arithmetic. Knowing exactly what "the square of every odd integer is one more than a multiple of $8$ " claims does not say how to establish it. The next lesson turns those shapes into a method, the direct proof.

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. It works with two definitions, divisibility and parity, then splits proofs into cases, and proves that things exist, both by producing them and without saying what they are.

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 ℤ (4 divides n \Rightarrow n 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.

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.

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.

Divisibility

For integers $a$ and $b$ , $a$ divides $b$ , written $a ∣ b$ , if there is an integer $k$ with $b = a k$ . So $3 ∣ 12$ because $12 = 3 \times 4$ , and $- 4 ∣ 12$ because $12 = (- 4) (- 3)$ . Every integer divides $0$ , since $0 = a \times 0$ , and $1$ divides every integer. On the other hand $0 ∣ b$ only when $b = 0$ , since $0 \times k$ is always $0$ .

Two points about the notation catch almost everyone once. First, $a ∣ b$ is a statement, true or false, while $\frac{b}{a}$ is a number: " $3 ∣ 12$ " is true, and writing " $3 ∣ 12 = 4$ " mixes a sentence with a calculation. Second, the order matters: $3 ∣ 12$ is true and $12 ∣ 3$ is false, because no integer $k$ gives $3 = 12 k$ .

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

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

Let $a$ , $b$ and $c$ be integers with $a ∣ b$ and $b ∣ c$ . By the definition of divisibility, there is an integer $k$ with $b = a k$ , and there is an integer $m$ with $c = b m$ . Substituting the first equation into the second gives $c = (a k) m = a (k m)$ . Since $k$ and $m$ are integers, $k m$ is an integer. So $c$ is $a$ times an integer, and by the definition of divisibility, $a ∣ 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 ∣ 12$ and $12 ∣ 60$ , without any division, $3 ∣ 60$ .

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

Answer

Let $a$ , $b$ and $c$ be integers with $a ∣ b$ and $a ∣ c$ , and let $x$ and $y$ be any integers. By the definition of divisibility, there are integers $k$ and $m$ with $b = a k$ and $c = a m$ . Then $b x + c y = a k x + a m y = a (k x + m y)$ . Since $k$ , $m$ , $x$ and $y$ are integers, $k x + m y$ is an integer, so by the definition of divisibility, $a ∣ (b x + c y)$ . Taking $x = y = 1$ gives $a ∣ (b + c)$ , and taking $x = 1$ , $y = - 1$ gives $a ∣ (b - c)$ .

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} \lor 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 rests on a fact taken as known here: every integer is even or odd, and none is both. (That fact comes from division with remainder, not from the definitions alone.) Take the claim that $n^{2} + n$ is even for every integer $n$ .

Let $n$ be an integer. If $n$ is even, then $n = 2 k$ for some integer $k$ , and $n^{2} + n = 4 k^{2} + 2 k = 2 (2 k^{2} + k)$ , which is even. If $n$ is odd, then $n = 2 k + 1$ for some integer $k$ , and $n^{2} + n = (4 k^{2} + 4 k + 1) + (2 k + 1) = 2 (2 k^{2} + 3 k + 1)$ , which is even. Since $n$ 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 = 2 k + 1$ for some integer $k$ . Then $n^{2} = 4 k^{2} + 4 k + 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 = 2 m$ . So $n^{2} = 8 m + 1$ , and $8 ∣ (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.

The triangle inequality

The absolute value of a real number is itself defined by cases: $| x | = x$ if $x \geq 0$ , and $| x | = - x$ if $x < 0$ . So any claim about absolute values invites a proof by cases on signs, because in each case the bars can be replaced by something plain.

Example. Prove that $| x + y | \leq | x | + | y |$ for all real numbers $x$ and $y$ .

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

If $x \geq 0$ and $y \geq 0$ , then $x + y \geq 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 \geq 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 \leq x - y = | x | + | y |$ , since $y < 0$ . In the second, $- (x + y) = - x - y \leq - y \leq x - y = | x | + | y |$ , since $x \geq 0$ .

The three cases exhaust all pairs of real numbers, and the inequality holds in each, so it holds for all $x$ and $y$ .

Two things make a case split sound. The cases must between them cover everything, which is why "one non-negative and one negative" had to be there; checking only the first two cases would prove nothing about $x = 3$ , $y = - 5$ . And "we may suppose" is honest only when the omitted case is the same argument with the letters swapped. The cases may overlap harmlessly, but none may be missing.

Now you. Prove that $| x y | = | x | | y |$ for all real numbers $x$ and $y$ .

Answer

Let $x$ and $y$ be real numbers. If $x \geq 0$ and $y \geq 0$ , then $x y \geq 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 |$ . Otherwise one is non-negative and one negative; the claim is symmetric, so suppose $x \geq 0 > y$ . Then $x y \leq 0$ , so $| x y | = - x y = x (- y) = | x | | y |$ (when $x y = 0$ both readings of $| x y |$ give $0$ ). The cases cover every pair, so the equation always holds.

Proving that something exists

A claim $\exists x P (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.

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 \dots \times (k + 1)$ . Consider the $k$ numbers $N + 2, N + 3, \dots, N + (k + 1)$ . Each has the form $N + j$ with $2 \leq j \leq k + 1$ . Then $j ∣ N$ , since $j$ is one of the factors of $N$ , and $j ∣ j$ , so $j ∣ (N + j)$ by the Now you on divisibility. As $2 \leq 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.

Existence without a witness

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 answer is known from outside the proof: Aleksandr Gelfond and Theodor Schneider showed, independently in the 1930s, that ${\sqrt{2}}^{\sqrt{2}}$ is irrational, so the second pair is the one. Some mathematicians, the constructivists, reject such proofs, because they rest on the claim that every statement is true or false even when nobody can say which.

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

Answer

Take $a = \sqrt{2}$ and $b = \log_{2} 9$ , both irrational. Since $\sqrt{2} = 2^{\frac{1}{2}}$ , we get $a^{b} = 2^{\frac{1}{2} \log_{2} 9} = 2^{\log_{2} 3} = 3$ , using $\frac{1}{2} \log_{2} 9 = \log_{2} 9^{\frac{1}{2}} = \log_{2} 3$ . So $a^{b}$ is rational, and this time the pair is named.

Where the direct route stalls

Every proof above ran forwards: unpack the hypothesis by its definition, then rearrange 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} = 2 k$ for some integer $k$ . The goal is $n = 2 \times$ (an integer), and all the hypothesis offers is $n = \pm \sqrt{2 k}$ , 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.

Contrapositive and contradiction

Some true statements give a direct proof nothing to work with, because the hypothesis says nothing usable about the thing the conclusion is about.

The previous lesson proved conditionals by assuming the hypothesis and walking forward from definitions, and it ended on a claim that walk cannot finish: for every integer $n$ , if $n^{2}$ is even then $n$ is even. It also used, without proof, the fact that $\sqrt{2}$ is irrational. This lesson pays both debts with two indirect methods, proof by contrapositive and proof by contradiction, proves Euclid's theorem that there are infinitely many primes, and says how to choose a method. It assumes the definitions of even, odd and divisibility: $n$ is even when $n = 2 k$ for some integer $k$ , odd when $n = 2 k + 1$ , and $a ∣ b$ when $b = a k$ for some integer $k$ .

Turning the conditional round

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$ , and a truth table shows the two are true in exactly the same rows. So a proof of the contrapositive is a proof of the original, not an approximation to one. A proof by contrapositive is a direct proof aimed at that equivalent statement: assume $\neg Q$ , and reach $\neg P$ .

What makes the swap worth doing is that negation can turn a useless hypothesis into a useful one. " $n^{2}$ is even" gives $n^{2} = 2 k$ , and there is no way back through the square to $n$ . Its partner in the contrapositive is " $n$ is not even", which, because every integer is even or odd and none is both, means " $n$ is odd", and that gives $n = 2 k + 1$ , a formula for $n$ itself. Squaring a formula is easy. Unsquaring a fact is not.

Example. Prove that for every integer $n$ , if $n^{2}$ is even then $n$ is even.

We prove the contrapositive: for every integer $n$ , if $n$ is not even then $n^{2}$ is not even. Let $n$ be an integer that is not even. Since every integer is even or odd, $n$ is odd, so $n = 2 k + 1$ for some integer $k$ . Then $n^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1$ . Since $2 k^{2} + 2 k$ is an integer, $n^{2}$ is odd, and since no integer is both odd and even, $n^{2}$ is not even. This proves the contrapositive, and therefore the original statement.

The first sentence is not decoration. Without it, the proof looks like a proof of the converse, and a careful reader will wonder whether the writer has confused the two.

Now you. Prove that for every integer $n$ , if $3 ∣ n^{2}$ then $3 ∣ n$ . (Use the fact that every integer is of the form $3 k$ , $3 k + 1$ or $3 k + 2$ for some integer $k$ .)

Answer

We prove the contrapositive: if $3$ does not divide $n$ then $3$ does not divide $n^{2}$ . Let $n$ be an integer not divisible by $3$ . Then $n = 3 k + 1$ or $n = 3 k + 2$ for some integer $k$ . In the first case $n^{2} = 9 k^{2} + 6 k + 1 = 3 (3 k^{2} + 2 k) + 1$ , and in the second $n^{2} = 9 k^{2} + 12 k + 4 = 3 (3 k^{2} + 4 k + 1) + 1$ . Either way $n^{2}$ leaves remainder $1$ on division by $3$ , so $3$ does not divide $n^{2}$ . This proves the contrapositive, and so the claim.

Assuming the opposite

A proof by contradiction proves a statement $Q$ by assuming $\neg Q$ and deriving something impossible: a statement together with its negation. The justification is one row of a truth table. The conditional $\neg Q \Rightarrow (R \land \neg R)$ has a conclusion that is false in every row, so if the conditional has been proved, its hypothesis must be false too. And $\neg Q$ false means $Q$ true.

For a conditional $P \Rightarrow Q$ , the thing to assume is its negation, which is $P \land \neg Q$ . So the proof starts with two assumptions rather than one: everything the direct proof had, plus the negated conclusion as a further fact to use.

The method is old. Aristotle, in the Prior Analytics of the fourth century BCE, gives as his standard example of reasoning "to the impossible" the proof that the diagonal of a square cannot be measured by its side, since otherwise odd numbers would equal even ones: the next proof in this lesson.

The contrapositive is a special case: if the argument uses $\neg Q$ to reach $\neg P$ , that contradicts the assumed $P$ . The difference is the destination. A contrapositive proof has a fixed target, $\neg P$ , while a proof by contradiction may end at any impossibility at all.

The square root of two

A real number is rational if it equals $\frac{a}{b}$ for some integers $a$ and $b$ with $b \neq 0$ , and irrational otherwise. "Irrational" is a negative: no pair of integers, out of infinitely many, has a certain property. Contradiction assumes one pair exists and extracts an impossibility from it, a single argument about a single, arbitrary pair.

Approximations show why checking cannot settle it. The fraction $\frac{99}{70}$ gives $99^{2} = 9801$ against $2 \times 70^{2} = 9800$ , and $\frac{577}{408}$ gives $577^{2} = 332 929$ against $2 \times 408^{2} = 332 928$ . The gap is one each time, and no amount of searching can show that it never closes.

Example. Prove that $\sqrt{2}$ is irrational.

Suppose, for contradiction, that $\sqrt{2}$ is rational, so $\sqrt{2} = \frac{a}{b}$ for some integers $a$ and $b$ with $b \neq 0$ . If $a$ and $b$ are both even, cancel a factor of $2$ from each; the denominator shrinks in size each time, so this must stop, and we may assume that $a$ and $b$ are not both even. Squaring $\sqrt{2} = \frac{a}{b}$ and multiplying by $b^{2}$ gives $a^{2} = 2 b^{2}$ , so $a^{2}$ is even. By the result proved above, $a$ is even, so $a = 2 c$ for some integer $c$ . Substituting, $4 c^{2} = 2 b^{2}$ , so $b^{2} = 2 c^{2}$ , and $b^{2}$ is even. By the same result, $b$ is even. So $a$ and $b$ are both even, which contradicts the choice of $a$ and $b$ . Hence $\sqrt{2}$ is not rational.

A proof that proves too much is wrong, so why does it not show $\sqrt{4}$ irrational? Run it with $4$ : from $a^{2} = 4 b^{2}$ the next step would need "if $4 ∣ a^{2}$ then $4 ∣ a$ ", and that is false, since $4 ∣ 36$ while $4$ does not divide $6$ . The proof for $2$ works because $2$ is prime, and it breaks exactly where it should.

Now you. Prove that $\sqrt{3}$ is irrational, using the result from the first Now you: if $3 ∣ n^{2}$ then $3 ∣ n$ .

Answer

Suppose, for contradiction, that $\sqrt{3} = \frac{a}{b}$ for integers $a$ and $b$ with $b \neq 0$ . Cancelling factors of $3$ from both as long as both are divisible by $3$ , which must stop because the denominator shrinks in size, we may assume $a$ and $b$ are not both divisible by $3$ . Squaring gives $a^{2} = 3 b^{2}$ , so $3 ∣ a^{2}$ , and therefore $3 ∣ a$ . Write $a = 3 c$ . Then $9 c^{2} = 3 b^{2}$ , so $b^{2} = 3 c^{2}$ and $3 ∣ b^{2}$ , hence $3 ∣ b$ . So $3$ divides both $a$ and $b$ , contradicting the choice of $a$ and $b$ . Hence $\sqrt{3}$ is irrational.

The primes never run out

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ . The primes thin out, from a quarter of the numbers up to $100$ to about one in thirteen of those up to a million, so whether they stop is a real question. Around 300 BCE Euclid answered it in Book IX of the Elements, Proposition 20. The proof needs one preliminary fact.

Every integer $N > 1$ has a prime divisor. Among the divisors of $N$ that are greater than $1$ there is at least one, $N$ itself, and there are only finitely many candidates between $2$ and $N$ , so there is a smallest; call it $d$ . Suppose, for contradiction, that $d$ is not prime. Then $d = r s$ for some integers with $1 < r < d$ . Now $r ∣ d$ and $d ∣ N$ , so $r ∣ N$ by the transitivity of divisibility from the previous lesson. That makes $r$ a divisor of $N$ greater than $1$ and smaller than $d$ , contradicting the choice of $d$ . So $d$ is prime.

Example. Prove that there are infinitely many primes.

Suppose, for contradiction, that there are only finitely many, and list all of them as $p_{1}, p_{2}, \dots, p_{k}$ . Let $N = p_{1} p_{2} \dots p_{k} + 1$ . Then $N > 1$ , so by the preliminary fact $N$ has a prime divisor $p$ . Since the list contains every prime, $p$ is one of $p_{1}, \dots, p_{k}$ , and so $p$ divides the product $p_{1} p_{2} \dots p_{k}$ . It also divides $N$ . A number dividing two integers divides their difference (from the previous lesson), so $p ∣ N - p_{1} p_{2} \dots p_{k}$ , that is, $p ∣ 1$ . But $p > 1$ , and no integer greater than $1$ divides $1$ . This contradiction shows the primes are not finite in number.

Now you. Prove directly that for every positive integer $n$ there is a prime greater than $n$ . (Consider a prime divisor of $n! + 1$ .)

Answer

Let $n$ be a positive integer. Since $n! + 1 > 1$ , it has a prime divisor $p$ . If $p \leq n$ , then $p$ is one of the factors $1, 2, \dots, n$ of $n!$ , so $p ∣ n!$ ; as also $p ∣ n! + 1$ , it would follow that $p ∣ 1$ , which is impossible. So $p > n$ . For $n = 6$ , $6! + 1 = 721 = 7 \times 103$ , and both prime factors exceed $6$ . The proof uses a small contradiction to locate $p$ , but it never assumes the primes are finite: it produces a larger prime from any $n$ .

What Euclid's proof does not say

A common retelling runs: multiply the primes together, add one, and the result is a new prime. The proof says something weaker, that $N$ has a prime divisor not on the list, and the retelling is false. The first cases make it look right: $2 + 1 = 3$ , $2 \times 3 + 1 = 7$ , then $31$ , $211$ and $2311$ , all prime. The sixth breaks it:

2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30 031 = 59 \times 509

Neither $59$ nor $509$ is among the primes from $2$ to $13$ , exactly as the proof promises. The new prime is a divisor of $N$ , not $N$ itself.

Nor did Euclid assume the primes were finite. His proposition reads "prime numbers are more than any assigned multitude of prime numbers": given any finite collection of primes, their product plus one either is prime or has a prime divisor, and the divisibility argument shows that divisor is not in the collection. That proves more than the textbook version, since it turns any finite list into a new prime.

Choosing a method

Try the direct route first. When it stalls, look at the shape of the statement. If it is a conditional whose hypothesis gives nothing to manipulate while the negation of its conclusion gives a formula, as " $n^{2}$ is even" against " $n$ is odd", use the contrapositive. If the statement is a negative with no hypothesis to start from, "is irrational", "there is no largest", "there are infinitely many", use contradiction, since assuming the positive version hands the proof an object to work on.

The claim that $\log_{2} 3$ is irrational shows the second shape. Suppose $\log_{2} 3 = \frac{p}{q}$ with $p$ and $q$ positive integers (positive because $\log_{2} 3 > 0$ ). Then $2^{\frac{p}{q}} = 3$ , so $2^{p} = 3^{q}$ . The left side is even and the right side is a product of odd numbers, hence odd, and no integer is both.

Prefer the contrapositive when both methods work. Its target, $\neg P$ , is fixed in advance, so a mistake usually shows as a failure to arrive. A proof by contradiction accepts any impossibility, including one produced by an algebra slip, so a wrong one can look exactly like a right one.

Contradictions in disguise

Many proofs by contradiction are something else wearing its opening sentence. The test is to delete "suppose, for contradiction" and ask whether the assumption was ever used. Consider: "Suppose, for contradiction, that the sum of odd integers $a$ and $b$ is odd. Write $a = 2 k + 1$ and $b = 2 m + 1$ . Then $a + b = 2 (k + m + 1)$ , which is even, a contradiction." The assumed oddness of $a + b$ did nothing until the last word. Strip the wrapper and what remains is a direct proof that $a + b$ is even.

The second disguise hides a contrapositive. "Suppose $n^{2}$ is even and $n$ is odd. Then $n = 2 k + 1$ , so $n^{2}$ is odd, contradicting $n^{2}$ even." The hypothesis appears only in the final clash; the work ran from $\neg Q$ to $\neg P$ . Writing it as a contrapositive says the same thing with fewer assumptions in the air.

The textbook proof of Euclid's theorem is the third: its argument works on any finite list, so the assumption that the list held every prime was never needed. Removing a disguise improves a proof. Every line becomes true, rather than true only in an impossible world about to collapse, and a stronger or constructive result often appears.

What none of these methods can do

Every proof in this lesson and the previous one handled infinitely many integers by one argument about an arbitrary integer. Some claims do not yield to that. Take "every integer $n \geq 2$ is a product of primes". For an arbitrary $n$ , either $n$ is prime, or $n = a b$ with $a$ and $b$ smaller than $n$ ; to finish, the proof needs $a$ and $b$ to be products of primes already, which is the claim for smaller numbers. The argument for each $n$ leans on the cases below it, and checking them one by one never ends. The next lesson supplies the method that follows such a chain all the way up: induction.

Induction

A claim about every natural number is infinitely many claims, and checking them one at a time never finishes.

The previous lesson, on proof by contrapositive and contradiction, ended on a claim neither method finishes: every integer $n \geq 2$ is a product of primes, where the argument for $n$ needs the claim for smaller numbers first. This lesson gives the method for such chains and proves it valid. Throughout, the natural numbers are $ℕ = {1, 2, 3, \dots}$ , starting at $1$ , and the definitions are the usual ones: $n$ is even when $n = 2 k$ for some integer $k$ , odd when $n = 2 k + 1$ , and $a ∣ b$ when $b = a k$ for some integer $k$ .

The principle

For each natural number $n$ let $P (n)$ be a statement, such as " $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ ". The principle of induction says: if $P (1)$ is true, and if for every natural number $n$ the conditional $P (n) \Rightarrow P (n + 1)$ is true, then $P (n)$ is true for every natural number $n$ .

The two hypotheses have names. Proving $P (1)$ is the base case. Proving $P (n) \Rightarrow P (n + 1)$ for every $n$ is the inductive step, and inside it the assumption $P (n)$ is the inductive hypothesis. The step is an ordinary conditional, proved directly: take an arbitrary $n$ , assume $P (n)$ , derive $P (n + 1)$ . This is not assuming what is to be proved, since the step never claims $P (n)$ is true, only that if it is, so is the next. The picture is a line of dominoes: the base case knocks over the first, and the step makes each falling domino knock over the next.

A claim can pass one check and fail the other. Let $P (n)$ be " $n^{2} + n$ is odd". The step holds: if $n^{2} + n$ is odd, then $(n + 1)^{2} + (n + 1) = (n^{2} + n) + 2 (n + 1)$ is an odd number plus an even one, hence odd. But $P (1)$ says $2$ is odd, which is false, and in fact $n^{2} + n = n (n + 1)$ is even for every $n$ . A proof by induction that skips the base case can prove something false.

A debt from the first lesson

The first lesson of this course defined even and odd, noted that nothing in the definitions says every integer is one or the other, and left that claim open, although every proof since has leaned on it. Induction pays the debt.

Example. Prove that every natural number is even or odd.

Let $P (n)$ be the statement " $n$ is even or $n$ is odd". For the base case, $1 = 2 \times 0 + 1$ , so $1$ is odd and $P (1)$ holds. For the inductive step, let $n$ be a natural number and assume $P (n)$ . If $n$ is even, then $n = 2 k$ for some integer $k$ , so $n + 1 = 2 k + 1$ is odd. If $n$ is odd, then $n = 2 k + 1$ for some integer $k$ , so $n + 1 = 2 k + 2 = 2 (k + 1)$ is even. In either case $n + 1$ is even or odd, so $P (n + 1)$ holds. By induction, $P (n)$ holds for every natural number $n$ .

The claim for all integers follows in a sentence: $0 = 2 \times 0$ is even, and for a natural number $n$ , if $n = 2 k$ then $- n = 2 (- k)$ , while if $n = 2 k + 1$ then $- n = 2 (- k - 1) + 1$ . The companion fact, that no integer is both, is a short contradiction: $2 k = 2 m + 1$ would give $k - m = \frac{1}{2}$ , and a difference of integers is an integer.

Now you. Prove by induction that $n^{2} + n$ is even for every natural number $n$ .

Answer

Let $P (n)$ be " $n^{2} + n$ is even". For the base case, $1^{2} + 1 = 2 = 2 \times 1$ , so $P (1)$ holds. For the step, let $n$ be a natural number with $n^{2} + n = 2 k$ for some integer $k$ . Then $(n + 1)^{2} + (n + 1) = n^{2} + 3 n + 2 = (n^{2} + n) + 2 (n + 1) = 2 k + 2 (n + 1) = 2 (k + n + 1)$ , and $k + n + 1$ is an integer, so $(n + 1)^{2} + (n + 1)$ is even and $P (n + 1)$ holds. By induction, $n^{2} + n$ is even for every natural number $n$ .

Why the principle holds

The principle rests on a property of $ℕ$ called the well-ordering principle: every nonempty collection of natural numbers has a least element. It fails for the integers, which have no least element. Well-ordering is taken as a basic property of $ℕ$ .

Theorem. The principle of induction holds.

Suppose, for contradiction, that $P (1)$ and the step both hold but $P (n)$ is false for some natural number $n$ . Then the collection of natural numbers $n$ for which $P (n)$ is false is nonempty, so by well-ordering it has a least element; call it $m$ . Since $P (1)$ is true, $m \neq 1$ , so $m \geq 2$ and $m - 1$ is a natural number. Since $m - 1 < m$ and $m$ is the least failure, $P (m - 1)$ is true. The inductive step with $n = m - 1$ then gives $P (m)$ , contradicting the choice of $m$ . So $P (n)$ holds for every $n$ .

A first failure would need a predecessor that succeeds, and the step forbids that. The same shape gives another way to write any induction, the smallest counterexample argument: take the least $n$ where the claim fails and find a smaller failure.

Sums

Adding $1 + 2 + \dots + 100$ in pairs from the outside in, $1 + 100$ , $2 + 99$ and so on, gives fifty pairs of $101$ , so $5050$ . The same pairing suggests $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ in general, and induction proves it.

Example. Prove that $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ for every natural number $n$ .

Let $P (n)$ be the statement $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ . For the base case, the left side is $1$ and the right side is $\frac{1 \times 2}{2} = 1$ , so $P (1)$ holds. For the step, let $n$ be a natural number and assume $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ . Adding $n + 1$ to both sides,

1 + 2 + \dots + n + (n + 1) = \frac{n (n + 1)}{2} + (n + 1) = \frac{n (n + 1) + 2 (n + 1)}{2} = \frac{(n + 1) (n + 2)}{2} .

The right side is the formula with $n + 1$ in place of $n$ , a target worth writing down before the algebra starts, so $P (n + 1)$ holds. By induction, the formula is true for every natural number $n$ .

Induction checks a formula; it does not find one. The usual route is a guess from small cases: $1$ , $1 + 3 = 4$ , $1 + 3 + 5 = 9$ and $1 + 3 + 5 + 7 = 16$ suggest $1 + 3 + \dots + (2 n - 1) = n^{2}$ , and the step is one line, $n^{2} + (2 n + 1) = (n + 1)^{2}$ .

Now you. Prove that $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ for every natural number $n$ .

Answer

Let $P (n)$ be the formula. For the base case, both sides equal $1$ , since $\frac{1 \times 2 \times 3}{6} = 1$ . For the step, assume $P (n)$ for a natural number $n$ and add $(n + 1)^{2}$ to both sides. The right side becomes

\frac{n (n + 1) (2 n + 1) + 6 (n + 1)^{2}}{6} = \frac{(n + 1) (2 n^{2} + 7 n + 6)}{6} = \frac{(n + 1) (n + 2) (2 n + 3)}{6},

which is the formula with $n + 1$ in place of $n$ , since $2 (n + 1) + 1 = 2 n + 3$ . So $P (n + 1)$ holds, and by induction the formula holds for every $n$ .

Other starting points, and divisibility

Nothing forces the base case to be $1$ . If $P (n_{0})$ holds and $P (n) \Rightarrow P (n + 1)$ for every $n \geq n_{0}$ , then $P (n)$ holds for every $n \geq n_{0}$ ; this is the ordinary principle applied to $Q (k) = P (n_{0} + k - 1)$ . A later start is what inequalities often need. Compare $2^{n}$ with $n^{2}$ for $n = 1, 2, 3, 4$ : $2 > 1$ , then $4 = 4$ , $8 < 9$ and $16 = 16$ . From $n = 5$ , where $32 > 25$ , the power of two stays ahead.

Claim. $2^{n} > n^{2}$ for every integer $n \geq 5$ . For the base case, $2^{5} = 32 > 25 = 5^{2}$ . For the step, let $n \geq 5$ and assume $2^{n} > n^{2}$ . Then $2^{n + 1} = 2 \times 2^{n} > 2 n^{2}$ , and it remains to show $2 n^{2} \geq (n + 1)^{2}$ , that is, $n^{2} \geq 2 n + 1$ . Since $n \geq 5$ , $n^{2} \geq 5 n = 2 n + 3 n > 2 n + 1$ . So $2^{n + 1} > (n + 1)^{2}$ , and by induction the claim holds for every $n \geq 5$ .

The step in fact works for every $n \geq 3$ , yet the claim is false at $3$ and $4$ : a true conditional says nothing when its hypothesis is false, so the chain starts only where a base case is verified. For divisibility, the step shows that the new expression is the old one plus a multiple of the divisor.

Claim. $3 ∣ n^{3} - n$ for every natural number $n$ . For the base case, $1^{3} - 1 = 0 = 3 \times 0$ . For the step, assume $n^{3} - n = 3 k$ for some integer $k$ . Expanding, $(n + 1)^{3} - (n + 1) = n^{3} + 3 n^{2} + 3 n + 1 - n - 1 = (n^{3} - n) + 3 (n^{2} + n) = 3 (k + n^{2} + n)$ , which is a multiple of $3$ . By induction, the claim holds for every $n$ .

Writing $n^{3} - n = (n - 1) n (n + 1)$ , three consecutive integers, gives a shorter proof. Induction's merit is that it needs no such insight, only the algebra of one step.

Strong induction

Some steps need more than the case just before. Strong induction lets the step assume every earlier case: if $P (1)$ is true, and for every natural number $n$ the truth of $P (1), P (2), \dots, P (n)$ together implies $P (n + 1)$ , then $P (n)$ holds for every $n$ . It is no stronger than ordinary induction. Apply the ordinary principle to $Q (n)$ , " $P (1)$ through $P (n)$ are all true": $Q (1)$ is $P (1)$ , and the strong step turns $Q (n)$ into $P (n + 1)$ and hence $Q (n + 1)$ . As before, the base can start at any $n_{0}$ .

Example. Prove that every integer $n \geq 2$ is a product of primes, where a single prime counts as a product of one prime.

We use strong induction starting at $2$ . For the base case, $2$ is prime, so it is a product of one prime. For the step, let $n \geq 2$ and assume that every integer $k$ with $2 \leq k \leq n$ is a product of primes. Consider $n + 1$ . If $n + 1$ is prime, it is a product of one prime. Otherwise $n + 1 = a b$ for integers $a$ and $b$ that are both greater than $1$ and less than $n + 1$ , so both lie between $2$ and $n$ . By the inductive hypothesis each is a product of primes, and writing those two products side by side expresses $n + 1 = a b$ as a product of primes. By strong induction, every integer $n \geq 2$ is a product of primes.

Ordinary induction could not do this: that $59$ factorises says nothing about $60$ , whose proof uses $6$ and $10$ instead, giving $60 = (2 \times 3) (2 \times 5)$ . Uniqueness of the factorisation, apart from order, is a separate and harder theorem.

Now you. The Fibonacci numbers are $F_{1} = F_{2} = 1$ and $F_{n + 1} = F_{n} + F_{n - 1}$ for $n \geq 2$ , giving $1, 1, 2, 3, 5, 8, 13, \dots$ . Prove that $F_{n} < 2^{n}$ for every natural number $n$ .

Answer

We use strong induction with two base cases, because the step reaches back two places. $F_{1} = 1 < 2$ and $F_{2} = 1 < 4$ . For the step, let $n \geq 2$ and assume $F_{k} < 2^{k}$ for every $k \leq n$ . Then $F_{n + 1} = F_{n} + F_{n - 1} < 2^{n} + 2^{n - 1} < 2^{n} + 2^{n} = 2^{n + 1}$ . So the bound holds for $n + 1$ , and by strong induction for every $n$ . The step starts at $n = 2$ because $n = 1$ would call on the undefined $F_{0}$ , so $F_{2}$ must be checked by hand. The bound is generous, since $F_{30} = 832 040$ against $2^{30} = 1 073 741 824$ .

All horses are one colour

Here is a proof by induction of something false. Let $P (n)$ be "in any group of $n$ horses, all the horses are the same colour". For the base case, a group of one horse is one colour. For the step, assume $P (n)$ and take a group of $n + 1$ horses, lined up. Remove the last horse: the first $n$ form a group of $n$ , so by hypothesis they share a colour. Remove the first horse instead: the last $n$ share a colour too. The horses in the middle belong to both groups, so the two colours are the same, and all $n + 1$ horses are one colour. By induction, all horses everywhere are the same colour.

The base case is fine, so the step must fail for some $n$ . Try $n = 1$ , going from one horse to two, $A$ and $B$ . Removing the last leaves ${A}$ , removing the first leaves ${B}$ , and each is trivially one colour. The middle horses, in both groups, number $n - 1$ , which here is none. Nothing links $A$ 's colour to $B$ 's, and the step from $P (1)$ to $P (2)$ is invalid.

For every $n \geq 2$ the groups overlap in $n - 1 \geq 1$ horses and the step is correct. It fails at exactly one link, the first, and that is enough: $P (2)$ is false, so the chain never gets going. A written step often assumes something silent about $n$ , and the remedy is to run it by hand at the smallest value it must cover.

What the proofs are about

Induction completes the toolkit: direct proof, cases, contrapositive, contradiction, and, for claims indexed by the natural numbers, two finite checks. The objects those proofs talk about, though, have stayed informal. The proof of the principle took "the collection of natural numbers where $P$ fails" and asked for its least element, without saying what a collection is or when two collections are the same. The horses came in "groups" and were removed from them. Mathematics needs those words to mean something exact, and the next lesson makes them precise: sets, and how to prove that two of them are equal.

Sets

Every proof so far has spoken of "the even integers" or "the primes" as collections, and none has said what a collection is, when two of them are the same, or how to build new ones from old.

The previous lesson completed the stock of proof methods with induction, but the objects the proofs talk about have been informal, and this lesson makes them precise. It assumes the connectives, including the rule that a conditional with a false hypothesis is vacuously true, the quantifiers $\forall$ and $\exists$ , and induction.

Membership and set builder notation

A set is a collection of objects, its elements, and it is determined by nothing except which objects those are. " $x$ is an element of $A$ " is written $x \in A$ , and its negation $x \notin A$ . So $3 \in ℕ$ and $- 3 \notin ℕ$ , with $ℕ$ , $ℤ$ , $ℚ$ and $ℝ$ standing as before for the natural numbers (starting at $1$ ), the integers, the rationals and the reals.

A small set can be listed between braces: ${2, 3, 5, 7}$ is the set of primes below $10$ . A large one is described by a property, in set builder notation:

{x \in A : P (x)}

read "the set of $x$ in $A$ such that $P (x)$ ". Here $A$ is a set already known and $P (x)$ an open sentence, and the result is the set of elements of $A$ that make $P$ true. So ${n \in ℤ : n^{2} < 10} = {- 3, - 2, - 1, 0, 1, 2, 3}$ , since $3^{2} = 9$ is below $10$ and $4^{2} = 16$ is not. A second form puts an expression first: ${2 k : k \in ℤ}$ is the even integers.

The notation comes with one rule, and proofs use it constantly: $y$ belongs to ${x \in A : P (x)}$ exactly when $y \in A$ and $P (y)$ is true. The insistence on a surrounding set $A$ looks like pedantry, and the last section shows that it is not.

Subsets and equality

$A$ is a subset of $B$ , written $A \subseteq B$ , when every element of $A$ is an element of $B$ :

A \subseteq B means \forall x (x \in A \Rightarrow x \in B)

To prove this universal conditional, let $x$ be an arbitrary element of $A$ and show, using only what membership in $A$ means, that $x \in B$ . One element of $A$ outside $B$ disproves it.

Two sets are equal when they have the same elements. So ${1, 2, 2} = {2, 1}$ : each element of either side, $1$ or $2$ , lies in the other. Order is not an element, and writing $2$ twice names the same element twice. The definition also gives the method this lesson is built round: $A = B$ exactly when $A \subseteq B$ and $B \subseteq A$ , so a proof that two sets are equal is two subset proofs, called a proof by double inclusion.

Keep $\in$ and $\subseteq$ apart: $1 \in {1, 2}$ and ${1} \subseteq {1, 2}$ , but ${1} \notin {1, 2}$ , since the set ${1}$ is not one of the numbers $1$ and $2$ . Yet ${1} \in {{1}, 2}$ .

Example. Prove that ${n \in ℤ : 2 ∣ n and 3 ∣ n} = {n \in ℤ : 6 ∣ n}$ .

Call the sides $L$ and $R$ . First, $L \subseteq R$ . Let $n \in L$ . Then $n$ is an even integer and $n = 3 b$ for some integer $b$ . If $b$ were odd, $3 b$ would be a product of odd numbers and so odd, contradicting $n$ even; hence $b = 2 c$ for some integer $c$ , and $n = 6 c$ . So $6 ∣ n$ , and $n \in R$ . Second, $R \subseteq L$ . Let $n \in R$ , so $n = 6 c$ for some integer $c$ . Then $n = 2 (3 c)$ and $n = 3 (2 c)$ , so $2 ∣ n$ and $3 ∣ n$ , and $n \in L$ . Each set is a subset of the other, so $L = R$ .

Now you. Prove that ${x \in ℝ : x^{2} - 3 x + 2 < 0} = (1, 2)$ .

Answer

Call the left side $S$ ; note $x^{2} - 3 x + 2 = (x - 1) (x - 2)$ . First, $S \subseteq (1, 2)$ . Let $x \in S$ , so $(x - 1) (x - 2) < 0$ . A product of two reals is negative only when one factor is positive and the other negative, and since $x - 1 > x - 2$ , the positive one is $x - 1$ . So $x > 1$ and $x < 2$ , and $x \in (1, 2)$ . Second, $(1, 2) \subseteq S$ . Let $1 < x < 2$ . Then $x - 1 > 0$ and $x - 2 < 0$ , so their product is negative and $x \in S$ . Hence $S = (1, 2)$ .

Union, intersection, difference and complement

Four operations build new sets from old, each a connective in disguise. $x$ is in the union $A \cup B$ when $x \in A$ or $x \in B$ , with the inclusive "or"; in the intersection $A \cap B$ when $x \in A$ and $x \in B$ ; and in the difference $A ∖ B$ when $x \in A$ and $x \notin B$ . With $A = {1, 2, 3, 4}$ and $B = {3, 4, 5}$ these are ${1, 2, 3, 4, 5}$ , ${3, 4}$ and ${1, 2}$ .

The complement of $A$ is everything not in $A$ , and "everything" needs a limit: a universe $U$ , fixed in advance and containing every set under discussion, with $A^{c} = U ∖ A$ . The universe is part of the meaning: the complement of the even integers is the odd integers when $U = ℤ$ , but also contains $\frac{1}{2}$ and $π$ when $U = ℝ$ .

The intersection of ${1, 2}$ and ${3}$ has no elements at all. It is the empty set $\emptyset$ , and it is a subset of every set $A$ . The claim $\emptyset \subseteq A$ means $\forall x (x \in \emptyset \Rightarrow x \in A)$ . The hypothesis $x \in \emptyset$ is false for every $x$ , so the conditional is vacuously true. The same argument shows there is only one empty set, since two sets with no elements are each a subset of the other. But ${\emptyset}$ is not empty: it has one element.

Proving an identity by double inclusion

An identity between sets claims that two sets are equal for every choice of $A$ , $B$ and $C$ . A drawing of overlapping circles shows one arrangement; double inclusion covers them all, one arbitrary element at a time.

Example. Prove that for all sets $A$ , $B$ and $C$ , $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ .

First, left in right. Let $x \in A \cap (B \cup C)$ . Then $x \in A$ , and $x \in B$ or $x \in C$ . If $x \in B$ , then $x \in A \cap B$ ; if $x \in C$ , then $x \in A \cap C$ . Either way $x$ is in the right side. Second, right in left. Let $x \in (A \cap B) \cup (A \cap C)$ . If $x \in A \cap B$ , then $x \in A$ and $x \in B$ , so $x \in A \cap (B \cup C)$ ; the case $x \in A \cap C$ is the same with $C$ for $B$ . Each side contains the other, so they are equal.

An "or" in the hypothesis became a proof by cases, and an "or" in the conclusion needed only one of its parts. That is the pattern of most identity proofs.

Now you. Prove that for all sets $A$ , $B$ and $C$ , $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ .

Answer

First, left in right. Let $x \in A \cup (B \cap C)$ . If $x \in A$ , or if $x$ is in both $B$ and $C$ , then $x$ is in $A \cup B$ and in $A \cup C$ , so in the right side. Second, right in left. Let $x \in (A \cup B) \cap (A \cup C)$ . If $x \in A$ , it is in the left side. If not, then $x \in A \cup B$ forces $x \in B$ and $x \in A \cup C$ forces $x \in C$ , so $x \in B \cap C$ , and again $x$ is in the left side. The sets are equal.

De Morgan's laws for sets

Augustus De Morgan's laws for statements, from 1847, say that $\neg (P \lor Q)$ is equivalent to $\neg P \land \neg Q$ , and $\neg (P \land Q)$ to $\neg P \lor \neg Q$ . Since union is "or", intersection "and" and complement "not", the same laws hold for subsets of a universe $U$ :

(A \cup B)^{c} = A^{c} \cap B^{c} (A \cap B)^{c} = A^{c} \cup B^{c}

Example. Prove that $(A \cup B)^{c} = A^{c} \cap B^{c}$ for all subsets $A$ and $B$ of $U$ .

First, left in right. Let $x \in (A \cup B)^{c}$ , so $x \in U$ and $x \notin A \cup B$ . If $x$ were in $A$ , it would be in $A \cup B$ , so $x \notin A$ ; likewise $x \notin B$ . Hence $x \in A^{c}$ and $x \in B^{c}$ , so $x \in A^{c} \cap B^{c}$ . Second, right in left. Let $x \in A^{c} \cap B^{c}$ , so $x \in U$ , $x \notin A$ and $x \notin B$ . Then " $x \in A$ or $x \in B$ " is false, so $x \notin A \cup B$ and $x \in (A \cup B)^{c}$ . The sets are equal.

The middle of each half is De Morgan's law for statements, applied to $x \in A$ and $x \in B$ . Every identity here is an equivalence of statements with " $x \in$ " written in front.

Now you. Prove that $(A \cap B)^{c} = A^{c} \cup B^{c}$ for all subsets $A$ and $B$ of $U$ .

Answer

First, left in right. Let $x \in (A \cap B)^{c}$ , so $x \in U$ and $x \notin A \cap B$ . Then " $x \in A$ and $x \in B$ " is false, so $x \notin A$ or $x \notin B$ , that is, $x \in A^{c}$ or $x \in B^{c}$ , and $x \in A^{c} \cup B^{c}$ . Second, right in left. Let $x \in A^{c} \cup B^{c}$ . If $x \in A^{c}$ , then $x \notin A$ , so $x \notin A \cap B$ ; if $x \in B^{c}$ , the same holds with $B$ . Either way $x \in (A \cap B)^{c}$ . The sets are equal.

Power sets and products

The power set $P (A)$ is the set of all subsets of $A$ . For $A = {1, 2, 3}$ it has eight elements: $\emptyset$ , three one-element sets, three pairs, and $A$ itself. Writing $| A |$ for the number of elements of a finite set, the pattern is general: if $| A | = n$ , then $| P (A) | = 2^{n}$ .

The proof is by induction on $n \geq 0$ . When $n = 0$ , $A = \emptyset$ , whose only subset is $\emptyset$ , and $1 = 2^{0}$ . Suppose every set of $n$ elements has $2^{n}$ subsets, and let $| A | = n + 1$ . Choose $a \in A$ and let $A^{'} = A ∖ {a}$ , which has $n$ elements. A subset of $A$ either omits $a$ , and is then a subset of $A^{'}$ , or contains $a$ , and is then $S \cup {a}$ for exactly one subset $S$ of $A^{'}$ . There are $2^{n}$ of each kind and none of both, so $A$ has $2^{n} + 2^{n} = 2^{n + 1}$ subsets.

An ordered pair $(a, b)$ differs from the set ${a, b}$ : $(a, b) = (c, d)$ exactly when $a = c$ and $b = d$ . The Cartesian product $A \times B$ is the set of all pairs $(a, b)$ with $a \in A$ and $b \in B$ , named after Descartes because $ℝ \times ℝ$ is the coordinate plane. For finite sets $| A \times B | = | A | | B |$ : sort the pairs by first coordinate, and each of the $| A |$ choices of $a$ gives a row of exactly $| B |$ pairs, with no pair in two rows. So ${1, 2, 3} \times {x, y}$ has $3 \times 2 = 6$ elements.

Unions and intersections of many sets

A family of sets $A_{1}, A_{2}, A_{3}, \dots$ , one for each $n \in ℕ$ , has a union and an intersection defined by the quantifiers:

x \in A_{1} \cup A_{2} \cup \dots ⟺ \exists n (x \in A_{n}) x \in A_{1} \cap A_{2} \cap \dots ⟺ \forall n (x \in A_{n})

Take $A_{n} = (0, \frac{1}{n})$ . The intersection of $A_{1}$ to $A_{N}$ is $(0, \frac{1}{N})$ , never empty, yet the intersection over all $n \in ℕ$ is $\emptyset$ . Suppose $x$ lies in every $A_{n}$ . Then $x > 0$ , so some natural number $n$ exceeds $\frac{1}{x}$ (a property of the reals proved in a later lesson), and for it $\frac{1}{n} < x$ , so $x \notin A_{n}$ , a contradiction. What holds at every finite stage can fail for the whole family.

Russell's paradox

Georg Cantor, who founded the theory, defined a set in 1895 as any collection of definite, distinct objects into a whole. Read literally, that allows ${x : P (x)}$ for any property $P$ , with no surrounding set. In 1901 Bertrand Russell took the property $x \notin x$ and formed

R = {x : x \notin x}

By the membership rule, $R \in R$ exactly when $R \notin R$ , and no statement can be equivalent to its own negation. Russell's letter of June 1902 reached Gottlob Frege as the second volume of his foundations of arithmetic, built on exactly this kind of set, went to press.

The repair, due to Ernst Zermelo in 1908, is the rule this lesson has used throughout: a property may only carve a subset out of a set already known, as ${x \in A : P (x)}$ . Run Russell's argument on $R_{A} = {x \in A : x \notin x}$ . If $R_{A}$ were in $A$ , then $R_{A} \in R_{A}$ exactly when $R_{A} \notin R_{A}$ , so $R_{A} \notin A$ . The paradox becomes a theorem: no set contains every set, which is why a complement needs a universe.

Sets now have a precise language and a method of proof, but a set on its own does nothing. Mathematics is mostly about processes that turn one thing into another, a number into its square or a point into its reflection, and the next lesson makes those processes precise as functions.

Functions

Squaring a number, reflecting a point and seating each guest at a table are all processes that turn one thing into another, and a proof about any of them needs to know exactly what such a process is and when it can be undone.

The previous lesson made collections precise as sets, with subsets, the Cartesian product $A \times B$ of ordered pairs, and the habit of proving two sets equal by showing each contains the other. A set on its own does nothing, though. This lesson builds processes out of sets, assuming only that lesson, the quantifiers, and the direct and contrapositive proofs before it. As throughout the course, $ℕ = {1, 2, 3, \dots}$ starts at $1$ .

What a function is

Let $A$ and $B$ be sets. A function $f : A \to B$ is a rule that assigns to each element $a$ of $A$ exactly one element of $B$ , written $f (a)$ and called the value of $f$ at $a$ . The set $A$ is the domain and $B$ is the codomain. A rule given by a formula is often written with a barred arrow, as in $x \mapsto x^{2}$ , read " $x$ goes to $x^{2}$ ".

"Rule" is informal, and the previous lesson supplies the formal version in one sentence: a function from $A$ to $B$ is the sets $A$ and $B$ together with a subset $f$ of $A \times B$ such that for every $a \in A$ there is exactly one $b \in B$ with $(a, b) \in f$ , and $f (a)$ names that $b$ . Nothing here asks for a formula, so a seating plan is as much a function as $3 x + 7$ is.

"Exactly one" makes two demands: every element of the domain receives a value, and none receives two. The rule "send $x$ to a real number whose square is $x$ " fails both as a function from $ℝ$ to $ℝ$ : at $x = - 1$ there is no such number, and at $x = 4$ there are two. The square root repairs both by shrinking the domain to $[0, \infty)$ and choosing the non-negative root, a convention rather than a discovery.

Two functions are equal when they have the same domain, the same codomain, and the same value at every element of the domain. So $x \mapsto (x + 1)^{2}$ and $x \mapsto x^{2} + 2 x + 1$ on $ℝ$ are one function written two ways.

Why the codomain is part of the function

Take the rule $x \mapsto x^{2}$ with two codomains: $s : ℝ \to ℝ$ and $t : ℝ \to [0, \infty)$ , with $s (x) = t (x) = x^{2}$ . They have the same set of pairs, yet they answer one question differently: is every element of the codomain a value? For $t$ it is, since each $y \geq 0$ equals $t (\sqrt{y})$ . For $s$ it is not, since no real number squares to $- 1$ .

That question decides, later in this lesson, whether a function can be undone: an inverse of $s$ would have to send $- 1$ somewhere, and there is nowhere to send it. That is why the codomain is recorded as part of the function, why $s$ and $t$ count as different, and why " $x \mapsto x^{2}$ is surjective" is neither true nor false until the codomain is named.

The values a function actually takes form its range, ${f (a) : a \in A}$ , a subset of the codomain. For $s$ and $t$ alike it is $[0, \infty)$ . The codomain is where values may land; the range is where they do.

Image and preimage

For $f : A \to B$ and $S \subseteq A$ , the image of $S$ is $f (S) = {f (x) : x \in S}$ , the values taken on $S$ . For $T \subseteq B$ , the preimage of $T$ is $f^{- 1} (T) = {x \in A : f (x) \in T}$ , the inputs that land in $T$ . The notation is a trap: $f^{- 1} (T)$ is a set, and it exists for every function, whether or not $f$ has an inverse.

With $s (x) = x^{2}$ on $ℝ$ , the image of $[- 1, 2]$ is $[0, 4]$ : squares of numbers in $[- 1, 2]$ lie between $0$ and $4$ , and each $y$ in $[0, 4]$ is the square of $\sqrt{y} \in [0, 2]$ . The preimage of $[1, 4]$ is $[- 2, - 1] \cup [1, 2]$ , since negative inputs count too, and the preimage of $[- 4, - 1]$ is $\emptyset$ .

Two copies of the graph of y = x². On the left, the inputs from −1 to 2 on the x axis map onto the image from 0 to 4 on the y axis. On the right, the outputs from 1 to 4 pull back to a preimage in two pieces, from −2 to −1 and from 1 to 2, because a number and its negative have the same square.

A round trip need not return where it started: the preimage of $T = [- 4, 4]$ is $[- 2, 2]$ , whose image is $[0, 4]$ , strictly smaller than $T$ . One inclusion always holds, though.

Example. Let $f : A \to B$ and $T \subseteq B$ . Prove that $f (f^{- 1} (T)) \subseteq T$ .

Let $y \in f (f^{- 1} (T))$ . By the definition of image, $y = f (x)$ for some $x \in f^{- 1} (T)$ . By the definition of preimage, $x \in f^{- 1} (T)$ means $f (x) \in T$ . So $y = f (x) \in T$ , and since $y$ was arbitrary, the inclusion holds.

The reverse fails for $s$ because $- 4 \in T$ is not a value at all. In general $f (f^{- 1} (T))$ is exactly the part of $T$ that $f$ reaches, so equality holds for every $T$ precisely when every element of $B$ is a value.

Now you. Let $f : A \to B$ and $S \subseteq A$ . Prove that $S \subseteq f^{- 1} (f (S))$ , and find a set $S$ for which the inclusion is strict when $f = s$ .

Answer

Let $x \in S$ . Then $f (x)$ is the value of $f$ at an element of $S$ , so $f (x) \in f (S)$ by the definition of image. By the definition of preimage, an element of $A$ whose value lies in $f (S)$ belongs to $f^{- 1} (f (S))$ , so $x \in f^{- 1} (f (S))$ . Hence $S \subseteq f^{- 1} (f (S))$ . For strictness take $S = [0, 1]$ : then $s (S) = [0, 1]$ and $s^{- 1} ([0, 1]) = [- 1, 1]$ , which contains $- 1 \notin S$ . The round trip collects every input that shares a value with something in $S$ .

Injective, surjective and bijective

A function $f : A \to B$ is injective, or one-to-one, when distinct inputs give distinct outputs. The useful form is the contrapositive: for all $a, a^{'} \in A$ , if $f (a) = f (a^{'})$ then $a = a^{'}$ . The proof template is "Let $a, a^{'} \in A$ with $f (a) = f (a^{'})$ ", then algebra, then "so $a = a^{'}$ ". To disprove it, one pair suffices: $s (2) = s (- 2)$ .

It is surjective, or onto, when every element of the codomain is a value: for every $b \in B$ there exists $a \in A$ with $f (a) = b$ . The template follows the quantifiers: "Let $b \in B$ . Put $a = \dots$ ", then check that $a \in A$ and $f (a) = b$ . The formula for $a$ comes from scratch work solving $f (a) = b$ , which is not part of the proof; the check that $a$ lies in the domain is, and it is the step most often forgotten. To disprove it, name one $b$ and prove that $f (a) = b$ has no solution in $A$ .

It is bijective, a bijection, when it is both, so that each $b \in B$ is the value of exactly one $a \in A$ . The two properties are independent. The map $d : ℕ \to ℕ$ , $d (n) = 2 n$ , is injective, since $2 m = 2 n$ gives $m = n$ , but not surjective, since $2 n = 1$ forces $n = \frac{1}{2} \notin ℕ$ . With the even natural numbers as codomain, the same rule is a bijection. The function $t$ is surjective and not injective.

Example. Prove that $f : ℝ \to ℝ$ , $f (x) = 3 x + 7$ , is a bijection.

Injective: let $a, a^{'} \in ℝ$ with $f (a) = f (a^{'})$ . Then $3 a + 7 = 3 a^{'} + 7$ , so $3 a = 3 a^{'}$ , and dividing by $3$ gives $a = a^{'}$ . Surjective: let $b \in ℝ$ and put $a = \frac{b - 7}{3}$ . This is a real number, and $f (a) = 3 \cdot \frac{b - 7}{3} + 7 = b$ . So $f$ is injective and surjective, hence a bijection.

On the integers the same rule, $n \mapsto 3 n + 7$ from $ℤ$ to $ℤ$ , is injective by the same argument but not surjective: $3 n + 7 = 0$ needs $n = - \frac{7}{3}$ , not an integer. The membership check is exactly where the two cases part.

Now you. Let $h : ℝ ∖ {1} \to ℝ ∖ {2}$ be given by $h (x) = \frac{2 x}{x - 1}$ . Show that $h$ never takes the value $2$ , so that it is a function into $ℝ ∖ {2}$ , and prove that it is a bijection.

Answer

Values: $\frac{2 x}{x - 1} = 2$ would give $2 x = 2 x - 2$ , which is false. Injective: let $a, a^{'} \neq 1$ with $\frac{2 a}{a - 1} = \frac{2 a^{'}}{a^{'} - 1}$ . Clearing denominators, $2 a a^{'} - 2 a = 2 a a^{'} - 2 a^{'}$ , so $a = a^{'}$ . Surjective: let $b \neq 2$ and put $a = \frac{b}{b - 2}$ , defined since $b \neq 2$ . It is not $1$ , since $\frac{b}{b - 2} = 1$ would give $b = b - 2$ . And $h (a) = \frac{2 b / (b - 2)}{b / (b - 2) - 1} = \frac{2 b / (b - 2)}{2 / (b - 2)} = b$ . So $h$ is a bijection. Both excluded points were forced: $1$ because the formula fails there, $2$ because it is never reached.

Composition

Given $f : A \to B$ and $g : B \to C$ , the composite $g \circ f : A \to C$ is $(g \circ f) (a) = g (f (a))$ , read " $g$ after $f$ ": $f$ runs first. Order matters: with $f (x) = x + 1$ and $g (x) = x^{2}$ on $ℝ$ , $(g \circ f) (1) = 4$ while $(f \circ g) (1) = 2$ . Composition is associative, since $h \circ (g \circ f)$ and $(h \circ g) \circ f$ both send $a$ to $h (g (f (a)))$ , so brackets can be dropped.

Example. Prove that if $f : A \to B$ and $g : B \to C$ are injective, then $g \circ f$ is injective.

Let $a, a^{'} \in A$ with $g (f (a)) = g (f (a^{'}))$ . The elements $f (a)$ and $f (a^{'})$ of $B$ have the same value under $g$ , and $g$ is injective, so $f (a) = f (a^{'})$ . Since $f$ is injective, $a = a^{'}$ . So $g \circ f$ is injective.

The proof peels the functions off from the outside in. A partial converse holds: if $g \circ f$ is injective then so is $f$ , since $f (a) = f (a^{'})$ gives $g (f (a)) = g (f (a^{'}))$ and so $a = a^{'}$ . But $g$ need not be: with $f : [0, \infty) \to ℝ$ , $f (x) = x$ , the composite $s \circ f$ is injective while $s$ is not.

Now you. Prove that if $f : A \to B$ and $g : B \to C$ are surjective, then $g \circ f$ is surjective.

Answer

Let $c \in C$ . Since $g$ is surjective, there is $b \in B$ with $g (b) = c$ . Since $f$ is surjective, there is $a \in A$ with $f (a) = b$ . Then $(g \circ f) (a) = g (f (a)) = g (b) = c$ , so $g \circ f$ is surjective. Again the proof works from the outside in, finding $b$ before $a$ .

Together the two results say that a composite of bijections is a bijection.

Inverses

The identity on $A$ is ${id}_{A} : A \to A$ , ${id}_{A} (a) = a$ . A function $g : B \to A$ is an inverse of $f : A \to B$ when $g \circ f = {id}_{A}$ and $f \circ g = {id}_{B}$ .

Theorem. A function $f : A \to B$ has an inverse if and only if it is a bijection.

Suppose first that $g$ is an inverse. For injectivity, let $f (a) = f (a^{'})$ ; applying $g$ gives $a = g (f (a)) = g (f (a^{'})) = a^{'}$ . For surjectivity, let $b \in B$ and put $a = g (b)$ ; then $f (a) = f (g (b)) = b$ . Conversely, suppose $f$ is a bijection. For each $b \in B$ , surjectivity gives some $a$ with $f (a) = b$ and injectivity says there is only one, so letting $g (b)$ be that $a$ assigns exactly one element of $A$ to each $b$ , and $g : B \to A$ is a function. By construction $f (g (b)) = b$ . For $a \in A$ , $g (f (a))$ is the unique element sent to $f (a)$ , and $a$ is such an element, so $g (f (a)) = a$ . Hence $g$ is an inverse.

Each half of the definition did one job: $g \circ f = {id}_{A}$ forced injectivity and $f \circ g = {id}_{B}$ surjectivity. Neither alone is enough. For $d (n) = 2 n$ , the map $e$ sending an even $m$ to $\frac{m}{2}$ and an odd $m$ to $1$ satisfies $e \circ d = {id}_{ℕ}$ , yet $d (e (1)) = 2$ . An inverse is also unique: if $g$ and $h$ are both inverses, then $g = g \circ (f \circ h) = (g \circ f) \circ h = h$ by associativity. So it earns the name $f^{- 1}$ . For $f (x) = 3 x + 7$ it is $f^{- 1} (y) = \frac{y - 7}{3}$ , the formula the surjectivity proof already found.

Counting functions between finite sets

Let $| A | = m$ and $| B | = n$ , and list $A$ as $a_{1}, \dots, a_{m}$ . A function $f : A \to B$ is a free choice of $f (a_{1})$ , then $f (a_{2})$ , and so on, each from $B$ : an ordered list of $m$ elements of $B$ . By the product rule of the previous lesson, extended to $m$ factors by induction, there are $n^{m}$ functions from $A$ to $B$ .

For an injection each choice must avoid the earlier ones: $n$ options for $f (a_{1})$ , $n - 1$ for $f (a_{2})$ , down to $n - m + 1$ for $f (a_{m})$ . So there are $n (n - 1) \dots (n - m + 1)$ injections, a falling factorial. When $m > n$ some factor is $0$ and there are none, which is the pigeonhole principle. When $m = n$ , an injection takes $n$ distinct values in a set of $n$ elements, so it hits all of $B$ , and there are $n!$ bijections.

A computer listing every function on small sets agrees. From a 3-element set to a 4-element set there are $4^{3} = 64$ functions, of which $4 \cdot 3 \cdot 2 = 24$ are injective. From a 4-element set to itself there are $256$ , and exactly $24 = 4!$ are injective, the same $24$ that are surjective. The falling factorial also settles the birthday problem: of the $365^{23}$ ways to give 23 people birthdays, the injective fraction is $\frac{365 \cdot 364 \dots 343}{365^{23}} \approx 0.493$ , so a shared birthday is more likely than not.

For finite sets of equal size, then, injective and surjective coincide. The map $d$ on $ℕ$ , injective and not surjective, shows that this fails for infinite sets, a first sign that counting the infinite needs a different idea.

When one output is not enough

A function relates each input to exactly one output, and that restriction is what made composition and inverses work. Many relations mathematics cares about break it. "Divides" on the positive integers links $3$ to $6$ , $9$ , $12$ and every other multiple. The equation $x^{2} + y^{2} = 1$ links $0$ to both $1$ and $- 1$ and links $2$ to nothing, so the circle is not the graph of a function from $ℝ$ to $ℝ$ . "Leaves the same remainder on division by $5$ " links $3$ to $8$ , $13$ and $- 2$ .

Each is still a set of ordered pairs, a subset of a product, with the "exactly one" condition dropped. The next lesson takes such relations up, beginning with the ones that declare two things to be the same for present purposes.

Equivalence relations

A function pairs each input with exactly one output, but "divides", "has the same birthday as" and "leaves the same remainder on division by $5$ as" pair things far more freely, and they need a language of their own.

The previous lesson closed on the observation that many useful relations are not functions at all. This lesson defines relations, picks out the ones that say two things are "the same for present purposes", and shows that each of them cuts its set into pieces, which is how modular arithmetic and the fractions are built. It assumes sets, the Cartesian product $A \times B$ of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$ , the quantifiers, and divisibility: $a ∣ b$ when $b = a k$ for some integer $k$ .

Relations as sets of pairs

A relation on a set $A$ is a subset of $A \times A$ . When the pair $(a, b)$ belongs to it we say $a$ is related to $b$ and write $a \sim b$ . A relation is exactly the set of pairs it holds between, so two relations are equal when they contain the same pairs, however differently they were described.

Take $A = {1, 2, 3, 4}$ and let $a \sim b$ mean $a ∣ b$ . As a set of pairs this is

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}

eight of the sixteen pairs in $A \times A$ . Order matters, since $(2, 4)$ is in the set and $(4, 2)$ is not. A relation on $A$ can be any subset of $A \times A$ , and a set of $n$ elements has $n^{2}$ ordered pairs, so it carries $2^{n^{2}}$ relations: for $A = {1, 2, 3}$ , $2^{9} = 512$ .

A function from $A$ to $B$ fits the same mould. Its graph, ${(a, f (a)) : a \in A}$ , is a set of pairs in which every $a \in A$ appears as a first coordinate exactly once, so functions are the relations with that property. On $ℝ$ , $x \sim y$ when $y = x^{2}$ is a function. The relation $x \sim y$ when $x = y^{2}$ is not, and it fails both ways: $4$ is related to $2$ and to $- 2$ , and $- 1$ is related to nothing. Divisibility above is not one either, since $1$ is related to four elements.

Reflexive, symmetric and transitive

Three properties of a relation $\sim$ on $A$ matter here, each a universal statement:

reflexive: \forall a \in A (a \sim a)

symmetric: \forall a, b \in A (a \sim b \Rightarrow b \sim a)

transitive: \forall a, b, c \in A ((a \sim b \land b \sim c) \Rightarrow a \sim c)

A relation with all three is an equivalence relation. Equality is the model, and "has the same birthday as" is another: everyone shares a birthday with themselves, sharing is mutual, and two people who share with a third share with each other.

Being universal, each property is broken by a single counterexample, and three relations on $ℝ$ show that any two can hold without the third. The order $x \leq y$ is reflexive and transitive but not symmetric, since $1 \leq 2$ and not $2 \leq 1$ . "Close to", meaning $| x - y | \leq 1$ , is reflexive and symmetric but not transitive: $0$ is close to $1$ and $1$ to $2$ , but $0$ is not close to $2$ . And $x \sim y$ when $x y > 0$ is symmetric and transitive (if $x y > 0$ and $y z > 0$ , then $x$ and $z$ both have the sign of $y$ ) but not reflexive, since $0 \cdot 0 = 0$ .

That last example refutes a tempting proof: "if $a \sim b$ then $b \sim a$ , so $a \sim a$ by transitivity". Each step is valid, but the argument needs some $b$ with $a \sim b$ to start from, and for $a = 0$ there is none. Reflexivity asks about every $a$ , including those related to nothing.

Proving a relation is an equivalence

Such a proof is three short proofs, one per property, each a universal conditional: take arbitrary elements, assume the hypothesis, and reach the conclusion from the definition of the relation.

Example. On $ℝ$ , let $x \sim y$ when $x - y \in ℤ$ . Prove that $\sim$ is an equivalence relation.

Reflexive: let $x \in ℝ$ . Then $x - x = 0$ , an integer, so $x \sim x$ . Symmetric: let $x \sim y$ , so $x - y = k$ for some integer $k$ . Then $y - x = - k$ , also an integer, so $y \sim x$ . Transitive: let $x \sim y$ and $y \sim z$ , so $x - y = k$ and $y - z = m$ for integers $k$ and $m$ . Adding, $x - z = k + m$ , an integer, so $x \sim z$ . All three hold, so $\sim$ is an equivalence relation.

Here $2.7 \sim 0.7 \sim - 3.3$ : two reals are related when they have the same fractional part. The three steps used that the integers contain $0$ and are closed under negation and addition.

Now you. On the nonzero reals, let $x \sim y$ when $\frac{x}{y} \in ℚ$ . Prove that $\sim$ is an equivalence relation.

Answer

Reflexive: for $x \neq 0$ , $\frac{x}{x} = 1$ , which is rational, so $x \sim x$ . Symmetric: let $\frac{x}{y} = q$ with $q$ rational. Since $x \neq 0$ , $q \neq 0$ , so $\frac{y}{x} = \frac{1}{q}$ is rational and $y \sim x$ . Transitive: let $\frac{x}{y} = q$ and $\frac{y}{z} = r$ with $q$ and $r$ rational. Then $\frac{x}{z} = \frac{x}{y} \cdot \frac{y}{z} = q r$ , which is rational, so $x \sim z$ . Hence $\sim$ is an equivalence relation.

Equivalence classes partition the set

Given an equivalence relation $\sim$ on $A$ and $a \in A$ , the equivalence class of $a$ is everything related to it:

[a] = {x \in A : x \sim a}

Under the fractional part relation above, $[0.7] = {\dots, - 1.3, - 0.3, 0.7, 1.7, \dots}$ , and $[0.7] = [2.7]$ : one class, two names. Any element of a class is a representative of it. A partition of $A$ is a collection of nonempty subsets of $A$ , its blocks, such that every element of $A$ lies in exactly one block. Birthdays cut a room into at most 366 blocks, and that always happens.

Theorem. If $\sim$ is an equivalence relation on $A$ , its equivalence classes form a partition of $A$ .

First, every element is in its own class: $a \sim a$ by reflexivity, so $a \in [a]$ . Hence every class is nonempty and every element lies in at least one class.

Second, if $a \sim b$ then $[a] = [b]$ , by double inclusion. Let $x \in [a]$ , so $x \sim a$ ; with $a \sim b$ , transitivity gives $x \sim b$ , so $x \in [b]$ . Conversely let $x \in [b]$ , so $x \sim b$ ; symmetry turns $a \sim b$ into $b \sim a$ , and transitivity gives $x \sim a$ , so $x \in [a]$ .

Third, two classes are equal or disjoint. Suppose $[a]$ and $[b]$ share an element $c$ , so $c \sim a$ and $c \sim b$ . Symmetry gives $a \sim c$ , transitivity gives $a \sim b$ , and the second step gives $[a] = [b]$ . So no element lies in two different classes, and each lies in exactly one.

The converse holds too. Given a partition of $A$ , let $a \sim b$ when $a$ and $b$ lie in the same block. This is reflexive because every element lies in some block, and symmetric because "the same block" ignores order. For transitivity, let $a$ and $b$ share a block $S$ , and $b$ and $c$ a block $T$ . Then $b$ lies in both, and since it lies in exactly one block, $S = T$ , so $a$ and $c$ share a block. The classes of this relation are the blocks, so equivalence relations on $A$ and partitions of $A$ are one idea described two ways. On ${1, 2, 3}$ there are five partitions (all together, all apart, or a pair beside a singleton, in three ways), so only five of the 512 relations on that set are equivalence relations.

Congruence modulo $n$

Fix a positive integer $n$ . Integers $a$ and $b$ are congruent modulo $n$ , written $a \equiv b (mod n)$ , when $n ∣ a - b$ . So $17 \equiv 2 (mod 5)$ and $- 7 \equiv 2 (mod 3)$ . The notation is Carl Friedrich Gauss's, from his Disquisitiones Arithmeticae of 1801, and a clock uses it daily: five hours after nine o'clock is two o'clock because $14 \equiv 2 (mod 12)$ .

Example. Prove that congruence modulo $n$ is an equivalence relation on $ℤ$ .

Reflexive: for $a \in ℤ$ , $a - a = 0 = n \cdot 0$ , so $a \equiv a (mod n)$ . Symmetric: let $a \equiv b (mod n)$ , so $a - b = n k$ for some integer $k$ . Then $b - a = n (- k)$ , so $b \equiv a (mod n)$ . Transitive: let $a - b = n k$ and $b - c = n m$ for integers $k$ and $m$ . Adding, $a - c = n (k + m)$ , so $a \equiv c (mod n)$ . Congruence modulo $n$ is therefore an equivalence relation.

Its classes, the congruence classes, number exactly $n$ . Division with remainder writes every integer uniquely as $a = q n + r$ with $0 \leq r < n$ , and then $a - r = q n$ , so $a \in [r]$ : every integer lies in one of $[0], [1], \dots, [n - 1]$ . These are different, because if $0 \leq r < s < n$ then $s - r$ lies strictly between $0$ and $n$ , and no multiple of $n$ does. For $n = 3$ :

[0] = {\dots, - 3, 0, 3, 6, \dots} [1] = {\dots, - 2, 1, 4, 7, \dots} [2] = {\dots, - 1, 2, 5, 8, \dots}

So $a \equiv b (mod n)$ says exactly that $a$ and $b$ leave the same remainder on division by $n$ .

Now you. On $ℤ$ , let $a \sim b$ when $3 ∣ a + 2 b$ . Prove that $\sim$ is an equivalence relation.

Answer

Reflexive: $a + 2 a = 3 a$ , so $a \sim a$ . Symmetric: let $a + 2 b = 3 k$ . Then $b + 2 a = 3 (a + b) - (a + 2 b) = 3 (a + b - k)$ , so $b \sim a$ . Transitive: let $a + 2 b = 3 k$ and $b + 2 c = 3 m$ . Then $a + 2 c = (a + 2 b) + (b + 2 c) - 3 b = 3 (k + m - b)$ , so $a \sim c$ . In fact $a + 2 b = (a - b) + 3 b$ , so this is congruence modulo $3$ in disguise, with three classes.

The fractions as classes of pairs

A fraction is written as a pair of integers, but different pairs name the same number: $\frac{1}{2}$ , $\frac{2}{4}$ and $\frac{- 3}{- 6}$ are one rational number written three ways. An equivalence relation makes this precise, and builds $ℚ$ from $ℤ$ without assuming the division it is meant to create.

Let $P = {(a, b) \in ℤ \times ℤ : b \neq 0}$ , and for pairs in $P$ let $(a, b) \sim (c, d)$ when $a d = b c$ , the cross multiplication test stated with multiplication alone. It is reflexive, since $a b = b a$ , and symmetric, since $a d = b c$ is the same equation as $c b = d a$ . Transitivity is the real work.

Claim. If $(a, b) \sim (c, d)$ and $(c, d) \sim (e, f)$ , then $(a, b) \sim (e, f)$ .

We are given $a d = b c$ and $c f = d e$ , and must show $a f = b e$ . Multiplying the first equation by $f$ gives $a d f = b c f$ , and by the second $b c f = b d e$ . Hence $a d f = b d e$ , that is, $d (a f - b e) = 0$ . The pair $(c, d)$ lies in $P$ , so $d \neq 0$ , and a product of integers is zero only when a factor is; so $a f = b e$ .

The condition $d \neq 0$ is not a formality. Allow $(0, 0)$ and it is related to everything, since $a \cdot 0 = b \cdot 0$ . Then $(1, 2) \sim (0, 0)$ and $(0, 0) \sim (3, 5)$ , but $(1, 2)$ is not related to $(3, 5)$ , because $1 \cdot 5 = 5$ and $2 \cdot 3 = 6$ . Transitivity would fail.

A rational number is now defined to be a class $[(a, b)]$ , written $\frac{a}{b}$ , and $ℚ$ is the set of these classes. So $\frac{1}{2}$ is the set ${(1, 2), (2, 4), (- 3, - 6), \dots}$ , and the integer $n$ reappears as the class of $(n, 1)$ .

Well defined operations

Arithmetic on classes is defined through representatives, and that creates an obligation. A rule that picks a representative of a class and computes with it defines something only if every representative gives the same answer. Such a rule is well defined, and until that is proved it is not yet a function.

Here is one that fails. "Send $[(a, b)]$ to $a$ " looks like a function from $ℚ$ to $ℤ$ . But $[(1, 2)] = [(2, 4)]$ , and the rule sends this one class to $1$ through one name and to $2$ through the other. A school favourite fails the same way: "add the tops and add the bottoms" gives $\frac{1}{2} \oplus \frac{1}{3} = \frac{2}{5}$ , yet with $\frac{2}{4}$ for $\frac{1}{2}$ it gives $\frac{3}{7}$ , and $\frac{2}{5} \neq \frac{3}{7}$ because $2 \cdot 7 = 14$ and $5 \cdot 3 = 15$ .

Example. Prove that addition of rationals, $[(a, b)] + [(c, d)] = [(a d + b c, b d)]$ , is well defined.

First, $b d \neq 0$ because $b \neq 0$ and $d \neq 0$ , so the result is a class of pairs in $P$ . Now let $(a, b) \sim (a^{'}, b^{'})$ and $(c, d) \sim (c^{'}, d^{'})$ , that is, $a b^{'} = b a^{'}$ and $c d^{'} = d c^{'}$ . We must show $(a d + b c, b d) \sim (a^{'} d^{'} + b^{'} c^{'}, b^{'} d^{'})$ , that is, $(a d + b c) b^{'} d^{'} = b d (a^{'} d^{'} + b^{'} c^{'})$ . Expanding and substituting,

(a d + b c) b^{'} d^{'} = (a b^{'}) d d^{'} + (c d^{'}) b b^{'} = (b a^{'}) d d^{'} + (d c^{'}) b b^{'} = b d (a^{'} d^{'} + b^{'} c^{'})

So the sum depends only on the classes, and addition of rationals is well defined.

Congruence classes behave as well. Define $[a] + [b] = [a + b]$ modulo $n$ . If $a \equiv a^{'} (mod n)$ and $b \equiv b^{'} (mod n)$ , then $(a + b) - (a^{'} + b^{'}) = (a - a^{'}) + (b - b^{'})$ is a sum of multiples of $n$ , so $a + b \equiv a^{'} + b^{'} (mod n)$ . Clock arithmetic is arithmetic on the twelve classes modulo $12$ , whether nine o'clock is represented by $9$ , $21$ or $- 3$ .

Now you. Prove that multiplication of congruence classes modulo $n$ , $[a] [b] = [a b]$ , is well defined.

Answer

Let $a - a^{'} = n k$ and $b - b^{'} = n m$ for integers $k$ and $m$ . Then

a b - a^{'} b^{'} = a (b - b^{'}) + b^{'} (a - a^{'}) = n (a m + b^{'} k)

so $a b \equiv a^{'} b^{'} (mod n)$ , and the product class does not depend on the representatives. For example, $10 \equiv 1 (mod 9)$ gives $10^{k} \equiv 1 (mod 9)$ for every $k$ , which is why a number and the sum of its digits leave the same remainder on division by $9$ .

Equivalence relations group things: they say when two objects are the same for present purposes, and cut a set into classes that become objects in their own right. The other great kind of relation ranks things instead. The order $\leq$ on the numbers, $\subseteq$ on sets and divisibility on the positive integers are reflexive and transitive but far from symmetric, and the next lesson takes up these orders.

Order

The relations $\leq$ on the numbers, $\subseteq$ on sets and "divides" on the positive integers do not sort things into groups of equals; they rank them, and ranking needs its own definitions of what comes first, what sits on top, and when a collection has a top at all.

The previous lesson picked out the equivalence relations, those that are reflexive (every element is related to itself), symmetric (a relation one way gives it the other way) and transitive (related along a chain means related end to end), and showed that they group things. This lesson turns to the relations that rank. It assumes relations as sets of pairs, power sets, the quantifiers, and divisibility: $a ∣ b$ when $b = a k$ for some integer $k$ . As throughout the course, $ℕ = {1, 2, 3, \dots}$ .

Antisymmetry

An order cannot be symmetric: if $x \leq y$ forced $y \leq x$ , then $1 \leq 2$ would give $2 \leq 1$ . What an order has instead is that two things each ranked below the other are the same thing. A relation $⪯$ on a set $A$ is antisymmetric when

\forall a, b \in A ((a ⪯ b \land b ⪯ a) \Rightarrow a = b)

The symbol $⪯$ stands for an abstract relation of this kind, read "precedes or equals"; $\leq$ is kept for numbers.

Antisymmetric is not the negation of symmetric. Equality is both, since whenever $a = b$ and $b = a$ , certainly $a = b$ . And " $x + y$ is even" on $ℤ$ is symmetric without being antisymmetric, since it relates $1$ and $3$ both ways.

To prove antisymmetry, take arbitrary $a$ and $b$ , assume both $a ⪯ b$ and $b ⪯ a$ , and deduce $a = b$ . To refute it, exhibit two different elements related both ways.

Partial orders

A relation on $A$ that is reflexive, antisymmetric and transitive is a partial order, and $A$ with it is a partially ordered set, or poset. Three examples carry the lesson.

The first is $\leq$ on $ℝ$ , with the ordering facts of school algebra taken as known. Reflexivity is $x \leq x$ . For antisymmetry, suppose $x \leq y$ and $y \leq x$ ; if $x \neq y$ then $x < y$ and $y < x$ , and adding gives $x + y < y + x$ , which is false, so $x = y$ . For transitivity, $x \leq y$ and $y \leq z$ mean $y - x \geq 0$ and $z - y \geq 0$ , and adding gives $z - x \geq 0$ .

Example. Let $X$ be a set. Prove that $\subseteq$ is a partial order on the power set $P (X)$ , the set of all subsets of $X$ .

Reflexive: for every $A \in P (X)$ , every element of $A$ is an element of $A$ , so $A \subseteq A$ . Antisymmetric: let $A \subseteq B$ and $B \subseteq A$ . Each set is a subset of the other, which is exactly the double inclusion that proves two sets equal, so $A = B$ . Transitive: let $A \subseteq B$ and $B \subseteq C$ , and let $x \in A$ . Since $A \subseteq B$ , $x \in B$ , and since $B \subseteq C$ , $x \in C$ . As $x$ was arbitrary, $A \subseteq C$ . All three properties hold, so $\subseteq$ is a partial order on $P (X)$ .

Now you. Prove that divisibility is a partial order on $ℕ$ .

Answer

Reflexive: $a = a \cdot 1$ , so $a ∣ a$ . Transitive: let $a ∣ b$ and $b ∣ c$ , say $b = a k$ and $c = b m$ with $k, m$ integers. Then $c = a (k m)$ and $k m$ is an integer, so $a ∣ c$ . Antisymmetric: let $a ∣ b$ and $b ∣ a$ , say $b = a k$ and $a = b m$ . Then $a = a k m$ , and since $a \neq 0$ , $k m = 1$ . Because $a$ and $b$ are positive, so are $k$ and $m$ , and two positive integers with product $1$ are both $1$ . So $b = a \cdot 1 = a$ .

The positivity is doing real work. On $ℤ$ , divisibility is still reflexive and transitive, but $2 ∣ - 2$ since $- 2 = 2 \cdot (- 1)$ , and $- 2 ∣ 2$ since $2 = (- 2) (- 1)$ , while $2 \neq - 2$ . The broken step is the last: $k m = 1$ also has the integer solution $k = m = - 1$ . So divisibility is not a partial order on $ℤ$ .

Total orders and strict orders

Two elements $a$ and $b$ of a poset are comparable when $a ⪯ b$ or $b ⪯ a$ . A partial order in which every pair is comparable is a total order, or linear order, because its elements line up in a single row. The order $\leq$ on $ℝ$ is total: for any two reals, either $x \leq y$ or $y \leq x$ .

The other two examples are not. Neither of $2$ and $3$ divides the other, so they are incomparable under divisibility, and so are $4$ and $6$ . In $P ({1, 2})$ the sets ${1}$ and ${2}$ are incomparable, since neither is a subset of the other. This is what "partial" means: the order ranks some pairs and is silent about others.

Each partial order has a strict version: $a ≺ b$ means $a ⪯ b$ and $a \neq b$ , which turns $\leq$ into $<$ , $\subseteq$ into "is a proper subset of", and divisibility into "divides and is different from".

Hasse diagrams

A finite poset can be drawn economically, leaving reflexivity and transitivity for the reader to fill in. Say that $b$ covers $a$ when $a ≺ b$ and there is no $c$ with $a ≺ c ≺ b$ . The Hasse diagram puts each element as a point, places $b$ higher on the page than $a$ whenever $a ≺ b$ , and draws a line only for covering pairs. Then $a ⪯ b$ exactly when $a = b$ or a path climbs from $a$ to $b$ .

Take the eight divisors of $30$ , namely $1, 2, 3, 5, 6, 10, 15, 30$ , under divisibility. The number $1$ is covered by the primes $2$ , $3$ and $5$ . Then $2$ is covered by $6$ and $10$ , $3$ by $6$ and $15$ , and $5$ by $10$ and $15$ . Finally $6$ , $10$ and $15$ are each covered by $30$ . That is twelve lines, drawn as the edges of a cube standing on the corner $1$ , with $30$ at the opposite corner. The poset has nineteen strict pairs in all (for instance $2 ≺ 30$ ), but the other seven follow by climbing.

The cube is no accident. A divisor of $30$ is a product of some of the primes $2$ , $3$ and $5$ , and $a ∣ b$ exactly when the primes of $a$ are among those of $b$ . So the divisors of $30$ under divisibility have the same diagram as $P ({2, 3, 5})$ under $\subseteq$ .

The divisors of $12$ give a different shape. They are $1, 2, 3, 4, 6, 12$ . Here $1$ is covered by $2$ and $3$ ; $2$ is covered by $4$ and $6$ ; $3$ by $6$ ; and $4$ and $6$ are covered by $12$ . Note that $12$ does not cover $2$ , because $4$ and $6$ lie between. Those seven lines draw two squares sharing an edge, from $2$ to $6$ , rather than a cube.

Hasse diagrams under divisibility. The eight divisors of 30 form a cube with 1 at the bottom, 30 at the top and twelve covering lines. The six divisors of 12 form two squares sharing the edge from 2 to 6 (highlighted), with seven covering lines.

Maximal against greatest

"Top" has two meanings in a poset, and they come apart as soon as the order is not total. An element $g$ of $A$ is greatest when everything lies below it: $a ⪯ g$ for every $a \in A$ . An element $m$ is maximal when nothing lies strictly above it: there is no $a \in A$ with $m ≺ a$ . Least and minimal are the same definitions turned upside down.

Take the divisors of $12$ other than $12$ , the set ${1, 2, 3, 4, 6}$ under divisibility. Nothing in it is a proper multiple of $4$ or of $6$ , so both are maximal. Neither is greatest, since neither divides the other, and nothing else could be, since a greatest element would be a multiple of both. So there are two maximal elements and no greatest. At the bottom, $1$ divides everything and is least. In a Hasse diagram the maximal elements are the points with no line going up.

Greatest is a statement about every element; maximal is a statement about none. That is why a greatest element is always maximal (anything above it would also be below it, and antisymmetry makes the two equal), while a maximal element may simply be incomparable with the rest. In a total order every pair is comparable, and the two notions coincide.

Infinite posets can lack both: under $\leq$ , $ℕ$ has no maximal element, since $n < n + 1$ .

Example. Prove that a poset has at most one greatest element.

Let $g$ and $g^{'}$ both be greatest elements of $A$ . Since $g$ is greatest and $g^{'} \in A$ , we have $g^{'} ⪯ g$ . Since $g^{'}$ is greatest and $g \in A$ , we have $g ⪯ g^{'}$ . By antisymmetry, $g = g^{'}$ .

Antisymmetry supplies the equality, and it is why one may speak of "the greatest element", written $\max A$ when it exists.

Now you. Prove that if a poset $A$ has a greatest element $g$ , then $g$ is the only maximal element of $A$ .

Answer

First, $g$ is maximal. Suppose $g ≺ a$ for some $a \in A$ , so $g ⪯ a$ and $g \neq a$ . Since $g$ is greatest, $a ⪯ g$ , and antisymmetry gives $a = g$ , a contradiction. Second, let $m$ be any maximal element. Since $g$ is greatest, $m ⪯ g$ . If $m \neq g$ then $m ≺ g$ , contradicting maximality of $m$ . So $m = g$ .

The poset ${1, 2, 3, 4, 6}$ is the contrapositive at work: it has two maximal elements, so it cannot have a greatest one.

Upper bounds and the least upper bound

Maximal and greatest look inside a set. Bounds look at it from outside, within a larger poset. Let $S$ be a subset of a poset $A$ . An element $u \in A$ is an upper bound of $S$ when $s ⪯ u$ for every $s \in S$ , and $S$ is bounded above when it has one. Lower bounds are defined the other way up. An upper bound need not belong to $S$ : in $ℝ$ , the upper bounds of $[0, 1)$ are exactly the numbers $u \geq 1$ , and none of them is in the set.

Among the upper bounds, the one that matters is the lowest. An element $u$ is the least upper bound, or supremum, of $S$ , written $\sup S$ , when two conditions hold:

(i) s ⪯ u for every s \in S, (ii) u ⪯ v for every upper bound v of S

Condition (i) says $u$ is an upper bound; condition (ii) says it lies below every other one. Together they say $u$ is the least element of the set of upper bounds, so by the upside-down version of the Example above there is at most one, and "the" is earned. The greatest lower bound, or infimum, $\inf S$ , is defined the other way up.

The definition works in any poset. Under divisibility on $ℕ$ the upper bounds of ${4, 6}$ are the common multiples, and each is a multiple of $12$ (if $n = 6 b$ and $4 ∣ 6 b$ , then $3 b$ is even, so $b$ is even). So $\sup {4, 6} = 12$ , the least common multiple. Under $\subseteq$ , $\sup {A, B} = A \cup B$ , since any set containing $A$ and $B$ contains their union.

In $ℝ$ , where $\leq$ is total, condition (ii) has a working form: no number below $u$ is an upper bound, that is, for every $b < u$ some $s \in S$ has $s > b$ . If $\sup S$ belongs to $S$ , it is the greatest element: $\sup [0, 1] = 1 = \max [0, 1]$ . But it need not belong.

Example. Prove that $S = {1 - \frac{1}{n} : n \in ℕ}$ has $\sup S = 1$ , and that $1 \notin S$ .

The set is ${0, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \dots}$ . For (i), each element satisfies $1 - \frac{1}{n} < 1$ because $\frac{1}{n} > 0$ , so $1$ is an upper bound. For (ii), let $b < 1$ ; we show $b$ is not an upper bound. Since $1 - b > 0$ , choose a natural number $n > \frac{1}{1 - b}$ , which exists because $ℕ$ has no upper bound in $ℝ$ , a fact a later lesson proves. Then $\frac{1}{n} < 1 - b$ , so $1 - \frac{1}{n} > b$ , and an element of $S$ lies above $b$ . Every upper bound is therefore at least $1$ , and $\sup S = 1$ . Finally $1 - \frac{1}{n} = 1$ would force $\frac{1}{n} = 0$ , which no $n$ allows, so $1 \notin S$ , and $S$ has a supremum but no greatest element.

Now you. Prove that $\sup (0, 1) = 1$ without using any fact about $ℕ$ .

Answer

For (i), every $x \in (0, 1)$ satisfies $x < 1$ , so $1$ is an upper bound. For (ii), let $b < 1$ and find an element of $(0, 1)$ above it. If $b \leq 0$ , the element $\frac{1}{2}$ will do. If $0 < b < 1$ , take the midpoint $x = \frac{b + 1}{2}$ : then $b < x < 1$ and $x > 0$ , so $x \in (0, 1)$ and $x > b$ . So no number below $1$ is an upper bound, and $\sup (0, 1) = 1$ , which is not in the interval.

A supremum can also fail to exist. The empty set has every real as an upper bound and so no least one, and $ℕ$ has no upper bound in $ℝ$ at all.

A gap in the rationals

Whether a least upper bound exists depends on the poset the bounds are drawn from, just as surjectivity depended on the codomain. Work in $ℚ$ under $\leq$ , and let

T = {q \in ℚ : q^{2} < 2}

The set is nonempty, since $1 \in T$ , and bounded above in $ℚ$ by $2$ , since a rational $q > 2$ has $q^{2} > 4$ . In fact any positive rational $u$ with $u^{2} > 2$ is an upper bound: if some $q \in T$ had $q > u$ , then $q^{2} > u^{2} > 2$ , contradicting $q \in T$ .

So the rational upper bounds can be pushed down, and the elements of $T$ pushed up. The decimals $1.5$ , $1.42$ , $1.415$ and $1.4143$ have squares $2.25$ , $2.0164$ , $2.002225$ and $2.00024449$ , all above $2$ , so each is an upper bound. The decimals $1.4$ , $1.41$ , $1.414$ and $1.4142$ have squares $1.96$ , $1.9881$ , $1.999396$ and $1.99996164$ , all below $2$ , so each is in $T$ . The two sides close in on a number whose square is $2$ , and an earlier lesson proved that no rational has square $2$ .

That suggests a fact, stated here and proved in a later lesson: $T$ is nonempty and bounded above in $ℚ$ , yet has no least upper bound in $ℚ$ , because below every rational upper bound lies a smaller one. Inside $ℝ$ the same set has supremum $\sqrt{2}$ . The rationals are totally ordered, as the reals are, yet something the reals have is missing from them, and least upper bounds are where the absence shows.

Whether every nonempty set of reals bounded above has a least upper bound is a question about what sets of real numbers look like, and it is where the course is heading. A prior question comes first: how many real numbers are there? Both $ℚ$ and $ℝ$ are infinite, and it is not yet clear that one infinity can be larger than another. The next lesson settles it by comparing the sizes of infinite sets.

Counting the infinite

Asking how many real numbers there are invites the answer "infinitely many", and that answer says nothing until "how many" has a meaning that works for infinite sets.

The previous lesson ranked sets of numbers by order, closed on the least upper bound, and left a prior question: how many reals are there? This lesson answers it with functions alone, assuming injective, surjective and bijective maps, inverses, and the fact that composites of injections (or bijections) are injections (or bijections). As throughout the course, $ℕ = {1, 2, 3, \dots}$ starts at $1$ .

Same size without counting

Someone who cannot count can still tell whether there are as many cups as saucers: put one cup on each saucer and see whether anything is left over. That pairing is a bijection, and it is the definition. Sets $A$ and $B$ have the same size, written $| A | = | B |$ , when there is a bijection $A \to B$ . And $| A | \leq | B |$ means there is an injection $A \to B$ , which seats every element of $A$ in its own place in $B$ , perhaps with places to spare. Finally $| A | < | B |$ means an injection exists and a bijection does not. Identities, inverses and composites make "same size" reflexive, symmetric and transitive.

For finite sets the definition agrees with counting. A set has $n$ elements when it is in bijection with ${1, 2, \dots, n}$ . The lesson on functions counted the injections from an $m$ -element set to an $n$ -element set as $n (n - 1) \dots (n - m + 1)$ , which is $0$ when $m > n$ . That is the pigeonhole principle: more than $n$ pigeons in $n$ holes put two in some hole. So no set has both $m$ and $n$ elements with $m < n$ , since one bijection followed by the inverse of the other would inject ${1, \dots, n}$ into ${1, \dots, m}$ . Two finite sets have the same size exactly when they have the same number of elements.

It also shows that a finite set is never the same size as a proper subset of itself, which has at most $n - 1$ elements when the set has $n$ . Richard Dedekind turned this round in 1888 and defined an infinite set as one that is the same size as a proper subset of itself.

Hilbert's hotel

David Hilbert gave the idea its best known picture in a Göttingen lecture of 1924, and George Gamow made it famous in his 1947 book One Two Three... Infinity. A hotel has a room for every natural number, all taken, when a new guest arrives. The manager asks the guest in room $n$ to move to room $n + 1$ . Everyone still has a room, nobody shares, and room $1$ is free.

The move is $s : ℕ \to ℕ ∖ {1}$ , $s (n) = n + 1$ , and it is a bijection. It is injective, since $m + 1 = n + 1$ gives $m = n$ . It is surjective, since each $k$ in $ℕ ∖ {1}$ has $k \geq 2$ , so $k - 1 \in ℕ$ and $s (k - 1) = k$ . So $| ℕ ∖ {1} | = | ℕ |$ , and by Dedekind's definition $ℕ$ is infinite.

When a coach brings a guest for every natural number, moving each guest from room $n$ to room $2 n$ frees the odd rooms for them, so $ℕ$ is the same size as two copies of itself. "The whole is greater than the part" is Euclid's fifth common notion, true for finite collections by the pigeonhole principle and false for infinite ones.

Countable sets

A set is countable when it is finite or the same size as $ℕ$ , and uncountable otherwise. A bijection $g : ℕ \to A$ is a list of $A$ , $g (1)$ first, $g (2)$ second, in which every element appears exactly once and is reached after finitely many steps. Cantor wrote $ℵ_{0}$ for the size of $ℕ$ . Starting $ℕ$ at $0$ instead changes nothing, since the hotel's shift is a bijection between the two versions.

The integers run off in both directions, so listing them in their usual order has no first term. Alternating works: $0, 1, - 1, 2, - 2, \dots$

Example. Prove that $f : ℕ \to ℤ$ , given by $f (n) = \frac{n}{2}$ for even $n$ and $f (n) = \frac{1 - n}{2}$ for odd $n$ , is a bijection, so that $ℤ$ is countable.

The values are integers ( $1 - n$ is even when $n$ is odd), beginning $f (1) = 0$ , $f (2) = 1$ , $f (3) = - 1$ , $f (4) = 2$ . Injective: for even $n$ , $f (n) = \frac{n}{2} \geq 1$ , while for odd $n$ , $f (n) = \frac{1 - n}{2} \leq 0$ because $n \geq 1$ . So if $f (m) = f (n)$ , then $m$ and $n$ have the same parity, and either $\frac{m}{2} = \frac{n}{2}$ or $\frac{1 - m}{2} = \frac{1 - n}{2}$ ; both give $m = n$ . Surjective: let $k \in ℤ$ . If $k \geq 1$ , put $n = 2 k$ , an even natural number, and $f (n) = k$ . If $k \leq 0$ , put $n = 1 - 2 k$ , which is odd and at least $1$ , so $n \in ℕ$ , and $f (n) = \frac{1 - (1 - 2 k)}{2} = k$ . Hence $f$ is a bijection and $| ℤ | = | ℕ |$ .

The surjectivity step also found the inverse: $f^{- 1} (k) = 2 k$ for $k \geq 1$ and $f^{- 1} (k) = 1 - 2 k$ for $k \leq 0$ . So $- 3$ sits at position $7$ in the list.

Now you. Prove that $g : ℕ \to ℤ ∖ {0}$ , given by $g (n) = \frac{n}{2}$ for even $n$ and $g (n) = - \frac{n + 1}{2}$ for odd $n$ , is a bijection.

Answer

For even $n$ , $g (n) = \frac{n}{2} \geq 1$ , and for odd $n$ , $g (n) = - \frac{n + 1}{2} \leq - 1$ , a nonzero integer. Injective: $g (m) = g (n)$ forces equal parity, since only even inputs give positive values, and then $\frac{m}{2} = \frac{n}{2}$ or $- \frac{m + 1}{2} = - \frac{n + 1}{2}$ gives $m = n$ . Surjective: let $k \neq 0$ . If $k \geq 1$ , then $n = 2 k$ is even and $g (n) = k$ . If $k \leq - 1$ , then $n = - 2 k - 1$ is odd and at least $1$ , and $g (n) = - \frac{- 2 k - 1 + 1}{2} = k$ . So $g$ is a bijection, listing $- 1, 1, - 2, 2, \dots$

Pairs of natural numbers

The set $ℕ \times ℕ$ is an infinite grid, with $(m, n)$ in row $m$ and column $n$ . Listing row $1$ first never reaches row $2$ . The way out is to list by diagonals. There are exactly $s - 1$ pairs with $m + n = s$ , from $(1, s - 1)$ to $(s - 1, 1)$ , so list the diagonal with sum $2$ , then sum $3$ , and so on, each by increasing first coordinate:

(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), \dots

Each pair lies on exactly one diagonal, and each diagonal is finite, so every pair appears once and is reached after finitely many steps.

The position of $(m, n)$ is a formula. With $s = m + n$ , the earlier diagonals hold $1 + 2 + \dots + (s - 2) = \frac{(s - 2) (s - 1)}{2}$ pairs, and $(m, n)$ is in place $m$ on its own, so its position is

p (m, n) = \frac{(m + n - 2) (m + n - 1)}{2} + m

This is the Cantor pairing function, shifted so that $ℕ$ starts at $1$ : a polynomial that is a bijection $ℕ \times ℕ \to ℕ$ , because the list visits every pair once and fills every position. It gives $p (1, 1) = 1$ , $p (1, 2) = 2$ , $p (2, 1) = 3$ and $p (3, 5) = \frac{6 \cdot 7}{2} + 3 = 24$ , and on the $1770$ pairs with $m + n \leq 60$ it returns $1$ to $1770$ , each once. So $ℕ \times ℕ$ is countable.

The rationals

Between two rationals lies their average, so $ℚ$ cannot be listed in increasing order. It can be listed in another, and the quickest proof uses a theorem that turns two injections into a bijection.

Theorem (Schröder and Bernstein). If there are injections $A \to B$ and $B \to A$ , then there is a bijection $A \to B$ .

So $| A | \leq | B |$ and $| B | \leq | A |$ give $| A | = | B |$ . Cantor stated the theorem in 1887 and Felix Bernstein, a student in his seminar, proved it in 1897. The proof is left to a later course.

Example. Prove that $ℚ$ is countable.

Every rational has exactly one form $\frac{a}{b}$ in lowest terms with $a \in ℤ$ and $b \in ℕ$ . With $f$ the bijection $ℕ \to ℤ$ above, define $h : ℚ \to ℕ \times ℕ$ by $h (\frac{a}{b}) = (f^{- 1} (a), b)$ , using that form; its uniqueness is what makes $h$ a function. If $h (\frac{a}{b}) = h (\frac{c}{d})$ , then $f^{- 1} (a) = f^{- 1} (c)$ , so $a = c$ on applying $f$ , and $b = d$ , so the rationals are equal and $h$ is injective. Then $p \circ h : ℚ \to ℕ$ is a composite of injections, hence an injection, and $n \mapsto n$ injects $ℕ$ into $ℚ$ . By Schröder and Bernstein, $| ℚ | = | ℕ |$ .

For instance $- \frac{3}{4}$ goes to $(7, 4)$ and then to $p (7, 4) = \frac{9 \cdot 10}{2} + 7 = 52$ . Position $p (4, 2) = 14$ is skipped, since $(4, 2)$ would stand for $\frac{2}{2}$ , which is not in lowest terms; that is why the theorem is needed.

Now you. Prove that $F (a, b) = p (f^{- 1} (a), f^{- 1} (b))$ is a bijection $ℤ \times ℤ \to ℕ$ , and compute $F (- 1, 2)$ .

Answer

Let $G (a, b) = (f^{- 1} (a), f^{- 1} (b))$ from $ℤ \times ℤ$ to $ℕ \times ℕ$ , and $H (m, n) = (f (m), f (n))$ . Since $f$ and $f^{- 1}$ undo each other in each coordinate, $H \circ G$ and $G \circ H$ are identities, so $G$ has an inverse and is a bijection. Then $F = p \circ G$ is a composite of bijections, hence a bijection, and $ℤ \times ℤ$ is countable. With $f^{- 1} (- 1) = 3$ and $f^{- 1} (2) = 4$ , $F (- 1, 2) = p (3, 4) = \frac{5 \cdot 6}{2} + 3 = 18$ .

Cantor's diagonal argument

Georg Cantor showed in 1874 that the reals are not countable, and in 1891 gave the proof now called the diagonal argument. It uses decimal expansions of numbers in $(0, 1)$ , and has one trap.

Some numbers have two expansions: $0.4999 \dots = 0.5$ , since the tail $0.0999 \dots$ is a geometric series with sum $\frac{9}{100} \cdot \frac{10}{9} = \frac{1}{10}$ . This is the only way it happens. Two different expansions first disagree at some place $k$ , and the later digits can make up at most one unit in place $k$ , which they do only when one tail is all $9$ s and the other all $0$ s. So an expansion with no $0$ and no $9$ is the only expansion of its number. For numbers with two, use the one that does not end in $9$ s.

Here is the start of a list of numbers in $(0, 1)$ , with the $n$ th digit of the $n$ th number in bold:

$n$	$x_{n}$	expansion	$n$ th digit	new digit
1	$π - 3$	0.1415926...	1	5
2	$e - 2$	0.7182818...	1	5
3	$\sqrt{2} - 1$	0.4142135...	4	5
4	$\frac{1}{2}$	0.5000000...	0	5
5	$\sqrt{3} - 1$	0.7320508...	5	4
6	$\ln 2$	0.6931471...	7	5

The new digit is $5$ , unless the diagonal digit is $5$ , when it is $4$ . The number $0.555545 \dots$ built from them differs from every $x_{n}$ in place $n$ .

Example. Prove that there is no surjection $ℕ \to (0, 1)$ .

Let $g : ℕ \to (0, 1)$ be any function, and let $d_{n, k}$ be the $k$ th digit of $g (n)$ , using the expansion chosen above. Put $c_{n} = 4$ if $d_{n, n} = 5$ and $c_{n} = 5$ otherwise, and let $y = 0. c_{1} c_{2} c_{3} \dots$ . Every digit of $y$ is $4$ or $5$ , so $\frac{4}{9} = 0.444 \dots \leq y \leq 0.555 \dots = \frac{5}{9}$ , and $y \in (0, 1)$ . Suppose $y = g (n)$ for some $n$ . The expansion of $y$ has no $0$ or $9$ , so it is the only one $y$ has, and the chosen expansion of $g (n)$ must be it. Then $d_{n, n} = c_{n}$ , contradicting the choice of $c_{n}$ . So $y$ is not a value of $g$ , and $g$ is not surjective.

So $(0, 1)$ , which is plainly not finite, is uncountable. So is $ℝ$ : a bijection $ℝ \to ℕ$ would inject $(0, 1)$ into $ℕ$ , while $n \mapsto \frac{1}{n + 1}$ injects $ℕ$ into $(0, 1)$ , and Schröder and Bernstein would make $(0, 1)$ countable. The care over $0$ s and $9$ s is needed. With the rule "replace each diagonal digit $d$ by $9 - d$ ", a list that starts with $0.5000 \dots$ and has every later diagonal digit $0$ produces $0.4999 \dots$ , which is the first number again.

Now you. Let $S$ be the set of infinite sequences $(t_{1}, t_{2}, \dots)$ with every term $0$ or $1$ . Prove that there is no surjection $ℕ \to S$ .

Answer

Let $g : ℕ \to S$ be any function, with $g (n) = (t_{n, 1}, t_{n, 2}, \dots)$ . Define $u$ by $u_{n} = 1 - t_{n, n}$ , so each $u_{n}$ is $0$ or $1$ and $u \in S$ . For every $n$ , $u_{n} \neq t_{n, n}$ , so $u$ and $g (n)$ differ in term $n$ and $u \neq g (n)$ . Hence $u$ is not a value of $g$ , and $g$ is not surjective. No trap arises here, because two sequences are equal only when every term agrees.

Cantor's theorem

The diagonal idea, build an object that disagrees with the $n$ th item at the $n$ th place, is not about decimals. It works for any set $A$ and its power set $P (A)$ , the set of all subsets of $A$ .

Theorem (Cantor). For every set $A$ , $| A | < | P (A) |$ .

The map $a \mapsto {a}$ is an injection $A \to P (A)$ , since ${a} = {a^{'}}$ forces $a = a^{'}$ . It remains to show that no $F : A \to P (A)$ is surjective. Each $F (a)$ is a subset of $A$ , which may or may not contain $a$ . Collect the elements not in their own image:

D = {a \in A : a \notin F (a)}

This is a subset of $A$ . Suppose $D = F (d)$ for some $d \in A$ . If $d \in D$ , the definition of $D$ gives $d \notin F (d) = D$ . If $d \notin D$ , then $d \notin F (d)$ , which is exactly the condition for $d \in D$ . Either way there is a contradiction, so $F$ is not surjective, there is no bijection, and $| A | < | P (A) |$ .

For a finite set this is $n < 2^{n}$ . For $ℕ$ the diagonal is visible: with $F (n)$ as row $n$ , the question "is $n \in F (n)$ ?" reads down the diagonal, and $D$ answers each one the other way. Applied repeatedly, the theorem gives an unending ladder, so there is no largest infinity:

| ℕ | < | P (ℕ) | < | P (P (ℕ)) | < \dots

The set $D$ should look familiar. Russell's paradox, from the lesson on sets, is the set of all sets that are not members of themselves, and Russell reached it in 1901 by studying this proof: run it on a supposed set of all sets with $F (x) = x$ , and $D$ becomes ${x : x \notin x}$ . Inside a genuine set $A$ , the same self-reference yields a theorem rather than a paradox.

The continuum hypothesis

Two infinite sizes are now in hand: that of $ℕ$ , shared by $ℤ$ , $ℕ \times ℕ$ and $ℚ$ , and the strictly larger size of $ℝ$ . In 1878 Cantor asked whether anything lies between: is every infinite set of reals either countable or the same size as $ℝ$ ? He believed so, and the claim is the continuum hypothesis, first on Hilbert's list of problems in 1900. Kurt Gödel showed in 1940 that it cannot be disproved from the usual axioms of set theory, and Paul Cohen showed in 1963 that it cannot be proved from them either. The axioms the rest of mathematics runs on do not decide it.

The count does settle a difference between two number systems that look alike. The rationals and the reals are both ordered and closed under the four operations, and between any two rationals lies another. Yet the rationals can be listed and the reals cannot, so something about the reals is missing from the rationals. Nothing so far has said what: counting shows the difference exists without locating it. The next lesson names it, as a property of least upper bounds called completeness.

The real numbers

The rationals and the reals obey the same rules of arithmetic and the same rules for inequalities, yet the rationals can be listed and the reals cannot, so something separates them that no rule of algebra mentions.

The previous lesson found that split by comparing infinite sets through bijections, and left open what the reals have that the rationals lack. This lesson names it, the completeness axiom, and uses it to pay debts that earlier lessons deferred to "a later lesson": that $ℕ$ has no upper bound in $ℝ$ , used without proof in the lessons on sets and on order; that the rationals with square less than $2$ have no least upper bound among the rationals, stated in the lesson on order; and that some real number has square $2$ , claimed in the lesson on quantifiers. It assumes upper bounds and the supremum: $u = \sup A$ when $u$ is an upper bound of $A$ lying below every other upper bound. As throughout the course, $ℕ = {1, 2, 3, \dots}$ .

The gap where $\sqrt{2}$ should be

Work inside $ℚ$ and let $T = {q \in ℚ : q^{2} < 2}$ . It is nonempty, since $1 \in T$ , and any positive $u$ with $u^{2} > 2$ is an upper bound, because an element $q > u$ would have $q^{2} > u^{2} > 2$ . The claim deferred by the lesson on order is that no rational is the least upper bound. The proof rests on two pieces of algebra that push a candidate up or down.

The first says a number whose square is below $2$ is never the top of $T$ . Let $u \geq 1$ with $u^{2} < 2$ , and set $h = \frac{2 - u^{2}}{2 u + 1}$ . Then $h > 0$ , and $h < 1$ because $2 - u^{2} \leq 1 < 3 \leq 2 u + 1$ . Since $0 < h < 1$ gives $h^{2} < h$ ,

(u + h)^{2} = u^{2} + 2 u h + h^{2} < u^{2} + h (2 u + 1) = 2

So $u + h$ is larger than $u$ with square still below $2$ . From $u = 1.4$ it gives $h = \frac{1}{95}$ , and $(1.4 + \frac{1}{95})^{2} \approx 1.9896$ .

The second says a number whose square is above $2$ is never the least upper bound. Let $u > 0$ with $u^{2} > 2$ , and set $k = \frac{u^{2} - 2}{2 u} > 0$ . Then $u - k = \frac{u^{2} + 2}{2 u}$ is positive, and

(u - k)^{2} = u^{2} - 2 u k + k^{2} > u^{2} - 2 u k = 2

So $u - k$ is a smaller upper bound. From $u = \frac{3}{2}$ it gives $\frac{17}{12}$ , with square $\frac{289}{144}$ . Both $h$ and $k$ are built from $u$ by arithmetic, so if $u$ is rational, so are they.

Example. Prove that $T = {q \in ℚ : q^{2} < 2}$ has no least upper bound in $ℚ$ .

Suppose, for contradiction, that $u \in ℚ$ is the least upper bound of $T$ . Since $1 \in T$ , $u \geq 1$ . Since $\sqrt{2}$ is irrational, as an earlier lesson proved, $u^{2} \neq 2$ , so either $u^{2} < 2$ or $u^{2} > 2$ . If $u^{2} < 2$ , the rational $u + h$ above lies in $T$ and exceeds $u$ , contradicting that $u$ is an upper bound. If $u^{2} > 2$ , the rational $u - k$ is an upper bound of $T$ smaller than $u$ , contradicting that $u$ is the least. Both cases are impossible, so $T$ has no least upper bound in $ℚ$ .

Now you. Prove that ${q \in ℚ : q^{2} < 3}$ has no least upper bound in $ℚ$ , using the irrationality of $\sqrt{3}$ .

Answer

Suppose $u \in ℚ$ is the least upper bound. Since $1$ is in the set, $u \geq 1$ , and since $\sqrt{3}$ is irrational, $u^{2} \neq 3$ . If $u^{2} < 3$ , let $h = \frac{3 - u^{2}}{2 u + 1}$ , rational, positive, and less than $1$ because $3 - u^{2} \leq 2 < 3 \leq 2 u + 1$ . Then $(u + h)^{2} < u^{2} + h (2 u + 1) = 3$ , so $u + h$ is in the set and exceeds $u$ , a contradiction. If $u^{2} > 3$ , let $k = \frac{u^{2} - 3}{2 u}$ . Then $u - k = \frac{u^{2} + 3}{2 u} > 0$ and $(u - k)^{2} > u^{2} - 2 u k = 3$ , so $u - k$ is a smaller upper bound, a contradiction.

The ordered field axioms

That proof used only arithmetic, order and the irrationality of $\sqrt{2}$ . To say what the reals have in addition, their familiar properties must be written down as a list, so that it is clear which ones the rationals share.

Addition and multiplication are commutative and associative, multiplication distributes over addition, there are elements $0 \neq 1$ with $x + 0 = x$ and $x \cdot 1 = x$ , every $x$ has a negative $- x$ , and every $x \neq 0$ has a reciprocal $\frac{1}{x}$ : these make $ℝ$ a field. The order $\leq$ is total and respects the arithmetic: $x \leq y$ implies $x + z \leq y + z$ , and $0 \leq x$ with $0 \leq y$ implies $0 \leq x y$ . A field with such an order is an ordered field. Every rule of school algebra, from $0 \cdot x = 0$ to "multiplying by a negative number reverses an inequality", follows from these axioms, and here they are taken as given.

The trouble is that $ℚ$ satisfies every one of them. So no argument from these axioms alone can produce a number whose square is $2$ , since it would work equally well in $ℚ$ , where there is none. Something else must be assumed.

The completeness axiom

It concerns least upper bounds, exactly where the rationals fail.

Completeness axiom. Every nonempty set of real numbers that is bounded above has a least upper bound in $ℝ$ .

The reals are an ordered field satisfying this axiom, a complete ordered field, and that is all this course assumes about them. The rationals are an ordered field that does not: $T$ is nonempty and bounded above, and has no rational least upper bound. Both conditions in the axiom are needed. The empty set has every real as an upper bound and so no least one, and $ℕ$ , as a later section proves, has no upper bound at all.

The idea took its modern form in 1872, in two independent constructions. Richard Dedekind, in Braunschweig, published Stetigkeit und irrationale Zahlen ("Continuity and irrational numbers"), defining a real number as a cut of the rationals into a lower and an upper class; he dated the idea to November 1858, when, teaching calculus in Zurich, he could find no rigorous proof that a bounded increasing quantity approaches a limit. The same year Georg Cantor, in Halle, built the reals from sequences of rationals whose terms eventually cluster together. In both constructions completeness is a theorem, and any two complete ordered fields turn out to be the same up to relabelling, so taking the axiom as a starting point describes $ℝ$ exactly.

Working with the supremum

The definition of $\sup A$ quantifies over every upper bound. Proofs usually want a form that tests only numbers just below $s$ .

Example. Prove that $s = \sup A$ if and only if $s$ is an upper bound of $A$ and, for every $ε > 0$ , some $a \in A$ satisfies $a > s - ε$ .

Suppose first that $s = \sup A$ . Then $s$ is an upper bound by definition. Let $ε > 0$ . Since $s - ε < s$ and $s$ lies below every upper bound, $s - ε$ is not an upper bound, so some $a \in A$ has $a > s - ε$ .

Conversely, suppose $s$ is an upper bound with the $ε$ property, and let $v$ be any upper bound of $A$ . Suppose, for contradiction, that $v < s$ , and take $ε = s - v > 0$ . Some $a \in A$ has $a > s - ε = v$ , contradicting that $v$ is an upper bound. So $s \leq v$ for every upper bound $v$ , and $s = \sup A$ .

The second half chose $ε$ to fit the contradiction. Picking $ε$ after the thing to be defeated is known is the move the final lesson makes over and over.

Lower bounds need no second axiom. If $A$ is nonempty and bounded below by $m$ , then $- A = {- a : a \in A}$ is nonempty and bounded above by $- m$ , so it has a supremum, and reversing every inequality shows that $- \sup (- A)$ is the greatest lower bound of $A$ . So every nonempty set bounded below has an infimum, $\inf A = - \sup (- A)$ .

Now you. Prove that $t = \inf A$ if and only if $t$ is a lower bound of $A$ and, for every $ε > 0$ , some $a \in A$ satisfies $a < t + ε$ .

Answer

Suppose $t = \inf A$ . It is a lower bound by definition. Let $ε > 0$ . Since $t + ε > t$ and $t$ lies above every lower bound, $t + ε$ is not a lower bound, so some $a \in A$ has $a < t + ε$ . Conversely, suppose $t$ is a lower bound with this property, and let $m$ be any lower bound. If $m > t$ , take $ε = m - t$ : some $a \in A$ has $a < t + ε = m$ , contradicting that $m$ is a lower bound. So $m \leq t$ for every lower bound $m$ , and $t = \inf A$ .

The Archimedean property

The lessons on sets and on order promised a proof that $ℕ$ has no upper bound in $ℝ$ . It does not follow from the ordered field axioms: there are ordered fields containing elements larger than every natural number. In $ℝ$ it follows from completeness.

Example. Prove the Archimedean property: for every real $x$ there is a natural number $n$ with $n > x$ .

Suppose, for contradiction, that some real $x$ has $n \leq x$ for every $n \in ℕ$ . Then $ℕ$ is nonempty and bounded above, so by completeness it has a supremum $s$ . By the characterisation with $ε = 1$ , some $n \in ℕ$ has $n > s - 1$ . Then $n + 1 > s$ , and $n + 1 \in ℕ$ , contradicting that $s$ is an upper bound of $ℕ$ .

The form the earlier lessons used follows at once: for every $ε > 0$ some $n$ has $\frac{1}{n} < ε$ . Take $n > \frac{1}{ε}$ and multiply by the positive number $\frac{ε}{n}$ . For $ε = 0.03$ the condition is $n > 33.3$ , so $n = 34$ is the first that works, with $\frac{1}{34} \approx 0.0294$ .

Now you. Prove that $\inf {\frac{1}{n} : n \in ℕ} = 0$ .

Answer

Every $\frac{1}{n}$ is positive, so $0$ is a lower bound. Let $ε > 0$ . By the Archimedean property some $n \in ℕ$ has $n > \frac{1}{ε}$ , so $\frac{1}{n} < ε = 0 + ε$ . By the characterisation of the infimum, the infimum is $0$ , which is not itself in the set.

The square root of two exists

The lesson on quantifiers said that "some $x$ has $x^{2} = 2$ " is false over the rationals and true over the reals. The real half needs completeness, and the proof is the rational argument run again.

Let $S = {x \in ℝ : x^{2} < 2}$ . It is nonempty, since $1 \in S$ , and bounded above by $2$ , since $x \geq 2$ gives $x^{2} \geq 4$ . By completeness it has a supremum $s$ , and $s \geq 1$ . The two pieces of algebra from the first section never used rationality, so they apply to $s$ . If $s^{2} < 2$ , then $s + h$ lies in $S$ and exceeds $s$ , impossible for an upper bound. If $s^{2} > 2$ , then $s - k$ is a smaller upper bound, impossible for the least one. So $s^{2} = 2$ . No other positive number qualifies, since $t > 0$ and $t^{2} = 2$ give $(s - t) (s + t) = 0$ with $s + t > 0$ . This $s$ is $\sqrt{2}$ .

Over $ℚ$ , the algebra ruled out both inequalities, irrationality ruled out equality, and no supremum was left. Over $ℝ$ , completeness supplies the supremum, the same algebra rules out both inequalities, and equality is what remains. The gap in the rationals is exactly where the reals have a number.

The rationals are dense

For all their gaps, the rationals are everywhere: between any two reals $a < b$ lies a rational. By the Archimedean property choose $n$ with $\frac{1}{n} < b - a$ , so $n b - n a > 1$ . The integers greater than $n a$ form a nonempty set bounded below (the Archimedean property, applied to $n a$ and to $- n a$ , gives an integer on each side), so by well-ordering it has a least element $m$ . Then $m - 1 \leq n a < m$ , so $n a < m \leq n a + 1 < n b$ , and dividing by $n$ gives $a < \frac{m}{n} < b$ . Between $0.3$ and $0.31$ , the proof takes $n = 101$ and $m = 31$ , and $\frac{31}{101} \approx 0.3069$ .

Density settles the last claim of the lesson on order, that $T$ has supremum $\sqrt{2}$ in $ℝ$ . Every $q \in T$ has $q < \sqrt{2}$ , and for any $b < \sqrt{2}$ there is a rational $q$ strictly between $\max {b, 0}$ and $\sqrt{2}$ , which lies in $T$ and exceeds $b$ . The irrationals are dense too: a rational $q$ between $a - \sqrt{2}$ and $b - \sqrt{2}$ gives the irrational $q + \sqrt{2}$ between $a$ and $b$ .

Where completeness is needed next

The Archimedean property, the density of the rationals and the existence of $\sqrt{2}$ are facts calculus uses without comment, and each came from one axiom. The first place calculus needs completeness itself is its foundation, the limit of a sequence. The decimal truncations $1$ , $1.4$ , $1.41$ , $1.414$ , and so on, of $\sqrt{2}$ form an increasing bounded sequence of rationals with nothing in $ℚ$ to converge to. The final lesson writes convergence with $ε$ and $N$ , proves limits with the methods of the whole course, and shows that in $ℝ$ every bounded increasing sequence converges, the theorem Dedekind found no proof of in 1858.

Limits, proved

Calculus rests on the statement that a sequence converges to a limit, and so far that statement has been written down, read as a game and negated, but never proved for a single sequence.

The previous lesson supplied what was missing: the completeness axiom, that every nonempty set of reals bounded above has a least upper bound, and from it the Archimedean property, that for every real $x$ some natural number exceeds $x$ . This lesson puts the whole course to work on one definition. It proves that particular sequences converge and that others do not, proves general theorems about limits, and ends with a theorem that is true in $ℝ$ and false in $ℚ$ , which is exactly what completeness buys. Along the way it separates two activities that textbooks tend to blur: finding a proof and writing one.

The definition, read closely

A sequence $a_{1}, a_{2}, a_{3}, \dots$ of real numbers converges to $L$ when

\forall ε > 0 \exists N \in ℕ \forall n \geq N (| a_{n} - L | < ε)

with $ℕ = {1, 2, 3, \dots}$ as throughout the course. The lesson on quantifiers read it as a game. A sceptic names a tolerance $ε > 0$ , as small as they like. A prover answers with a position $N$ . The sceptic then picks any term from position $N$ on, and the prover wins if that term lies within $ε$ of $L$ . The sequence converges to $L$ when the prover has a winning answer to every tolerance, and we write $a_{n} \to L$ .

Because $\exists N$ comes after $\forall ε$ , the position may depend on the tolerance, and for any interesting sequence it must: a smaller $ε$ usually needs a later $N$ . Because the last quantifier is $\forall n \geq N$ , it is not enough for one term to land close; every term from $N$ on must, so the sequence stays close rather than visiting. The first $N - 1$ terms are ignored completely, which is why changing finitely many terms never changes a limit.

The quantifiers also dictate the shape of every convergence proof before any arithmetic is done. The universal $\forall ε > 0$ is met by "Let $ε > 0$ ", assuming nothing about it but positivity. The existential $\exists N$ is met by naming an $N$ , which may be built from $ε$ but from nothing chosen later. The inner universal is met by "Let $n \geq N$ ". What remains is to show $| a_{n} - L | < ε$ using only those facts. An $N$ that works may always be replaced by a larger one, so there is no need to find the smallest; the proof only has to find one.

The first limit: $\frac{1}{n} \to 0$

Theorem. The sequence $a_{n} = \frac{1}{n}$ converges to $0$ .

Proof. Let $ε > 0$ . By the Archimedean property there is a natural number $N$ with $N > \frac{1}{ε}$ . Let $n \geq N$ . Then

| a_{n} - 0 | = \frac{1}{n} \leq \frac{1}{N} < ε

where the first inequality holds because $n \geq N > 0$ , and the second follows from $N > \frac{1}{ε}$ on multiplying both sides by the positive number $\frac{ε}{N}$ . Since $ε$ was arbitrary, $\frac{1}{n} \to 0$ . $□$

For $ε = 0.01$ the proof asks for $N > 100$ , and $N = 101$ is the answer the lesson on quantifiers found by hand. The proof answers every tolerance at once, with a recipe rather than a table.

The one step that is not arithmetic is the existence of $N$ , and it is not a formality. It is the Archimedean property, which the previous lesson derived from completeness. There are ordered fields that obey every rule of school algebra and contain positive elements smaller than every $\frac{1}{n}$ ; in such a field the sceptic names one of those as $ε$ and wins. The most basic limit in analysis is already a fact about the reals, not about algebra.

How a proof is found, and how it is written

For most sequences the right $N$ is not obvious, and the finished proof hides how it was found, because the work happens in two passes. The first is scratch work, done on the side and never handed in: start from the goal $| a_{n} - L | < ε$ , simplify $| a_{n} - L |$ , and work backwards to a condition on $n$ that guarantees it. The second is the proof, which runs forwards: it starts from $ε$ , names the $N$ the scratch work found, and checks that it wins.

Example. Prove that $a_{n} = \frac{3 n + 1}{n + 2}$ converges to $3$ .

Scratch work. Simplify the distance to the limit:

| a_{n} - 3 | = | \frac{3 n + 1 - 3 (n + 2)}{n + 2} | = \frac{5}{n + 2}

The goal $\frac{5}{n + 2} < ε$ holds exactly when $n > \frac{5}{ε} - 2$ . That is the sharpest condition, but a cruder one is easier to write with: since $\frac{5}{n + 2} < \frac{5}{n}$ , it is enough that $\frac{5}{n} < ε$ , which holds once $n > \frac{5}{ε}$ . So take $N > \frac{5}{ε}$ .

Proof. Let $ε > 0$ . By the Archimedean property there is $N \in ℕ$ with $N > \frac{5}{ε}$ . Let $n \geq N$ . Then

| a_{n} - 3 | = \frac{5}{n + 2} < \frac{5}{n} \leq \frac{5}{N} < ε

so $| a_{n} - 3 | < ε$ for every $n \geq N$ . Since $ε$ was arbitrary, $a_{n} \to 3$ . $□$

At $ε = 0.1$ the proof asks for $N > 50$ , so $N = 51$ , while the sharp condition $n > 48$ shows the smallest working position is $49$ . Both win, and the proof is shorter for not caring which. What the proof never contains is the backwards reasoning: "suppose $| a_{n} - 3 | < ε$ , then..." would be assuming the conclusion, and a reader would rightly object.

Now you. Prove that $a_{n} = \frac{4 n - 1}{2 n + 3}$ converges to $2$ , showing the scratch work and the proof separately.

Answer

Scratch work. $| a_{n} - 2 | = | \frac{4 n - 1 - 2 (2 n + 3)}{2 n + 3} | = \frac{7}{2 n + 3}$ , which is less than $\frac{7}{2 n}$ . That is below $ε$ once $n > \frac{7}{2 ε}$ .

Proof. Let $ε > 0$ . By the Archimedean property there is $N \in ℕ$ with $N > \frac{7}{2 ε}$ . Let $n \geq N$ . Then $| a_{n} - 2 | = \frac{7}{2 n + 3} < \frac{7}{2 n} \leq \frac{7}{2 N} < ε$ . Since $ε$ was arbitrary, $a_{n} \to 2$ . $□$

Proving that a sequence diverges

A sequence diverges when it converges to no real number at all. The lesson on quantifiers negated the definition: $a_{n}$ fails to converge to $L$ when

\exists ε > 0 \forall N \in ℕ \exists n \geq N (| a_{n} - L | \geq ε)

The roles swap. Now the prover picks one tolerance, the sceptic picks any starting position, and the prover must find a term beyond it that misses. To prove divergence, this must be done for every candidate $L$ , so the proof starts "Let $L$ be any real number."

Example. Prove that $a_{n} = (- 1)^{n}$ diverges.

Let $L$ be any real number, and take $ε = 1$ . Let $N \in ℕ$ . The terms at positions $2 N$ and $2 N + 1$ are both beyond $N$ , and they are $1$ and $- 1$ . If both were within $1$ of $L$ , the triangle inequality would give

2 = | 1 - (- 1) | \leq | 1 - L | + | L - (- 1) | < 1 + 1 = 2

which is impossible. So one of the two positions gives an $n \geq N$ with $| a_{n} - L | \geq 1$ . Since $N$ was arbitrary, $a_{n}$ does not converge to $L$ , and since $L$ was arbitrary, it converges to nothing. $□$

The proof never says which of the two terms misses, only that one does, and an existential claim needs no more.

Now you. Prove that $a_{n} = n$ diverges.

Answer

Let $L$ be any real number, and take $ε = 1$ . Let $N \in ℕ$ . By the Archimedean property there is a natural number $m > L + 1$ ; let $n$ be the larger of $N$ and $m$ . Then $n \geq N$ and $n > L + 1$ , so $| a_{n} - L | \geq n - L > 1$ . Since $N$ and then $L$ were arbitrary, $a_{n}$ diverges. $□$

Uniqueness and the $\frac{ε}{2}$ argument

Writing $lim a_{n} = L$ presumes a sequence has only one limit, and that needs proof.

Theorem. If $a_{n} \to L$ and $a_{n} \to M$ , then $L = M$ .

Proof. Suppose not, so $L \neq M$ , and let $ε = \frac{| L - M |}{2}$ , which is positive. Since $a_{n} \to L$ there is $N_{1}$ with $| a_{n} - L | < ε$ for all $n \geq N_{1}$ , and since $a_{n} \to M$ there is $N_{2}$ with $| a_{n} - M | < ε$ for all $n \geq N_{2}$ . Let $n$ be the larger of $N_{1}$ and $N_{2}$ . By the triangle inequality,

| L - M | \leq | L - a_{n} | + | a_{n} - M | < ε + ε = | L - M |

a contradiction. So $L = M$ . $□$

The idea is to spend the tolerance in halves: two distances each below $\frac{ε}{2}$ sum to less than $ε$ , and taking the later of two positions makes both guarantees hold at once. The same budget proves that limits respect addition.

Example. Prove that if $a_{n} \to L$ and $b_{n} \to M$ , then $a_{n} + b_{n} \to L + M$ .

Let $ε > 0$ . Then $\frac{ε}{2} > 0$ , so, applying the definition to each sequence with tolerance $\frac{ε}{2}$ , there are $N_{1}$ and $N_{2}$ with $| a_{n} - L | < \frac{ε}{2}$ for $n \geq N_{1}$ and $| b_{n} - M | < \frac{ε}{2}$ for $n \geq N_{2}$ . Let $N$ be the larger of $N_{1}$ and $N_{2}$ , and let $n \geq N$ . Then

| (a_{n} + b_{n}) - (L + M) | \leq | a_{n} - L | + | b_{n} - M | < \frac{ε}{2} + \frac{ε}{2} = ε

Since $ε$ was arbitrary, $a_{n} + b_{n} \to L + M$ . $□$

Now you. Prove that if $a_{n} \to L$ , then $a_{n + 1} - a_{n} \to 0$ .

Answer

Let $ε > 0$ . There is $N$ with $| a_{n} - L | < \frac{ε}{2}$ for all $n \geq N$ . Let $n \geq N$ ; then $n + 1 \geq N$ too, so

| a_{n + 1} - a_{n} | \leq | a_{n + 1} - L | + | L - a_{n} | < \frac{ε}{2} + \frac{ε}{2} = ε

Since $ε$ was arbitrary, $a_{n + 1} - a_{n} \to 0$ . $□$ For $(- 1)^{n}$ the consecutive differences are always $\pm 2$ , which gives a second proof that it diverges.

Bounded, increasing, and what completeness buys

A sequence is bounded when some $B$ has $| a_{n} | \leq B$ for every $n$ . Every convergent sequence is. If $a_{n} \to L$ , the definition with $ε = 1$ gives $N$ with $| a_{n} - L | < 1$ for $n \geq N$ , and then $| a_{n} | \leq | a_{n} - L | + | L | < | L | + 1$ . Only the finitely many terms before position $N$ are left, so $B$ , the largest of $| a_{1} |, \dots, | a_{N - 1} |$ and $| L | + 1$ , bounds them all. The converse fails, as the bounded divergent $(- 1)^{n}$ shows. But one extra condition rescues it.

A sequence is increasing when $a_{n} \leq a_{n + 1}$ for every $n$ , and then, by induction, $a_{n} \leq a_{m}$ whenever $n \leq m$ .

Theorem (monotone convergence). A bounded increasing sequence of reals converges to the supremum of its terms.

Proof. The set $A = {a_{n} : n \in ℕ}$ is nonempty and bounded above, so by the completeness axiom it has a supremum $s$ . Let $ε > 0$ . Since $s - ε < s$ , it is not an upper bound of $A$ (the supremum characterisation from the previous lesson), so some term has $a_{N} > s - ε$ . Let $n \geq N$ . Then $s - ε < a_{N} \leq a_{n} \leq s$ , the middle step because the sequence increases and the last because $s$ is an upper bound. So $| a_{n} - s | < ε$ , and $a_{n} \to s$ . $□$

In $ℚ$ the theorem is false. The decimal truncations of $\sqrt{2}$ , namely $1, 1.4, 1.41, 1.414, 1.4142, \dots$ , are rational, increasing and bounded above by $2$ . In $ℝ$ the $n$ th truncation is within $10^{- (n - 1)}$ of $\sqrt{2}$ , and $10^{- (n - 1)} \leq \frac{1}{n}$ , so they converge to $\sqrt{2}$ , exactly as $\frac{1}{n}$ does. If they also converged to some rational $q$ (a real tolerance can always be shrunk to a rational one, so the definition means the same in either setting), uniqueness would force $q = \sqrt{2}$ , which is irrational. So the sequence has no limit in $ℚ$ . The proof breaks at its first line, where a supremum is needed and the rationals do not supply one. That is what completeness buys: sequences that ought to converge, do.

Writing a proof someone else can check

A proof is written for a reader who does not trust its writer, and four habits make it checkable. First, state what is being proved, with the quantifiers put back: "for every $ε > 0$ there is an $N$ " is a claim a reader can hold the proof against, while " $a_{n}$ gets close to $3$ " is not. Second, name every quantity when it is introduced and say where it comes from: "let $ε > 0$ " makes it arbitrary, "there is $N \in ℕ$ with $N > \frac{5}{ε}$ " makes it chosen, and a reader can then check that $N$ depends on $ε$ and on nothing chosen later. Third, justify each step by a definition or an earlier result, by name: the Archimedean property, the triangle inequality, the completeness axiom.

The fourth habit is to read the finished proof back as the sceptic, hunting for the move that would lose the game. Writing "take $N = \frac{5}{ε}$ " loses it, because that is not a natural number for most $ε$ , and the Archimedean property is what repairs it. Writing "let $ε = \frac{1}{n}$ " loses it too, because the sceptic chose $ε$ first and $n$ does not yet exist. A proof that survives that reading can be checked by anyone, line by line, without trusting its author.

What has been built

The course began with patterns that held for forty cases, or for every number below 906,150,257, and then failed, and it has built the means to settle such claims instead. Statements and quantifiers say exactly what is claimed and what its negation claims. Direct proof, cases, the contrapositive, contradiction and induction establish it. Sets, functions and relations are the language the claims are written in, bijections measure infinite sets, and completeness says what the real numbers are. This lesson needed nearly all of it: quantifiers for the definition, negation for divergence, contradiction for uniqueness, the supremum for monotone convergence.

Real Analysis continues directly from here, with the same $ε$ arguments applied to products and quotients of sequences, to continuity, derivatives and integrals, and to the question of which sequences converge when no limit is known in advance. Calculus uses these limits informally, as a tolerance game played with functions rather than sequences, and everything proved here stands behind it. Discrete Mathematics takes induction, sets, functions and relations as its daily tools. Each of them assumes a reader who can take a definition, say exactly what it claims, and prove things from it, which is what this course set out to make.

Proof and Logic, from libre.university