Proof Techniques Flashcards

Which of the following best describes a 'non-constructive' existence proof?

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.

Prove or disprove: 'For all integers n, n² − n is even.' The correct conclusion is:

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.

Which rule of inference is: 'P ∨ Q, ¬P ⊢ Q'?

Answer: Disjunctive syllogism

Disjunctive syllogism eliminates one option in a disjunction when the other is known to be false.

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?

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.

Why is 'proof by example' invalid for universal statements?

Answer: Both A and C

A single example demonstrates existence but cannot rule out counterexamples; universal proofs require an argument covering every case.

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:

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'.

To prove: 'If x and y are both irrational, then x + y is irrational', a student attempts a direct proof. The attempt fails because:

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.