Counterexamples in Proof Techniques I

students, imagine someone says, “All swans are white,” or “Every even number is divisible by $4$.” One single example can break a universal statement. That is the power of a counterexample 🔍. In discrete mathematics, counterexamples are one of the fastest and clearest ways to test whether a claim is true. This lesson will help you understand what counterexamples are, how to find them, and how they fit into the larger toolbox of proof techniques.

Learning Goals

By the end of this lesson, students, you will be able to:

explain what a counterexample is and why it matters,
use counterexamples to show that a statement is false,
connect counterexamples to proof techniques like direct proof, contrapositive, and contradiction,
recognize when a single example is enough to disprove a claim,
apply counterexample thinking to statements about numbers, sets, and functions.

What Is a Counterexample?

A counterexample is a specific example that shows a general statement is false. It works when a statement claims that something is true for every object in a set, but you find just one object for which the statement fails.

For example, consider the statement:

$$\text{For every integer } n,\ n^2 \ge n.$$

To test this, try a few values:

if $n=0$, then $0^2=0$ and $0\ge 0$ is true,
if $n=1$, then $1^2=1$ and $1\ge 1$ is true,
if $n=2$, then $2^2=4$ and $4\ge 2$ is true.

So far, it looks true. But if we try $n=\tfrac{1}{2}$, then $\left(\tfrac{1}{2}\right)^2=\tfrac{1}{4}$ and $\tfrac{1}{4}\ge \tfrac{1}{2}$ is false. That is a counterexample, so the statement is false for all real numbers.

In discrete mathematics, we usually care about integers, sets, graphs, logic statements, and functions. Counterexamples help us quickly check whether a universal claim is actually valid ✅.

Why Counterexamples Matter

Counterexamples are important because they save time and prevent mistakes. In mathematics, a statement can sound convincing but still be false. A proof must work for every case, not just several examples.

A counterexample is especially useful for statements with words like:

“all,”
“every,”
“for any,”
“for all.”

If a statement has one of these words, then one failure is enough to disprove it.

For example:

$$\text{All prime numbers are odd.}$$

This sounds plausible if you think about $3$, $5$, $7$, and $11$. But $2$ is a prime number and it is even. So $2$ is a counterexample, and the statement is false.

This is a key idea in reasoning: to prove a universal statement, you need a general argument; to disprove it, one counterexample is enough.

How to Find a Counterexample

Finding a counterexample is often a search process. students, you usually begin by identifying the kind of object the statement talks about, then you try “edge cases” or unusual cases.

Here are some useful strategies:

1. Try small values

Small numbers often reveal errors quickly.

Example:

$$\text{For every integer } n,\ n^2 > n.$$

Try $n=0$:

$$0^2>0 \quad \Rightarrow \quad 0>0,$$

which is false. So $0$ is a counterexample.

2. Try boundary values

If a statement involves inequalities, zeros, negatives, or smallest elements, test those first.

Example:

$$\text{If } a>b,\text{ then } a^2>b^2.$$

This is false. Take $a=-1$ and $b=-2$. Then $-1>-2$, but

$$(-1)^2=1 \quad \text{and} \quad (-2)^2=4,$$

so $1>4$ is false. Thus $a=-1$ and $b=-2$ form a counterexample.

3. Look for special structures

Sometimes a statement seems true for common cases but fails for special ones, like odd numbers, negative numbers, or empty sets.

Example:

$$\text{The sum of two odd integers is odd.}$$

This is false because if $3$ and $5$ are odd, then $3+5=8$, and $8$ is even. So $3$ and $5$ are a counterexample pair.

Counterexamples in Logic Statements

Counterexamples are especially common in logic because many mathematical claims are universal statements.

A statement like

$$\forall x\in S,\ P(x)$$

means “for every $x$ in $S$, the property $P(x)$ is true.” To disprove it, you only need one $x$ in $S$ such that $P(x)$ is false.

Example:

$$\forall n\in\mathbb{Z},\ n^2+n+41\text{ is prime}.$$

This famous-looking expression is not always prime. Try $n=40$:

$$40^2+40+41=1600+40+41=1681=41^2,$$

which is not prime. So $n=40$ is a counterexample.

Notice something important: a statement can be true for many values and still be false overall. Counterexamples check the full range, not just a sample.

Counterexamples and Proof Techniques

Counterexamples are not proofs of truth; they are tools for disproving false statements. They fit into Proof Techniques I by helping you understand the difference between proving and disproving.

Direct proof

A direct proof shows a statement is true by starting from known facts and logically reaching the conclusion.

Contrapositive

If the statement has the form

$$P\rightarrow Q,$$

you can prove it by proving the contrapositive:

$$\neg Q\rightarrow \neg P.$$

Contradiction

A contradiction proof assumes the statement is false and shows that this leads to an impossible result.

Counterexample

A counterexample does the opposite of proof: it shows a statement is false by giving one specific failure.

So, students, the connection is this: direct proof, contrapositive, and contradiction are methods for proving statements, while counterexamples are a method for disproving universal statements. Together, they form a foundation for mathematical reasoning.

Worked Examples

Let’s practice with several examples.

Example 1: A claim about integers

Statement:

$$\text{For every integer } n,\ n^2\text{ is even.}$$

Counterexample: $n=1$.

Then

$$1^2=1,$$

which is odd. So the statement is false.

Example 2: A claim about prime numbers

Statement:

$$\text{Every number of the form } 2^n-1 \text{ is prime.}$$

Check $n=4$:

$$2^4-1=16-1=15,$$

and $15$ is not prime. So $n=4$ is a counterexample.

Example 3: A claim about sets

Statement:

$$A\subseteq B \Rightarrow |A|<|B|.$$

This says every subset has smaller size than the whole set. But if $A=B$, then $A\subseteq B$ is true and $|A|<|B|$ is false. For instance, let $A=B=\{1,2\}$. So this is a counterexample.

Example 4: A claim about functions

Statement:

$$\text{Every function is one-to-one.}$$

This is false. Consider the function

$$f(x)=x^2.$$

Then

$$f(2)=4 \quad \text{and} \quad f(-2)=4,$$

so different inputs give the same output. This is a counterexample to the claim that every function is one-to-one.

Common Mistakes to Avoid

students, counterexamples are powerful, but students sometimes make these mistakes:

Using an example that does not match the statement’s domain. If a claim is about integers, a fraction is not a valid counterexample.
Showing only that a statement is hard to prove. Hard to prove does not mean false.
Using a non-example instead of a counterexample. A counterexample must directly violate the claim.
Confusing one example with a proof. One example cannot prove a universal statement true.

A useful reminder is:

$$\text{One example can disprove a universal statement, but many examples cannot prove it.}$$

How Counterexamples Fit the Bigger Picture

In Proof Techniques I, the main goal is to reason carefully and correctly. Counterexamples sharpen your thinking because they force you to ask:

What exactly does the statement claim?
What is the domain?
Is it a universal statement?
Can one failure be enough to disprove it?

This habit is valuable in math and in everyday life. If someone says, “All buses are late,” you only need one bus that arrives on time to show the claim is false. That is the same logic used in mathematics 🚌.

Counterexamples also help you improve proofs. If you think a statement is true, trying to find a counterexample can reveal hidden exceptions before you write a proof.

Conclusion

Counterexamples are one of the simplest and most useful ideas in discrete mathematics. students, when a statement claims that something is true for every case, a single failure is enough to show that the statement is false. Counterexamples help you test ideas, catch errors, and understand the difference between proving and disproving. They connect directly to the larger proof techniques of direct proof, contrapositive, and contradiction by showing the opposite side of mathematical reasoning. In short, counterexamples are a fast and reliable way to challenge universal claims and build stronger mathematical thinking.

Study Notes

A counterexample is a specific example that shows a general statement is false.
Counterexamples are used to disprove statements with words like $\text{all}$, $\text{every}$, and $\text{for all}$.
To disprove a universal statement, only one counterexample is needed.
To prove a universal statement, many examples are not enough; a general proof is required.
Helpful ways to find counterexamples include testing small values, boundary cases, and special cases.
Counterexamples fit into Proof Techniques I as the main tool for disproving false statements.
Direct proof, contrapositive, and contradiction are proof methods; counterexamples are a disproof method.
Always check the domain carefully so your counterexample is valid.
A statement can be true in many cases and still be false overall.
Counterexamples are useful in numbers, sets, functions, and logic statements.