$$\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}}$$

2.7: Counterexamples

$$\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}}$$

Counterexamples

Not all deductions are valid. To show that a particular deduction is not valid, you need to show that it is possible for its conclusion to be false at the same time that all of its hypotheses are true. To do this, you should find an assignment to the variables that makes all of the hypotheses true, but makes the conclusion false.

Exercise $$\PageIndex{1}$$

Show that the deduction $A \lor B, \quad A \Rightarrow B, \quad \therefore\ A$ is not valid.

Hint:

To make the conclusion false, we let $$A$$ be false. Then, to make the first hypothesis true, we must let $$B$$ be true. Fortunately, this also makes the second hypothesis true.

Solution

Let $$A$$ be false, and let $$B$$ be true. Then

$A \lor B = \mathsf{F} \lor \mathsf{T} = \mathsf{T}$

and $A \Rightarrow B = \mathsf{F} \Rightarrow \mathsf{T} = \mathsf{T},$

so both hypotheses of the deduction are true. However, the conclusion of the deduction (namely, $$A$$) is false.

Since we have a situation in which both hypotheses of the deduction are true, but the conclusion of the deduction is false, the deduction is not valid.

Any situation in which all of the hypotheses of a deduction are true, but the conclusion is false, is called a counter example to the deduction.

$\text{To show that a deduction is not valid, find a counterexample.}$

Exercise $$\PageIndex{2}$$

Show that each of these deductions is invalid, by finding a counterexample.

1. $$A \lor B$$, $$A \Rightarrow B$$
2. $$P \lor Q$$, $$P \& Q$$
3. $$A \Rightarrow (B \& C)$$, $$\lnot A \Rightarrow (B \lor C)$$, $$C$$
4. $$P \Rightarrow Q$$, $$\lnot P \Rightarrow R$$, $$Q \& (P \lor R)$$