Proof Techniques: Five Ways to Be Sure
Chapter Six
Syllabus topic Module 1, "Mathematical Foundations (Sets, Relations, Functions, Proof Techniques)"
Pages 25 to 29 of 438
In one line
A proof is an argument that leaves no case unexamined, and there are five shapes it can take.
In the wording a student can write in an examination: a proof of a statement is a finite chain of reasoning from accepted premises to the statement, in which every step is justified. The standard techniques are direct proof, proof by contraposition, proof by contradiction, proof by induction and the pigeonhole principle.
Why this subject needs proof at all
Because a machine has to be right for every input, and there are infinitely many inputs.
You can test a program. You cannot test a machine on infinitely many strings, and the strings that break a machine are almost never short. Chapter 13 builds eight machines, and for each one the question "is this right?" is a question about an infinite set. Testing answers it for a few members. A proof answers it for all of them.
The other reason is that the negative results of this paper cannot be obtained any other way. "No machine of this kind accepts this language" is a statement about every machine there could ever be. There is no way to check them one at a time, because there are infinitely many of those too.
One: direct proof
Assume the hypothesis and reason forward to the conclusion.
Statement. If a string w has even length, then w reversed has even length.
Proof. Let w have even length, say length 2k for some whole number k. Reversal does not add or remove symbols, so w reversed has the same number of symbols as w, namely 2k. A number of the form 2k is even, so w reversed has even length.
That is a complete proof and it is three sentences long. The shape is always the same: name the assumption, name what it gives you, and arrive.
Two: proof by contraposition
To prove "if P then Q", prove "if not Q then not P" instead. The two statements are logically the same, and sometimes the second is much easier to argue.
Statement. If the number of a in w is odd then w is not the empty string.
Contrapositive. If w is the empty string then the number of a in w is not odd.
Proof of the contrapositive. If w is the empty string it has no symbols, so it has 0 occurrences of a, and 0 is even, so the count is not odd.
The original statement would have required reasoning about every odd count. The contrapositive has exactly one case.
The trap. The contrapositive of "if P then Q" is "if not Q then not P". It is NOT "if not P then not Q", which is a different statement called the inverse and is not equivalent to the original. This is the single commonest logical error students make in this paper, and chapter 36 is where it costs marks: the pumping lemma says "if regular then pumpable", so the useful contrapositive is "if not pumpable then not regular", and a student who writes "if not regular then not pumpable" has said something both different and false.
Proof Techniques: Five Ways to Be Sure
Three: proof by contradiction
Assume the statement is false, derive something impossible, and conclude the statement is true.
This is the technique the two most important results in the paper use, so it deserves the most attention. The halting problem in chapter 74 is a proof by contradiction, and so is every application of the pumping lemma in chapter 37.
Statement. There is no largest whole number.
Proof. Suppose there were. Call it N. Then N plus 1 is a whole number and is larger than N, which contradicts N being the largest. So there is no largest whole number.
The shape, in four lines, which is worth learning as a template:
- Suppose, for contradiction, that the statement is false.
- Write out exactly what that assumption gives you.
- Derive two things that cannot both hold.
- Conclude that the assumption was wrong, so the statement is true.
Step 2 is where students lose marks. "Suppose the language is regular" is not enough; the next line has to say what being regular gives you, namely a machine with some definite finite number of states, and it is that number the rest of the argument attacks.
Four: proof by induction
Used to prove a statement about every whole number, or about every string, by proving it for the smallest case and then proving that each case carries the next one.
The two parts.
Base case. Prove the statement for the starting value, usually 0 or 1, or for the empty string.
Inductive step. Assume the statement holds for some value n, which is called the inductive hypothesis, and prove it holds for n plus 1.
Once both are done, the statement holds for every value from the base upwards, because the base gives the first, the step carries the first to the second, the second to the third, and so on without end.
Statement. The number of strings of length exactly k over an alphabet of size 2 is 2 to the k.
Base case. For k equal to 0 there is exactly one string of length 0, the empty string, and 2 to the 0 is 1. True.
Inductive step. Assume there are 2 to the k strings of length k. A string of length k plus 1 is a string of length k with one more symbol on the end, and there are 2 choices for that symbol. Different choices give different strings, and every string of length k plus 1 arises this way exactly once. So there are 2 to the k multiplied by 2, which is 2 to the (k plus 1). True.
Proof Techniques: Five Ways to Be Sure
Therefore the statement holds for every k.
Induction on strings. Very often in this book the induction is not over numbers but over the length of a string. The base case is the empty string and the step assumes the claim for w and proves it for w with one more symbol. Chapter 11 defines the extended transition function exactly this way, and chapter 16 proves the subset construction correct exactly this way. It is the same principle: the strings of each length are built from the strings one shorter.
Five: the pigeonhole principle
If n items are put into m boxes and n is greater than m, then some box holds at least two items.
It is obvious, it needs no proof, and it is the engine of the most examined theorem in Module 1.
Why it matters here. A machine with m states, run on a string of length m or more, visits at least m plus 1 states along the way, counting the one it starts in. There are only m states to be visited. So some state is visited twice. That is the entire content of the pumping lemma, and chapter 36 does nothing but write it out carefully and see what follows.
Worked, on a machine. A machine has 3 states. Feed it the string aaaa, of length 4. The run passes through 5 states in total: where it starts, and where it is after each of the 4 symbols. Five visits, three states, so some state occurs twice. Between the two occurrences the machine has read a non empty piece of the string and come back to where it was, which means that piece can be repeated any number of times without the machine noticing. Hence "pumping".
Putting two together: proving a language is not regular
Here is the combination that earns marks in the examination, using three of the five techniques at once. The full treatment is chapter 37; this is the skeleton.
To prove that the language of strings a to the n followed by b to the n is not regular:
- Contradiction: suppose it is regular.
- Then some machine accepts it, with some definite number of states, call it m.
- Pigeonhole: feed the machine a to the m followed by b to the m. While reading the a part it
Proof Techniques: Five Ways to Be Sure
passes through more states than it has, so it repeats one.
- So a non empty block of a can be repeated without the machine noticing, giving a string with more a
than b that the machine still accepts.
- That string is not in the language, so the machine does not accept the language after all.
- Contradiction, so no such machine exists, so the language is not regular.
Notice that step 2 says "some definite number", not "a large number". The proof must work whatever m is, which is why the string chosen in step 3 is written in terms of m rather than as a particular string.
Distinctions
| Technique | Prove what | Typical use in this book |
|---|---|---|
| Direct | the statement itself | simple closure properties |
| Contraposition | if not Q then not P | using the pumping lemma the right way round |
| Contradiction | assume false, hit an impossibility | the halting problem, the pumping lemma |
| Induction | base case plus step | correctness of a construction, over string length |
| Pigeonhole | more items than boxes | the pumping lemma, and state count bounds |
What it does NOT mean
A proof is not a worked example. Showing a machine accepts three strings proves that it accepts three strings. It does not prove the machine is correct, and an examination answer that offers examples where a proof was asked for has answered a different question.
Contraposition is not the inverse. "If not P then not Q" is not equivalent to "if P then Q". See the trap above.
A counterexample is not a proof, except of a negative. One counterexample disproves a universal claim completely. No number of confirming instances proves one.
Induction does not prove the base case by assuming it. The base case must be checked outright. An induction whose base case is skipped can prove false statements, which is why examiners mark it separately.
Quick revision
- Direct: assume the hypothesis, reason to the conclusion.
- Contraposition: prove "if not Q then not P", which is equivalent. The inverse is not.
- Contradiction: assume the negation, write out what it gives, derive an impossibility. Used for the
halting problem and every pumping lemma argument.
- Induction: base case, then assume for n and prove for n plus 1. Often over string length, with the
empty string as the base.
- Pigeonhole: more items than boxes forces a repeat. A machine with m states run on a string of length
m or more must revisit a state, and that is the pumping lemma.
- A proof is needed because a machine must be right on infinitely many inputs, and because negative
results are claims about every possible machine.
Test yourself
1. Give the contrapositive of "if L is regular then L satisfies the pumping lemma". If L does not satisfy the pumping lemma then L is not regular. This is the form in which the lemma is actually used.
Proof Techniques: Five Ways to Be Sure
2. Why must the base case of an induction be proved separately? Because the inductive step only shows that each case carries the next. Without a first case that is known outright, the chain has nothing to start from, and a step can be perfectly valid while the statement is false for every value.
3. A machine has 5 states. What does the pigeonhole principle tell you about its run on a string of length 6? The run visits 7 states counting the start, among only 5 distinct states, so at least one state is visited twice, and the portion of input read between the two visits can be repeated without changing where the machine ends up.
4. Prove by contradiction that the empty string is in every language of the form L star. Suppose some L star did not contain the empty string. L star is the set of concatenations of zero or more strings from L, and the concatenation of zero strings is the empty string by definition. So the empty string is in L star, contradicting the supposition.
5. Name the technique each of these needs: showing a construction is correct for all inputs; showing a language is not context free; showing two regular expressions denote the same language. Induction, usually on string length; contradiction with the pumping lemma for context free languages; either a direct two way containment argument or, in this book, an exact machine comparison.
6. State the pigeonhole principle and say what the boxes are when it is applied to a finite automaton. If more items than boxes are distributed among the boxes, some box holds two or more. Applied to an automaton, the boxes are the states and the items are the points in time during a run.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.