Proof by contradiction

What are proofs?

We use proofs to show that mathematical theorems are true beyond doubt. Similarly, we face theorems that we have to prove in automaton theory.

There are different types of proofs such as direct, indirect, deductive, inductive, divisibility proofs, and many others.

Indirect proof

Sometimes it'd not easy to prove something directly but easier to prove it indirectly. Indirect proofs work without formalizing the process. These proofs initiate by assuming the denial of the probable conclusion.

Proof by contradiction is a type of indirect proof.

Proof by contradiction

This proof works by assuming that the theorem is false. We prove through this theorem that the previous assumption leads to a contradiction or an incorrect result.

To prove a sentence $S$ by contradiction, we assume $¬S$ and derive a statement that we know is false already. This ultimately means that $S$ must be true.

To create this proof, we follow the steps below:

1. We assume a hypothesis and the negation of the conclusion.
2. Use the assumptions to derive new consequences until one of them is the opposite of the premise.
3. Conclude that the assumption is false and opposite; the original conclusion must be true.

Examples

Example 1

Proposition: For all integers $n$, if $n^3 + 5$ is odd, then $n$ is even.

Proof: Let $n$ be the integer and assume for the sake of contradiction that both $n$ and $n^3 + 5$ are odd.

To show that these are odd, let $j$ and $k$ exist such that $n=2j+1$ and $n^3 + 5 = 2k+1$.

The original equation is:

Substitute the value of $n$:

Expand $(2j+1)^3$:

Simplify the equation:

Divide both sides by 2:

Rearrange the equation:

Through this, we see that $5/2$is a noninteger rational number, while $k-4j^3 - 6j^2 -3j$is an integer part by the closure property for integers which is impossible.

Result: Thus, our assumption that when $n^3+5$ is odd, then $n$ is odd is false. Hence, $n$ must be even.

Example 2

Proposition: $\sqrt2$ is irrational.

Proof: To add contradiction, we will assume that $\sqrt2$ is rational.

Let $a$ and $b$ be two positive integers with no common factors. At least one of these is odd. Write the equation in terms of $a$ and $b$.

Take square on both sides:

Rearrange the equation:

Since it is a squared value, we will assume $a$ is even. We replace a by $2k$ since it is even.

The equation will become:

Expand the squared value:

Simplify:

This shows that $b$ is also even though we assumed that at least one of them would be odd. This is a contradiction of our assumption.

Result: Since the assumption was incorrect, $\sqrt2$ is not rational. $\sqrt2$ is irrational.