TMUA Proof Techniques 5 — Questions and Answers
Question 1: Which of the following best describes a 'non-constructive' existence proof?
- It exhibits a specific object satisfying the property
- It proves existence without identifying the object explicitly (Correct answer)
- It uses induction to build the object step by step
- It checks all cases in a finite domain
Correct answer: It proves existence without identifying the object explicitly
A non-constructive proof establishes that something must exist (e.g. via contradiction) without providing an explicit example.
Question 2: Prove or disprove: 'For all integers n, n² − n is even.' The correct conclusion is:
- False; n=3 gives 6, which is odd
- True; n² − n = n(n−1) is a product of consecutive integers (Correct answer)
- False; n=2 gives 2, not even
- True; all squares are even
Correct answer: True; n² − n = n(n−1) is a product of consecutive integers
n(n−1) is a product of consecutive integers, so one factor is always even, making the product even.
Question 3: Which rule of inference is: 'P ∨ Q, ¬P ⊢ Q'?
- Modus ponens
- Modus tollens
- Disjunctive syllogism (Correct answer)
- Hypothetical syllogism
Correct answer: Disjunctive syllogism
Disjunctive syllogism eliminates one option in a disjunction when the other is known to be false.
Question 4: In a proof by cases for an integer n, the usual split is n ≡ 0 (mod 2) and n ≡ 1 (mod 2). What guarantees these two cases are exhaustive?
- The well-ordering principle
- Every integer is either even or odd (the division algorithm) (Correct answer)
- The fundamental theorem of arithmetic
- De Morgan's laws
Correct answer: Every integer is either even or odd (the division algorithm)
The division algorithm guarantees every integer has remainder 0 or 1 when divided by 2, covering all possibilities.
Question 5: Why is 'proof by example' invalid for universal statements?
- Examples are too specific to generalise without additional argument
- Examples can only be used in constructive proofs
- Examples are allowed only in existence proofs
- Both A and C (Correct answer)
Correct answer: Both A and C
A single example demonstrates existence but cannot rule out counterexamples; universal proofs require an argument covering every case.
Question 6: A student claims: 'Since 2+3=5 (prime), 4+3=7 (prime), and 6+3=9 is not prime, the pattern breaks.' This is an example of:
- A valid proof by induction
- A counterexample disproving a conjecture (Correct answer)
- A proof by contradiction
- A proof by contrapositive
Correct answer: A counterexample disproving a conjecture
Finding 6+3=9 which is not prime provides a counterexample that disproves the conjecture that 'even + 3 is always prime'.
Question 7: To prove: 'If x and y are both irrational, then x + y is irrational', a student attempts a direct proof. The attempt fails because:
- Irrational numbers cannot be added
- The sum of two irrationals can be rational, e.g. √2 + (−√2) = 0 (Correct answer)
- Direct proofs never apply to irrationals
- The statement is true and the proof should succeed
Correct answer: The sum of two irrationals can be rational, e.g. √2 + (−√2) = 0
√2 + (−√2) = 0 ∈ ℚ is a counterexample showing the statement is false, so no valid proof exists.
TMUA Proof Techniques 5
Which of the following best describes a 'non-constructive' existence proof?