Direct Proofs

Recipe for a proof

The ingredients used in a proof include assumed simple facts (axioms), definitions of the objects (and operations) we are dealing with, hypotheses, rules of inference, and a pinch of insight. A proof is a sequence of mathematical statements, starting with a hypothesis or a known fact, and every $i$th statement is true given that all the $\left(i-1\right)$ statements preceding it are true. Normally, the last statement is the conclusion. Axioms, hypotheses, and definitions are considered true statements in proof. Otherwise, a statement is true if it is deducible from the previous statements according to the inference rules.

We can see the stated components in any existing proof. The famous question is how to cook new proofs. The notorious but correct answer to this question is no recipe exists for constructing a new proof. Then how do we do it? It is an art to develop new proofs, like creating a new painting or dish that no one has ever tasted. However, we can discuss famous practices and major categories of existing proofs. Let’s explore the categories, starting with direct proofs.

Direct proofs

Direct proofs are normally constructed to establish the truth value of a quantified conditional statement of the following type:

$$\forall x \left(P(x)\Rightarrow Q(x)\right).$$

Certainly, there is a domain for which the above statement is analyzed. It is assumed that all the domain members have the property $P$, and we write proof to conclude that every domain member has the property $Q$. Here $P(x)$ is the hypothesis, and $Q(x)$ is the conclusion. Usually, there are multiple hypotheses and facts to start with; in that case, $P$ is the conjunction of all. That is, if $P_1, P_2, P_3, \ldots, P_n$ are assumed true statements, then we can write $P$ as follows:

$$P(x) \equiv \left(P_1(x) \land P_2(x) \land P_3(x) \land \ldots \land P_n(x)\right).$$

Other than hypotheses, we use definitions and rules of inference to proceed toward the conclusion. Let’s look at a few examples to explore the typical structure of the direct proof.

Examples

Let’s assume the set of integers as the domain. An integer is even if it can be written as $2k$ for some integer $k$. An odd integer can be written as $2k+1$ for some integer $k$. Every integer is either even or odd. Let’s prove the following statement using the available information.

Theorem 1

If $x$ is an even integer, then $x^2$ is also even.

Proof

We have to show that $\forall x \left(E(x)\Rightarrow E(x^2)\right)$, where $E(x)$ means $x$ is even. We know that when the hypothesis of an implication is false, the implication is true. Therefore, the given statement is trivially true for all integers that are not even. Now, we only concentrate on even integers. Take an arbitrary even integer $y$. By definition, we can write $y=2k$ for some integer $k$. Squaring both sides, we get $y^2=(2k)^2.$ We can rewrite it as $y^2=2(2k^2)$. As $k$ is an integer so is $z=2k^2$. Because $y^2$ can be written as $2z$, it is even. We took $y$ as an arbitrary even integer. Therefore, by using universal generalization, we conclude that for every even integer, its square is also even. We have shown that the given statement is true for all integers, whether they are even or not. So, $\forall x \left(E(x)\Rightarrow E(x^2)\right)$ is true.

Theorem 2

If $x$ is an odd integer, then $x^2$ is also odd.

Proof

We have to show that $\forall x \left(O(x)\Rightarrow O(x^2)\right)$, where $O(x)$ means $x$ is odd. Take an arbitrary odd integer $y$. By definition, we can write $y=2k+1$ for some integer $k$. Squaring both sides, we get $y^2=(2k+1)^2.$ We can open up the square on the right side and rewrite it as $y^2=4k^2+4k+1$. As $k$ is an integer so is $z=2k^2+2k$. Because $y^2$ can be written as $2z+1$, it is odd. We took $y$ as an arbitrary odd integer. Therefore, by using universal generalization, we conclude that for every odd integer, its square is also odd. If $x$ is not odd, then the implication is vacuously true. We have shown that the given statement is true for all integers, whether odd or not. Therefore, $\forall x\left(O(x)\Rightarrow O(x^2)\right)$ is true.

Theorem 3

If $m$ is an odd integer, and $n$ is an even integer, then $mn$ is even.

Proof

We have to show that $\forall m \forall n\left(O(m)\land E(n)\Rightarrow E(mn)\right)$. Take an arbitrary odd integer $y$ and an arbitrary even integer $z$. By definition, we can write $y=2j+1$ and $z=2k$ for some integers $j$ and $k$. After multiplication, we get $yz=(2j+1)(2k).$ We can simplify the expression on the right side and rewrite it as $yz=4jk+2k$. As $j$ and $k$ are integers so is $p=(2jk+k)$. Because $yz$ can be written as $2p$, it is even. We took $y$ as an arbitrary odd integer and $z$ as an arbitrary even integer. So, by using universal generalization, we conclude that the product of any odd integer with an even integer is even. Therefore, $\forall m \forall n\left(O(m)\land E(n)\Rightarrow E(mn)\right)$ is true.