6.7: Proof by counterexample

Last updated
Save as PDF

Page ID: 88413

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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.