CC 141

Discrete Structures
Department of Computer Science
School of Systems and Technology

University of Management and Technology

Lahore, Pakistan
Chapter No. 9

Relations
 ORDERED PAIR
• An ordered pair (a, b) consists of two elements “a” and “b” in
which “a” is the first element and “b” is the second element.

• The ordered pairs (a, b) and (c, d) are equal if, and only if,
a = c and b = d.

• Note that (a, b) and (b, a) are not equal unless a = b.

3
 EXERCISE
• Find x and y given (2x, x + y) = (6, 2)

• SOLUTION:
Two ordered pairs are equal if and only if the corresponding
components are equal. Hence, we obtain the equations:
2x = 6 ……………(1)
and x + y = 2 ……………..(2)

Solving equation (1) we get x = 3 and when substituted in (2) we

get y = -1.

4
Ordered Pairs ………. Practice Questions
1. Find x and y given (x2 – 5x, 7) = (6, y2 - 6y)
2. Find x and y, if (2x - 3, y + 1) = (x + 5, 7)
3. Given (x - 3, y + 2) = (4, 5), find x and y.
 ORDERED n-TUPLE
• The ordered n-tuple, (a1, a2, …, an) consists of elements a1, a2, ..an together with
the ordering: first a1, second a2, and so forth up to an.

• In particular, an ordered 2-tuple is called an ordered pair, and an ordered 3-

tuple is called an ordered triple.

• Two ordered n-tuples (a1, a2, …, an) and (b1, b2, …, bn) are equal if and only if
each corresponding pair of their elements is equal, i.e., ai = bj, for all i = 1, 2, …,
n.

6
CARTESIAN PRODUCT OF TWO SETS
• Let A and B be sets. The Cartesian product of A and B, denoted A 
B (read “A cross B”) is the set of all ordered pairs (a, b), where a is
in A and b is in B.

• Symbolically:
A B = {(a, b)| a  A and b  B}

• NOTE
If set A has m elements and set B has n elements then
A  B has m  n elements.

7
CARTESIAN PRODUCT OF TWO SETS
 EXAMPLE
• Let A = {1, 2}, B = {a, b, c} then Evaluate:

i. AB
ii. BA
iii. AA
iv. BB

9
 EXAMPLE
• Let A = {1, 2}, B = {a, b, c} then

A  B = {(1,a), (1,b), (1,c), (2,a), (2, b), (2, c)}

B  A = {(a,1), (a,2), (b, 1), (b, 2), (c, 1), (c, 2)}
A  A = {(1, 1), (1,2), (2, 1), (2, 2)}
B  B = {(a,a), (a,b), (a,c), (b,a), (b, b), (b, c),
(c,a),
(c,b),(c,c)}

10
 REMARK
o A  B  B  A for non-empty and unequal sets A and B.
oA   =   A = 
o | A  B| = |A|  |B|

11
 CARTESIAN PRODUCT OF MORE THAN
TWO SETS
• The Cartesian product of sets A1, A2, …, An,
denoted A1 A2  … An, is the set of all ordered
n-tuples (a1, a2, …, an)

where
a1 A1, a2  A2,…, an  An.

• Symbolically:
A1 A2  … An ={(a1, a2, …, an) | ai Ai, for i=1, 2, …, n}

12
 BINARY RELATION
• Let A and B be sets. A (binary) relation R from A to B is a
subset of A  B.

• When (a, b)  R, we say a is related to b by R,

written a R b.

Otherwise if (a, b)  R, we write a R b.

13
 EXERCISE
• Let A = {1, 2}, B = {1, 2, 3}
Then A  B = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}
Let
R1 = {(1,1), (1, 3), (2, 2)}
R2 = {(1, 2), (2, 1), (2, 2), (2, 3)}
R3 = {(1, 1)}
R4 = A  B
R5 = 

All being subsets of A  B are relations from A to B.

14
 DOMAIN OF RELATION
• The domain of a relation R from A to B is the set of
all first elements of the ordered pairs which belong
to R denoted Dom(R).

• Symbolically:
Dom (R) = {a  A | (a, b)  R}

15
 RANGE OF RELATION
• The range of a relation R from A to B is the set of all second
elements of the ordered pairs which belong to R denoted
Ran(R).

• Symbolically:
Ran(R) = {b B|(a,b)  R}

16
 EXERCISE
• Let A = {1, 2}, B = {1, 2, 3},
Define a binary relation R from A to B as follows:
R = {(a, b)  A  B | a < b}
Then
• Find the ordered pairs in R.
• Find the Domain and Range of R.
• Is 1R3, 2R2?

17
 SOLUTION
• Given
A = {1, 2} and B = {1, 2, 3},
A  B = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)}

a.) Find the ordered pairs in R?

R = {(a, b) A  B | a < b}
R = {(1,2), (1,3), (2,3)}
b.) Find the domain and range of R?
Dom(R) = {1,2} and Ran(R) = {2, 3}
c.) Is 1R3, 2R2?
Since (1,3)  R so 1R3
But (2, 2)  R so 2 is not related with 3.

18
 EXERCISE
• Let A = {eggs, milk, corn} and
B = {cows, goats, hens}

• Define a relation R from A to B by (a, b)  R iff a is produced by b.

• Then R = {(eggs, hens), (milk, cows), (milk, goats)}

• Thus, with respect to this relation eggs R hens,

milk R cows, and milk R goats.

19
 EXERCISE
• Find all binary relations from {0,1} to {1}

• SOLUTION:
Let A = {0,1} & B = {1}
Then,
A  B = {(0,1), (1,1)}
All binary relations from A to B are in fact all subsets of
A B, which are:
R1 = 
R2 = {(0,1)}
R3 = {(1,1)}
R4 = {(0,1), (1,1)} = A  B
20
 REMARK
• If |A| = m and |B| = n

• Then as we know that the number of elements in A

 B are m  n.

• Now as we know that the total number of and the

total number of relations from A to B are 2m  n.

21
 EXERCISE
• Define a binary relation E on the set of the integers Z, as
follows:

• for all m, n  Z, m E n  m – n is even.

a) Is 0E0?
b) Is 5E2?
c) Is (6,6)  E?
d) Is (-1,7)  E?
e) Prove that for any even integer n, nE0.

22
 SOLUTION
• E = {(m, n)  Z Z | m – n is even}
(a) (0, 0)  Z  Z and 0 - 0 = 0 is even, Therefore 0E0.

(b) (5, 2)  Z  Z but 5 - 2 = 3 is not even so 5E2

(c) (6, 6)  E since 6 - 6 = 0 is an even integer.

(d) (-1, 7)  E since (– 1) – 7 = – 8 is an even integer.

(e) For any even integer n, we have

n – 0 = n, an even integer
so (n, 0)  E
or 23
 RELATION ON A SET
• A relation on the set A is a relation from A to A.

• In other words, a relation on a set A is a subset of A  A.

24
 EXERCISE
• Let
A = {1, 2, 3, 4}

Define a relation R on A as
(a, b)  R iff a divides b {symbolically written as a  b}

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

25
 REMARK
• For any set A
• A  A is known as the universal relation.
•  is known as the empty relation.

26
 ARROW DIAGRAM OF A RELATION
• Let
A = {1, 2, 3}, B = {x, y} and
R = {(1, y), (2, x), (2, y), (3, x)}
be a relation from A to B.
The arrow diagram of R is:
1 R
x

2
y
3

A B
27
 DIRECTED GRAPH OF A RELATION
• Let
A = {0, 1, 2, 3} and
R = {(0, 0), (1, 3), (2, 1), (2, 2), (3, 0), (3, 1)}
be a binary relation on A.
1
0

2 3

DIRECTED GRAPH 28
 MATRIX REPRESENTATION OF A
RELATION
• Let
A = {a1, a2, …, an} and B = {b1, b2, …, bm}.
Let R be a relation from A to B.
Define the n  m order matrix M by
1 if (ai , bi )  R
m(i, j ) 
0 if (ai , bi )  R

for i=1,2,…,n and j=1,2,…,m

29
 EXAMPLE
• Let A = {1, 2, 3} and B = {x, y}
Let R be a relation from A to B defined as
R = {(1, y), (2, x), (2, y), (3, x)}

x y
1 0 1
M 2  1 1
3  1 0 32

30
 EXAMPLE
• For the relation matrix.
1 2 3
1  1 0 1
M 2  1 0 0
3  0 1 1

• List the set of ordered pairs represented by M.

• Draw the directed graph of the relation.

31
 SOLUTION
• The relation corresponding to the given Matrix is
• R = {(1,1), (1,3), (2,1), (3,1), (3,2), (3,3)}

• And its Directed graph is given below

1 2

3
32
 EXERCISE
• Let
A = {2, 4} and B = {6, 8, 10} and
define relations R and S from A to B as follows:

for all (x, y)  A  B, xRyx|y

for all (x, y)  A  B, xSyy–4=x

State explicitly which ordered pairs are in A  B, R, S,

R  S and R  S.

33
 SOLUTION
A  B = {(2, 6), (2, 8), (2, 10), (4, 6), (4, 8), (4, 10)}

R = {(2, 6), (2, 8), (2, 10), (4, 8)}

S = {(2, 6), (4, 8)}

R  S = {(2, 6), (2, 8), (2,10), (4, 8)} = R

R  S = {(2, 6), (4, 8)} = S

34
 Practice Question ... Do it Yourself
Let A = {2, 3, 5, 6, 8}
The congruence modulo 3 relation T is defined on A as
follows: for all integers m, n  A, mTn  3 | (m – n)
i.e. m-n is divisible by 3
Write T as a set of ordered pairs.
The directed graph representation.
The matrix representation.
 Practice Question ... Do it Yourself
Define a binary relation S from R to R as follows:
for all (x, y)  RXR, xSy  x  y.
Is (2,1)  S?
Is (2,2)  S?
Is 2S3?
Is (-1) S (-2)?
Draw the directed graph of S
 PROPERTIES OF RELATION
• There are several properties that are used to classify relation
on a set. We will introduce the most important of these here.

37
 REFLEXIVE RELATION
• Let R be a relation on a set A. R is reflexive if, and only if, for
all a  A, (a, a) R. Or equivalently aRa.

That is, each element of A is related to itself.

REMARK
R is not reflexive iff there is an element “a” in A such that
(a, a) R. That is, some element “a” of A is not related to itself.

38
 EXAMPLE
• Let A = {1, 2, 3, 4} and define relations R1, R2, R3, R4 on
A as follows:

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

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

39
• Then,
R1 is reflexive, since (a, a)  R1 for all a A.
R2 is not reflexive, because (4, 4)  R2.
R3 is reflexive, since (a, a)  R3 for all a A.
R4 is not reflexive, because (1, 1)  R4, (3, 3)  R4

40
DIRECTED GRAPH OF A REFLEXIVE
RELATION
• The directed graph of every reflexive relation includes an
arrow from every point to the point itself (i.e., a loop).

41
 EXAMPLE
• Let A = {1, 2, 3, 4} and define relations R1, R2, R3 and R4 on A by

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

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

• Then their directed graphs are

42
 1 2
1 2

4 3
R1 is reflexive because at
every point of the set A we 4 3
have a loop in the graph.
R2 is not reflexive, as there
is no loop at 4.
1 2
1 2

4
3
4 3
R4 is not reflexive, as there are
R3 is reflexive no loops at 1and 3.
43
MATRIX REPRESENTATION OF A
REFLEXIVE RELATION

• Let A = {a1, a2, …, an}. A Relation R on A is reflexive

if and only if (ai, aj)  R  i=1,2, …,n.

• Accordingly, R is reflexive if all the elements on the

main diagonal of the matrix M representing R are
equal to 1.

44
 EXAMPLE
• The relation R = {(1,1), (1,3), (2,2), (3,2), (3,3)} on
A = {1, 2, 3} represented by the following matrix M, is
reflexive.

1 2 3
1  1 0 1
M 2  0 1 0
3  0 1 1

45
 SYMMETRIC RELATION
• Let R be a relation on a set A. R is symmetric if, and only if, for
all a, b  A, if (a, b) R then (b, a) R.

• That is, if aRb then bRa.

• REMARK
R is not symmetric iff there are elements a and b in A such
that (a, b)  R but (b, a)  R.

46
 EXAMPLE
• Let A = {1, 2, 3, 4} and define relations R1, R2, R3, and R4 on A as
follows:

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

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

47
• Then R1 is symmetric because for every order pair (a, b) in R1

• We have (b, a) in R1 for example we have (1, 3) in R1

we also have (3,1) in R1 similarly all other ordered pairs can be checked.

• R2 is also symmetric we say it is vacuously true.

• R3 is not symmetric, because (2, 3)  R3 but (3, 2)  R3.
• R4 is not symmetric because (4, 3)  R4 but (3, 4)  R4.

48
DIRECTED GRAPH OF A SYMMETRIC
RELATION
• For a symmetric directed graph whenever there is an arrow
going from one point of the graph to a second, there is an
arrow going from the second point back to the first.

49
 EXAMPLE
• Let A = {1, 2, 3, 4} and define relations R1, R2, R3, and R4 on A
by the directed graphs:

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

50
 2
1 1 2

4
3 4 3
R1 is symmetric R2 is symmetric

1
2
1
2

4
3 4 3

R3 is not symmetric since there R4 is not symmetric since

are arrows from 2 to 3 and from there is an arrow from 4 to 3
3 to 4 but not conversely but no arrow from 3 to 4

51
 MATRIX REPRESENTATION OF A
SYMMETRIC RELATION
• Let
A = {a1, a2, …, an}.
A relation R on A is symmetric if and only if for all
ai, aj  A, if (ai, aj) R then (aj, ai)R.

• Accordingly, R is symmetric if the elements in the ith row are the same as
the elements in the ith column of the matrix M representing R.

• More precisely, M is a symmetric matrix. i.e. M = Mt

52
 EXAMPLE
• The relation R = {(1, 3), (2, 2), (3,1), (3, 3)} on A = {1, 2, 3}
represented by the following matrix M is symmetric.

1 2 3
1  0 0 1
M 2  0 1 0 
3  1 0 1 

53
 TRANSITIVE RELATION
• Let R be a relation on a set A. R is transitive if and only if for all a, b, c  A, if
(a, b)  R and (b, c)  R
then (a, c)  R.

• That is, if aRb and bRc then aRc.

• In words, if any one element is related to a second and that second element is
related to a third, then the first is related to the third.

• Note that the “first”, “second” and “third” elements need not to be distinct. 54
 REMARK
• R is not transitive iff there are elements a, b, c in A such that If
(a, b)  R and (b, c)  R but (a, c)  R.

55
 EXAMPLE
• Let A = {1, 2, 3, 4} and define relations R1, R2 and R3 on A as follows:
R1 = {(1, 1), (1, 2), (1, 3), (2, 3)}
R2 = {(1, 2), (1, 4), (2, 3), (3, 4)}
R3 = {(2, 1), (2, 4), (2, 3), (3,4)}

• Then R1 is transitive because (1, 1), (1, 2) are in R then to be transitive relation
(1,2) must be there and it belongs to R Similarly for other order pairs.
• R2 is not transitive since (1, 2) and (2, 3)  R2 but (1,3)  R2.
• R3 is transitive.

56
DIRECTED GRAPH OF A TRANSITIVE
RELATION
• For a transitive directed graph, whenever there is an arrow
going from one point to the second, and from the second to
the third, there is an arrow going directly from the first to the
third.

57
 EXAMPLE
• Let A = {1, 2, 3, 4} and define relations R1, R2 and R3 on A by
the directed graphs:

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

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

58
 1 1 2
2

4 4 3
3
R1 is transitive R2 is not transitive since there is
an arrow from 1 to 2 and from 2
2 to 3 but no arrow from 1 to 3
1 directly

4
3
R3 is transitive
59
 EXERCISE
• Let A = {1, 2, 3, 4} and define the null relation  and universal
relation A  A on A. Test these relations for reflexive,
symmetric and transitive properties.

60
 SOLUTION
• Reflexive:
•  is not reflexive since (1,1), (2,2), (3,3), (4,4)  .
• A  A is reflexive since (a, a)  A  A for all a  A.

61
• Symmetric
• For the null relation  on A to be symmetric, it must
satisfy the implication:
if (a, b)   then (b, a)  .
Since (a, b)   is never true, the implication is
vacuously true or true by default.
Hence  is symmetric.

• The universal relation A  A is symmetric, for it

contains all ordered pairs of elements of A. Thus,
if (a, b)  A  A then (b, a)  A  A for all a,
b in A.
62
• Transitive
• The null relation  on A is transitive, because the implication.
if (a, b)   and (b, c)   then (a, c)   is true by default,
Since the condition (a, b)   is always false.

• The universal relation A  A is transitive for it contains all ordered

pairs of elements of A.

Accordingly, if (a, b)  A  A and (b, c)  A  A

then (a, c)  A  A as well.

63
 EXERCISE
• Let A = {0, 1, 2} and
R = {(0, 2), (1,1), (2, 0)} be a relation on A.

• Is R reflexive? Symmetric? Transitive?

• Which ordered pairs are needed in R to make it a reflexive and
transitive relation.

64
 SOLUTION
• R is not reflexive, since 0  A but (0, 0) R and also
2  A but (2, 2)  R.

• R is clearly symmetric.

• R is not transitive, since (0, 2) & (2, 0)  R but (0, 0) R.

65
• For R to be reflexive, it must contain ordered pairs (0,0) and (2,2).

• For R to be transitive,
we note (0, 2) and (2, 0)  R but (0, 0)  R.
Also (2, 0) and (0, 2)  R but (2, 2) R.

• Hence (0, 0) and (2, 2). Are needed in R to make it a transitive

relation.

66
 Practice Question ... Do it Yourself

Define a relation L on the set of real numbers R be

defined as follows:
for all x, y  R, x L y  x < y.
1. Is L reflexive?
2. Is L symmetric?
3. Is L transitive?
 Practice Question ... Do it Yourself
Define a relation R on the set of positive integers Z+ as
follows:
for all a, b  Z+, a R b iff a x b is odd.
Determine whether the relation is
a. Reflexive
b. Symmetric
c. Transitive
Justify your answer.
 Practice Question ... Do it Yourself
Let “D” be the “divides” relation on Z+ defined as: for all
m, n  Z, mDn  m|n.
Determine whether the relation is
a. Reflexive
b. symmetric
c. transitive
Justify your answer.
 EQUIVALENCE RELATION
• Let A be a non-empty set and R a binary relation on A.
R is an equivalence relation if, and only if, R is reflexive,
symmetric, and transitive.

70
 EXAMPLE
• Let A = {1, 2, 3, 4} and
R = {(1,1), (2, 2), (2, 4), (3, 3), (4, 2), (4, 4)}
be a binary relation on A.

• Note that R is reflexive, symmetric and transitive, hence an

equivalence relation.

71
 Irreflexive Relation
Let R be a binary relation on a set A. R is irreflexive iff
for all a  A, (a, a)  R. That is, R is irreflexive if no
element in A is related to itself by R.

REMARK:

R is not irreflexive iff there is an element a  A such that

(a, a)  R.
 Example
Let A = {1,2,3,4} and define the following relations on A:
R1 = {(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)}
R2 = {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)}
R3 = {(1,2), (2,3), (3,3), (3,4)}

Solution:
1. Relation R1 is irreflexive relation
2. Relation R2 is reflexive
3. Relation R3 is neither irreflexive nor is reflexive
Matrix Representation of Irreflexive Relation
A relation is irreflexive if in its matrix representation the
diagonal elements are all zero, if one of them is not zero the we
will say that the relation is not irreflexive.

EXAMPLE :
Let A = {1,2,3} and R = {(1,3), (2,1), (2,3),
1 2 3
(3,2)} be represented by the matrix 1  0 0 1

M 2  1 0 1 
3  0 1 0
R is irreflexive, since all elements in the main diagonal
are 0’s.
 Example

Let R be the relation on the set of integers Z defined as:

for all a,b  Z, (a,b)  R  a > b.
Is R irreflexive?
 Anti-Symmetric Relation
Let R be a binary relation on a set A.
R is anti-symmetric iff

 a, b  A if (a,b)  R and (b,a)  R then a = b

Remarks:
1. R is not anti-symmetric iff there are elements a and b in A
such that (a,b)  R and (b, a)  R but a  b
2. The properties of being symmetric and being anti-
symmetric are not negative of each other
 Example
Let A = {1,2,3,4} and define the following relations on
A.
R1 = {(1,1),(2,2),(3,3)}
R2 = {(1,2),(2,2), (2,3), (3,4), (4,1)}
R3={(1,3),(2,2), (2,4), (3,1), (4,2)}
R4={(1,3),(2,4), (3,1), (4,3)}

Which of above relations are Anti-Symmetric?

Matrix Representation of Anti-Symmetric Relation
Let R be an anti-symmetric relation on a set A = {a1, a2, …, an}.
Then if (ai, aj)  R for i  j then (aj, ai)  R
Thus in the matrix representation of R there is a 1 in the ith row
and jth column iff the jth row and ith column contains 0 vice
versa
EXAMPLE :
Let A = {1,2,3} and a relation R
1 2 3
= {(1,1), (1,2), (2,3), (3,1)} on A
be represented by the matrix.
1  1 1 0
M 2  0 0 1
3  1 0 0
 Partial Order Relation

 Let R be a binary relation defined on a set A. R is a

partial order relation, iff R is reflexive, anti-
symmetric, and transitive
 The set A together with a partial ordering R is called a
partially ordered set.
 Example
A = {1,2,3,4} and
R1 = {(1,1),(2,2),(3,3),(4,4)}
R2 = {(1,1),(1,2), (2,1), (2,2), (3,3),(4,4)}
R3={(1,1),(1,2), (1,3), (1,4), (2,2), (2,3),(2,4), (3,3),(3,4), (4,4)}

R1 is a partial order relation because you can see easily that the
relation is reflexive, anti-symmetric and reflexive

R2 is not anti-symmetric. Note that R2 is reflexive and transitive but

not anti-symmetric as (1,2) & (2,1)  R2 but 1  2; Hence not a
partial order relation.
R3 is a partial order relation you can easily see that it is reflexive
anti-symmetric and transitive
 Practice Question ... Do it Yourself
Let R be the set of real numbers and define the “less than or
equal to” , on R as follows:
for all real numbers x and y in R.
x  y  x < y or x = y
Show that  is a partial order relation
 Practice Question ... Do it Yourself
Let A be a non-empty set and P(A) the power set of A. Define
the “subset” relation, , as follows:
for all X,Y  P(A), X  Y   x, iff x  X then x  Y.
Show that  is a partial order relation
 Practice Question ... Do it Yourself

Let “|” be the “divides” relation on a set A of positive integers.

That is, for all a, b  A,
a|b  b = ka for some integer k.
Prove that | is a partial order relation on A.
 Practice Question ... Do it Yourself

Let “R” be the relation defined on the set of integers Z as follows:

for all a, b  Z, aRb  b=ar for some positive integer r.
Show that R is a partial order on Z.
 Summary
The topics we covered:
• Ordered Pairs
• Cartesian Product
• Relations
• Directed Graphs
• Matrix Representation of Relations
• Properties of Relations
• Partial Order Relations
• Practice Questions