The Nature of Proof

loopspace

6th November 2011

Creative Commons License

Contents

  1. Home

  2. 1. Introduction

  3. 2. The Nature of Proof

  4. 3. Examples of Proofs

  5. 4. Finding Proofs

    1. 4.1. Knowing Where to Begin

    2. 4.2. When There Is No Beginning

    3. 4.3. General Techniques

  6. 5. Further Reading

1 Introduction

On this page I want to gather some thoughts, techniques, and resources to help with reading and writing mathematical proofs. As with all mathematics, the best way to learn about proofs is by doing it yourself, but it can be useful to have some guidance.

2 The Nature of Proof

The exact nature of a mathematical proof can be hard to pin down. At one extreme lies the systems of formal proofs that encode proofs and theorems in an almost unrecognisable language “known only to a bunch of monks that live on a mountain"; at the other extreme are the “hand waving" proofs of which “proof by pictures" is a common example (not all “proof by pictures" are hand-waving). Somewhere in the middle lie “proofs by mathematicians". The important thing to note from this is the word “somewhere". “Proofs by mathematicians" do not lie at a specific point in this range, but can vary quite considerably between the two extremes.

A different way of expressing this range may help make this clearer. The purpose of a proof is to convince someone that something is true. Exactly how that proof is worded will depend on who that someone is and how much they demand before being convinced. Sometimes, it's enough just to give some evidence for a result being true. At other times, it's important to make sure that every step is clear. The extremes correspond to someone who won't believe anything unless they logically have to and someone who is prepared to believe anything not obviously false.

Mathematicians primarily write proofs for other mathematicians. And since proofs are our business, we usually want to be fairly sure that they are true. We build our results on those of others and thus our results are at most as sure as the results we build on. In turn, we want our results to be built upon by others and want to be sure that we are giving them a good foundation to build upon.

But even within this there is room for manoeuvre, mainly because we present our results in different contexts. In a paper we try to be as rigorous and careful as we can, and try to write so that the reader is convinced that we could have written a formal proof if we'd been so inclined. In a seminar, we are more lax and tend to be nearer the “just convince them" end of the spectrum.

When reading proofs it is therefore important to know who the proof is intended for. The other thing to realise when reading a proof is that when a mathematician is not sure of exactly who will be reading then they will default to the more rigorous end of the spectrum.

The issue for writing proofs is subtly different. Most mathematical proofs are written by mathematicians for other mathematicians1, and thus there is a symmetry between the author and the audience. But proofs written by students are written to be read by their lecturer, or the grader on an exam. The reader therefore already knows that the result is true and so the task of the proof is not to convince the reader of the truth of the result, but to convince the reader that the author knows that the result is true.

1This is also true of textbooks. If you think about who chooses a textbook for a course, you'll see why.

Thus when writing a proof, the essential aim is to convince the reader that you could put in all the details if asked. Note that you are not required to actually put in all these details, just sufficient to show that you could do so.

The other aspect of writing proofs that is a little different between students and mathematicians is in putting the details of how the proof was devised. The purpose, for a mathematician, of a proof is to convince another mathematician that a result is true. Exactly how the proof was thought of is largely irrelevant to that and so is often left out2. On the other hand, for students writing proofs the method is often more important than the actual proof since the purpose of the proof is to demonstrate the students' capability in doing mathematics – which involves devising proofs as well as understanding them.

2The method used may be thought to be of interest in which case it is included, but not usually as part of the proof itself.

In summary, a student studying mathematics could encounter the following types of proof. They can further vary depending on whether or not they are spoken or written, and whether the person devising the proof knows exactly who they are talking to or writing for.

  1. By a mathematician for a mathematician.

  2. By a mathematician for a student.

  3. By a student for a mathematician.

  4. By a student for a student.

3 Examples of Proofs

Let us consider a simple statement to illustrate the different types of proof, perhaps with a little exaggeration for effect.

Theorem 1

The composition of linear transformations is again linear.

  1. By a mathematician for a mathematician. (This is perhaps the most artificial example since a mathematician generally wouldn't consider this needed proving.)

    Proof

    Let T:UV and S:VW be linear transformations. Then

    ST(u+λv)=S(T(u)+λT(v))=ST(u)+λST(v)

    hence ST is linear.

    Characteristics of this proof:

    • Definitions are not expanded out: for example, what “linear" means.

    • “Obvious" (i.e. to the author) assumptions are not made clear: for example, that U, V, and W are vector spaces, that u,v are vectors in U, and that λ is a scalar (indeed, the coefficient field hasn't even been mentioned).

    • Only the main step is presented: it is assumed that the reader will know how to fill in the “before" and “after" pieces to complete the proof.

  2. By a mathematician for a student. When written, this type of proof has to be both rigorous and clear. If done badly, it can easily fail on both counts. At best, it tends to be very “wordy".

    Proof

    We want to prove that the composition of two linear transformations is again a linear transformation. So we start with two linear transformations. As we wish to consider their composition (as functions) we must ensure that the domain of one is the codomain of the other. Thus let T:UV and S:VW be linear transformations where U, V, and W are vector spaces over .

    As the codomain of T is the domain of V, the composition ST is well-defined as a function from U to W. To prove that it is linear, we need to show that if u,vU are two arbitrary vectors and λ is an arbitrary scalar, then ST(u+λv)=ST(u)+λST(v).

    So let u,vU be two arbitrary, but fixed, vectors and λ a scalar3. We consider the left-hand side of what we want to prove: ST(u+λv). By definition of composition, we have

    3Note that the previous sentence did not make a choice of u,v,λ but said “if …", we therefore need to choose them here. Although in this case it is fairly harmless, some proofs require more care to show that what is being chosen really does exist so it is good to get into good habits now.

    ST(u+λv)=S(T(u+λv))

    As T is linear, T(u+λv)=T(u)+λT(v) and so

    ST(u+λv)=S(T(u)+λT(v))

    Now S is also linear, which means that for x,yV and μ, S(x+μy)=S(x)+μS(y). We apply this taking x=T(u), y=T(v), and μ=λ to see that

    ST(u+λv)=S(T(u))+λS(T(v))

    Finally, we recall that by definition ST(z)=S(T(z)) and so

    ST(u+λv)=ST(u)+λST(v)

    Characteristics of this proof:

    • Meticulous explanation of just about everything; for example, including the definition of the composition of a function.

    • Sometimes includes extra explanations intended to indicate how the proof might be constructed (no particular examples of this in this case).

    • Extreme care taken with notation and application of definitions; for example, most people are happy with ST for the composition rather than ST.

  3. By a student for a mathematician.

    Proof

    To show that the composition of two linear transformations is again linear, it is sufficient to show that this is true for two arbitrary (composable) linear transformations. So let T:UV and S:VW be linear transformations between vector spaces. We wish to show that the composition ST is again linear. It is enough to show that

    ST(u+λv)=ST(u)+λST(v)

    for any u,vU and λ.

    We can show this by applying first the linearity of T and then the linearity of S to the expression on the left-hand side. That is,

    ST(u+λv)=S(T(u)+λT(v))linearity ofT=ST(u)+λST(v)linearity ofS

    As this holds for all u,vU, and λ, ST is thus linear.

    Characteristics of this proof:

    • Trivial details are omitted, but replaced with “signposts" to show that the omissions are deliberate; for example the words “between vector spaces" in the first paragraph and the word “composable" in parentheses.

    • The important steps are done carefully.

    • The flow of the proof is well signposted.

  4. By a student for a student.

    Proof

    Well, it works for matrices, doesn't it?

The last example was, perhaps, a little facetious. The important point to realise is that before reading a proof, you should work out who is writing it and who they are trying to convince.

4 Finding Proofs

Reading and writing a proof are different skills. They can be compared to differentiation and integration. Differentiation is often fairly algorithmic and once the basic rules are learnt, it is fairly easy to differentiate many seemingly complicated functions. On the other hand, integration is an art. Even with a long list of examples, finding the integral of a complicated function (even proving that it has a closed form) can be sheer guess-work. So it can seem with proofs.

But just as with integration, there are standard techniques and examples that can guide you through the seemingly tortuous process of finding a proof.

4.1 Knowing Where to Begin

Often the most difficult part of finding a proof is knowing where to begin. Theorems are often stated quite concisely and so the first step is to expand the statement to recognisable terms. As this is “rough working", the term “recognisable" should be interpreted personally. At this stage, it is also important to separate out the pieces of the theorem into hypothesis and conclusion.

For an experienced mathematician, the theorem used in the previous section needs no expansion: it is obvious what the terms mean. However, for a student encountering linearity for the first time, it may be a little too concise.

This process of expanding out theorems generally involves the following types of expansion

  1. Expanding out a definition.

  2. Replacing generic statements by statements about generic objects.

  3. Including implicit information.

Of course, this expansion can result in quite a length rephrasing in which case part of the process is finding a good way to write that rephrasing so that its structure is clear. Remember that these rewritings are purely for your benefit so a good method is a useful one.

Let us illustrate those with Theorem 1 from the previous section.

  1. Original statement:

    The composition of linear transformations is again linear.

  2. Replace generic statements:

    If S and T are two composable linear transformations then their composition, ST, is again linear.

    It is important to be precise here. The word “composable" could have been left out, as the statement only makes sense if S and T are composable, but until you are completely familiar with this kind of process, it is better to be overly precise than otherwise. In this case, leaving in the word “composable" reminds us that there is a restriction on the domains and codomains which will be useful later. (However, one has to draw the line somewhere: even the word “composable" is not quite enough since it leaves open the question as to whether it is ST or TS!)

  3. Include implicit information:

    If S:VW and T:UV are linear transformations then ST:UW is again linear.

    Here's where remembering that S and T are composable in the previous step helps keep things clear. As S and T are composable, we only need 3 vector spaces. Then, since we explicitly have the vector spaces the fact that S and T are composable is plain, though some may prefer to keep that fact in the statement. Also, some may like to have the fact that U, V, and W are vector spaces explicitly stated.

  4. Expand out definitions:

    If S:VW and T:UV are such that S(v1+λv2)=S(v1)+λS(v2) and T(u1)+μT(u2) for all v1,v2V, u1,u2U, and λ,μ, then ST(x1+ηx2)=ST(x1)+ηST(x2) for all x1,x2U and η.

    Note that I have been careful not to repeat myself with the newly introduced symbols. It would be technically alright to reuse u1 and u2 in place of x1 and x2 since these are local declarations (restricted by the phrases “for all …"). However, humans are not good at differentiating between local and global declarations so it is best not to reuse symbols unless the scope is very clear.

  5. Replace generic statements:

    If S:VW and T:UV are such that S(v1+λv2)=S(v1)+λS(v2) and T(u1)+μT(u2) for all v1,v2V, u1,u2U, and λ,μ, then whenever x1,x2U and η, ST(x1+ηx2)=ST(x1)+ηST(x2).

    Up to now, the rephrasing has not taken into account the fact that there is a conclusion and a hypothesis. This rephrasing modifies a part of the conclusion to turn it from a generic statement “P(p) is true for all pQ" to a statement about a generic object “whenever pQ then P(p) is true". We do not do this for the similar statements in the hypothesis. This is because these two pieces are treated differently in the proof.

  6. Replace generic statements, and reorganise to bring choices to the fore:

    Let S:VW and T:UV be such that S(v1+λv2)=S(v1)+λS(v2) and T(u1)+μT(u2) for all v1,v2V, u1,u2U, and λ,μ. Let x1,x2U and η. Then ST(x1+ηx2)=ST(x1)+ηST(x2).

    In this form, the distinction between hypothesis and conclusion is all the clearer. Parts of the hypothesis use the word “Let", parts of the conclusion use the word “Then".

With this formulation, the proof essentially writes itself. With all its gory details:

Proof

Let S:VW and T:UV be such that S(v1+λv2)=S(v1)+λS(v2) and T(u1)+μT(u2) for all v1,v2V, u1,u2U, and λ,μ. Let x1,x2U and η.4 Then:

4A shorthand for this is to write “Let … be as in the statement of the theorem."

ST(x1+ηx2)=S(T(x1)+ηT(x2))

using the hypothesis on T as x1,x2U and η. So:

ST(x1+ηx2)=ST(x1)+ηST(x2)

using the hypothesis on S as T(x1),T(x2)V and η. Hence the conclusion is true.

Notes:

  1. This could be condensed, but the important thing here is how to find it, not what the final form should be.

  2. Notice that I wrote “as x1,x2U" rather than “with u1=x1 and u2=x2". This is partly style, and partly because in the statement of linearity, u1 and u2 are placeholders into which we put x1 and x2. So saying u1=x1 is semantically incorrect as it equates a virtual vector with an actual vector. This is a very minor point, though.

4.2 When There Is No Beginning

Some theorems just don't seem to have a beginning. A simple example are the “There exists …" or “There doesn't exist …" type results where one has to find something satisfying certain properties, or prove that such doesn't exist. The hypotheses tend to be about the properties of the object, but this doesn't always lend itself to the style of proof in the previous example.

In these circumstances, a good strategy is to set aside questions of existence for the time being and try to find other properties of the object that it would have to have. This process of finding properties is like a proof which has a beginning but no particular end. However, that can be simpler than a proof with an end but no particular beginning!

A classic example of this is the “no largest number" theorem. Again, this is a slightly artificial example as the proof is so well-known, and also quite obvious, that it can be hard to imagine not knowing it, but let's pretend.

Theorem 2

There is no largest natural number.

We leave aside existence for now and simply imagine that we have such a number, say N. Then N is the largest number. So what does it look like? What properties does it have? We start with its defining property:

It is bigger than every natural number.

and apply our expansion techniques. This leads to:

For each n, Nn.

Now as we are focussing on particular properties of N, we can introduce a further replacement technique: that of replacing a strong statement by a weaker one, or of replacing a generic statement by a particular occurrence of it (we actually used this in the proof of linearity: the generic statement “T(u1+λu2)=T(u1)+λT(u2)" for all u1,u2U and λ" was replaced by the particular statement “T(x1+ηx2)=T(x1)+ηT(x2)").

N1

Which doesn't seem very helpful: we knew that already as N. Let's try a different one.

N2

Which does tell us something we didn't know already. It tells us that N1 since N2>1. Since we are playing dumb, let's try the next.

N3

Which, by the same argument, tells us that N2.

But N is a natural number! So if we keep going, we should eventually reach N and be able to conclude that NN.

That, however, is not a proof. But whilst examples are not proofs, they often suggest a strategy. In this case, several strategies are possible. Here are two.

  1. The direct approach to a negative result: By assumption, if N exists then NN+1, but then N+1>N so we obtain the contradiction N>N.

  2. The indirect approach to a positive result: If N exists, it is an element of . Let us prove that no element in is a maximum. So let k. Then k+1 and k<k+1. Hence k is not the maximum of . As this holds for all k, does not have a maximum.

4.3 General Techniques

In one representation of formal mathematics, a chain of logical implications provides a path from a source (namely, the hypothesis) to a destination (the conclusion)5. The purpose of the proof, then, is to demonstrate that such a path exists. The most usual method for doing this is to construct an explicit path, namely a chain of logical implications that starts with the hypothesis and ends with the conclusion.

5The similarity with functions is not coincidental.

If one doesn't see such a path, even after expanding out the statement as indicated above, there are several techniques that can be used to try to find such a path.

  1. Just start. If one has expanded out the statement of the theorem to the point where there are no unfamiliar terms, then there will probably be something you can deduce from the hypothesis. Even if it seems useless, it is worth making a list of these simple deductions to see if they hint at a strategy.

  2. Just Finish. Working from the end can often be a useful strategy.

  3. Look for related ideas. A proof consists of a chain of simple steps. Some of those steps will be applications of other theorems and definitions. So write down a list of these that might be useful.

  4. Look for an overall proof. It can be useful to break a proof down into smaller chunks, along the lines of “If I could prove that X was Y, then I know that Y is Z so if I can just show that Z is W then I'm done".

  5. Look for similar results. Do you know of a result that's a bit like this one? Maybe with slightly different hypotheses or conclusion, or applies to a different thing. The proof of that one may be adaptable to the current problem.

  6. Modify the problem. Try changing the hypotheses a little, or the conclusion. Sometimes it can be useful to weaken the hypothesis to such a point that it is obvious that the conclusion cannot hold. The reason why it doesn't hold in that case can give an indication of how to prove that it does hold in the original case. Similarly, one can sometimes weaken the conclusion to such a point that it is obvious that it does hold. Again, the reason why it holds can give an indication of how to prove it in the original case.

  7. Look for examples. Examples are almost always not proofs. But examples can give indications as to the strategy for a proof. Figuring out why something holds in a particular instance can be easier than the general case, but usually gives some insight as to how the general case should be approached. Obviously, the more examples, the more intuition one will get.

5 Further Reading