Proof by Implication

Proof by Implication

Proof by Implication (or Direct Proof of Implication) is a method used to prove a logical implication of the form:

$$P \implies Q$$

where $P$ and $Q$ are statements, and the goal is to prove that if $P$ is true, then $Q$ must also be true.

The structure of the implication $P \implies Q$ is:

• $P$ is called the hypothesis or antecedent.
• $Q$ is called the conclusion or consequent.

Steps in a Proof by Implication

1. Assume the Hypothesis is True:

   • Start by assuming that the hypothesis $P$ is true. This is the foundation of a proof by implication because we are trying to show that if $P$ holds, then $Q$ must follow.

2. Derive the Conclusion:

   • From the assumption that $P$ is true, you logically deduce that $Q$ must also be true. This is done through valid logical steps, such as using known theorems, definitions, or rules of inference.

3. Conclude the Proof:

   • Once you've established that $Q$ follows from the assumption of $P$, you can conclude that the implication $P \implies Q$ is true.

---

Example of Proof by Implication

Example 1: Prove that if $n$ is an even integer, then $n^2$ is even.

We need to prove that if $n$ is even, $n^2$ is also even. The implication we are trying to prove is:

$$\text{If } n \text{ is even, then } n^2 \text{ is even.}$$

Step 1: Assume the Hypothesis is True

• Assume $n$ is even. By the definition of an even integer, this means that there exists an integer $k$ such that:

$$n = 2k$$

Step 2: Derive the Conclusion

• We need to prove that $n^2$ is even. Starting with the assumption $n = 2k$, we calculate $n^2$:

$$n^2 = (2k)^2 = 4k^2$$

• Notice that $4k^2$ is clearly divisible by 2 (since $4k^2 = 2 \cdot (2k^2)$, and it is of the form $2m$, where $m$ is an integer). Therefore, $n^2$ is even.

Step 3: Conclusion

• Since we have shown that $n^2$ is even when $n$ is even, we conclude that if $n$ is even, then $n^2$ is even.

Thus, the implication $P \implies Q$ is proven: If $n$ is even, then $n^2$ is even.

---

Example 2: Prove that if a number $n$ is divisible by 4, then $n$ is divisible by 2.

We need to prove the following implication:

$$\text{If } n \text{ is divisible by 4, then } n \text{ is divisible by 2.}$$

Step 1: Assume the Hypothesis is True

• Assume that $n$ is divisible by 4. By the definition of divisibility, there exists an integer $k$ such that:

$$n = 4k$$

Step 2: Derive the Conclusion

• We need to prove that $n$ is divisible by 2. Since $n = 4k$, we can rewrite $n$ as:

$$n = 2(2k)$$

• This shows that $n$ is of the form $2m$, where $m = 2k$ is an integer. Therefore, $n$ is divisible by 2.

Step 3: Conclusion

• Since we have shown that $n$ is divisible by 2 when $n$ is divisible by 4, we conclude that if $n$ is divisible by 4, then $n$ is divisible by 2.

Thus, the implication $P \implies Q$ is proven: If $n$ is divisible by 4, then $n$ is divisible by 2.

---

Key Points to Remember in Proof by Implication

1. Start with the assumption that the hypothesis is true: This is essential because in a proof of implication, you prove the conclusion by assuming that the hypothesis holds.

2. Focus on deriving the conclusion: Use logical reasoning and known facts to show that the conclusion necessarily follows from the assumption.

3. The structure of an implication: The structure of an implication is $P \implies Q$, and you must prove that if $P$ is true, then $Q$ must also be true. If you successfully show this, the implication is true.

4. No need to prove the converse: In a proof by implication, you are only proving that $P \implies Q$ holds; you do not need to prove the converse (that $Q \implies P$) unless asked.

---

Conclusion

Proof by implication is a powerful technique used to establish the truth of statements of the form "If $P$, then $Q$." The proof involves assuming that $P$ is true and showing that this assumption leads logically to $Q$. By proving this, you have proven the truth of the implication $P \implies Q$. This method is commonly used in mathematics and logic when dealing with conditional statements.