Existence, Non-Existence, and Parity via Contradiction

The core of proof by contradiction is the derivation of a contradiction from the assumption of the negation. This method does not rely on direct proof but instead shows that the negation leads to an impossibility, thus proving the original statement.

The original statement is "if ab is even, then at least one of a or b is even." The negation is "ab is even and it is not true that at least one of a or b is even," which means "ab is even and both a and b are odd." We assume this and then derive a contradiction: if both a and b are odd, then ab is odd, but we have ab even, so contradiction.

We assume √2 = a/b where a and b are integers with no common factors. After deriving that both a and b are even, we have a contradiction because a/b is not in lowest terms, as both share a factor of 2. This contradicts the initial assumption.

Proof by contradiction is a valuable tool when direct proof is challenging or not straightforward. For example, proving irrationality or infinitude often uses contradiction. It is not always the best method, and it can be used for non-mathematical statements, but it always requires an assumption.

We want to prove that there is no smallest positive rational number. So, we assume the opposite: that there is a smallest positive rational number, say r. Then, we consider r/2, which is positive and rational but smaller than r, contradicting the minimality of r. Thus, the assumption is false.

The assumption in proof by contradiction is always the negation of the statement we wish to prove. This allows us to show that this negation leads to a contradiction, thereby establishing the truth of the original statement.

Logic is used to deduce logical consequences from the assumption of the negation. These deductions are step-by-step implications that eventually lead to a contradiction, which is essential for the proof.

The irrationality of √2 is a standard example proven by contradiction in elementary math. The other statements are typically proven by other methods (e.g., the Pythagorean theorem by geometric proof).

Once a contradiction is derived from the assumption, we reject the assumption because it leads to an impossibility. This rejection allows us to conclude that the original statement is true.

We want to prove that the product of two consecutive integers is even. The negation is that the product is odd. We assume this and note that if the product is odd, both integers must be odd. But consecutive integers cannot both be odd (since one must be even), so we have a contradiction.

After assuming finitely many primes, we form N = product of all primes + 1. N is not divisible by any prime in the list because it leaves a remainder of 1 when divided by any prime. This means N has a prime factor not in the list, contradicting the assumption that the list contains all primes.

Proof by contradiction is useful for statements where a direct proof is not obvious or is complex. For example, proving the irrationality of numbers or the infinitude of primes is often more straightforward by contradiction.

A contradiction must be a false statement. "2 = 3" is false, while the other options are true statements and cannot serve as contradictions.

The assumption is the negation of the true statement, so it is false. We temporarily assume it to show that it leads to a contradiction, confirming its falsity.

The proof that √2 is irrational is a classic example of proof by contradiction. We assume √2 is rational and derive a contradiction, showing that it must be irrational.