Indirect Proofs and Proofs by Contradiction

Concept: An indirect proof, also known as proof by contraposition, is a method of proving a statement by assuming the negation of the conclusion and showing that it leads to the negation of the hypothesis.
Form: To prove $∀n : (P(n) → Q(n))$ , instead of directly showing that $P(n)$ implies $Q(n)$ , we show that $¬Q(n)$ implies $¬P(n)$ .
Validity: This method is valid because the implication $P(n) → Q(n)$ is logically equivalent to its contrapositive $¬Q(n) → ¬P(n)$ .

Statement: If $n^2$ is divisible by 3, then $n$ is divisible by 3.
- $P(n)$ : $n$ is divisible by 3.
- $Q(n)$ : $n^2$ is divisible by 3.
Indirect Proof:
- Assume that $n$ is not divisible by 3.
- We want to show that this implies $n^2$ is not divisible by 3.
- Case 1: If $n$ is not divisible by 3, it leaves a remainder of 1 when divided by 3.
  - $n = 3k + 1$ for some integer $k$ .
  - Then, $n^2 = (3k + 1)^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$ .
  - Thus, $n^2$ is not divisible by 3, as it leaves a remainder of 1.
- Case 2: If $n$ is not divisible by 3, it leaves a remainder of 2 when divided by 3.
  - $n = 3k + 2$ for some integer $k$ .
  - Then, $n^2 = (3k + 2)^2 = 9k^2 + 12k + 4 = 9k^2 + 12k + 3 + 1 = 3(3k^2 + 4k + 1) + 1$ .
  - Thus, $n^2$ is not divisible by 3, as it leaves a remainder of 1.
- In both cases, if $n$ is not divisible by 3, then $n^2$ is not divisible by 3. This completes the indirect proof.

Concept: A proof by contradiction involves assuming the negation of the statement to be proven and showing that this assumption leads to a contradiction.
Method:
- Assume $¬P$ is true, where $P$ is the statement to be proven.
- Show that this assumption leads to a contradiction (a statement that is always false, denoted as $F$ ).
- Conclude that $P$ must be true.
Validity:
- The logical equivalence $\neg P → F$ implies $P$ is true.
- Truth table verification:
  | P | ¬P | F | ¬P → F | P |
  |---|----|---|--------|---|
  | T | F | F | T | T |
  | F | T | F | F | F |
- Since the columns for $P$ and $¬P → F$ are the same, the equivalence is verified.

Proof (by contradiction):
- Assume that $\sqrt{2}$ is rational. This is the negation of what we want to prove.
- If $\sqrt{2}$ is rational, then it can be written as $\sqrt{2} = \frac{a}{b}$ , where $a$ and $b$ are integers with no common factors, and $a$ and $b$ are positive.
- It follows that $a^2 = 2b^2$ .
- Since $b$ is an integer, $b^2$ is also an integer, so $a^2$ is even.
- If $a^2$ is even, then $a$ must be even. If $a$ were odd, then $a^2$ would also be odd.
- Since $a$ is even, we can write $a = 2k$ for some positive integer $k$ .
- By substitution, $(2k)^2 = 2b^2$ , which gives $4k^2 = 2b^2$ , and thus $b^2 = 2k^2$ .
- This tells us that $b^2$ is even. Using the same reasoning as before, $b$ must also be even.
- Now we have that both $a$ and $b$ are even, which contradicts our initial assumption that $a$ and $b$ have no common factors.
- Therefore, our assumption that $\sqrt{2}$ is rational must be false, and $\sqrt{2}$ is irrational.

Proof (by contradiction):
- Assume that there are finitely many primes: $p1, p2, p3, …, pn$ (where $p_n$ is the largest prime).
- Consider the number $q = p1 * p2 * p3 * … * pn + 1$ .
- $q$ is greater than $p_n$ (the largest prime).
- Note that if we divide $q$ by any of the primes $p_i$ , we get a remainder of 1.
- $q$ cannot be prime because it's greater than $p_n$ (the supposed largest prime).
- However, $q$ is not divisible by any of the primes $p1, p2, p3, …, pn$ , meaning it has no prime factors from that set.
- This contradicts the Fundamental Theorem of Arithmetic, which states that every integer greater than 1 can be represented uniquely as a product of prime numbers.
- Therefore, our assumption that there are finitely many primes must be false, and there are infinitely many primes.