Mathematical Writing - Vivaldi Franco 2014
Implications - Direct Proof
Forms of Argument
Many mathematical statements take the form of an implication:
If then .
For example:
If is an odd prime, then is divisible by .
If the sequence is periodic, then is also periodic.
Implications may appear in disguise, without the ’if...then’ construct:
is a subset of .
Every repeating decimal is rational.
The determinant of an invertible matrix is non-zero.
When we rewrite these sentences as explicit implications, we note that it is necessary to introduce an auxiliary quantity:
If , then .
If is a repeating decimal, then is rational.
If is an invertible matrix, then .
This is due to the presence of a hidden universal quantifier. So the symbolic form of an implication is not , but rather
(7.2)
where and are predicates over . Let us expand one of our sentences so as to tell the full story:
For all real numbers r, if the decimal digits of r are repeating, then r is rational.
Spelling out an implication in this way will help us structure its proof.
7.3.1 Direct Proof
From the truth table (4.9) we see that if is false, then is true regardless of the value of , so there is nothing to prove. If is true, then the implication is true provided that is true. So a direct proof of the implication consists in assuming and deducing . The assumption of lasts only until we have proved ; after that is discharged and may no longer be used.
Every direct proof of ’If then ’ must contain a section during which is assumed. The beginning of the section is announced by a sentence such as
Assume . Suppose . Let .
The task of the rest of the proof is to prove not the original theorem, but . We make this clear by writing
RTP:
where RTP stands for Remains To Prove (or Required To Prove). The block ends when the proof of is completed. This is announced with a closing sentence such as
We have proved . The proof of is complete.
The above considerations suggest what should be the opening sentence of a direct proof of an implication:
Theorem. If is a prime and is also prime, then is composite.
PROOF. Suppose is a prime number greater than 3, such that is prime.
RTP: is composite.
All three assumptions (, prime, prime) must be used in the proof. If not, either the proof is wrong or some assumption is redundant.
Often you can work out how the proof of an implication must start even if you haven’t the faintest idea of what the mathematics is about. We illustrate this point with some real life examples:
Theorem. A closed subset of a compact set is compact.
PROOF. Let be a compact set, and let be a subset of . Assume that is closed. RTP: is compact.
Theorem. If is a root of a monic polynomial whose coefficients are algebraic integers, then is an algebraic integer.
PROOF. Let be a monic polynomial whose coefficients are algebraic integers, and let be a root of . RTP: is an algebraic integer.
Theorem. Every basis of a finite-dimensional linear space has the same number of elements.
PROOF. Let be a finite-dimensional linear space, and let and be two bases for . Suppose has elements and has elements. RTP: .
Establishing a good notation is often decisive. In all the examples above, the proof begins by giving names to things. Some authors make this unnecessary by including names in the theorem; others obscure the statement of a theorem by putting too many names in it. Let us rewrite the last theorem in such a way as to establish some notation within the statement itself.
Theorem. Let be a finite-dimensional linear space. Then every basis for has the same number of elements.
Theorem 1. Let be a finite-dimensional linear space, and let and be two bases for . Then .
Let us compare the three formulations of this theorem. The first is plain and effective. The second contains a minimum of notation, which does no harm but is unnecessary. The last version establishes some useful notation. Normally the notation should be introduced within the proof, unless one plans to use it at a later stage. For instance, one could find the sentence
Let , , be as in Theorem 1.
in the text following the theorem.