0.7 Writing a proof a grader accepts

A proof is an argument written for a reader. It declares its objects, gives every step with its reason, and ends by stating what was shown. You can check your own proof against a short list before anyone else does.

Chapters 0.1 and 0.2 were about finding a proof. This one is about writing it down so that someone else, usually a grader in a hurry, can check it line by line and agree. A correct idea written badly loses points, and often hides a gap you did not notice. Each rule below has a reason: readers cannot check what they cannot follow.

Before you start

Chapter 0.2: the proof techniques.

Quick checkIn a proof by contradiction of 'if P then Q', the first written line should be:

Quick checkWhich line would a grader object to?

The picture: scratch work and the write-up

Every proof has two lives. The scratch work is where you find the idea: messy, out of order, full of crossed-out attempts, often working backwards from the conclusion. The write-up is a clean argument in the forward direction, from what you are given to what you must show. The reader only ever sees the write-up. The most common mistake is to hand in the scratch work.

Definition B

Scratch work

Scratch work is everything you do to find the proof: examples, diagrams, working backwards from the conclusion, false starts. It is not handed in.

In one lineThe private search for a proof: any order, any guesses, often working backwards from the goal.

Why it existsFinding a proof and presenting it are different tasks; mixing them produces unreadable or circular write-ups.

Definition B

Proof write-up

A proof write-up states what is assumed, declares every object it uses, proceeds forward one justified step at a time, and ends by stating the conclusion.

In one lineThe finished argument: declared objects, forward steps each with a reason, and a final sentence stating what was proved.

Why it existsIt is what a reader can check line by line.

In analysis (Unit 1) the split is sharp. The scratch work for an $\varepsilon$ - $\delta$ proof works backwards from $|f(x) - L| < \varepsilon$ to find $\delta$ ; the write-up starts with “Let $\varepsilon > 0$ . Set $\delta = \dots$ ” and runs forwards. Chapter 1.3 shows both side by side.

Where this came from· Why mathematicians write proofs in prose

The two-column “statement | reason” layout is a teaching device. It grew up in United States school geometry in the early twentieth century, after the 1890s reforms made geometry the place where students were taught to prove. Research mathematicians write their proofs as ordinary paragraphs, with the reasons woven into the sentences. Paul Halmos’s essay “How to write mathematics” (1970) is a classic statement of why: a proof is written for a reader, so the writer should have something to say and should say it to someone. Its section headings include “Say something” and “Speak to someone”. Keith Conrad’s guide, which Spagnolie linked for MATH 375, is a modern short version of the same advice.

The rules, with reasons

1. Say what you are proving and how

Start with the statement (or its name), then “Proof.” If you use a technique other than direct proof, say so in the first line: “We prove the contrapositive.” “Suppose, for contradiction, that…” “We use induction on $n$ .” The reader then knows what to expect.

Quick checkWhich is the best first sentence of a proof that

2^n \ge n + 1

for all

n \ge 1

2. Declare every object before you use it

Every letter needs an introduction: “Let $n$ be an odd integer”, “Let $\varepsilon > 0$ ”, “Since $x \in L(S)$ , there are scalars $c_1, \dots, c_k$ with $x = \sum c_i x_i$ .” An undeclared letter is the most common reason a grader cannot follow a proof. Make clear whether a letter is arbitrary (chosen by the reader: “let $x$ be any…”) or specific (constructed by you: “set $\delta = \varepsilon/2$ ”).

Quick checkA proof says: 'Let

\varepsilon > 0

. Set

\delta = \varepsilon/2

.' Which letter is arbitrary and which is constructed?

3. Go forward, and give a reason for every step that is not routine algebra

Each line should follow from earlier lines, definitions, axioms or cited theorems, and the reason should be visible: “by the triangle inequality”, “since $T$ is linear”, “by the induction hypothesis”. Routine algebra (expanding brackets) needs no comment. Anything a classmate might ask “why?” about needs one.

4. Write in sentences, with words between formulas

“Then”, “so”, “since”, “hence” tell the reader how each line relates to the last. Two formulas side by side with no words force the reader to guess the logic. Never use " $\Rightarrow$ " as shorthand for “so” inside a proof; it means implication, which is a different thing.

Worked example

Rewrite as a proof in sentences: '

n

even

\Rightarrow

n = 2k

\Rightarrow

n^2 = 4k^2 = 2(2k^2)

\Rightarrow

n^2

even'.

Solution.

Declare the object and the assumption. “Let $n$ be an even integer.” The chain starts with an undeclared $n$ . A sentence introduces it and says it is arbitrary.
Turn the first arrow into a word. “Then $n = 2k$ for some integer $k$ .” This arrow is the definition of even, so the sentence says which fact is used and names the integer it provides.
Turn the second arrow into a word. “So $n^2 = 4k^2 = 2(2k^2)$ .” “So” says the line follows from the one before. The step is algebra, so no extra reason is needed.
Turn the last arrow into a closing sentence. “Since $2k^2$ is an integer, $n^2$ is even.” This names the condition being checked, an integer inside the bracket, and states the claim.

Answer. “Let $n$ be an even integer. Then $n = 2k$ for some integer $k$ . So $n^2 = 4k^2 = 2(2k^2)$ . Since $2k^2$ is an integer, $n^2$ is even.” $\blacksquare$

5. End by saying what you showed

Close with a sentence that matches the statement: “Hence $n^2$ is odd. $\blacksquare$ ” or “This contradicts $p, q$ being in lowest terms, so $\sqrt 2$ is irrational. $\blacksquare$ ” The reader should not have to work out whether you are done.

6. Use the right level of detail

Spagnolie on Piazza: “Assume that any properties of the real numbers hold without proof. The point of this chapter is to learn about linear spaces… Later we will… assume that any properties of linear spaces hold without proof. … We will build a house, one solid brick at a time.” So: what the current chapter is about must be justified carefully; what earlier chapters established can be cited.

Quick checkIn a 2.1-style proof that a set of matrices is a vector space, which may you use without proof?

From scratch work to write-up

Worked example

Turn this scratch work into a proof: 'if

x

and

y

are rational, so is

x + y

The scratch work (what you might write while thinking). “rational means fraction. $x = a/b$ , $y = c/d$ . add: $(ad + bc)/bd$ . top and bottom integers. bd not 0 since b, d not 0. done.”

The write-up.

State the setup. Let $x$ and $y$ be rational numbers. Declares the objects as arbitrary.
Unfold the hypothesis with named integers. Then $x = a/b$ and $y = c/d$ for some integers $a, b, c, d$ with $b \ne 0$ and $d \ne 0$ . Definition of rational. The non-zero conditions are part of the definition and are needed later.
Compute, in a sentence. So $x + y = \dfrac{ad + bc}{bd}$ . Routine algebra; no reason needed.
Check every condition of the target definition. Here $ad + bc$ and $bd$ are integers, since sums and products of integers are integers, and $bd \ne 0$ because neither $b$ nor $d$ is zero. ‘Rational’ needs integer top, integer bottom, and bottom non-zero. All three must be checked.
State the conclusion. Hence $x + y$ is rational. $\blacksquare$ Matches the statement exactly.

Answer. The ideas are the same as the scratch work. The write-up adds declarations, the full definition (including $b, d \ne 0$ ), the reasons, and an ending.

Your answerTest the formula from the proof on numbers before you trust it. With

x = \frac{a}{b} = \frac12

and

y = \frac{c}{d} = \frac23

, compute

\frac{ad + bc}{bd}

Worked example

Fix this flawed proof: 'Claim: if

n^2

is even then

n

is even. Proof:

n = 2k

, so

n^2 = 4k^2 = 2(2k^2)

, which is even.'

Solution.

Identify what was actually proved. The proof starts from " $n = 2k$ " (the conclusion) and derives ” $n^2$ even” (the hypothesis). Compare the first line with the claim’s hypothesis, and the last line with its conclusion.
Name the error. That is the converse, “if $n$ is even then $n^2$ is even”. It is true, but it is a different theorem. Proving the converse is the most common logical error.
Repair it. Prove the contrapositive: if $n$ is odd, $n = 2k + 1$ , then $n^2 = 2(2k^2 + 2k) + 1$ is odd. So if $n^2$ is even, $n$ cannot be odd, and $n$ is even. The contrapositive of the claim is equivalent to it and easy to prove directly.

Answer. The original ‘proof’ proved the converse. The repaired proof says “We prove the contrapositive” in its first line.

Worked example

Fix this induction write-up: 'Show

2^n \ge n + 1

2^1 \ge 2

. Assume

2^n \ge n + 1

. Then

2^{n+1} \ge n + 2

. Done.'

Solution.

The step is asserted, not shown. “Then $2^{n+1} \ge n + 2$ ” is the thing to prove; no reason is given. A grader cannot check a line with no justification.
The variable is reused. The hypothesis uses $n$ , the same letter as the statement for all $n$ , which blurs “assume one case” with “assume all cases”. Use a separate letter $k$ for the fixed case.
Rewrite. Base case: $2^1 = 2 \ge 1 + 1$ . Inductive step: let $k \ge 1$ and assume $2^k \ge k + 1$ . Then $2^{k+1} = 2 \cdot 2^k \ge 2(k + 1) = 2k + 2 \ge k + 2$ , using the hypothesis and then $k \ge 0$ . Hence $2^{k+1} \ge (k + 1) + 1$ . By induction, $2^n \ge n + 1$ for all $n \ge 1$ . $\blacksquare$ Every inequality now has its reason.

Answer. The fixed version declares $k$ , shows the step with reasons, and states the conclusion.

Worked example

Write up this scratch work properly: '

\{(x, y) : y = 3x\}

is a subspace of

\mathbb R^2

. (0,0) ok. (a,3a)+(b,3b) = (a+b, 3(a+b)) ok. c(a,3a) = (ca, 3ca) ok.'

Solution.

Name the set and the technique. “Let $S = \{(x, y) \in \mathbb R^2 : y = 3x\}$ . We use the subspace test: $S$ is non-empty, closed under addition and closed under scaling.” Rule 1: say what you prove and how. Naming the three checks tells the reader what to look for.
Check the zero vector. “Since $0 = 3 \cdot 0$ , we have $(0, 0) \in S$ .” Scratch work says “ok”. The write-up says why it is ok, using the membership condition $y = 3x$ .
Declare the arbitrary elements and unfold. “Let $u, v \in S$ . Then $u = (a, 3a)$ and $v = (b, 3b)$ for some real numbers $a, b$ .” Rule 2. Membership means $y = 3x$ , so the second entry is three times the first. Different letters, because $u$ and $v$ need not be equal.
Check addition. “Then $u + v = (a + b,\ 3a + 3b) = (a + b,\ 3(a + b))$ , whose second entry is three times its first, so $u + v \in S$ .” The write-up states the membership condition being verified, so the reader can see the check is complete.
Check scaling. “For any real $c$ , $cu = (ca,\ 3ca)$ , so $cu \in S$ .” Same, for the second closure property.
End with the conclusion. “By the subspace test, $S$ is a subspace of $\mathbb R^2$ .” Rule 5, matching the claim exactly.

Answer. The scratch work had the right computations. The write-up adds the technique, the declared objects, the membership condition being checked, and an ending. $\blacksquare$

Worked example

Write a complete proof by contradiction: if

x

is rational and

y

is irrational, then

x + y

is irrational.

Solution. The plan: assume the opposite, use it to write $y$ as a fraction, and read off a contradiction.

State the technique and the exact assumption. “Suppose, for contradiction, that $x$ is rational, $y$ is irrational, and $x + y$ is rational.” The negation of ‘if P then Q’ is ‘P and not Q’ (0.1). The first line tells the reader which technique we use.
Unfold both rational numbers, with different letters. “Then $x = a/b$ and $x + y = c/d$ for integers $a, b, c, d$ with $b \ne 0$ and $d \ne 0$ .” Items 3 and 4 of the self-check below: declare the objects, and unfold the definition fully including the side conditions $b, d \ne 0$ .
Solve for $y$ . “So $y = (x + y) - x = \dfrac cd - \dfrac ab = \dfrac{cb - ad}{bd}$ .” Routine algebra. It rewrites $y$ in the form that the word ‘rational’ demands.
Check every condition. “Here $cb - ad$ and $bd$ are integers, and $bd \ne 0$ because $b \ne 0$ and $d \ne 0$ .” Integer top, integer bottom, non-zero bottom: all three parts of the definition are checked.
State the contradiction and the conclusion. “So $y$ is rational, contradicting that $y$ is irrational. Hence $x + y$ is irrational.” $\blacksquare$ Rule 5: the last sentence matches the claim.

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

Your answerIn the induction step of '

3 \mid 4^n - 1

', suppose

k = 3

. Then

4^k - 1 = 63 = 3m

gives

m = 21

. The proof says

4^{k+1} - 1 = 3(4m + 1)

. Compute

4m + 1

Your answerA proof that the product of two odd integers is odd writes

m = 2a + 1

and

n = 2b + 1

. Take

m = 7

and

n = 9

, so

a = 3

and

b = 4

. Compute the integer

2ab + a + b

for which the proof says

mn = 2(2ab + a + b) + 1

Worked example

Find the gap, and then a counterexample: 'Claim: if

x < y

then

x^2 < y^2

. Proof: multiply

x < y

x

and by

y

to get

x^2 < xy

and

xy < y^2

. Hence

x^2 < y^2

Solution.

Check each line of the proof. The last line (“Hence”) follows from the two before it, since $x^2 < xy < y^2$ . Do not assume the flaw is where you first look. This line is fine.
Check the multiplications. Multiplying $x < y$ by a number keeps the direction only if that number is positive. We multiplied by $x$ and by $y$ without knowing their signs. The rule ‘multiply both sides by $c$ ’ needs $c > 0$ . For $c < 0$ the inequality flips.
Name the missing hypothesis. The claim needs $0 \le x < y$ (or at least $x, y \ge 0$ ). Under that hypothesis both multiplications are allowed, and the proof is correct.
Find a counterexample to the claim as stated. Take $x = -3$ and $y = 2$ . Then $x < y$ , but $x^2 = 9 > 4 = y^2$ . A single case where the hypothesis holds and the conclusion fails disproves a ‘for every’ claim.

Answer. The gap is multiplying an inequality by a number whose sign is unknown. The statement is false in general ( $x = -3$ , $y = 2$ ) and true for $0 \le x < y$ .

Your answerScratch work on the claim 'if

f

and

g

are increasing then

fg

is increasing': take

f(x) = g(x) = x

and compare the points

-2

and

-1

. Compute

(fg)(-2) - (fg)(-1)

Proof workshopRebuild the write-up: the product of two odd integers is odd

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Proof workshopMark this proof: give the role of each line

Each line of the proof is shown in order. Choose the reason that justifies it, then press Check.

Let $x$ and $y$ be even integers.
Then $x = 2a$ and $y = 2b$ for some integers $a, b$ .
So $x + y = 2a + 2b = 2(a + b)$ .
Since $a + b$ is an integer, $x + y$ is even.

The self-check list

Before handing in a proof, check each item. This is the list a grader uses, in the order they use it.

Statement. Did I prove the statement asked, not its converse or a special case?
Technique. If not direct, did I say which technique, and is the starting assumption exactly right (for contradiction: P and not Q)?
Objects. Is every letter declared, and is it clear which are arbitrary and which I constructed?
Definitions. Did I unfold each definition fully, including side conditions (non-zero denominators, “for some integer”)?
Reasons. Could a classmate ask “why?” about any line I did not justify?
Direction. Does the write-up go forwards, with no step that assumes the conclusion?
Quantifiers. For “for every”, did I use an arbitrary object? For “there exists”, did I construct one and check it works?
Ending. Does the last sentence state exactly what was claimed?

Quick checkA proof of 'for every

\varepsilon > 0

there is

N

with …' starts 'Let

\varepsilon = 0.1

.' What is wrong?

Quick checkWhich word should never appear as a reason in a proof?

Where it is used

Used inside maths· Inside maths: every graded proof from here on

MATH 521, 541 and 551 are graded on write-ups. A correct idea without declarations, reasons and an ending typically earns partial credit; the same idea written to this checklist earns full credit. MATH 375 HW1 made it explicit: 4 of 20 points were for clarity alone.

Used in the real world· Beyond school: code review and formal proofs

A proof write-up is the mathematical version of a pull request. Reviewers at software companies ask the same things a grader does: is every variable defined, does each change have a reason, does it do what the description claims? Proof assistants (Lean, Coq) go one step further and refuse a proof with any unjustified step. Lean’s mathematics library now contains formal proofs of large parts of undergraduate mathematics, each written as declarations plus justified steps.

Traps

Watch out· Handing in scratch work

Working backwards from the conclusion is how you find a proof; it is not a proof. Rewrite the argument forwards before handing it in.

Watch out· 'Clearly', 'obviously', 'it is easy to see'

Each of these words replaces a reason. Graders read them as “the writer did not check this”.

Watch out· Proving an example

“Take $n = 4$ ” proves nothing about all $n$ . An example belongs in scratch work, or in a disproof.

Watch out· Reusing a letter

If $x = 2k$ and $y = 2k$ , you have silently assumed $x = y$ . Different objects get different letters.

Problems

check

Find every problem with this proof: “If $a \mid b$ then $a \mid bc$ . Proof: $b = ak$ , so $bc = akc$ . Clearly done.”

Solution

$a$ , $b$ , $c$ and $k$ are never declared (“Let $a, b, c$ be integers with $a \mid b$ ; then $b = ak$ for some integer $k$ ”). “Clearly done” should be “so $bc = a(kc)$ , and since $kc$ is an integer, $a \mid bc$ .”

check

Which of the self-check items does this violate? “Claim: every subspace contains $O$ . Proof: the $x$ -axis contains $(0, 0)$ .”

Solution

Item 7 (quantifiers): a ‘for every’ statement proved by one example. Also item 1: it proves a special case.

check

Rewrite as a sentence with words: " $x \in N(T) \Rightarrow T(x) = O \Rightarrow T(cx) = cT(x) = O$ ".

Solution

“Let $x \in N(T)$ , so $T(x) = O$ . Since $T$ is linear, $T(cx) = c\,T(x) = cO = O$ , so $cx \in N(T)$ .”

use

Write a complete proof, following the checklist: the product of two odd integers is odd.

Solution

Let $m$ and $n$ be odd integers. Then $m = 2a + 1$ and $n = 2b + 1$ for some integers $a, b$ . So $mn = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1$ . Since $2ab + a + b$ is an integer, $mn$ is odd. $\blacksquare$

use

This scratch work found a proof that $\{(x, y) : x + y = 0\}$ is a subspace of $\mathbb R^2$ : “(0,0) ok. (a,-a)+(b,-b)=(a+b,-(a+b)) ok. c(a,-a)=(ca,-ca) ok.” Write it up properly.

Solution

Let $S = \{(x, y) \in \mathbb R^2 : x + y = 0\}$ . We use the subspace test. First, $0 + 0 = 0$ , so $(0, 0) \in S$ . Next, let $u, v \in S$ ; then $u = (a, -a)$ and $v = (b, -b)$ for some real $a, b$ , because $x + y = 0$ means $y = -x$ . Then $u + v = (a + b, -(a + b))$ , whose entries add to 0, so $u + v \in S$ . Finally, for any real $c$ , $cu = (ca, -ca) \in S$ . By the subspace test, $S$ is a subspace of $\mathbb R^2$ . $\blacksquare$

prove

Write a complete proof by contradiction, with the first line stating the assumption: there is no largest even integer.

Solution

Suppose, for contradiction, that there is a largest even integer $M$ . Then $M + 2$ is an integer, and $M + 2 = 2k + 2 = 2(k + 1)$ where $M = 2k$ , so $M + 2$ is even. But $M + 2 > M$ , contradicting that $M$ is the largest even integer. Hence there is no largest even integer. $\blacksquare$

prove

Write a complete proof by induction, with the base case, hypothesis (using $k$ ) and conclusion each labelled: $3 \mid 4^n - 1$ for all $n \ge 1$ .

Solution

Base case: $4^1 - 1 = 3 = 3 \cdot 1$ . Inductive step: let $k \ge 1$ and assume $3 \mid 4^k - 1$ , say $4^k - 1 = 3m$ for an integer $m$ . Then $4^{k+1} - 1 = 4 \cdot 4^k - 1 = 4(3m + 1) - 1 = 12m + 3 = 3(4m + 1)$ , so $3 \mid 4^{k+1} - 1$ . By induction, $3 \mid 4^n - 1$ for all $n \ge 1$ . $\blacksquare$

stretch

Find the gap: “Claim: if $f$ and $g$ are increasing functions, then $fg$ is increasing. Proof: let $x < y$ . Then $f(x) < f(y)$ and $g(x) < g(y)$ , so $f(x)g(x) < f(y)g(y)$ .” Then find a counterexample.

Solution

Multiplying inequalities is only valid for positive quantities. With $f(x) = g(x) = x$ on $\mathbb R$ , both are increasing, but $fg(x) = x^2$ decreases on $x < 0$ : $(-2)^2 = 4 > 1 = (-1)^2$ . The missing hypothesis is that $f$ and $g$ are positive.

Summary

Scratch work finds the proof; the write-up presents it, forwards, for a reader.
Say what you prove and which technique. Declare every object, and whether it is arbitrary or constructed.
Give a reason for every step a classmate might question. Use words between formulas. Never “clearly”.
End with a sentence that states the claim.
Cite what earlier “bricks” established; prove carefully what the current chapter is about.
Before handing in, run the eight-item self-check.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

The picture: scratch work and the write-up

Scratch work

Proof write-up

The rules, with reasons

1. Say what you are proving and how

2. Declare every object before you use it

3. Go forward, and give a reason for every step that is not routine algebra

4. Write in sentences, with words between formulas

5. End by saying what you showed

6. Use the right level of detail

From scratch work to write-up

The self-check list

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere