Writing a proof as prose
You have written a page of correct steps. How do you know the proof is finished?
Where you are 14 in Proof techniques
Why this exists
A proof is an argument with one destination. Before it starts, somebody has named a claim: the sum of two even numbers is even, or vertical angles are congruent. Every line of the proof is there to get to that claim.
That makes the ending the first thing a careful reader checks. They do not have to follow every step to ask two cheap questions: where did this start, and where did it stop? If it starts from what was given and stops at the claim, the steps in between are worth checking. If it stops anywhere else, it does not matter how good those steps are. The page proves something, just not what was promised.
It is easy to stop when the algebra looks finished instead of when the claim has been reached. This lesson is about telling those two moments apart.
Definition
A proof ends at the line that states the claim itself, with a reason showing that it follows from the lines above. Lines before that one are unfinished. Lines after it are not part of the proof.
Most proofs also say that they have ended, in two small ways.
- A closing sentence that says the claim aloud, usually beginning with therefore, so or hence. The symbol \therefore stands for “therefore” when space is short.
- An end mark: a small square \square or a filled one \blacksquare, or the letters \text{Q.E.D.}, short for the Latin quod erat demonstrandum, “which was to be shown”. Euclid closed his theorems with the Greek words for that same phrase.
The mark is a signpost and nothing more. It carries no mathematics: writing \square after a line does not make that line the claim.
To decide whether a last line really is the claim, compare the two on three points.
- The subject. Both must be about the same objects. A proof that n^2 is even is not a proof that n is.
- The scope. Both must cover the same cases: one case, every case, or some case.
- The direction. Both must run the same way. “If P then Q” is not “if Q then P”, and x \le y is not y \le x.
These three checks catch most wrong endings, but passing them is not the whole test. “n^2 is odd” matches “n^2 is even” on all three points and says the opposite, and x \le y falls short of a claim that x < y. In the end the last line has to say what the claim says. When it says the same thing in a different form, one more line closes the gap, and that line gives its reason. Examples 1 and 4 show this.
Intuition
Think of the claim as an address written down before you set out. The given facts are where you start, each line is a step, and the walk is over when you are standing at the address: not in the street outside it, and not at a different house that looks the same from the road. Figure 1 shows four walks aimed at one claim.
The first walk ends. The second stops short: its last line is true, but one step is still missing. The third arrives somewhere real, often the converse of the claim or one special case of it, and that is exactly why it is easy to mistake for the end. The fourth does end, and then keeps going. If the extra lines are also true and justified, nothing is lost, but the proof was already over, and a reader who meets an unproved extra claim after the end mark has a reason to trust the page less.
This is why it helps to write the claim at the top of the page before writing the first line of the proof, and to keep looking back at it. The last line is not something discovered at the bottom of the page. It is the statement everything else is bent toward.
Results
Ending rule. A proof of a claim is finished at the first line that states the claim, matching it in subject, scope and direction, and that follows by a stated reason from the givens, definitions, known results and earlier lines.
Equivalent forms. If the last line you reach is the claim in a different form, for example an equation where the claim uses a word, add one line that says so and names its reason. That added line is the ending.
What the ending looks like depends on the shape of the claim.
- If P, then Q. Start by supposing P. The last line is Q.
- For every x in a set, S(x). Start by taking x to be an arbitrary member of the set. The last line is S(x), followed by a sentence saying that since x was arbitrary, it holds for every x.
- There is an x with S(x). Start by choosing or building a particular x. The last line names that x and checks that S(x) is true of it.
- P if and only if Q. Start by proving P \Rightarrow Q. Each direction has its own last line, and only the second one, Q \Rightarrow P, ends the proof.
- Anything proved by cases. Start by splitting into cases that leave nothing out. The last line is one sentence after the final case, saying that in every case the claim holds.
- Anything proved by contradiction. Start by supposing the claim is false. The last line comes one line after the contradiction, and it is the claim itself.
Why it is true
A proof is a chain of small statements, each of the form “this follows from what came before”. Read down the page: the first line follows from the givens alone, the second from the givens and the first, and so on. So after line k, the only thing that has been shown is
The claim to be proved is a different statement:
These two are the same statement exactly when line k is the claim. For any other last line, what has been shown is something else.
- If line k is an earlier step, only that step has been shown, and the proof stops short.
- If line k is a different statement, such as the converse or one special case, that different statement has been shown, and the proof ends somewhere else.
- If line k is stronger than the claim and implies it, enough has been shown, but the reader is owed one line that says it implies the claim. That line is then the last one.
The same reading explains why a chain that starts at the claim proves nothing by itself. If you reason forward from the claim and arrive at a true statement T, you have shown \text{claim} \Rightarrow T. The proof needs T \Rightarrow \text{claim}, and true statements can follow from false ones. Example 7 shows this happening.
An end mark is not a statement, so it sits outside the chain and nothing follows from it. Lines after the claim sit outside it too: the chain was already complete, so each of them needs a proof of its own.
Worked examples
Closing the gap between a line and the claim
Claim: the sum of two even integers is even. A writer has produced this, and the page ends here.
Proof. Let m and n be even integers. Then m = 2a and n = 2b for some integers a and b. So m + n = 2a + 2b = 2(a + b).
Has the proof ended? If not, add what is missing.
SolutionCompare the last line with the claim. The last line is m + n = 2(a + b). The claim is that m + n is even. The subject matches, since both are about m + n. The scope matches too, because m and n were any even integers. But the last line is an equation and the claim is a word.
The word has a definition: an integer is even when it is two times an integer. Here a + b is an integer, because a sum of two integers is an integer, so 2(a + b) is exactly “two times an integer”. One more sentence finishes the proof:
Since a + b is an integer, m + n is two times an integer, which is what it means to be even. Therefore the sum of two even integers is even. \square
The first added sentence gives the reason, and the second says the claim in its own words, so the reader never has to translate from the equation back to the claim.
A claim about every integer
Claim: for every integer n, the number n^2 + n is even. Write a proof and end it.
SolutionA claim about every integer cannot be checked one integer at a time. Take n to be any integer, and use the fact that every integer is even or odd to split into two cases.
Case 1: n is even. Then n = 2k for an integer k, so n^2 + n = 4k^2 + 2k = 2(2k^2 + k), which is two times an integer.
Case 2: n is odd. Then n = 2k + 1 for an integer k, so
which is two times an integer.
Now the ending, which takes two sentences that do two different jobs.
The first closes the cases: every integer is even or odd, so these two cases cover n, and in each of them n^2 + n is even. The second closes the scope: since n was an arbitrary integer, n^2 + n is even for every integer n. \square
Stopping after Case 2 would leave the reader to supply both sentences.
Five last lines, one claim
Claim: if a and b are even, then ab is even. Five writers each begin “Let a = 2m and b = 2n for integers m and n”, and each finishes differently. Which of them has ended the proof?
- (a) Then ab = 4mn.
- (b) Then ab = 2(2mn), which is two times an integer, so ab is even.
- (c) Then ab = 4mn, so if ab is even, then a and b are even.
- (d) Then ab = 4mn, so ab is even when a = 4 and b = 6.
- (e) Then ab = 2(2mn), which is two times an integer, so ab is even. Also a + b = 2(m + n), so a + b is even.
Put each last line beside the claim and compare subject, scope and direction.
(a) stops short. 4mn is a product, not yet the word “even”. The missing step is to write 4mn = 2(2mn) and use the definition.
(b) ends the proof. Its last line says ab is even, for any even a and b, and it gives the reason.
(c) arrives at the converse, so the direction is wrong. The converse is not merely unproved, it is false: 2 \cdot 3 = 6 is even, but 3 is odd.
(d) checks one case, so the scope is wrong. It is true that 4 \cdot 6 = 24 is even, but that says nothing about other even numbers.
(e) ends after its first sentence, exactly as (b) does. The second sentence is true and justified, so nothing is wrong with it, but it is not part of the proof of this claim.
Only (b) and (e) contain an ending, and only (b) stops there.
A last line in the claim’s own form
Claim: vertical angles are congruent. In Figure 2, \angle 1 and \angle 3 are vertical angles. Finish this proof that \angle 1 \cong \angle 3, and say which row is the ending.
| Statements | Reasons |
|---|---|
| m\angle 1 + m\angle 2 = 180^\circ | \angle 1 and \angle 2 form a linear pair |
| m\angle 3 + m\angle 2 = 180^\circ | \angle 3 and \angle 2 form a linear pair |
| m\angle 1 + m\angle 2 = m\angle 3 + m\angle 2 | both sums equal 180^\circ |
| m\angle 1 = m\angle 3 | subtract m\angle 2 from both sides |
The claim is about congruence, \angle 1 \cong \angle 3, and the last row is about measures, m\angle 1 = m\angle 3. The subject matches, the scope matches, and the direction matches, but the form does not: congruence is a statement about angles, and equal measures is a statement about numbers. They are linked by the definition of congruent angles, which says angles are congruent exactly when their measures are equal. So there is one row to add:
| Statements | Reasons |
|---|---|
| \angle 1 \cong \angle 3 | angles with equal measures are congruent |
That row is the ending. The proof is finished there, and not one row earlier.
Check. Try numbers. If m\angle 2 = 56^\circ, the two linear pairs give m\angle 1 = m\angle 3 = 180^\circ - 56^\circ = 124^\circ, so the measures really are equal.
Ending a proof by contradiction
Claim: there is no smallest positive real number.
Proof. Suppose there is a smallest positive real number, and call it s. Then s > 0, so \displaystyle \frac{s}{2} is also positive, and \displaystyle \frac{s}{2} < s because halving a positive number makes it smaller. So \displaystyle \frac{s}{2} is a positive real number smaller than s. This contradicts the choice of s as the smallest.
Has the proof ended?
SolutionNot yet. The last line says that a contradiction has been reached, and a contradiction is not the claim. Every step after the supposition was allowed, so the clash can only come from the supposition made at the start: that a smallest positive real number exists.
The claim says exactly that this supposition is false, so the ending is one more line that says it:
Therefore there is no smallest positive real number. \square
The proof began by supposing the opposite of the claim, so it ends by stating the claim, not by stating the clash.
Both directions
Claim: an integer n is even if and only if n + 1 is odd.
Solution“If and only if” makes two claims in one sentence, so there are two last lines and only one of them ends the proof.
First direction: if n is even, then n + 1 is odd. Suppose n is even, so n = 2k for an integer k. Then n + 1 = 2k + 1, which is two times an integer plus one, so n + 1 is odd.
That line closes the first direction, but the proof is not over. What has been shown is only that an even n gives an odd n + 1. The other direction has not been touched.
Second direction: if n + 1 is odd, then n is even. Suppose n + 1 is odd, so n + 1 = 2k + 1 for an integer k. Subtracting 1 from both sides gives n = 2k, so n is even.
Both directions have now been shown, so n is even if and only if n + 1 is odd. \square
The second direction supposes the conclusion of the first and arrives at the supposition of the first. That is what makes the two together an “if and only if”.
A proof found backwards
Claim: for every real number x, x^2 + 1 \ge 2x. Write the proof, and explain why the scratch work that finds it is not the proof.
SolutionScratch work usually starts from the claim. x^2 + 1 \ge 2x says the same as x^2 - 2x + 1 \ge 0, which is (x - 1)^2 \ge 0, and that is true of every real x because a square is never negative.
That scratch work shows only that the claim leads to a true statement. The written proof runs the other way, from the true statement to the claim:
Proof. Let x be any real number. A square is never negative, so (x - 1)^2 \ge 0. Expanding, x^2 - 2x + 1 \ge 0. Adding 2x to both sides keeps the inequality, so x^2 + 1 \ge 2x. Since x was arbitrary, this holds for every real x. \square
Here is why the direction matters. Run the same scratch work on the false claim 3 = -3. Square both sides and you get 9 = 9, which is true. But that chain shows only that 3 = -3 leads to 9 = 9. The other direction fails, because squaring loses the sign: (-3)^2 = 9 does not make -3 = 3. A chain that starts at the claim and reaches a true line has not ended anywhere. The proof above works because its last line is the claim, reached by steps that are each allowed in the direction they are written.
Boundaries
A matching last line is necessary, not enough. A last line that is the claim ends the proof only if every line above it is justified. A gap in the middle is not repaired by a correct ending, and a neat \square does not hide it from a careful reader.
Only claims have endings. A problem that asks you to find a number ends with the number and a check of it. Trying a claim on examples ends with “it works for these”, which is not a proof, as why a pattern is not a proof explains.
A weaker claim ends at the weaker claim. If you can only show one special case, or one direction of an “if and only if”, the proof ends there and says so. It does not borrow the closing sentence of the larger claim.
A stronger result ends a proof of a weaker one, with one line. Having proved a statement for every real number, you may end a proof of it for x = 2 with “in particular, for x = 2”, and then the instance. The line links the two, and it is the ending.
A long proof has more than one ending. When a proof leans on a lemma (see theorems, lemmas and corollaries), the lemma ends first, with its own last line and mark, and the theorem ends afterwards.
The mark is a convention, and conventions vary. Some texts use \text{Q.E.D.}, some a square, and a two-column proof often has no mark because its last row is the claim. A construction may end with \text{Q.E.F.}, quod erat faciendum, “which was to be done”. None of this changes the mathematics.
Where this goes next
Each technique has its own shape of ending. A direct proof ends on the claim. Proof by contradiction ends one line after the clash, and proof by cases ends after the last case is closed. An if and only if proof ends after its second direction, and induction ends with the sentence that hands the result to every whole number.
Setting the ending down well is part of writing a proof as prose, and in a two-column layout it is the last row of a two-column proof. The other end of a proof, what may be assumed before the first step, is the subject of what may be assumed and what must be shown.
Exercises
Reading the claim
- A proof is to show “If x is a multiple of 6, then x is a multiple of 3.” What does its first line suppose, and what must its last line say?
- A proof is to show “For every integer n, n^2 - n is even.” Besides an equation, what sentence must the ending contain, and why?
- A proof is to show “There is a positive integer less than 20 that is a multiple of both 4 and 6.” Write the ending of the proof.
- How many last lines does a proof of “P if and only if Q” have, and which one ends the proof?
Does it end?
Each exercise gives a claim and the last lines of a proof. Say whether the proof has ended. If it has not, say what is missing.
- Claim: “If n is even, then n^2 is even.” Last line: “Then n = 2k, so n^2 = 4k^2.”
- Claim: “If n is even, then n^2 is even.” Last lines: “So n^2 is even. Therefore, if n^2 is even, then n is even.”
- Claim: “For every integer n, n^2 + n is even.” Last line: “Take n = 5. Then 5^2 + 5 = 30, which is even, so the claim is true.”
- Claim: “If a and b are odd, then a + b is even.” Last line: “Write a = 2m + 1 and b = 2n + 1. Then a + b = 2m + 2n + 2 = 2(m + n + 1).”
- Claim: “There is no largest integer.” Last lines: “Suppose N is the largest integer. Then N + 1 is an integer and N + 1 > N. This is a contradiction.”
- Claim: “If n is even, then n + 1 is odd.” Last line: “Therefore n + 1 is odd or n is even.”
Finishing a proof
- Claim: “If n is odd, then n + 2 is odd.” The proof begins “Suppose n is odd, so n = 2k + 1.” Write the rest, ending included.
- Claim: “The sum of three consecutive integers is a multiple of 3.” Write a proof, ending included.
- Claim: “For every real number x, x^2 - 6x + 10 > 0.” Write a proof that ends correctly. Hint: write the left side as a square plus a number.
- Claim: “For every real number x, x^2 + 4 \ge 4x.” Your scratch work will run from the claim. Write the proof so that it runs from a true statement to the claim.
- Two vertical angles measure (2x + 10)^\circ and (3x - 20)^\circ. Claim: each of them measures 70^\circ. Write the proof, and say why x = 30 is not its last line.
Claims with parts
- Claim: “An integer n is odd if and only if n + 3 is even.” Write the proof, with the last line of each direction.
- Claim: “For every integer n, n^2 leaves remainder 0 or 1 when divided by 4.” Prove it by splitting into the cases n even and n odd, and write the two closing sentences.
- In Figure 2, a proof that \angle 2 \cong \angle 4 has reached the line m\angle 2 = m\angle 4. Write the one line that finishes the proof.
Reasoning
- A writer puts \square after a step that is not the claim. Does the mark make the proof finished? What does a mark contribute?
- A proof that x^2 + 1 > 0 for every real number x has ended. A reader now asks for a proof that x^2 + 1 > 0 when x = 2. Write the one line that finishes it, and say why that line is allowed to end the proof even though it is not the same sentence as the original claim.
- Why is “this is a contradiction” never the last line of a proof by contradiction?
- A student proves “4 = -4” by squaring both sides to get 16 = 16, which is true, and then says the claim holds. Check the arithmetic, and explain where the ending fails.
Answers
- The first line supposes “x is a multiple of 6”, so x = 6k for an integer k. The last line must say “x is a multiple of 3”. In between, x = 6k = 3(2k) and 2k is an integer.
- The sentence that says the scope is covered: “since n was arbitrary, this holds for every integer n”. The argument works on one arbitrary integer, and that sentence is what turns it into a statement about all of them. The equation alone is only about the n in hand.
- 12 = 4 \cdot 3 and 12 = 6 \cdot 2, and 0 < 12 < 20, so 12 is such an integer. The ending names the integer and checks every condition the claim sets.
- Two last lines, one for each direction. The second one ends the proof, because only then have both “if” and “only if” been shown.
- No, it stops short. 4k^2 is not yet the word “even”. It needs n^2 = 4k^2 = 2(2k^2), and 2k^2 is an integer, so n^2 is two times an integer, which makes it even. Then the closing sentence: therefore n^2 is even.
- The proof has already ended at “So n^2 is even”, if the reason was given. The last sentence is the converse, which is a different claim. It happens to be true here, but nothing above proves it, so it needs a proof of its own. It is not an ending for this claim.
- No. It checks one integer and the claim is about every integer, so the scope is wrong. 5^2 + 5 = 30 is even, but that says nothing about n = 6 or n = -3.
- It stops one line short. The last line has the form 2(m + n + 1). It still needs “m + n + 1 is an integer, so a + b is two times an integer, so a + b is even”, and then the closing sentence: therefore a + b is even.
- No. “This is a contradiction” is not the claim. The proof needs one more line: therefore there is no largest integer. The contradiction shows that the supposition, that N is the largest integer, cannot be true, and the claim says exactly that.
- No. This line is true the moment we suppose that n is even, because its second half is the supposition itself. It says nothing about n + 1 on its own, so arriving at it proves nothing. The claim is that n + 1 is odd, and that is what the last line must state.
- Then n + 2 = 2k + 3 = 2(k + 1) + 1. Since k + 1 is an integer, n + 2 is two times an integer plus one, so n + 2 is odd. Therefore, if n is odd, then n + 2 is odd.
- Call the three integers n, n + 1 and n + 2. Their sum is n + (n + 1) + (n + 2) = 3n + 3 = 3(n + 1). Since n + 1 is an integer, the sum is a multiple of 3. Since n was arbitrary, the sum of any three consecutive integers is a multiple of 3.
- Write x^2 - 6x + 10 = (x - 3)^2 + 1. A square is never negative, so this is at least 1, and 1 > 0. Therefore x^2 - 6x + 10 > 0, and since x was arbitrary, this holds for every real x.
- Let x be any real number. Then (x - 2)^2 \ge 0, which expands to x^2 - 4x + 4 \ge 0. Adding 4x to both sides gives x^2 + 4 \ge 4x. The scratch work ran the other way: subtracting 4x from the claim gives (x - 2)^2 \ge 0.
- Vertical angles are equal, so 2x + 10 = 3x - 20, which gives x = 30. Then 2(30) + 10 = 70 and 3(30) - 20 = 70. The last line is: therefore each of the two angles measures 70^\circ. The line x = 30 is a fact about the unknown, but the claim is about the angles, so the subject does not match.
- First direction: if n is odd, n = 2k + 1, so n + 3 = 2k + 4 = 2(k + 2), which is even. That closes only the first direction. Second direction: if n + 3 is even, n + 3 = 2m, so n = 2m - 3 = 2(m - 2) + 1, which is odd. Therefore n is odd if and only if n + 3 is even.
- If n = 2k, then n^2 = 4k^2, which has remainder 0. If n = 2k + 1, then n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1, which has remainder 1. Closing sentences: every integer is even or odd, so these cases cover every integer, and in each the remainder is 0 or 1. Since n was arbitrary, this holds for every integer n.
- Therefore \angle 2 \cong \angle 4, since angles with equal measures are congruent. The claim is about congruence and the last line was about measures, so the definition closes the gap.
- No. A mark is not a statement: it is not true or false and nothing follows from it. Putting it after a step that is not the claim only announces that the writer has stopped, and the reader still has to compare the last line with the claim. The mark’s whole job is to tell the reader where the proof ends.
- In particular, for x = 2, we have x^2 + 1 = 2^2 + 1 = 5 > 0. The new claim is one instance of what was already proved for every x, and the words “in particular” name that as the reason. A line that is not word for word the claim may end a proof when it is joined to the claim by a stated reason.
- The contradiction shows that the supposition made at the start is false. The claim is that supposition’s opposite, so one more line must say it, as in “therefore there is no largest integer”. Until the claim itself is written, the proof has only shown that something clashed.
- 4^2 = 16 and (-4)^2 = 16, so 16 = 16 is true. The chain, though, runs from the claim to a true line, so it shows only that 4 = -4 leads to 16 = 16. The proof would need the reverse, that 16 = 16 leads to 4 = -4, and it does not, because squaring loses the sign: (-4)^2 = 4^2 while -4 \ne 4.