Lecture 3

Mathematical Proofs
1.7 Introduction to Proofs
1.8 Proof Methods and Strategy

2020/9/14 1
 Example vs. Proof
• Prove that an odd number + an odd number = an
even number.
• Think for a moment how you would proceed?
• “Proof”
Since 3 + 5 = 8,
and 3, 5 are odd and 8 even,
So, odd + odd = even

What is wrong with the above “proof” ?

How should we proceed to prove that odd + odd = even ?

2020/9/14 2
 Prove that n2 – n + 41 is a prime number, for all
positive integers n.

Examples: n = 1, true
n = 2, true
n = 3, true
…
n = 40 true
what about n = 41?

2020/9/14 3
 Example vs. Proof
• In general, providing an example (or examples) is
not giving a proof; we should use general
properties instead
• E.g., Prove that “an odd number + an odd number
= an even number”
• Let m, n be any two odd numbers

Since 3 + 5 = 8, Then, m = 2k+1, n = 2j+1

3, 5 are odd and 8 even, Then, m + n = (2k+1) + (2j+1)

So, odd + odd = even = 2k + 2j +2

= 2(k+j+1)
(Wrong !) = 2p where p = k+j+1
= even
2020/9/14 4
(Correct )
 How would you prove that your program is
correct (that is, it works correctly for all inputs) ?

The American space shuttle Challenger exploded

killing all seven astronauts in 1986
https://www.youtube.com/watch?v=eGLCB6Cl-VY

It was caused by a bug in the computer program.

2020/9/14 5
1.7 Introduction to Proofs
A mathematical system consists of
◼ Undefined terms
◼ Definitions
◼ Axioms

2020/9/14 6
Undefined Terms
Undefined terms are the basic building blocks
of a mathematical system. These are words
that are accepted as starting concepts of a
mathematical system.
◼ Example: in Euclidean geometry we have
undefined terms such as
 Point
 Line
◼ Example: in set theory, a set is an undefined term

2020/9/14 7
Definitions
A definition is a proposition constructed from
undefined terms and previously accepted concepts in
order to create a new concept.
◼ Example. In Euclidean geometry the following is definition:
 Two angles are supplementary if the sum of their
measures is 180 degrees.

◼ Example. In number theory,

 A number, n, is even if it is divisible by 2, that is,
n = 2k, k is an integer
 A number, n, is odd if it is not divisible by 2, that is,
n = 2k + 1, k is an integer

2020/9/14 8
Axioms
An axiom is a proposition accepted as true
without proof within the mathematical system.
◼ Example: In Euclidean geometry the following is
axiom
 Given two distinct points, there is exactly one
line that contains them.

2020/9/14 9
Theorems
A theorem is a proposition of the form p → q
which must be shown to be true by a
sequence of logical steps that assume that p
is true, and use definitions, axioms and
previously proven theorems.
◼ Example: In Euclidean geometry the following is a
theorem
 If two sides of a triangle are equal, then the
angles opposite them are equal. …(*)

2020/9/14 10
Lemmas and Corollaries
A lemma is a small theorem which is used to
prove a bigger theorem.
A corollary is a theorem that can be proven to
be a logical consequence of another theorem.
◼ Example from Euclidean geometry
 If a triangle is equilateral, then it is equiangular
 (follows immediately from the theorem (*))

2020/9/14 11
Types of Proof
A proof is a logical argument that consists of
a series of steps using propositions in such a
way that the truth of the theorem is
established.
- Direct proof
- Indirect proof
- Proof by contraposition
- Proof by contradiction

2020/9/14 12
Direct proof
In a direct method of a conditional statement
p → q we assume that p is true and use
axioms, definitions, and previously proven
theorems, together with rules of reference, to
show that the proposition q must also be true.

2020/9/14 13
Class Exercise 1
Give a direct proof of the theorem
“If n is an even integer, then n2 is even.”

2020/9/14 14
Indirect Proof –
Proof by contraposition

Proofs by contraposition make use of the fact

that p → q is equivalent to its contrapositive
q → p. This means that p → q can be
proved by showing q → p is true.
To show q → p is true, we take q as a
hypothesis, and using axioms, definitions,
and previously proved theorems, together
with rules of inference, we show that p
must follow.

2020/9/14 15
Class Exercise 2
Give a proof by contraposition of the theorem
“if n is an integer and 3n + 2 is odd, then n is
odd.” (Try a direct proof first.)

2020/9/14 16
Indirect Proof –
Proof by contradiction

In a proof by contradiction, we assume what we

have to prove to be false. Then we validly derive
a contradiction, which must be false. Then we
conclude our assumption is false, then what we
want to prove is true.

Can you use a direct proof to show that “there is

no greatest number” ?

2020/9/14 17
Class Exercise 3
Give a proof by contradiction of the theorem
“if 3n+2 is odd, then n is odd.”

2020/9/14 18
Class Exercise 4
Give a proof by contradiction for “there is no
greatest number”.
Proof:
1. Assume there is greatest number, say m
2. Since to any number we can add 1, we
have number m + 1
3. m + 1 > m
4. m is not greatest number
5. Statements 1 and 4 contradict
2020/9/14 19
 How would you prove that the angle sum of
any triangle is 180o ?

Use a protractor to measure the angles?

No! This is a physical experiment, not a

mathematical proof

2020/9/14 20
 Class Exercise 5 - pigeonholes
Given that there are 3 pigeonholes and 4 pigeons.
Prove by contradiction that when all 4 pigeons are
put into the pigeon-holes, there is at least one
pigeon which has at least 2 pigeons.
Proof:
Assume that all 4 pigeons are put into the
pigeonholes, and that no pigeonhole has more than
1 pigeon. Since there are 3 pigeonholes and no
pigeonhole has more than 1 pigeon, there are at
most 3 pigeons, contradicting that all 4 pigeons are
put into the pigeonholes.
2020/9/14 21
Class Exercise 6
Give a proof by contradiction for the theorem
“2 is an irrational number”.

2020/9/14 22
Class Exercise 6
Give another proof by contradiction for the theorem
“2 is an irrational number”.

2020/9/14 23
Tutorial 3
Give a proof by contradiction for the theorem
“3 is an irrational number”.

2020/9/14 24
Class Exercise 7

Prove by contradiction that the Rules of Inference

are all valid.

2020/9/14 25
Rules of Inference (1)
1. Law of detachment or 3. Rule of Addition (Add)
modus ponens (MP) p
p→q pq
p
 q 4. Rule of simplification
2. Modus tollens (MT) (Simp)
p→q pq
q p
p

2020/9/14 26
Rules of Inference (2)
5. Rule of conjunction (Conj) 7. Rule of disjunctive
p syllogism (Disj)
q pq
pq p
q
6. Rule of hypothetical syllogism
(HS)
p→q
q→r
p→r

2020/9/14 27
Tutorial 3
Give a proof by contradiction for the theorem
“there is no greatest prime number”.

http://primes.utm.edu/notes/proofs/infinite/euclids.html

2020/9/14 28
1.8 Proof Methods and Strategy

Exhaustive Proofs
Proofs by Cases
Existence Proofs
Uniqueness Proofs

2020/9/14 29
Exhaustive Proofs
Prove by exhaustion that (n+1)3  3n if n is a
positive integer with n  4.

2020/9/14 30
Proofs by Cases
Prove by cases that if n is an integer, then n2  n.

2020/9/14 31
Existence Proofs
(Constructive existence proof)
Show that there exists an even prime number.

2020/9/14 32
Existence Proofs
(Constructive existence proof)
Show that there exists a positive integer that
can be written as the sum of cubes of
positive integers in two different ways.

2020/9/14 33
Existence Proofs
(Non-constructive existence proof)
Show that there exists irrational numbers x
and y such that xy is rational.

2020/9/14 34
Uniqueness Proofs
Show that if a and b are real numbers and a  0, then
there is a unique real number r such that ar + b = 0.

2020/9/14 35
 Class Exercise 8 – Very hard!
Prove:
Every even number greater than two can be
expressed as the sum of two prime numbers.

任何一個大於2的偶數，均可表示成兩個質數之和。
http://zh.wikipedia.org/wiki/%e5%93%a5%e5%be%b7%e5%b7%b4%e8%b5%ab
%e7%8c%9c%e6%83%b3

2020/9/14 36