CSM 165: Lecture 4
Kwame Atta Gyamfi (PhD)
Dept. of Mathematics
KNUST
February 9, 2024
Summary of topics
1 Intro: Proof Strategies
2 Equivalent statements
3 Counterexample
4 Direct proofs
5 In direct proofs
Contradiction
Contrapositions
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Warm-up exercise
Example 1
Determine if the following statement is true or false.
∀n ∈ N ∃m ∈ N (n > 3 → (n + 7)2 > 49 + m)
1 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Summary of topics
1 Intro: Proof Strategies
2 Equivalent statements
3 Counterexample
4 Direct proofs
5 In direct proofs
2 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Definition 2 (What is a mathematical proof?)
A proof is a sequence of logically valid statements to
demonstrate the validity of some precise statement.
The word ’proof’ has different meaning in different contexts
(or field). E.g. A ”proof”
in biology might consist of experimental data confirming a
certain hypothesis.
in sociology or psychology might consist of the results of
a survey.
in CS/Maths, might consists of convincing arguments that
show that the desired conclusions follow logically from the
given hypotheses.
What is common to all forms of proof is that they are
arguments that convince experienced practitioners of the
given field.
3 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Why do we need proofs?
1 Explain why an ”intuitive” idea is true.
2 Explain the ideas underpinning the result being proved.
Any proof, is better than no proof at all.
3 For pedagogical reasons.
4 A way of communicating to another person an idea that
one believes to be true but the other person does not.
4 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Mathematical statements
1 Theorem: A statement that has been proven to be true.
e.g. If two sides of a triangle are equal, then the angles
opposite them are equal.
2 Axioms, postulates, hypothesis, premises:
Assumptions (often unproven) defining the structures
about which we are reasoning.
3 Defintion: A definition is a well-established fact. e.g. A
circle is a closed curve in which every point on the curve is
equidistant from a fixed point called center.
4 Lemma: A minor theorem used as a stepping-stone to
proving a major theorem. Eg. If we subtract 1 from a
positive integer, then the result is either a positive or 0.
5 Corollary: A minor theorem proved as an easy
consequence of a mojor theorm.
6 Conjecture: A statement whose truth value has not been 5 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Summary of topics
1 Intro: Proof Strategies
2 Equivalent statements
3 Counterexample
4 Direct proofs
5 In direct proofs
6 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Prooving that two or more statements are
equivalent
Also called proof of if and only if statements.
Exactly two propositions p1 and p2 .
1 We prove that propositions p1 and p2 are equivalent by
showing that p1 ↔ p2 is a tautology.
2 Alternatively, p1 ↔ p2 ≡ ((p1 →) ∧ (p2 → p1 ))
A general rule of thumb!!!
We can only prove what we don’t know
using what we know.
7 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Example of proving equivalent statements I
Example 3
Prove that for every positive integer n, n is even if and only if
n − 1 is odd.
8 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Summary of topics
1 Intro: Proof Strategies
2 Equivalent statements
3 Counterexample
4 Direct proofs
5 In direct proofs
9 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Proof by Counterexample I
Proof by Counterexample
We use this strategy to prove that a statement of the form
∀xP(x) is False for an element its domain of discourse.
Example 4 (Disprove the following statement)
1 For every positive integer n, 2n + n is prime.
10 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Proof by Counterexample II
Example 5 (Disprove the following statement)
2 For all real numbers a and b, if a2 = b2 , then a = b.
11 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Summary of topics
1 Intro: Proof Strategies
2 Equivalent statements
3 Counterexample
4 Direct proofs
5 In direct proofs
12 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Direct proof I
A direct proof is a type of proof that follows from definition(s).
Example 6
Prove that the sum of any two integers is even.
13 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Direct proof II
Example 7
Prove that the sum of an even and odd integer is odd.
14 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Direct proof III
Example 8
Prove that the sum of two odd integer is even.
Proof
If x and y are odd, then x = 2c + 1 and y = for some
integers c and d. So, x + y = 2c + 1 + 2d + 1 = 2(c + d + 1).
Now is an integer, so 2(c + d + 1) is an integer.
15 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Direct proof IV
Example 9
Prove the following statements are true.
(a) If n is an odd integer, then n2 is odd.
(b) If a and b are positive integers, then a2 − ab + b2 > 0.
(c) The sum of two rational numbers is rational.
(d) Every odd integer is the difference of two squares.
16 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Workings
17 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Summary of topics
1 Intro: Proof Strategies
2 Equivalent statements
3 Counterexample
4 Direct proofs
5 In direct proofs
18 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Intro
19 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Contradiction
Summary of lectures
1 Intro: Proof Strategies
2 Equivalent statements
3 Counterexample
4 Direct proofs
5 In direct proofs
Contradiction
Contrapositions
20 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Contradiction
Proof by contradiction I
Assume the negation of the given statement is true.
Deduce and incompatible statements from the negation.
Example 10
Prove the following statements using a proof by contradiction.
(a) The earth is flat.
(b) The sum of any rational number and any irrational number
is irrational.
√
(c) 2 is irrational.
(d) There is no greatest integer.
21 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Contradiction
Proof by contradiction II
Example 11
Prove that if 5n + 2 is odd, then n is odd.
Proof.
Assume that 5n + 2 is odd and n is even. If the assumption is
true, then n = 2k for some k ∈ Z. This would mean that
5n + 2 = 5(2k ) + 2 = 10k + 2 = 2(5k + 1). Since the last
expression is even, it contradicts our assumption that 5n + 2 is
odd. We therefore conclude that n must be even.
This would require lots of practice to get used to.
22 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Contrapositions
Summary of lectures
1 Intro: Proof Strategies
2 Equivalent statements
3 Counterexample
4 Direct proofs
5 In direct proofs
Contradiction
Contrapositions
23 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Contrapositions
Proofs by contrapositives
Recall the meta-statement: P → Q ⇔ ¬Q → ¬P
A proof by contraposition is to prove the contraposition of a
given statement.
Example 12
1 Prove by contraposition that if 5n + 2 is odd, then n is odd.
2 Prove that if 3n + 2 is even then n is even.
[Short Quiz]
Write and submit the converse of all statements given in
Example 12.
24 / 25
Intro: Proof Strategies Equivalent statements Counterexample Direct proofs In direct proofs
Contrapositions
Example 13
Prove the following statements using a proof by contraposition.
1 If a real number is irrational, then its square root is
irrational.
2 If r =√mn, where√m and n are positive integers, then
m ≤ r or n ≤ r .
25 / 25