Math101 - Lecture 2 revision

[fardell24]

MATH101 – Lecture 2 1 March 2000

Proof by Contraposition or Contradiction
If in an implication “if A then B” we assume B false and prove that A is false then the implication must be true
Example
Prove that p is a prime number larger than 2 then p + 1 is not prime
Proof: Let A be: - p is a prime number larger than 2
Let B be: - p + 2 is not prime
We wish to prove the implication If A then B
For a proof by contradiction we assume B false
We assume P + 1 is prime (ie B false). We now use this to get a contradiction,
We have: - 1) p is a prime number larger than 2 (A true)
2) p + 1 is prime (B false)
Last time we proved p + q is even for two primes larger than 2. We apply this to the current case. Must have p (p + 1) is even.
But p + (p +1) = 2p + 1 is odd. A contradiction. B cannot be false. It must be true.
If A implies B
Assume B false
Get contradiction
Then B must be false

Types of Theorems and their proofs
“If and only if” or Equivalence.
eg A if and only if B
A is equivalent to B
A is true if and only if B is true
A is a necessary and sufficient condition for B
Two way implications
Equivalence (“if and only”) requires two proofs:
1) A implies B
2) B implies A
Eg Prove that if n is a counting number then n is odd
if and only if n^2 is odd.
Proof: We have two implications to proove
1) If n odd and then n^2 is odd
2) IF n^2 odd then n odd
1) We assume n is odd, there is a counting number m such that n = 2m + 1
n^2 = (2m+1)^2 = (2m)^2 + 1^2 + 2x1x2m
= 4m^2 + 4m + 1
= 4((m^2 +m) +1
Which is odd we have proved 1)
2) Assume n^2 is odd
Lecture notes give proof by contradiction: assume n even then n = 2m, for some counting number m.
So, n^2 = 4m^2 an even number. We have a contradiction. n^2 is odd. So n can't be even.
Therefore n is odd

OR direct proof n^2 odd implies n odd.
N^2 odd means that n^2 – 1 is even
Therefore n^2 = (n – 1)(n+1) is even
Therefore either n + 1 is even
OR n – 1 is even
OR Both!
If n + 1 is even then n is odd.
If n – 1 is even then is is odd.