1. Assume the opposite of what we want to prove is true.
2. Do some math until a nonsensical statement arises, which disproves what we assumed to be true.
3. Conclude that the original thing we were asked to prove must be true.

Example: Prove by contradiction that there is no greatest integer

1. Assume the opposite/negation:

• Assume there exists a greatest integer $k$ .

2. Do some math and find a contradiction:

• Consider the integer $k + 1$. By definition, $k + 1 > k$.
• This contradicts the assumption that $k$ is the greatest integer.
• Therefore, there is no greatest integer.
• Must state: "a contradiction".

3. Conclude:

• There is no greatest integer.

Example: Prove by contradiction that if $n^2$ is odd, then $n$ is odd

• Assume there exists an odd integer $n^2$ such that $n$ is even.
• Let $n = 2a$.
• $n^2 = (2a)^2 = 4a^2 = 2(2a^2)$ which is a multiple of $2$ (even).
• This is a contradiction.
• Therefore, if $n^2$ is odd, then $n$ is odd.

Example: Prove by contradiction that if $n^3$ is even, then $n$ is even

• Assume there exists an odd $n$ such that $n^3$ is even.
• Let $n = 2m + 1$.
• $n^3 = (2m + 1)^3$
• $= (2m + 1)(2m + 1)(2m + 1) = (4m^2 + 4m + 1)(2m + 1)$
• $= 8m^3 + 4m^2 + 8m^2 + 4m + 2m + 1$
• $= 8m^3 + 12m^2 + 6m + 1$
• $= 2(4m^3 + 6m^2 + 3m) + 1$, which is of the form $2k + 1$ (odd).
• This is a contradiction.
• Therefore, if $n^3$ is even, then $n$ is even.

Example: Proof by Contradiction that $\sqrt{2}$ is Irrational

Reminder:

• A number is rational if it can be written in the form $\frac{a}{b}$, where a and b are integers with no common factors.

Part 1: Prove by contradiction that if $n^2$ is even, then $n$ is even.

1. Assume there exists an odd $n$ such that $n^2$ is even.
2. Let $n = 2m + 1$. Then $n^2 = (2m + 1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1$.
3. This expression is of the form $2k + 1$ (odd), which is a contradiction.
4. Therefore, if $n^2$ is even, then $n$ is even.

Part 2: Prove by contradiction that $\sqrt{2}$ is irrational.

1. Assume that $\sqrt{2}$ can be written as $\frac{a}{b}$, where a and b are integers with no common factors.

• Aiming to contradict this.

2. From $\sqrt{2} = \frac{a}{b}$:

• $\sqrt{2} = \frac{a}{b}$
• $\sqrt{2}b = a$
• Squaring both sides: $2b^2 = a^2$
• Therefore, $a^2$ must be even (since it is $2b^2$).

3. By the previous proof, if $a^2$ is even, then $a$ must be even.

• So, $a$ can be written in the form $a = 2n$.

1. Substituting $a = 2n$ into $a^2 = 2b^2$:

• $(2n)^2 = 2b^2$
• $4n^2 = 2b^2$
• Dividing both sides by $2$: $2n^2 = b^2$

4. By the previous proof, since $b^2$ is even, $b$ must also be even.
5. If $a$ and $b$ are both even, they share a common factor of $2$, which contradicts the assumption that $\frac{a}{b}$ is in simplest form (no common factors). Therefore, $\sqrt{2}$ is irrational.