Mathematical Concepts For Computing

AQ010-3-1 (Version E)

RELATIONS AND FUNCTIONS

 TOPIC LEARNING OUTCOMES
At the end of this topic, You should be able to
• Understand the concept of relations and their representation
• Define the Cartesian product of two sets
• Calculate the number of relations between two sets using the power set
• Learn about different properties of relations, such as reflexivity, symmetry, and
transitivity
• Understand the concept of a function
• Determine whether a given relation is a function
• Determine the domain and range of a relation and function
• Understand operations on functions such as addition, subtraction, multiplication,
and division on functions
• Calculate composite functions and inverse functions.

AQ010-3-1-MCFC Relations and Functions SLIDE 2

 Contents & Structure
• Relations
• Representation of relations
• Cartesian product
• Properties of relations
• Functions
• Domain and range
• Operations on functions
• Composite functions
• Inverse functions

AQ010-3-1-MCFC Relations and Functions SLIDE 3

 Introduction

The most direct way to express a relationship between elements of two sets is to use
ordered pairs made up of two related elements. For this reason, sets of ordered pairs
are called binary relations.
Applications
Relations can be used to
• solve problems such as determining which pairs of cities are linked by airline flights
in a network,
• finding a viable order for the different phases of a complicated project or producing
a useful way to store information in computer databases.

AQ010-3-1-MCFC Relations and Functions SLIDE 4

 Applications

To explain the connection / relationship between

• a program and a variable it uses.

• a computer language and a valid statement in the language.
• elements of sets are represented using the structure called a relation.
• people, numbers, sets, and many other entities can be formalized in the idea of a
binary relation.

AQ010-3-1-MCFC Relations and Functions SLIDE 5

 Relation
Example 1:
Let A be the set of students in your school,
B be the set of courses, and
R be the relation that consists of those pairs (a, b),
where a is a student enrolled in course b.
For instance,
 If Jason and Sherman are enrolled in MCFC, the pairs (Jason, MCFC) and
(Sherman, MCFC) belong to R.
 If Jason is also enrolled in IOOP, then the pair (Jason, IOOP) is also in R.
 However, if Sherman is not enrolled in FSD, then the pair (Sherman, FSD) is not in
R.

AQ010-3-1-MCFC Relations and Functions SLIDE 6

 Cartesian Product Set

Ordered pairs
An ordered pair consists of two elements, of which one is designated as the
first element and the other as the second element.
 It is written as (a, b) where a is the first element and b is the second element.

Definition:
We use the notation aRb to denote that (a, b)R, and a is said to be related to b by R
if aRb.

AQ010-3-1-MCFC Relations and Functions SLIDE 7

 Cartesian Product Set

Consider two sets, the set of all ordered pairs (a, b) where a A and b B is
called the product , or Cartesian product of A and B.

• A short designation of this product is A x B, which is read “A crosses B”, by

definition
A x B = (a, b)a  A, b  B
 A x A can be represented as A2

AQ010-3-1-MCFC Relations and Functions SLIDE 8

 Cartesian Product Set

A binary relation between set A and B is a subset of A × B.

Example 2:
Given A={1, 2}, B={p, q}
A × B = { (1,p), (1, q), (2, p), (2, q) }

If R1={(1, p)}, R2={(2, k)} and R3={(1,q), (2,p)}

R1 and R3 are the relations between A and B,

but R2 is not the relation between A and B.

AQ010-3-1-MCFC Relations and Functions SLIDE 9

 Representation of relations

Example 3:
Let A ={ 0,1,2} and B ={a, b}.
Then {(0,a),(0,b),(1,a),(2,b)} is a relation from A to B.
Relations can be represented graphically using arrows to represent ordered pairs or to
use a table.

AQ010-3-1-MCFC Relations and Functions SLIDE 10

 Example 4
Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R = { (a, b)| a
divides b }?
Sol :

1 1
2 2

3 3

4 4

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

(2,2), (2,4),
(3,3),
(4,4) }
AQ010-3-1-MCFC Relations and Functions SLIDE 11
 Example 5: Consider the following relations on Z.
R1 = { (a, b) | a  b }
R2 = { (a, b) | a > b }
R3 = { (a, b) | a = b or a = -b } Which of these relations
contain each of the pairs
R4 = { (a, b) | a = b } (1,1), (1,2), (2,1), (1,-1),
R5 = { (a, b) | a = b+1 } and (2,2)?
R6 = { (a, b) | a + b  3 }
Sol : (1,1) (1,2) (2,1) (1,-1) (2,2)
R1 ● ● ●
R2 ● ●

R3 ● ● ●

R4 ● ●

●
R5
● ● ● ●
AQ010-3-1-MCFC R6 Relations and Functions SLIDE 12
 Relation - Domain and range
Domain of R : Dom(R) is the set of all elements in A that are related to some
element in B.
Range of R : Ran(R) is the set of all elements in B that are related to some
element in A.
Example 6: Let A = {Alice, Bob, Claire, Dan} be a set students, and
B= {CS101, CS201, CS202} be a set of courses.
Then, a possible relation is:
{(Alice, CS101), (Bob, CS201), (Bob, CS202), (Dan, CS201), (Dan, CS202)}

Domain = {Alice, Bob, Dan}

Range = { CS101, CS201, CS202}

AQ010-3-1-MCFC Relations and Functions SLIDE 13

 Representing Relations

AQ010-3-1-MCFC Relations and Functions SLIDE 14

 Quick Review Question 1

Given A = {1, 2, 3, 4} and B = {x, y, z}. Let R be the following relation from A to B:
R = {(1,y), (1,z), (3,y), (4,x), (4,z)}
(a) Find A x B.
(b) Use table and arrow diagram to represent R.
(c) Determine the domain and range of R.

AQ010-3-1-MCFC Relations and Functions SLIDE 15

 Number of relations on a set
• A relation on set A is a subset of A × A has n2 elements when A has n elements and a
set with m elements has 2m subsets of A × A .
• Thus, there are 2n2 relations on a set with n elements.

Example 7: A = { a, b, c}

The number of relations on set A = 232 =29=512

AQ010-3-1-MCFC Relations and Functions SLIDE 16

 Equivalence Relation

• An equivalence relation is a binary relation that

is reflexive, symmetric and transitive.

Properties of a relation:
Let R be a relation on a set A,
- R is reflexive : If (a,a)  R for every element a  A.
- R is symmetric : If (b,a)  R whenever (a,b)  R, for some a,b  A.
- R is transitive: If (a,b)  R and (b,c)  R, then
(a,c)  R , for a, b, c  A.

AQ010-3-1-MCFC Relations and Functions SLIDE 17

 Properties of Relations

Example 8: Are the following relations on {1, 2, 3, 4} reflexive?

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

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

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

Sol: R2

AQ010-3-1-MCFC Relations and Functions SLIDE 18

 Properties of Relations

Example 9:
Are the following relations on {1, 2, 3, 4} symmetric?

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

Sol: R1, R2

AQ010-3-1-MCFC Relations and Functions SLIDE 19

 Properties of Relations

Example 10:
Are the following relations on {1, 2, 3, 4} transitive?

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

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

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

Sol: R1

AQ010-3-1-MCFC Relations and Functions SLIDE 20

 Example 11
Consider the relation R on a set {1,2,3,4,5}.
R = {(1,1), (1,3), (1,5), (2,2), (2,4), (3,1), (3,3), (3,5), (4,2), (4,4), (5,1), (5,3), (5,5)} is an
equivalence relation?

Answer:
• R is reflexive because (1,1), (2,2), (3,3), (4,4), (5,5) are in R.
• R is symmetric because whenever (x,y) is in R, (y,x) is in R as well.
• R is transitive because whenever (x,y) and (y,z) are in R, (x,z) is in R as well.
• So, R is an equivalence realtion.

AQ010-3-1-MCFC Relations and Functions SLIDE 21

 Quick Review Question 2

Consider the relation R on a set {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)}

Answer:
R is NOT an equivalence relation because R is not symmetric.

AQ010-3-1-MCFC Relations and Functions SLIDE 22

 Functions

A function f from a nonempty set A to a nonempty set B is an assignment of

exactly one element of B to each element of A.

We write the function as f : A  B.

Functions are also called mappings or transformations.

- b = f(a) is called the image of a under f, and a

f
• • is called the object of b.
a b= (a)
- A is the domain of f and B is the co-domain
A B - f(A) = { f(a) | a  A} is called the range of f

AQ010-3-1-MCFC Relations and Functions SLIDE 23

 From Relation to Function

A relation f from A to B is a function if:

• Every element of A is related to some element of B
• An element of A cannot be related to more than one element of B.

A B A B

1 a 1 a
2 b 2 b
3 c 3 c
4 4

A function (many-to-one) Not a function (one-to-many)

AQ010-3-1-MCFC Relations and Functions SLIDE 24

 Relation Vs Function
A function yields a single result for any element in its domain.
Example: age (of a person), square (of an integer) etc.

A relation allows multiple mappings between the domain and the co-domain.
Example: students enrolled in multiple courses.

AQ010-3-1-MCFC Relations and Functions SLIDE 25

 Example 12
Determine whether the following relation is a function.

A B A B

α 1 α 1
β 2 β

γ 2
γ 3

A Not a function B A B
Not a function

α 1 α 1
2
β 2 β
3
γ γ
4
a function a function

AQ010-3-1-MCFC Relations and Functions SLIDE 26

 Example 13
Let f be the function defined by the rule f(x)= X2
f

0 0
1
1 2
3
2 4

Set X Set Y

X2 = Y is a function from X to Y.
Domain is {0, 1, 2} and Codomain is {0, 1, 2, 3, 4}.

f(a)=b, so f(0)=0, f(1)=1 and f(2)=4

Range is {0,1,4}
AQ010-3-1-MCFC Relations and Functions SLIDE 27
 Operations on Functions

 Sum of functions
(f +g)(x) = f(x) + g(x)

 Difference of functions
(f – g)(x) = f(x) – g(x)

 Product of functions
(fg)(x) = f(x) . g(x)

 Quotient of functions
(f/g)(x) = f(x)
g(x)

AQ010-3-1-MCFC Relations and Functions SLIDE 28

 Example 14

Given
Find:

1.( f  g )( x)
2.( f  g )( x)
3.( fg )( x)
f ( x)
4.
g ( x)

AQ010-3-1-MCFC Relations and Functions SLIDE 29

 Composite Functions

 Let g be a function from the set A to the set B and let f be a function from set B the
set C.
 Find the image of a under f and then find the image of f(a) under g.
 The composition functions f and g, is defined by
(g o f)(a) = g(f(a))

AQ010-3-1-MCFC Relations and Functions SLIDE 30

 Composition Functions- Example

You use composite functions whenever you buy a sale (discounted) item. When you are
standing in the store trying to decide if you can afford the item, the first thing you
calculate is the discount.
• For example, I want to buy this 20-dollar shirt, and it is on sale at 15% off. This
means that the shirt is really 17 dollars.
• Now, you must calculate what the shirt will cost after sales tax (let's say it is 8%).
• Your total cost for the shirt after the discount and sales tax will be $18.36. This
process of computation can be expressed as a composite function.
• If f(x) = The price of the shirt after the discount and g(x) = The price after sales tax
then,
• The function for the final cost of the shirt = g(f(x)).

AQ010-3-1-MCFC Relations and Functions SLIDE 31

 Example 15
Given . Find:

1. fog ( x)
2.gof ( x)

AQ010-3-1-MCFC Relations and Functions SLIDE 32

 Inverse Functions

Let f be a one-to-one function 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 as f -1.
Hence, f -1(b) = a when f(a) = b.

AQ010-3-1-MCFC Relations and Functions SLIDE 33

 Example 16
Given that f ( x)  2 x  1find
, f 1
( xand
) f 1
(15)

AQ010-3-1-MCFC Relations and Functions SLIDE 34

 Summary / Recap of Main Points

• Relations
• Representation of relations
• Cartesian product
• Properties of relations
• Functions
• Domain and range
• Operations on functions
• Composite functions
• Inverse functions

AQ010-3-1-MCFC Relations and Functions SLIDE 35