Counterexamples

What you will get from this section. You will learn what a counterexample is, why a counterexample to an if-then statement must satisfy the if part, and how to find counterexamples to more complicated statements involving quantifiers and nested implications.

What is a counterexample?

A counterexample is an example that shows a general statement is false.

Many mathematical statements are claims about many things at once. For example:

This is really saying:

In symbols, this has the form

where $S$ is the set of square numbers. To disprove this kind of statement, we do not need to check every possible value of $n$. We only need to find one value of $n$ for which the statement fails. This means the overall statement is false, since it requires $P(n)$ to be true for all $n\in S$.

Here are some examples:

• To disprove: "All primes are odd", it is enough to find a prime that is not odd. In this case, $2$ is a counterexample, as it is a prime that is not odd.
• To disprove: "$x^2+4x+2$ is always positive", which is the same as $\forall x\in\mathbb{R},\, x^2+4x+2 > 0$. In this case, $x=-1$ is a counterexample, since $x^2+4x+2 = 1-4+2=-1$, which is not greater than $0$.
• To disprove: "Everyone loves horror movies", it is enough to find one person who does not love horror movies. That one person you found, who does not love horror movies, is a counterexample.

Technically, finding a counterexample is really the same as showing that the negation of the original statement is true. The original statement says "this works for every case"; the negation says "there exists at least one case where it does not work". Thus, if we are able to find a case where it does not work, this immediately proves that the negation is true. This case is called a counterexample.

Counterexamples to if-then statements

A common type of counterexample question asks us to find counterexamples to if-then statements. In the following examples, we will look carefully at both valid and invalid counterexamples.

Example 1: If $n$ can be written as a sum of two squares, then $n$ cannot be a cube.

Counterexample: $n=8=2^2+2^2$, therefore it belongs to the set of integers about which the statement is making a claim. But $n=8=2^3$, so it does not satisfy the claim. Hence, it is a valid counterexample.

Invalid counterexample: $n=27=3^3$ is not a valid counterexample, even though it is a cube. This is because it is not possible to write $27$ as a sum of two squares. The square numbers no bigger than $27$ are

and no two of these add to $27$. Therefore, it does not belong to the set of integers about which the statement is making a claim, so it is simply not involved with the statement and cannot serve as a counterexample.

In these if-then statements, the whole statement can often be interpreted as a "for all" statement: the conditions in the if part define the set being quantified over. So the if part is really describing some set of integers, numbers, or other objects that satisfy the if conditions. Thus, these statements can often be interpreted as "$\forall s \in S$, $P(s)$ is true". The if part is actually just a description of what is in $S$. Therefore, to be a valid counterexample, you must be a member of $S$ in the first place. This is the central concept tested in these problems.

Example 2: If a quadrilateral has all four sides equal, then it is a square.

Counterexample: a rhombus with angles $60^\circ, 120^\circ, 60^\circ, 120^\circ$. This works because the quadrilateral has all four sides equal, so the if part is true. It belongs to the set about which the statement is making a claim. But it is not a square, since its angles are not all $90^\circ$.

Invalid counterexample: a rectangle with side lengths $2$ and $3$. This is not a valid counterexample, because a $2$ by $3$ rectangle does not have all four sides equal. Therefore, it does not belong to the set about which the statement is making a claim, and so it is irrelevant to the statement and cannot serve as a counterexample.

Succinctly, we can summarise the situation for these if-then statements as follows: to serve as a counterexample, an object must first satisfy the if part, and then not satisfy the then part.

Example 3: If $n$ is a positive integer greater than $3$, then there exists a positive integer $m<n$ such that for every integer $r$ with $m<r<m+3$, $r$ is a positive factor of $n$.

Is $n=6$ a valid counterexample? It is true that $6$ is a positive integer greater than $3$, so it does satisfy the if part. Now suppose we try $m=2$. The integers $r$ satisfying $2<r<5$ are $3$ and $4$. But $r=4$ is not a positive factor of $6$, so this particular choice of $m$ fails.

Does this mean $n=6$ is a counterexample? No! It is not a counterexample because, for the then part of the statement to fail, we would have to show that every positive integer $m<n$ fails. In this case, all we have shown is that the claim fails for $m=2$. We have not shown that no valid value of $m$ can be found.

Indeed, $m=1$ works. The integers $r$ satisfying $1<r<4$ are $2$ and $3$, and both are positive factors of $6$. Therefore, $n=6$ is not a valid counterexample.

A valid counterexample is $n=9$. For the statement to be true for $n=9$, we would need to find a positive integer $m<n$ such that every integer $r$ with $m<r<m+3$ is a positive factor of $9$. In other words, $r=m+1$ and $r=m+2$ must both be positive factors of $9$.

This is impossible, since the positive factors of $9$ are $1,\ 3,\ 9$, and no two of them differ by $1$. Therefore, the then part of the statement fails for every positive integer $m<n$, and so $n=9$ is a valid counterexample.

Example 4: If $n$ is a multiple of $4$ greater than $4$, then for every integer $m$ with $2<m<n$, if $m$ is a factor of $n$, then $m$ is even.

Counterexample: $n=12$, with $m=3$.

This works because $12$ is a multiple of $4$ and $12>4$, so the outer if part is true. Also, $2<3<12$, and $3$ is a factor of $12$, so the inner if part is true. But $3$ is not even, so the inner then part is false.

Incorrect counterexample: $n=10$, with $m=5$.

This is not a counterexample, even though $5$ is a factor of $10$ and $5$ is not even. The problem is that $10$ is not a multiple of $4$, so the outer if part is false.

Incorrect counterexample: $n=12$, with $m=5$.

This is not a counterexample either. The number $12$ satisfies the outer if part, and $2<5<12$, but $5$ is not a factor of $12$. So the inner if part is false, and the inner implication has not been broken.

If-then counterexample summary

In general, we can view a valid counterexample as an $n$ that satisfies the if part, but for which the negation of the then part is true. The fact that $n$ satisfies the if part means it belongs to the set of objects that the statement is making a general claim about. The fact that the negation of the then part is true means that, for this relevant value of $n$, the general claim fails.

Summary

• A counterexample to a statement that makes a general claim about a set of objects is one object in that set for which the claim fails.
• To disprove $P \Rightarrow Q$, or if $P$ then $Q$, find a case where $P$ is true and $Q$ is false. This is a valid counterexample.