P4 Chapter 1: Proofs by Contradiction
www.dilanmaths.com
Introducing Proofs by Contradiction
🖉 To prove a statement is true by contradiction:
Prove there is no greatest integer.
Proof structure:
1. “Assume that [negation of statement].”
2. [Reasoning followed by…]
“This contradicts the assumption that…” or “This is a contradiction.”
3. “Therefore [restate original statement].”
Therefore, there is no greatest integer.
Thinking Deeper
Prove there is no greatest integer.
Proof structure:
1. “Assume that [negation of statement].”
2. [Reasoning followed by…]
“This contradicts the assumption that…” or “This is a contradiction.”
3. “Therefore [restate original statement].”
Therefore, there is no greatest integer.
In a nutshell, this proof is a formal way of writing “You think you’ve found the biggest possible integer?
Well, I’ll add 1 to it!”
Test Your Understanding
Prove there is no greatest even integer.
Proof structure:
1. “Assume that [negation of statement].”
2. [Reasoning followed by…]
“This contradicts the assumption that…” or “This is a contradiction.”
3. “Therefore [restate original statement].”
Therefore, there is no greatest even integer.
1
?
?
?
Negation of a Statement
Proof structure:
1. “Assume that [negation of statement].”
Let’s focus on the first step in different scenarios.
“There are infinitely many prime numbers.”
“There are infinitely many non-prime (i.e. composite) numbers.”
“There are finitely many prime numbers.”
“There are finitely many non-composite numbers.”
“All Popes are Catholic.”
“No Popes are Catholic.”
“There exists a Pope who is not Catholic.”
“Dr Frost is the Pope.”
“If it is raining, my garden is wet.”
“It is not raining and my garden is dry.”
“It is raining and my garden is not wet.”
“It is not raining and my garden is wet.”
Which of the following statements are the correct negations?
Negation of a Statement
?
?
?
🖉 To negate different types of statement:
Type | Negation | Example |
| | “If a number is prime, it is not square” 🡪 “Suppose a number is prime and is square” |
| | “All cats are cute” 🡪 “Suppose there exists a cat which is not cute.” |
Do not use the word ‘if’ in the negation. Use ‘and’.
a
b
c
a
b
c
Proofs Involving Oddness & Evenness
Proof structure:
1. “Assume that [negation of statement].”
2. [Reasoning followed by…]
“This contradicts the assumption that…” or “This is a contradiction.”
3. “Therefore [restate original statement].”
Test Your Understanding
Proof structure:
1. “Assume that [negation of statement].”
2. [Reasoning followed by…]
“This contradicts the assumption that…” or “This is a contradiction.”
3. “Therefore [restate original statement].”
2
?
?
?
Proofs Involving Rational Numbers
Proof structure:
1. “Assume that [negation of statement].”
2. [Reasoning followed by…]
“This contradicts the assumption that…” or “This is a contradiction.”
3. “Therefore [restate original statement].”
Test Your Understanding
Proof structure:
1. “Assume that [negation of statement].”
2. [Reasoning followed by…]
“This contradicts the assumption that…” or “This is a contradiction.”
3. “Therefore [restate original statement].”
The negation of “at least one is irrational” is “neither is irrational”.
3
?
?
?
Proof there are Infinitely Many Primes
Let’s first show informally with examples.
Prove by contradiction that there are infinitely many prime numbers.
Assume there are finitely many primes and we can list all of them.
Multiply them all together and add 1.
Proof there are Infinitely Many Primes
Prove by contradiction that there are infinitely many prime numbers.
This proof is courtesy of Euclid and is one of the earliest known proofs.
Therefore, there are an infinite number of primes.
? Assumption
? Assumption
? Conclusion
4
1. “Assume that [negation of statement].”
2. [Reasoning followed by…]
“This contradicts the assumption that…” or “This is a contradiction.”
3. “Therefore [restate original statement].”
This detail might seem unnecessary but is key to proving a contradiction later.
Test Your Understanding
1. “Assume that [negation of statement].”
2. [Reasoning followed by…]
“This contradicts the assumption that…” or “This is a contradiction.”
3. “Therefore [restate original statement].”
?
?
?
5
An Example from the Show ‘QI’
🙶All numbers are interesting.🙷
Proof:
Suppose there exists one or more ‘uninteresting’ numbers.
There must therefore be a ‘least (smallest) uninteresting number’.
This makes the number interesting.
This contradicts the fact this number was uninteresting.
Therefore, there are no uninteresting numbers.
© Talkback / BBC