UK A-Level: Proof by Deduction and Exhaustion

At the heart of advanced mathematics lies the concept of proof—the definitive, logical argument that establishes a statement as universally true. For A-Level students, moving from computational mathematics to the rigorous world of formal proof is a critical step. Mastering the foundational techniques of proof by deduction and proof by exhaustion not only secures marks in exams but also cultivates the precise, analytical thinking essential for university-level STEM subjects.

The Language and Structure of Mathematical Proof

Before diving into specific methods, you must understand the formal environment in which proofs exist. A mathematical proof is a sequence of logical deductions, starting from known facts or assumed premises, that leads inexorably to the statement you wish to prove. The known facts can be axioms (fundamental assumptions), previously proven theorems, or given conditions of the problem.

The language is precise. You will use key phrases like "let...", "assume that...", "therefore...", "hence...", and "it follows that..." to structure your argument. Each step must be justified, either by basic algebra, a known theorem (e.g., "by the factor theorem..."), or a logical principle. A proof is not an exploration; it is a directed, watertight argument. At A-Level, you are expected to present proofs clearly, using correct mathematical notation and coherent written explanation, often concluding with a final statement such as "QED" (quod erat demonstrandum) or a simple box (∎).

Proof by Deduction (Direct Proof)

Proof by deduction, or direct proof, is the most straightforward and common technique. You start from known truths and apply a series of logical, typically algebraic, steps to arrive directly at the statement you need to prove.

The classic A-Level example involves proving statements about even and odd numbers. Recall the definitions: an even integer can be written as $2k$ for some integer $k$; an odd integer can be written as $2k+1$.

Example: Prove that the sum of any two odd numbers is even.

1. Let the first odd number be $2m+1$, where $m$ is an integer.
2. Let the second odd number be $2n+1$, where $n$ is an integer.
3. Their sum is $(2m+1)+(2n+1)=2m+2n+2$.
4. This simplifies to $2(m+n+1)$.
5. Since $m$ and $n$ are integers, $(m+n+1)$ is also an integer. Let this integer be $p$.
6. Therefore, the sum is $2p$, which is by definition an even number.
7. Hence, the sum of any two odd numbers is even.

Notice the structure: introduce variables using the definitions, manipulate the algebra, and finally re-express the result in a form that matches the definition of the conclusion. Your job is to build a logical bridge from "what you know" to "what you need to show."

Proof by Exhaustion

Proof by exhaustion is used when a statement needs to be verified for every case in a finite, and manageably small, set of possibilities. You quite literally "exhaust" all possibilities, proving the statement separately for each one.

This method is powerful for theorems about specific numbers, divisibility rules in a limited set, or properties of shapes with a fixed number of sides. The critical step is demonstrating that your list of cases is complete and that no possibility has been missed.

Example: Prove that the only prime number that is one less than a perfect cube is 7.

1. Consider the perfect cubes near a prime: $1^3=1$, $2^3=8$, $3^3=27$, $4^3=64$, etc.
2. The numbers one less than these are: $0,7,26,63,...$
3. We test each for primality within a reasonable range. The statement says "prime number," so we only need to find all primes of this form.

• $1^3-1=0$: Not prime.
• $2^3-1=7$: This is prime.
• $3^3-1=26$: This is even and greater than 2, so not prime.
• For any integer $n>2$, $n^3-1=(n-1)(n^2+n+1)$. Since $n-1>1$, this is a product of two integers greater than 1, so $n^3-1$ is composite.

1. We have exhausted all cases (for $n=1$ and $n=2$ by direct check, and for $n>2$ by a general algebraic argument). The only prime found is 7.

The exhaustion was achieved by splitting into cases: $n=1$, $n=2$, and $n>2$. The final case used a general deductive argument to cover infinitely many numbers, which is a clever and valid way to complete an exhaustion proof.

Disproof by Counterexample

To disprove a universal statement (a statement claiming something is true "for all..."), you only need to find a single, specific example where it is false. This is called a counterexample. It is a crucial skill, as identifying false conjectures is as important as proving true ones.

Example: Disprove the statement "For all real numbers $x$, $x^2>x$." You might test a few numbers and find that for $x=0.5$, $x^2=0.25$, which is not greater than $0.5$. Therefore, $x=0.5$ is a valid counterexample. The statement is false. The counterexample must satisfy the conditions of the statement (here, being a real number) but violate its conclusion.

Proof by Contradiction Fundamentals

Proof by contradiction is a powerful indirect method. You start by assuming the opposite of what you want to prove is true. You then proceed with logical deductions from this assumption until you reach an impossibility—a statement that contradicts a known fact, an earlier step, or the assumption itself. This logical clash means your initial assumption must be false, and therefore the original statement you wanted to prove must be true.

The classic A-Level example is proving the irrationality of $\sqrt{2}$.

1. Assume the opposite: Assume $\sqrt{2}$ is rational, so it can be written as a fraction $\frac{a}{b}$ where $a$ and $b$ are integers with no common factors (in its simplest form).
2. Deduce: Then $2=\frac{a^2}{b^2}$, so $a^2=2b^2$. This means $a^2$ is even.
3. A key lemma: If $a^2$ is even, then $a$ itself must be even. So let $a=2k$.
4. Substitute: $(2k{)}^2=2b^2$ $\to$ $4k^2=2b^2$ $\to$ $b^2=2k^2$. This means $b^2$ is even, so $b$ is also even.
5. Find the contradiction: We have shown both $a$ and $b$ are even. This contradicts our initial stipulation that $a$ and $b$ have no common factors (they share a factor of 2).
6. Conclude: Our initial assumption that $\sqrt{2}$ is rational leads to a contradiction. Therefore, $\sqrt{2}$ must be irrational.

The skeleton of a contradiction proof is: 1) Assume the negation. 2) Deduce logically. 3) Find a contradiction. 4) Conclude the original statement is true.

Common Pitfalls

1. Assuming the Result (Circular Reasoning): This is the most serious error. You cannot use the statement you are trying to prove as a step in your proof. Example: "To prove $x^2\ge 0$ for all real $x$, we note that squaring a number makes it positive, so $x^2\ge 0$." This simply re-states the question. A correct proof would use properties of order and multiplication.

1. Incomplete Proof by Exhaustion: Failing to demonstrate that all cases have been covered. Simply checking a few examples is not proof by exhaustion unless you have argued that these are the only examples. Always state why your list of cases is complete.

1. Misusing Counterexamples: Using an example that doesn't meet the conditions of the original statement. For "For all prime $p>2$, $p$ is odd," the counterexample $p=9$ is invalid because 9 is not prime. The search for a counterexample must be within the hypothesis's constraints.

1. Unjustified Steps in Deduction: Skipping algebraic or logical steps you deem "obvious." At A-Level, you must show key manipulations, especially when applying definitions (like even/odd) or factorising. If you use a theorem (e.g., the Factor Theorem), state that you are using it.

Summary

• A mathematical proof is a logically sound, step-by-step argument that establishes a statement as universally true, using precise language and clear justification.
• Proof by deduction builds a direct chain of reasoning from known facts to the desired conclusion, often through algebraic manipulation of carefully defined terms.
• Proof by exhaustion is used for finite scenarios, requiring the methodical verification of a statement for every single possible case, ensuring the list of cases is complete.
• To disproof by counterexample, find just one specific example that satisfies the conditions of a universal statement but violates its conclusion.
• Proof by contradiction works indirectly: assume the statement is false, deduce logically until you reach an impossible contradiction, which forces you to conclude the original statement must be true.