What is the fundamental difference between a 'set of examples' and a 'proof by exhaustion'?

A set of examples only shows a statement is true for specific instances, whereas a proof by exhaustion tests every possible instance in the domain, leaving no room for counter-examples.

When is proof by exhaustion preferred over proof by deduction?

It is preferred when the domain is finite and small, or when the statement behaves differently across different subsets of the domain, making a single algebraic proof difficult.

How does proof by exhaustion relate to disproof by counter-example?

They are opposites: exhaustion proves a statement is true for all cases, while a counter-example proves a statement is false by finding just one case where it fails.

What is the most common error when defining cases for a proof by exhaustion?

Failing to make the cases 'collectively exhaustive,' which means some values in the domain are not covered by any of the tested cases.

Why is it a mistake to use exhaustion for the domain of 'all real numbers'?

The set of real numbers is uncountably infinite; you cannot test every individual value, and they cannot be easily partitioned into a finite set of discrete cases like integers can.

What happens to a proof by exhaustion if one case is found to be false?

The entire proof fails, and the general statement is disproven. The failing case acts as a counter-example to the original claim.

Define 'collectively exhaustive' in the context of mathematical proof.

It means that the set of cases chosen covers every single possibility within the domain, ensuring no value is left out of the proof.

What does it mean for cases to be 'mutually exclusive'?

It means the cases do not overlap; no single value from the domain belongs to more than one case, which simplifies the proof structure.

In proof by exhaustion, what is a 'finite domain'?

A domain that contains a specific, countable number of elements, such as the set of integers between 1 and 100.

How can you use exhaustion for an infinite set of integers?

By partitioning the infinite set into a finite number of exhaustive categories, such as 'even' ($2n$) and 'odd' ($2n+1$), and proving the statement for both categories.

Library Podcasts

Courses

Referral & Rewards

Proof by Exhaustion

Summary

Proof by exhaustion is a mathematical technique used to verify a statement by breaking the problem down into a finite number of cases and proving each case individually. It is most effective when the domain of the problem is small or can be logically partitioned into a manageable set of exhaustive categories.

1. Definition & Core Concepts

Proof by Exhaustion is a method of mathematical proof where a statement is shown to be true by examining every possible case within the given domain. If the statement holds for every individual case, the entire statement is considered proven.

The term 'exhaustion' refers to the fact that the proof 'exhausts' all possibilities, leaving no scenario unexamined. This method relies on the domain being finite or being able to be split into a finite number of exhaustive subsets.

A key requirement is that the cases chosen must be mutually exclusive (no overlap) and collectively exhaustive (covering every possible value in the domain). If even one case is omitted, the proof is logically incomplete.

Diagram showing a domain split into three distinct, exhaustive cases (Case 1, Case 2, and Case 3) to illustrate the concept of proof by exhaustion.

2. Underlying Principles

3. Methods & Techniques

Step 1: Define the Domain

Clearly identify the set of numbers or objects the statement applies to. For example, if the statement is about 'integers between 1 and 10', the domain is $\{1, 2, 3, ..., 10\}$ .

Step 2: Partition into Cases

Divide the domain into a finite number of cases. If the domain is small, each individual value can be a case. If the domain is large or infinite, group them into categories like even ( $2n$ ) and odd ( $2n+1$ ).

Step 3: Verify Each Case

Perform the necessary calculations or logical steps for every single case identified. You must show that the statement holds true for every subset created in Step 2.

Step 4: Conclude

State that since all possible cases have been tested and found true, the general statement is proven by exhaustion.

4. Key Distinctions

5. Exam Strategy & Tips

6. Common Pitfalls & Misconceptions

Proof by Exhaustion

Summary

1. Definition & Core Concepts

Diagram showing a domain split into three distinct, exhaustive cases (Case 1, Case 2, and Case 3) to illustrate the concept of proof by exhaustion.

2. Underlying Principles

The logical foundation of this method is the Law of the Excluded Middle, which suggests that for any proposition, either that proposition is true or its negation is true. By proving every specific instance of a proposition, we eliminate the possibility of its negation being true.

It utilizes the property of disjunction. If a statement $P$ is equivalent to $C_1 \lor C_2 \lor ... \lor C_n$ , then proving $C_1 \implies P$ , $C_2 \implies P$ , ..., and $C_n \implies P$ confirms that $P$ is true for the entire set.

This method is purely deductive but relies on brute-force verification. Unlike a general algebraic proof that uses variables to represent any number, exhaustion uses specific values or specific categories of values.

3. Methods & Techniques

Step 1: Define the Domain

Clearly identify the set of numbers or objects the statement applies to. For example, if the statement is about 'integers between 1 and 10', the domain is $\{1, 2, 3, ..., 10\}$ .

Step 2: Partition into Cases

Divide the domain into a finite number of cases. If the domain is small, each individual value can be a case. If the domain is large or infinite, group them into categories like even ( $2n$ ) and odd ( $2n+1$ ).

Step 3: Verify Each Case

Perform the necessary calculations or logical steps for every single case identified. You must show that the statement holds true for every subset created in Step 2.

Step 4: Conclude

State that since all possible cases have been tested and found true, the general statement is proven by exhaustion.

4. Key Distinctions

It is important to distinguish between proving a statement and merely providing examples. A proof by exhaustion is only valid if every possible case is checked.

Feature	Proof by Exhaustion	Proof by Deduction
Approach	Case-by-case verification	General algebraic manipulation
Domain	Best for finite or partitioned sets	Best for infinite sets (e.g., all real numbers)
Complexity	Can be tedious with many cases	Requires identifying general patterns
Reliability	Absolute (if all cases are covered)	Absolute (if logic is sound)

5. Exam Strategy & Tips

Identify the Bounds: Always check if the question specifies a range (e.g., $1 \le n \le 5$ ). If a range is given, exhaustion is usually the intended method.
Show All Work: Examiners look for the explicit testing of every case. Do not skip values or use '...' unless the pattern is trivial and you have defined the boundaries clearly.
Check for Completeness: Ensure your cases cover the entire domain. If you split integers into 'positive' and 'negative', you have missed 'zero'.
Efficiency: Look for ways to minimize work. For instance, if proving something about prime numbers, you only need to test factors up to $\sqrt{n}$ .

6. Common Pitfalls & Misconceptions

The 'Few Examples' Trap: A common mistake is testing two or three values and assuming the statement is true for all. This is not a proof; it is merely an observation.
Overlapping Cases: While not logically fatal, overlapping cases lead to redundant work. Aim for mutually exclusive cases to keep the proof clean.
Infinite Domains: You cannot use simple exhaustion for an infinite set like 'all integers' unless you can group them into a finite number of categories (like even/odd) that cover the entire set.

Identify the Bounds: Always check if the question specifies a range (e.g., $1 \le n \le 5$ ). If a range is given, exhaustion is usually the intended method.
Show All Work: Examiners look for the explicit testing of every case. Do not skip values or use '...' unless the pattern is trivial and you have defined the boundaries clearly.
Check for Completeness: Ensure your cases cover the entire domain. If you split integers into 'positive' and 'negative', you have missed 'zero'.
Efficiency: Look for ways to minimize work. For instance, if proving something about prime numbers, you only need to test factors up to $\sqrt{n}$ .