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 can not be true

• It is done by:

  • Assuming the negation (opposite) of the result is true

  • Showing that this then leads to a contradiction

How do I determine the negation of a statement?

• The negation of a statement is the opposite

  • It is the statement that makes the original statement false

• To negate statements that mention “all”, “every”, “and” “both”:

  • Replace these phrases with “there is at least one”, “or” or “there exists” and include the opposite

• To negate statements that mention “there is at least one”, “or” or “there exists”:

  • Replace these phrases with “all”, “every”, “and” or “both” and include the opposite

• To negate a statement with “if A occurs then B occurs”:

  • Replace with “A occurs and the negation of B occurs”

• Examples include:

What are the steps for proof by contradiction?

• STEP 1: Assume the negation of the statement is true

  • You assume it is true but then try to prove your assumption is wrong

    • For example: To prove that there is no smallest positive number you start by assuming there is a smallest positive number called a

• STEP 2: Find two results which contradict each other

  • Use algebra to help with this

  • Consider how a contradiction might arise

    • For example: ½a is positive and it is smaller than a which contradicts that a was the smallest positive number

• 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 type of statements might I be asked to prove by contradiction?

• Irrational numbers

  • To show  is irrational where p is a prime

    • Assume  where a & b are integers with no common factors and b ≠ 0

    • Use algebra to show that p is a factor of both a & b

  • To show that  is irrational where p & q are different primes

    • Assume  where a & b are integers with no common factors and b ≠ 0

    • Use algebra to show q^b = p^a

  • To show that a or b must be irrational if their sum or product is irrational

    • Assume a & b are rational and write as fractions

    • Show that a + b or ab is rational

• Prime numbers

  • To show a polynomial is never prime

    • Assume that it is prime

    • Show there is at least one factor that cannot equal 1

  • To show that there is an infinite number of prime numbers

    • Assume there are n primes p₁, p₂, ..., p_n

    • Show that  is a prime that is bigger than the n primes

• Odds and evens

  • To show that n is even if n² is even

    • Assume n² is even and n is odd

    • Show that n² is odd

• Maximum and minimum values

  • To show that there is no maximum multiple of 3

    • Assume there is a maximum multiple of 3 called a

    • Multiply a by 3