The validity of proof by exhaustion stems from the basic logical principle that if a proposition is true for every element in a finite set , then the proposition "for all is true" is also true. This is a direct application of the conjunction rule in logic, where if is true, then the universal statement over is true.
This method relies on the ability to partition the domain of the statement into a finite number of distinct, non-overlapping, and collectively exhaustive cases. Each case represents a subset of the domain, and together they cover the entire domain relevant to the statement. The proof then proceeds by demonstrating the truth of the statement within each of these sub-domains.
The strength of this method lies in its directness and certainty once all cases are verified. Unlike inductive proofs which infer general truth from a base case and a recursive step, or deductive proofs which rely on general axioms, proof by exhaustion provides a concrete, case-by-case verification that leaves no room for doubt, provided the case analysis is complete and correct.
Applicability: Proof by exhaustion is most effective in scenarios where the number of possible inputs or conditions is small and finite. This often occurs in problems involving small integers, specific configurations in combinatorics, or properties of small graphs. For instance, proving a property for all prime numbers less than 10, or for all possible arrangements of 3 items.
Limitations: The primary limitation is its impracticality for large or infinite domains. If the number of cases is too vast, the time and effort required to check each one become prohibitive, making the method unfeasible. For example, proving that "all even numbers are divisible by 2" cannot be done by exhaustion because there are infinitely many even numbers.
Minimizing Cases: To make the method more efficient, one can often reduce the number of distinct cases that need to be checked. This might involve using properties like symmetry, modular arithmetic, or other mathematical insights to group similar cases or show that if a property holds for one representative of a group, it holds for all. For example, when checking primality of a number , one only needs to test divisibility by primes up to .
Clearly State Cases: When using proof by exhaustion, explicitly list and define each case you intend to verify. This demonstrates a clear understanding of the method and helps organize your work.
Systematic Verification: Show clear, step-by-step working for each case. Do not just state the result; demonstrate how it is derived for that specific case, ensuring logical flow and accuracy.
Ensure Completeness: Double-check that your chosen cases cover all possibilities within the given domain. A common error is to miss an edge case or a specific type of value, which invalidates the entire proof.
Conclude Clearly: End the proof with a concise statement affirming that, since all cases have been verified, the original statement is proven by exhaustion for its specified domain. This provides a definitive closure to your argument.
Incomplete Case Analysis: The most frequent error is failing to identify or verify all possible cases. This renders the entire proof invalid, as there might be an unexamined scenario where the statement does not hold.
Confusing Examples with Exhaustion: Simply showing a few examples where a statement holds is not proof by exhaustion. The method demands verification of every single allowed value within the finite domain, not just a representative subset.
Applying to Infinite Sets: Attempting to use proof by exhaustion for statements over infinite sets (e.g., "all integers") is a fundamental misunderstanding of the method's scope and limitations. It is inherently designed for finite domains.
Lack of Clarity: Presenting cases in a disorganized or unclear manner can make the proof difficult to follow and assess, even if the underlying logic is sound. Clear presentation is crucial for demonstrating the validity of the exhaustive check.
