Transition to Abstract Mathematics
Chapter 4 – Direct Proof and
Proof by Contrapositive
Part A
Scope
• Chapter 4: Direct Proof and Proof by Contrapositive
• Sections 4.1 to 4.5
• Exercises & Additional Exercises
• Page 87 to 110
Learning Outcomes
To learn how to prove a mathematical statement
using the following five proof techniques: Trivial
Proof, Vacuous Proof, Direct Proof, Proof by
Contrapositive, and Proof by Cases.
Purpose
Every mathematical statement presents two
problems for us:
1. To determine the truth or falseness of the
statement, and
2. To verify the correctness of our belief.
From Chapter 4 to Chapter 7 we will learn
various proof techniques that will enable us to
perform these two tasks given a mathematical
statement.
Terminology
• A true mathematical statement whose truth is
accepted without proof is referred to as an
axiom.
• A true mathematical statement whose truth can
be verified is often referred to as a theorem.
• Alternative terms used are proposition, result,
observation and fact.
• The choice often depends on the significance of
the statement or the degree of difficulty of its
proof.
Terminology
• A corollary is a mathematical result that can be
deduced from, and is thereby a consequence of,
some earlier result.
• A lemma is a mathematical result that is useful in
establishing the truth of some other result.
• A lemma is not of primary importance itself.
• Indeed, its very existence is due only to its
usefulness in proving another (more interesting)
result.
• Most theorems (or results) are stated as
implications.
Overview
In this chapter we will be proving statements of the
form
∀𝑥 ∈ 𝑆, 𝑃 𝑥 ⇒ 𝑄 𝑥
as true.
• The first four proof techniques we will learn all
focus on the implication part, 𝑃 𝑥 ⇒ 𝑄 𝑥 , and
works because of the truth table of implication.
• The fifth proof technique focuses on the domain
part, ∀𝑥 ∈ 𝑆.
• Quick task: Draw a complete truth table for 𝑃 → 𝑄
from memory.
1. Trivial Proof
• We want to prove the result
∀𝑥 ∈ 𝑆, 𝑃 𝑥 ⇒ 𝑄 𝑥
as true.
• If it can be shown that 𝑄 𝑥 is true for all 𝑥 ∈ 𝑆,
regardless of the truth value of 𝑃 𝑥 , then the
result is true.
• Why? We see this from the truth table of
implication: 𝑷 𝑸 𝑷⟹𝑸
𝑇 𝑇 𝑇
𝑇 𝐹 𝐹
𝐹 𝑇 𝑇
𝐹 𝐹 𝑇
1. Trivial Proof
• This method of proving is called a trivial proof.
• Example
For 𝑥 ∈ ℝ, if 𝑥 ≥ 0, then 𝑥 ≥ 0.
If we let 𝑃 𝑥 ∶ 𝑥 ≥ 0 and 𝑄 𝑥 ∶ 𝑥 ≥ 0, then we
see that 𝑄 𝑥 will always be true irrespective of
whether 𝑃 𝑥 is true or false. The statement is thus
true since 𝐴𝑛𝑦𝑡ℎ𝑖𝑛𝑔 → 𝑇𝑟𝑢𝑒 is true.
2. Vacuous Proof
• Again, we want to prove the result
∀𝑥 ∈ 𝑆, 𝑃 𝑥 ⇒ 𝑄 𝑥
as true.
• If it can be shown that 𝑃 𝑥 is false for all 𝑥 ∈ 𝑆,
regardless of the truth value of 𝑄 𝑥 , then the
result is true.
• Why? We see this from the truth table of
implication: 𝑷 𝑸 𝑷⟹𝑸
𝑇 𝑇 𝑇
𝑇 𝐹 𝐹
𝐹 𝑇 𝑇
𝐹 𝐹 𝑇
2. Vacuous Proof
• This method of proving is called a vacuous proof.
• Example
For 𝑥 ∈ ℝ, if 7 is even, then 𝑥 2 ≤ 0.
If we let 𝑃 𝑥 ∶ 7 𝑖𝑠 𝑒𝑣𝑒𝑛 and 𝑄 𝑥 ∶ 𝑥 2 ≤ 0, then
we see that 𝑃 𝑥 will always be false irrespective of
whether 𝑄 𝑥 is true or false. The statement is thus
true since 𝐹𝑎𝑙𝑠𝑒 → 𝐴𝑛𝑦𝑡ℎ𝑖𝑛𝑔 is true.
Axioms
We will assume without proof that:
1. The negative of every integer is an integer.
2. The sum (and difference) of every two integers is
an integer.
3. The product of every two integers is an integer.
Note that the same can’t be said about division.
Definitions
• An integer 𝑛 is defined to be even if 𝑛 = 2𝑘 for
some integer 𝑘.
• An integer 𝑛 is defined to be odd if 𝑛 = 2𝑘 + 1
for some integer 𝑘.
Any other result must be proved first at this stage!
3. Direct Proof
• To give a direct proof of a quantified statement
∀𝑥 ∈ 𝑆, 𝑃 𝑥 ⇒ 𝑄 𝑥
➢Assume that 𝑃 𝑥 is true for an arbitrary element
𝑥 ∈ 𝑆, and then
➢Show that 𝑄 𝑥 must be true as well for this element
𝑥.
• Why? We see this from the truth table of
implication: 𝑷 𝑸 𝑷⟹𝑸
𝑇 𝑇 𝑇
𝑇 𝐹 𝐹
𝐹 𝑇 𝑇
𝐹 𝐹 𝑇
3. Direct Proof
• This method of proving is called a direct proof.
• Example
If 𝑛 is an odd integer,
then 𝑛2 + 3𝑛 + 5 is an odd integer.
Assume that 𝑛 is an odd integer and let 𝑛 = 2𝑘 + 1 where 𝑘 is
an integer (by definition). Then
𝑛2 + 3𝑛 + 5 = 2𝑘 + 1 2 + 3 2𝑘 + 1 + 5
= 4𝑘 2 + 4𝑘 + 1 + 6𝑘 + 3 + 5
= 4𝑘 2 + 10𝑘 + 8 + 1
= 2 2𝑘 2 + 5𝑘 + 4 + 1
= 2𝑥 + 1
which is odd since 𝑥 = 2𝑘 2 + 5𝑘 + 4 is an integer by the axioms.
Please try now Class Exercise A
which is uploaded on Ulwazi.
