LECTURE NOTES

on

DISCRETE MATHEMATICS

Eusebius Doedel
 LOGIC

Introduction. First we introduce some basic concepts needed in our

discussion of logic. These will be covered in more detail later.

A set is a collection of “objects” (or “elements”).

EXAMPLES :

• the infinite set of all integers : Z ≡ {· · · , −2, −1, 0, 1, 2, 3, · · ·}.

• the infinite set of all positive integers : Z+ ≡ {1, 2, 3, · · ·}.

• the infinite set R of all real numbers.

• the finite set {T , F }, where T denotes “True ” and F “False ”.

• the finite set of alphabetic characters : {a, b, c, · · · , z}.

1
A function (or “map”, or “operator”) is a rule that associates to every
element of a set one element in another set.

EXAMPLES :

• If S1 = {a, b, c} and S2 = {1, 2} then the associations

a 7→ 2, b 7→ 1, c 7→ 2,

define a function f from S1 to S2 . We write

f : S1 −→ S2 .

• Similarly f (n) = n2 defines a function f : Z+ −→ Z+ .

• f (n) = n2 can also be viewed as a function f : Z −→ Z.

2
EXAMPLE :

Let Pn denoet the infinite set of all polynomial functions p(x) of degree
n or less with integer coefficients.

• The derivative operator D restricted to elements of Pn can be

viewed as a function from Pn to Pn−1 ,
dp
D : Pn −→ Pn−1 , D : p 7→ .
dx

For example, if p(x) = x3 + 2x + 1, then

D : x3 + 2x + 1 7→ 3x2 + 2 ,

i.e.,
D(x3 + 2x + 1) = 3x2 + 2 .

3
EXAMPLE :

• We can also define functions of several variables, e.g.,

f (x, y) = x + y ,

can be viewed as a function “from Z+ cross Z+ into Z+ ”.

We write
f : Z+ × Z+ −→ Z+ .

4
Basic logical operators.

The basic logical operators

∧ (“and” , “conjunction”)

∨ (“or” , “disjunction”)

¬ (“not” , “negation”)

are defined in the tables below :

p q p∨q p q p∧q
p ¬p T T T T T T
T F T F T T F F
F T F T T F T F
F F F F F F

5
Let B ≡ {T , F }. Then we can view ¬, ∨, and ∧, as functions

¬ : B −→ B, ∨ : B × B −→ B , ∧ : B × B −→ B .

We can also view the arithmetic operators −, +, and ×, as functions

− : Z −→ Z, + : Z × Z −→ Z, ∗ : Z × Z −→ Z,

defined by value tables, for example,

x −x
· ·
-2 2
-1 1
0 0
1 -1
2 -2
· ·

6
Logical expressions.

A logical expression (or “proposition”) P (p, q, · · ·) is a function

P : B × B × · · · × B −→ B .

For example,

P1 (p, q) ≡ p ∨ ¬q and P2 (p, q, r) ≡ p ∧ (q ∨ r)

are logical expressions.

Here
P1 : B × B −→ B ,
and
P2 : B × B × B −→ B .

7
The values of a logical expression can be listed in a truth table .

EXAMPLE :
p q ¬q p ∨ (¬q)
T T F T
T F T T
F T F F
F F T T

8
Analogously, arithmetic expressions such as

A1 (x, y) ≡ x + (−y) and A2 (x, y, z) ≡ x × (y + z)

can be considered as functions

A1 : R × R −→ R, and A2 : R × R × R −→ R ,

or, equivalently,

A1 : R2 −→ R, and A2 : R3 −→ R .

9
Two propositions are equivalent if they always have the same values.

EXAMPLE :

¬(p ∨ q) is equivalent to ¬p ∧ ¬q ,

(one of de Morgan’s laws), as can be seen in the table below :

p q p∨q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T

10
NOTE :

In arithmetic

−(x + y) is equivalent to (−x) + (−y) ,

i.e., we do not have that

−(x + y) is equivalent to (−x) × (−y) .

Thus the analogy between logic and arithmetic is limited.

11
The three basic logical operators ¬ , ∨ , and ∧ , are all we need.

However, it is very convenient to introduce some additional operators,

much like in arithmetic, where we write x3 to denote x × (x × x).

Three such additional operators are

⊕ “exclusive or”
→ “conditional” , “if then”
↔ “biconditional” , “if and only if” , “iff”
defined as :
p q p⊕q p→q p↔q
T T F T T
T F T F F
F T T T F
F F F T T

12
EXAMPLE :

Suppose two persons, P and Q, are suspected of committing a crime.

• Let P denote the statement by P that

“Q did it, or we did it together”.

• Let Q denote the statement by Q that

“P did it, or if I did it then we did it together”.

• Suppose we know P always tells the truth and Q always lies.

Who committed the crime ?

NOTE : By “did it” we mean “was involved”.

13
Let p denote “P did it” and let q denote “Q did it”.
Then p and q are logical variables.

We are given that the value of the logical expression

q ∨ (p ∧ q) is True ,
and that  
p ∨ q → (p ∧ q) is False .

Equivalently we have that the value of the logical expression

    
¬ p ∨ q → (p ∧ q) ∧ q ∨ (p ∧ q)
is True .

Our problem is to find for what values of p and q this is the case.

14
As an analogy from arithmetic, consider the problem of finding the values
of x and y in Z so that

the value of the arithmetic expression x2 + y is 5 ,

and such that

the value of x + y is 3 ,

i.e., we want to find all solutions of the the simultaneous equations

x2 + y = 5 , x+y =3 .

(How many solutions are there ?)

15
For the “crime problem” we have the truth table

    
p q ¬ p ∨ q → (p ∧q) ∧ q ∨ (p ∧ q)
T T F T T T F T T
T F F T T F F F F
F T T F F F T T F
F F F T T F F F F
(1) (2) (6) (5) (4) (3) (9) (8) (7)

The order of evaluation has been indicated at the bottom of the table.

The values of the entire expression are in column (9).

We observe that the expression is True only if p = F and q = T .

Therefore Q was involved in the crime, but P was not.

16
EXERCISE :

Consider the logical expression in the preceding “crime” example.

Find a much simpler, equivalent logical expression.

(It must have precisely the same values as listed in column “(9)”.)

17
EXERCISE :

Suppose three persons, P, Q, and R, are suspects in a crime.

• P states that “Q or R, or both, were involved”.

• Q states that “P or R, or both, were involved”.

• R states that “P or Q, but not both, were involved”.

• Suppose P and Q always tell the truth, while R always lies.

Who were involved in the crime ?

NOTE : there may be more than one solution · · ·

18
EXERCISE :

Construct a truth table for the logical expression

(p ∧ (¬(¬p ∨ q))) ∨ (p ∧ q) .

Based on the truth table find a simpler, equivalent logical expression.

19
A contradiction is a logical expression whose value is always False .
For example p ∧ ¬p is a contradiction :
p ¬p p ∧ ¬p
T F F
F T F

A tautology is a logical expression that is always True .

For example p ∨ ¬p is a tautology :
p ¬p p ∨ ¬p
T F T
F T T

A logical expression that is neither a tautology nor a contradiction

is called a contingency.

20
EXERCISE :

Verify by truth table that the following expressions are tautologies :

 
(p → q) ∧ p → q ,

 
(p → q) ∧ ¬q → ¬p .

21
NOTATION :

We use the symbol “⇒” to indicate that a conditional statement is a

tautology.

For example, from the preceding exercise we have

 
(p → q) ∧ p ⇒ q , (”modus ponens”) ,

 
(p → q) ∧ ¬q ⇒ ¬p , (”modus tollens”) .

22
As another example we show that
 
(p → q) ∧ (¬p → r) ∧ (q → r) → r
is a tautology.
 
p q r (p → q) ∧ (¬p → r) ∧ (q → r) → r
T T T T T F T T T T T
T T F T T F T F F T F
T F T F F F T F T T T
T F F F F F T F T T F
F T T T T T T T T T T
F T F T F T F F F T F
F F T T T T T T T T T
F F F T F T F F T T F
(1) (2) (3) (5) (9) (6) (7) (10) (8) (11) (4)

The last column (11) consist of True values only. Therefore we can write
 
(p → q) ∧ (¬p → r) ∧ (q → r) ⇒ r

QUESTION : Does it matter which of the two ∧’s is evaluated first?

23
EXAMPLE :
Here we illustrate another technique that can sometimes be used to show
that a conditional statement is a tautology.

Consider again the logical expression

P (p, q, r) ⇐⇒ (p → q) ∧ (¬p → r) ∧ (q → r) .

We want to show that

P (p, q, r) ⇒ r ,
i.e., that
P (p, q, r) → r always has value True .

NOTE : We need only show that:

We can’t have that P (p, q, r) is True , while r is False .

24
So suppose that P (p, q, r) is True , while r is False .

(We must show that this cannot happen ! )

Thus all three of

(a) p → q (b) ¬p → F and (c) q → F

have value True .

(c) can only have value True if q = F .

(b) can only have value True if ¬p = F , i.e., if p = T .

But then (a) becomes T → F which has value F .

So indeed, not all three, (a), (b), and (c) can have value True .

QED ! (“quod erat demonstrandum”: “which was to be shown”)

25
NOTE :

This was an example of a proof by contradiction.

(We will give more examples later · · · )

26
EXERCISE :

Use a proof “by contradiction” to prove the following:

 
(p → q) ∧ p ⇒ q ,

 
(p → q) ∧ ¬q ⇒ ¬p .

(Already done by truth table.)

27
EXERCISE :

Also use a ”direct proof” to prove that

 
(p → q) ∧ p ⇒ q ,

 
(p → q) ∧ ¬q ⇒ ¬p .

(In a direct proof one assumes that the LHS is True and then one shows
that the RHS must be True also.)

28
NOTATION :

From the definition of the ↔ operator we see that logical expressions

P1 (p, q, · · ·) and P2 (p, q, · · ·) ,

are equivalent if and only if

P1 (p, q, · · ·) ↔ P2 (p, q, · · ·)
is a tautology.

In this case we write

P1 (p, q, · · ·) ⇐⇒ P2 (p, q, · · ·) .

29
EXAMPLE :

¬(p ∧ q) is equivalent to ¬p ∨ ¬q ,

i.e.,

¬(p ∧ q) ⇐⇒ (¬p ∨ ¬q) ,

as seen in the truth table

p q ¬ (p ∧ q) ↔ (¬p ∨ ¬q)
T T F T T F F F
T F T F T F T T
F T T F T T T F
F F T F T T T T

30
The operators

⊕ , → , and ↔ ,

can be expressed in terms of the basic operators

¬ , ∧ , and ∨ ,

as verified below :

 
p q (p ⊕ q) ↔ (p ∨ q) ∧ ¬ (p ∧ q)
T T F T T F F T
T F T T T T T F
F T T T T T T F
F F F T F F T F

31
 p q (p → q) ↔ (q ∨ ¬p)
T T T T T F
T F F T F F
F T T T T T
F F T T T T

 
p q (p ↔ q) ↔ (q ∨ ¬p) ∧(p ∨ ¬q)
T T T T T T T F
T F F T F F T T
F T F T T F F F
F F T T T T T T

32
Thus we can write

p ⊕ q ⇐⇒ (p ∨ q) ∧ ¬(p ∧ q) ,

p → q ⇐⇒ q ∨ ¬p ,

p ↔ q ⇐⇒ (q ∨ ¬p) ∧ (p ∨ ¬q) .

It also follows that

p ↔ q ⇐⇒ (p → q) ∧ (q → p) .

33
Basic logical equivalences.

The fundamental logical equivalences (“laws”) are :

p ∨ q ⇐⇒ q ∨ p p ∧ q ⇐⇒ q ∧ p commutative law

p ∨ (q ∧ r) ⇐⇒ p ∧ (q ∨ r) ⇐⇒
(p ∨ q) ∧ (p ∨ r) (p ∧ q) ∨ (p ∧ r) distributive law

p ∨ F ⇐⇒ p p ∧ T ⇐⇒ p identity law

p ∨ ¬p ⇐⇒ T p ∧ ¬p ⇐⇒ F complement law

34
Some useful additional laws are :

¬T ⇐⇒ F ¬F ⇐⇒ T negation law

p ∨ p ⇐⇒ p p ∧ p ⇐⇒ p idempotent law

p ∨ T ⇐⇒ T p ∧ F ⇐⇒ F domination law

p ∨ (p ∧ q) ⇐⇒ p p ∧ (p ∨ q) ⇐⇒ p absorption law

NOTE : Remember the absorption laws : they can be very useful !

35
Some more laws are :

(p ∨ q) ∨ r ⇐⇒ p ∨ (q ∨ r) (p ∧ q) ∧ r ⇐⇒ p ∧ (q ∧ r) associative law

¬(p ∨ q) ⇐⇒ ¬p ∧ ¬q ¬(p ∧ q) ⇐⇒ ¬p ∨ ¬q de Morgan

¬(¬p) ⇐⇒ p double negation

p → q ⇐⇒ ¬q → ¬p contrapositive

36
• All laws of logic can in principle be proved using truth tables.

• To illustrate the axiomatic nature of the fundamental laws,

we prove an additional law using only the fundamental laws.

• At every step the fundamental law used will be indicated.

• Once proved, additional laws may be used in further proofs.

37
EXAMPLE : Proof of the idempotent law

p ∨ p ⇐⇒ p

p ⇐⇒ p∨F identity law

⇐⇒ p ∨ (p ∧ ¬p) complement law

⇐⇒ (p ∨ p) ∧ (p ∨ ¬p) distributive law

⇐⇒ (p ∨ p) ∧ T complement law

⇐⇒ p∨p identity law

38
NOTE :

• Proving additional laws, using only the fundamental laws, is not as

easy as one might expect, because we have very few tools available.

• However after proving some of these additional equivalences we

have a more powerful set of laws.

39
Simplification of logical expressions.

It is useful to simplify logical expressions as much as possible.

This is much like in arithmetic where, for example, the expression

x3 + 3x2 y + 3xy 2 + y 3
is equivalent to
(x + y)3 .

40
EXAMPLE : Reconsider the logical expression
    
¬ p ∨ q → (p ∧ q) ∧ q ∨ (p ∧ q)

from the “crime example”.

It is equivalent to the much simpler logical expression

¬p ∧ q ,
because it has the same truth table values :

p q ¬p ¬p ∧ q
T T F F
T F F F
F T T T
F F T F

41
One way to simplify a logical expression is by using

• the fundamental laws of logic,

• known additional laws,

• the definitions of the additional logical operators.

For the “crime example” this can be done as follows :

42
     
¬ p ∨ q → (p ∧ q) ∧ q ∨ (p ∧ q)
    
⇐⇒ ¬ p ∨ q → (p ∧ q) ∧ q ∨ (q ∧ p) commutative law
  
⇐⇒ ¬ p ∨ q → (p ∧ q) ∧ q absorption law
  
⇐⇒ ¬ p ∨ (p ∧ q) ∨ ¬q ∧ q equivalence of →
  
⇐⇒ ¬ p ∨ (p ∧ q) ∨ ¬q ∧ q associative law
 
⇐⇒ ¬ p ∨ ¬q ∧ q absorption law

⇐⇒ ···

43
  
¬ p ∨ ¬q ∧ q
 
⇐⇒ ¬p ∧ ¬¬q ∧ q de Morgan
 
⇐⇒ ¬p ∧ q ∧ q double negation
 
⇐⇒ ¬p ∧ q ∧ q associative law

⇐⇒ ¬p ∧ q idempotent law

44
EXERCISE :

Use logical equivalences to simplify the logical expression

(p ∧ (¬(¬p ∨ q))) ∨ (p ∧ q) .

(This example was already considered before, using a truth table.)

EXERCISE :

Use logical equivalences to verify the following equivalence:

(¬p ∧ q) ∨ (¬q ∧ p) ⇐⇒ (p ∨ q) ∧ ¬(p ∧ q) .

(This was considered before in connection with the ⊕ operator.)

45
EXERCISE :

Use logical equivalences to show that the logical expression

 
(p → q) ∧ (¬p → r) ∧ (q → r) → r ,

is a tautology, i.e., show that

 
(p → q) ∧ (¬p → r) ∧ (q → r) ⇒ r .

NOTE : Earlier we proved this by truth table and by contradiction.

46
Predicate Calculus.

Let S be a set.

A predicate P is a function from S to {T , F } :

P : S −→ {T , F } ,
or
P : S × S × · · · × S −→ {T , F } .
or
P : S1 × S2 × · · · × Sn −→ {T , F } .

47
EXAMPLE : Let Z+ denote the set of all positive integers.
Define
P : Z+ −→ {T , F }
by
P (x) = T if x ∈ Z+ is even ,

P (x) = F if x ∈ Z+ is odd .

We can think of P (x) as the statement

“x is an even integer”,

which can be either True or False .

• What are the values of P (12), P(37), P(-3) ?

48
EXAMPLE :

Let U be a set and S a subset of U .

Let P (x) denote the statement “x ∈ S”, i.e.,

P (x) ⇐⇒ x ∈ S .

Then
P : U −→ {T , F } .

49
EXAMPLE :

Let P (x, y) denote the statement “x + y = 5”, i.e.,

P (x, y) ⇐⇒ x + y = 5 .

Then we can think of P as a function

P : Z+ × Z+ −→ {T , F } .

50
Quantifiers.

For a more compact notation we introduce the quantifiers

∀, ∃, and ∃!

DEFINITIONS : Let S be a set and P a predicate, P : S −→ {T , F } .

Then we define :

∀x ∈ S P (x) means “ P (x) = T for all x ∈ S ”.

∃x ∈ S P (x) means “ there exists an x ∈ S for which P (x) = T ”.

∃!x ∈ S P (x) means “ there is a unique x ∈ S for which P (x) = T ”.

51
If it is clear from the context what S is, then one often simply writes

∀x P (x) , ∃x P (x) , ∃!x P (x) .

If S has a finite number of elements then

∀x P (x) ⇐⇒ P (x1 ) ∧ P (x2 ) ∧ · · · ∧ P (xn )

∃x P (x) ⇐⇒ P (x1 ) ∨ P (x2 ) ∨ · · · ∨ P (xn )

and
 
∃!x P (x) ⇐⇒ P (x1 ) ∧ ¬P (x2 ) ∧ ¬P (x3 ) ∧ ¬ · · · ∧ ¬P (xn )
 
∨ ¬P (x1 ) ∧ P (x2 ) ∧ ¬P (x3 ) ∧ ¬ · · · ∧ ¬P (xn )
∨
··· 
∨ ¬P (x1 ) ∧ ¬P (x2 ) ∧ ¬P (x3 ) ∧ ¬ · · · ∧ P (xn )

52
Let S be a set and

P : S × S −→ {T , F } .

Then
∀x, y P (x, y) and ∀x∀y P (x, y)

both mean  
∀x ∀yP (x, y) .

Thus ∀x, y P (x, y) means

“P (x, y) is True for any choice of x and y ”.

53
Similarly,

∃x, y P (x, y) and ∃x∃y P (x, y)

both mean  
∃x ∃yP (x, y) .

Thus ∃x, y P (x, y) means

“There exist an x and y for which P (x, y) is True ”.

54
EXAMPLE :

Let
P : S × S −→ {T , F } ,
where
S = {1, 2} .

Then

∀x, y P (x, y) ⇐⇒ P (1, 1) ∧ P (1, 2) ∧ P (2, 1) ∧ P (2, 2) ,

while

∃x, y P (x, y) ⇐⇒ P (1, 1) ∨ P (1, 2) ∨ P (2, 1) ∨ P (2, 2) .

55
EXERCISE : Let

P : Z × Z −→ {T , F } ,

where P (x, y) denotes

“ x + y = 5 ”.

What are the values of the following propositions ?

∀x, y P (x, y)

∃x, y P (x, y)

∀x ∃!y P (x, y)

∃x ∀y P (x, y)

56
EXERCISE : Let

P : Z+ × Z+ × Z+ −→ {T , F } ,

where P (x, y, z) denotes the statement

“ x2 + y 2 = z ”.
What are the values of the following propositions?
∃x, y, z P (x, y, z)

∀x, y, z P (x, y, z)

∀x, y ∃z P (x, y, z)

∀x, z ∃y P (x, y, z)

∀z ∃x, y P (x, y, z)

57
EXAMPLE :

Let
P, Q : S −→ {T , F } ,
where
S = {1, 2} .

Then
     
∀x P (x) ∨ Q(x) ⇐⇒ P (1) ∨ Q(1) ∧ P (2) ∨ Q(2) ,

while
 
∀x, y P (x) ∨ Q(y) ⇐⇒

       
P (1)∨Q(1) ∧ P (1)∨Q(2) ∧ P (2)∨Q(1) ∧ P (2)∨Q(2) .

58
EXERCISE : ( see preceding example · · · ):

Show that
 
∀x P (x) ∨ Q(x)

is not equivalent to
 
∀x, y P (x) ∨ Q(y)

Hint: Take S = {1, 2} , and find predicates P and Q so that one of the
propositions is True and the other one False .

59
EXAMPLE : If
P, Q : S −→ {T , F } ,
where
S = {1, 2} ,
then
     
∃x P (x) ∧ Q(x) ⇐⇒ P (1) ∧ Q(1) ∨ P (2) ∧ Q(2) .

EXAMPLE : If again
P, Q : S −→ {T , F } ,
and
S = {1, 2} ,
then
     
∀x P (x) → Q(x) ⇐⇒ P (1) → Q(1) ∧ P (2) → Q(2)
   
⇐⇒ ¬P (1) ∨ Q(1) ∧ ¬P (2) ∨ Q(2) .

60
EXAMPLE :

     
∀xP (x) ∨ ∀xQ(x) ⇐⇒
6 ∀x P (x) ∨ Q(x)

i.e., there are predicates P and Q for which the equivalence not valid.

As a counterexample take

P, Q : Z+ −→ {T , F } ,

where
P (x) ⇐⇒ “x is even” , and Q(x) ⇐⇒ “x is odd” .

Then the RHS is True but the LHS is False .

61
EXERCISE :

Show that

     
∃xP (x) ∧ ∃xQ(x) 6
⇐⇒ ∃x P (x) ∧ Q(x)

by giving an example where LHS and RHS have a different logical value.

62
Some equivalences (Valid for any propositions P and Q) :

   
(1) ¬ ∃xP (x) ⇐⇒ ∀x ¬P (x)

     
(2) ∀xP (x) ∧ ∀xQ(x) ⇐⇒ ∀x P (x) ∧ Q(x)

     
(3) ∀xP (x) ∧ ∀xQ(x) ⇐⇒ ∀x∀y P (x) ∧ Q(y)

     
(4) ∀xP (x) ∨ ∀xQ(x) ⇐⇒ ∀x∀y P (x) ∨ Q(y)

63
EXAMPLE : Proof of Equivalence (1) when the set S is finite .

   
¬ ∃xP (x) ⇐⇒ ¬ P (x1 ) ∨ P (x2 ) ∨ · · · ∨ P (xn )
  
⇐⇒ ¬ P (x1 ) ∨ P (x2 ) ∨ · · · ∨ P (xn )
 
⇐⇒ ¬P (x1 ) ∧ ¬ P (x2 ) ∨ · · · ∨ P (xn )

⇐⇒ ···

⇐⇒ ¬P (x1 ) ∧ ¬P (x2 ) ∧ ¬ · · · ∧ ¬P (xn )

⇐⇒ ∀x¬P (x)

64
EXERCISES :

These equivalences are easily seen to be valid:

• Prove Equivalence 2 :
     
∀xP (x) ∧ ∀xQ(x) ⇐⇒ ∀x P (x) ∧ Q(x)

• Prove Equivalence 3 :
     
∀xP (x) ∧ ∀xQ(x) ⇐⇒ ∀x∀y P (x) ∧ Q(y)

65
EXAMPLE : Proof of Equivalence (4) .

     
∀xP (x) ∨ ∀xQ(x) ⇐⇒ ∀x∀y P (x) ∨ Q(y)

NOTE : A correct proof consist of verifying that

LHS ⇒ RHS and RHS ⇒ LHS

or equivalently

LHS ⇒ RHS and ¬ LHS ⇒ ¬ RHS

66
PROOF :
     
(i) ∀xP (x) ∨ ∀xQ(x) ⇒ ∀x∀y P (x) ∨ Q(y)

is easily seen to be True by a direct proof (with 2 cases).

h   i  
(ii) ¬ ∀xP (x) ∨ ∀xQ(x) ⇒ ¬∀x∀y P (x) ∨ Q(y)

can be rewritten as
     
∃x¬P (x) ∧ ∃x¬Q(x) ⇒ ∃x∃y ¬P (x) ∧ ¬Q(y)

P and Q being arbitrary, we may replace them by ¬P and ¬Q :

     
∃xP (x) ∧ ∃xQ(x) ⇒ ∃x∃y P (x) ∧ Q(y)

which is easily seen to be True by a direct proof.

QED !

67
EXERCISE :

Prove that the equivalence

     
∀xP (x) ∧ ∃xQ(x) ⇐⇒ ∀x∃y P (x) ∧ Q(y)

is valid for all propositions P and Q.

Hint : This proof can be done along the lines of the preceding proof.

68
More equivalences (Valid for any propositions P and Q) :

 
(5) ¬ ∀xP (x) ⇐⇒ ∃x¬P (x)

     
(6) ∃xP (x) ∨ ∃xQ(x) ⇐⇒ ∃x P (x) ∨ Q(x)

     
(7) ∃xP (x) ∨ ∃xQ(x) ⇐⇒ ∃x∃y P (x) ∨ Q(y)

     
(8) ∃xP (x) ∧ ∃xQ(x) ⇐⇒ ∃x∃y P (x) ∧ Q(y)

69
Equivalences (5)-(8) follow from

• negating equivalences (1)-(4), and

• replacing P by ¬P and Q by ¬Q ..

70
EXAMPLE : Proof of Equivalence (6), using Equivalence (2)

     
(2) ∀xP (x) ∧ ∀xQ(x) ⇐⇒ ∀x P (x) ∧ Q(x)

     
¬ ∀xP (x) ∧ ∀xQ(x) ⇐⇒ ¬∀x P (x) ∧ Q(x)

     
∃x¬P (x) ∨ ∃x¬Q(x) ⇐⇒ ∃x ¬P (x) ∨ ¬Q(x)

     
(6) ∃xP (x) ∨ ∃xQ(x) ⇐⇒ ∃x P (x) ∨ Q(x)

71
EXERCISE :

• Prove Equivalence 7 using Equivalence 3.

• Prove Equivalence 8 using Equivalence 4.

72
EXAMPLE (of negating a logical expression) :

  
¬∃x∀y∀zP (x, y, z) ⇐⇒ ∀x¬ ∀y ∀zP (x, y, z)

 
⇐⇒ ∀x∃y¬ ∀zP (x, y, z)

⇐⇒ ∀x∃y∃z¬P (x, y, z)

73
EXAMPLE (of transforming a logical expression) :

   
∃x P (x) → Q(x) ⇐⇒ ∃x ¬P (x) ∨ Q(x)
   
⇐⇒ ∃x¬P (x) ∨ ∃xQ(x) ⋆
   
⇐⇒ ¬∀xP (x) ∨ ∃xQ(x)
   
⇐⇒ ∀xP (x) → ∃xQ(x)

⋆ This step follows from the earlier Equivalence 6.

74
EXAMPLE : (from Rosen’s book: in detail)

Let

D(x) denote the statement “x is a duck”

P (x) ,, “x is one of my poultry”

O(x) ,, “x is an officer”

W (x) ,, “x is willing to waltz”

75
 Statement logic equivalent
   
Ducks never waltz ¬∃x D(x) ∧ W (x) ∀x (D(x) → ¬W (x)

   
Officers always waltz ¬∃x (O(x) ∧ ¬W (x) ∀x (O(x) → W (x)

   
All my poultry are ducks ∀x (D(x) ∨ ¬P (x) ∀x (P (x) → D(x)

   
My poultry are not officers ∀x¬ O(x) ∧ P (x) ∀x (P (x) → ¬O(x)

QUESTION : Do the first three statements imply the last one?

76
Do the first three statements imply the last one, i.e., is

h     i
∀x(D(x) → ¬W (x)) ∧ ∀x(O(x) → W (x)) ∧ ∀x(P (x) → D(x))
 
→ ∀x(P (x) → ¬O(x))

a tautology, i.e., do we have

h     i
∀x(D(x) → ¬W (x)) ∧ ∀x(O(x) → W (x)) ∧ ∀x(P (x) → D(x))
 
⇒ ∀x(P (x) → ¬O(x))

The answer is YES .

In fact, it is a tautology for any predicates D, O, P , W .

77
h     i
∀x(D(x) → ¬W (x)) ∧ ∀x(O(x) → W (x)) ∧ ∀x(P (x) → D(x))
(1) (2) (3)
 
⇒ ∀x(P (x) → ¬O(x))
(4)

To prove this, we must show that :

if (1) , (2) , and (3) are True then (4) is True .

To show (4) is True , we must show:

If, for arbitrary z, P (z) is True then, using (1,2,3), ¬O(z) is True .

78
h     i
∀x(D(x) → ¬W (x)) ∧ ∀x(O(x) → W (x)) ∧ ∀x(P (x) → D(x))
(1) (2) (3)
 
⇒ ∀x(P (x) → ¬O(x))
(4)

PROOF : Let z be an arbitrary element from our set of objects.

Assume P (z) is True .

We must show that ¬O(z) is True , i.e., O(z) is False .

From (3) it follows D(z) is True .

From (1) follows ¬W (z) is True . i.e., W (z) is False .

From (2), since W (z) is False , it follows O(z) is False . QED !

79
EXERCISE (from Rosen):

Express each of the following using predicates and quantifiers:

(1) All clear explanations are satisfactory.

(2) Some excuses are unsatisfactory.

(3) Some excuses are not clear explanations.

Question : Does (3) follow from (1) and (2) ?

Hint : See preceding example.

80
 REVIEW EXERCISES.

Problem 1. By truth table check if the ⊕ operator is associative:

(p ⊕ q) ⊕ r ⇐⇒ p ⊕ (q ⊕ r) .

Problem 2. Use logical equivalences to prove that

p → (q → r) ⇐⇒ (p ∧ q) → r .

Problem 3. By contradiction show that the following is a tautology:

[(p ∨ t) ∧ (p → q) ∧ (q → r) ∧ (r → s) ∧ (s → t)] → t .

Problem 4. Use logical equivalences to simplify

([(p ∧ q) ↔ p] → p) → (p → q) .

81
Problem 5. Verify the following basic tautologies, which are known as
“laws of inference”, and which are useful in proofs:

Tautology Name

(p ∧ (p → q)) ⇒ q modus ponens

(¬q ∧ (p → q)) ⇒ ¬p modus tollens

((p → q) ∧ (q → r)) ⇒ (p → r) hypothetical syllogism

((p ∨ q) ∧ ¬p) ⇒ q disjunctive syllogism

((p ∨ q) ∧ (¬p ∨ r)) ⇒ (q ∨ r) resolution

82
Problem 6. Express the following statements in predicate logic:

(a) “There is a unique x for which P (x) is True .”

(b) “There is no greatest integer.”

(c) “x0 is the smallest integer for which P (x) is True .”

(d) “Every person has exactly two parents.”

NOTE :

- Let P (x, y) denote “y is a parent of x ” .

- You may use the predicates x ≤ y , x > y , and x 6= y .

83
Problem 7.

Let P (x, y, z) denote the statement

x2 y = z ,

where the universe of discourse of all three variables is the set Z.

What is the truth value of each of the following?

P (1, 1, 1) ∀y, z∃xP (x, y, z)

P (0, 7, 0) ∃!y, z∀xP (x, y, z)

∀x, y, zP (x, y, z) ∀x, y∃zP (x, y, z)

∃x, y, zP (x, y, z) ∀x∃y, zP (x, y, z)

84
Problem 8.
Let P (x, y, z, n) denote the statement

xn + y n = z n ,

where x, y, z, n ∈ Z+ .

What is the truth value of each of the following:

P (1, 1, 2, 1) ∀x, y∃!zP (x, y, z, 1)

P (3, 4, 5, 2) ∀z∃x, yP (x, y, z, 1)

P (7, 24, 25, 2) ∃x, y∀zP (x, y, z, 2)

∃!x, y, zP (x, y, z, 2) ∃x, y, zP (x, y, z, 3)

NOTE : One of the above is very difficult!

85
Problem 9.
Give an example that shows that

∀x∃yP (x, y) ⇐⇒
6 ∃y∀xP (x, y) .

Problem 10.
Prove that

∀x[P (x) → Q(x)] ⇒ [∀xP (x) → ∀xQ(x)].

Problem 11.
Prove that

∀x∃y(P (x) ∨ Q(y)) ⇐⇒ ∀xP (x) ∨ ∃xQ(x) .

86
 MATHEMATICAL PROOFS.

• We will illustrate some often used basic proof techniques .

(Some of these techniques we have already seen · · · )

• Several examples will be taken from elementary Number Theory.

87
DEFINITIONS : Let n, m ∈ Z+ .

• We call n odd if ∃k ∈ Z : k ≥ 0, n = 2k + 1.
• We call n even if n is not odd. (Then n = 2k for some k ∈ Z+ .)

• We say “m divides n”, and write m|n, if n = qm for some q ∈ Z+ .

• In this case we call m a divisor of n.
• If m|n then we also say that “n is divisible by m”.

• n (n ≥ 2) is a prime number if its only positive divisors are 1 and n.

• n (n ≥ 2) composite if it is not prime.
• n and m are relatively prime if 1 is their only common divisor.

88
Direct proofs.

Many mathematical statements have the form

“ if P then Q ”
i.e.,
P ⇒ Q,
or, more often,  
∀x P (x) → Q(x) ,

where P and Q represent specific predicates .

RECALL : a direct proof consists of

• assuming that, for arbitrary x, P (x) is True

• demonstrating that Q(x) is then necessarily True also,

89
PROPOSITION : If n ∈ Z+ is odd then n2 is odd.

REMARK :
This proposition is of the form P ⇒ Q or, more specifically,

∀n ∈ Z+ : P (n) → Q(n) ,

where P and Q are predicates (functions)

P, Q : Z+ −→ {T , F } ,
namely,

P (n) ⇐⇒ ”n is odd ” , Q(n) ⇐⇒ ”n2 is odd ” .

NOTE : Actually Q(n) ⇐⇒ P (n2 ) here !

90
 If n ∈ Z+ is odd then n2 is odd.

PROOF :

Assume n ∈ Z+ is odd (i.e., assume P (n) = T ).

Then, by definition, n = 2k + 1 for some k ∈ Z, k ≥ 0.

By computation we find

n2 = (2k + 1)2 = 2(2k2 + 2k) + 1 = 2m + 1 ,

where we have defined m ≡ 2k2 + 2k.

Thus, by definition, n2 is odd, i.e., Q(n) = T . QED !

91
PROPOSITION : If n ∈ Z+ is odd then 8 | (n − 1)(n + 1) .

PROOF : If n ∈ Z+ is odd then we can write

n = 2k + 1 for some integer k, k ≥ 0 .

By computation we find

(n − 1)(n + 1) = n2 − 1 = 4k2 + 4k = 4k(k + 1) .

Clearly
4 | 4k(k + 1) .
Note, however, that either k is even or k + 1 is even, i.e.,

2|k or 2 | (k + 1) .

Thus
8 | 4k(k + 1) . QED !

92
LEMMA (Needed in the following example · · ·) For x ∈ R , x 6= 0, 1 :
n
X 1 − xn+1
xk = , ∀n ≥ 0 , ( Geometric sum ) .
k=0
1−x

PROOF ( a ”constructive proof” ) :

Let n
X
Sn = xk .
k=0
Then
Sn = 1 + x + x2 + · · · + xn−1 + xn ,

x · Sn = x + x2 + · · · + xn−1 + xn + xn+1 ,
so that
Sn − x · Sn = (1 − x) · Sn = 1 − xn+1 ,

from which the formula follows. QED !

93
DEFINITION :

A perfect number is a number that equals the sum of all of its divisors,
except the number itself.

EXAMPLES :

6 is perfect :
6 = 3 + 2 + 1,

and 28 is perfect :

28 = 14 + 7 + 4 + 2 + 1 ,

and so is 496 :

496 = 248 + 124 + 62 + 31 + 16 + 8 + 4 + 2 + 1 .

94
PROPOSITION : Let m ∈ Z+ , m > 1.

If 2m − 1 is prime, then n ≡ 2m−1 (2m − 1) is perfect,

or, using quantifiers,

∀m ∈ Z+ : 2m − 1 is prime → 2m−1 (2m − 1) is perfect .

PROOF : Assume 2m − 1 is prime.

Then the divisors of n = 2m−1 (2m − 1) are

1, 2, 22 , 23 , · · · , 2m−1 ,
and
(2m − 1), 2(2m − 1), 22 (2m − 1), · · · , 2m−2 (2m − 1), 2m−1 (2m − 1) .

The last divisor is equal to n , so we do not include it in the sum.

95
The sum is then

m−1 m−2
X
k m
X
k 1 − 2m m 1 − 2m−1
2 + (2 − 1) 2 = + (2 − 1)
k=0 k=0
1−2 1−2

= (2m − 1) + (2m − 1)(2m−1 − 1)

= (2m − 1) (1 + 2m−1 − 1)

= (2m − 1) 2m−1 = n. QED !

NOTE : We used the formula

m
X
k 1 − xm+1
x = , (the geometric sum) ,
k=0
1−x

(valid for x 6= 0, 1).

96
Proving the contrapositive.

It is easy to see (by Truth Table) that

p→q ⇐⇒ ¬q → ¬p .

EXAMPLE :

The statement

“n2 even ⇒ n even”,

proved earlier is equivalent to

“¬(n even) ⇒ ¬(n2 even)”,

i.e., it is equivalent to

n odd ⇒ n2 odd .

97
This equivalence justifies the following :

If we must prove

P ⇒ Q,

then we may equivalently prove the contrapositive

¬Q ⇒ ¬P .

(Proving the contrapositive is sometimes easier .)

98
PROPOSITION : Let n ∈ Z+ , with n ≥ 2.

If the sum of the divisors of n is equal to n + 1 then n is prime.

PROOF : We prove the contrapositive :

If n is not prime then the sum of the divisors can not equal n + 1.

So suppose that n is not prime.

Then n has divisors

1, n, and m, for some m ∈ Z+ , m 6= 1, m 6= n ,
and possibly more.

Thus the sum of the divisors is greater than n + 1. QED !

99
Some specific contrapositives.

(p ∧ q) → r ⇐⇒ ¬r → (¬p ∨ ¬q)

(p ∨ q) → r ⇐⇒ ¬r → (¬p ∧ ¬q)
   
∀xP (x) → q ⇐⇒ ¬q → ∃x¬P (x)
   
∃xP (x) → q ⇐⇒ ¬q → ∀x¬P (x)
 
p → ∀xQ(x) ⇐⇒ ∃x¬Q(x) → ¬p
 
p → ∃xQ(x) ⇐⇒ ∀x¬Q(x) → ¬p

100
PROPOSITION : Let n ∈ Z+ , with n ≥ 2.

∀a, b ∈ Z+ ( n|a ∨ n|b ∨ n 6 |ab ) ⇒ n is prime .

PROOF : The contrapositive is

If n is not prime then ∃a, b ( n 6 |a ∧ n 6 |b ∧ n|ab ) .

Here the contrapositive is easier to understand and quite easy to prove :

Note that if n is not prime then

n = ab,
for certain integers a and b, both greater than 1 and less than n.

Clearly n 6 |a , n 6 |b , and n|ab . QED !

101
PROPOSITION : Let n ∈ Z+ . Then
5|n2 ⇒ 5|n ,

PROOF : We prove the contrapositive , i.e.,

5 6 |n ⇒ 5 6 |n2 .
So suppose 5 6 |n.

Then we have the following cases :

n = 5k + 1 ⇒ n2 = 25k2 + 10k + 1 = 5(5k2 + 2k) + 1 ,
n = 5k + 2 ⇒ n2 = 25k2 + 20k + 4 = 5(5k2 + 4k) + 4 ,
n = 5k + 3 ⇒ n2 = 25k2 + 30k + 9 = 5(5k2 + 6k + 1) + 4 ,
n = 5k + 4 ⇒ n2 = 25k2 + 40k + 16 = 5(5k2 + 8k + 3) + 1 ,
for k ∈ Z, k ≥ 0.

This shows that 5 6 |n2 . QED !

102
Proof by contradiction.

To prove a statement P ⇒ Q by contradiction :

• assume P = T and Q = F ,

• show that these assumptions lead to an impossible conclusion

(a “contradiction”).

(We have already seen some proofs by contradiction.)

103
PROPOSITION :

If a prime number is the sum of two prime numbers

then one of these equals 2.

PROOF :

Let p1 , p2 , and p be prime numbers, with p1 + p2 = p.

Suppose that neither p1 nor p2 is equal to 2.

Then both p1 and p2 must be odd ( and greater than 2 ) .

Hence p = p1 + p2 is even, and greater than 2.

This contradicts that p is prime. QED !

104
 √ + m
√
PROPOSITION : 2 is irrational, i.e., if m, n ∈ Z then n
6= 2.
+ m
√
PROOF : Suppose m, n ∈ Z and n = 2.
We may assume m and n are relatively prime (cancel common factors).
√
Then m = 2n ⇒ m2 = 2n2 *
⇒ m2 even
⇒ m even (proved earlier)
⇒ ∃k ∈ Z+ (m = 2k)
⇒ 2n2 = m2 = (2k)2 = 4k2 (using * above)
⇒ n2 = 2k2
⇒ n2 even
⇒ n even
Thus both n and m are even and therefore both are divisible by two.
This contradicts that they are relatively prime. QED !
NOTATION : The “⇒” means that the immediately following state-
ment is implied by the preceding statement(s).

105
EXERCISE :

Use a proof by contradiction to show the following:

(p ∨ q) ∧ (p → r) ∧ (q → r) ⇒ r .

(p → q) ∧ (q → r) ⇒ p → r .

Hint : See a similar example earlier in the Lecture Notes.

106
PROPOSITION :

If the integers
1, 2, 3, · · · , 10,

are placed around a circle, in any order, then there exist three integers
in consecutive locations around the circle that have a sum greater than
or equal to 18.

107
PROOF : (by contradiction)

Suppose any three integers in consecutive locations around the circle

have sum less than 18, that is, less then or equal to 17.

Excluding the number 1, which must be placed somewhere, there remain

exactly three groups of three integers in consecutive locations.

The total sum is then less than or equal to 1 + 17 + 17 + 17 = 52.

However, we know that this sum must equal

1 + 2 + 3 + · · · + 10 = 55 .

Hence we have a contradiction. QED !

108
Proof by cases (another example) :

PROPOSITION : Let n ∈ Z+ . Then

6 | n(n + 1)(n + 2) .

PROOF : We always have that 2|n or 2|(n + 1) . (Why ?)

There remain three cases to be considered :

For some k ∈ Z+ , k ≥ 0 :
n = 3k : Then 3|n ,

n = 3k + 1 : Then 3|(n + 2) ,

n = 3k + 2 : Then 3|(n + 1) .
QED !

109
FACT : Any real number x can be uniquely written as
x = n + r,
where
n ∈ Z and r ∈ R , with 0 ≤ r < 1 .

DEFINITION : We then define the floor of x as

⌊x⌋ ≡ n .

EXAMPLES : ⌊7⌋ = 7 , ⌊−7⌋ = −7 , ⌊π⌋ = 3 , ⌊−π⌋ = −4 .

EXAMPLE : Use a proof by cases to show that

1
⌊2x⌋ = ⌊x⌋ + ⌊x + ⌋ .
2

110
 ⌊2x⌋ = ⌊x⌋ + ⌊x + 21 ⌋ , x = n + r , 0 ≤ r < 1

PROOF :
1
Case 1 : 0 ≤ r < 2
: Then
1 1
0 ≤ 2r < 1 and ≤ r+ < 1.
2 2

LHS : ⌊2x⌋ = ⌊2n + 2r⌋ = 2n

RHS : ⌊x⌋ = ⌊n + r⌋ = n

1 1
⌊x + ⌋ = ⌊n + r + ⌋ = n
2 2

so that the identity is satisfied.

111
 ⌊2x⌋ = ⌊x⌋ + ⌊x + 21 ⌋ , x = n + r , 0 ≤ r < 1

PROOF : (continued · · · )
1
Case 2 : 2
≤ r < 1 : Then
1 1
1 ≤ 2r < 2 and 1 ≤ r+ < 1 + .
2 2

LHS : ⌊2x⌋ = ⌊2n + 2r⌋ = 2n + 1

RHS : ⌊x⌋ = ⌊n + r⌋ = n

1 1
⌊x + ⌋ = ⌊n + r + ⌋ = n + 1
2 2

so that the identity is satisfied. QED !

112
Existence proofs.

• Mathematical problems often concern the existence, or non-existence,

of certain objects.

• Such problems may arise from the mathematical formulation of

problems that arise in many scientific areas.

• A proof that establishes the existence of a certain object is called

an existence proof.

113
EXAMPLE : For any positive integer n there exists a sequence
of n consecutive composite integers , i.e.,

∀n ∈ Z+ ∃m ∈ Z+ : m + i is composite , i = 1, · · · , n .

For example,

n = 2 : (8,9) are 2 consecutive composite integers (m = 7),

n = 3 : (8,9,10) are 3 three consecutive composite integers (m = 7),

n = 4 : (24,25,26,27) are 4 consecutive composite integers (m = 23),

n = 5 : (32,33,34,35,36) are 5 consecutive composite integers (m = 31).

114
 ∀n ∈ Z+ ∃m ∈ Z+ : m + i is composite , i = 1, · · · , n .

PROOF :

Let m = (n + 1)! + 1.

Then, clearly, the n consecutive integers

(n + 1)! + 1 + 1, (n + 1)! + 1 + 2, ···, (n + 1)! + 1 + n ,

are composite. (Why ?) QED !

NOTE : This is a constructive existence proof : We demonstrated

the existence of m by showing its value (as a function of n).

115
PROPOSITION : There are infinitely many prime numbers.

The idea of the proof (by contradiction) :

• Assume there is only a finite number of prime numbers.

• Then we’ll show ∃N > 1 ∈ Z+ that is neither prime nor composite .

• But this is impossible !

• Thus there must be infinitely many prime numbers !

116
PROOF :

Suppose the total number of primes is finite , say,

p1 , p2 , · · · , pn .

Let
N = p1 p2 · · · pn + 1

• Then N cannot be prime. (Why not ?)

• Also, none of the p1 , p2 , · · · , pn divide N ,

since N divided by pi gives a remainder of 1 , (i = 1, · · · , n) .

• Thus N cannot be composite either ! QED !

117
NOTE :

• This proof is a non-constructive existence proof.

• We proved the existence of an infinite number of primes

without actually showing them !

118
NOTE :

• There is no general recipe for proving a mathematical statement

and often there is more than one correct proof.

• One generally tries to make a proof as simple as possible,

so that others may understand it more easily.

• Nevertheless, proofs can be very difficult, even for relatively simple

statements such as Fermat’s Last Theorem :

¬∃x, y, z, n ∈ Z+ , n ≥ 3 : xn + y n = z n .

119
NOTE :

• There are many mathematical statements that are thought to be

correct, but that have not yet been proved (“open problems ”),
e.g., the “Goldbach Conjecture ” :

“Every even integer greater than 2 is the sum of two prime numbers”.

• Indeed, proving mathematical results is as much an art as it is

a science, requiring creativity as much as clarity of thought.

• An essential first step is always to fully understand the problem.

• Where possible, experimentation with simple examples may help

build intuition and perhaps suggest a possible method of proof.

120
 REVIEW EXERCISES.

Problem 1. Use a direct proof to show the following:

   
(p ∨ q) ∧ (q → r) ∧ (p ∧ s) → t ∧ ¬q → (u ∧ s) ∧ ¬r ⇒ t .

(Assuming the left-hand-side is True , you must show that t is True .)

Problem 2. Let n be a positive integer.

Prove the following statement by proving its contrapositive:

”If n3 + 2n + 1 is odd then n is even ”.

121
 Problem 3. Let n be an integer. Show that

3|n2 ⇒ 3|n ,

by proving its contrapositive.

Hint : There are two cases to consider.

Problem 4. Give a direct proof to show the following:

The sum of the squares of any two rational numbers is a rational number.

122
Problem 5.

Show that for all positive real x

√
if x is irrational then x is irrational .

by proving the contrapositive .

Problem 6. Use a proof by contradiction to prove the following:

If the integers 1, 2, 3, · · · , 7, are placed around a circle, in any order,

then there exist two adjacent integers that have a sum greater than or
equal to 9 .

(Can you also give a direct Proof ?)

123
FACT : Any real number x can be uniquely written as
x = n − r,
where
n ∈ Z and r ∈ R , with 0 ≤ r < 1 .

DEFINITION : We then define the ceiling of x as

⌈x⌉ ≡ n .

EXAMPLES : ⌈7⌉ = 7 , ⌈−7⌉ = −7 , ⌈π⌉ = 4 , ⌈−π⌉ = −3 .

Problem 7.
Is the following equality valid for all positive integers n and m ?
n+m n m
⌊ ⌋ = ⌈ ⌉ + ⌊ ⌋.
2 2 2

If Yes then give a proof. If No then give a counterexample.

124
 SET THEORY

Basic definitions.

• Let U be the collection of all objects under consideration.

(U is also called the “universe” of objects under consideration.)

• A set is a collection of objects from U .

125
Let A , B , and C be sets.

x∈A ⇐⇒ “x is an element (a member) of A”.

x∈
/A ⇐⇒ ¬(x ∈ A)

A⊆B ⇐⇒ ∀x ∈ U : x ∈ A ⇒ x ∈ B subset

A=B ⇐⇒ (A ⊆ B) ∧ (B ⊆ A) equality

The above take values in {T , F }.

126
The following are set-valued :

A∪B ≡ { x ∈ U : (x ∈ A) ∨ (x ∈ B) } union

A∩B ≡ { x ∈ U : (x ∈ A) ∧ (x ∈ B) } intersection

Ā ≡ {x∈U : x∈
/A} complement

A−B ≡ { x ∈ U : (x ∈ A) ∧ (x ∈
/ B) } difference

127
Venn diagram.
This is a useful visual aid for proving set theoretic identities.

EXAMPLE : For the two sides of the identity

(A ∩ B) − C = A ∩ (B − C)

we have the following Venn diagrams :

C C

A B A B

128
The actual proof of the identity, using the above definitions and the laws
of logic, is as follows :

 
x ∈ (A ∩ B) − C

⇐⇒ x ∈ (A ∩ B) ∧ x ∈
/C

⇐⇒ (x ∈ A ∧ x ∈ B) ∧ x ∈
/C

⇐⇒ x ∈ A ∧ (x ∈ B ∧ x ∈
/ C) associative law

⇐⇒ x ∈ A ∧ x ∈ (B − C)

⇐⇒ x ∈ A ∩ (B − C)

129
EXAMPLE :

For the two sides of the identity

A − (B ∪ C) = (A − B) ∩ (A − C)

we have the following Venn diagrams :

C C

A B A B

130
The actual proof of the identity is as follows :

 
x ∈ A − (B ∪ C)

⇐⇒ x ∈ A ∧ x ∈
/ (B ∪ C)

⇐⇒ x ∈ A ∧ ¬(x ∈ (B ∪ C))

⇐⇒ x ∈ A ∧ ¬(x ∈ B ∨ x ∈ C)

⇐⇒ x ∈ A ∧ x ∈
/B ∧ x∈
/C de Morgan

⇐⇒ x ∈ A ∧ x ∈ A ∧ x ∈
/ B ∧x ∈
/C idempotent law

⇐⇒ x ∈ A ∧ x ∈
/B ∧ x∈A ∧ x∈
/C commut.+assoc.

⇐⇒ x ∈ (A − B) ∧ x ∈ (A − C)

⇐⇒ x ∈ (A − B) ∩ (A − C)

131
EXAMPLE : A ∩ B = A ∪ B ⇒ A=B

PROOF : ( a direct proof · · · )

Assume (A ∩ B) = (A ∪ B). We must show that A = B.

This is done in two stages :

(i) show A ⊆ B and (ii) show B ⊆ A .

To show (i) :
Let x ∈ A. We must show that x ∈ B.
Since x ∈ A it follows that x ∈ A ∪ B.
Since (A ∩ B) = (A ∪ B) it follows that x ∈ (A ∩ B).
Thus x ∈ B also.

The proof of (ii) proceeds along the same steps.

132
Subsets.

S ⊆ U means S is a subset of a universal set U .

The set of all subsets of U is denoted by 2U or P (U ) , the power set .

This name is suggested by the following fact :

If U has n elements then P (U ) has 2n elements (sets) .

133
EXAMPLE :

Let
U = {1 , 2 , 3} .

Then
n o
P (U ) = {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} .

We see that P (U ) has 23 = 8 elements .

NOTE : The empty set ∅ = {} and U itself are included in P (U ).

134
Basic set theoretic identities :

A∪B =B∪A A∩B =B∩A commutative laws

A ∪ (B ∩ C) = A ∩ (B ∪ C) =
(A ∪ B) ∩ (A ∪ C) (A ∩ B) ∪ (A ∩ C) distributive laws

A∪∅=A A∩U =A identity laws

A ∪ Ā = U A ∩ Ā = ∅ complement laws

135
Some additional identities :

Ū = ∅ ∅¯ = U

A∪A=A A∩A=A idempotent laws

A∪U =U A∩∅=∅ domination laws

A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A absorption laws

136
Some more identities :

(A ∪ B) ∪ C = (A ∩ B) ∩ C =
A ∪ (B ∪ C) A ∩ (B ∩ C) associative law

A ∪ B = Ā ∩ B̄ A ∩ B = Ā ∪ B̄ de Morgan’s laws

¯ =A
Ā involution law

All the preceding identities can be proved using the definitions of set
theory and the laws of logic.

Note the close correspondence of these identities to the laws of logic.

137
NOTE : One can also proceed axiomatically by only assuming :

• the existence of a power set P (U ) , where U is a universal set ,

• special elements U and ∅ ,

• a unary operator ¯ , and two binary operators ∪ and ∩ ,

• the basic set theoretic identities .

Given this setup one can derive all other set theoretic identities.

Note the close correspondence between the above axiomatic setup and
the axiomatic setup of logic !

138
EXAMPLE :

Prove the idempotent law

A∪A=A
using only the basic set theoretic identities :

A = A∪∅ identity law

A ∪ (A ∩ Ā) complement law

(A ∪ A) ∩ (A ∪ Ā) distributive law

(A ∪ A) ∩ U complement law

A∪A identity law

139
EXAMPLE :

( to illustrate the close relation between Set Theory and Logic · · · )

Using another approach we prove the absorption law :

A ∪ (A ∩ B) = A

Thus we must prove

∀x ∈ U : x ∈ A ∪ (A ∩ B) ⇐⇒ x ∈ A

∀x ∈ U : x ∈ A ∨ x ∈ A ∩ B ⇐⇒ x ∈ A

∀x ∈ U : x ∈ A ∨ (x ∈ A ∧ x ∈ B) ⇐⇒ x ∈ A

140
 ∀x ∈ U : x ∈ A ∨ (x ∈ A ∧ x ∈ B) ⇐⇒ x ∈ A

Define logical predicates a(x) and b(x) :

a(x) ⇐⇒ x ∈ A , b(x) ⇐⇒ x ∈ B .

Then we must prove

∀x ∈ U : a(x) ∨ (a(x) ∧ b(x)) ⇐⇒ a(x) .

It suffices to prove that, for arbitrary logical variables a and b ,

a ∨ (a ∧ b) ⇐⇒ a .

But this is the absorption law from logic !

141
 REVIEW EXERCISES.

For each of the following, determine whether it is valid or invalid.

If valid then give a proof. If invalid then give a counterexample.

(1) A ∩ (B ∪ A) = A
(2) A ∪ (B ∩ C) = (A ∪ B) ∩ C
(3) (A ∩ B) ∪ (C ∩ D) = (A ∩ D) ∪ (C ∩ B)
(4) (A ∩ B) ∪ (A ∩ B̄) = A
(5) A ∪ ((B ∪ C) ∩ A) = A
(6) A − (B ∪ C) = (A − B) ∩ (A − C)
(7) B ∩ C ⊆ A ⇒ (B − A) ∩ (C − A) = ∅
(8) (A ∪ B) − (A ∩ B) = A ⇒ B = ∅

142
 FUNCTIONS

DEFINITIONS : Let A and B be sets.

Then f is called
a function from A to B

if to each element of A it associates exactly one element of B .

We write
f : A −→ B

and we call A the domain of f and B the codomain of f .

We also define the range of f to be

f (A) ≡ {b ∈ B : b = f (a) for some a ∈ A} .

143
We say that f is :

one-to-one (or injective) iff ∀a1 , a2 ∈ A : a1 6= a2 ⇒ f (a1 ) 6= f (a2 )

iff ∀a1 , a2 ∈ A : f (a1 ) = f (a2 ) ⇒ a1 = a2

onto (or surjective) iff ∀b ∈ B ∃a ∈ A : f (a) = b

iff f (A) = B

bijective iff f is one-to-one and onto

144
EXAMPLE :
Let
A = {a, b, c} , B = {1, 2} ,

and let f : A −→ B be defined by

f : a 7→ 1 , f : b 7→ 2 , f : c 7→ 1 .

Then f not one-to-one, but f is onto.

A B
a
1

2
c

145
EXAMPLE :
Let
A = {a, b} , B = {1, 2, 3} ,

and let f : A −→ B be defined by

f : a 7→ 1 , f : b 7→ 3 .

Then f is one-to-one but not onto.

A B
a
1

2
b
3

146
EXAMPLE :

Let A = B = Z+ , and let

f : Z+ −→ Z+
be defined by

n(n + 1)
f : n 7→ ,
2

i.e.,
n(n + 1)
f (n) = .
2

Then f is one-to-one but not onto.

147
 f (n) ≡ n(n + 1)/2

PROOF : (1) f is not onto :

Here
f (Z+ ) = { 1 , 3 , 6 , 10 , 15 , 21 , · · · } ,

so it seems that f is not onto.

To be precise, we show that f (n) can never be equal to 2 :

f (n) = 2 ⇐⇒ n(n + 1)/2 = 2 ⇐⇒ n2 + n − 4 = 0 .

But this quadratic equation has no integer roots.

148
(2) f is one-to-one : Assume that f (n1 ) = f (n2 ).

We must show that n1 = n2 :

f (n1 ) = f (n2 ) ⇐⇒ n1 (n1 + 1)/2 = n2 (n2 + 1)/2

⇐⇒ n21 + n1 = n22 + n2

⇐⇒ n21 − n22 = − (n1 − n2 )

⇐⇒ (n1 + n2 )(n1 − n2 ) = − (n1 − n2 )

⇐⇒ n1 = n2 or n1 + n2 = − 1

However n1 , n2 ∈ Z+ . Thus n1 + n2 cannot be negative.

It follows that n1 = n2 . QED !

149
EXAMPLE :

Define
f : Z × Z −→ Z × Z
or equivalently
f : Z2 −→ Z2
by
f (m, n) = (m + n , m − n) ,

or equivalently, in matrix multiplication notation

    
m 1 1 m
f : 7→ .
n 1 −1 n

Then f is one-to-one, but not onto.

150
PROOF :

(i) One-to-one :
Suppose
f (m1 , n1 ) = f (m2 , n2 ) .
Then
(m1 + n1 , m1 − n1 ) = (m2 + n2 , m2 − n2 ) ,
i.e.,
m1 + n1 = m2 + n2 ,
and
m1 − n1 = m2 − n2 .

Add and subtract the equations, and divide by 2 to find

m1 = m2 and n1 = n2 ,
that is,
(m1 , n1 ) = (m2 , n2 ) .
Thus f is one-to-one.

151
(ii) Not onto :
Let (s, d) ∈ Z2 be arbitrary. Can we solve

f (m, n) = (s, d) ,

i.e., can we solve

m+n = s ,
m−n = d ,
for m, n ∈ Z ?

Add and subtract the two equations, and divide by 2 to get

s+d s−d
m = and n = .
2 2
However, m and n need not be integers, e.g., take s = 1, d = 2.

Thus f is not onto. QED !

152
Given two functions

f : A −→ B and g : B −→ C ,

we can compose them :

 
(g ◦ f )(a) ≡ g f (a) .

go f
f g

a f(a) g(f(a))

A B C

153
EXAMPLE :
Let A = B = C = Z (all integers), and define f, g : Z −→ Z by
f (n) ≡ n2 + 2n − 1 , g(n) ≡ 2n − 1 .

 
• Let h1 (n) ≡ f g(n) . Then

h1 (n) = f (2n − 1) = (2n − 1)2 + 2(2n − 1) − 1 = 4n2 − 2 .

 
• Let h2 (n) ≡ g f (n) . Then

h2 (n) = g(n2 + 2n − 1) = 2(n2 + 2n − 1) − 1 = 2n2 + 4n − 3 .

 
• Let h3 (n) ≡ g g(n) . Then

h3 (n) = g(2n − 1) = 2(2n − 1) − 1 = 4n − 3 .

154
Inverses. Let
f : A −→ B ,
and
g : B −→ A .

Then g is called the inverse of f if

 
∀a ∈ A : g f (a) = a ,
and  
∀b ∈ B : f g(b) = b .

If f has an inverse g then we say

f is invertible ,
and we write f −1 for g .

155
EXAMPLE :

Let f : Z −→ Z be defined by f : n 7→ n − 1 , i.e.,

f (n) = n − 1 (”shift operator”) .

• f is one-to-one :

If f (n1 ) = f (n2 ) then n1 − 1 = n2 − 1 , i.e., n1 = n2 .

• f is onto :

Given any m ∈ Z , can we find n such that f (n) = m ?

That is, can we find n such that n − 1 = m ?

Easy: n = m + 1 !

156
 f (n) = n − 1 , f : Z −→ Z

It follows that f is invertible, with inverse

f −1 (m) = m + 1 .

Check :
 
f f −1 (m) = f (m + 1) = (m + 1) − 1 = m ,

 
f −1 f (n) = f −1 (n − 1) = (n − 1) + 1 = n .

157
EXAMPLE :

Let f : R −→ R be defined by f : x 7→ 1 − 2x , i.e.,

f (x) = 1 − 2x .

• f is one-to-one :

If f (x1 ) = f (x2 ) then 1 − 2x1 = 1 − 2x2 , i.e., x1 = x2 .

• f is onto :

Given any y ∈ R , can we find x such that f (x) = y ?

That is, can we find x such that 1 − 2x = y ?

Easy: x = (1 − y)/2 !
1−y
( We actually constructed the inverse in this step : f −1 (y) = 2
.)

158
 f (x) = 1 − 2x , f : R −→ R

We found that f is invertible, with inverse

1−y
f −1
(y) = .
2

Check ( not really necessary · · · ) :

   
f f −1 (y) = f ((1 − y)/2) = 1 − 2 (1 − y)/2 = y ,

  1 − (1 − 2x)
f −1
f (x) = f (1 − 2x) =
−1
= x.
2

NOTE : We constructed f −1 (y) by solving f (x) = y for x .

159
THEOREM :

f : A −→ B is invertible if and only if f is 1 − 1 and onto .

REMARK :

• It is not difficult to see that this theorem holds for finite sets.

• However, the proof also applies to infinite sets.

160
PROOF :
(1a) First we show that if f is invertible then f is 1 − 1 .

By contradiction: Suppose f is invertible but not 1 − 1.

Since f is not 1 − 1 there exist a1 , a2 ∈ A, a1 6= a2 , such that

f (a1 ) = f (a2 ) ≡ b0 .

Since f is invertible there is a function g : B −→ A such that

 
g (f (a) ) = a, ∀a ∈ A .
In particular
   
g f (a1 ) = a1 , and g f (a2 ) = a2 ,
i.e.,
g(b0 ) = a1 , and g(b0 ) = a2 .
Thus g is not single-valued (not a function). Contradiction !

161
(1b) Now we show that if f is invertible then f is onto.

By contradiction: Suppose f is invertible but not onto.

Since f is not onto there exists b0 ∈ B such that

f (a) 6= b0 , ∀a ∈ A .

Since f is invertible there is a function g : B −→ A such that

 
f g(b) = b, ∀b ∈ B .

In particular
 
f g(b0 ) = b0 , where g(b0 ) ∈ A .

But this contradicts that f (a) 6= b0 , ∀a ∈ A .

162
(2a) Next we show that if f is 1 − 1 and onto then f is invertible.

Define a function g : B −→ A as follows :

Since f is 1 − 1 and onto we have that for any b ∈ B

b = f (a) for some unique a ∈ A .

For each such a ∈ A set

g(b) = a .

Then g : B −→ A , and by construction

 
f g(b) = f (a) = b .

163
  
(2b) We still must show that ∀a ∈ A : g f (a) = a .

 
By contradiction : Suppose g f (a0 ) 6= a0 for some a0 ∈ A .

Define b0 = f (a0 ) . Then b0 ∈ B and

g(b0 ) 6= a0 ,
where both g(b0 ) and a0 lie in A .

Since f is one-to-one it follows that

 
f g(b0 ) 6= f (a0 ) ,

i.e.,  
f g(b0 ) 6= b0 .

But this contradicts the result of (2a) ! QED !

164
EXAMPLE :

• Define f : Z+ −→ Z+ by
f (n) = n(n − 2)(n − 4) + 4 .
Then f is not one-to-one ; for example, f (2) = f (4) = 4 :

n 1 2 3 4 5 6 7 ···
f (n) 7 4 1 4 19 52 109 · · ·

Using calculus one can show that f (n) is increasing for n ≥ 3.

Thus f is not onto ; for example,

∀n ∈ Z+ : f (n) 6= 2 .

165
• Now let
S = f (Z+ ) = {1, 4, 7, 19, 52, 109, · · ·} ,

and consider f as a function

f : Z+ −→ S .

Then f is onto, but still not one-to-one, since f (2) = f (4) = 4.

• Finally let
D = Z+ − {2} ,
and consider f as a function

f : D −→ S .

Now f is one-to-one and onto, and hence invertible.

166
EXAMPLE : The floor and ceiling functions.

FACT :

∀x ∈ R ∃ ! n ∈ Z and ∃ ! r ∈ R with 0 ≤ r < 1 such that

x = n + r.

We already defined the floor function, ⌊·⌋ , as

⌊x⌋ = n .

EXAMPLES :

⌊π⌋ = 3 , ⌊e⌋ = 2 , ⌊3⌋ = 3 , ⌊−7/2⌋ = − 4 ,

where e = 2.71828 · · · .

167
FACT :

∀x ∈ R ∃ ! n ∈ Z and ∃ ! r ∈ R with 0 ≤ r < 1 such that

x = n − r.

We already defined the ceiling function, ⌈·⌉ , as

⌈x⌉ = n .

EXAMPLES :

⌈π⌉ = 4 , ⌈e⌉ = 3 , ⌈3⌉ = 3 , ⌈−7/2⌉ = − 3 .

168
We see that

⌊·⌋ : R −→ Z ,

and

⌈·⌉ : R −→ Z .

EXERCISE :

• Is ⌊·⌋ one-to-one? onto? invertible?

• Is ⌈·⌉ one-to-one? onto? invertible?

• Draw the graphs of ⌊·⌋ and ⌈·⌉ .

169
EXAMPLE : Let p , k ∈ Z+ .

Then
p p+k
⌈ ⌉ < .
k k

PROOF :

By definition of the ceiling function we can write

p p
= ⌈ ⌉ − r,
k k
where 0 ≤ r < 1 .

Hence
p p p p+k
⌈ ⌉ = + r < + 1 = . QED !
k k k k

170
EXAMPLE : Show that the linear function

f : R2 −→ R2
defined by
f (x, y) = (x + y , x − y) ,
or, in matrix form,
    
x 1 1 x
f : 7→ ,
y 1 −1 y

is one-to-one and onto.

• One-to-one : Exercise!

Hint : See the earlier example where this function was considered as

f : Z2 −→ Z2 .

171
• Onto :
    
x 1 1 x
f (x, y) = (x + y , x − y) or f : 7→
y 1 −1 y

We can construct the inverse by solving

f (x, y) = (s, d) ,
that is, by solving
x+y = s , x−y = d ,
for x, y ∈ R :
s+d s−d
x = , y = .
2 2
Thus the inverse is
  1  
s+d s−d s 2
1
2 s
g(s, d) = ( , ) or g : 7→ 1 .
2 2 d 2 − 21 d

172
 f (x, y) = (x + y , x − y) , g(s, d) = ( s+d
2
, s−d
2
)

Check ( not really necessary · · · ) :

s+d s−d
f (g(s, d)) = f ( , )
2 2
s+d s−d s+d s−d
= ( + , − ) = (s, d) ,
2 2 2 2
and
g(f (x, y)) = g(x + y , x − y)

(x + y) + (x − y) (x + y) − (x − y)
= ( , ) = (x, y) .
2 2

173
EXAMPLE :

More generally, a function

f : R2 −→ R2

is linear if it can be written as

f (x, y) = ( a11 x + a12 y , a21 x + a22 y ) ,

or equivalently, as matrix-vector multiplication ,

    
x a11 a12 x
f : 7→ ,
y a21 a22 y

where aij ∈ R , (i, j = 1, 2) .

174
     
x a11 a12 x
f : R2 −→ R2 , f : 7→
y a21 a22 y

This function is invertible if the determinant

D ≡ a11 a22 − a12 a21 6= 0 .

In this case the inverse is given by

    
s 1 a22 −a12 s
f −1
: 7→ .
d D −a21 a11 d

EXERCISE : Check that

f −1 (f (x, y)) = (x, y) and f (f −1 (s, d)) = (s, d) .

175
Now consider the same linear function
    
n a11 a12 n
f : 7→ ,
m a21 a22 m

but with aij ∈ Z , (i, j = 1, 2) , and as a function

f : Z2 −→ Z2 .

Is     
s 1 a22 −a12 s
f −1 : 7→ .
d D −a21 a11 d

still the inverse?

176
ANSWER : Not in general !

f is now invertible only if the determinant

• D = a11 a22 − a12 a21 6= 0,

and

• ∀i, j : D | aij .

In this case f −1 is still given by

    
s 1 a22 −a12 s
f −1 : 7→ .
d D −a21 a11 d

177
EXERCISE : Show that
    
n 3 2 n
f : 7→ ,
m 4 3 m

is invertible as a function f : Z2 −→ Z2 .

What is the inverse?

EXERCISE : Show that

    
n 3 1 n
f : 7→ ,
m 4 3 m

is not invertible as a function f : Z2 −→ Z2 .

178
 REVIEW EXERCISES.
Problem 1.

Define
f : R −→ R
by 
 1/x if x 6= 0 ,
f (x) ≡
0 if x=0.


• Draw the graph of f .

• Is f one-to-one?

• Is f onto?

• What is f −1 ?

179
Problem 2. Consider a function

f : A −→ B .

For each of the following, can you find a function f that is

(i) one-to-one (ii) onto (iii) one-to-one and onto ?

• A = {1, 2, 3} , B = {1, 2}

• A = {1, 2} , B = {1, 2, 3}

• A = {all even positive integers} , B = {all odd positive integers}

180
Problem 3.

Can you find a function f : Z −→ Z+ that is one-to-one and onto ?

Can you find a function g : Z+ −→ Z that is one-to-one and onto ?

Problem 4. Let Sn be a finite set of n elements.

Show that a function

f : Sn −→ Sn

is one-to-one if and only if it is onto.

181
Problem 5. Let f : A −→ B and g : B −→ C be functions.

• Suppose f and g are one-to-one.

Is the composition g ◦ f necessarily one-to-one?

• Suppose the composition g ◦ f is one-to-one.

Are f and g necessarily one-to-one?

• Suppose f and g are onto.

Is the composition g ◦ f necessarily onto?

• Suppose the composition g ◦ f is onto.

Are f and g necessarily onto?

Justify your answers.

182
Problem 6.

Let P2 denote the set of all polynomials of degree 2 or less ,

i.e., polynomials of the form

p(x) = a x2 + b x + c , a, b, c ∈ R , x ∈ R .

Let P1 denote the set of all polynomials of degree 1 or less ,

i.e., polynomials of the form

p(x) = d x + e , d, e ∈ R , x ∈ R .

Consider the derivative function (or derivative operator )

D : P2 −→ P1 .

183
For example,
D : 3x2 + 7x − 4 7→ 6x + 7 ,
and
D : 5x − 2π 7→ 5.

QUESTIONS :

• Is D indeed a function from P2 to P1 ?

• Is D one-to-one ?

• Is D onto ?

• Does D have an inverse ?

184
Problem 7. If A and B are sets, and if
f : A −→ B ,

then for any subset S of A we define the image of S as

f (S) ≡ {b ∈ B : b = f (a) for some a ∈ S} .

Let S and T be subsets of A . Prove that

• f (S ∪ T ) = f (S) ∪ f (T ) ,

• f (S ∩ T ) ⊆ f (S) ∩ f (T ) .

• Also give an example that shows that in general

f (S ∩ T ) 6= f (S) ∩ f (T ) .

185
Problem 8. If A and B are sets, and if

f : A −→ B ,

then for any subset S of B we define the pre-image of S as

f −1 (S) ≡ {a ∈ A : f (a) ∈ S} .

NOTE : f −1 (S) is defined even if f does not have an inverse!

Let S and T be subsets of B . Prove that

• f −1 (S ∪ T ) = f −1 (S) ∪ f −1 (T ) ,

• f −1 (S ∩ T ) = f −1 (S) ∩ f −1 (T ) .

186
THE DIVISION THEOREM :

∀n ∈ Z, ∀d ∈ Z+ , ∃! q, r ∈ Z : ( 0 ≤ r < d , n = qd + r ) .

EXAMPLE : If n = 21 and d = 8 then

n = 2·d + 5 .

Thus, here q = 2 and r = 5 .

• d is called the divisor,

• q is called the quotient; we write q = n div d ,

• r is called the remainder; we write r = n mod d .

187
EXAMPLES :

n = 14 , d = 5 : 14 = 2 · d + 4 , so

14 div 5 = 2 and 14 mod 5 = 4 .

n = −14 , d = 5 : −14 = (−3) · d + 1 , so

−14 div 5 = − 3 and − 14 mod 5 = 1 .

188
Let d ∈ Z+ and n, q, r ∈ Z .

From the definitions of “div” and “mod” it follows that :

PROPERTY 1 : n = (n div d) d + n mod d

Example : 23 = (23 div 7) · 7 + 23 mod 7

PROPERTY 2 : If 0 ≤ r < d then (qd + r) mod d = r

Example : (5 · 7 + 3) mod 7 = 3

PROPERTY 3 : (qd + n mod d) mod d = n mod d

Example : (5 · 7 + 23 mod 7) mod 7 = 23 mod 7

189
PROPERTY 4 : Let a, b ∈ Z and d ∈ Z+ . Then

(ad + b) mod d = b mod d .

PROOF :
By the Division Theorem

b = qd + r, where r = b mod d , with 0 ≤ r < d .

Thus, using Property 2
 
(ad + b) mod d = (a + q)d + r mod d = r = b mod d .

QED !

EXAMPLE : (57 · 7 + 13) mod 7 = 13 mod 7 .

190
PROPERTY 5 : Let a ∈ Z and d ∈ Z+ . Then

(a mod d) mod d = a mod d .

PROOF : Using Property 3,

(a mod d) mod d = (0 · d + a mod d) mod d = a mod d .

EXAMPLE :

(59 mod 7) mod 7 = 59 mod 7 .

191
PROPERTY 6 :

Let a, b ∈ Z and d ∈ Z+ . Then

(a + b) mod d = (a mod d + b mod d) mod d .

EXAMPLE :

(5 + 8) mod 3 = 1 = (5 mod 3 + 8 mod 3) mod 3 .

192
PROOF :

By the Division Theorem

a = qa d + ra , where ra = a mod d , with 0 ≤ ra < d ,

b = qb d + rb , where rb = b mod d , with 0 ≤ rb < d .

Thus
(a + b) mod d = (qa d + ra + qb d + rb ) mod d
 
= (qa + qb )d + ra + rb mod d

= (ra + rb ) mod d (using Property 4)

= (a mod d + b mod d) mod d . QED !

193
DEFINITION :

If a, b ∈ Z , d ∈ Z+ , and if

a mod d = b mod d ,
then we also write
a ≡ b (mod d) ,
and we say
“a is congruent to b modulo d”.

EXAMPLE :
83 ≡ 31 (mod 26) .

Note that 83 − 31 = 52 , which is divisible by 26 , i.e.,

26 | (83 − 31) .

194
PROPOSITION : Let a, b ∈ Z , and d ∈ Z+ . Then

a ≡ b (mod d) if and only if d | (a − b) .

PROOF :

(⇒) First, if a ≡ b (mod d) then, by definition,

a mod d = b mod d .

Hence there exist qa , qb , r ∈ Z , with 0 ≤ r < d , such that

a = qa d + r and b = qb d + r (same remainder).

It follows that
a − b = (qa − qb ) d ,
so that d | (a − b).

195
 a ≡ b (mod d) if and only if d | (a − b)

(⇐) Conversely, if d | (a − b) then

a − b = qd ,

i.e. ,
a = b + qd ,
for some q ∈ Z .

It follows that

a mod d = (b + qd) mod d = b mod d .

196
PROPOSITION : If a, b ∈ Z , and c, d ∈ Z+ , then

a ≡ b (mod d) ⇒ ac ≡ bc (mod dc) .

PROOF :
a ≡ b (mod d) if and only if d | (a − b) ,

i.e.,
a − b = qd , for some q ∈ Z .

Then ac − bc = qdc , so that (dc) | (ac − bc) ,

i.e.,
ac ≡ bc (mod dc) .

NOTE : We also have that ac ≡ bc (mod d) .

197
PROPOSITION : Let a, b ∈ Z and d ∈ Z+ . Then

a ≡ b (mod 2d) ⇒ a2 ≡ b2 (mod 4d) .

EXAMPLE : Let a = 13 , b = 7 d = 3 . Then

13 ≡ 7 (mod 2 · 3) ,
i.e.,
13 (mod 6) = 7 (mod 6) ,

and

132 ≡ 72 (mod 4 · 3) ,
i.e.,
169 (mod 12) = 49 (mod 12) (Check!) .

198
 a ≡ b (mod 2d) ⇒ a2 ≡ b2 (mod 4d)

PROOF : Suppose a ≡ b (mod 2d) .

Then 2d|(a − b) , i.e., a − b = q2d , for some q ∈ Z .

Thus a and b differ by an even number.

It follows that a and b must be both even or both odd.

Hence a + b must be even, i.e., a + b = 2c for some c ∈ Z .

Then a2 − b2 = (a + b) (a − b) = (2c) (q2d) = cq 4d .

It follows that 4d|(a2 − b2 ) , i.e., a2 ≡ b2 (mod 4d) . QED !

NOTE : Also a2 ≡ b2 (mod 2d) and a2 ≡ b2 (mod d) .

199
PROPOSITION : If n > 3 then not all of
n , n+2 , n+4 ,
can be primes.

Idea of the proof : Always one of these three numbers is divisible by 3 .

PROOF. By contradiction : Assume that n > 3 and that

n , n + 2 and n + 4 are primes .
Since n is prime and n > 3 we have
n mod 3 = 1 or n mod 3 = 2 . (Why ?)

Case 1 : If n mod 3 = 1 then n = 3k + 1 and

n + 2 = 3k + 3 , i.e., 3|(n + 2) .

Case 2 : If n mod 3 = 2 then n = 3k + 2 and

n + 4 = 3k + 6 , i.e., 3|(n + 4) .
Contradiction !

200
THE FACTORIZATION THEOREM :

 
∀n ∈ (Z+ − {1}) , ∃! m, {pi }m m
i=1 , {ni }i=1 :

m ∈ Z+ ,

∀i (i = 1, · · · , m) : pi , ni ∈ Z+ ,

1 < p1 < p2 < · · · < pm ,

∀i (i = 1, · · · , m) : pi is a prime number ,

n = pn1 1 pn2 2 · · · pnmm .

EXAMPLE : 252 = 22 32 71 .

201
PROPOSITION : log2 3 is irrational.

PROOF : By contradiction:
Suppose log2 3 is rational, i.e., ∃p, q ∈ Z+ , such that
log2 3 = p/q .
By definition of the log function it follows that

2p/q = 3 ,

from which
2 p = 3q .
Let n = 2p . Then n ∈ Z+ , with n ≥ 2 .
Then n has two different prime factorizations, namely
n = 2p and n = 3q .

This contradicts the Factorization Theorem. QED !

202
REMARK :

The fact that

2p 6= 3q ,

also follows from the facts that 2p is even and 3q is odd.

203
DEFINITION :

We call n ∈ Z+ a perfect square if

∃k ∈ Z+ : n = k2 .

FACT :

The factorization of a perfect square has only even powers :

If
k = pn1 1 pn2 2 · · · pnmm ,
then
n = k2 = p12n1 p22n2 · · · pm
2nm
.

204
PROPOSITION :
+
√
If n ∈ Z is not a perfect square then n is irrational.

PROOF :

By contradiction :
√
Suppose n is not a perfect square, but n is rational.

Thus
√ p
n = ,
q
i.e.,
p2 = n q 2 ,

for some p, q ∈ Z+ .

205
 p2 = n q 2

• The prime factorization of p2 has even powers only.

• The prime factorization of q 2 has even powers only.

• The prime factorization of n must have an odd power,

(otherwise n would be a perfect square).

• Thus the factorization of nq 2 must have an odd power.

• Thus p2 has two distinct factorizations:

one with even powers and one with at least one odd power.

This contradicts the uniqueness in the Factorization Theorem.

QED !

206
DEFINITION :

k ∈ Z+ is the greatest common divisor of n, m ∈ Z+ ,

k = gcd(n, m) ,
if

• k|n and k|m ,

• no positive integer greater than k divides both n and m .

207
REMARK :

One can determine

gcd( n , m )
from the minimum exponents in the prime factorizations of n and m.

EXAMPLE : If
n = 168 , m = 900 ,
then

n = 23 3 1 7 1 , m = 22 3 2 5 2 ,

and
gcd(168, 900) = 22 31 = 12 .

208
THE EUCLIDEAN THEOREM :

Let n , d ∈ Z+ , and let

r = n mod d , (the remainder)

Then 

 gcd(d , r) if r > 0,

gcd(n, d) =


d if r = 0.


209
EXAMPLE :

gcd(93 , 36) = gcd(36 , 93 mod 36) = gcd(36 , 21)

= gcd(21 , 36 mod 21) = gcd(21 , 15)

= gcd(15 , 21 mod 15) = gcd(15 , 6)

= gcd(6 , 15 mod 6) = gcd(6 , 3)

= 3.

210
EXAMPLE :

gcd(2008 , 1947) = gcd(1947 , 2008 mod 1947) = gcd(1947 , 61)

= gcd(61 , 1947 mod 61) = gcd(61 , 56)

= gcd(56 , 61 mod 56) = gcd(56 , 5)

= gcd(5 , 56 mod 5) = gcd(5 , 1)

= 1.

Thus 2008 and 1947 are relatively prime .

211
LEMMA :

Let a, b, c ∈ Z , and d ∈ Z+ .

Then

(1) ( a = b + c , d|a , d|b ) ⇒ d|c ,

(2) ( a = b + c , d|b , d|c ) ⇒ d|a ,

(3) ( a = bc , d|c ) ⇒ d|a .

212
 (1) ( a = b + c , d|a , d|b ) ⇒ d|c

PROOF of (1) :
d|a ⇐⇒ ∃qa ∈ Z : a = d qa ,
and
d|b ⇐⇒ ∃qb ∈ Z : b = d qb .

Thus
c = a − b = d qa − d qb = d (qa − qb ) .

Hence d|c .

EXERCISE : Prove (2) and (3) in a similar way.

213
 
gcd(d, r) if r>0
gcd(n, d) =
d if r=0

PROOF OF THE EUCLIDEAN THEOREM :

By the Division Theorem

n = q · d + r,
where
q = n div d and r = n mod d .

Case 1 : r = 0 .

Then clearly d|n .

Also d|d and no greater number than d divides d .

Hence d = gcd(n, d) .

214
 
gcd(d, r) if r>0
gcd(n, d) =
d if r=0

Case 2 : r > 0:

Let k = gcd(n, d) .

Then k|n and k|d .

By the Division Theorem

n = q · d + r,
By Lemma (3) k|qd .

By Lemma (1) k|r .

Thus k divides both d and r .

215
 
gcd(d, r) if r>0
gcd(n, d) =
d if r=0

k = gcd(n, d) , n = q · d + r.

Show k is the greatest common divisor of d and r :

By contradiction :
Suppose k1 > k and k1 = gcd(d, r) .
Thus k1 |d and k1 |r
By Lemma (3) k1 |qd .
By Lemma (2) k1 |n .
Thus k1 divides both n and d .
Since k1 > k this contradicts that k = gcd(n, d) . QED !

216
 REVIEW EXERCISES.

Problem 1.
√
Prove that a composite number n has a factor k ≤ n .

Thus to check if a number n is prime one needs only check whether

√
n mod k = 0 , k = 2, 3, · · · , ⌊ n⌋ .

Problem 2. Use the above fact to check whether 143 is prime.

217
Problem 3. Find all integer solutions of

2x ≡ 7(mod 17) .

Problem 4. Find all integer solutions of

4x ≡ 5(mod 9) .

Problem 5.

Does there exists an integer x that simultaneously satisfies

x ≡ 2(mod 6) and x ≡ 3(mod 9) ?

218
Problem 6. Let

S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ,

and define
f : S −→ S ,
by
f (k) = (5k + 3) mod 10 .
Is f invertible?

Problem 7. with S as above, also consider

f (k) = (6k + 3) mod 10 ,

and
f (k) = (7k + 3) mod 10 .

219
Problem 8. Let n ≥ 2 ,

Sn = { 0 , 1 , 2 , 3 , · · · , n − 1 } ,
and define

f : Sn −→ Sn ,

by
f (k) = (pk + s) mod n ,

where p is prime, with p > n , and s ∈ Sn .

Prove that f is one-to-one (and hence onto and invertible ).

220
 THE PRINCIPLE OF INDUCTION
Let
S = { s1 , s2 , s3 , · · · }

be a countably infinite set .

Suppose P is a predicate,

P : S −→ { T , F } ,

such that :
(i) P (s1 ) = T ,

(ii) P (sn ) = T ⇒ P (sn+1 ) = T .

Then
P (s) = T , for all s ∈ S .

221
EXAMPLE :
n
X n(n + 1)
k = , ∀n ∈ Z+ .
k=1
2

Here S = Z+ and
n
X n(n + 1)
P (n) = T if k = ,
k=1
2
and n
X n(n + 1)
P (n) = F if k 6= .
k=1
2

We must show that P (n) = T for all n .

222
PROOF :
(i) “By inspection” the formula holds if n = 1 , i.e., P (1) = T .

(ii) Suppose P (n) = T for some arbitrary n ∈ Z+ , i.e.,

n
X n(n + 1)
k = .
k=1
2

We must show that P (n + 1) = T , i.e., 

n+1
X (n + 1) (n + 1) + 1
k = .
k=1
2

This is done as follows:

n+1 n
X X  n(n + 1)
k = k + (n + 1) = + (n + 1)
k=1 k=1
2
 
(n + 1) (n + 1) + 1
= . QED !
2

223
EXAMPLE :
n
X n(n + 1)(2n + 1)
k2 = , ∀n ∈ Z+ .
k=1
6

PROOF :

(i) Again the formula is valid if n = 1 .

(ii) Suppose
n
X
2 n(n + 1)(2n + 1)
k = ,
k=1
6
for some arbitrary n ∈ Z+ .

We must show that

  
n+1
X (n + 1) (n + 1) + 1 2(n + 1) + 1
k2 = .
k=1
6

224
 Pn 2 n(n+1)(2n+1) Pn+1 (n+1) ((n+1)+1) (2(n+1)+1)
k=1 k = 6
⇒ k=1 k2 = 6

n+1
X n
X 
To do this : k2 = k2 + (n + 1)2
k=1 k=1

= n(n + 1)(2n + 1)/6 + (n + 1)2

 
= (n + 1) n(2n + 1) + 6(n + 1) /6

= (n + 1) (2n2 + 7n + 6)/6

= (n + 1) (n + 2) (2n + 3)/6
  
= (n + 1) (n + 1) + 1 2(n + 1) + 1 /6 . QED !

225
EXAMPLE :

(n3 − n) mod 3 = 0 , ∀n ∈ Z+ .

PROOF :

(i) By inspection P (1) = T .

(ii) Suppose P (n) = T , i.e.,

(n3 − n) mod 3 = 0 , for some arbitrary n ∈ Z+ .

We must show that P (n + 1) = T , i.e.,

 
(n + 1)3 − (n + 1) mod 3 = 0 .

226
 (n3 − n) mod 3 = 0 ⇒ ( (n + 1)3 − (n + 1) ) mod 3 = 0

To do this :

 
(n + 1)3 − (n + 1) mod 3 = (n3 + 3n2 + 3n − n) mod 3

 
= 3(n2 + n) + n3 − n mod 3

= (n3 − n) mod 3 = 0 . QED !

227
EXAMPLE :
Let P (n) denote the statement

“A set Sn of n elements has 2n subsets”.

CLAIM : P (n) = T for all n ≥ 0 .

PROOF :

(i) P (0) = T because the empty set has one subset, namely itself.

(ii) Suppose that P (n) = T for some arbitrary n , ( n ≥ 0 ) ,

i.e., Sn has 2n subsets.

We must show that P (n + 1) = T , i.e., Sn+1 has 2n+1 subsets.

228
To do this write
Sn+1 = { s1 , s2 , · · · , sn , sn+1 } = Sn ∪ {sn+1 } .
Now count the subsets of Sn+1 :

(a) By inductive hypothesis Sn has 2n subsets.

These are also subsets of Sn+1 .

(b) All other subsets of Sn+1 have the form

T ∪ {sn+1 } ,
where T is any subset of Sn .

Thus there are 2n such additional subsets.

The total number of subsets of Sn+1 is therefore

2n + 2n = 2n+1 . QED !

229
EXAMPLE :

Let P (n) denote the statement

3n < n!

CLAIM :
P (n) = T for all integers n with n > 6 .

REMARK : P (n) is False for n ≤ 6 . (Check!)

230
PROOF :

(i) P (7) = T , because

37 = 2187 < 5040 = 7!

(ii) Assume P (n) = T for some arbitrary n , (n ≥ 7) ,

i.e.,
3n < n! (n ≥ 7) .

We must show that P (n + 1) = T , i.e.,

3n+1 < (n + 1)!

231
 3n < n! ⇒ 3n+1 < (n + 1)!

To do this :

3n+1 = 3 · 3n

< 3 · n! (by inductive assumption)

< (n + 1) n! (since n ≥ 7)

= (n + 1)!

232
EXERCISE : For which nonnegative integers is

n2 ≤ n! ?

Prove your answer by induction.

EXERCISE : For which positive integers n is

n 2 ≤ 2n ?

Prove your answer by induction.

233
EXAMPLE :

Let m
X 1
Hm ≡ . (”Harmonic numbers.”)
k=1
k
Let P (n) denote the statement
n
H2n ≥ 1 + .
2

CLAIM : P (n) = T for all n ∈ Z+ .

PROOF :
(i) It is clear that P (1) = T , because
2
X 1 1
H21 = = 1+ .
k=1
k 2

234
(ii) Assume that

P (n) = T for some arbitrary n ∈ Z+ ,

i.e.,
n
H 2n ≥ 1 + .
2

We must show that

P (n + 1) = T ,
i.e.,
n+1
H2n+1 ≥ 1 + .
2

235
To do this :

n+1
2X n
2 n+1
2X
1 X 1 1
H2n+1 = = +
k=1
k k=1
k k=2n +1
k

n
2 n +2n
2X
X 1 1
= +
k=1
k k=2n +1
k

n n 1
≥ (1 + ) + 2 n
2 2 + 2n
n 1
= (1 + ) +
2 2
n+1
= 1+ . QED !
2

236
REMARK :

It follows that
∞
X 1
diverges ,
k=1
k

i.e.,
n
X 1
−→ ∞ as n −→ ∞ .
k=1
k

237
EXAMPLE : (The Binomial Formula.)

For n ≥ 0 , a, b nonzero,

n  
X n
(a + b)n = an−k bk ,
k
k=0

where
 
n n!
≡ .
k k! (n − k)!

REMARK : Thus we can write

     
n n n
(a + b)n = an + an−1 b + an−2 b2 + · · · + abn−1 + bn .
1 2 n−1

238
PROOF :

The formula holds if n = 0 . (Check!)

Assume that for some arbitrary n, ( n ≥ 0 )

n  
X n
(a + b)n = an−k bk .
k
k=0

We must show that the formula is also valid for n + 1 , i.e., that

n+1  
X n+1
(a + b)n+1 = an+1−k bk .
k
k=0

239
This can be done as follows :
n  
X n
(a + b)n+1 = (a + b)(a + b)n = (a + b) an−k bk
k
k=0
n   n−1  
X n X n
= an+1 + an−k+1 bk + an−k bk+1 + bn+1
k k
k=1 k=0
n   n  
X n X n
= an+1 + an−k+1 bk + an−k+1 bk + bn+1
k k−1
k=1 k=1
n n   o
n+1
X n n
= a + + an−k+1 bk + bn+1
k k−1
k=1
n  
X n+1
= an+1 + an−k+1 bk + bn+1
k
k=1
n+1  
X n+1
= an+1−k bk . QED !
k
k=0

240
REMARK :

In the proof we used the fact that

   
n n n! n!
+ = +
k k−1 k! (n − k)! (k − 1)! (n − k + 1)!

n! (n − k + 1) + n! k
=
k! (n − k + 1)!

(n + 1)!
=
k! (n − k + 1)!

 
n+1
= .
k

241
REMARK :

One can order the binomial coefficients in Pascal’s triangle as follows :

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
. . . . . . . . . .

242
Observe that every entry can be obtained by summing the closest entries
in the preceding row.

This is so because the (n + 1)st and (n + 2)nd rows look like :

   
n n
1 ········· ········· 1
k−1 k
 
n+1
1 ········· ········· 1
k

and we have shown above that

     
n n n+1
+ = .
k k−1 k

243
REMARKS :

• The advantage of a proof by induction is that it is systematic.

• A disadvantage is that the result (e.g., a formula) must be known in

advance from a heuristic argument or by trial and error.

• In contrast, a constructive proof actually derives the result.

244
EXAMPLE : For x ∈ R , x 6= 0, 1 :
n
X
k 1 − xn+1
x = , ∀n ≥ 0 , ( Geometric sum ) .
k=0
1−x

PROOF ( a constructive proof : already done earlier ) :

Let n
X
Sn = xk .
k=0
Then
Sn = 1 + x + x2 + · · · + xn−1 + xn ,

x · Sn = x + x2 + · · · + xn−1 + xn + xn+1 ,
so that
Sn − x · Sn = (1 − x) · Sn = 1 − xn+1 ,

from which the formula follows. QED !

245
ALTERNATE PROOF ( by induction ) :

(i) “By inspection” we find that the formula holds if n = 0 .

1−xn+1
(ii) Suppose that Sn = 1−x
, for some arbitary n, ( n ≥ 0 ) .

1−x(n+1)+1
Show Sn+1 = 1−x
:

n+1 1 − xn+1
Sn+1 = Sn + x = + xn+1
1−x
(1 − xn+1 ) + xn+1 (1 − x)
=
1−x
1 − xn+1 + xn+1 − xn+2
=
1−x
1 − x(n+1)+1
= . QED !
1−x

246
EXERCISE :

Use mathematical induction to prove that

21 | (4n+1 + 52n−1 ) ,

whenever n is a positive integer.

EXERCISE :

The Fibonacci numbers are defined as: f1 = 1 , f2 = 1 , and

fn = fn−1 + fn−2 , for n ≥ 3 .

Use a proof by induction to show that

3 | f4n ,

for all n ≥ 1 .

247
Variations on the Principle of Induction.

Let S = { s1 , s2 , s3 , · · · } be a countably infinite set and P a predicate :

P : S −→ { T , F } .

VARIATION 1 : ( as used so far · · · )

 h i
P (s1 ) ∧ ∀n ≥ 1 : P (sn ) ⇒ P (sn+1 ) ⇒ ∀n : P (sn ) .

VARIATION 2 :
 h i
P (s1 ) ∧ P (s2 ) ∧ ∀n ≥ 2 : P (sn−1 ) ∧ P (sn ) ⇒ P (sn+1 ) ⇒ ∀n : P (sn ) .

VARIATION · · ·

STRONG INDUCTION :
 h i
P (s1 ) ∧ ∀n ≥ 1 : P (s1 ) ∧ P (s2 ) ∧ · · · ∧ P (sn ) ⇒ P (sn+1 ) ⇒ ∀n : P (sn ) .

248
EXAMPLE : The Fibonacci Numbers.

The Fibonacci numbers are defined recursively as

f1 = 1 ,

f2 = 1 ,

fn = fn−1 + fn−2 , for n ≥ 3 .

249
f1 = 1 f11 = 89 f21 = 10946

f2 = 1 f12 = 144 f22 = 17711

f3 = 2 f13 = 233 f23 = 28657

f4 = 3 f14 = 377 f24 = 46368

f5 = 5 f15 = 610 f25 = 75025

f6 = 8 f16 = 987 f26 = 121393

f7 = 13 f17 = 1597 f27 = 196418

f8 = 21 f18 = 2584 f28 = 317811

f9 = 34 f19 = 4181 f29 = 514229

f10 = 55 f20 = 6765 f30 = 832040

250
PROPERTY :

There is an explicit formula for fn , namely

√  √  i
1 h  1+ 5 n  1− 5 n
fn = √ − .
5 2 2

251
We can also write

√  √  i
1 h  1+ 5 n  1− 5 n
fn = √ −
5 2 2

1  1 + √5 n h  1 − √5 n i
= √ 1 − √
5 2 1+ 5

1  1 + √5 n h  1 − 2.236 n i
≈ √ 1 −
5 2 1 + 2.236

1  1 + √5 n h  n i
= √ 1 + (−1)n+1 0.3819
5 2

1  1 + √5 n
≈ √ .
5 2

252
f1 = 1 ≈ 0.72361 f11 = 89 ≈ 88.99775

f2 = 1 ≈ 1.17082 f12 = 144 ≈ 144.00139

f3 = 2 ≈ 1.89443 f13 = 233 ≈ 232.99914

f4 = 3 ≈ 3.06525 f14 = 377 ≈ 377.00053

f5 = 5 ≈ 4.95967 f15 = 610 ≈ 609.99967

f6 = 8 ≈ 8.02492 f16 = 987 ≈ 987.00020

f7 = 13 ≈ 12.98460 f17 = 1597 ≈ 1596.99987

f8 = 21 ≈ 21.00952 f18 = 2584 ≈ 2584.00008

f9 = 34 ≈ 33.99412 f19 = 4181 ≈ 4180.99995

f10 = 55 ≈ 55.00364 f20 = 6765 ≈ 6765.00003

253
 h  √ n  √ n i
fn = √1 1+ 5
− 1− 5
5 2 2

PROOF (By Induction, using Variation 2) :

The formula is valid when n = 1 :

√ √ i
1 h 1+ 5 1− 5
f1 = √ − = 1 .
5 2 2

The formula is also valid when n = 2 :

√  √  i
1 h  1+ 5 2  1− 5 2 1 √
f2 = √ − = √ 5 = 1 .
5 2 2 5
(Check!)

254
Inductively, assume that we have

√  √ 
1 h  1 + 5 n−1  1 − 5 n−1 i
fn−1 = √ − ,
5 2 2

and
√  √  i
1 h  1+ 5 n  1− 5 n
fn = √ − .
5 2 2

We must show that

√  √ 
1 h  1 + 5 n+1  1 − 5 n+1 i
fn+1 = √ − .
5 2 2

255
Using the inductive hypothesis for n and n − 1 we have

fn+1 = fn−1 + fn (by definition)

√  √  √  √  i
1 h  1+ 5 n−1  1− 5 n−1  1+ 5 n  1− 5 n
= √ − + −
5 2 2 2 2
√  √  √  √ i
1 h  1 + 5 n−1  1+ 5  1 − 5 n−1  1− 5
= √ 1+ − 1+
5 2 2 2 2
√  √  √  √ i
1 h  1+ 5 n−1  3+ 5  1− 5 n−1  3− 5
= √ −
5 2 2 2 2
√  √  √  √  i
1 h  1+ 5 n−1  1+ 5 2  1− 5 n−1  1− 5 2
= √ −
5 2 2 2 2
√  √ 
1 h  1 + 5 n+1  1 − 5 n+1 i
= √ − . QED !
5 2 2

256
Direct solution of the Fibonacci recurrence relation.

f1 = 1 , f2 = 1 ,

fk = fk−1 + fk−2 , for k ≥ 3 .

Try solutions of the form

fn = c z n ,

This gives

c z n = c z n−1 + c z n−2 , or z n − z n−1 − z n−2 = 0 ,

from which we obtain the characteristic equation

z2 − z − 1 = 0 .

257
 z2 − z − 1 = 0

The characteristic equation has solutions (“roots”):

√
1 ± 1 + 4
z = ,
2
that is, √ √
1 + 5 1 − 5
z1 = , z2 = .
2 2

The general solution of the recurrence relation is then

fn = c1 z1n + c2 z2n .

258
 fn = c1 z1n + c2 z2n

The constants c1 and c2 are determined by the initial conditions :

f1 = 1 ⇒ c1 z1 + c2 z2 = 1 ,
and
f2 = 1 ⇒ c1 z12 + c2 z22 = 1 ,
that is, √ √
1+ 5 1− 5
c1 + c2 = 1,
2 2
and
 1 + √5 2  1 − √5 2
c1 + c2 = 1,
2 2
from which we find
1 1
c1 = √ and c2 = − √ . (Check!)
5 5

259
 fn = c1 z1n + c2 z2n

We found that
√ √
1 + 5 1 − 5
z1 = , z2 = .
2 2

and
1 1
c1 = √ and c2 = − √ . (Check!)
5 5

from which
√  √ 
1  1 + 5 n 1  1 − 5 n
fn = √ − √ .
5 2 5 2

260
 REVIEW EXERCISES.

Problem 1.

Prove that the Fibonacci numbers satisfy the following relations:

Pn
• k=1 f2k−1 = f2n , for n ∈ Z+ .

• fn−1 fn+1 − fn2 = (−1)n , for n ∈ Z+ , (n ≥ 2) .

• −f1 + f2 − f3 + · · · − f2n−1 + f2n = f2n−1 − 1 , for n ∈ Z+ .

261
Problem 2. The recurrence relation

xn+1 = c xn (1 − xn ) , n = 1, 2, 3, · · · ,

known as the logistic equation, models population growth when there are
limited resources.
Write a small computer program (using real arithmetic) to see what
happens to the sequence xn , n = 1, 2, 3, · · · , with 0 < x1 < 1 , for
each of the following values of c :
(a) 0.5 , (b) 1.5 , (c) 3.2 , (d) 3.5 , (e) 3.9

Problem 3. Find an explicit solution to the recurrence relation

xn+1 = 3 xn − 2 xn−1 , n = 1, 2, 3, · · · ,

with x1 = 1 and x2 = 3 .

262
 RELATIONS

A binary relation relates elements of a set to elements of another set.

EXAMPLE :

The operator “≤” relates elements of Z to elements of Z. e.g.,

2 ≤ 5, and 3≤3, but 7 6≤ 2 .

We can also view this relation as a function

≤ : Z × Z −→ {T , F } .

263
RECALL :

Let
A = {a1 , a2 , · · · , anA } and B = {b1 , b2 , · · · , bnB } .

The product set A × B is the set of all ordered pairs from A and B.

More precisely,

A × B ≡ {(a, b) : a ∈ A, b ∈ B} .

264
NOTE :

• The product set A × B has nA · nB elements.

• If A and B are distinct and nonempty then A × B 6= B × A.

EXAMPLE :

If
A = {!, ?} and B = {•, ◦ , },
then

A × B = { (!, •) , (!, ◦) , (!, ) , (?, •) , (?, ◦) , (?, ) } .

265
We can now equivalently define :

DEFINITION :

A binary relation R from A to B is a subset of A × B.

NOTATION :

If R ⊆ A × B, and
(a, b) ∈ R ,
then we say that
“a is R-related to b”,
and we also write
aRb .

266
EXAMPLE :

Let A = {1, 3} and B = {3, 5, 9}.

Let R denote the relation “divides” from A to B, i.e.,

aRb if and only if a|b .

Then
1R3 , 1R5 , 1R9 , 3R3 , and 3R9 .

Thus
R = { (1, 3) , (1, 5) , (1, 9) , (3, 3) , (3, 9) } .

267
We can represent R by the following diagram

A B
1
5

9
3
3

This representation is an example of a directed bipartite graph.

Note that R is not a function, since it is multi-valued.

268
REMARK :

We see that a relation generalizes the notion of a function.

Unlike functions from a set A to a set B :

• A relation does not have to be defined for all a ∈ A .

• A relation does not have to be single-valued.

269
A finite relation from a set A into itself can be represented
by an ordinary directed graph.

EXAMPLE :

Let

A = {1 , 2 , 3 , 4 , 5 , 6} ,

and let R denote the relation “divides” from A to A .

We say that R is a relation “on A” .

This relation has the following directed graph representation :

270
 2 3

1 4

6 5

The “divides” relation on the set A .

271
We can compose relations as follows :

Let R be a relation from A to B , and S a relation from B to C.

R S

A B C

S oR

Then S ◦ R is the relation from A to C defined by

a(S ◦ R)c if and only if ∃b ∈ B : aRb ∧ bSc .

272
EXAMPLE :

Let

A = {1, 2, 3}, B = {2, 6}, and C = {1, 9, 15},

and define the relations R and S by

aRb if and only if a|b ,

and
bSc if and only if b + c is prime .

Define
T = S◦R .

273
Then from the diagram below we see that

T = { (1, 1) , (1, 9) , (1, 15) , (2, 1) , (2, 9) , (2, 15) , (3, 1) } .

R S

A B C
1 1
2
2 9
6
3 15

S oR = T

274
Let A, B, C, and D be sets, and let R S, and T be relations :

R : A −→ B , S : B −→ C , T : C −→ D .

PROPOSITION :

The composition of relations is associative, i.e.,

(T ◦ S) ◦ R = T ◦ (S ◦ R) .

R S T
A B C D

S oR ToS
To S oR

275
 R S T
A B C D

S oR ToS
To S oR

(T ◦ S) ◦ R = T ◦ (S ◦ R) .

PROOF : Let a ∈ A and d ∈ D. Then

a(T ◦ S) ◦ Rd ⇐⇒ ∃b ∈ B : (aRb ∧ bT ◦ Sd)

⇐⇒ ∃b ∈ B, ∃c ∈ C : (aRb ∧ bSc ∧ cT d)

⇐⇒ ∃c ∈ C, ∃b ∈ B : (aRb ∧ bSc ∧ cT d)

⇐⇒ ∃c ∈ C : (aS ◦ Rc ∧ cT d) ⇐⇒ aT ◦ (S ◦ R)d .
QED !

276
EXAMPLE : Let the relation R on

A = { 2, 3, 4, 8, 9, 12 } ,
be defined by

(a, b) ∈ R if and only if (a|b ∧ a 6= b) .

Then

R = { (2, 4) , (2, 8) , (2, 12) , (3, 9) , (3, 12) , (4, 8) , (4, 12) } ,

and
R2 ≡ R ◦ R = { (2, 8) , (2, 12) } ,

R3 ≡ R2 ◦ R = R ◦ R ◦ R = { } .

277
 R R R
21
0
0
1 21
0
0
1 0
1
21
0 1
0
02
1

31
0 31 11
00
0
1 31
0
0
1 0
10 00
11
003
11

4
4 1
0 1
0 1
0 1
0
0
1 0
1 0
1 0
1 4
4

81
0
0
1 1
0
08
1 1
0
08
1 1
0
0
1 8

91
0
0
1 1
0
09
1 1
0
09
1 1
0
0
1 9

00
11 0
1 1
0 1
0
12
00
11 12 1
0 0 12
1 0 12
1

R2
R3
278
EXAMPLE :

Let R be the relation on the set of all real numbers defined by

xRy if and only if xy = 1

Then
xR2 z ⇐⇒ ∃y : xRy and yRz

⇐⇒ ∃y : xy = 1 and yz = 1

⇐⇒ x = z and x 6= 0 . (Why ?)

279
The last equivalence in detail:

∃y : xy = 1 and yz = 1 if and only if x = z and x 6= 0 .

PROOF : (⇒) Let x and z be real numbers, and assume that

∃y : xy = 1 and yz = 1 .

Then x and z cannot equal zero.

Thus we can write

1 1
y = and y = .
x z

Hence 1/x = 1/z, i.e., x = z.

Thus x = z and x 6= 0 .

280
 ∃y : xy = 1 and yz = 1 if and only if x = z and x 6= 0 .

(⇐)

Conversely, suppose x and z are real numbers with

x=z and x 6= 0 .

Let y = 1/x.

Then xy = 1 and yz = 1.

QED !

281
Similarly

xR3 z ⇐⇒ ∃y : xR2 y and yRz

⇐⇒ ∃y : x = y and x 6= 0 and yz = 1

⇐⇒ xz = 1 (Why ?)
Thus
R3 = R ,
R4 = R3 ◦ R = R ◦ R = R2 ,
R5 = R4 ◦ R = R2 ◦ R = R3 = R,
and so on · · ·

Thus we see that

Rn = R2 if n is even ,
and
Rn = R if n is odd .

282
EXAMPLE :

Let R be the relation on the real numbers defined by

xRy if and only if x2 + y 2 ≤ 1 .

Then
xR2 z ⇐⇒ ∃y : xRy and yRz

⇐⇒ ∃y : x2 + y 2 ≤ 1 and y 2 + z 2 ≤ 1

⇐⇒ x2 ≤ 1 and z 2 ≤ 1 (Why ?)

⇐⇒ | x | ≤ 1 and | z | ≤ 1 .

283
 y z
1

−1 1
1
x x
R R2

−1

The relations R and R2 as subsets of R2 .

284
Similarly

xR3 z ⇐⇒ ∃y : xR2 y and yRz

⇐⇒ ∃y : | x | ≤ 1 and | y | ≤ 1 and y 2 + z 2 ≤ 1

⇐⇒ ∃y : | x | ≤ 1 and y 2 + z 2 ≤ 1 (Why ?)

⇐⇒ | x | ≤ 1 and | z | ≤ 1 (Why ?)

Thus R3 = R2 .

285
Similarly

R4 = R3 ◦ R = R2 ◦ R = R3 = R2 ,

R5 = R4 ◦ R = R2 ◦ R = R3 = R2 ,

and so on · · ·

Thus we see that

Rn = R2 for all n ≥ 2 .

286
The relation matrix.

A relation between finite sets can be represented by a relation matrix.

(Also known as the transition matrix).

For a relation R from A to B the relation matrix R has entries


 0 if (ai , bj ) 6∈ R ,
Rij =
1 if (ai , bj ) ∈ R .


287
EXAMPLE :

Reconsider the example where

A = {1, 2, 3}, B = {2, 6}, and C = {1, 9, 15} ,

aRb if and only if a|b, and bSc if and only if b + c is prime .

R S

A B C
1 1
2
2 9
6
3 15

S oR = T

288
 R S

A B C
1 1
2
2 9
6
3 15

S oR = T

The relation matrices of R and S are

2 6 1 9 15
1 1 1  
2 1 1 1
R = 2 1 1 and S = .
6 1 0 0
3 0 1

289
We found that

T = S ◦ R = { (1, 1) , (1, 9) , (1, 15) , (2, 1) , (2, 9) , (2, 15) , (3, 1) } .

R S

A B C
1 1
2
2 9
6
3 15

S oR = T

290
 R S

A B C
1 1
2
2 9
6
3 15

S oR = T
The relation matrices of R and S were found to be
 
1 1  
1 1 1
R = 1 1  , S = .
1 0 0
0 1
The relation matrix of T = S ◦ R is
 
1 1 1
T = 1 1 1 .
1 0 0

291
PROPOSITION :

Let A, B, and C be finite sets.

Let R be a relation from A to B.

Let S be a relation from B to C.

Let T = S ◦ R.

Then the relation matrix of T has the same zero-structure

as the matrix product RS.

292
PROOF :

Tij = 1 ⇐⇒ ai T cj

⇐⇒ ai Rbk and bk Scj , for some bk ∈ B

⇐⇒ Rik = 1 and Skj = 1 for some k

PnB
⇐⇒ ℓ=1 Riℓ Sℓj 6= 0

⇐⇒ [RS]ij 6= 0 . QED !

293
REMARK :

If we use Boolean arithmetic, then T = RS .

EXAMPLE :

The matrix product RS in the preceding example is

   
1 1   2 1 1
1 1 1 1 1
= 2 1 1 .
1 0 0
0 1 1 0 0

Using Boolean arithmetic the matrix product is

 
1 1 1
T = 1 1 1 .
1 0 0

294
The inverse of a relation.

Let R be a relation from A to B.

Then the inverse relation R−1 is the relation from B to A defined by

b R−1 a if and only if aRb,

or, in equivalent notation,

(b, a) ∈ R−1 if and only if (a, b) ∈ R .

Thus, unlike functions, relations are always invertible.

295
EXAMPLE :
A
B
1 a

2
b
3

Here
R = {(1, a), (1, b), (2, a), (3, b)} ,
and
R−1 = {(a, 1), (a, 2), (b, 1), (b, 3)} .

The relation matrices are

 
1 1  
1 1 0
R = 1 0, R−1 = .
1 0 1
0 1

296
Note that

R−1 = RT (transpose) .

This holds in general, because if

A = {a1 , a2 , · · · , anA } , B = {b1 , b2 , · · · , bnB } ,

then, by definition of R−1 we have for any ai , bj that

bj R−1 ai ⇐⇒ ai Rbj .

Hence [R−1 ]ji = Rij .

297
EXERCISE : Let R be the relation on the set

A = {1, 2, 3, 4},
defined by
a1 Ra2 if and only if a1 < a2 .

• Write down R as a subset of A × A .

• Show the relation matrix of R .

• Do the same for R2 , R3 , · · ·

EXERCISE : Do the same for a1 Ra2 if and only if a1 ≤ a2 .

EXERCISE : Do the same for a1 Ra2 if and only if a1 + a2 = 5 .

EXERCISE : Do the same for the set Z instead of A .

298
DEFINITION : Let R be a relation on A (i.e., from A to A).

• R is called reflexive if
∀a ∈ A : (a, a) ∈ R, i .e., ∀a ∈ A : aRa ,

i.e., if the relation matrix R (for finite A) satisfies

∀i : Rii = 1 .

EXAMPLES :

The “divides” relation on Z+ is reflexive.

The “≤” relation on Z is reflexive.

The “⊆” relation on a power set 2A is reflexive.

The “<” relation on Z is not reflexive.

299
• R is symmetric if
∀a, b ∈ A : aRb → bRa ,
or, equivalently,
aRb ⇒ bRa ,

i.e., if the relation matrix (for finite A) is symmetric :

∀i, j : Rij = Rji .

EXAMPLES :

The relation on the real numbers defined by

xRy if and only if x2 + y 2 ≤ 1 ,

is symmetric.

The “divides” relation on Z+ is not symmetric.

300
• R is antisymmetric if for all a, b ∈ A we have

aRb ∧ bRa ⇒ a = b ,

or equivalently,

a 6= b ⇒ ¬(aRb) ∨ ¬(bRa) ,

i.e., if the relation matrix (for finite A) satisfies

∀i, j with i 6= j : Rij Rji 6= 1 .

EXAMPLES :

The “≤” relation on Z is antisymmetric.

The “divides” relation on Z+ is antisymmetric.

The “⊆” relation on a power set 2A is antisymmetric.

301
• R is transitive if
aRb ∧ bRc ⇒ aRc .

We’ll show later that R is transitive if and only if

n
X
Rk = R
k=1

in Boolean arithmetic

EXAMPLES :

The “divides” relation on Z+ is transitive.

The “≤” relation on Z is transitive.

The “⊆” relation on a power set 2S is transitive.

The relation aRb ⇐⇒ “a + b is prime” on Z+ is not transitive.

302
EXERCISE : Let A be a set of n elements.

• How many relations are there on A ?

How many relations are there on A that are :

• symmetric ?
• antisymmetric ?

• symmetric and antisymmetric ?

• reflexive ?

• reflexive and symmetric ?

(∗)
• transitive ?

(∗)
Hint : Search the web for “the number of transitive relations” !

303
• An equivalence relation is a relation that is

- reflexive

- symmetric

- transitive.

EXAMPLE :

The following relation on Z is an equivalence relation :

aRb if and only if a mod m = b mod m .

(Here m ≥ 2 is fixed.)

304
• A partial order is a relation that is
- reflexive
- antisymmetric
- transitive.

EXAMPLES :
The “divides” relation on Z+ .

- The “≤” relation on Z+ .

- The “⊆” relation on the power set 2S .

- The operator “<” on Z is not a partial order:

(It is antisymmetric (!) and transitive, but not reflexive.)

305
• A relation R on a set A is called a total order if

- R is a partial order, and

- ∀a, b ∈ A we have aRb or bRa .

EXAMPLES :

- The partial order “≤” is also a total order on Z+ .

- The partial order m|n on Z+ is not a total order.

(For example 5 6 |7 and 7 6 |5 .)

- The partial order “⊆” on 2S is not a total order.

306
Equivalence classes.

Let A be a set and let R be an equivalence relation on A .

Let a1 ∈ A.

Define
[a1 ] = {a ∈ A : aRa1 } ,
that is

[a1 ] = all elements of A that “are equivalent ” to a1 .

Then [a1 ] is called the equivalence class generated by a1 .

307
EXAMPLE :

Let R be the relation “congruence modulo 3” on Z+ , i.e.,

aRb if and only if a mod 3 = b mod 3 .

For example

1R1 , 1R4 , 1R7 , 1R10 , · · · ,

2R2 , 2R5 , 2R8 , 2R11 , · · · ,

3R3 , 3R6 , 3R9 , 3R12 , · · · .

308
Thus
[1] = { 1 , 4 , 7 , 10 , 13 , · · · } ,

[2] = { 2 , 5 , 8 , 11 , 14 , · · · } ,

[3] = { 3 , 6 , 9 , 12 , 15 , · · · } .

We see that
Z+ = [1] ∪ [2] ∪ [3] .

• The relation R has partitioned Z+ into the subsets [1] , [2] , [3] .

• Any member of a subset can represent the subset, e.g.,

[11] = [2] .

309
EXAMPLE :

Consider Z × Z , the set of all ordered pairs of integers.

Define a relation R on Z × Z by

(a1 , b1 )R(a2 , b2 ) if and only if a1 − b1 = a2 − b2 .

Note that R can be viewed as subset of

(Z × Z) × (Z × Z) .

310
 (a1 , b1 )R(a2 , b2 ) if and only if a1 − b1 = a2 − b2

R is an equivalence relation :

• R is reflexive : (a, b)R(a, b) ,

• R is symmetric : (a1 , b1 )R(a2 , b2 ) ⇒ (a2 , b2 )R(a1 , b1 ) ,

• R is transitive:
(a1 , b1 )R(a2 , b2 ) ∧ (a2 , b2 )R(a3 , b3 ) ⇒ (a1 , b1 )R(a3 , b3 ) .
.

311
 (a1 , b1 )R(a2 , b2 ) if and only if a1 − b1 = a2 − b2

The equivalence classes are

Ak = { (a, b) : a − b = k } .

For example,

A1 = [(2, 1)] = {· · · , (−1, −2) , (0, −1) , (1, 0) , (2, 1) , · · ·} .

The sets Ak partition the set Z × Z , namely,

Z×Z = ∪∞
k=−∞ Ak .

312
b A −3 A −2 A −1
A0

A1

A
2

A3

313
DEFINITION :

• The reflexive closure of R is the smallest relation containing R that

is reflexive.

• The symmetric closure of R is the smallest relation containing R

that is symmetric.

• The transitive closure of R is the smallest relation containing R

that is transitive.

314
EXAMPLE :

Let A = {1, 2, 3, 4} , and let R be the relation on A defined by

R = { (1, 4) , (2, 1) , (2, 2) , (3, 2) , (4, 1) } .

Then R is not reflexive, not symmetric, and not transitive :

111
00
00
11
00
11
11
00
00
11
2
00
11

11
00 11
00
00
11 00
11
00
11
4
00
11
3

315
The reflexive closure of R is :

1 1010 2
1
0
0
1
0
1

1
0 1
0
4
0
1 0
1
3

316
The symmetric closure of R is :

111
00
00
11
00
11
2
11
00
00
11
00
11

11
00 11
00
00
11
4
00
11
3

317
To get the transitive closure of R :

111
00
00
11
00
11
2
11
00
00
11
00
11

11
00 11
00
00
11
4
00
11
3

318
To get the transitive closure of R :

111
00
00
11
00
11
2
11
00
00
11
00
11

11
00 11
00
00
11
4
00
11
3

319
To get the transitive closure of R :

111
00
00
11
00
11
2
11
00
00
11
00
11

11
00 11
00
00
11
4
00
11
3

320
The transitive closure of R is :

111
00
00
11
2
1
0
0
1

11
00 1
0
00
11 0
1
00
11
4
0
1
3

321
PROPERTY : The transitive closure R∗ of a relation R is given by

k
R∗ = ∪∞
k=1 R .

PROOF : Later · · ·

PROPERTY : For a finite set of n elements, the relation matrix of

the transitive closure is
n
X
R∗ = Rk (using Boolean arithmetic) .
k=1

NOTE : It suffices to sum only the first n powers of the matrix R !

322
EXAMPLE : In the preceding example,

R = { (1, 4) , (2, 1) , (2, 2) , (3, 2) , (4, 1) } ,

1 1010 1
0
0
1
2
0
1

1
0 1
0
4
0
1 0
1
3

we have the relation matrix :

 
0 0 0 1
1 1 0 0
R = 
0
 .
1 0 0
1 0 0 0

323
Thus, using Boolean arithmetic,

     
0 0 0 1 0 0 0 1 1 0 0 0
1 1 0 0
R2  1 1 0 0 = 1 1 0 1
 
= R · R = 
0
 ,
1 0 0 0 1 0 0 1 1 0 0
1 0 0 0 1 0 0 0 0 0 0 1

     
0 0 0 1 1 0 0 0 0 0 0 1
1 1 0 0 1 1 0 1 1 1 0 1
R3 = R · R2

= 
0
 =   ,
1 0 0 1 1 0 0 1 1 0 1
1 0 0 0 0 0 0 1 1 0 0 0

     
0 0 0 1 0 0 0 1 1 0 0 0
1 1 0 0 1 1 0 1
R4 = R · R3  = 1 1 0 1

= 
0
   .
1 0 0 1 1 0 1 1 1 0 1
1 0 0 0 1 0 0 0 0 0 0 1

324
Therefore

4
X
R∗ = Rk = R + R2 + R3 + R4 =
k=1

       
0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0
1 1 0 0 + 1 1 0 1 + 1 1 0 1 + 1 1 0 1
  
 
0 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1
1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1

 
1 0 0 1
1 1 0 1
= 
1
 .
1 0 1
1 0 0 1

325
The graph of R∗ (shown before) is :

111
00
00
11
2
1
0
0
1

11
00 1
0
00
11
4
0
1
3

which indeed has the relation matrix

 
1 0 0 1
4
X 1 1 0 1
R∗ = Rk = 
1
 .
1 0 1
k=1
1 0 0 1

326
RECALL : The transitive closure R∗ of a relation R is given by

k
R∗ = ∪∞
k=1 R (to be proved later · · · )

EXAMPLE : Consider the relation R on the real numbers

xRy if and only if xy = 1 .

Earlier we found that

xR2 y if and only if x = y ∧ x 6= 0 ,

and
R = R3 = R5 = ··· ,
R2 = R4 = R6 = ··· .

Thus the transitive closure is

xR∗ y if and only if xy = 1 ∨ (x = y ∧ x 6= 0) .

327
EXAMPLE : Again consider the relation R on the real numbers

xRy if and only if x2 + y 2 ≤ 1 .

Earlier we found that

xR2 y if and only if |x| ≤ 1 ∧ |y| ≤ 1,

and
Rn = R2 , for n ≥ 2 .

Thus the transitive closure is

xR∗ y if and only if x2 + y 2 ≤ 1 ∨ ( | x |≤ 1 ∧ | y |≤ 1 ) ,

that is,

xR∗ y if and only if |x| ≤ 1 ∧ |y| ≤ 1. (Why ?)

328
EXERCISE : Let R be the relation on the real numbers given by

xRy if and only if x2 + y 2 = 1 .

• Draw R as a subset of the real plane.

• Is R reflexive?

• Is R symmetric?

• Is R antisymmetric?

• Is R transitive?

• What is R2 ? (Be careful!)

• What is R3 ?

• What is the transitive closure of R ?

329
EXERCISE : Let R be the relation on the real numbers given by

xRy if and only if xy ≤ 1 .

• Draw R as a subset of the real plane.

• Is R reflexive?

• Is R symmetric?

• Is R antisymmetric?

• Is R transitive?

• What is R2 ?

• What is R3 ?

• What is the transitive closure of R ?

330
EXERCISE : Let R be the relation on the real numbers given by

xRy if and only if x2 ≤ y .

• Draw R as a subset of the real plane.

• Is R reflexive?

• Is R symmetric?

• Is R antisymmetric?

• Is R transitive?

• What is R2 ?

• What is R3 ?

• What is Rn ? (Prove your formula for Rn by induction.)

• What is the transitive closure of R ?

331
 xRy if and only if x2 ≤ y

Then
xR2 z ⇐⇒ ∃y : xRy and yRz

⇐⇒ ∃y : x2 ≤ y and y 2 ≤ z

⇐⇒ x4 ≤ z .
Similarly
xR3 z ⇐⇒ ∃y : xR2 y and yRz

⇐⇒ ∃y : x4 ≤ y and y 2 ≤ z

⇐⇒ x8 ≤ z .
By induction one can prove that
n 2n
xR z ⇐⇒ x ≤ z.

332
We see that

• The relation R corresponds to the area of the x, y-plane that

lies on or above the curve y = x2 .

• The relation R2 corresponds to the area of the x, y-plane that

lies on or above the curve y = x4 .

• The relation Rn corresponds to the area of the x, y-plane that

2n
lies on or above the curve y = x .

333
The transitive closure is
k
R∗ = ∪∞
k=1 R .
(to be proved later · · · )

We find that R∗ is the union of the following two regions:

• The area of the x, y-plane that lies on or above the curve

y = x2 (i.e., the area that corresponds to the relation R ).

• The area inside the rectangle whose corners are located at

(x, y) = (−1, 0) , (1, 0) , (1, 1) , (−1, 1) ,
(excluding the border of this rectangle).

(Check!)

334
Let R be a relation on a set A .

Recursively define

R1 = R , Rn+1 = Rn ◦ R , n = 1, 2, 3, · · · .

Then for all n ∈ Z+ we have:

PROPERTY 1 : Rn ◦ R = R ◦ Rn

PROPERTY 2 : R symmetric ⇒ Rn is symmetric

EXERCISE : Use induction to prove these properties.

335
 PROPERTY 1 : Rn ◦ R = R ◦ Rn , for all n ∈ Z+

PROOF : Clearly, the equality holds if n = 1.

Inductive assumption :
Rn ◦ R = R ◦ Rn , for some arbitrary n ∈ Z+ .
We must show that
Rn+1 ◦ R = R ◦ Rn+1 .
To do this :
Rn+1 ◦ R = (Rn ◦ R) ◦ R (by definition)

= (R ◦ Rn ) ◦ R (by inductive assumption)

= R ◦ (Rn ◦ R) (by associativity)

= R ◦ Rn+1 (by definition). QED !

336
 PROPERTY 2 : R symmetric ⇒ Rn is symmetric

PROOF : Clearly True if n = 1 .

Inductively assume that Rn is symmetric.
We must show that Rn+1 is symmetric:
aRn+1 b ⇐⇒ aRn ◦ Rb (by definition of power)

⇐⇒ ∃p(aRp ∧ pRn b) (by definition of composition)

⇐⇒ ∃p(pRa ∧ bRn p) (since R and Rn are symmetric)

⇐⇒ ∃p(bRn p ∧ pRa) (commutative law of logic)

⇐⇒ bR ◦ Rn a (by definition of composition)

⇐⇒ bRn ◦ Ra (by Property 1)

⇐⇒ bRn+1 a (by definition of power) . QED !

337
Let R be a relation on a set A and let n ∈ Z+ .

PROPERTY 3 : R transitive ⇒ Rn is transitive

PROOF :

Let R be transitive.

Obviously R1 is transitive.

By induction assume that Rn is transitive for some n ∈ Z+ .

We must show that Rn+1 is transitive, i.e., we must show that

aRn+1 b ∧ bRn+1 c ⇒ aRn+1 c .

338
 Given R and Rn are transitive. Show Rn+1 is transitive

· · · continuation of proof · · ·

aRn+1 b ∧ bRn+1 c
⇒ aRn ◦ Rb ∧ bRn ◦ Rc (power)

⇒ aRn ◦ Rb ∧ bR ◦ Rn c (by Property 1)

⇒ aRp ∧ pRn b ∧ bRn q ∧ qRc (∃p, q: composition)

⇒ aRp ∧ pRn q ∧ qRc (inductive assumption)

⇒ aRn ◦ Rq ∧ qRc (composition)

⇒ aR ◦ Rn q ∧ qRc (by Property 1)

339
 Given R and Rn are transitive. Show Rn+1 is transitive.

· · · continuation of proof · · ·

aR ◦ Rn q ∧ qRc

⇒ aRn s ∧ sRq ∧ qRc (∃s: composition)

⇒ aRn s ∧ sRc (since R is transitive)

⇒ aR ◦ Rn c (composition)

⇒ aRn ◦ Rc (by Property 1)

⇒ aRn+1 c (power) QED !

340
Let R and S be relations on a set A .
Recall that we can also think of R as a subset of A × A .

We have:
PROPERTY 4 : R ⊆ S ⇒ Rn ⊆ S n

PROOF : The statement clearly holds when n = 1 .

Inductive step:
Given R ⊆ S and Rn ⊆ S n . Show Rn+1 ⊆ S n+1

To do this :
Suppose that (x, z) ∈ Rn+1 .
Then ∃y : (x, y) ∈ R and (y, z) ∈ Rn .
By the assumptions (x, y) ∈ S and (y, z) ∈ S n .
Hence (x, z) ∈ S n+1 . QED !

341
Let S be a relation on a set A .

PROPERTY 5 : S is transitive if and only if ∀n ∈ Z+ : S n ⊆ S

PROOF :

(⇐) (∀n ∈ Z+ : S n ⊆ S) ⇒ S is transitive

Let (x, y) ∈ S and (y, z) ∈ S .

Then, by definition of composition, (x, z) ∈ S 2 .

Since, in particular, S 2 ⊆ S it follows that (x, z) ∈ S .

Hence S is transitive.

342
(⇒) S is transitive ⇒ ∀n ∈ Z+ : S n ⊆ S

By induction :

Clearly S n ⊆ S if n = 1 .

Suppose that for some n we have S n ⊆ S .

We must show that S n+1 ⊆ S .

343
 Given (1): S is transitive, and (2): S n ⊆ S . Show S n+1 ⊆ S

To do this, suppose that (x, z) ∈ S n+1 .

We must show that (x, z) ∈ S .

By definition of composition, (x, z) ∈ S n ◦ S , and hence

∃y : (x, y) ∈ S and (y, z) ∈ S n .

By inductive hypothesis (2) (y, z) ∈ S .

Thus (x, y) ∈ S and (y, z) ∈ S .

By assumption (1) S is transitive, so that (x, z) ∈ S . QED !

344
THEOREM :

The transitive closure R∗ of a relation R is given by

k
R∗ = ∪∞
k=1 R .

k
PROOF : Let U = ∪∞
k=1 R .

We must show that

(1) U is transitive.

(2) U is the smallest transitive relation containing R .

If so, then R∗ = U .

345
 k
U = ∪∞
k=1 R ⋆

(1) We first show that U is transitive :

Suppose (x, y) ∈ U and (y, z) ∈ U .
We must show that (x, z) ∈ U .

From ⋆ it follows that

(x, y) ∈ Rm and (y, z) ∈ Rn , for some m, n ∈ Z+ .

By definition of composition
(x, z) ∈ Rn+m .

Thus, using ⋆ again, it follows that

(x, z) ∈ U .

346
 k
U = ∪∞
k=1 R ⋆

(2) Show U is the smallest transitive relation containing R :

To do this it suffices to show that :

( S transitive and R ⊆ S ) ⇒ U ⊆S .

R
U

347
 k
U = ∪∞
k=1 R ⋆

R ⊆ S ⇒ Rn ⊆ S n Property 4

S is transitive ⇐⇒ ∀n ∈ Z+ : S n ⊆ S Property 5

To do: Given S transitive and R ⊆ S . Show U ⊆ S

Let (x, y) ∈ U . Then, by ⋆ we have

(x, y) ∈ Rn for some n ∈ Z+ .

By Property 4 : (x, y) ∈ S n .

By Property 5 : (x, y) ∈ S . QED !

348
 REVIEW PROBLEMS

and

REVIEW CLICKER QUESTIONS

349
Review Problem 1.

Prove that for every integer n we have

n5 − n ≡ 0 (mod 30)

350
Review Problem 2.

Suppose m and n are relatively prime integers; m ≥ 2 , n ≥ 2 .

Prove that logm n is an irrational number.

351
Review Problem 3. If A and B are sets, and if

f : A −→ B ,

then for any subset S of B we define the pre-image of S as

f −1 (S) ≡ {a ∈ A : f (a) ∈ S} .

NOTE : f −1 (S) is defined even if f does not have an inverse!

Let S and T be subsets of B .

Prove that

f −1 (S ∩ T ) = f −1 (S) ∩ f −1 (T )

352
Review Problem 4.

Prove that if a , b , and c are integers such that

m≥2 and a ≡ b(mod m)

then

gcd(a, m) = gcd(b, m) .

353
Review Problem 5.

Use mathematical induction to prove that

21 | (4n+1 + 52n−1 ) ,

whenever n is a positive integer.

354
Review Problem 6.

The Fibonacci numbers are defined as: f1 = 1 , f2 = 1 , and

fn = fn−1 + fn−2 , for n ≥ 3 .

Use a proof by induction to show that

fn−1 fn+1 − fn2 = (−1)n

for all n ≥ 2 .

355
Review Problem 7.

Let A and B be non-empty sets.

Let f be a 1 − 1 function from A to B .

Suppose S is an partial order on B .

Define a relation R on A as follows:

∀a1 , a2 ∈ R : a1 Ra2 ⇐⇒ f (a1 )Sf (a2 ) .

Prove that R is an partial order on A .

356