Direct proof

The term direct proof is often used to denote the strategy of proving the statement $P\Rightarrow Q$ by first assuming that $P$ is true, then trying to derive the validity of $Q$. Let us see a simple example. For integers $a,b \in \mathbb{Z}$, we use the notation $a \mid b$ to denote the fact that $a$ divides $b$ (which is the same as saying $b = q \cdot a$ for some $q\in\mathbb{Z}$). We remark that this definition only concerns divisibility between two integers.

Example 6

We will show that, for all integers $a, b, c$, we have $a \mid b$ and $a \mid c$ implies $a \mid (b + c)$. Notice here $P \equiv (a\mid b) \land (a \mid c)$ and $Q \equiv a \mid (b + c)$. We first assume the validity of $P$, which says that $b = q_1a$ and $c = q_2a$. This would imply that $b + c = (q1 + q2)a$, or equivalently $a \mid (b + c)$.

Example 7

For all integers $x, x \mid 0$. To prove this statement, we can simply write $0 = 0 \cdot x$. According to this definition, we have $0 \mid 0$ but no other integer is divisible by $0$.

Example 8

For all integers $x, y, (x − y) \mid x^2 - y^2$ . This can also be done via a direct proof. We can write $(x^2 - y^2) = (x - y)(x + y)$. Notice that $(x + y) \in \mathbb{Z}$, so we have that $(x - y) | (x^2 - y^2)$ by definition.

In the above three examples, one can see that the statements we prove actually contain quantifiers. But in our proofs, we do not seem to be dealing with them at all. Do you know why? Try to convince yourself of this point before reading forward.