What may be assumed and what must be shown
Someone says a claim is always true. While you argue for it, what may you take for granted, and what is left for you to earn?
Where you are 14 in Proof techniques
Why this exists
A claim can be tested. Try ten numbers, or draw five pictures, and it holds every time. That is evidence, and it is worth having. It is not a proof, because the eleventh number or the sixth picture might break it, and nothing you did rules that out.
A proof does something stronger. It is a short chain of statements that makes the claim unavoidable for anyone who accepts where the chain starts. That last part carries all the weight. The chain is only as good as its starting point, so a proof has to be strict about what it starts from.
There are two ways to get this wrong. Start from too little, and you cannot take a single step. Start from too much, and the proof looks fine but proves nothing: it may have quietly started from the very thing it was meant to show, or from what a picture seems to say, or from one lucky example. This lesson fixes the rules: exactly what a proof may assume, and exactly what it must show.
Definition
Nearly every claim worth proving is a conditional: it has the shape “if P, then Q”, even when the words hide it. “The sum of two even integers is even” means: if a and b are even integers, then a + b is even. The shape is written
- P is the hypothesis, also called the given. It is what the claim is allowed to start from.
- Q is the conclusion, what the proof must prove.
A proof of P \Rightarrow Q is a finite list of statements whose last line is Q, where every line is there for one of these reasons, and no other.
- It is a given: part of P.
- It is a definition being used: a word swapped for what the word means, or the meaning swapped back for the word. A definition works in both directions, so “n is even” and “n = 2k for some integer k” may replace each other (definitions are biconditional).
- It is an accepted fact: a postulate, which is a fact we agree to start from, or a theorem that has already been proved by other means (definitions, postulates and theorems).
- It follows from earlier lines by algebra or by a rule of logic: substituting equals for equals, adding the same number to both sides, and the like.
- It names something the claim talks about, and gives it only the properties the claim gives it. “Let n be an integer” lets n stand for any integer at all, and lets you use that n is an integer, and nothing more.
Things that are not on the list are just as important. The conclusion is not on it. “It looks true in the figure” is not on it. “It worked for the numbers I tried” is not on it. “It is obvious” is not on it, unless a reason comes with it.
Intuition
Picture crossing a river on stepping stones. The given is the bank you start on. Each stone you step onto has to be solid already: a given, a definition, a proved fact, or something the stones behind you already hold up. The far bank is the conclusion. You may not declare that you are already standing on the far bank, and you may not step onto a stone that is “probably solid”.
There is a second way to see it, as a promise. The person who states the claim is promising: whenever the given is true, the conclusion is true too. A proof only has to keep that promise. So you may take the given for granted, because the promise is about what follows when the given holds. And you may not take the conclusion for granted, because the conclusion is the thing that was promised.
Results
The shape of a proof. To prove P \Rightarrow Q, assume P, and from it reach Q.
In words: assume P, explain, explain, explain, and so Q.
Every line has a source. Each line is a given, a definition, an accepted fact, a consequence of earlier lines, or the naming of an object. A line that is none of these is a gap.
A chosen example is not a proof. A claim about every integer, or every triangle, needs an argument that works for an arbitrary one. A single example can prove only a claim that says some example exists, and a single counterexample is enough to disprove a claim about all of them.
A claim and its converse are different claims. Having proved P \Rightarrow Q tells you nothing about Q \Rightarrow P. Each has its own given and its own conclusion.
Why it is true
Why the given may be assumed. A conditional can only fail in one way. Here is its truth table, where T means true and F means false.
| P | Q | P \Rightarrow Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The claim is false in the second row only: the given holds and the conclusion does not. To show the claim is never false, we have to show that row cannot happen. So we suppose the given holds, which is the situation the second row starts from, and we show the conclusion must then hold. The two rows where P is false need no work, because the promise says nothing about them. (The conditional’s truth table is worked out in its own lesson.)
Why the conclusion may not be assumed. Suppose a proof could begin by assuming Q. Then “if x = 2, then x^2 = 9” would be proved at once: assume x^2 = 9, and stop. But that claim is false, since 2^2 = 4. A method that proves a false claim is not a method. Assuming Q turns the job into proving Q \Rightarrow Q, which is trivial, and which is not the claim.
Why a definition may replace a word. A definition is an agreement that a word means a phrase. Swapping the word for the phrase changes nothing, in either direction, so there is nothing to prove and no risk in doing it.
Why “let n be an integer” covers every integer. Suppose the lines that follow use only the fact that n is an integer. Then the same lines, word for word, work for n = 4, for n = -17 and for any other integer. The proof has no way of depending on a property it was never given. \blacksquare
Worked examples
Sorting a claim into given and prove
For each claim, write it as “if ... then” and name the given and the conclusion.
(a) The sum of two even integers is even.
(b) Vertical angles are congruent.
(c) A square is a rectangle.
SolutionThe claims talk about things in general, so the first job is to give those things names. The names come from the claim itself, and they are what the given is about.
(a) If a and b are even integers, then a + b is even. The given is that a and b are even integers. The conclusion is that a + b is even.
(b) If segments \overline{AB} and \overline{CD} cross at a point E, then \angle AEC \cong \angle BED. The given is the crossing, which puts E between A and B and between C and D, so the two angles sit opposite each other. The conclusion is the congruence of one pair of opposite angles. (The other pair is proved the same way.)
(c) If ABCD is a square, then ABCD is a rectangle. The given is that the figure is a square. The conclusion is that it is a rectangle.
In each case the conclusion is a sentence you may not use until the last line. The given, on the other hand, is on the table from the first line. Sorting the claim this way is the first thing a proof does, and Given, prove and the diagram does it for geometry in detail.
A first proof
Prove that the sum of two even integers is even.
SolutionThe given is that a and b are even integers, and the conclusion is that a + b is even. A proof has to use what “even” means, so we start from the definition: an integer n is even when n = 2k for some integer k.
| Statements | Reasons |
|---|---|
| 1. a and b are even integers | given |
| 2. a = 2k for some integer k | definition of even: line 1 |
| 3. b = 2m for some integer m | definition of even: line 1 |
| 4. {a + b = 2k + 2m} | substitution: lines 2 and 3 |
| 5. {a + b = 2(k + m)} | distributive property: line 4 |
| 6. k + m is an integer | accepted fact: a sum of integers is an integer |
| 7. a + b is even | definition of even: lines 5 and 6 |
Read the reasons column. Line 1 is the given. Lines 2, 3 and 7 are the definition of even, used forwards in lines 2 and 3 and backwards in line 7. Lines 4 and 5 are algebra on earlier lines. Line 6 is an accepted fact. No line is there because it “looks true”, and the conclusion appears only as the last line.
A proof about a segment
In Figure 2, M is the midpoint of \overline{AB}. Prove that AB = 2 \cdot AM.
The given is that M is the midpoint of \overline{AB}. The ticks on the figure repeat part of that, but the proof starts from the words.
| Statements | Reasons |
|---|---|
| 1. M is the midpoint of \overline{AB} | given |
| 2. M lies between A and B | definition of midpoint: line 1 |
| 3. AM = MB | definition of midpoint: line 1 |
| 4. {AM + MB = AB} | Segment Addition Postulate: line 2 |
| 5. {AM + AM = AB} | substitution: line 3 into line 4 |
| 6. AB = 2 \cdot AM | combining like terms: line 5 |
The definition of a midpoint says two things at once: the point is on the segment, and it splits the segment into two equal pieces. Lines 2 and 3 use both halves. Line 4 is a postulate, an accepted fact about how lengths along a line add up (the Segment Addition Postulate). The proof never measures anything.
One letter or two
A student tries to prove that the sum of two odd integers is even:
“Let a = 2k + 1 and b = 2k + 1. Then a + b = 4k + 2 = 2(2k + 1), which is even.”
Is this a proof? If not, repair it.
SolutionIt is not. Each line is correct algebra, but look at what line one did. By writing 2k + 1 twice with the same k, it made a and b equal. The claim gave no such thing: a and b are two odd integers, and they may differ. The pair 3 and 5 is a fair test. Here 3 = 2(1) + 1 and 5 = 2(2) + 1, so the two need different values of k, and the student’s proof never covers it. It proves the claim only for pairs of equal numbers, such as 3 and 3.
Repair: give each unknown its own letter, unless the claim says they are equal.
| Statements | Reasons |
|---|---|
| 1. a and b are odd integers | given |
| 2. a = 2k + 1 for some integer k | definition of odd: line 1 |
| 3. b = 2m + 1 for some integer m | definition of odd: line 1 |
| 4. {a + b = 2k + 2m + 2} | addition: lines 2 and 3 |
| 5. {a + b = 2(k + m + 1)} | distributive property: line 4 |
| 6. k + m + 1 is an integer | accepted fact: sums of integers are integers |
| 7. a + b is even | definition of even: lines 5 and 6 |
Assuming that two things are equal, or different, or non-zero, when the claim did not say so, is the same mistake as assuming part of the conclusion. It is a line with no source.
Starting from the answer
A student “proves” that -2 = 2:
“Suppose {-2 = 2}. Square both sides: (-2)^2 = 2^2, so {4 = 4}. That is true, so {-2 = 2}.”
Every step is legal algebra. Where does it go wrong?
SolutionThe first line assumes the conclusion. That is the error, and the false result shows what it costs.
From a false statement, a legal step can land on a true one. Squaring both sides turns {-2 = 2} into {4 = 4}, because squaring forgets the sign. So arriving at something true tells us nothing about the statement we started from. The steps only run one way: from {-2 = 2} you can reach {4 = 4}, but from {4 = 4} you cannot get back.
Working backwards from a conclusion on scrap paper is a fine way to find an idea. It becomes a proof only if you then write it forwards, from the given, with every step justified in that direction. Backwards working is safe exactly when every step can be reversed, and squaring cannot be.
A hidden assumption
A student “proves” that if x^2 = x, then x = 1:
“Start from x^2 = x. Divide both sides by x. This gives x = 1.”
What was assumed without being given? Then state and prove a true version.
SolutionDividing by x is only allowed when x \neq 0, and the claim never said x is not zero. So the student used a line with no source. It matters, because x = 0 satisfies x^2 = x and is not 1. The claim as stated is false, and x = 0 is a counterexample.
A true version says what really follows: if x^2 = x, then x = 0 or x = 1.
| Statements | Reasons |
|---|---|
| 1. x^2 = x | given |
| 2. x^2 - x = 0 | subtract x from both sides: line 1 |
| 3. x(x - 1) = 0 | factor the left side: line 2 |
| 4. {x = 0} or {x - 1 = 0} | zero-product property: line 3 |
| 5. {x = 0} or {x = 1} | add 1 to both sides of the second equation: line 4 |
Line 4 uses the zero-product property, an accepted fact: a product is zero only if one of its factors is. The proof never divided, so it never had to assume x \neq 0.
Both directions
Prove that an integer n is even if and only if n^2 is even.
Solution“If and only if” makes two claims, and each needs its own proof with its own given (proving an if and only if).
First claim: if n is even, then n^2 is even. The given is that n is even, so n = 2k for some integer k. Then n^2 = (2k)^2 = 4k^2 = 2(2k^2), and 2k^2 is an integer, so n^2 is even by the definition.
Second claim: if n^2 is even, then n is even. Now the given is that n^2 is even. Writing n^2 = 2m does not lead anywhere, because nothing in it tells us how to write n itself. So we use an equivalent form of the claim, its contrapositive: if n is not even, then n^2 is not even (a conditional and its contrapositive say the same thing).
The contrapositive is a new conditional, and it has its own given and its own conclusion. Its given is that n is odd, since an integer that is not even is odd (an accepted fact). Its conclusion is that n^2 is odd. From the given, n = 2k + 1 for some integer k, so
and 2k^2 + 2k is an integer, so n^2 is odd. This proves the contrapositive, and the contrapositive is equivalent to the second claim.
Both claims are proved, so n is even exactly when n^2 is even. Notice that in the second half the assumption “n is even” would have been forbidden, since that is what the second half is trying to reach. What you may assume depends on which claim you are proving at that moment.
Boundaries
A proof shows what follows from the given. It does not show the given ever happens. “If a whole number is both even and odd, then it equals 1000” is true, because no whole number is both, so there is never a case that could break it. Nothing about 1000 is being claimed. A true claim with an impossible given is empty, and the proof of it does not make the given possible. In the same way, when a given is false in a particular case, the proof is still correct; it has simply earned nothing about that case.
Something is always left unproved. Every proof rests on postulates, and those are agreed, not shown. They can be chosen differently. Change the postulate about parallel lines and a different list of theorems follows (the parallel postulate). A proof is a promise relative to its starting points, and never a promise about the world.
An accepted fact must not depend on the claim. You may use a theorem that was proved earlier, but only if its own proof did not use the theorem you are now proving. Using a result that leans on yours makes a circle: each seems to support the other, and neither is supported.
One example never proves a claim about every case, but one counterexample always disproves it. A claim about all integers is settled for good the moment you find one integer that breaks it. “If n is prime, then n is odd” fails at n = 2 and is finished. See counterexamples.
Where this goes next
Everything later in proof is this anatomy, dressed for a particular job. A two-column proof puts the line and its source side by side, so that the source of every line is visible at once. A direct proof is the plain shape from this lesson: assume the given, reach the conclusion. Proof by contraposition and by contradiction change what is assumed at the start, as the second half of the last example did: each one says plainly what it is supposing, and then proves the conditional that the supposition makes.
In geometry the same rules meet a new source of trouble, the picture, and what a diagram lets you assume says which marks count as givens and which do not. To practice naming a reason for every line, go to giving a reason for every step. And for proving something about even and odd numbers with nothing more than their definitions, see proving statements about even and odd numbers.
Exercises
Sorting the statement
- Write “A number divisible by 6 is divisible by 3” as “if ... then”, and name the given and the conclusion.
- Do the same for “The product of an even integer and any integer is even.”
- Do the same for “Two lines that cross at one right angle make four right angles.”
- Write the converse of the claim in Exercise 1. Is the converse true?
What each line may use
- Here is a proof that if n is odd, then n + 2 is odd. For each line, say which kind of reason it has: a given, a definition, an accepted fact, or algebra on earlier lines. Lines: (1) n is odd. (2) n = 2k + 1 for some integer k. (3) n + 2 = 2k + 3. (4) 2k + 3 = 2(k + 1) + 1. (5) k + 1 is an integer. (6) n + 2 is odd.
- A proof of “if a and b are even integers, then ab is even” is being written. Which of these may appear as a line, and why? (i) a = 2k for some integer k. (ii) ab = 2m for some integer m. (iii) a = 6 and b = 4. (iv) b = 2j for some integer j.
- A student tests “the sum of two odd integers is even” on 3 + 5, 7 + 9, 1 + 11 and 13 + 21, and writes “so it is proved”. What do the four tests show, and what does the student still owe?
Writing short proofs
- Prove: if a is even and b is any integer, then ab is even.
- Prove: if n is even, then n + 5 is odd.
- Prove: if a and b are odd integers, then ab is odd.
- Prove: if a divides b and a divides c, then a divides b + c. (Here “a divides b” means b = ar for some integer r.)
- Prove: the sum of three consecutive integers is divisible by 3.
- M is the midpoint of \overline{AB}, with AM = 3x + 2 and MB = 5x - 8. Find x and AB, and name the source of each line of your work.
- \angle 1 and \angle 2 form a linear pair, with m\angle 1 = (2x + 10)^\circ and m\angle 2 = (3x - 5)^\circ. Find x and both angles, and name the source of each line.
- Given m\angle A + m\angle B = 90^\circ and m\angle B + m\angle C = 90^\circ, prove that m\angle A = m\angle C.
Finding the flaw
- A student “proves” that if a and b are even, then a + b is divisible by 4: “Write a = 2k and b = 2k. Then a + b = 4k.” What went wrong, and is the claim true?
- “If n is prime, then n is odd.” Is this claim true? Justify your answer.
- A student “proves” that if x^2 = 25, then x = 5: “Take x = 5. Then x^2 = 25, which is the given. Done.” What did the student actually prove, and is the claim true?
- A student “proves” that if ab = ac, then b = c, by dividing both sides by a. What was assumed without being given? Show that the claim can fail.
Reasoning
- Explain why a proof may assume the given but may not assume the conclusion.
- In the proof of Example 3, suppose M were only known to lie between A and B, and were not said to be the midpoint. Which lines would still be justified, and which would not?
- “If n is a multiple of 4, then n is even” is true. Write its converse, say whether it is true, and say what a proof of the original claim tells you about the converse.
- Prove: if n^2 is odd, then n is odd. (Hint: prove the contrapositive.)
- “If a whole number is both even and odd, then it equals 1000.” Is this claim true? Explain what a proof of it would and would not show.
Answers
- If n is an integer divisible by 6, then n is divisible by 3. Given: n is an integer divisible by 6. Conclusion: n is divisible by 3. The claim says “a number”, so the proof starts by naming one.
- If a is an even integer and b is any integer, then ab is even. Given: a is even and b is an integer. Conclusion: ab is even. Nothing is given about b beyond being an integer.
- If two lines cross and one of the four angles is a right angle, then all four angles are right angles. Given: two crossing lines, one angle right. Conclusion: all four angles are right.
- The converse is: if n is divisible by 3, then n is divisible by 6. It is false. Take n = 9: it is divisible by 3 but not by 6. The original claim is true; its converse is not.
- Line 1: given. Line 2: definition of odd, applied to line 1. Line 3: algebra, adding 2 to both sides of line 2. Line 4: algebra, rewriting 2k + 3 as 2k + 2 + 1 = 2(k + 1) + 1. Line 5: accepted fact, a sum of integers is an integer. Line 6: definition of odd, applied to lines 4 and 5.
- (i) and (iv) may appear: each is the definition of even applied to the given. (ii) may not appear yet: it says ab is even, which is the conclusion. It can only be the last line. (iii) may not appear: it picks particular numbers, and the claim is about every pair of even integers.
- The four tests show that the claim holds for those four pairs. They say nothing about any other pair. The student still owes an argument that works for any two odd integers, such as naming them 2k + 1 and 2m + 1 and adding.
- Let a be even and b an integer. Then a = 2k for some integer k (definition of even), so ab = 2kb = 2(kb). Since kb is an integer, ab is even by the definition.
- Let n be even, so n = 2k for some integer k. Then n + 5 = 2k + 5 = 2(k + 2) + 1. Since k + 2 is an integer, n + 5 is odd by the definition of odd.
- Let a = 2k + 1 and b = 2m + 1, two different letters, since the claim does not say the integers are equal. Then ab = (2k + 1)(2m + 1), which expands to 4km + 2k + 2m + 1, which is 2(2km + k + m) + 1. The number 2km + k + m is an integer, so ab is odd.
- Since a divides b, b = ar for some integer r. Since a divides c, c = as for some integer s, a new letter. Then b + c = ar + as = a(r + s). The number r + s is an integer, so a divides b + c.
- Let the integers be 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 3 times an integer, so it is divisible by 3.
- x = 5 and AB = 34. Since M is the midpoint, AM = MB (definition of midpoint), so {3x + 2 = 5x - 8} (substitution). Then 10 = 2x and x = 5 (algebra). So AM = 3(5) + 2 = 17, and MB = 5(5) - 8 = 17 as it should. AB = AM + MB = 34 (Segment Addition Postulate).
- x = 35, m\angle 1 = 80^\circ and m\angle 2 = 100^\circ. The angles of a linear pair add to 180^\circ (linear pair theorem, from the given), so (2x + 10) + (3x - 5) = 180 (substitution). Then 5x + 5 = 180, so x = 35 (algebra). Substituting, 2(35) + 10 = 80 and 3(35) - 5 = 100, and 80 + 100 = 180.
- From the first given, m\angle A = 90^\circ - m\angle B (subtract m\angle B from both sides). From the second given, m\angle C = 90^\circ - m\angle B (subtract m\angle B from both sides). Both equal 90^\circ - m\angle B, so m\angle A = m\angle C (substitution).
- Writing the same letter k for both makes a and b equal, which the claim did not say. The claim is false. Take a = 2 and b = 4: both are even, but a + b = 6 is not divisible by 4.
- False. The number 2 is prime and is even, so it is a counterexample. One counterexample is enough to disprove a claim about all primes.
- The student assumed the conclusion and derived the given, which proves the converse: if x = 5, then x^2 = 25. The original claim is false. Take x = -5: then x^2 = 25, and x \ne 5. The solutions of x^2 = 25 are 5 and -5.
- The student assumed a \neq 0, which was not given. The claim fails at a = 0: then ab = 0 = ac for every b and c, for example b = 1 and c = 2, and b \neq c. The claim is true when a \neq 0 is added to the given.
- The claim promises that whenever the given is true, the conclusion is true. A proof has to keep that promise, so it starts where the promise starts, at the given. The truth table shows the claim can only fail when the given is true and the conclusion is false, so assuming the given covers the only case that matters. Assuming the conclusion would turn the job into proving Q \Rightarrow Q, which is always true and is not the claim.
- Line 1 would now read “M lies between A and B”, still a given, so line 2 is that given again and line 4 (the Segment Addition Postulate) still follows from it. Line 3, AM = MB, would not be justified: it came from the half of the definition of midpoint that is now missing. Without it, lines 5 and 6 cannot follow, and the claim itself can fail: with AM = 1 and MB = 3, AB = 4, not 2.
- The converse is: if n is even, then n is a multiple of 4. It is false: 6 is even and is not a multiple of 4. A proof of the original claim tells you nothing about its converse. Each needs its own proof or its own counterexample.
- Prove the contrapositive: if n is even, then n^2 is even. Let n = 2k for some integer k. Then n^2 = 4k^2 = 2(2k^2), and 2k^2 is an integer, so n^2 is even. The contrapositive is equivalent to the original claim, so if n^2 is odd then n is odd.
- True, but only because no whole number is both even and odd, so the given never holds and there is no case that could break the claim. That is the last two rows of the truth table, where P is false and the conditional is true whatever Q says. The claim is never false, which is all it promises. It does not show that any number has both properties, and it says nothing about 1000.