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:

Statement	Negation
a is rational	a is irrational
every even number bigger than 2 can be written as the sum of two primes	there exists an even number bigger than 2 which cannot be written as a sum of two primes
n is even and prime	n is not even or n is not prime
there is at least one odd perfect number	all perfect numbers are even
n is a multiple of 5 or a multiple of 3	n is not a multiple of 5 and n is not a multiple of 3
if n² is even then n is even	n² is even and n is odd

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 $\sqrt[n]{p}$ is irrational where p is a prime

Assume $\sqrt[n]{p} = \frac{a}{b}$ 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 $\log_{p} (q)$ is irrational where p & q are different primes

Assume $\log_{p} (q) = \frac{a}{b}$ 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 $p = 1 + p_{1} \times p_{2} \times . . . \times p_{n}$ 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

Examiner Tip

A question won't always state that you should use proof by contradiction, you will need to recognise that it is the correct method to use
- There will only be two options (e.g. a number is rational or irrational)
- Contradiction is often used when no other proof seems reasonable

Worked example

Prove the following statements by contradiction.

For any integer

n

, if

n^{2}

is a multiple of 3 then

n

is a multiple of 3.

1-5-2-ib-aa-hl-proof-by-contradiction-a-we-solution

\sqrt{3}

is an irrational number.

1-5-2-ib-aa-hl-proof-by-contradiction-b-we-solution

Proof by Contradiction (DP IB Maths: AA HL)

Revision Note

Proof by Contradiction

What is proof by contradiction?

How do I determine the negation of a statement?

What are the steps for proof by contradiction?

What type of statements might I be asked to prove by contradiction?

Examiner Tip

Worked example

You've read 0 of your 10 free revision notes

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

Author: Dan