CMP 242 - Discrete Structures

Relations and Functions

M. O. Odim (Ph.D.)
Department of Computer Science
Redeemer’s University

1
 Relation in Math
The concept of relation in math refers to an association of two objects or two variables based
some property possessed by them.

For Example:
1. Rachel is the daughter of Noah.
This statement shows the relation between two persons.
The relation (R) being ‘is daughter of’.

2. 5 is less than 9.
This statement shows the relation between two numbers.
The relation (R) being ‘is less than’.
If A and B are two non-empty sets, then the relation R from A to B is a subset of A x B, i.e., R
⊆ A x B.
If (a, b) ∈ R, then we write a R b and is read as 'a' related to 'b'.

2
 Definition
Given sets A and B, a relation between A and B is a subset of A × B.
By this definition, a relation R is simply a specification of which
pairs are related by R, that is, which pairs the relation R is true
for.

For the relation > on the set {1, 2, 3},

> = {(2, 1), (3, 1), (3, 2)}.

Common mathematical relations that will concern us include <, >, , , =,

≠, !,≡, ⊆, ⊂ , etc.
3
 Representation of Relation in Math:
The relation in math from set A to set B is
expressed in different forms.

(i) Roster form

(ii) Set builder form

(iii) Arrow diagram

4
 Roster form:
In this, the relation (R) from set A to B is represented as a set of ordered
pairs.
● In each ordered pair 1st component is from A; 2nd component is from B.
● Keep in mind the relation we are dealing with. (>, < etc.)

For Example:

1. If A = {p, q, r} B = {3, 4, 5}

then R = {(p, 3), (q, 4), (r, 5)}

Hence, R ⊆ A × B 5
2. Given A = {3, 4, 7, 10} B = {5, 2, 8, 1} then the relation R from A to B is
defined as ‘is less than’ and can be represented in the roster form as R =
{(3, 5) (3, 8) (4, 5), (4, 8), (7, 8)}

• Here, 1ˢᵗ component < 2ⁿᵈ component.

• In roster form, the relation is represented by the set of all ordered
pairs belonging to R.
•
If A = {-1, 1, 2} and B = {1, 4, 9, 10}
if a R b means a² = b
then, R (in roster form) = {(-1, 1), (1, 1), (2, 4)

6
 Set builder form:

In this form, the relation R from set A to set B is represented as

R = {(a, b): a ∈ A, b ∈ B, a...b},
the blank space is replaced by the rule which associates a and b.

For Example:
Let A = {2, 4, 5, 6, 8} and B = {4, 6, 8, 9}
Let R = {(2, 4), (4, 6), (6, 8), (8, 10) then R in the set builder form, it
can be written as
R = {a, b} : a ∈ A, b ∈ B, a is 2 less than b}

7
 Arrow diagram:
Draw two circle (oval shape) representing Set A and Set
B.
Write their elements in the corresponding sets, i.e.,
elements of Set A in circle A and elements of Set B in
circle B.
● Draw arrows from A to B which satisfy the relation and
indicate the ordered pairs.
For Example:
1. If A = {3, 4, 5} B = {2, 4, 6, 9, 15, 16, 25}, then
relation R from A to B is defined as ‘is a positive
square root of’ and can be represented by the arrow
diagram as shown (upper right).
Here R = {(3, 9); (4, 16); (5, 25)}
2. If A = {2, 3, 4, 5} and B = {1, 3, 5} and R be the relation
'is less than' from A to B, as shown (lower right)
then R = {(2, 3), (2, 5), (3, 5), (4, 5)} 8
 Domain and Range of a Relation
Suppose R be a relation from set A to set B, then
• The set of all first components of the ordered pairs belonging to R is called the
domain of R.
Thus, Dom(R) = {a ∈ A: (a, b) ∈ R for some b ∈ B}.

• The set of all second components of the ordered pairs belonging to R is

called the range of R.

Thus, range of R = {b ∈ B: (a, b) ∈R for some a ∈ A}.

Therefore, Domain (R) = {a : (a, b) ∈ R} and Range (R) = {b : (a, b) ∈ R}

Note:
The domain of a relation from A to B is a subset of A.
The range of a relation from A to B is a subset of B. 9
 For Example:
If A = {2, 4, 6, 8) B = {5, 7, 1, 9}.

Let R be the relation ‘is less than’ from A to B. Find Domain (R) and Range (R).

Solution:
Under this relation (R), we have
R = {(4, 5); (4, 7); (4, 9); (6, 7); (6, 9), (8, 9) (2, 5) (2, 7) (2, 9)}

Therefore, Domain (R) = {2, 4, 6, 8} and Range (R) = {1, 5, 7, 9}

10
 Solved examples on domain and range of a
relation:

1. In the given ordered pair (4, 6); (8, 4); (4, 4); (9, 11); (6, 3); (3, 0); (2,
3) find the following relations. Also, find the domain and range.
(a) Is two less than

(b) Is less than

(c) Is greater than

(d) Is equal to

11
Solution:
(a) R₁ is the set of all ordered pairs whose 1ˢᵗ component is two less than the 2ⁿᵈ
component. Therefore, R₁ = {(4, 6); (9, 11)}

Also, Domain (R₁) = Set of all first components of R₁ = {4, 9} and Range (R₂) = Set of all
second components of R₂ = {6, 11}

(b) R₂ is the set of all ordered pairs whose 1ˢᵗ component is less than the second
component.
Therefore, R₂ = {(4, 6); (9, 11); (2, 3)}.
Also, Domain (R₂) = {4, 9, 2} and Range (R₂) = {6, 11, 3}

(c) R₃ is the set of all ordered pairs whose 1ˢᵗ component is greater than the second
component.
Therefore, R₃ = {(8, 4); (6, 3); (3, 0)}
Also, Domain (R₃) = {8, 6, 3} and Range (R₃) = {4, 3, 0}

(d) R₄ is the set of all ordered pairs whose 1ˢᵗ component is equal to the second component.
Therefore, R₄ = {(4, 4)}
Also, Domain (R) = {4} and Range (R) = {4} 12
2. Let A = {2, 3, 4, 5} and B = {8, 9, 10, 11}. b.
Let R be the relation ‘is factor of’ from A to B.

(a) Write R in the roster form. Also, find

Domain and Range of R.

(b) Draw an arrow diagram to represent the 3. The arrow diagram below shows the relation
relation. (R) from set A to set B. Write this relation in
the roster form.

Solution: Solution:
(a) Clearly, R consists of elements (a, b) where Clearly, R consists of elements (a, b), such that
a is a factor of b. ‘a’ is square of ‘b’
i.e., a = b².
So, in roster form R = {(9, 3); (9, -3); (4, 2); (4, -
Therefore, Relation (R) in the roster form is R 2); (16, 4); (16, -4)}
= {(2, 8); (2, 10); (3, 9); (4, 8), (5, 10)}

Therefore, Domain (R) = Set of all first

components of R = {2, 3, 4, 5} and Range (R) =
Set of all second components of R = {8, 10, 9}
13
 Worked problems on domain and range of a relation:
4. Let A = {1, 2, 3, 4, 5} and B = {p, q, r, s}.
Let R be a relation from A in B defined by Solution:
R = {1, p}, (1, r), (3, p), (4, q), (5, s), (3, p)} Since, x = {0, 1, 2, 3, 4, 5}
Therefore,
Find domain and range of R. x = 0 ⇒ x + 2 = 0 + 2 = 2 and x + 3 = 0 + 3 = 3
x = 1 ⇒ x + 2 = 1 + 2 = 3 and x + 3 = 1 + 3 = 4
Solution: x = 2 ⇒ x + 2 = 2 + 2 = 4 and x + 3 = 2 + 3 = 5
x = 3 ⇒ x + 2 = 3 + 2 = 5 and x + 3 = 3 + 3 = 6
Given R = {(1, p), (1, r), (4, q), (5, s)} x = 4 ⇒ x + 2 = 4 + 2 = 6 and x + 3 = 4 + 3 = 7
Domain of R = set of first components of x = 5 ⇒ x + 2 = 5 + 2 = 7 and x + 3 = 5 + 3 = 8
all elements of R = {1, 3, 4, 5} Hence, R = {(2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7,
Range of R = set of second components of 8)}
all elements of R = {p, r, q, s} Therefore, Domain of R = {a : (a, b) ∈R} = Set of first
components of all ordered pair belonging to R.
Therefore, Domain of R = {2, 3, 4, 5, 6, 7}
5. Determine the domain and range of the Range of R = {b : (a, b) ∈ R} = Set of second
relation R defined by R = {x + 2, x + 3} : x components of all ordered pairs belonging to R.
∈ {0, 1, 2, 3, 4, 5} Therefore, Range of R = {3, 4, 5, 6, 7, 8}
14
6. Let A = {3, 4, 5, 6, 7, 8}. Define a
7. The adjoining figure shows a relation between
relation R from A to A by
the sets A and B.
R = {(x, y) : y = x - 1}.
Write this relation in
• Depict this relation using an arrow
• Set builder form
diagram.
• Roster form
• Write down the domain and range of R.
• Find the domain and range
Solution:
Solution:
By definition of relation
We observe that the relation R is 'a’ is the
R = {(4, 3) (5, 4) (6, 5)}
square of ‘b’.
The corresponding arrow diagram is shown.
In set builder form R = {(a, b) : a is the square of
b, a ∈ A, b ∈ B}
We can see that domain = {4, 5, 6} and
In roster form R = {(4, 2) (4, -2)(9, 3) (9, -3)}
Range = {3, 4, 5}
Therefore, Domain of R = {4, 9}

Range of R = {2, -2, 3, -3}

Note: The element 1 is not related to any

element in set A.
15
 Kinds of Relations
A relation R on a set A is called
• Reflexive • reflexive if for all a ∈ A, aRa.
• Symmetric • symmetric if for all a, b ∈ A, aRb implies
bRa.
• Antisymmetric • antisymmetric if for all a, b ∈ A, aRb and
(Asymmetric) bRa implies a = b.
• transitive if for all a, b, c ∈ A, aRb and bRc
• transitive implies aRc.

16
 Mapping or Functions:

• If A and B are two non-empty sets, then a relation ‘f‘

from set A to set B is said to be a function or mapping,
• If every element of set A is associated with unique
element of set B.
• The function ‘f’ from A to B is denoted by f : A →
B.
• If f is a function from A to B and x ∈ A, then f(x)
∈ B where f(x) is called the image of x under f and
x is called the pre image of f(x) under ‘f’.
• Note:
For f to be a mapping from A to B:

● Every element of A must have image in B.

Adjoining figure does not represent a mapping
since the element d in set A is not associated with
any element of set B. 17
For f to be a mapping from A to B:
No element of A must have more than one image.
Note:
Adjoining figure does not represent a mapping Every mapping is a relation but every
since element b in set A is associated with two relation may not be a mapping.
elements d, f of set B. • Two or more elements of A may
have the same image in B.

● f : x → y means that under the

function of 'f' from A to B, an
element x of A has image y in B.

● Different elements of A can have the same image ● It is necessary that every f image is
in B. Adjoining figure represents a mapping. in B but there may be some
elements in B which are not f
images of any element of A.

18
 Domain,Co-domain and Range of Function

Let : A → B (f be function from A to B),

then
Set A is known as the domain of the
function ‘f’

● Set B is known as the co-domain of the

function ‘f’
Solution:
● Set of all f-images of all the elements (a) a has unique image p.
of A is known as the range of f. Thus, b has unique image q.
range of f is denoted by f(A). c has unique image q.
1. Which of the arrow diagrams given d has unique image r.
below represents a mapping? Give Thus, each element of A has a unique
reasons to support your answer image in B. Therefore, the given
arrow diagram (a) represents a
mapping.
19
(b) In the given arrow diagram, the element ‘a’ of set A is associated with two
elements, i.e., q and r of set B. So, each element of set A does not have a
unique image in B.

Therefore, the given arrow diagram (b) does not represent a mapping.

(c) The element ‘b’ of set A is not associated with any element of set B. So b ∈
A does not have any image. For a mapping from A to B, every element of set
A must have a unique image in set B which is not represented by this arrow
diagram. So, the given arrow diagram (c) does not represent a mapping.
(d) a has a unique image p. b has a unique image q. c has a unique image r. Thus,
each element in set A has a unique image in set B.

Therefore, the given arrow diagram (d) represents a mapping.

20
2. Find out if R is a mapping from A to B. 3. Let A = {1, 2, 3, 4} and B = {0, 3, 6, 8, 12, 15}
(i) Let A = {3, 4, 5} and B= {6, 7, 8, 9} and Consider a rule f (x) = x² - 1, x∈A, then
R = {(3, 6) (4, 7) (5, 8)}
(a) show that f is a mapping from A to B.
Solution:
(b) draw the arrow diagram to represent the
Since, R = {(3, 6); (4, 7); (5, 8)} then Domain mapping.
(R) = {3, 4, 5} = A
(c) represent the mapping in the roster form.
We observe that no two ordered pairs in R
have the same first component. (d) write the domain and range of the
Therefore, R is a mapping from A to B. mapping.
(ii) Let A = {1, 2, 3} and B= {7, 11} and R = {(1, Solution:
7); (1, 11); (2, 11); (3, 11)} (a)
Solution: Using f (x) = x² - 1, x ∈ A we have
Since, R = {(1, 7); (1, 11); (2, 11); (3, 11)} f(1) = 0,
then Domain (R) = {1, 2, 3} = A f(2) = 3,
But the ordered pairs (1, 7) (1, 11) have the f(3) = 8,
same first component. f(4) = 15
We observe that every element in set A has
Therefore, R is not a mapping from A to B. unique image in set B.
Therefore, f is a mapping from A to B.
21
(b) Arrow diagram which represents the
mapping is given below.
Representation of a function by an arrow
diagram:

In this, we represent the sets by closed

figures and the elements are
represented by points in the closed
figure.
(c) Mapping can be represented in the
roster form as The mapping f : A → B is represented by
f = {(1, 0); (2, 3); (3, 8); (4, 15)} arrow which originates from elements
of A and terminates at the elements
of B.
(d) Domain (f) = {1, 2, 3, 4} Range (f) =
{0, 3, 8, 15}

22
 Some examples of functions:

Note:
• Observe in figure (i) and figure (ii), there are some elements in B which are not f-
images of any elements of A. In figure (iii), figure (iv), two elements of A have the
same image in B. 23
 Ordered pairs
• The definition of a set explicitly disregards the order of the set elements, all that matters is who’s in, not
who’s in first
• However, sometimes the order is important leading to the notion of an ordered pair of two elements x and y,
denoted (x, y).
• The crucial property is:
• (x, y) = (u, v) if and only if x = u and y = v.
• This notion can be extended naturally to define an ordered n-tuple as the ordered counterpart of a set with n
elements.
• Given two sets A and B, their cartesian product A×B is the set of all ordered pairs (x, y), such that x ∈ A and y
∈ B:
A x B = {(x, y) : x ∈ A, y ∈ B}.
useful special case:
A2 = A × A = {(x, y) : x, y ∈ A}.
a general definition: A1 = A, and for n ≥ 2,
An = {(x1, x2, . . . , xn) : x1, x2, . . . , xn ∈ A}

24
.
 DEFINITION

• A (numerical) sequence is an ordered list of numbers.

Examples: 2, 4, 6, 8, 10, 12, . . . (positive even integers)
0, 1, 1, 2, 3, 5, 8, . . . (the Fibonacci numbers)
0, 1, 3, 6, 10, 15, . . . (numbers of key comparisons in selection sort)
• A sequence is usually denoted by a letter (such as x or a) with a subindex (such as n or i) written in curly brackets,
e.g., {xn}.
• We use the alternative notation x(n). This notation stresses the fact that a sequence is a function: its argument n
indicates a position of a number in the list, while the function’s value x(n) stands for that number itself. x(n)
is called the generic term of the sequence.
• There are two principal ways to define a sequence:
• by an explicit formula expressing its generic term as a function of n, e.g.,
x(n) = 2n for n ≥ 0
• by an equation relating its generic term to one or more other terms of the sequence, combined with one or more
explicit values for the first term(s),
x(n) = x(n − 1) + n for n > 0, (1)
x(0) = 0. (2)
The latter method is particularly important for analysis of recursive algorithms 25
 Recurrence Equation or Recurrence Relation
(or simply a recurrence)

• An equation such as (1) is called a recurrence equation or

recurrence relation (or simply a recurrence), and
• an equation such as (2) is called its initial condition.
• An initial condition can be given for a value of n other than 0 (e.g.,
for n = 1)
• For some recurrences (e.g., for the recurrence F(n) = F(n − 1) + F(n −
2), defining the Fibonacci numbers more than one value needs to be
specified by initial conditions.

26
 Solving a Recurrence
To solve a given recurrence subject to a given initial condition implies to find an explicit formula for
the generic term of the sequence that satisfies both the recurrence equation and the initial condition
or to prove that such a sequence does not exist. For example, the solution to recurrence (1) subject
to initial condition (2) is

𝑛 𝑛+1
𝑥(𝑛) = for n≥0. (3)
2
by substituting this formula into (1) to check that the equality holds for every n > 0, i.e., that
𝑛 𝑛+1 𝑛−1 𝑛−1+1
= +n
2 2
and into (2) to check that 𝑥 0 =0 i.e., that
0 0+1
=0
2

27
 General Solution to a Recurrence Equation
Sometimes it is convenient to distinguish between a general solution and a particular solution to a
recurrence. Recurrence equations typically have an infinite number of sequences that satisfy them.
A general solution to a recurrence equation is a formula that specifies all such sequences.
Typically, a general solution involves one or more arbitrary constants. For example, for recurrence
(1), the general solution can be specified by the formula
𝑛 𝑛+1
𝑥 𝑛 =𝑐+ (4)
2
Where c is such an arbitrary constant. By assigning different values to c,
we can get all the solutions to equation (1) and only these solutions.
A particular solution is a specific sequence that satisfies a given recurrence
equation.
Usually we are interested in a particular solution that satisfies a given initial
condition. For example, sequence (3) is a particular solution to (1)– (2).
28
 Methods for Solving Recurrence Relations
No universal method exists that would enable us to solve every recurrence relation.
There are several techniques, however, some more powerful than others, that
can solve a variety of recurrences. We consider 2.

• Method of Forward Substitutions

• Method of Backward Substitutions

29
 Method of Forward Substitutions
Starting with the initial term (or terms) of the sequence given by the initial condition(s), we can use the recurrence
equation to generate the few first terms of its solution in the hope of seeing a pattern that can be expressed by a
closed-end formula.
If such a formula is found, its validity should be either checked by direct substitution into the recurrence equation
and the initial condition (as we did for (1)–(2)) or proved by mathematical induction.

For example, consider the recurrence

x(n) = 2x(n − 1) + 1 for n > 1, (5)
x(1) = 1. (6)
We obtain the few first terms as follows:
x(1) = 1,
x(2) = 2x(1) + 1= 2 . 1+ 1= 3,
x(3) = 2x(2) + 1= 2 . 3 + 1= 7,
x(4) = 2x(3) + 1= 2 . 7 + 1= 15.
It is not difficult to notice that these numbers are one less than consecutive powers of 2:
x(n) = 2n − 1 for n = 1, 2, 3, and 4.
30
We can prove the hypothesis that this formula yields the generic term of the
solution to (5)–(6) either by direct substitution of the formula into (5) and (6) or
by mathematical induction.
As a practical matter, the method of forward substitutions works in a very limited
number of cases because it is usually very difficult to recognize the pattern in
the first few terms of the sequence.

31
 Method of Backward Substitutions

• works exactly as its name implies: using the recurrence relation in question, we
express x(n − 1) as a function of x(n − 2) and substitute the result into the original
equation to get x(n) as a function of x(n − 2).
• Repeating this step for x(n −2) yields an expression of x(n) as a function of x(n −
3).
• For many recurrence relations, we will then be able to see a pattern and express
x(n) as a function of
x(n − i) for an arbitrary i = 1, 2, . . . . Selecting i to make n − i reach the initial
condition and using one of the standard summation formulas often leads to a
closed-end formula for the solution to the recurrence.

32
As an example, let us apply the method of backward substitutions to recurrence (1)–(2).
Thus, we have the recurrence equation
x(n) = x(n − 1) + n.
Replacing n by n − 1 in the equation yields x(n − 1) = x(n − 2) + n − 1; after substituting this
expression for x(n − 1) in the initial equation, we obtain
x(n) = [x(n − 2) + n − 1]+ n = x(n − 2) + (n − 1) + n.
Replacing n by n − 2 in the initial equation yields x(n − 2) = x(n − 3) + n − 2; after
substituting this expression for x(n − 2), we obtain
x(n) = [x(n − 3) + n − 2]+ (n − 1) + n = x(n − 3) + (n − 2) + (n − 1) + n.
Comparing the three formulas for x(n), we can see the pattern arising after i such
substitutions:
x(n) = x(n − i) + (n − i + 1) + (n − i + 2) + . . . + n.
Since initial condition (2) is specified for n = 0, we need n − i = 0, i.e., i = n, to reach it:
x(n) = x(0) + 1+ 2 + . . . + n = 0 + 1+ 2 + . . . + n = n(n + 1)/2.
33
The method of backward substitutions works well for a
wide variety of simple recurrence relations.
There are many examples of its successful applications
of this method in computing
e.g. Mathematical Analysis of Recursive Algorithms
(in CMP 452)

34