Self-Assessment Quiz: Proof by Contradiction and Cases

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

A proof by contradiction of a statement $P$ proceeds by:

A) assuming $P$ and deriving $P$ again B) assuming $\neg P$ and deriving a statement of the form $q \land \neg q$ C) checking $P$ on many examples until convinced D) proving the contrapositive of $P$

Question 2

Proof by contradiction is logically valid because of:

A) De Morgan's laws B) the law of the excluded middle ($P$ is either true or false) C) mathematical induction D) the definition of a prime

Question 3

In the proof that $\sqrt 2$ is irrational, the contradiction is between:

A) "$p$ is even" and "$q$ is even" B) "$\frac{p}{q}$ is in lowest terms" and "$p$ and $q$ are both even" C) "$p^2 = 2q^2$" and "$\sqrt 2$ is rational" D) "$2$ is prime" and "$2$ is even"

Question 4

Why is the assumption "in lowest terms" essential to the $\sqrt 2$ proof?

A) It makes the algebra simpler. B) Without it, "both $p$ and $q$ are even" is not absurd, so there is no contradiction. C) It is required by the definition of irrational. D) It guarantees $q \ne 0$.

Question 5

In Euclid's proof of infinitely many primes, the manufactured number $N = p_1 p_2 \cdots p_k + 1$:

A) is always prime B) is always composite C) always has a prime factor not in the list $p_1, \dots, p_k$ D) is always even

Question 6

The smallest example where $N = p_1 \cdots p_k + 1$ is composite uses the first six primes: $2\cdot3\cdot5\cdot7\cdot11\cdot13 + 1 = 30031$. This number equals:

A) a prime B) $59 \times 509$ (both new primes) C) $30030 \times 1$ D) $173^2$

Question 7

To prove "no program can decide whether an arbitrary program halts," the contradiction proof:

A) builds a faster halting checker B) assumes a correct halts exists and feeds a program its own description to create a paradox C) tests every program up to a large size D) uses proof by cases on the program's length

Question 8

In the halting-problem argument, the assumption that the final contradiction destroys is:

A) that programs can loop forever B) that trouble calls itself C) that a correct, always-terminating halts(P, x) exists D) that Python is Turing-complete

Question 9 (True/False, justify)

True or false: In a proof by cases, the cases are allowed to overlap, but they must not leave any possibility uncovered. Justify in one sentence.

Question 10

The single non-negotiable obligation of a proof by cases — the one students most often forget — is:

A) that the cases are disjoint B) that the cases are exhaustive (cover every possibility) C) that there are exactly two cases D) that each case uses the same algebra

Question 11

"Without loss of generality, assume $a \le b$" is legitimate only when:

A) $a$ and $b$ are integers B) the roles of $a$ and $b$ are genuinely interchangeable in the statement C) $a$ is smaller than $b$ D) there are exactly two variables

Question 12 (True/False, justify)

True or false: In the claim "$m^n$ is positive whenever $m > 0$," you may write "WLOG, assume $m \le n$." Justify.

Question 13

A constructive existence proof differs from a non-constructive one in that the constructive proof:

A) is shorter B) exhibits an actual witness (or an algorithm to find one) C) uses contradiction D) works only for finite sets

Question 14

The §5.4 proof that there exist irrationals $a, b$ with $a^b$ rational is non-constructive because:

A) it uses no algebra B) at the end you still cannot say which pair $(a, b)$ works C) it is false D) $\sqrt 2$ is not actually irrational

Question 15

A uniqueness proof "$\exists! x\, P(x)$" requires you to show:

A) only that at most one $x$ works B) only that at least one $x$ works C) both: at least one $x$ exists, and any two that work are equal D) that infinitely many $x$ work

Question 16

"At most one solution exists" is vacuously true when:

A) exactly one solution exists B) two solutions exist C) zero solutions exist D) the solution is irrational

Question 17

How many counterexamples are needed to disprove "$\forall x\, P(x)$"?

A) all of them B) exactly one C) at least half D) it cannot be disproved

Question 18 (True/False, justify)

True or false: The claim "$n^2 + n + 41$ is prime for all $n \ge 0$" is false, and is disproved by $n = 40$. Justify by giving the value.

Question 19 (Short answer)

A test suite passes 10,000 random cases for a universal property. In one sentence, state exactly what this does and does not establish.

Question 20 (Short answer)

You are handed the claim "$X$ is irrational" (for some specific number $X$). Name the proof strategy you would reach for first, and state the one-word feature of the claim that points you there.

Answer Key

Topics to review by question