Choosing a Route from Assumptions to a Conclusion
A proof is not just a collection of true statements: each step must follow from the assumptions or from a result already established. In “Finding the Right Lemma,” we saw how an intermediate fact can bridge a gap between what is given and what must be shown. Elementary proofs also rely on choosing an effective route through the argument. Sometimes the assumptions lead straight to the conclusion. Sometimes it is easier to divide the possibilities into cases, prove an equivalent contrapositive, or assume the conclusion fails and derive a contradiction.
The first step is to identify the logical shape of the claim. An implication has the form “if \(P\), then \(Q\).” A direct proof starts with \(P\) and derives \(Q\). A contrapositive proof instead proves “if not \(Q\), then not \(P\),” which is logically equivalent to the original implication. A proof by contradiction assumes that the desired claim is false and shows that this assumption conflicts with something known. A proof by cases establishes the claim separately for possibilities that together cover every permitted input.
These are strategies, not shortcuts around justification. In a case argument, the cases must cover all possibilities. In a contrapositive proof, the statement proved must genuinely be the contrapositive, not merely a related claim. In a contradiction proof, the contradiction must follow from the assumptions and the temporary assumption that the conclusion fails.
Direct Proof and Proof by Cases
A direct proof is a natural first choice when the hypothesis supplies useful inequalities, equations, or definitions. For example, if the hypothesis says that two positive numbers are ordered, the difference between their reciprocals can make the conclusion transparent. A proof by cases is useful when an object can be divided into a small number of forms and the argument depends on which form occurs.
Worked Example: Comparing Reciprocals Directly
We prove that if \(0<x<y\), then \(1/y<1/x\). The assumptions imply \(y-x>0\), and \(xy>0\), so the following difference is positive:
The equality follows by putting the two fractions over the common denominator \(xy\). Since \(1/x-1/y>0\), we have \(1/y<1/x\), as required. This direct proof works because the hypothesis gives precisely the signs needed to show that the difference is positive.
Worked Example: The Larger of a Number and Its Negative
For every real \(x\), we claim that \(|x|\) is the larger of \(x\) and \(-x\). We divide into the exhaustive cases \(x\geq0\) and \(x<0\).
If \(x\geq0\), the definition of absolute value gives \(|x|=x\). Also, \(x\geq -x\), since \(2x\geq0\). Thus \(x\), and therefore \(|x|\), is the larger of the two numbers. If \(x<0\), then \(|x|=-x\). In this case \(-x>x\), because \(-2x>0\), so again \(|x|\) is the larger. The cases include every real \(x\), and the claim follows.
The case split is part of the proof, not merely a convenience in the explanation. The inequalities defining the cases account for the boundary as well: \(x=0\) belongs to the first case, and both numbers are then equal. A split into \(x>0\) and \(x<0\) alone would leave that value untreated.
Contrapositive: Reverse the Direction Carefully
For an implication \(P\Rightarrow Q\), its contrapositive is \(\neg Q\Rightarrow\neg P\). These statements are equivalent: they are false in exactly the same situation, namely when \(P\) is true and \(Q\) is false. The contrapositive can be easier to prove when it is simpler to describe what would make the conclusion fail than to build the conclusion directly.
Worked Example: A Bound on a Sum
We prove that for real numbers \(x\) and \(y\), if \(x+y>10\), then \(x>5\) or \(y>5\). The conclusion is an “or” statement, so a useful contrapositive is: if \(x\leq5\) and \(y\leq5\), then \(x+y\leq10\).
Assume \(x\leq5\) and \(y\leq5\). Adding the inequalities gives \(x+y\leq5+5=10\). This proves the contrapositive. Therefore the original implication holds: if \(x+y>10\), it cannot be true that both \(x\leq5\) and \(y\leq5\), so at least one of \(x>5\) or \(y>5\) must hold.
Negating a conclusion with “or” changes it to a conjunction: “not \(x>5\) and not \(y>5\)” means \(x\leq5\) and \(y\leq5\). This is why it is important to write out the contrapositive before proving it. A common error is to negate only one part of a compound conclusion, or to reverse the implication without negating both statements.
A Case Argument with Integer Remainders
The division algorithm gives a systematic way to make cases for integers. For any integer \(n\), division by \(3\) gives exactly one of the forms \(n=3k\), \(n=3k+1\), or \(n=3k+2\), where \(k\) is an integer. These cases are exhaustive, so a calculation in each case can establish a conclusion for every integer.
Proof. Let \(n\) be an integer. By the division algorithm, there are an integer \(k\) and a remainder \(r\in\{0,1,2\}\) such that \(n=3k+r\). We examine all three possible remainders.
If \(r=0\), then \(n=3k\), so \(3\mid n\). If \(r=1\), then
The final expression has remainder \(1\) upon division by \(3\), so \(3\nmid n^2\). If \(r=2\), then
This expression also has remainder \(1\), so again \(3\nmid n^2\). Thus, in the two nonzero-remainder cases, the hypothesis \(3\mid n^2\) cannot hold. Under that hypothesis the only possible case is \(r=0\), which gives \(3\mid n\). This proves the theorem. \(\square\)
The calculations establish more than the desired implication: a square of an integer has remainder \(0\) or \(1\) when divided by \(3\), never remainder \(2\). For the theorem, the key point is that the remainder is \(0\) only when the original integer has remainder \(0\). The proof succeeds because the remainder cases are exhaustive and each algebraic identity is explicit.
Contradiction: Assume the Opposite
A proof by contradiction begins by assuming that the desired conclusion is false. The proof then uses that assumption together with the original hypotheses to reach a statement known to be impossible. The temporary assumption must be stated clearly, and the final contradiction must actually conflict with an established fact or with another consequence of the assumptions.
Worked Example: The Square Root of Three Is Irrational
We prove that the positive square root of \(3\) is irrational. Suppose, for contradiction, that \(\sqrt{3}\) is rational. Then \(\sqrt{3}=p/q\) for integers \(p\) and \(q\), with \(q>0\). Among all such representations, choose one with the smallest positive denominator \(q\). Such a smallest denominator exists by the Well-Ordering Principle.
Squaring the equation and multiplying by \(q^2\) gives
Thus \(3\mid p^2\). By the theorem just proved, \(3\mid p\), so \(p=3k\) for some integer \(k\). Substitute this into the equation:
It follows that \(3\mid q^2\), and the same theorem gives \(3\mid q\). Write \(q=3\ell\) for an integer \(\ell\). Since \(q>0\), we have \(\ell>0\), and \(q/3=\ell<q\). Also \(p/3=k\) is an integer, so
This is another representation of \(\sqrt{3}\) with a positive integer denominator smaller than \(q\), contradicting the choice of \(q\). Therefore \(\sqrt{3}\) is irrational.
The contradiction is not simply that a fraction appears in the argument; rational numbers are fractions by definition. The contradiction is that the assumed rational representation can be replaced by another one with a strictly smaller positive denominator, despite the original denominator being chosen as the smallest possible. The divisibility theorem supplied the intermediate fact needed to produce that smaller representation.
A Practical Choice of Proof Strategy
When beginning a proof, first rewrite the claim in a form that exposes its assumptions and conclusion. Then consider the structure of the conclusion and the available information. A direct proof is often suitable when the assumptions give quantities that can be rearranged or compared. A case proof is natural when a definition divides the possibilities into a few exhaustive forms. A contrapositive proof is useful when the negation of the conclusion gives simpler assumptions. Contradiction is effective when assuming failure leads to a conflict, such as violating a minimum choice or an established theorem.
For an implication, separate the hypothesis from the conclusion. For a universal claim, keep in view that the argument must cover every permitted input.
Use the definitions and assumptions to see whether the conclusion follows through a short chain of justified steps.
If the direct route stalls, test whether exhaustive cases, the contrapositive, or a contradiction gives a more manageable target.
Verify that every case is covered, every negation is correct, and the final step really establishes the requested conclusion.
One common pitfall is choosing a strategy before checking its logical details. Cases that omit a boundary value leave a gap. A contrapositive proof that establishes a different implication does not prove the original claim. A contradiction argument that ends with an unexpected result, but no actual incompatibility, is unfinished. Writing the route in a few words before doing the algebra can prevent these errors.
No single method is always best. The goal is not to use the most elaborate strategy, but to make the reasoning easy to verify. In the examples here, direct comparison used a positive difference, an absolute-value claim called for two sign cases, and the irrationality proof used a contradiction tied to a smallest denominator. Matching the proof structure to the claim is a central part of elementary proof mastery.
Check Your Understanding
For each question, identify the proof structure and the logical step that makes it work.
- What is the contrapositive of “if \(P\), then \(Q\),” and why is it equivalent to the original implication?
- Why must the cases in a proof by cases be exhaustive? In the absolute-value example, where is the value \(x=0\) handled?
- In the theorem about divisibility by \(3\), what are the possible remainders for \(n\), and what remainders can \(n^2\) have?
- In the irrationality proof, what contradicts the choice of the denominator \(q\) as smallest?
- Give one feature of a claim that might make a contrapositive or a proof by cases more useful than a direct proof.