Questions: Proving by Contradiction

Question 1

A student assumes ¬P, works through several steps, and derives a statement that is clearly false given the other facts of the problem — but does not derive a statement of the form Q ∧ ¬Q. Has the student completed a valid proof by contradiction?

• A. Yes — deriving any false statement from ¬P is sufficient to conclude ¬P is false
• B. Yes — the contradiction is implicit; a false conclusion demonstrates that ¬P cannot hold
• C. No — the proof is incomplete. A contradiction requires deriving Q ∧ ¬Q, a statement that is simultaneously true and false, not merely a false statement
• D. No — but only if the false statement was derived using an error in reasoning

Answer: (C)

This is the most common error in contradiction proofs. A 'false given other facts' is not the same as a logical contradiction. A contradiction must be of the form Q ∧ ¬Q — the exact same proposition asserted both true and false within the proof. If the student merely derived something that conflicts with background knowledge, the proof structure is incomplete: it hasn't yet shown that assuming ¬P alone creates an internal impossibility.

Question 2

For which of the following is proof by contradiction the most natural approach?

• A. Proving that the sum of two even numbers is even
• B. Proving that if n² is even then n is even
• C. Proving that there are infinitely many prime numbers
• D. Proving that (a+b)² = a² + 2ab + b²

Answer: (C)

Proving there are infinitely many primes is a classic non-constructive existence result — the direct approach (exhibiting infinitely many primes explicitly) is not feasible. Euclid's contradiction proof assumes there are finitely many primes, constructs their product plus one, and shows that number can't be divisible by any prime on the list — a contradiction. The sum of two evens (A) and algebraic identities (D) follow directly from definitions. That n² even implies n even (B) can be done by contrapositive. Contradiction is most powerful for negatives, irrationality claims, and non-constructive existence results.

Question 3

In a valid proof by contradiction of proposition P, the contradiction must arise specifically from the assumption of ¬P — deriving any false or absurd-looking statement is not sufficient.

• T. True
• F. False

Answer: True

The logical force of a contradiction proof comes from the assumption of ¬P causing the impossibility. If the contradiction arises from an unrelated error or from some other background assumption being wrong, it does not establish P. The structure requires: (assume ¬P) + (apply valid reasoning) + (other accepted truths) → Q ∧ ¬Q. The '¬P is the culprit' is what allows you to discharge the assumption and conclude P must hold.

Question 4

Proof by contradiction and proof by contrapositive are the same technique: both assume the negation of something and derive a contradiction.

• T. True
• F. False

Answer: False

These are distinct techniques. Proof by contrapositive proves 'P → Q' by directly proving '¬Q → ¬P' — a positive chain of reasoning from ¬Q to ¬P, with no contradiction involved. Proof by contradiction assumes ¬P (or assumes the entire proposition is false) and derives an explicit logical impossibility (Q ∧ ¬Q). Contrapositive is technically a direct proof of the contrapositive form; contradiction is an indirect proof that derives an impossibility. The structural difference matters when deciding which technique to use.

Question 5

What distinguishes a genuine logical contradiction from merely deriving a statement that is false in context, and why does the distinction matter for the validity of a contradiction proof?

Model answer: A genuine logical contradiction is a statement of the form Q ∧ ¬Q — the exact same proposition is simultaneously asserted true and false within the proof, regardless of any external context. A false-in-context statement is one that contradicts background knowledge or previous results, but is not self-negating. The distinction matters because the validity of reductio ad absurdum depends on the law of excluded middle: ¬P → (Q ∧ ¬Q) implies P, because Q ∧ ¬Q is an absolute impossibility. If instead ¬P merely implies something empirically false or contextually awkward, the logical engine fails — the impossibility might have another source, and we cannot conclude ¬P is the culprit.

Getting this distinction right is what separates a valid contradiction proof from a proof that only *looks* like one. Common error: a student derives '2 = 3' from ¬P and considers the proof complete, but '2 ≠ 3' is an external fact, not a logical negation of anything already in the proof. A cleaner contradiction would be: from ¬P, derive that some integer n is both even (2 | n) and odd (2 ∤ n). That is Q ∧ ¬Q, a self-contained logical impossibility.