Implications - Direct Proof - Forms of Argument

Mathematical Writing - Vivaldi Franco 2014

Implications - Direct Proof
Forms of Argument

Many mathematical statements take the form of an implication:

If $$P$$ then $$Q$$.

For example:

If $$p$$ is an odd prime, then $$2^{p-1}-1$$ is divisible by $$p$$.

If the sequence $$(a_k)$$ is periodic, then $$(a_{2k})$$ is also periodic.

Implications may appear in disguise, without the ’if...then’ construct:

$$A$$ is a subset of $$B$$.

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 $$x\in A$$, then $$x\in B$$.

If $$r$$ is a repeating decimal, then $$r$$ is rational.

If $$A$$ is an invertible matrix, then $${det}(A)\not =0$$.

This is due to the presence of a hidden universal quantifier. So the symbolic form of an implication is not $$P\Rightarrow Q$$, but rather

$$\begin{aligned} \forall x\in X,\,\,{\fancyscript{P}}(x)\Rightarrow {\fancyscript{Q}}(x) \end{aligned}$$

(7.2)

where $${\fancyscript{P}}$$ and $${\fancyscript{Q}}$$ are predicates over $$X$$. 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 $$P$$ is false, then $$P\Rightarrow Q$$ is true regardless of the value of $$Q$$, so there is nothing to prove. If $$P$$ is true, then the implication is true provided that $$Q$$ is true. So a direct proof of the implication consists in assuming $$P$$ and deducing $$Q$$. The assumption of $$P$$ lasts only until we have proved $$Q$$; after that $$P$$ is discharged and may no longer be used.

Every direct proof of ’If $$P$$ then $$Q$$’ must contain a section during which $$P$$ is assumed. The beginning of the section is announced by a sentence such as

Assume $$P$$.  Suppose $$P$$.  Let $$P$$.

The task of the rest of the proof is to prove not the original theorem, but $$Q$$. We make this clear by writing

RTP: $$Q$$

where RTP stands for Remains To Prove (or Required To Prove). The block ends when the proof of $$Q$$ is completed. This is announced with a closing sentence such as

We have proved $$Q$$.  The proof of $$Q$$ is complete.

The above considerations suggest what should be the opening sentence of a direct proof of an implication:

Theorem. If $$p>3$$ is a prime and $$p+2$$ is also prime, then $$p+4$$ is composite.

PROOF. Suppose $$p$$ is a prime number greater than 3, such that $$p+2$$ is prime.

RTP: $$p+4$$ is composite.

All three assumptions ($$p>3$$, $$p$$ prime, $$p+2$$ 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 $$X$$ be a compact set, and let $$C$$ be a subset of $$X$$. Assume that $$C$$ is closed. RTP: $$C$$ is compact.

Theorem. If $$\lambda \in \mathbb {C}$$ is a root of a monic polynomial whose coefficients are algebraic integers, then $$\lambda $$ is an algebraic integer.

PROOF. Let $$p$$ be a monic polynomial whose coefficients are algebraic integers, and let $$\lambda \in \mathbb {C}$$ be a root of $$p$$. RTP: $$\lambda $$ is an algebraic integer.

Theorem. Every basis of a finite-dimensional linear space has the same number of elements.

PROOF. Let $$V$$ be a finite-dimensional linear space, and let $$B_1$$ and $$B_2$$ be two bases for $$V$$. Suppose $$B_1$$ has $$n_1$$ elements and $$B_2$$ has $$n_2$$ elements. RTP: $$n_1=n_2$$.

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 $$V$$ be a finite-dimensional linear space. Then every basis for $$V$$ has the same number of elements.

Theorem 1. Let $$V$$ be a finite-dimensional linear space, and let $$B_1$$ and $$B_2$$ be two bases for $$V$$. Then $$\# B_1=\# B_2$$.

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 $$V$$, $$B_1$$, $$B_2$$ be as in Theorem 1.

in the text following the theorem.