Proof by Contradiction (DP IB Analysis & Approaches (AA)): Revision Note

Proof by Contradiction

What is proof by contradiction?

• Proof by contradiction is a way of proving a result is true by showing that the negation (opposite) can not be true

• It is done by

  • Assuming the negation of the result is true

  • Showing that this then leads to a contradiction

How do I find the negation of a statement?

• The negation of a statement is the opposite

  • Examples include:

What are the steps for proof by contradiction?

• STEP 1
  Assume the negation of the statement is true

• STEP 2
  Find two results which contradict each other

  • Use algebra to help with this

  • Consider how a contradiction might arise

• STEP 3
  Explain why the original statement is true

  • In your explanation mention

    • The negation can’t be true as it led to a contradiction

    • Therefore the original statement must be true

What could I be asked to prove by contradiction?

• You could be asked to use prove by contradiction to

  • prove that a number is irrational

    • by first assuming it is rational and written in its simplest form

    • e.g.

    • but then using algebra to show that and are both even

    • meaning wasn't in its simplest form after all

  • prove that there is no maximum multiple of 5

    • by first assuming there is (call it )

    • but then is a bigger multiple of 5

    • so can't have been the biggest after all

  • prove that there are infinitely many prime numbers

    • by first assuming there are only a finite number

    • call them where is the biggest

    • but then showing that is prime and bigger than

    • so wasn't the biggest after all