Elementary Foundations: An introduction to topics in discrete mathematics

In mathematics, we often want to prove that some statement $P$ logically implies some other statement $Q\text{;}$ i.e. we want to prove that $P\Rightarrow Q$ or $(\mathrm{\forall }x)(P(x)\Rightarrow Q(x))\text{.}$ Note that the universal form covers the common statement “all $A$ are $B$”, since this can be rephrased “for all $x\text{,}$ if $x$ is $A$ then $x$ is $B$”.

Below are some common methods for proving $P\Rightarrow Q\text{.}$ In the universal case $(\mathrm{\forall }x)(P(x)\Rightarrow Q(x))\text{,}$ the domain of $x$ may be infinite, so we cannot prove $P(x)\Rightarrow Q(x)$ for each specific $x\text{,}$ one-by-one. Instead, we treat $x$ as a fixed but arbitrary object in the domain, and try to construct an argument proving $P(x)\Rightarrow Q(x)$ which does not depending on knowing the specific object $x\text{.}$ So all of the methods below can also be used in the universal case.

Since a conditional $P\to Q$ is true automatically when $P$ is false, it will be a tautology as long as we cannot have the case of $P$ true and $Q$ false at the same time. (See Figure 1.3.2.) Therefore, we (almost always) begin a proof by assuming that $P$ is true, and proceed to demonstrate that $Q$ must then also be true, based on that assumption.