Part 2

New Skills

Formulating Maths
Introduction
Hypotheses &c
Implications
And & or
For all & there exists
Dependence

Proof
Introduction
Counter examples
Constructing proofs
Understanding
Experimentation
Precision
Examples
Assumptions
Contradiction
Induction
The End

 

---

Site map

---

 

 

 

Having found a method which looks as though it will provide the required proof, the final stage is to fill in the details and to write out a complete proof. Typically, these two tasks can be carried out simultaneously. It may happen that while you are doing this, you encounter some difficulty which you had not previously noticed-you may have made a slip in calculation, or you may have overlooked some logical difficulty, or you may have knowingly made an unwarranted assumption (for simplicity) which you now find hard to remove, or there may be a point where you want to reverse your argument but it is not clear how to do so. If this happens, you will have to return to experimentation until you find a way around the difficulty.

As explained in Writing mathematics, the purpose of writing out a rigorous solution is both to ensure that you have not made any errors or overlooked any difficulties, and to provide the reader with an argument which is complete, clear, accurate, and unambiguous. Your solution should provide a proof which will satisfy someone with a similar level of mathematical knowledge to yourself (but someone who has not solved the problem). In writing your solution, it is a good idea to imagine that you are writing it for such a person, even if you expect the solution to be read only by your tutor.

In writing your formal solution, you should aim to observe the following general points:

(i)

Each statement should be mathematically accurate; in particular, the principles of Implications, And & or, For all & there exists and Dependence, should be observed.

(ii)

When the symbols are converted into words, each statement should make sense as a sentence in English, and be unambiguous.

(iii)

Each statement should follow logically from previous statements in your argument, or from standard results.

(iv)

It should be clear to the reader why each statement is true. Where appropriate, include phrases such as ``By So-and-So's Theorem, ...'' or ``It follows from (*) above that ...''.

(v)

All assumptions being made at any stage should be made clear to the reader.

We can illustrate (v) with two specific cases. If you are arguing by contradiction, write something like:

The proof will be by contradiction. Suppose that the result is false. Then ...

If your argument is divided into several cases, say explicitly what the cases are. For example:

We shall divide the argument into three cases which together cover all possible integers n ³ 2:

Case 1:

n has two distinct prime factors p₁ and p₂,

Case 2:

n = 2^k for some k ³ 1,

Case 3:

n = p^k for some odd prime p, and some k ³ 1.

Case 1: ...

What we have said so far in this section concerns your formal solution; this material must not be omitted from your written solution. However, sometimes it is appropriate to include some extra explanation which will help the reader understand what you are doing, even though it is not strictly necessary and may even be imprecisely expressed (just as books sometimes include informal explanations of their arguments). This may be a diagram, or it may be some extract from your process of experimentation. Indeed, including material of this type in your written solutions is to be recommended; if you make small errors in the solution, your informal comments often satisfy the reader that they were not errors of substance.

We now give rigorous, complete, solutions to our Example 0. This solution is based on the informal working carried out in Experimentation, but is set out in a precise and logical way. In this example, material written in italics does not form part of the solution; this material contains comments included in these notes for the purposes of explaining why we are setting out the proof as we are; in normal circumstances, these comments would be omitted.

Example 0. Let A, B, and C be sets. Prove that (A ÈB) Ç(AÈC) = A È(B ÇC).

Solution. Let x Î (AÈB) Ç(A ÈC). Then x Î A ÈB and x Î A ÈC. Hence [x Î A or x Î B] and (simultaneously) [x Î A or x Î C]. Thus, if x Ï A, then x Î B and x Î C, so x Î B ÇC. Hence, x Î A or x Î B ÇC, so x Î A È(B ÇC). Thus,

(A ÈB) Ç(A ÈC) Í AÈ(B ÇC). (1)

Conversely, let x Î A È(B ÇC). Then x Î A or x Î BÇC. We consider these two cases separately. If x Î A, then x Î A ÈB and x Î A ÈC, so x Î (A ÈB) Ç(A ÈC). If x Î B ÇC, then x Î B and x Î C, so x Î A ÈB and x Î A ÈC, so x Î (A ÈB) Ç(A ÈC). In either case, we have shown that x Î (A ÈB) Ç(A ÈC). Thus,

A È(B ÇC) Í (A ÈB) Ç(A ÈC). (2)

It follows from (1) and (2) that (A ÈB) Ç(A ÈC) = A È(BÇC), as required.

Note how the unions and intersections in the problem have produced statements involving ``or'' and ``and'', so we have had to apply the principles of And & or.

It would be sensible to include the Venn diagram given in Experimentation with the formal solution.