6.7: Proof by counterexample

Sometimes we want to prove that $P \not\Rightarrow Q\text{;}$ i.e. that $P \rightarrow Q$ is not a tautology.

Recall. The equivalence

$$\begin{equation*} P \rightarrow Q \Leftrightarrow (P \land C_1 \rightarrow Q) \land \cdots \land (P \land C_m \rightarrow Q) \end{equation*}$$

holds for any set of cases $C_1, C_2, \ldots, C_m$ such that $C_1 \lor \cdots \lor C_m$ is a tautology. (See Section 6.4.)

So if $P \land C_i \rightarrow Q$ is not a tautology for at least one $i\text{,}$ then $P \rightarrow Q$ also cannot be a tautology. Again, this also works in the universal case since $\forall$ distributes over $\land$ (Proposition 4.2.1).

Definition: Counterexample

relative to the logical implication $P \Rightarrow Q\text{,}$ a statement $C$ such that $P \land C \rightarrow Q$ is false

Example $\PageIndex{1}$

In Exercise 6.12.8, you are asked to prove the following statement by proving the contrapositive.

If $2^n - 1$ prime, then $n$ is prime.

Prove that the converse of this statement is false.

Solution

The converse statement is “If $n$ is prime, then $2^n - 1$ is prime.” But the case $n=11$ is a counterexample:

$$\begin{equation*} 2^{11} - 1 = 2047 = 23 \cdot 89 \end{equation*}$$

is not prime even though $n = 11$ is prime.

Check your understanding. Attempt Exercise 6.12.9.