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:

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

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

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

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

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

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

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)