Proof by contradiction

• Proof by contradiction is used when it is hard to build the object directly or when the statement claims something cannot exist. The structure is: assume the negation of what you want to prove, then logically derive a contradiction, meaning you reach something impossible (like 1 = 0) or you violate a known fact or definition. Since the assumption leads to impossibility, it must be false, so the original statement is true. This method depends on having correct negations, especially with quantifiers and inequalities.
• The classic beginner example is proving sqrt(2) is irrational. You assume the opposite, that sqrt(2) = a/b in lowest terms, then algebra forces a and b to both be even, contradicting the assumption that the fraction was reduced. Contradictions often emerge from parity (even/odd), divisibility, ordering (smaller than smallest), or minimality (choosing a smallest counterexample). A good contradiction proof clearly marks the assumption, shows the chain of reasoning, and explicitly identifies the contradiction at the end.

• There is no smallest positive real number (assume s, then s/2 is smaller).

• 1Prove: sqrt(2) is irrational.
• 2Prove: There is no integer n such that n^2 = 2.

• 1Give the contrapositive of: If x is a multiple of 8, then x is divisible by 4.
• 2Prove or disprove: If n^2 is divisible by 3 then n is divisible by 3.

MCQ

Which proof method starts by assuming the negation and reaching a contradiction?