Scene 1

§ 2.1 Mathematical Systems, Direct Proofs
and Counterexamples

Scene 2

1
Axiom - statement that is accepted to be true without proof

>Types of Mathematical Statements
1
Axiom - statement that is accepted to be true without proof
Example: Euclid’s axioms, the first of which is “A straight line
segment can be drawn joining any two points.”
2
Theorem - a mathematical statement whose truth can be verified,
although mathematician usually reserve this term for important
or interesting.
3
Corollary - a mathematical statement that is a consequence of a
theorem or an axiom.
4
Lemma - a mathematical result that is useful in verifying the
truth in another result.

Scene 3

1
Axiom - statement that is accepted to be true without proof
Example: Euclid’s axioms, the first of which is “A straight line
segment can be drawn joining any two points.”

Scene 4

2
Theorem - a mathematical statement whose truth can be verified,
although mathematician usually reserve this term for important
or interesting.

Scene 5

3
Corollary - a mathematical statement that is a consequence of a
theorem or an axiom.

Scene 6

4
Lemma - a mathematical result that is useful in verifying the
truth in another result.

Scene 7

A direct proof is a way of showing the truth or falsehood of a given
statement by a straightforward combination of established facts,
usually existing lemmas and theorems, without making any further
assumptions.

>Direct Proofs
Definition
A direct proof is a way of showing the truth or falsehood of a given
statement by a straightforward combination of established facts,
usually existing lemmas and theorems, without making any further
assumptions.
Definition
An indirect proof may begin with certain hypothetical scenarios and
then proceed to eliminate the uncertainties in each of these scenarios
until an inescapable conclusion is forced.

Scene 8

An indirect proof may begin with certain hypothetical scenarios and
then proceed to eliminate the uncertainties in each of these scenarios
until an inescapable conclusion is forced.

Scene 9

1
Always state the assumptions that can be made.

>How To Write Proofs: The Basics
1
Always state the assumptions that can be made.
2
Always state what you are trying to prove.
3
Always separate strings of equations - whether a simple
statement or a long series of algebraic steps, separation makes it
easier for the reader to be able to verify the work.
4
Always state that the proof is complete in some way
Use a black box or an open box
Write Q.E.D., which is the abbreviation for the Latin phrase
‘quod erat demonstrandum,’, which means ‘which had to be
demonstrated’
5
Never refer to yourself in a proof - if you need to use a pronoun,
use ‘we’

Scene 10

2
Always state what you are trying to prove.

Scene 11

3
Always separate strings of equations - whether a simple
statement or a long series of algebraic steps, separation makes it
easier for the reader to be able to verify the work.

Scene 12

4
Always state that the proof is complete in some way

Scene 13

Write Q.E.D., which is the abbreviation for the Latin phrase
‘quod erat demonstrandum,’, which means ‘which had to be
demonstrated’

Scene 14

5
Never refer to yourself in a proof - if you need to use a pronoun,
use ‘we’

Scene 15

If n is an odd integer then 5n + 3 is an even integer.

>A First Proof
Example
If n is an odd integer then 5n + 3 is an even integer.
We need to start with something of the form 2k + 1 and we need to
end with something of the form 2k. So we want to use the definitions
we established above and keep these in mind.
Proof: Assume that n is an odd integer. We want to show that 5n + 3
is an even integer.
Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,
5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 = 2(5k + 4)
Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

Scene 16

We need to start with something of the form 2k + 1 and we need to
end with something of the form 2k. So we want to use the definitions
we established above and keep these in mind.

Scene 17

Proof: Assume that n is an odd integer. We want to show that 5n + 3
is an even integer.

Scene 18

Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1.

>A First Proof
Example
If n is an odd integer then 5n + 3 is an even integer.
We need to start with something of the form 2k + 1 and we need to
end with something of the form 2k. So we want to use the definitions
we established above and keep these in mind.
Proof: Assume that n is an odd integer. We want to show that 5n + 3
is an even integer.
Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1.
Now,
5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 = 2(5k + 4)
Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

Scene 19

Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,

>A First Proof
Example
If n is an odd integer then 5n + 3 is an even integer.
We need to start with something of the form 2k + 1 and we need to
end with something of the form 2k. So we want to use the definitions
we established above and keep these in mind.
Proof: Assume that n is an odd integer. We want to show that 5n + 3
is an even integer.
Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,
5n + 3 =
5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 = 2(5k + 4)
Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

Scene 20

>A First Proof
Example
If n is an odd integer then 5n + 3 is an even integer.
We need to start with something of the form 2k + 1 and we need to
end with something of the form 2k. So we want to use the definitions
we established above and keep these in mind.
Proof: Assume that n is an odd integer. We want to show that 5n + 3
is an even integer.
Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,
5n + 3 = 5(2k + 1) + 3 =
(10k + 5) + 3 = 10k + 8 = 2(5k + 4)
Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

Scene 21

>A First Proof
Example
If n is an odd integer then 5n + 3 is an even integer.
We need to start with something of the form 2k + 1 and we need to
end with something of the form 2k. So we want to use the definitions
we established above and keep these in mind.
Proof: Assume that n is an odd integer. We want to show that 5n + 3
is an even integer.
Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,
5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 =
10k + 8 = 2(5k + 4)
Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

Scene 22

5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 =

>A First Proof
Example
If n is an odd integer then 5n + 3 is an even integer.
We need to start with something of the form 2k + 1 and we need to
end with something of the form 2k. So we want to use the definitions
we established above and keep these in mind.
Proof: Assume that n is an odd integer. We want to show that 5n + 3
is an even integer.
Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,
5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 =
2(5k + 4)
Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

Scene 23

5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 = 2(5k + 4)

Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

Scene 24

>Another Example
Example
If n is an odd integer then n2 is odd.
Suppose n is an odd integer. Then we can write n in the form
n = 2k + 1 where k ∈ Z. Consider
n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1
Since k is an integer, so is 2k2 + 2k and so we can write n2 in the form
necessary for inclusion in the set of odd integers. Therefore, if n is
odd then n2 is as well. Q.E.D.

Scene 25

Suppose n is an odd integer. Then we can write n in the form
n = 2k + 1 where k ∈ Z.

>Another Example
Example
If n is an odd integer then n2 is odd.
Suppose n is an odd integer. Then we can write n in the form
n = 2k + 1 where k ∈ Z.
Consider
n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1
Since k is an integer, so is 2k2 + 2k and so we can write n2 in the form
necessary for inclusion in the set of odd integers. Therefore, if n is
odd then n2 is as well. Q.E.D.

Scene 26

Suppose n is an odd integer. Then we can write n in the form
n = 2k + 1 where k ∈ Z. Consider

>Another Example
Example
If n is an odd integer then n2 is odd.
Suppose n is an odd integer. Then we can write n in the form
n = 2k + 1 where k ∈ Z. Consider
n2 = (2k + 1)2 =
4k2 + 4k + 1 = 2(2k2 + 2k) + 1
Since k is an integer, so is 2k2 + 2k and so we can write n2 in the form
necessary for inclusion in the set of odd integers. Therefore, if n is
odd then n2 is as well. Q.E.D.

Scene 27

>Another Example
Example
If n is an odd integer then n2 is odd.
Suppose n is an odd integer. Then we can write n in the form
n = 2k + 1 where k ∈ Z. Consider
n2 = (2k + 1)2 = 4k2 + 4k + 1 =
2(2k2 + 2k) + 1
Since k is an integer, so is 2k2 + 2k and so we can write n2 in the form
necessary for inclusion in the set of odd integers. Therefore, if n is
odd then n2 is as well. Q.E.D.

Scene 28

n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1

Since k is an integer, so is 2k2 + 2k and so we can write n2 in the form
necessary for inclusion in the set of odd integers. Therefore, if n is
odd then n2 is as well. Q.E.D.

Scene 29

Every odd integer is the difference of two perfect squares.

>Perfect Squares
Example
Every odd integer is the difference of two perfect squares.
Let n be an odd integer. We want to show that n is the difference of
two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since
k is an integer, k2 and (k + 1)2 are both perfect squares.
Consider
(k + 1)2 = k2 + 2k + 1
and
k2 + 2k + 1 − k2 = 2k + 1
Therefore, if n is odd then we can express n as the difference of
perfect squares. Q.E.D.

Scene 30

>Perfect Squares
Example
Every odd integer is the difference of two perfect squares.
Let n be an odd integer.
We want to show that n is the difference of
two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since
k is an integer, k2 and (k + 1)2 are both perfect squares.
Consider
(k + 1)2 = k2 + 2k + 1
and
k2 + 2k + 1 − k2 = 2k + 1
Therefore, if n is odd then we can express n as the difference of
perfect squares. Q.E.D.

Scene 31

Let n be an odd integer. We want to show that n is the difference of
two perfect squares.

>Perfect Squares
Example
Every odd integer is the difference of two perfect squares.
Let n be an odd integer. We want to show that n is the difference of
two perfect squares.
Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since
k is an integer, k2 and (k + 1)2 are both perfect squares.
Consider
(k + 1)2 = k2 + 2k + 1
and
k2 + 2k + 1 − k2 = 2k + 1
Therefore, if n is odd then we can express n as the difference of
perfect squares. Q.E.D.

Scene 32

Let n be an odd integer. We want to show that n is the difference of
two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1.

>Perfect Squares
Example
Every odd integer is the difference of two perfect squares.
Let n be an odd integer. We want to show that n is the difference of
two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1.
Since
k is an integer, k2 and (k + 1)2 are both perfect squares.
Consider
(k + 1)2 = k2 + 2k + 1
and
k2 + 2k + 1 − k2 = 2k + 1
Therefore, if n is odd then we can express n as the difference of
perfect squares. Q.E.D.

Scene 33

Let n be an odd integer. We want to show that n is the difference of
two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since
k is an integer, k2 and (k + 1)2 are both perfect squares.

Scene 34

Let n be an odd integer. We want to show that n is the difference of
two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since
k is an integer, k2 and (k + 1)2 are both perfect squares.
Consider
(k + 1)2 = k2 + 2k + 1

Scene 35

Therefore, if n is odd then we can express n as the difference of
perfect squares. Q.E.D.

Scene 36

If n is an odd integer then 4n3 + 2n − 1 is odd.

>More Odd and Even Integers
Example
If n is an odd integer then 4n3 + 2n − 1 is odd.
Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is
an odd integer.
If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider
4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1
= 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1
= 32k3 + 48k2 + 28k + 5
= 2(16k3 + 24k2 + 14k + 2) + 1
Since 16k3 + 24k2 + 14k + 2 is an integer, 4n3 + 2n − 1 is odd and
this completes the proof.

Scene 37

Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is
an odd integer.

Scene 38

If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1.

>More Odd and Even Integers
Example
If n is an odd integer then 4n3 + 2n − 1 is odd.
Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is
an odd integer.
If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1.
Consider
4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1
= 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1
= 32k3 + 48k2 + 28k + 5
= 2(16k3 + 24k2 + 14k + 2) + 1
Since 16k3 + 24k2 + 14k + 2 is an integer, 4n3 + 2n − 1 is odd and
this completes the proof.

Scene 39

If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider

>More Odd and Even Integers
Example
If n is an odd integer then 4n3 + 2n − 1 is odd.
Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is
an odd integer.
If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider
4n3 + 2n − 1 =
4(2k + 1)3 + 2(2k + 1) − 1
= 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1
= 32k3 + 48k2 + 28k + 5
= 2(16k3 + 24k2 + 14k + 2) + 1
Since 16k3 + 24k2 + 14k + 2 is an integer, 4n3 + 2n − 1 is odd and
this completes the proof.

Scene 40

4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1

Scene 41

Scene 42

Scene 43

Scene 44

Since 16k3 + 24k2 + 14k + 2 is an integer, 4n3 + 2n − 1 is odd and
this completes the proof.

Scene 45

Although this is correct, it is not the most efficient proof we could
have written. We could have simply noted that

4n3 + 2n − 1 = 4n3 + 2n − 2 + 1 = 2(2n3 + n − 1) + 1

is odd for all n, making this a trivial proof. It would be better to
rewrite the hypothesis as ‘if n is an integer’.

Scene 46

For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z
then Y = Z.

>Intersections and Unions
Example
For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z
then Y = Z.
Let X, Y, Z be sets.
Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We
will show that Y and Z are subsets of each other.
Let y ∈ Y. Then y ∈ X ∪ Y. So, y ∈ X ∪ Z. That means y ∈ X or
y ∈ Z. If y ∈ Z, we are done. So suppose y ∈ X. Then y ∈ X ∩ Y. So,
y ∈ X ∩ Z. Thus both cases lead to y ∈ Z. Hence, Y ⊆ Z.
In a symmetric argument, it can be shown by assuming that we have
some z ∈ Z that Z ⊆ Y.
Since Y ⊆ Z and Z ⊆ Y, it must be the case that Y = Z. Thus, we
have arrived at the desired result. Q.E.D.

Scene 47

Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z.

>Intersections and Unions
Example
For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z
then Y = Z.
Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z.
We
will show that Y and Z are subsets of each other.
Let y ∈ Y. Then y ∈ X ∪ Y. So, y ∈ X ∪ Z. That means y ∈ X or
y ∈ Z. If y ∈ Z, we are done. So suppose y ∈ X. Then y ∈ X ∩ Y. So,
y ∈ X ∩ Z. Thus both cases lead to y ∈ Z. Hence, Y ⊆ Z.
In a symmetric argument, it can be shown by assuming that we have
some z ∈ Z that Z ⊆ Y.
Since Y ⊆ Z and Z ⊆ Y, it must be the case that Y = Z. Thus, we
have arrived at the desired result. Q.E.D.

Scene 48

Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We
will show that Y and Z are subsets of each other.

>Intersections and Unions
Example
For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z
then Y = Z.
Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We
will show that Y and Z are subsets of each other.
Let y ∈ Y. Then y ∈ X ∪ Y. So, y ∈ X ∪ Z. That means y ∈ X or
y ∈ Z. If y ∈ Z, we are done. So suppose y ∈ X. Then y ∈ X ∩ Y. So,
y ∈ X ∩ Z. Thus both cases lead to y ∈ Z. Hence, Y ⊆ Z.
In a symmetric argument, it can be shown by assuming that we have
some z ∈ Z that Z ⊆ Y.
Since Y ⊆ Z and Z ⊆ Y, it must be the case that Y = Z. Thus, we
have arrived at the desired result. Q.E.D.

Scene 49

>Intersections and Unions
Example
For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z
then Y = Z.
Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We
will show that Y and Z are subsets of each other.
Let y ∈ Y.
Then y ∈ X ∪ Y. So, y ∈ X ∪ Z. That means y ∈ X or
y ∈ Z. If y ∈ Z, we are done. So suppose y ∈ X. Then y ∈ X ∩ Y. So,
y ∈ X ∩ Z. Thus both cases lead to y ∈ Z. Hence, Y ⊆ Z.
In a symmetric argument, it can be shown by assuming that we have
some z ∈ Z that Z ⊆ Y.
Since Y ⊆ Z and Z ⊆ Y, it must be the case that Y = Z. Thus, we
have arrived at the desired result. Q.E.D.

Scene 50

>Intersections and Unions
Example
For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z
then Y = Z.
Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We
will show that Y and Z are subsets of each other.
Let y ∈ Y. Then y ∈ X ∪ Y. So,
y ∈ X ∪ Z. That means y ∈ X or
y ∈ Z. If y ∈ Z, we are done. So suppose y ∈ X. Then y ∈ X ∩ Y. So,
y ∈ X ∩ Z. Thus both cases lead to y ∈ Z. Hence, Y ⊆ Z.
In a symmetric argument, it can be shown by assuming that we have
some z ∈ Z that Z ⊆ Y.
Since Y ⊆ Z and Z ⊆ Y, it must be the case that Y = Z. Thus, we
have arrived at the desired result. Q.E.D.

2.1_mathematical_systems_direct_proofs_and_counterexamples_slides

Page 1 (0s)

Page 2 (8s)

Page 3 (36s)

Page 4 (49s)

Page 5 (1m 0s)

Page 6 (1m 10s)

Page 7 (1m 20s)

Page 8 (1m 50s)

Page 9 (2m 4s)

Page 10 (2m 40s)

Page 11 (2m 48s)

Page 12 (3m 2s)

Page 13 (3m 13s)

Page 14 (3m 27s)

Page 15 (3m 38s)

Page 16 (4m 22s)

Page 17 (4m 38s)

Page 18 (4m 50s)

Page 19 (5m 33s)

Page 20 (6m 18s)

Page 21 (6m 59s)

Page 22 (7m 43s)

Page 23 (8m 27s)

Page 24 (8m 44s)

Page 25 (9m 17s)

Page 26 (9m 52s)

Page 27 (10m 29s)

Page 28 (11m 1s)

Page 29 (11m 23s)

Page 30 (11m 57s)

Page 31 (12m 30s)

Page 32 (13m 5s)

Page 33 (13m 45s)

Page 34 (14m 27s)

Page 35 (14m 48s)

Page 36 (15m 3s)

Page 37 (15m 44s)

Page 38 (15m 56s)

Page 39 (16m 36s)

Page 40 (17m 17s)

Page 41 (17m 57s)

Page 42 (18m 8s)

Page 43 (18m 18s)

Page 44 (18m 28s)

Page 45 (18m 42s)

Page 46 (19m 5s)

Page 47 (20m 8s)

Page 48 (21m 7s)

Page 49 (22m 9s)

Page 50 (23m 4s)