I don’t know — a proof is a proof. What kind of a proof ? It’s a proof. A proof is a proof, and when you have a good proof, it’s because it’s proven.
Jean Chr´etien (b. 1934), Prime Minister of Canada
The goal of a mathematical proof is to provide a completely convincing explanation that a deduction is valid. It needs to be so carefully written that it would hold up in court forever, even against your worst enemy, in any country of the world, and without any further explanation required. Fortunately, the rules of logic are accepted worldwide, so, if applied properly, they create an irrefutable case.
In the previous sections of this chapter, we wrote our proofs in two-column format. We will now start the transition to writing proofs in English prose; our ideas will be expressed in sentences and paragraphs, using correct grammar, combining words with appropriate mathematical notation. A proof written in prose needs to convey the same information as would be found in a two-column proof, so essentially the same rules and strategies will still apply, but writing in ordinary English provides more freedom, and often leads to shorter proofs that are more reader-friendly.
The big advantage of two-column proofs is that the rules are very clear, so there are no ambiguities that require good judgment to resolve. This makes them easier for beginners who may have difficulty deciding what they are allowed to do. The disadvantage is that being required to record every detail of every step makes the proofs very verbose, so they cannot reasonably be used in the complicated situations that arise in the study of advanced mathematics.
Just as when using the two-column format, our proofs will be a sequence of assertions that lead from the hypotheses to the desired conclusion. Each assertion must have a logical justification based on assertions that were stated earlier in the proof. Any subproof (for \(\Rightarrow\)-introduction or Proof by Contradiction) will form a paragraph of its own within the proof.
Before the proof begins, we always provide a statement of the theorem that will be proved.
- The statement is preceded by the label “Theorem” (or a suitable substitute).
- The statement of the result begins with a list all of the hypotheses. To make it clear that they are assumptions, not conclusions, this list of assertions is introduced by an appropriate word or phrase such as “Assume…,” or “Suppose that …,” or “If …,” or “Let ….”
- The statement of the result ends with a statement of the desired conclusion, introduced by an appropriate word or phrase such as “Then …,” or “Therefore, ….”
Following the statement of the result, we begin our proof in a new paragraph.
- The proof is labelled with the single word: “Proof.”
- We then proceed to give a well-organized series of assertions that logically lead from our hypotheses to the desired conclusion.
- A small square is drawn at the right margin at the end of the proof to signify that the proof is complete.
For example, here is how the ’s first deduction could be treated:
- if the Pope is here, then the Queen and the Registrar are both here, and
- the Pope is here.
Then the Registrar is here.
From Assumption 2, we know that the Pope is here. Therefore, Assumption tells us that the Queen and the Registrar are both here. In particular, the Registrar is here.
Here is another example:
- If the Pope is here, and the Queen is not here, then the Registrar is here.
Conclusion: If the Pope is here, then either the Queen or the Registrar is also here.
Proof by Contradiction.
Suppose the conclusion is false. (This will lead to a contradiction.) This means that the Pope is here, but neither the Queen nor the Registrar is here. In particular, the Pope is here and the Queen is not here, so Hypothesis tells us that the Registrar is here. However, since neither the Queen nor the Registrar is here, we also know that the Registrar is not here. Therefore, the Registrar is both here and not here. This is a contradiction.
Suppose the Pope is here. (We wish to show that either the Queen or the Registrar is also here.) From the Law of Excluded Middle, we know that the Queen is either here or not here, and we consider these two possibilities as separate cases.
Assume the Queen is here. Then it is true that either the Queen or the Registrar is here, as desired.
Assume the Queen is not here. Then the Pope is here, and the Queen is not here. From Hypothesis , we conclude that the Registrar is here. Therefore, either the Queen or the Registrar is here, as desired.
Note that some of the rules of the two-column format are relaxed for proofs written in prose:
- We will no longer list all of the hypotheses at the start of our proof. Instead, we refer to the list that is in the statement of the theorem.
- We will no longer make a practice of numbering all of the assertions in our proofs. However, if there is a particular assertion that will be used repeatedly, we may label it with a number for easy reference.
- We will usually not cite the basic rules of by name every time they are used. However, we should be able to justify any assertion with a rule, if called upon to do so.
Translate both proofs of Example \(2.6.2\). into two-column format (using our usual symbolization key).
Write a proof of each of these theorems in English prose.
- If the Pope is here, then the Queen is here.
- If the Queen is here, then the Registrar is here.
Conclusion: If the Pope is here, then the Registrar is here.
- If the Pope is here, then the Registrar is here.
- If the Queen is here, then the Spy is here.
- The Pope and the Queen are both here.
Then the Registrar and the Spy are both here.
- If Adam is here, then Betty is here.
- If Betty is not here, then Charlie is here.
- Either Adam is here, or Charlie is not here.
Then Betty is here.
- If Jack and Jill went up the hill, then something will go wrong.
- If Jack went up the hill, then Jill went up the hill.
- Nothing will go wrong.
Then Jack did not go up the hill.