Classic Number-Theoretic Proofs by Contradiction

In proof by contradiction, the goal is to prove that a statement is true. To do this, we start by assuming the opposite of what we want to prove, which is the negation of the statement. This assumption is then used to derive a contradiction. If the negation leads to a contradiction, it must be false, so the original statement is true.

Proof by contradiction is particularly effective for statements that are difficult to prove directly, such as the irrationality of √2. The classic proof assumes that √2 is rational, then derives a contradiction by showing that this leads to a fraction that is not in lowest terms. The other statements are typically proven directly without contradiction.

To prove that √2 is irrational, we assume the negation of this statement, which is that √2 is rational. This means we assume √2 can be written as a fraction a/b in lowest terms, where a and b are integers with no common factors. This assumption is then used to derive a contradiction.

After assuming the negation of the statement, the next step is to logically derive consequences from this assumption. The goal is to reach a contradiction, such as a statement that is false or contradicts known facts. This contradiction shows that the assumption must be incorrect.

A contradiction is a statement that is always false, such as "2 = 3" or "a number is both even and odd." When we derive a contradiction from the assumption, it means that the assumption cannot be true. Therefore, the assumption (the negation of the original statement) is false, which implies that the original statement is true.

A contradiction is a statement that is false in all circumstances. A number cannot be both even and odd simultaneously, so this is a contradiction. The other statements are true or not always false (e.g., not all primes are odd, since 2 is even).

We want to prove that there are infinitely many primes. So, we assume the negation: that there are only finitely many primes. We then list these primes as p1, p2, ..., pn and consider the number N = p1 * p2 * ... * pn + 1. This leads to a contradiction because N is not divisible by any of the primes, so it must be prime or have a prime factor not in the list.

From √2 = a/b, we square both sides to get 2 = a^2 / b^2, so a^2 = 2b^2. This means a^2 is even, so a is even. Write a = 2k. Then 2b^2 = (2k)^2 = 4k^2, so b^2 = 2k^2, meaning b^2 is even, so b is even. But if a and b are both even, then a/b is not in lowest terms, contradicting the assumption. Thus, the initial assumption that √2 is rational must be false.

The sum of two rational numbers is usually proven directly: if a/b and c/d are rational, then a/b + c/d = (ad + bc)/(bd) is rational. The other statements are often proven by contradiction in elementary mathematics.

After assuming the negation and deriving a contradiction, we conclude that the negation cannot be true. Therefore, the original statement must be true. This is the final step of the proof.

We want to prove "if n^2 is even, then n is even." The negation of this implication is "n^2 is even and n is not even," i.e., n is odd. So, we assume n^2 is even and n is odd. Then, if n is odd, n^2 is odd, which contradicts n^2 being even. Thus, the assumption is false, and the original statement is true.

After assuming there are finitely many primes, we consider the number N = p1 * p2 * ... * pn + 1. This number is greater than 1 and is not divisible by any of the primes p1, p2, ..., pn because dividing by any pi leaves a remainder of 1. Therefore, N must be prime or have a prime factor not in the list, contradicting the assumption that we have all primes.

Proof by contradiction is versatile and can be used for various types of statements. For example, existential statements (e.g., "there exists an irrational number"), universal statements (e.g., "all primes are greater than 1"), and uniqueness statements (e.g., "there is only one even prime") can all be proven by contradiction.

The contradiction is a statement that is logically false, such as "0 = 1" or "P and not P." It may contradict the assumption or known facts, but ultimately, it must be false. This falsehood shows that the assumption leads to an impossibility.

The steps in order are: first, assume the negation of the statement; second, derive a contradiction from this assumption; and third, conclude that the original statement is true because the negation is false. Thus, the conclusion is the final step.