Writing a Good Proof - Forms of Argument

Mathematical Writing - Vivaldi Franco 2014

Writing a Good Proof
Forms of Argument

Proofs come in all shapes and sizes. Correctness is, of course, imperative, but a good proof requires a lot more since the conflicting requirements of clarity and conciseness must be resolved. On the one hand, reading a proof is demanding, and any assistance will be welcome. On the other hand, a proof is a rigorous exercise in logic and the exposition must remain succinct and essential. The level of exposition and the amount of detail will depend on the mathematical maturity of the target audience.

There is one general rule, to be applied at all key junctures in a proof:

·  SAY WHAT YOU PLAN TO DO.

·  WHEN YOU’VE DONE IT, SAY SO.

We now examine statements of theorems and proofs that are less than optimal, and we seek to improve them. Our proofs are very detailed, and suitable for first-year university students. In some cases we also provide a concise version of the proof, aimed at expert readers.

Our first theorem is taken from a textbook.

BAD THEOREM. If $$x^2 \ne 0$$, then $$x^2 > 0$$.

BAD PROOF. If $$x > 0$$ then $$x^2 = xx > 0$$. If $$x < 0$$ then $$-x > 0$$ , so $$(-x)(-x) > 0$$, i.e., $$x^2 > 0$$. $$\square $$

The statement of the theorem is incomplete, in that there is no information about the quantity $$x$$. The theorem is an implication, but in the proof what has happened to the assumption $$x^2\ne 0$$? If the assumption is obvious, one may leave it out, but one must judge whether the readers are sophisticated enough to see what it must be. Furthermore, this is a proof by cases (see Sect. 7.2), and it would be helpful if this were made explicit.

THEOREM. For all real numbers $$x$$, if $$x^2 \ne 0$$, then $$x^2 > 0$$.

PROOF. Let $$x$$ be a real number such that $$x^2\ne 0$$. Then $$x\ne 0$$, and we have two cases:

(i)

(ii)

The following statement establishes a simple relation between rational and irrational numbers.

BAD THEOREM. $$\forall a,b\in \mathbb {R}, \,\,(a\in \mathbb {Q}\wedge b\not \in \mathbb {Q})\Rightarrow a+b\not \in \mathbb {Q}$$.

BAD PROOF: Suppose $$a+b\in \mathbb {Q}$$. Then $$a+b=m/n$$.

If $$a\in \mathbb {Q}$$, then $$a=p/q$$, and $$b=m/n-p/q\in \mathbb {Q}$$. $$\square $$

The symbolic formulation of the theorem obscures its simple content. The proof is straightforward, but the use of unnecessary symbols (the numerator and denominator of the rational numbers serve no purpose) and the lack of comments make it less clear than it should be.

THEOREM. The sum of a rational and an irrational number is irrational.

PROOF. Let $$a$$ and $$z$$ be a rational and an irrational number, respectively. Consider the identity $$z=(a+z)-a$$. If $$a+z$$ were rational, then $$z$$, being the difference of two rational numbers, would also be rational, contrary to our assumption. Thus $$a+z$$ must be irrational. $$\square $$

The choice of symbols keeps the rational and the irrational numbers well-separated in our mind.

Next we consider an arithmetical statement.

BAD THEOREM. $$n$$ odd $$\,\Rightarrow \, 8|n^2-1.$$

BAD PROOF.

$$n$$odd $$\,\,\Rightarrow \exists j\in \mathbb {Z},\,\,n=2j+1$$;

$$\therefore \,\,n^2-1=4j(j+1)$$;

$$\forall j\in \mathbb {Z},\,\,2\mid j(j+1)\,\,\Rightarrow \,\,8\mid n^2-1$$$$\square $$

This is a clumsy attempt to achieve conciseness via an entirely symbolic exposition. Combining words and symbols and adding some short explanations will improve readability and style. We shall see that a clearer proof need not be longer.

THEOREM. The square of an odd integer is of the form $$8n+1$$.

DETAILED PROOF. Let $$k$$ be an odd integer. We show that $$k^2=8n+1$$, for some $$n\in \mathbb {Z}$$.

Since $$k$$ is odd, we have $$k=2j+1$$, for some integer $$j$$. We find

$$\begin{aligned} k^2=(2j+1)^2=4j^2+4j+1=4j(j+1)+1. \end{aligned}$$

(1)

Now, one of $$j$$ or $$j+1$$ is even, and therefore their product is even. Thus we have $$j(j+1)=2n$$, for some $$n$$. Inserting this expression in (1) we obtain $$k^2=8n+1$$, as desired. $$\square $$

This proof is quite detailed, and can safely be shortened.

PROOF. An odd integer $$k$$ is of the form $$k=2j+1$$, for some integer $$j$$. A straightforward manipulation gives $$k^2=4j(j+1)+1$$. Our claim now follows from the observation that the product $$j(j+1)$$ is necessarily even. $$\square $$

The adverb ’necessarily’ signals that the conclusion (the product $$j(j+1)$$ is even) requires a moment’s thought. The expression ’straightforward manipulation’ is used to omit some steps in the derivation, while warning the reader that some calculations are required. In such a circumstance, the adjective ’straightforward’ is preferable to ’easy’, which is subjective, or ’trivial’, which carries a hint of arrogance. So it’s appropriate to claim that the arithmetical identity

$$\begin{aligned} 29&= \left( 2+\frac{\sqrt{-1}\,(1+\sqrt{5})}{2}\right) \left( 2-\frac{\sqrt{-1}\,(1+\sqrt{5})}{2}\right) \\&\times \left( 2+\frac{\sqrt{-1}\,(1-\sqrt{5})}{2}\right) \left( 2-\frac{\sqrt{-1}\,(1-\sqrt{5})}{2}\right) \end{aligned}$$

can be verified with a ’straightforward calculation’.

In the following example everything needs re-writing: definition, theorem, and proof.

BAD DEFINITION. Let $$q_j$$ be digits. We define

$$ \overline{q_1\cdots q_n}=q_1\cdots q_nq_1\cdots $$

BAD THEOREM. Let $$x=m+0.q_1'\cdots q_k'\overline{q_1\cdots q_n}$$, where $$m\in \mathbb {Z}$$. Then $$x\in \mathbb {Q}$$.

BAD PROOF: Let $$A=0.q_1'\cdots q_k'$$, $$B=0.q_1\cdots q_n.$$ Then $$A,B\in \mathbb {Q}$$, and

$$ 0.\overline{q_1\ldots q_n}= B\left( 1+\frac{1}{10^n}+\frac{1}{10^{2n}}+\cdots \right) =B\frac{10^n}{10^n-1}=:C\in \mathbb {Q}. $$

Thus $$ x=m+A+C10^{-k}\in \mathbb {Q}$$. $$\square $$

In the definition, the decimal nature of the digits is not mentioned and the periodicity of the digit sequence could be made more evident. In the statement of the theorem the number $$x$$ is represented with an inappropriate hybrid notation, as the sum of a decimal number and a number expressed symbolically. The proof lacks explanations and the choice of symbols is not ideal.

As we did before, we state the theorem with words, which is more effective. We introduce the notation after the statement of the theorem but before the beginning of the proof. This arrangement should be considered if the notation is needed outside the confines of the proof, or if the proof is heavy and needs lightening up, or simply as a variation from the rigid definition-theorem-proof format. We number the various steps in the argument for future reference.

THEOREM. Every number whose decimal digits eventually repeat is rational.

1. Before proving the theorem, we establish some notation. We denote a string (finite or infinite) of decimal digits by $$d_1d_2\cdots $$, with $$d_k\in \{0,1,\ldots ,9\}$$; the over-bar denotes a pattern of digits which repeats indefinitely:

$$\begin{aligned} \overline{d_1\cdots d_n}= {d_1\cdots d_n} {d_1\cdots d_n} \, \cdots . \end{aligned}$$

(7.9)

DETAILED PROOF.

2. Let $$x$$ be a real number with eventually repeating decimal digits. Then $$x$$ has a decimal representation of the type

$$ x=d_0'\cdots d_j'.d_{j+1}'\cdots d_m'\overline{d_1\cdots d_n} $$

for some $$m\geqslant 0$$, $$0\leqslant j\leqslant m$$, and $$n\geqslant 1$$. The primed digits form the aperiodic part of the digit sequence.

3. We shall compute the value of $$x$$ in terms of two integers $$M$$ and $$N$$, given by:

$$ M=d_0'\cdots d_m'=\sum _{k=0}^m d_k'10^{m-k} \qquad N=d_1\cdots d_n=\sum _{k=1}^n d_k10^{n-k}. $$

First, we get rid of the aperiodic part; we shift it to the left of the decimal point by multiplying by a suitable power of 10, and then we subtract it off, to get

$$\begin{aligned} 10^{m-j}x-M=0.\overline{d_1\,\cdots \,d_n}. \end{aligned}$$

(7.10)

4. Next we compute, using (7.9)

$$\begin{aligned} 0.\overline{d_1\,\cdots \,d_n}&= \frac{N}{10^n}+\frac{N}{10^{2n}}+\frac{N}{10^{3n}}+\cdots \\&= N\left( \frac{1}{10^n}+\frac{1}{10^{2n}}+\frac{1}{10^{3n}}+\cdots \right) \\&= N\sum _{k=1}^\infty \left( \frac{1}{10^n}\right) ^k=\frac{N}{10^n-1}. \end{aligned}$$

5. In the last step we have used the formula of the sum of the geometric series

$$ \sum _{k=1}^\infty q^k =\frac{q}{1-q} \qquad |q|<1. $$

From Eq. (7.10) and the result above, we obtain

$$ 10^{m-j}x-M=\frac{N}{10^n-1} $$

and hence

$$ x=10^{j-m}\left( M+\frac{N}{10^n-1} \right) . $$

The right-hand side of this equation consists of sums and products of rational numbers, and is therefore rational. $$\square $$

Let us examine the main steps in the proof:

1.

2.

3.

4.

5.

We give a concise version of the same proof.

PROOF. Let $$x$$ be a real number with eventually repeating decimal digits $$d_k$$. Without loss of generality, we may assume that the integer part of $$x$$ is zero, and that the fractional part is purely periodic:

$$\begin{aligned} x=0.\overline{d_1\,\cdots \, d_n}. \end{aligned}$$

(1)

(Any real number may be reduced to this form by first multiplying by a power of 10, and then subtracting an integer, and neither operation affects the tail of the digit sequence.) Defining the decimal integer $$M=d_1\cdots d_n$$, we find, from (1)

$$\begin{aligned} x =\frac{M}{10^n}+\frac{M}{10^{2n}}+\frac{M}{10^{3n}}+\cdots \,=\, M\sum _{k=1}^\infty \left( \frac{1}{10^n}\right) ^k \,=\,\frac{M}{10^n-1}. \end{aligned}$$

(7.11)

We see that $$x$$ is rational. $$\square $$

The expression ’without loss of generality’ indicates that the restriction being introduced does not weaken the argument in any way (see also Sect. 5.2). A brief parenthetical remark is added for clarification: it too could be omitted.

Exercise 7.1

You are given cryptic proofs of mathematical statements. Rewrite them in a good style, with plenty of explanations.

1.

2.

3.

4.

Exercise 7.2

The following text has several faults: (a) explain what they are; (b) write an appropriate revision.

WRONG THEOREM. For all numbers $$x$$ and $$y$$,

$$ \frac{x^2+y^2}{|xy|}>2. $$

WRONG PROOF. For

$$\begin{aligned} \frac{x^2+y^2}{|xy|}>2&\Rightarrow x^2+y^2>2xy\\&\Rightarrow x^2-2xy+y^2>0\\&\Rightarrow (x-y)^2>0. \end{aligned}$$

The last equation is trivially true, which proves it.$$\square $$

Exercise 7.3

Identify the flaw in the proof of the following statements.

1.

2.

Exercise 7.4

Write the first few sentences of the proof of each statement, introducing all relevant notation in an appropriate order, and identifying the RTP. (For this task, understanding the meaning of the statements is unimportant.)

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

Exercise 7.5

You are asked to help the reader approach the following problem:

Prove that for all integers $$m,n$$, we have $$m\mathbb {Z}+n\mathbb {Z}={\gcd }(m,n)\mathbb {Z}$$.

Formulate a number of easier sub-problems of increasing difficulty, eventually leading to the original problem.

Footnotes

1

Abbreviation for the Latin quod erat demonstrandum, meaning ’which had to be demonstrated’.

2

If a prime divides the product of two integers, then it divides one of the factors.

3

This result, known as Wilson’s theorem, was first formulated by Bhaskara (a 7$$^{\text {th}}$$ Century Indian mathematician) and first proved by Lagrange.

4

This phenomenon has deep roots, see [9, p. 155].

5

Christian Goldbach (German: 1690—1764).

6

Latin for ’it does not follow’.