More Examples of Proofs

You have now seen every proof strategy in Chapter 3 in isolation. Real mathematical proofs almost never use a single strategy — they layer them, peel quantifiers, drop into cases, switch to contrapositive partway through, and recombine. This section is the gym: a curated collection of theorems where the right strategy is not labelled on the box, and the proof requires combining two or three of the moves you have learned. Treat each example as a small puzzle: identify the goal's logical form, choose the outermost strategy, see what new goal emerges, choose the next strategy, and continue until the gap closes.

The strategy decision guide

Refer to this table as you tackle the examples:

Goal $P \Rightarrow Q$ → direct (or contrapositive if $\neg Q$ unpacks; contradiction if $\neg Q$ collides with a given). Goal $\forall x \in D, P(x)$ → let $x$ be arbitrary; prove $P(x)$. Goal $\exists x \in D, P(x)$ → exhibit a witness and verify. Goal $P \wedge Q$ → prove $P$; prove $Q$; conclude. Goal $P \vee Q$ → prove one disjunct, or assume $\neg P$ and prove $Q$. Goal $P \Leftrightarrow Q$ → prove both directions. Goal $\neg P$ → assume $P$ and derive a contradiction. Goal $\exists! x, P(x)$ → prove existence; prove uniqueness. Given $P \vee Q$ → case analysis.

Every theorem in this section starts with one of these forms. Match the form to the strategy and the proof begins to write itself.

Proofs about sets — the recurring shape

Set-theory proofs are the most common compound proofs in undergraduate mathematics. The key reductions:

• $A \subseteq B$: let $x \in A$ be arbitrary, show $x \in B$ — a universal-then-conditional. • $A = B$: prove $A \subseteq B$ AND $B \subseteq A$ — a conjunction of two subset proofs. • $x \in A \cup B$: show $x \in A \vee x \in B$ — a disjunction. • $x \in A \cap B$: show $x \in A \wedge x \in B$ — a conjunction. • $x \in A \setminus B$: show $x \in A \wedge x \notin B$. • $x \notin A$: negation — usually proved by contradiction.

Every set-equality proof you will encounter for the rest of Chapter 3 reduces to combinations of these. A typical mid-difficulty proof is 4 to 6 strategy applications nested inside each other.

Proofs about divisibility — the recurring shape

Divisibility statements unpack the same way every time: $a \mid b$ means $b = ak$ for some integer $k$. Almost all divisibility proofs in this chapter follow the pattern:

1. Unpack the given divisibility into $b = ak$.
2. Compute / manipulate to get the conclusion in the form $c = a \cdot (\text{integer})$.
3. Re-pack: conclude $a \mid c$.

Number-theory proofs about parity, primes, and modular arithmetic are all special cases of this template.

How to choose between competing strategies

When two strategies seem plausible, pick the one that gives the most concrete starting material. Direct proof is concrete when the hypothesis unpacks ('$n$ is even' gives $n = 2k$). Contrapositive is concrete when the negated conclusion unpacks better. Contradiction is concrete when the negated goal will clash with a structural fact. If both look equally hard, just start one — you can pivot if it stalls.

Pause and think: Given the statement "if $A \cap B = \emptyset$, then $\forall x, x \in A \Rightarrow x \notin B$," peel the strategies in order. What is your outermost strategy? Your next? When do you switch to contradiction?

Try it

• Strategy planning — for each, name the OUTERMOST and NEXT strategy (do not actually write the proof): (a) "$A \cap (A \cup B) = A$," (b) "for all integers $n$, if $n^2 + 1$ is odd then $n$ is even," (c) "there exist $x, y \in \mathbb{Q}$ with $x^2 + y^2 = 2$."
• Spot the strategy: read the proof "Let $x \in A \cap (A \cup B)$. Then $x \in A$ and $x \in A \cup B$. So $x \in A$." Identify each move — arbitrary, conjunction unpacking, conclusion.
• Write the skeleton (first sentence of each move) of a proof that "for all sets $A, B$, $A \setminus B \subseteq A$." Do not fill in the middle.
• Two-direction challenge: write the topic sentences for both directions of "an integer $n$ is divisible by 6 iff $n$ is divisible by 2 AND by 3." Which direction needs $\gcd(2,3) = 1$?
• Combined techniques: prove "if $n^2$ is irrational, then $n$ is irrational" (where $n$ is a real number). Which strategy is cleanest? Why?

A trap to watch for

The most common error in compound proofs is losing the thread — starting with a universal, dropping into a case split, switching to contradiction, and forgetting where the original quantifier or implication left off. Every time you apply a strategy, the goal transforms; the proof is only complete when the LAST goal is established and every transformation's closing claim is asserted ('since $x$ was arbitrary,' 'in both cases the conclusion holds,' 'this contradicts our assumption,' etc.). A well-organised proof signposts each transition. Treat the proof like a tree: each strategy opens a sub-branch, and you must close every branch before declaring victory. If you cannot point at the place where the original goal is finally asserted, the proof is incomplete.

What you now know

You have the full Chapter 3 toolkit: direct, contrapositive, contradiction, arbitrary-element for universals, witness for existentials, case analysis for disjunctions, two-direction for biconditionals, and existence-plus-uniqueness for $\exists!$. You can compound these to handle proofs about sets, divisibility, number theory, and abstract algebra. The next chapters will use these strategies as building blocks: induction (Chapter 6) is itself a strategy that decomposes a universal-over-$\mathbb{N}$ into a base case plus an inductive step, both proved with the techniques you just learned. The same will be true of relations and functions in later chapters. Every advanced proof is a compound of these primitives.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §3.7.
• 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, chs. 4–8.
• Solow, D. (2014). How to Read and Do Proofs (6th ed.). Wiley, ch. 13 (Putting it all together).
• Pierce, B. C. et al. (2018). Software Foundations, Vol. 1: Logical Foundations. Online textbook (Coq), ch. 'Tactics' (composing tactics).