Module - II

SEM: III

Course: Discrete Mathematics & Graph Theory

Course Code: 22CS2304

Module II - RELATIONS AND ORDER RELATIONS

Contents

1. Closure of relations

2. Equivalence Relations

3. Partial Orderings

4. Functions

5. The Growth of Functions

Self-Study

1. Transitive Closure

2. Warshall’s Algorithm

Course Name: DMGT School of Engineering, DSU 2

1. Closure of Relations

➢ Consider set A and the collection of all relations on A.

➢ Let P be a property of such relations such as being symmetric or being transitive or being reflexive.

➢ A relation with property P will be called a P-relation.

➢ The P-closure of an arbitrary relation R on A written (P(R)), is a P-relation such that,

R ⊆ P(R) ⊆ S → for every P-relation S containing R.

➢ We will write reflexive (R), symmetric (S) and transitive (T) for the reflexive, symmetric and transitive closures of R.

NOTE: Generally P(R) need not exist. However, in general situation P(R) will always exist.

Course Name: DMGT School of Engineering, DSU 3

Definition

➢ The closure of a relation R with respect to property P is the relation obtained by adding the minimum number of

ordered pairs to R to obtain property P.

OR

➢ Let R be a relation on a set A. R may or may not have some property P, such as reflexivity, symmetry, or transitivity.

If there is a relation S with property P containing R such that S is a subset of every relation with property P

containing R, then S is called the closure of R with respect to P.

Course Name: DMGT School of Engineering, DSU 4

Discussion

➢ Let A be the set and R be the relation on set A.

➢ Let, P be the property and property can be reflexive, symmetric or transitive.

➢ If relation R on set A, does not satisfy any property or some property. In order to make relation R satisfy

the property, some ordered pairs are added and a new relation S is formed which satisfies the property.

➢ S is called the closure of relation with respect to P.

➢Add only necessary/ smallest/ minimum number of ordered pairs to make relation satisfy the property.

➢Upon adding ordered pairs, the new relation formed must satisfy the property.

➢A new relation formed must contain relation R i.e., R is a subset of new relation say S → R ⊆ S

Course Name: DMGT School of Engineering, DSU 5

Diagonal Relation

➢ Let A be a set and let Δ = {(x, x) | x in A}. Δ is called a diagonal relation on A and sometimes

it is called the equality relation E.

Course Name: DMGT School of Engineering, DSU 6

Reflexive Closure
➢ Let R be a relation on A. The reflexive closure of R, denoted by r(R) is R ∪ Δ.

➢ In other words, reflexive (R) is obtained by simply adding to R those elements (a, a) in the diagonal

which do not already belong to R.

NOTE:

➢ Add loops to all vertices on the digraph.

➢ Put 1’s on the diagonal of the connection matrix of R.

➢ The reflexive relation r(R) of a relation R is the smallest reflexive relation that contains R as a subset.

Course Name: DMGT School of Engineering, DSU 7

Reflexive Closure - Example

➢ The relation R = {(1, 1), (1, 2), (2, 1), (3, 2)} on the set A = {1, 2, 3} is not reflexive.

➢ How can we produce a reflexive relation containing R that is as small as possible?

➢ This can be done by adding (2, 2) and (3, 3) to R, because these are the only pairs of the form (a, a)

that are not in R.

➢ This new relation is called the reflexive closure of R.

Course Name: DMGT School of Engineering, DSU 8

Reflexive Closure

➢ Let, N be a set of positive integers and R be a relation i.e. less than ( < ) on the set. Determine reflexive

closure of R.

r(R) = r(<) = < ∪ ≤ = {(a, b) : a ≤ b}

➢ General Formula

𝑅𝑟+ = R ∪ Δ where Δ = {(a, a) | ∀ a ∈ A}

➢ The closure of a relation R w.r.t property P is the relation obtained by adding minimum number of

ordered pairs of R to obtain property P.

Course Name: DMGT School of Engineering, DSU 9

Problem1

Let, A = {1, 2, 3, 4} and R = {(1, 2), (2, 1), (1, 1), (2, 2)}. Compute Reflexive r(R).

r (R) = R ∪ Δ

Δ = {(1, 1), (2, 2), (3, 3), (4, 4)}

R ∪ Δ = {(1, 2), (2, 1), (1, 1), (2, 2)} ∪ {(1, 1), (2, 2), (3, 3), (4, 4)}

R ∪ Δ = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1)}

r(R) = {(1, 1), (2, 2), (3, 3), (4, 4), {(1, 2), (2, 1)}

Course Name: DMGT School of Engineering, DSU 10

Problem2

Let, A = {1, 2, 3, 4} and R = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3)}. Compute Reflexive r(R).

r (R) = R ∪ Δ

Δ = {(1, 1), (2, 2), (3, 3), (4, 4)}

R ∪ Δ = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3)} ∪ {(1, 1), (2, 2), (3, 3), (4, 4)}

R ∪ Δ = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (2, 4), (3, 1), (4, 3)}

r(R) = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (2, 4), (3, 1), (4, 3)}

Course Name: DMGT School of Engineering, DSU 11

Problem3

Let, A = {1, 2, 3} and R = ∅. Compute Reflexive r(R).

r (R) = R ∪ Δ

Δ = {(1, 1), (2, 2), (3, 3)}

R ∪ Δ = ∅ ∪ {(1, 1), (2, 2), (3, 3)}

R ∪ Δ = {(1, 1), (2, 2), (3, 3)}

r(R) = {(1, 1), (2, 2), (3, 3)}

Course Name: DMGT School of Engineering, DSU 12

Symmetric Closure

➢ Let R be a relation on A. Then 𝑅−1 is the inverse of R then, the symmetric closure of R denoted as S(R) is

the relation R ∪ 𝑅 −1.

➢ In other words, symmetric (R) is obtained by adding to R all pairs (b, a) whenever (a, b) belongs to R.

➢ A symmetric closure s(R) is the smallest symmetric relation that contains R as a subset.

Course Name: DMGT School of Engineering, DSU 13

Symmetric Closure - Example

➢ The relation {(1, 1), (1, 2), (2, 2), (2, 3), (3, 1), (3, 2)} on {1, 2, 3} is not symmetric.

➢ How can we produce a symmetric relation that is as small as possible and contains R?

➢ To do this, we need only add (2, 1) and (1, 3), because these are the only pairs of the form (b, a)

with (a, b) ∈ R that are not in R.

➢ This new relation is symmetric and contains R. Furthermore, any symmetric relation that contains R

must contain this new relation, because a symmetric relation that contains R must contain (2, 1) and (1,

3).

➢ Consequently, this new relation is called the symmetric closure of R.

Course Name: DMGT School of Engineering, DSU 14

Symmetric Closure

➢ Let, N be a set of positive integers and R be a relation i.e. less than ( < ) on the set. Determine

symmetric closure of R.

s(R) = S(<) = < ∪ > = {(a, b) : a = b}

➢ General Formula

s(R) = R ∪ 𝑅−1 where 𝑅−1 {(b, a) : (a, b) ∈ R}

Course Name: DMGT School of Engineering, DSU 15

Problem1

Let, A = {1, 2, 3, 4} and R = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3)}. Find symmetric closure.

s(R) = R ∪ 𝑅−1

𝑅−1 = { 1, 1 , 3, 1 , 4, 2 , 1, 3 , 3, 3 , 3, 4 }

R ∪ 𝑅−1 = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3)} ∪ { 1, 1 , 3, 1 , 4, 2 , 1, 3 , 3, 3 , 3, 4 }

R ∪ 𝑅 −1 = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3), (4, 2), (3, 4)}

s(R) = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3), (4, 2), (3, 4)}

Course Name: DMGT School of Engineering, DSU 16

Problem2

Consider the following relation R on the set: A = {1,2,3,4} R = {(1,1) (1,3) (2,4) (3,1) (3,3) (4,3)}
Compute Reflexive(R) and Symmetric(R)

Reflexive(R) = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3), (2, 2), (4, 4)}

Symmetric(R) = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3), (4, 2), (3, 4)}

Course Name: DMGT School of Engineering, DSU 17

Problem3

Consider the following relation R on the set: A = {a, b, c}, R = {(a, a), (a, b), (b, c), (c, c)}
Compute: Reflexive(R) and Symmetric(R)

Reflexive(R) = {(a, a), (a, b), (b, c), (c, c), (b, b)}

Symmetric(R) = {(a, a), (a, b), (b, c), (c, c), (b, a), (c, b)}

Course Name: DMGT School of Engineering, DSU 18

Transitive Closure

➢ The transitive closure 𝑅+ is the smallest transitive relation that contains R as a subset.

➢ Let, relation R is defined on A and A contains n elements, then:

t(R) = 𝑅∗ = R ∪ 𝑅2 ∪ . . . . ∪ 𝑅𝑛

Where, 𝑅2 = R o R

𝑅3 = R o R o R and so on 𝑅𝑛 = 𝑅𝑛−1 o R

Where, 𝑅∗ is a transitive closure of a relation R.

Course Name: DMGT School of Engineering, DSU 19

Problem1

Consider the following relation R on the set: A = {1, 2, 3}, R = {(1, 2), (2, 3), (3, 3)}. Find transitive
closure.

|A| = 3
t(R) = R ∪ 𝑅2 ∪ 𝑅3
R = {(1, 2), (2, 3), (3, 3)}
𝑅2 = R o R = {(1, 3), (2, 3), (3, 3)}
𝑅3 = 𝑅2 o R = {(1, 3), (2, 3), (3, 3)}
t(R) = R ∪ 𝑅2 ∪ 𝑅3 = {(1, 2), (2, 3), (3, 3), (1, 3)}

Course Name: DMGT School of Engineering, DSU 20

Problem2

Consider the following relation R on the set: A = {1, 2, 3}, R = {(1, 2), (2, 3), (3, 1)}. Find transitive
closure.

|A| = 3
t(R) = R ∪ 𝑅2 ∪ 𝑅3
R = {(1, 2), (2, 3), (3, 1)}
𝑅2 = R o R = {(1, 3), (2, 1), (3, 2)}
𝑅3 = 𝑅2 o R = {(1, 1), (2, 2), (3, 3)}
t(R) = R ∪ 𝑅2 ∪ 𝑅3 = {(1, 2), (2, 3), (3, 1), (1, 3), (2, 1), (3, 2), (1, 1), (2, 2), (3, 3)}

Course Name: DMGT School of Engineering, DSU 21

Problem3

Consider the following relation R on the set: A = {a, b, c}, R = {(a, a), (a, b), (b, c), (c, c)} Find
transitive closure.

|A| = 3
t(R) = R ∪ 𝑅2 ∪ 𝑅3
R = = {(a, a), (a, b), (b, c), (c, c)}
𝑅2 = R o R = {(a, a), (a, b), (a, c), (b, c), (c, c)}
𝑅3 = 𝑅2 o R = {(a, a), (a, b), (a, c), (b, c), (c, c)}
t(R) = R ∪ 𝑅2 ∪ 𝑅3 = {(a, a), (a, b), (b, c), (c, c), (a, c)}

Course Name: DMGT School of Engineering, DSU 22

Digraph Representation of R

➢ To find the reflexive closure – add loops.

➢ To find the symmetric closure – add arcs on the opposite direction.

➢ To find the transitive closure – if there is a path from a to b add an arc from b to b.

Course Name: DMGT School of Engineering, DSU 23

Paths in Directed Graphs

➢ A path in a directed graph is obtained by traversing along edges.

➢ A path from a to b in the directed graph G is a sequence of edges (x0, x1), (x1, x2), (x2, x3), . . . , (𝑥𝑛−1 ,

𝑥𝑛 ) in G, where n is a nonnegative integer, and 𝑥0 = a and 𝑥𝑛 = b, that is, a sequence of edges where the

terminal vertex of an edge is the same as the initial vertex in the next edge in the path.

➢ This path is denoted by x0, x1, x2,..., 𝑥𝑛−1 , 𝑥𝑛 and has length n.

➢ A path in a directed graph can pass through a vertex more than once.

➢ Moreover, an edge in a directed graph can occur more than once in a path.

Course Name: DMGT School of Engineering, DSU 24

Problem1

• Identify the paths and length in the directed graph:

1. a, b, e, d

2. a, e, c, d, b

3. b, a, c, b, a, a, b

4. d,c

5. c, b, a
Figure 1: A Directed Graph
6. e, b, a, b, a, b, e

Course Name: DMGT School of Engineering, DSU 25

Problem1 - Solution

Paths Remarks Length

a, b, e, d (a, b), (b, e), (e, d) is an edge 3

a, e, c, d, b (c, d) is not an edge -

b, a, c, b, a, a, b (b, a), (a, c), (c, b), (b, a), (a, a), and (a, b) are all edges 6

d,c (d, c) is an edge 1

c, b, a (c, b) and (b, a) are edges 2

e, b, a, b, a, b, e (e, b), (b, a), (a, b), (b, a), (a, b), and (b, e) are edges 6

Course Name: DMGT School of Engineering, DSU 26

Solve - Problem2

Determine whether these sequences of vertices are paths in this directed graph.

a) a, b, c, e

b) b, e, c, b, e

c) a, a, b, e, d, e

d) b, c, e, d, a, a, b

e) b, c, c, b, e, d, e, d
Figure 2: A Directed Graph
f) a, a, b, b, c, c, b, e, d

Course Name: DMGT School of Engineering, DSU 27

Theorem

➢ Let 𝑀𝑅 be the zero–one matrix of the relation R on a set with n elements. Then the zero–one matrix of

the transitive closure 𝑅∗ is

Course Name: DMGT School of Engineering, DSU 28

Example

1. Find the zero–one matrix of the transitive closure of the relation R where

Solution:

Course Name: DMGT School of Engineering, DSU 29

Homework Problem

Consider the following relation R on the set:

A = {1, 2, 3, 4}
R = {(1, 3), (1, 1), (2, 4), (3, 1), (3, 3), (4, 3)}.
Compute:
i. reflexive (R)
ii. symmetric (R)
iii. transitive (R).

Course Name: DMGT School of Engineering, DSU 30

2. Equivalence Relations

➢ A relation on a set A is called an equivalence relation if it is:

i) Reflexive i.e., (a, a) ∈ R, ∀ a ∈ A

ii) Symmetric i.e., (a, b) ∈ R then (b, a) ∈ , ∀ a, b ∈ A

iii) Transitive i.e., (a, b) ∈ R and (b, c) ∈ R then, (a, c) ∈ R, ∀ a, b ∈ A

➢ The general idea behind an equivalence relation is that it is a classification of objects which are in some way “alike”.

The relation “=“ of equality on any set s is an equivalence relation.

➢ The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular

equivalence relation.

Course Name: DMGT School of Engineering, DSU 31

Problem1

The relation ⊆ of set inclusion is not an equivalence relation.

It is reflexive and transitive (A ⊆ B and B ⊆ C then, A ⊆ C) but not symmetric as A ⊆ B does not imply
B ⊆ A.

Example:

R is reflexive → 1 ⊆ 1

R is transitive → 2 ⊆ 3 3 ⊆ 4 then, 2 ⊆ 4

R is not symmetric → 2 ⊆ 3 but, 3 ⊄ 2

Hence, R is not equivalence relation

Course Name: DMGT School of Engineering, DSU 32
Problem2

Let, A = {1, 2, 3, 4}
i) R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 3), (3, 3), (4, 4)}
ii) R2 = {(1, 1), (1, 2), (2, 2), (3, 3), (4, 4)}
iii) R3 = ∅
iv) R4 = A × A

R1 → Reflexive, Symmetric, Transitive → Equivalence

R2 → Reflexive, Not Symmetric → Not equivalence
R3 → Not Equivalence
R4 → Equivalence

Course Name: DMGT School of Engineering, DSU 33

Problem3

If R is relation on the set of integers Z defined by R = {(x, y) : x ∈ z, y ∈ z, (x – y) is divisible by 6}

Then prove that R is an equivalence relation.

Let, R = {(12, 6), (6, 12), (6, 6), (9, 3), (20, 8), . . . . . }

i) Reflexive:
Let, x ∈ Z then, x –x = 0 and 0 is divisible by 6.
(x, x) ∈ R
Therefore, xRx ∀ n ∈ Z
Hence, R is reflexive

Course Name: DMGT School of Engineering, DSU 34

Problem3

Let, R = {(12, 6), (6, 12), (6, 6), (9, 3), (20, 8), . . . . . }

ii) Symmetric
Let, xRy → (x, y) ∈ R which is:
(x – y) is divisible by 6
(y – x) is divisible by 6
→ yRx i.e., (y, x) ∈ R
Hence, R is symmetric ∀ x, y ∈ Z

Course Name: DMGT School of Engineering, DSU 35

Problem3

Let, R = {(12, 6), (6, 12), (6, 6), (9, 3), (20, 8), . . . . . }

iii) Transitive
Let, (x, y) ∈ R and (y, z) ∈ R
(x – y) is divisible by 6 and (y – z) is divisible by 6
[(x – y) + (y – z)] is divisible by 6
[(x – y + y - z]
(x – z) is divisible by 6
xRz
(x, z) ∈ R
Hence, R is transitive ∀ x, y, z ∈ Z
R is an equivalence relation on set of integers.

Course Name: DMGT School of Engineering, DSU 36

Problem4

A = {x|x is a string of 0’s and 1’s}

Let, R be a relation on A such that,

R = {(a,b) | a and b ∈ A have equal number of 0’s in them.

Course Name: DMGT School of Engineering, DSU 37

Problem4

Let, a = 00111, 1011, . . . .

b = 10011, 1101, . . . .

The condition is a, b must have equal number of 0’s in them.

R is reflexive → Since if a has equal number of 0’s as b has.

R is symmetric → Since (a,b) have equal number of 0’s (b,a) also have equal number of 0’s

(a,b) ∈ R, (b,a) ∈ R

R is transitive → (a,b) ∈ R have equal number of 0’s

(b,c) ∈ R have equal number of 0’s

∴ (a,c) too have equal number of 0’s

(a,c) ∈ R

Course Name: DMGT School of Engineering, DSU 38

Problem5

A = {x|x is positive integer}

Let, R be a relation on A such that,

R = {(a, b) | a and b ∈ A and a-b = odd positive integer

Course Name: DMGT School of Engineering, DSU 39

Problem5

For Positive integers,

Even – Odd = Odd Even – Even = Even

Odd – Even = Odd Odd – Odd = Even

i. If (a,a) i.e., Even – Even = Even and Odd – Odd = Even is not odd positive integer (a,a) ∉ R

Hence, its not reflexive

ii. If (a,b) ∈ R then, (b,a) ∉ R

Example: (4,1) ∈ R but, (1,4) ∉ R [4-1 = 3 and 1-4 = -3]

Hence, its not symmetric

Course Name: DMGT School of Engineering, DSU 40

Problem5

iii. If (a,b) ∈ R and (b,c) ∈ R

a – b = +ve odd, b –c = +ve odd, Then, a – c = ?

Case 1: (odd – even) = odd ; (even – odd) = odd then, (odd – odd) = even

Hence, its not transitive

Course Name: DMGT School of Engineering, DSU 41

Problem6

Let A = {1,2,3,4,5}

Let R be relation on A such that R = {(x,y) | x+y=5}

A = {1,2,3,4,5} and R = {(x,y) | x+y=5}

R = {(1,4) (2,3) (4,1) (3,2)}

i. R is not reflexive (1,1) (2,2) (3,3) ∉ R

ii. R is symmetric

iii. R is transitive (1,4) ∈ R (4,1) ∈ R but, (1,1,) ∉ R

Hence, R is not equivalence relation.

Course Name: DMGT School of Engineering, DSU 42

Equivalence Classes

➢ Suppose A is a set and R is an equivalence relation on A, the equivalence class of x denoted by [x], is set of all

elements y in A such that y is related to x by R.

[x] = { y : y ∈ A, (x, y) ∈ R } OR [x] = { y ∈ A : yRx }

Course Name: DMGT School of Engineering, DSU 43

Example

➢ Let A = {1, 2, 3, 4} and R = {(1, 2), (2, 1), (1, 1), (2, 2), (3, 3), (4, 4)} is an equivalence relation. Determine equivalence

classes.

[1] = {2, 1} or {1, 2}

[2] = {1, 2}

[3] = {3}

[4] = {4}

Course Name: DMGT School of Engineering, DSU 44

Quotient Set

➢ The collection of all equivalence classes of elements of set A under an equivalence relation R is denoted by A/R.

➢ A/R = {[x] : x ∈ A}

➢ Ex: A/R = { [1], [2], [3], [4]} or {[1], [3], [4]}

A/R = {{1, 2}, {3}, {4}}

Course Name: DMGT School of Engineering, DSU 45

Partitions on a Set

➢ Let A be a non-empty set. A partition of set A is a subdivision of A into non overlapping, non empty subsets.

➢ A partition of a set A is a set of non-empty subsets of A denoted as {A1, A2, . . . . Ak} such that-

i) Each a in A belongs to one of the Ai

ii) A1 ∪ A2 ∪ . . . . ∪ Ak = A

iii) The sets of {Ai} are disjoint/ mutually disjoint

Ai ≠ Aj then, Ai ∩ Aj = ∅

➢ The subsets in a partition are called cells.

➢ In order to find partition of a given set, the equivalence classes are found first and from that partitions are obtained.

Course Name: DMGT School of Engineering, DSU 46

Example 1

➢ Consider the following collections of subsets of S = {1, 2, . . . . , 8, 9} and identify whether it is a partition or not.

i) [{1, 3, 5}, {2, 6}, {4, 8, 9}]

It is not a partition as none of the subsets contain 7

ii) [{1, 3, 5}, {2, 4, 6, 8}, {5, 7, 9}]

It is not a partition as 5 is present in 2 subsets i.e., {1, 3, 5} and {5, 7, 9} are not disjoint.

iii) [{1, 3, 5}, {2, 4, 6, 8}, {7, 9}]

It is a partition on set A.

Course Name: DMGT School of Engineering, DSU 47

Example 2

Let A = {1, 2, 3, 4, 5, 6, 7}. Verify whether following are partitions of A

a) [{1,3,5}, {2}, {4,7}]

b) [{1,5,7}, {3,4}, {2,5,6}]

a) Here, 6 ∈ A but, 6 does not belongs to any given partitions. Hence, these are not partitions of A.

b) Here, two partitions {1,5,7} {2,5,6} are not disjoint partitions of A. hence, these are not

partitions of A.

Course Name: DMGT School of Engineering, DSU 48

Problem 1

Consider the following relation R on S = {1, 2, 3}. R = {(1, 1), (1, 2), (2, 2), (2, 1), (3, 3)} and R is an

equivalence relation on S. Find equivalence classes, quotient set and representative of equivalence

class.

i) [1] = {1, 2} [2] = {1, 2} [3] = {3}

ii) Quotient set S/R

S/R = {{1, 2}, {3}}

iii) {1, 3} or {2, 3} is the set representatives of the equivalence classes.

Course Name: DMGT School of Engineering, DSU 49

Problem 2

Let R be the following relation on set A. A = {1, 2, 3, 4, 5, 6} and R be a relation R = {(1, 1), (1, 5),

(2, 2), (2, 3), (2, 6), (3, 2), (3, 3), (3, 6), (4, 4), (5, 1), (5, 5), (6, 2), (6, 3), (6, 6)}. Find the partition

of A induced by R.

i) [1] = {1, 5} [2] = {2, 3, 6} [3] = {2, 3, 6}

[4] = {4} [5] = {1, 5} [6] = {2, 3, 6}

ii) P = [{1,5}, {2, 3, 6}, {4}]

Course Name: DMGT School of Engineering, DSU 50

Problem 3

Consider the set of words w = {sheet, last, sky, wash, wind, sit}. Find w/R where R is the

equivalence relation on w defined by either:

a) “ has the same number of letters as “

b) “begins with the same letter “

Course Name: DMGT School of Engineering, DSU 51

Problem 3

a) “has the same number of letters as”

w = {sheet, last, sky, wash, wind, sit} = {5, 4, 3, 4, 4, 3}

R = {(sheet, sheet), (last, last), (last, wash), (last, wind), (sky, sky), (sky, sit), (wash, wash), (wash, last),

(wash, wind), (wind, wind), (wind, last), (wind, wash), (sit, sit), (sit, sky)}

[sheet] = {sheet} [last] = {last, wash, wind}

[sky] = {sky, sit} [wash] = {wash, wind, last}

[wind] = {last, wash, wind} [sit] = {sit, sky}

P = {{sheet}, {sky, sit}, {last, wash, wind}}

Course Name: DMGT School of Engineering, DSU 52
Problem 3

b) begins with the same letter

w = {sheet, last, sky, wash, wind, sit}

R = {(sheet, sheet), (sheet, sky), (sheet, sit), (last, last), (sky, sky), (sky, sheet), (sky, sit), (wash, wash), (wash,

wind), (wind, wind), (wind, wash), (sit, sit), (sit, sky), (sit, sheet)}

[sheet] = {sheet, sky, sit} [last] = {last}

[sky] = {sheet, sky, sit} [wash] = {wash, wind}

[wind] = {wash, wind} [sit] = {sit, sky}

P = {{sheet, sky, sit}, {last}, {wash, wind}}

Course Name: DMGT School of Engineering, DSU 53

Problem 4

Given S = {0, 1, 2, 3, 4, 5}

Find the partition induced by equivalence relation.

R = {(0, 0), (0, 4), (1, 1), (1, 3), (4, 5), (0, 5), (5, 4), (5, 0), (5, 5), (2, 2), (3, 1), (3, 3), (4, 0), (4, 4)}

i) [0] = {0, 4, 5} [1] = {1, 3} [2] = {2} [3] = {1, 3}

[4] = {0, 5, 4} [5] = {4, 0, 5}

ii) P = [{0, 4, 5}, {1, 3}, {2}]

Course Name: DMGT School of Engineering, DSU 54

Problem 5

For the equivalence relation R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 3), (3, 3), (4, 4)} defined on

set A = {1, 2, 3, 4}. Determine the partitions induced.

Course Name: DMGT School of Engineering, DSU 55

Problem 6

Find the partitions of A induced by R, given A = {1, 2, . . . , 11, 12}.

Given R = {(x, y) ∈ R iff (x-y) is a multiple of 5}

Course Name: DMGT School of Engineering, DSU 56

3. Partial Orderings

➢ A relation R on a set A is called a partial ordering or a partial order if R is reflexive, antisymmetric and transitive.

i.e., Reflexive → if ∀ a ∈ A, (a, a) ∈ R

Antisymmetric → if ∀ (a, b) ∈ R, (b, a) ∈ R the, a=b

Transitive → ∀ (a, b) ∈ R, (b, c) ∈ R then, (a, c) ∈ R

➢ A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R).

➢ Members of S are called elements of the poset.

➢ A poset is denoted by (S,R) or (S, ≼) where a ≼ b means a is related to b

Course Name: DMGT School of Engineering, DSU 57

 Definition 2:

The elements a and b of a poset (S, ≼) are called comparable if either a ≼ b or b ≼ a. When a and b are elements
of S such that neither a ≼ b nor b ≼ a, a and b are called incomparable.
The word “partial” in “partial ordering” indicates that not every pair of element in the set is comparable

EXAMPLE 1 In the poset (Z+, |), are the integers 3 and 9 comparable? Are 5 and 7 comparable?

Solution: The integers 3 and 9 are comparable, because 3 | 9. The integers 5 and 7 are incomparable, because 5
∤ 7 and 7 ∤ 5.

Definition 3:

If (S, ≼) is a poset and every two elements of S are comparable, S is called a totally ordered or linearly ordered
set, and ≼ is called a total order or a linear order. A totally ordered set is also called a chain.

EXAMPLE 2 The poset (Z, ≤) is totally ordered, because a ≤ b or b ≤ a whenever a and b are integers

Course Name: DMGT School of

58
Engineering, DSU
Course Name: DMGT School of
59
Engineering, DSU
Example 1

Show that the “greater than or equal” relation (≥) is a partial ordering on the set of integers

Because a ≥ a for every integer a, ≥ is reflexive. If a ≥ b and b ≥ a, then a = b. Hence, ≥ is antisymmetric.

Finally, ≥ is transitive because a ≥ b and b ≥ c imply that a ≥ c. It follows that ≥ is a partial ordering on the

set of integers and (Z, ≥) is a poset.

Course Name: DMGT School of Engineering, DSU 60

Example 2

Show that the inclusion relation ⊆ is a partial ordering on the power set of a set S.

Because A ⊆ A whenever A is a subset of S, ⊆ is reflexive. It is antisymmetric because A ⊆ B and B ⊆ A

imply that A = B. Finally, ⊆ is transitive, because A ⊆ B and B ⊆ C imply that A ⊆ C. Hence, ⊆ is a partial

ordering on P (S), and (P (S), ⊆) is a poset.

Course Name: DMGT School of Engineering, DSU 61

Example 3

A = {1, 2, 3}
R1 = { }
R2 = {(1, 1), (2, 2), (3, 3)}
R3 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
R4 = A × A

R1 → Not reflexive → Not partially Ordered Set/ Poset

R2 → Reflexive, Antisymmetric, Transitive → Partial Ordering Relation

R3 → Reflexive, Not Antisymmetric → Not Partial Ordering Relation

R4 → Reflexive, Not Antisymmetric → Not Partial Ordering Relation

Course Name: DMGT School of Engineering, DSU 62

Example 4

Given A = {1, 2, 3, 4}
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
Determine (A, R) is a Poset ?

R → Reflexive

R → Antisymmetric

R → Transitive

Hence, R is a partial order relation and (A, R) is a Poset.

Course Name: DMGT School of Engineering, DSU 63

Example 5

For the given di-graph. Find if (A, R) is a POSET ?

A = {1, 2, 3, 4}

R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 4), (3, 2), (3, 4), (3, 1)}

R is reflexive, antisymmetric, transitive.

Hence, (A, R) is a poset.

Course Name: DMGT School of Engineering, DSU 64

Example 6

From the given digraphs, write relations as set of ordered pairs, check for equivalence or partial ordering
relations.

A = {a, b, c, d}

R = {(a, b), (b, a), (a, c), (c, d), (b, d), (c, c)}

R is not reflexive. Hence, it is neither equivalence or partial

ordering relation.

Course Name: DMGT School of Engineering, DSU 65

Example 7

Is the relation {3, 4, 5, 6, <=} POSET ?

R = {(3, 3), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6), (5, 5), (5, 6), (6, 6)}

R → Reflexive, Antisymmetric, Transitive

R is a partial ordering relation and hence, given set is a POSET.

Course Name: DMGT School of Engineering, DSU 66

Example 8

Show that the relation “greater than or equal to” is a partially ordering relation on a set of integers.
Z = {. . . . . . , -3, -2, -1, 0, 1, 2, 3, . . . . }

i. Reflexive → For every integer ‘a’, a ∈ Z

aRa or (a, a) ∈ R i.e., a >= a → Hence, reflexive
ii. Antisymmetric → For any two integers (a, b) ∈ Z and (b, a) ∈ Z i.e., aRb and bRa
a>=b and b>=a → a = b → Hence, antisymmetric
iii. Transitive → Let, (a, b) ∈ R and (b, c) ∈ R
a>=b and b>=c → a>=c → Hence, Transitive

Course Name: DMGT School of Engineering, DSU 67

HASSE DIAGRAMS

A Hasse diagram is used to represent partial order relations with sufficient information

Procedure to draw the Hasse diagram:

Step 1: Start with a directed graph of the relation in which all arrows point upward.

Step 2: Remove self loops. Self loops are quite obvious and they must be present for all vertices because R is reflexive.
So we can remove them to simplify the diagram

Step 3: Remove all transitive edges

a. Check if (a,b) and (b,c) are in partial ordering.

b. If yes, then remove the edge between vertices a and c

c. If (c,d) also belongs to the partial order then remove the edge(a,d) and so on.

Step 4: Remove all the arrows of the directed graph. If we assume that all edges are pointing upwards then there is no
need to show the directions in the graph. We can safely remove the arrows in the diagram.

Course Name: DMGT School of Engineering, DSU 68

Example

Let’s say we have a set S={1,2,3,9,18} and Relation R is defined on set S. R={(a,b) | a divides b)}
1. Reflexivity: a|a
2. Antisymmetry: a|b and b|a → a=b
3. Transitivity: a|b and b|c → a|c
Therefore , R is a partial order and (S,R) is a poset.
Lets try to represent relation R={(a,b) | a divides b)} using a directed graph S ={1,2,3,9,18}

18

9
2
3
1

Course Name: DMGT School of Engineering, DSU 69

 Hasse Diagram for the poset ({1,2,3,4,6,8,12})

Course Name: DMGT School of Engineering, DSU 70

Maximal Element and Minimal Element

➢ An element of a poset is called maximal if it is not less than any element of the poset.
➢ a is maximal in the poset (S, ≼ ) if there is no b ⋲ S such that a ⊰ b.
➢ An element of a poset is called minimal if it is not greater than any element of the poset.
➢ a is minimal if there is no element b ⋲ S such that b ⊰ a
➢ Maximal and minimal elements are easy to spot using a Hasse diagram.

Course Name: DMGT School of Engineering, DSU 71

Problem

Which elements of the poset ({2, 4, 5, 10, 12, 20, 25}, |) are maximal, and which are minimal?

Solution: The Hasse diagram for this poset shows that the maximal elements are 12, 20, and 25, and the
minimal elements are 2 and 5.

Course Name: DMGT School of Engineering, DSU 72

Greatest Element and Least Element

➢ a is the greatest element of the poset (S, ≼) if b ≼ a for all b ∈ S. The greatest element is unique when it

exists.

➢ a is the least element of (S, ≼ )if a ≼ b for all b ∈ S. The least element is unique when it exists

Course Name: DMGT School of Engineering, DSU 73

 Problem

➢ Determine whether the posets represented in each of the Hasse diagram below have a greatest element and a

least element.

➢ The least element of the poset with Hasse diagram (a) is a. This poset has no greatest element.
➢ The poset with Hasse diagram (b) has neither a least nor a greatest element.
➢ The poset with Hasse diagram (c) has no least element. Its greatest element is d.
➢ The poset with Hasse diagram (d) has least element a and greatest element d.

Course Name: DMGT School of Engineering, DSU 74

Least Upper Bound, Greatest Lower Bound

➢ The element x is the least upper bound of A if a ≼ x whenever a ∈ A, and x ≼ z whenever z is an upper
bound of A.

➢ The element y is called the greatest lower bound of A if y is a lower bound of A and z ≼ y whenever z is a
lower bound of A.

➢ The greatest lower bound and least upper bound of A is unique if it exists.

Course Name: DMGT School of Engineering, DSU 75

 Problem
Find the greatest lower bound and the least upper bound of {b, d, g}, if they exist, in the poset shown in the
above figure.

The upper bounds of {b, d, g} are g and h. Because g ≺ h, g is the least upper bound. The lower bounds of {b, d, g} are
a and b. Because a ≺ b, b is the greatest lower bound.

Course Name: DMGT School of Engineering, DSU 76

 Topological Sorting

A total ordering ≼ is said to be compatible with the partial ordering R if a ≼ b whenever aRb. Constructing a

compatible total ordering from a partial ordering is called topological sorting.

Course Name: DMGT School of Engineering, DSU 77

 Problem1

Find a compatible total ordering for the poset ({1, 2, 4, 5, 12, 20}, |).

Course Name: DMGT School of Engineering, DSU 78

 Problem2
A development project at a computer company requires the completion of seven tasks. Some of these tasks can be

started only after other tasks are finished. A partial ordering on tasks is set up by considering task X ≺ task Y if task

Y cannot be started until task X has been completed. The Hasse diagram for the seven tasks, with respect to this

partial ordering, is shown in below. Find an order in which these tasks can be carried out to complete the project.

Course Name: DMGT School of Engineering, DSU 79

4. Functions

➢ Let, y be a variable such that –

y = 𝑥2 + 1

Where y is a dependent variable and x is an independent variable.

➢ We say that y is a function of x → y = f(x) = 𝑥 2 + 1 A f B

If x = 1 → y = 2 2
1 4
x=2→y=5
2 5

x = 3 → y = 10 8
3
10

The two sets are related through the function.

Course Name: DMGT School of Engineering, DSU 80
Definition

• Given any two non empty sets A, B, a function (“transformation” or “mapping”) f from A to B (f:

A→B) is an assignment of exactly one element f(x)B to each element xA.

• Functions can be represented graphically in several ways:

• • y
• • •
a• b
•
•
• •
A • x
B
Venn Diagram Graph Plot

Course Name: DMGT School of Engineering, DSU 81

Terminologies

If f:A→B, and f(a)=b (where aA & bB), then:

➢ A is the domain of f.

➢ B is the codomain of f.

➢ b is the image of a under f.

➢ a is a pre-image of b under f.

➢ In general, b may have more than one pre-image.

➢ The range (set of all possible output values) RB of f is {b | a ∈ A ( b = f(a) ) }.

Course Name: DMGT School of Engineering, DSU 82

Identify whether it is a function or not ?

1 A

2 B

3 C

A
1
Valid B
2
C
3
D

Valid

Course Name: DMGT School of Engineering, DSU 83

Identify whether it is a function or not ?

1
A
2
B
3

A
1
Invalid B
2
C
3
D

Invalid

Course Name: DMGT School of Engineering, DSU 84

Identify whether it is a function or not ?

1
A
2
B
3
C
4
A
1
Valid B
2
C
3
D

Invalid
Course Name: DMGT School of Engineering, DSU 85
Example 1

Let A = {1, 2, 3} and B = {a, b, c, d}. With the help of Venn diagram given below identify image, pre-
image and range. A B

a
1
b
Solution 2 c
3 d
‘a’ is the image of 1 and ‘b’ is the image of 2 and 3
1 is the pre-image of a, 2 and 3 is the pre-image of b
Ran(f) = {a, b}
Domain of f : {1, 2, 3}
Co-domain of f: {a, b, c, d}
Course Name: DMGT School of Engineering, DSU 86
Example 2

Let R be the relation with ordered pairs (Abdul, 22), (Brenda, 24), (Carla, 21), (Desire, 22), (Eddie, 24),
and (Felicia, 22). Here each pair consists of a graduate student and this student’s age. Specify a function
determined by this relation.

Solution

This relation defines the function f, where

f(Abdul) = 22, f(Brenda) = 24, f(Carla) = 21, f(Desire) = 22, f(Eddie) = 24, f(Felicia) = 22
Domain: Set{Abdul, Brenda, Carla, Desire, Felicia}
Codomain: Set of positive integers {age is +ve}
Range: Set {21, 22, 24}
Course Name: DMGT School of Engineering, DSU 87
Example 3

Consider the function f(x) = 𝑥 3 i.e., f assigns to each real number its cube. Then find the image of (2).

Solution

f (x) = 𝑥 3

f (2) = 23 = 8

So, the image of 2 is 8

Course Name: DMGT School of Engineering, DSU 88

Example 4

Let A = {a, b, c d} and B = {r, s, t, u} and function f is defined as shown pictorially. A B

Write the image of each element of A and the range of function. r

a
b s

c t
Solution d u

Image:

f (a) = s f (b) = u f (c) = r f (d) = s

Range:

f (A) = {r, s, u}

Course Name: DMGT School of Engineering, DSU 89

Example 5

Let A = {0, ± 1, ± 2, ± 3}. Consider f: A → R where R is the set of all real numbers defined by

f(x) = 𝑥 3 - 2𝑥 2 + 3x + 1 for x € A. Find the range of f.

Solution

f(x) = 𝑥 3 - 2𝑥 2 + 3x + 1

f(0) = 1 f(1) = 3 f(2) = 7 f(3) = 19 f(-1) = -5 f(-2) = -21

f(-3) = -53

Range of f = {-53, -21, -5, 1, 2, 7, 19}

Course Name: DMGT School of Engineering, DSU 90

Function Addition/ Multiplication

➢ A function is called real-valued if its codomain is the set of real numbers, and it is called integer-
valued if its codomain is the set of integers.

➢ Two real-valued functions or two integer-valued functions with the same domain can be added, as well
as multiplied.

➢ Let f and g be functions from A to R. Then f + g and f x g are also functions from A to R defined for all
x ∈ A by:

(f + g): A → R, where (f + g)(x) = f(x) + g(x)

(f × g ): A → R, (f . g)(x) = f(x)g(x)

Course Name: DMGT School of Engineering, DSU 91

Example

Let f1 and f2 be functions from R to R such that f(x) = 𝑥 2 and g(x) = x − 𝑥 2 . What are the functions f + g
and f x g?

(f + g)(x) = f(x) + g(x) = 𝑥 2 + (x − 𝑥 2 ) = x

(f × g)(x) = 𝑥 2 (x − 𝑥 2 ) = 𝑥 3 - 𝑥 4

Course Name: DMGT School of Engineering, DSU 92

Types of Functions

1. One-to-One Function (INJUCTION)

2. Onto Function (SURJECTION)

3. One-to-One Correspondence (BIJECTIVE)

4. Identity Function

5. Inverse Function

Course Name: DMGT School of Engineering, DSU 93

1. One-to-One Function

➢ A function f is said to be one-to-one, or an injunction, if and only if f (a) = f (b) implies that a = b for
all a and b in the domain of f.

➢ A function is said to be injective if it is one-to-one.

➢ A function is one-to-one (1-1), or injective, or an injection, iff every element of its range has only one
pre-image.

Course Name: DMGT School of Engineering, DSU 94

Example 1

➢ Determine whether the function f from {a, b, c, d} to {1, 2, 3, 4, 5} with f (a) = 4, f (b) = 5, f (c) = 1,
and f (d) = 3 is one-to-one

Solution

The function f is one-to-one because f takes on different values at the four elements of its domain.

Course Name: DMGT School of Engineering, DSU 95

Example 2

Let A = {1, 2, 3} and B = {a, b, c, d}. In each case state whether the given function f (if defined) is
injective or not.

i) f = {(1, a), (2, d), (3, b)}

ii) f = {(1, a), (2, a), (3, d)}

iii) f = {(1, a), (1, b), (2, d), (3, c)}

iv) f = {(1, a), (2, b)}

Course Name: DMGT School of Engineering, DSU 96

NOTE: Sufficient Conditions for one to one functions

• A function f is increasing if ∀x∀y(x < y → f (x) ≤ f (y)),

• A function f is strictly increasing if ∀x∀y(x < y → f (x) < f (y)),

• A function f is decreasing if ∀x∀y(x < y → f (x) ≥ f (y)),

• A function f is strictly decreasing if ∀x∀y(x < y → f (x) > f (y))

• A function that is either strictly increasing or strictly decreasing must be one-to-one.

• However, a function that is increasing, but not strictly increasing, or decreasing, but
not strictly decreasing, is not one-to-one.

Course Name: DMGT School of Engineering, DSU 97

Examples

Example 1: Consider the function f(x) = x (the identity function). For any 𝑥1 and 𝑥2

where 𝑥1 <𝑥2 , f(𝑥1 ) = x1 and f(𝑥2 ) = 𝑥2 , which satisfies the condition for a strictly

increasing function and is one-to-one.

f(x) = x → 𝑥1 <𝑥2

f(𝑥1 ) = x1

f(𝑥2 ) = 𝑥2

Course Name: DMGT School of Engineering, DSU 98

Examples

Example 2: Consider the function f(x) = −x. For any 𝑥1 and 𝑥2 where 𝑥1 <𝑥2 , f(𝑥1 ) =

−𝑥1 and f(𝑥2 ) = −𝑥2 , which satisfies the condition for a strictly decreasing function and

is one-to-one.

f(x) = −x → 𝑥1 <𝑥2

f(𝑥1 ) = −𝑥1

f(𝑥2 ) = −𝑥2

Course Name: DMGT School of Engineering, DSU 99

Examples

Example 3: Consider the function f(x)=𝑥2 . For 𝑥1 = −1 and 𝑥2 = 1, we have 𝑥1 <𝑥2 , but f(𝑥1 ) = 1

and f(𝑥2 ) = 1, which are equal. So, this function is increasing but not strictly increasing and is

not one-to-one.

f(x)=𝑥2 → 𝑥1 <𝑥2

𝑥1 = −1 and 𝑥2 = 1

f(𝑥1 ) = 1

f(𝑥2 ) = 1
Course Name: DMGT School of Engineering, DSU 100
Examples

Example 4: Consider the function f(x) = −𝑥2 . For 𝑥1 = −1 and 𝑥2 =1, we have 𝑥1 <𝑥2 , but f(𝑥1 ) =

−1 and f(𝑥2 ) = −1, which are equal. So, this function is decreasing but not strictly decreasing

and is not one-to-one.

f(x) = −𝑥2 → 𝑥1 <𝑥2

𝑥1 = −1 and 𝑥2 =1

f(𝑥1 ) = −1

f(𝑥2 ) = −1
Course Name: DMGT School of Engineering, DSU 101
NOTE: Constant Function

➢ A function f: A → B is said to be constant if and only if f (a) = c for every a belongs to A, where c is a
fixed element of B

Course Name: DMGT School of Engineering, DSU 102

2. Onto Function

➢ A function f from A to B is called onto, or a surjection, if and only if for every element b ∈ B there is
an element a ∈ A with f (a) = b. A function f is called surjective if it is onto.

➢ A function f:A→B is onto or surjective or a surjection iff its range is equal to its codomain (bB,
aA: f(a)=b).

Course Name: DMGT School of Engineering, DSU 103

Example 1

Let f be the function from {a, b, c, d} to {1, 2, 3} defined by f (a) = 3, f (b) = 2, f (c) = 1, and f (d) = 3. Is
f an onto function?

Solution

➢ Because all three elements of the codomain are images of elements in the domain, we see that f is onto.

➢ Note that if the codomain were {1, 2, 3, 4}, then f would not be onto.

Course Name: DMGT School of Engineering, DSU 104

Example 2

Let A = {1, 2, 3, 4} and B = {a, b, c, d} and f = {(1, a), (2, b), (3, c), (4, d)}. State whether the given
function f (if defined) is onto or not.

Solution
A B

It is an onto function. 1 a

2 b

3 c

4 d

Course Name: DMGT School of Engineering, DSU 105

Example 3

Let A = {1, 2, 3} and B = {a, b, c, d} and f = {(1, a), (2, b), (3, c)}. State whether the given function f (if
defined) is onto or not.

Solution
A B

It is not an onto function. a

1
b
2
c
3
d

Course Name: DMGT School of Engineering, DSU 106

3. Bijective Function

➢ The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto.

Course Name: DMGT School of Engineering, DSU 107

Example 1

Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f (a) = 4, f (b) = 2, f (c) = 1, and f (d) = 3. Is f a
bijection?

Solution
A B
➢ The function f is one-to-one and onto. It is one-to-one because
a 1
no two values in the domain are assigned the same function
b 2
value. It is onto because all four elements of the codomain are c 3

d 4
images of elements in the domain. Hence, f is a bijection

Course Name: DMGT School of Engineering, DSU 108

Example 2

Consider the functions 𝑓1 : A → B, 𝑓2 : B → C, 𝑓3 : C → D, 𝑓4 : D → E defined by the following

diagrams. Check for bijection.

Course Name: DMGT School of Engineering, DSU 109

4. Identity Function

➢ The function f is called the identity function if each element of set A has an image on itself i.e. f (a) = a
∀ a ∈ A.

➢ For any domain A, the identity function I:A→A (variously written, IA, 1, 1A) is the unique function such
that aA: I(a)=a.

➢ Note that the identity function is both one-to-one and onto (bijective).

➢ Consider, A = {1, 2, 3, 4, 5} and I: A → A such that I= {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}.

Course Name: DMGT School of Engineering, DSU 110

5. Inverse Function

➢ Let f be a one-to-one correspondence from the set A to the set B. The inverse function of f is the

function that assigns to an element b belonging to B the unique element a in A such that f (a) = b. The

inverse function of f is denoted by f −1. Hence, f −1(b) = a when f (a) = b.

➢ A one-to-one correspondence is called invertible because we can define an inverse of this function. A

function is not invertible if it is not a one-to-one correspondence, because the inverse of such a function

does not exist.

Course Name: DMGT School of Engineering, DSU 111

Example 1

➢ Let f be the function from {a, b, c} to {1, 2, 3} such that f (a) = 2, f (b) = 3, and f (c) = 1. Is f invertible, and if it is, what

is its inverse?

Solution

The function f is invertible because it is a one-to-one correspondence. The inverse function f −1 reverses
the correspondence given by f , so f −1 (1) = c, f −1(2) = a, and f −1 (3) = b.

Course Name: DMGT School of Engineering, DSU 112

Example 2
➢ Let f : Z → Z be such that f (x) = x + 1. Is f invertible, and if it is, what is its inverse?

Solution

➢ The function f has an inverse because it is a one-to-one correspondence. suppose that y is the image of x, so
that

y = x+1

Therefore, x=y-1

Consequently f −1(y)= y-1

Course Name: DMGT School of Engineering, DSU 113

Example 3
➢ Let f be the function from R to R with f (x) =𝑥 2 . Is f invertible?

Solution

Because f (−2) = f (2) = 4, f is not one-to-one. If an inverse function were defined, it would have to assign
two elements to 4. Hence, f is not invertible.

Course Name: DMGT School of Engineering, DSU 114

Determine if each function is one-to-one

i) To each person on the earth, assign the number which correspond to his age.

ii) To each country in the world, assign the latitude and longitude of its capital.

iii) To each book written by one author assign the author.

Course Name: DMGT School of Engineering, DSU 115

Problem 1
Find the nature of the following functions defined on A = {1, 2, 3}
i) f = {(1, 1), (2, 2), (3, 3)}
ii) g = {(1, 2), (2, 2), (3, 2)}
iii) h = {(1, 2), (2, 2), (3, 1)}
iv) p = {(1, 2), (2, 3), (3, 1)}

Solution
i) Identity

ii) Constant

iii) Neither

iv) One-to-one correspondence.

Course Name: DMGT School of Engineering, DSU 116

Problem 2

Let A = {1, 2, 3} and B = {1, 2, 3, 4, 5}. Find whether the following functions from A to B are one-to-one and onto.

i) f = {(1, 1), (2, 3), (3, 4)}

ii) g = {(1, 1), (2, 3), (3, 3)}

Solution

i) One-to-one

ii) Neither

Course Name: DMGT School of Engineering, DSU 117

Problem 3

Let A = {a1, a2, a3}, B = {b1, b2, b3}, C = {c1, c2}, d = {d1, d2, d3, d4}. Let 𝑓1 : A → B, 𝑓2 : A → D, 𝑓3 : B → C and 𝑓4 :

D → B be functions defined as follows:

i) f1 = {(a1, b2), (a2, b3), (a3, b1)}

ii) f2 = {(a1, d2), (a2, d1), (a3, d4)}

iii) f3 = {(b1, c2), (b2, c2), (b3, c1)}

Solution
iv) f4 = {(d1, b1), (d2, b2), (d3, b1), (d4, b2)}
i) Both

ii) One-to-One

iii) Onto

iv) Neither

Course Name: DMGT School of Engineering, DSU 118

Equal Function

➢ Two functions are equal when they have the same domain, have the same codomain, and map
each element of their common domain to the same element in their common codomain.

▪ For every x in R, let's check if f(x)=g(x):

▪ f(x)=2x g(x)=x+x

▪ If we substitute x with any real number, we can see that f(x)=g(x).

For example:

▪ f(3)=2×3=6

▪ g(3)=3+3=6

▪ Since f(x)=g(x) for all x in R, we can conclude that f and g are equal functions.
Course Name: DMGT School of Engineering, DSU 119
Composition of Functions

Let g be a function from the set A to the set B and let f be a function from the set B to the set C. The
composition of the functions f and g, denoted for all a ∈ A by f ◦ g, is defined by:

(f ◦ g)(a) = f (g(a))

Course Name: DMGT School of Engineering, DSU 120

Example 1

Let g be the function from the set {a, b, c} to itself such that g(a) = b, g(b) = c, and g(c) = a. Let f be the
function from the set {a, b, c} to the set {1, 2, 3} such that f (a) = 3, f (b) = 2, and f (c) = 1. What is the
composition of f and g, and what is the composition of g and f ?

Solution

The composition f ◦ g is defined by

(f ◦ g) (a) = f (g(a)) = f (b) = 2
(f ◦ g) (b) = f (g(b)) = f (c) = 1
(f ◦ g) (c) = f (g(c)) = f (a) = 3

Course Name: DMGT School of Engineering, DSU 121

Example 2

Let the function f: A → B and g: B → C be denoted by the following arrow diagram. Find the
composition of g ◦ f: A→ C

Solution

i) (g ◦ f) a = g(f(a)) = g(y) = t

ii) (g ◦ f) b = g(f(b)) = g(x) = s

iii) (g ◦ f) c = g(f(c)) = g(y) = t

Hence, g ◦ f = {s, t}
Course Name: DMGT School of Engineering, DSU 122
Example 3

Let the functions f and g be defined by f(x) = 2x + 1 and g(x) = 𝑥 2 - 2

Find the formula defining the composition function g ◦ f

Solution

(g ◦ f) = g(f(x)) = g(2x + 1)

g(2x + 1) = (2𝑥 + 1)2 - 2

= 4𝑥 2 + 1 + 4x – 2

g(2x + 1) = 4𝑥 2 + 4x – 1

Hence, (g ◦ f) = 4𝑥 2 + 4x – 1

Course Name: DMGT School of Engineering, DSU 123

Example 4

Let f: R → R and f(x) = 𝑥 2

g: R → R and g(x) = 2x + 1

Find f ◦ g and g ◦ f

Solution

(f ◦ g) = 4𝑥 2 + 4x + 1

(g ◦ f) = 2𝑥 2 + 1

Course Name: DMGT School of Engineering, DSU 124

Example 5
If f = {(1, 2), (3, 5), (4, 1)} and g = {(2, 3), (5, 1), (1, 3)}. Write (f ◦ g) and (g ◦ f).

Solution
Domain of f : {1, 3, 4} Range of f : {2, 5, 1}

Domain of g : {2, 5, 1} Range of g : {3, 1}

f(1) = 2 f(3) = 5 f(4) = 1

g(2) = 3 g(5) = 1 g(1) = 3

f ◦ g (2) = f(g(2)) = f(3) = 5 g ◦ f (1) = g(f(1)) = g(2) = 3

f ◦ g (5) = f(g(5)) = f(1) = 2 g ◦ f (3) = g(f(3)) = g(5) = 1

f ◦ g (1) = f(g(1)) = f(3) = 5 g ◦ f (4) = g(f(4)) = g(1) = 3

f ◦ g = { (2, 5), (5, 2), (1, 5)} g ◦ f = {(1, 3), (3, 1), (4, 3)}
Course Name: DMGT School of Engineering, DSU 125
Example 6
Let, f(n) = 𝑛2 g(n) = n + 1 h(n) = n – 1 Find h o f o g

Solution

h o f o g = h o f o (g(n))

= h o f o (n + 1)

= h o f (n + 1)

= h o (𝑛 + 1)2

= h (𝑛 + 1)2

= (𝑛 + 1)2 - 1

= 𝑛2 + 1 + 2n – 1

h o f o g = 𝑛2 + 2n

Course Name: DMGT School of Engineering, DSU 126

Theorem P.T., 𝑓 −1 −1 = f
The inverse function reverses the correspondence of the original function,
f −1(b) = a when f (a) = b,
and
f (a) = b when f −1(b) = a.

(f −1 ◦ f )(a) = f −1(f (a)) = f −1(b) = a,

and
(f ◦ f −1)(b) = f (f −1(b)) = f (a) = b.
Consequently
f −1 ◦ f = 𝐼𝐴
and
f ◦ f −1 = 𝐼𝐵 ,

where 𝐼𝐴 and 𝐼𝐵 are the identity functions on the sets A and B, respectively. That is,
𝑓 −1 −1
=f

Course Name: DMGT School of Engineering, DSU 127

The Graphs of Function
➢ We can represent a function f:A→B as a set of ordered pairs {(a,f(a)) | aA}.

➢ Note that a, there is only one pair (a, f(a)).

➢ For functions over numbers, we can represent an ordered pair (x,y) as a point on a plane. A function is
then drawn as a curve (set of points) with only one y for each x.

The Graph of f(n)=2n+1 from Z to Z

Course Name: DMGT School of Engineering, DSU 128

Partial Functions

➢ A partial function f from a set A to a set B is an assignment to each element a in a subset of A, called

the domain of definition of f , of a unique element b in B.

➢ f is undefined for elements in A that are not in the domain of definition of f .

➢ When the domain of definition of f equals A, we say that f is a total function.

EXAMPLE

The function f : Z → R where f (n) = √n is a partial function from Z to R where the domain of definition

is the set of nonnegative integers. Note that f is undefined for negative integers.

Course Name: DMGT School of Engineering, DSU 129

Floor and Ceil functions

➢ The floor function assigns to the real number x the largest integer that is less than or equal to x. The

value of the floor function at x is denoted by 𝑥

➢ The ceiling function assigns to the real number x the smallest integer that is greater than or equal to x.

The value of the ceiling function at x is denoted by ⌈𝑥⌉

EXAMPLES
0.5 0 0.5 1
1.5 1 1.5 2
2.7 2 2.7 3
0.2 0 0.2 1
2.5 2 2.5 3

Course Name: DMGT School of Engineering, DSU 130

Graph Floor and Ceil functions

Graph of Floor Function Graph of Ceil Function

Course Name: DMGT School of Engineering, DSU 131

5. The Growth of Functions
➢ The relative performance of an algorithms depends on input data size N.
➢ The order of growth is normally determined for larger values of n for the following reasons:
1. The behaviour of an algorithm changes as the value of n increases
2. In real time applications large values of n is encountered.
➢ If there are multiple input parameters, we will try to reduce them to a single parameter, expressing
some parameters in terms of the selected parameter.
➢ Between two algorithms it is considered that the one having a smaller order of growth is more efficient

➢ However, this is true only for large enough input sizes

Course Name: DMGT School of Engineering, DSU 132

Dominant Term
➢ In the running time expression, when n becomes large a term will become significantly larger
than the other ones : this is the so-called dominant term

➢ The growth rate is not affected by

1. constant factors or

2. lower-order terms

Course Name: DMGT School of Engineering, DSU 133

Rate of growth of function

Course Name: DMGT School of Engineering, DSU 134

Asymptotic Notations
➢ The order of growth can be expressed using two methods:
1. Order of growth using asymptotic notations.
2. Order of growth using limits.
• Asymptotic Behavior of a Function
➢ Asymptotic notations are the notations using which two algorithms can be compared
with respect to efficiency based on the order of growth of an algorithm’s basic
operation.
➢ The different types of asymptotic notations are:
1. O (Big Oh)
2. Ω (Big Omega)
3. Θ (Big Theta)

Course Name: DMGT School of Engineering, DSU 135

Big-Oh Notation (O)

Let f(n) be the efficiency of an algorithm, the function f(n) is said to be

in O(g(n))
f(n) = or ∈ O(g(n)),
if
 positive constants c and n0, such that n  n0,
We have 0  f(n)  cg(n)

➢ g(n) is an asymptotic upper bound for f(n).

Course Name: DMGT School of Engineering, DSU 136

Big-Omega Notation (Ω)

Let f(n) be the efficiency of an algorithm, the function f(n) is

said to be in Ω(g(n))
f(n) = or ∈ Ω(g(n)),
if
 positive constants c and n0, such that n  n0,
We have 0  cg(n)  f(n)

➢ g(n) is an asymptotic lower bound for f(n).

Course Name: DMGT School of Engineering, DSU 137

Big-Theta Notation (Θ)

Let f(n) be the efficiency of an algorithm, the function

f(n) is said to be in Θ(g(n))
f(n) = or ∈ Θ(g(n)),
if
 positive constants c1, c2 and n0, such that n  n0,
We have 0  c1g(n)  f(n)  c2g(n)

➢ This notation represents both upper and lower bound.

Course Name: DMGT School of Engineering, DSU 138