Skip to main content

Proof Strategy Starts from Theorem Shape

What This Concept Is​

Proof strategy is the deliberate act of matching a theorem's surface form to a productive proof method before committing to symbols. You do not choose a method because it is your favourite or because the last proof you wrote used it. You choose it because the theorem's shape -- implication, biconditional, universal, existential, negation of a universal -- suggests a specific opening move.

Common matches:

Theorem shapeFirst-try method
$\forall x,\ P(x) \rightarrow Q(x)$direct proof from $P(x)$, or contrapositive from $\lnot Q(x)$
$P \leftrightarrow Q$prove both directions separately
$\exists x,\ P(x)$construct a specific witness
$\forall x,\ P(x)$ -- but you suspect falsehunt for a counterexample
Claim whose negation gives a concrete impossibilityproof by contradiction
Statement split by a definition or dichotomyproof by cases
Statement indexed by $\mathbb{N}$ with self-similar structureinduction

The underlying discipline is Polya's: understand the problem first; devise a plan; only then carry it out. See Wikipedia: How to Solve It for the original four-step heuristic which still structures most working mathematicians' practice.

The skill being trained is reading mathematical shapes fluently. A fluent reader sees "$\forall n \in \mathbb{N},\ \ldots$" and immediately thinks "induction is a candidate." A fluent reader sees "if and only if" and immediately starts a two-column proof skeleton with labelled directions.

Why It Matters Here​

Most beginner proof frustration comes from trying to prove everything the same way -- usually by staring at the statement and hoping manipulation produces a result. The theorem is already telling you half the proof structure in its connectives. Ignoring that information and flailing with algebra is expensive.

Strategy-first thinking also protects against two widespread bugs:

  • Proving the wrong theorem. Without a plan, students often drift into proving the converse, the contrapositive without labelling it, or a near-miss statement.
  • Doing the right algebra in the wrong shape. Many "proofs" in homework are manipulations that would establish an equivalence if only the student had started by assuming the right hypothesis.

Later modules reinforce this habit. Algorithmic correctness proofs in Semester 2 almost always decompose into (a) a termination argument by well-founded descent, (b) a partial-correctness argument by loop invariant, and (c) a base case. That's strategy-first at scale -- the theorem shape dictates the proof skeleton.

Concrete Examples​

Example 1 -- shape suggests contrapositive.

Statement: "If $n^2$ is even, then $n$ is even."

A direct proof is possible but awkward (you would need to argue from "$n^2$ is a multiple of 2" back to $n$). The contrapositive is much cleaner:

Suppose $n$ is odd. Write $n = 2k + 1$. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd.

Because the contrapositive is true, the original implication is true. The theorem shape did not force contraposition, but it strongly suggested it.

Example 2 -- shape forces two halves.

Statement: "An integer is divisible by 6 iff it is divisible by 2 and by 3."

The biconditional demands two directions. Forward ($\rightarrow$) is nearly free: $n = 6k \Rightarrow n = 2(3k) = 3(2k)$. Reverse ($\leftarrow$) is the substantive half: from $2 \mid n$ and $3 \mid n$, derive $6 \mid n$. This uses either the coprimality lemma ($\gcd(2, 3) = 1$) or a direct argument on cases mod 6.

Writing this as "just one direction" would leave half the theorem unproven, regardless of how careful the algebra looked.

Example 3 -- shape suggests hunting for a counterexample first.

Statement: "Every function $f : \mathbb{Z} \rightarrow \mathbb{Z}$ that is injective is surjective."

Before attempting a proof, notice this is a universal claim with a modest-sized counterexample candidate space. Ten seconds' thought gives $f(n) = 2n$: injective, not surjective (odd integers are missed). The strategic move was to not start a proof; the shape of the claim said "try a counterexample first, and only if no counterexample survives do you bother proving it."

Example 4 -- the same theorem with two valid plans.

Statement: "There are infinitely many primes."

  • Plan A (contradiction, Euclid's classic). Suppose finitely many primes $p_1, \ldots, p_k$; consider $N = p_1 p_2 \cdots p_k + 1$; $N$ is not divisible by any $p_i$; so its prime factorisation exposes a prime outside the list, contradicting finiteness.
  • Plan B (direct construction). Show that for every $n \ge 1$, there exists a prime larger than $n$. One way: argue that $n! + 1$ has a prime factor, and that factor must exceed $n$.

Both plans reach the same conclusion. Choosing between them is a strategic call -- the first is shorter, the second is more constructive and easier to generalise. A strategy-first student knows this choice exists before writing the proof.

Common Confusion / Misconceptions​

  1. "Start manipulating until something pops out." This is the opposite of strategy. Symbol-pushing without a plan tends to produce algebra that is correct but irrelevant, because no direction of proof has been committed to.
  2. "The chosen method is valid only when it feels natural." Validity comes from logic, not comfort. Contrapositive proofs are valid whether or not they feel like the intuitive route; contradiction is valid whether or not it matches your first guess at the argument.
  3. "Always use the method that worked last time." Habits calcify. A student who learned direct proofs first will try direct proof on every theorem, including ones that obviously need induction or a counterexample.
  4. "The plan sentence is unnecessary once I understand the theorem." Writing down the plan ("I will prove both directions; the forward direction is direct, the reverse by contrapositive") is cheap insurance against drift. Skipping it is exactly the habit Polya warns against in How to Solve It.

How To Use It​

Before writing any proof body, ask the following in sequence:

  1. What is the outermost connective? Implication, biconditional, universal, existential, negation, conjunction of claims?
  2. Is the direct route natural? If yes, proceed. If no, consider contrapositive, contradiction, or cases.
  3. Would a counterexample settle the matter faster? If the claim is universal and suspicious, spend a few minutes testing small or extreme cases.
  4. Does the statement split naturally into cases? Parity, sign, emptiness of a set, or base-vs-inductive step all signal case analysis.
  5. Is there an inductive structure? If the statement is indexed by $\mathbb{N}$ or by the constructors of a recursive type, induction (ordinary, strong, or structural) is probably the right tool.
  6. Write one sentence of plan. Example: "Prove both directions. Forward is direct from the definition of divisibility; reverse uses contrapositive."
  7. Only now start writing the proof. If the plan fails partway, stop and revise the plan before continuing to scribble symbols.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). Every correctness proof is a composite: "prove the loop invariant by induction, prove termination by a well-founded measure, conclude partial correctness from the invariant at exit." That whole architecture is strategy-driven -- the shape of the correctness claim forces the three-part proof skeleton.
  • Semester 5 (concurrency). Deadlock-freedom is a universal claim over reachable states; the strategic choice is invariant or model checking. Liveness is an existential claim over executions; the strategic choice is fairness assumptions plus progress arguments.
  • Semester 6 (distributed systems). Proving a protocol correct decomposes into safety (universal, by invariant) and liveness (existential, by progress). Consensus proofs structurally mirror the strategy laid out here.
  • Semester 7 (architecture). Reviewing an ADR is a miniature proof strategy exercise: classify the claim's shape, identify the obligation, and select the review technique matching that shape. Risk-driven review is Polya's planning step applied to architecture decisions.

Check Yourself​

  1. Why does the theorem's outermost connective matter before any algebra starts?
  2. What is usually the cleanest structure for an iff statement, and why do two paragraphs work better than one?
  3. Give an example of a universally quantified statement that is best disproved, not proved. What signalled this to you?
  4. When is contradiction strictly preferable to contrapositive? When is it strictly worse?
  5. Why does writing a one-sentence plan before the proof reduce errors, even for experienced provers?
  6. Name one theorem shape from this cluster that would make you reach for induction and one that would make you reach for cases.

Mini Drill or Application​

For each statement, write a one-sentence proof plan (method + why it fits the shape), then identify the first line of the proof you would actually write:

  1. "If $a$ and $b$ are odd integers, then $ab$ is odd."
  2. "An integer is divisible by 6 iff it is divisible by 2 and by 3."
  3. "All functions from a finite set to itself are injective."
  4. "For every $n \ge 1$, $1 + 2 + \cdots + n = n(n+1)/2$."
  5. "There exists no largest prime."
  6. "For every integer $n$, $n^3 - n$ is divisible by 6."

Compare your plans with a classmate's. Disagreements on strategy are more instructive than disagreements on algebra.

Read This Only If Stuck​