Proof by Contraposition

A proof by contraposition is a method of proof that is logically equivalent to a direct proof but uses a different approach. In this method, you prove the contrapositive of a statement instead of proving the statement itself directly.

Contrapositive:

The contrapositive of an implication of the form $P \rightarrow Q$ (i.e., "If $P$, then $Q$") is the statement $\neg Q \rightarrow \neg P$ (i.e., "If not $Q$, then not $P$").

• Original statement: $P \rightarrow Q$ ("If $P$, then $Q$")
• Contrapositive: $\neg Q \rightarrow \neg P$ ("If not $Q$, then not $P$")

It turns out that a statement and its contrapositive are logically equivalent. This means that if you prove the contrapositive, you have also proven the original statement.

Steps in a Proof by Contraposition:

1. Restate the statement: Start with the original statement, typically of the form "If $P$, then $Q$".
2. Form the contrapositive: Write the contrapositive of the statement, which will be of the form "If not $Q$, then not $P$".
3. Prove the contrapositive: Prove the contrapositive directly, i.e., prove that $\neg Q$ implies $\neg P$.
4. Conclude the original statement: Since the contrapositive is logically equivalent to the original statement, proving the contrapositive proves the original statement.

Example of Proof by Contraposition:

Let's prove the following statement by contraposition:

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

Step 1: Restate the original statement

The original statement is:

"If $n^2$ is even, then $n$ is even."

This is in the form of an implication: $P \rightarrow Q$, where:

• $P$: $n^2$ is even.
• $Q$: $n$ is even.

Step 2: Form the contrapositive

The contrapositive of this statement is:

"If $n$ is not even (i.e., $n$ is odd), then $n^2$ is not even (i.e., $n^2$ is odd)."

This is equivalent to:

"If $n$ is odd, then $n^2$ is odd."

Step 3: Prove the contrapositive

Now, we prove the contrapositive: "If $n$ is odd, then $n^2$ is odd."

• If $n$ is odd, then by definition, $n = 2k + 1$, where $k$ is an integer.

• Squaring both sides of $n = 2k + 1$, we get:

  $$n^2 = (2k + 1)^2$$

  Expanding this:

  $$n^2 = 4k^2 + 4k + 1$$

  Notice that $4k^2 + 4k$ is an even number, because it is divisible by 2. Therefore, $n^2$ is of the form $2m + 1$, where $m$ is an integer, which means $n^2$ is odd.

Thus, we've shown that if $n$ is odd, then $n^2$ is odd.

Step 4: Conclude the original statement

Since we have proven the contrapositive, which is logically equivalent to the original statement, we can conclude that the original statement is true: "If $n^2$ is even, then $n$ is even."

General Structure of Proof by Contraposition:

1. State the original implication: $P \rightarrow Q$.
2. Write the contrapositive: $\neg Q \rightarrow \neg P$.
3. Prove the contrapositive: Show that $\neg Q$ implies $\neg P$.
4. Conclude that the original implication $P \rightarrow Q$ is true.

Why Use Contraposition?

• Simplicity: Sometimes proving the contrapositive is easier or more direct than proving the original statement.
• Logical equivalence: Since a statement and its contrapositive are logically equivalent, proving one is as good as proving the other.

If you need further help with specific examples or problems involving contraposition, feel free to ask!