Proof Structure

Context: This lesson plan is from a weekly communication recitation that accompanies M.I.T.’s Real Analysis (18.100C). This week students learn about the Taylor series and the Stieltjes integral (Rudin pp. 120-127). This recitation is often combined with Recitation 9b on proof elegance.

Authors: This recitation was developed by Craig Desjardins, Joel B. Lewis, Todd Kemp, Mohammed Abouzaid, Peter Speh, Kyle Ormsby, and Susan Ruff

Communication objectives: Structure proofs (and collections of statements) to help readers follow the logic.

Recitation: This recitation varies each term depending on instructor inclinations. Some topics covered include the following:

Claims, lemmas, propositions, theorems, corollaries, etc.

Recitation instructors: Joel B. Lewis, Craig Desjardins

What different kinds of statements are there (lemma, theorem, proposition, claim, corollary, etc.), and when is each used?

Examples:

  • Proposition: sum from 1 to infinity of 1/n diverges.
  • Lemma: If the limit as x goes to infinity of the integral from 1 to x of f(t) dt diverges, then the sum from 1 to infinity of f(n) diverges.
  • Claim: The limit as x goes to infinity of the integral from 1 to x of 1/t dt diverges.
  • Theorem: the sum from 1 to infinity of 1/n^p converges if p>1 and diverges if p<1.
  • Corollary: the sum from 1 to infinity of 1/n^2 converges.

When is each kind of statement used?

  • Theorems are main results with broad applicability.
  • A lemma is an intermediate result used to prove a theorem. An intermediate result may be stated and proved as a lemma rather than within the proof of the theorem if the result works for a more general context than that needed in the proof of the theorem within which it’s used, or if pulling the lemma out of the theorem proof makes the theorem’s proof easier for readers to understand.
  • A claim is usually smaller than a lemma. It may appear within a proof to help structure the proof, or it may appear within exposition. It may be set formally using a claim environment or it may simply be signaled by wording such as “We claim that…”
  • A proposition is a secondary or intermediate result, but is more interesting and valuable elsewhere than is a lemma. One frequently has a major result (a Theorem) whose proof is broken into many propositions, none of which is as interesting on its own as is the theorem.
  • A corollary is a straightforward extension of a theorem; it is easily proved by using the theorem.

A well-written theorem is “tight.” A good example is The Alternating Series Test: each part of the theorem statement is necessary.

Pulling a lemma out of a proof to simplify the proof

Recitation instructors: Mohammed Abouzaid and Peter Speh (description written by Mohammed Abouzaid)

“The goal is to introduce the students to the framework of Definition/Lemma/Proposition/Theorem/Corollary into which most mathematical writing is organised. We did this by showing them the proof of Theorem 3.0.11 in http://arxiv.org/abs/0709.1639v1 (starting on p. 25 and ending on p. 33) and comparing it to the proof of the same result (now Theorem 5.5) in http://arxiv.org/abs/0709.1639v4 (starting on p. 25 and ending on p. 31). The main point was that the original version had a long (8 page or so) proof, and that the revised version made things much easier to understand by separating two Lemmas from the bulk of the proof. [The original and revision include highlighting to emphasize the changes.]

“Because of the advanced nature of the mathematics, the recitation lecturer just went through these papers on the screen, highlighting the relevant features. Then, having seen how a Lemma can be used to split off a technical result from a long proof, we discussed other components of a mathematical paper/book (Proposition and Corollary), and what each signifies.

“Remark: The example was selected by me (Mohammed) based on wanting a paper which both shows a problematic choice, and a way to correct it by splitting off a Lemma. I can imagine different instructors can find different papers in their subjects which they could use for this purpose. I was hesitant about using something in which they could not understand the mathematics, but that made things run much more smoothly: We want to focus on structure, and since the main problem we want to point out is that you need to split results whose proofs are too long, it would take a lot of time to have them read something, then have a discussion about it. Before showing them the revised version, I asked them what they thought the problem was and how they would fix it, and they suggested breaking the result into pieces.”

Proof-writing strategies: auxiliary functions and existence proofs

Recitation instructors: Craig Desjardins and Joel B. Lewis

Auxiliary functions Auxiliary functions can simplify proofs. For example,

Show that there exists a c such that c=ln(c) + 2.

Proof: It is equivalent to show that ln(x) + (2-x) = 0 has a solution.
So let g(x) = ln(x) + (2-x).

g(a) is negative for some small a
g(1) is positive
so g(c) = 0 for some c in (0,1)

Other examples:

  • Intermediate Value Theorem
  • Taylor’s Theorem

Existence theorems: When proving an existence theorem, a natural inclination is to simply go looking for an example; however, this strategy is not always necessary.

Example:

Prove: An irrational number raised to an irrational number can be rational.
Proof: Consider √2√2 (the square root of 2 raised to the square root of 2). If √2√2 is rational, we’re done. If it’s irrational, then (√2√2)√2 is an irrational raised to an irrational, but it equals 2, which is rational.

Recursive sequences also give a good example of when existence aids a proof.

Local to global structure

Recitation instructor: Kyle Ormsby

“I cobbled together several topics from previous years to make a lesson I’d like to refer to as “Local-to-global structure in math communication.”  Local structure focused on reductionist vs. purely logical presentations of proofs.  The goal was to lead the students towards the idea that, both as a convenience for the reader (in terms of information order) and as an illumination of the problem-solving method, it’s often good to start by reducing a problem to a very tangible statement before proving that statement.  I also sold this as a good way to write proofs in a test-taking situation (“writing to learn”).

“Intermediate between local and global was a discussion of all the labels in mathematics (Theorem, Proposition, Lemma, Corollary, Remark, Claim, Definition, …) and how to use them, especially in longer documents.  Probably the most interesting part was discussing how a lemma could be used as a receptacle for a general statement, a specific case of which your theorem proof uses, or as a way to “copy-paste” a portion of a long argument into its own section (thus easing the burden on the reader).

“Global structure (and some of this was covered in Recitation 12) discussed how and when to use conceptual vs. formal explanations of concepts.  Rudin’s writing on the Riemann-Stieltjes integral was used as an example (cf. Rudin pp.122-132, especially the placement of Definition 6.2 vs. Remark 6.18).  The students had surprisingly good ideas about specific instances in which it might be best to include formal explanations first.”

Page content licensed by M.I.T. Department of Mathematics under the license:
CC BY-NC-SA (Attribution-NonCommercial-ShareAlike)