Proof Strategies

How does a mathematician turn a vague hunch — "I think this is true" — into a permanent fact the entire community will accept? By writing a proof: a step-by-step argument that begins from accepted truths (axioms, definitions, prior theorems) and ends, by undeniable logic, at the conclusion. Chapter 3 is the heart of the course because here we stop talking about logic and start doing mathematics. The structured approach you will learn — analyse the goal, choose a strategy, work the gap from both ends — is exactly how working mathematicians draft proofs, and exactly how proof assistants like Coq and Lean check them. Master this skeleton and the rest of the chapter is variations on a theme.

Givens and goals

The most fundamental distinction in proof-writing is between givens — statements you already know (or have assumed) to be true — and the goal, the statement you are trying to prove. The entire art of proof is figuring out how to bridge the gap. At every step you should be able to point to your current givens list and your current goal and say: "I am here, I want to be there."

Givens grow as the proof progresses (each derived step adds to them). Goals can shrink and transform: assuming the hypothesis of an implication moves it onto the givens side; letting a variable be arbitrary peels off a universal quantifier from the goal. Watching the givens/goal pair evolve is how you stay oriented inside a long proof.

The direct proof template

The direct proof is the most natural strategy for proving a conditional $P \Rightarrow Q$. The skeleton is:

1. Assume $P$ (add it to your givens).
2. Use definitions and known results to derive intermediate facts.
3. Conclude $Q$. $\blacksquare$

Each line must follow logically from earlier givens. "Therefore," "so," and "hence" are not decorative — they are claims that the next line is a logical consequence of what came before. If a reader cannot reconstruct the reasoning for any step, the proof is broken.

The structured approach

Before writing any prose, do the bookkeeping:

Step 1. Write your givens and your goal explicitly. Step 2. Analyse the logical form of the goal. Step 3. Choose a strategy matched to that form. Step 4. Apply the strategy — this transforms givens and goal. Step 5. Repeat until givens entail the goal.

Strategies are chosen by the form of the goal: $P \Rightarrow Q$ → direct proof, $\forall x, P(x)$ → arbitrary $x$, $\exists x, P(x)$ → exhibit a witness, $P \wedge Q$ → prove each conjunct, $P \vee Q$ → prove one disjunct or assume the negation of the other. The full menu of strategies is the rest of this chapter.

Working from both ends

Experienced provers work forward from givens (what new facts can I derive?) and backward from the goal (what would suffice to conclude it?) until the two directions meet. The final written proof reads forward, but the discovery process is bidirectional. If you stare at the goal and feel stuck, ask: "what is the form of this goal, and what is the standard move for that form?" Then make that move and see what new goal you face.

Pause and think: Suppose your goal is "If $n$ is an integer, then $n^2 + n$ is even." What are your givens? What is the form of the goal? Which strategy does that form suggest? (Hint: there is an outer universal and an inner conditional. Peel them in order.)

The shape of a proof, visualized

Every proof has a tree structure: the goal at the root, decomposed step by step into sub-goals and finally into premises at the leaves. The widget below builds proof trees one layer at a time for four canonical proofs (direct, contrapositive, contradiction, existence). Watch how the goal decomposes — that decomposition is the strategy.

Try it

• For each statement, identify givens, goal, and the matching strategy before writing a single line of proof: (a) "If $a \mid b$, then $a \mid 3b$." (b) "For all integers $n$, $n^3 - n$ is even."
• Predict first: in the direct proof of "if $m$ and $n$ are even, then $m + n$ is even," what is the very first line you write after "Assume the hypothesis"?
• Spot the flaw: a student writes "Suppose $n$ is even. Then $n = 4$ is even, and $n^2 = 16$ is even. So if $n$ is even then $n^2$ is even." What strategy did they violate?
• Work backward: to prove $a \mid (b + c)$, what definition of "divides" must you end at? Now work forward: what does the given $a \mid b$ tell you in symbolic form?
• Skeleton-only: write the first sentence and the last sentence of a direct proof of "if $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$." Do not fill in the middle.

A trap to watch for

The single most common rookie mistake is to prove by example: substituting one concrete value for an arbitrary variable and declaring the universal proved. "Let $n$ be an arbitrary integer. Take $n = 4$: then $n^2 = 16$ is even..." is not a proof — it shows the claim holds for one integer, not all of them. The word "arbitrary" in a proof means: I am about to do the proof in a way that uses no special property of this object beyond its membership in the domain. If your argument uses the fact that $n$ equals a specific number, you have not proved the universal. Examples are useful for building intuition and finding counterexamples, but they cannot replace a general argument.

What you now know

You can take any mathematical statement, identify its givens and goal, analyse the logical form of the goal, and choose a proof strategy that matches. You know the direct-proof template for conditionals and the structured-approach bookkeeping that keeps long proofs from wandering. The remaining sections of this chapter are each a specialisation: contradiction and contrapositive for conditionals you cannot crack directly, quantifier strategies for "for all" and "there exists," and case analysis for disjunctions. Every one of them slots into the same structured-approach skeleton.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §3.1.
• Polya, G. (1957). How to Solve It: A New Aspect of Mathematical Method. Princeton University Press.
• Hammack, R. (2018). Book of Proof (3rd ed.). Open-source textbook, ch. 4.
• Solow, D. (2014). How to Read and Do Proofs (6th ed.). Wiley, ch. 1–3.
• Pierce, B. C. et al. (2018). Software Foundations, Vol. 1: Logical Foundations. Online textbook (Coq), ch. "Logic."