How to structure long proofs

Question

How do you structure proofs that are longer than say half a page?

I have already encountered a variety of styles (in my short math life), some of which I list below and I just hoped to hear some wise words or your ideas on the topic, for example in which situation to use which (lecture, tutorial, research paper, thesis, book, etc.)

1. Write the proof down in running text, proof auxiliary claims that are need within the proof where they are needed.

2. Write the proof down in running text; where auxiliary claims are needed refer to them and

   2.1 make lemmata before the theorem that contain the auxiliary claims

   2.2 make lemmata after the theorem that contain the auxiliary claims

3. Give a list of steps, the last one being the conclusion using the prior steps.

   3.1 Proof step 1 before writing down step 2 etc.

   3.2 First write all steps down, then proof them in the same order

   3.3 First write all steps down, then write down the conclusion including running text proof, then prove the remaining steps

Answer 1

You may enjoy reading these essays by Lamport:

• How to Write a Proof

• How to Write a 21st Century Proof

Answer 2

I agree with the comment above saying that it depends on your audience. If you are writing a proof of a theorem that you will submit to a journal, then you will probably leave out a lot of details. If you are teaching a class and writing notes, then you will probably give a lot of details.

If you audience is not familiar with the background, then you might want to provide this.

It also depends on how long exactly your proof is. You might want to write a whole book for the proof and in that case, you can split things into chapters as well.

I (personally) think that the important thing is that your proof is clear.

1. Introduction: A long proof/argument could start by stating what you are going to do. If you reduce the proof to some technicality, then state that you will do this. Also in the introduction you can give the background background for the result. This background can contain an explanation of why the result is interesting.

2. Meat: Try to split the proof into lemmas/claims.

3. Examples: Don't under estimate examples. Reading long proofs containing a lot of technical details can be hard because one doesn't have a good example to think about. So before or after a lemma, you might provide an example illustrating the lemma/claim.

4. Conclusion: I would end by summarizing what you have proved. You might write something like: "We have now proved out result. From lemma X we got that ... Combining this with lemma Y with reach the conclusion that ...

Answer 3

As someone who has read long proofs but never written one, I have a definite preference for #1, the exceptions being for proofs that would be too much of a digression and there is some other paper you can reference (e.g., "for a proof of this lower bound, see [Schmuckelberg, 1979]") and for things that are basic enough you can reasonably expect your readers to know (e.g., unless you're writing a pop math column, you can probably forgo proving Fermat's little theorem).

One of the things to consider about your readers is how they're going to read your proof. If they're going to read it on their computer screens, it makes sense to provide hyperlinks for all those things that would interrupt your flow. For example, at ProofWiki, in one of the proofs of the Pythagorean theorem, they don't stop to prove the triangle side-angle-side equality; you either already know it's valid and keep going, or you stop to click and read that proof before coming back to the Pythagorean theorem (maybe not the best example, since that's not a very long proof, but I think you get the point). If your readers want to print out your proof, giving hyperlinks for proofs of the more important assertions might not go over so well.