6.3: Direct Proof

Recall. The argument

$$\begin{equation*} A \rightarrow C_1, C_1 \rightarrow C_2, \dotsc, C_{m-1} \rightarrow C_m, C_m \rightarrow B \therefore A \rightarrow B \end{equation*}$$

is valid (Extended Law of Syllogism).

Procedure $\PageIndex{1}$: Direct proof.

• To prove $P \Rightarrow Q\text{,}$ start by assuming that $P$ is true. Then, through a sequence of (appropriately justified) intermediate conclusions, arrive at $Q$ as a final conclusion.
• To prove $(\forall x)(P(x) \Rightarrow Q(x))\text{,}$ start by assuming that $x$ is an arbitrary but unspecified element in the domain such that $P(x)$ is true. The first sentence in your argument should be: “Suppose $x$ is a such that $P(x)$”, where the blank is filled in by the definition of the domain of $x\text{.}$ Then, through a sequence of (appropriately justified) intermediate conclusions that do not depend on knowing the specific object $x$ in the domain, arrive at $Q(x)$ as a conclusion.

Example $\PageIndex{1}$

Prove: If $n$ is even, then $n^2$ even.

Solution

Let $P(n)$ represent the predicate “$n$ is even” and let $Q(n)$ represent the predicate “$n^2$ is even”, with domain the integers.

Suppose that $n$ is an arbitrary (but unspecified) integer such that $n$ is even. Then there exists an integer $m$ such that $n = 2m\text{,}$ and so $n^2 = 4m^2 = 2(2m)$ is even.

Check your understanding. Attempt Exercises 6.12.4–6.12.6.