Hard A-Level Proof by contradiction Questions

Challenging, exam-style A-Level Proof by contradiction questions with worked solutions. Stretch yourself on the hardest primes, euclid, counterexample, rationals problems.

primeseuclidcounterexamplerationalscontradictionnumber-theory
A-Level34 questionsStep-by-step solutions
Question 1
8 markschallenging
Which sequence correctly outlines a proof by contradiction?
Show worked solution

Worked solution

  1. Recall a direct proof

    assume P, deduce Q\text{assume}\ P,\ \text{deduce}\ Q

    A direct proof reasons forward from the hypothesis.

  2. Recall a proof by contradiction

    assume ¬Q, derive P∧¬P\text{assume}\ \lnot Q,\ \text{derive}\ P\wedge\lnot P

    A contradiction proof assumes the negation and reaches an impossibility.

  3. Compare the two approaches

    contradiction targets an impossibility\text{contradiction targets an impossibility}

    The defining feature is the impossibility that is reached.

  4. Work only with consequences of the assumption

    each line follows from the assumption\text{each line follows from the assumption}

    Nothing outside the assumption may be used until the contradiction appears.

  5. Look for a statement of the form P and not P

    P∧¬PP\wedge\lnot P

    A contradiction is any pair of statements that cannot both be true.

  6. Confirm no algebraic slip was made

    re-check each deduction\text{re-check each deduction}

    The contradiction must come from the assumption, not from an error.

  7. Deduce that the assumption cannot hold

    ⇒ assumption is false\Rightarrow\ \text{assumption is false}

    Because it leads to a contradiction, the assumption is impossible.

  8. Invoke the law of the excluded middle

    P∨¬PP\vee\lnot P

    A statement is either true or false, so rejecting the negation proves the claim.

  9. Record the number sets involved

    a,b∈Z, b≠0a,b\in\mathbb{Z},\ b\neq 0

    Being explicit about the sets keeps each deduction valid.

  10. Note the key definition being used

    apply the relevant definition\text{apply the relevant definition}

    The definition of the objects underpins the whole argument.

  11. Summarise the chain of reasoning

    assumption⇒⋯⇒contradiction\text{assumption}\Rightarrow\cdots\Rightarrow\text{contradiction}

    The argument links the assumption directly to an impossibility.

  12. Verify the contradiction is genuine

    contradiction confirmed\text{contradiction confirmed}

    A real contradiction, not an unproved claim, is required to finish.

  13. Restate the established result

    claim now proved\text{claim now proved}

    We restate what has been shown for clarity.

  14. Reflect on why the method succeeds

    eliminating false leaves true\text{eliminating false leaves true}

    Ruling out the only alternative establishes the original statement.

  15. State the defining feature

    assume the negation, then reach a contradiction\text{assume the negation, then reach a contradiction}

    This is what distinguishes proof by contradiction.

Answer
Assume ¬P\lnot P; derive a statement and its negation; conclude PP
Question 2
8 markschallenging
What is the correct negation of “there exists a smallest positive rational”?
Show worked solution

Worked solution

  1. Write the statement to be disproved

    ∃ a smallest positive rational\exists\ \text{a smallest positive rational}

    A proof by contradiction assumes this statement is false.

  2. Form its exact logical negation

    take the opposite, covering every other case\text{take the opposite, covering every other case}

    The negation must be precise or the proof is invalid.

  3. Check the negation covers all other cases

    the negation must be complete\text{the negation must be complete}

    An imprecise negation would prove the wrong statement.

  4. Work only with consequences of the assumption

    each line follows from the assumption\text{each line follows from the assumption}

    Nothing outside the assumption may be used until the contradiction appears.

  5. Look for a statement of the form P and not P

    P∧¬PP\wedge\lnot P

    A contradiction is any pair of statements that cannot both be true.

  6. Confirm no algebraic slip was made

    re-check each deduction\text{re-check each deduction}

    The contradiction must come from the assumption, not from an error.

  7. Deduce that the assumption cannot hold

    ⇒ assumption is false\Rightarrow\ \text{assumption is false}

    Because it leads to a contradiction, the assumption is impossible.

  8. Invoke the law of the excluded middle

    P∨¬PP\vee\lnot P

    A statement is either true or false, so rejecting the negation proves the claim.

  9. Record the number sets involved

    a,b∈Z, b≠0a,b\in\mathbb{Z},\ b\neq 0

    Being explicit about the sets keeps each deduction valid.

  10. Note the key definition being used

    apply the relevant definition\text{apply the relevant definition}

    The definition of the objects underpins the whole argument.

  11. Summarise the chain of reasoning

    assumption⇒⋯⇒contradiction\text{assumption}\Rightarrow\cdots\Rightarrow\text{contradiction}

    The argument links the assumption directly to an impossibility.

  12. Verify the contradiction is genuine

    contradiction confirmed\text{contradiction confirmed}

    A real contradiction, not an unproved claim, is required to finish.

  13. Restate the established result

    claim now proved\text{claim now proved}

    We restate what has been shown for clarity.

  14. Reflect on why the method succeeds

    eliminating false leaves true\text{eliminating false leaves true}

    Ruling out the only alternative establishes the original statement.

  15. State the assumption that opens the proof

    ∀ q>0 ∃ q′ with 0<q′<q\forall\ q>0\ \exists\ q'\ \text{with}\ 0<q'<q

    We assume this and work towards a contradiction.

Answer
For every positive rational there is a smaller positive rational
Question 3
8 markschallenging
Suppose q=mnq=\frac{m}{n} is assumed to be the smallest positive rational. Which value forces the contradiction?
Show worked solution

Worked solution

  1. State the claim

    there is no smallest positive rational\text{there is no smallest positive rational}

    We show no positive rational can be least.

  2. Assume the opposite

    let q be the smallest positive rational\text{let}\ q\ \text{be the smallest positive rational}

    Suppose such a least value exists.

  3. Note q is positive and rational

    q>0, q∈Qq>0,\ q\in\mathbb{Q}

    These are the assumed properties of q.

  4. Halve it

    q2\frac{q}{2}

    Consider half of q.

  5. The half is rational

    q2∈Q\frac{q}{2}\in\mathbb{Q}

    Half of a rational is rational.

  6. The half is positive

    q2>0\frac{q}{2}>0

    Half of a positive number is positive.

  7. The half is smaller than q

    0<q2<q0<\frac{q}{2}<q

    So a smaller positive rational exists.

  8. This contradicts q being smallest

    contradiction\text{contradiction}

    q was assumed to be the least positive rational.

  9. Record the number sets involved

    a,b∈Z, b≠0a,b\in\mathbb{Z},\ b\neq 0

    Being explicit about the sets keeps each deduction valid.

  10. Note the key definition being used

    apply the relevant definition\text{apply the relevant definition}

    The definition of the objects underpins the whole argument.

  11. Summarise the chain of reasoning

    assumption⇒⋯⇒contradiction\text{assumption}\Rightarrow\cdots\Rightarrow\text{contradiction}

    The argument links the assumption directly to an impossibility.

  12. Verify the contradiction is genuine

    contradiction confirmed\text{contradiction confirmed}

    A real contradiction, not an unproved claim, is required to finish.

  13. Restate the established result

    claim now proved\text{claim now proved}

    We restate what has been shown for clarity.

  14. Reflect on why the method succeeds

    eliminating false leaves true\text{eliminating false leaves true}

    Ruling out the only alternative establishes the original statement.

  15. Conclude the claim

    no smallest positive rational exists\text{no smallest positive rational exists}

    The assumption of a least value is impossible.

Answer
m2n\frac{m}{2n}, a smaller positive rational
Question 4
8 markschallenging
Which is a correct start to proving log⁡25\log_2 5 is irrational, leading to a parity contradiction?
Show worked solution

Worked solution

  1. State the claim

    log⁡25 is irrational\log_{2}5\ \text{is irrational}

    We show it is not a ratio of integers.

  2. Assume the opposite

    log⁡25=pq\log_{2}5=\frac{p}{q}

    Suppose it equals a fraction with positive integers p and q.

  3. Rewrite in exponential form

    2p/q=52^{p/q}=5

    Undo the logarithm.

  4. Raise both sides to the power q

    2p=5q2^{p}=5^{q}

    Remove the fractional exponent.

  5. Compare parity of the two sides

    2p is even, 5q is odd2^{p}\ \text{is even},\ 5^{q}\ \text{is odd}

    An even number cannot equal an odd number.

  6. Confirm no algebraic slip was made

    re-check each deduction\text{re-check each deduction}

    The contradiction must come from the assumption, not from an error.

  7. Deduce that the assumption cannot hold

    ⇒ assumption is false\Rightarrow\ \text{assumption is false}

    Because it leads to a contradiction, the assumption is impossible.

  8. Invoke the law of the excluded middle

    P∨¬PP\vee\lnot P

    A statement is either true or false, so rejecting the negation proves the claim.

  9. Record the number sets involved

    a,b∈Z, b≠0a,b\in\mathbb{Z},\ b\neq 0

    Being explicit about the sets keeps each deduction valid.

  10. Note the key definition being used

    apply the relevant definition\text{apply the relevant definition}

    The definition of the objects underpins the whole argument.

  11. Summarise the chain of reasoning

    assumption⇒⋯⇒contradiction\text{assumption}\Rightarrow\cdots\Rightarrow\text{contradiction}

    The argument links the assumption directly to an impossibility.

  12. Verify the contradiction is genuine

    contradiction confirmed\text{contradiction confirmed}

    A real contradiction, not an unproved claim, is required to finish.

  13. Restate the established result

    claim now proved\text{claim now proved}

    We restate what has been shown for clarity.

  14. Reflect on why the method succeeds

    eliminating false leaves true\text{eliminating false leaves true}

    Ruling out the only alternative establishes the original statement.

  15. Conclude the claim

    log⁡25 is irrational\log_{2}5\ \text{is irrational}

    The parity contradiction refutes the assumption.

Answer
Assume log⁡25=pq\log_2 5=\frac{p}{q}, so 2p=5q2^{p}=5^{q}
Question 5
8 markschallenging
Which statement correctly matches proofs to their method?
Show worked solution

Worked solution

  1. Recall a direct proof

    assume P, deduce Q\text{assume}\ P,\ \text{deduce}\ Q

    A direct proof reasons forward from the hypothesis.

  2. Recall a proof by contradiction

    assume ¬Q, derive P∧¬P\text{assume}\ \lnot Q,\ \text{derive}\ P\wedge\lnot P

    A contradiction proof assumes the negation and reaches an impossibility.

  3. Compare the two approaches

    contradiction targets an impossibility\text{contradiction targets an impossibility}

    The defining feature is the impossibility that is reached.

  4. Work only with consequences of the assumption

    each line follows from the assumption\text{each line follows from the assumption}

    Nothing outside the assumption may be used until the contradiction appears.

  5. Look for a statement of the form P and not P

    P∧¬PP\wedge\lnot P

    A contradiction is any pair of statements that cannot both be true.

  6. Confirm no algebraic slip was made

    re-check each deduction\text{re-check each deduction}

    The contradiction must come from the assumption, not from an error.

  7. Deduce that the assumption cannot hold

    ⇒ assumption is false\Rightarrow\ \text{assumption is false}

    Because it leads to a contradiction, the assumption is impossible.

  8. Invoke the law of the excluded middle

    P∨¬PP\vee\lnot P

    A statement is either true or false, so rejecting the negation proves the claim.

  9. Record the number sets involved

    a,b∈Z, b≠0a,b\in\mathbb{Z},\ b\neq 0

    Being explicit about the sets keeps each deduction valid.

  10. Note the key definition being used

    apply the relevant definition\text{apply the relevant definition}

    The definition of the objects underpins the whole argument.

  11. Summarise the chain of reasoning

    assumption⇒⋯⇒contradiction\text{assumption}\Rightarrow\cdots\Rightarrow\text{contradiction}

    The argument links the assumption directly to an impossibility.

  12. Verify the contradiction is genuine

    contradiction confirmed\text{contradiction confirmed}

    A real contradiction, not an unproved claim, is required to finish.

  13. Restate the established result

    claim now proved\text{claim now proved}

    We restate what has been shown for clarity.

  14. Reflect on why the method succeeds

    eliminating false leaves true\text{eliminating false leaves true}

    Ruling out the only alternative establishes the original statement.

  15. State the defining feature

    assume the negation, then reach a contradiction\text{assume the negation, then reach a contradiction}

    This is what distinguishes proof by contradiction.

Answer
The infinitude of primes and the irrationality of 2\sqrt{2} are both proved by contradiction

Unlock 29 more Proof by contradiction questions

Create a free account to work through every A-Level Proof by contradiction question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Proof by contradiction practice

Practice QuestionsWorked Solutions

Related Pure Maths topics

Areas and further applicationsMathematical argument and notationArithmetic sequences and seriesBinomial expansion (rational powers)Binomial expansionCircles