Speak Maths Β· Masterβs road
Proof: a few signs that carry an argument
A proof is a story where every line must follow from the lines before. A handful of signs lets you write the whole argument on one page, and check it line by line.
Draft: written by an AI helper and not yet checked by a teacher.
The alphabet
Read each sign aloud, the way it is written under it.
- Say: let N be defined as p one times p two and so on up to p k, plus oneMeans: βletβ introduces a new name for an object we have just built
- Say: p divides NMeans: N is a whole-number multiple of p; read it left to right, the small one first
- Say: P implies Q (or: if P then Q)Means: whenever P is true, Q is true as well
- Say: P implies Q, and P; therefore QMeans: the three dots say: this line is forced by the lines above
- Say: if not P leads to a contradiction, then PMeans: proof by contradiction: suppose the opposite, reach nonsense, and so the claim holds
- Say: P of 1, and for every n, P of n implies P of n plus one, implies P of n for every nMeans: induction: a first domino falls, and each domino knocks over the next
- Say: end of proof (Q E D)Means: the black square marks the end of the argument: it has been shown
The story: Why there is no largest prime
Tap a line to see its words.
- Suppose there is a largest prime. Then all the primes can be listed, from smallest to largest: p one up to p k.
- Let N be the product of the whole list, plus one.
- Each prime on the list divides the product, so it cannot divide N, which is one more.
- But N is bigger than 1, so it has a prime divisor q, and every prime is on the list.
- So q divides N, and q does not divide N. That is a contradiction.
- Therefore the supposition was false: whichever prime you pick, there is a larger one.
- End of proof.
- Check: the first six primes give 30031, which is not prime, but its prime factors 59 and 509 are new.
In words this story is 600 letters long; in symbols, 119.
Read it
What does it say?
Write it
Which notation says this?
If 4 divides n, then 2 divides n.
The claim holds for 1, and whenever it holds for n it holds for n plus one; therefore it holds for every n.
If supposing the opposite of P leads to a contradiction, then P holds.
p divides N.
If n is even, then n squared is even.
P implies Q, and P holds; therefore Q.
Let N be 2 to the power n, minus 1.
If supposing P leads to a contradiction, then P is false.
The claim holds for 1 and for 2, and whenever it holds for n it holds for n plus 2; therefore it holds for every n.
Every multiple of 10 is a multiple of 5.
P holds, and the proof is finished.
The first domino falls: the claim holds for n equal to 1.
Build it
Tap the tiles in order. One tile does not belong.
If the claim holds for n, then it holds for n plus one.
Let N be the product p one to p k, plus one.
P implies Q, and P; therefore Q.
If not P leads to a contradiction, then P.
The claim holds for 1, and for every n it passes from n to n plus 1; therefore it holds for every n.
3 divides 12 and 12 divides 24; therefore 3 divides 24.
Challenges
Creative puzzles that use every sign of this chapter. Take your time; there is no clock.
1 Who divides whom
Rows are divisors, columns are numbers. Judge each sentence: true or false?
| β | β | β | ||
| β | β | β | ||
| β | β | β |
A tick means the row number divides the column number.
An implication whose left side is false is true whatever the right side says (3 β€ 10, so the third holds). It fails only when the left side is true and the right side false.
2 Six signs of an argument
Pair each line with what it says.
Tap a line, then its meaning.
P β Q and Q β P look alike but are different claims; βletβ gives a name, β₯ marks nonsense, and β closes the proof.
3 The tempting mistake
From βif P then Qβ and P we may conclude Q. One tile is wrong. Find it, then fix it.
Tap the tile that is wrong.
Q β P together with P tells us nothing about Q; the converse is a different claim. The rule needs P β Q.
4 The chain of dominoes
Induction: the first domino falls, and each one knocks over the next; then all of them fall. One tile is wrong. Find it, then fix it.
Tap the tile that is wrong.
The step must go forward, from P(n) to P(n+1), and for every n, not just for one.
5 Skipping dominoes
Domino 1 falls, and each domino knocks over the one two places further on. What can we conclude?
From P(1) the step gives P(3), P(5), P(7) and so on: only the odd ones. P(2) is never pushed.
6 Nonsense from a supposition
Suppose P is false and reach a contradiction. What has been shown?
If βnot Pβ leads to nonsense, βnot Pβ cannot hold, so P does.
7 A prime we did not have
Let N be defined as below. Which of these divides N?
N = 106 = 2 Β· 53. Dividing by 3, 5 or 7 always leaves remainder 1, so none of the listed primes divides it; 2 is a prime outside the list.
8 A two-line proof
Every multiple of 6 is a multiple of 3. Write a proof in symbols: if 6 divides n, then n = 6k = 3(2k), so 3 divides n. End it properly. Then compare.
One way:
Writing n = 6k = 3(2k) shows the factor 3 directly; the black square says nothing is left to prove.
9 Four numbers, four divisors
In this little world n ranges over 4, 6, 9 and 12 only. A tick shows which divides which. Judge each sentence.
| β | β | |||
| β | β | β | ||
| β | ||||
| β | β | β | β |
A tick means the column number divides the row number.
An implication for all n fails as soon as one row has the left tick without the right one: 6 is even but not a multiple of 4, and 9 is a multiple of 3 but not of 6. Divisible by 2 and by 3 does force divisible by 6 here.
10 Parts of a domino run
Pair each line with its part in a proof by induction.
Tap a line, then its meaning.
Induction needs a start and a forward step; the backward step P(n+1) β P(n) is true of many claims yet proves nothing about larger n.
11 Four arrows
Four arrows that look alike. Pair each with what it really says.
Tap a line, then its meaning.
An implication and its contrapositive stand or fall together; the inverse is a different claim. An arrow to β₯ refutes what is on its left.
12 What contradiction proves
Proof by contradiction: if supposing not P leads to nonsense, then P holds. One tile is wrong. Find it, then fix it.
Tap the tile that is wrong.
The supposition that failed was Β¬P, so what stands is P. Concluding Β¬P would be concluding the very thing that led to nonsense.
13 One more than the product
Let N be the product of the listed primes plus one; then no listed prime divides N. One tile is wrong. Find it, then fix it.
Tap the tile that is wrong.
Each p_i divides the product, so dividing N by p_i leaves remainder 1: p_i β€ N. That is the heart of the proof that primes never run out.
14 Five primes and a stranger
N is one more than the product of the first five primes. What follows?
Dividing 2311 by any of 2, 3, 5, 7, 11 leaves remainder 1. In fact 2311 is itself prime: a prime not on the list, as the proof promised.
15 A ladder that starts on step 3
The third domino falls, and from 3 on each knocks over the next. What can we conclude?
Induction gives everything from the base upwards: 3, 4, 5, β¦ Nothing pushes 1 or 2, so they are not covered.
16 The dry ground
If it rained (R), the ground is wet (W). The ground is not wet. What follows?
From P β Q and Β¬Q we get Β¬P: had it rained, the ground would be wet; it is not, so it did not rain. This is the contrapositive at work.
17 Even plus even
The sum of two even numbers is even. Write the proof: let a = 2m and b = 2n, add them, pull out the 2, and finish properly. Then compare.
One way:
Writing a + b = 2(m + n) shows the factor 2 directly; the black square says the argument is complete.
18 No largest even number
Suppose M were the largest even number. Then M + 2 is even and larger: a contradiction. So there is no largest even number. Write the argument. Then compare.
One way:
The supposed largest leads to something larger, which is β₯; by contradiction the supposition fails. Every even number has an even successor two steps on.
Chapter finished. The symbols are yours.
Tell your own
Write a two-line proof of something small β the sum of two even numbers is even β in notation only: a let, an implication, a therefore, and the black square.
Kept on this device only.