Discrete

Math:
Relations
 Cartesian products of sets
Definition : Given two non-empty sets A and B, the set of all
ordered pairs (x, y), where x ∈ A and y ∈ B is called Cartesian
product of A and B; symbolically, we write

A × B = {(x, y) | x ∈ A and y ∈ B}

If A = {1, 2, 3} and B = {4, 5}, then

A × B = {(1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5)} and
B × A = {(4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3)}
(i) Two ordered pairs are equal, if and only if the
corresponding first elements are equal and the
second elements are also equal, i.e. (x, y) = (u, v)
if and only if x = u, y = v.

(ii) If n(A) = p and n (B) = q, then n (A × B) = p × q.

(iii) A × A × A = {(a, b, c) : a, b, c ∈ A}. Here (a, b, c) is

called an ordered triplet
 Relations

• A Relation R from a non-empty set A to a non empty set

B is a subset of the Cartesian product set A × B. The
subset is derived by describing a relationship between
the first element and the second element of the ordered
pairs in A × B. The set of all first elements in a relation
R, is called the domain of the relation R, and the set of
all second elements called images, is called the range
of R.
• (i) A relation may be represented either by the
Roster form or by the set builder form, or by an
arrow diagram which is a visual representation of a
relation.

• (ii) If n(A) = p, n(B) = q; then the n(A × B) = pq.

• Given (x,y) in A X B,

(x R y) ↔ (x,y)  R.
x is related to y by R
 Example
If A = {2, 4, 6, 9} and B = {4, 6, 18, 27, 54}, a ∈ A, b ∈ B, find the
set of ordered pairs such that 'a' is factor of 'b' and a < b.
• Solution

Since A = {2, 4, 6, 9} B = {4, 6, 18, 27, 54}, we have to find a set of ordered pairs (a, b)
such that a is factor of b and a < b. Since 2 is a factor of 4 and 2 < 4. So (2, 4) is one
such ordered pair. Similarly, (2, 6), (2, 18), (2, 54) are other such ordered pairs. Thus
the required set of ordered pairs is {(2, 4), (2, 6), (2, 18), (2, 54), (6, 18), (6, 54,), (9,
18), (9, 27), (9, 54)}.
R = {(1,1), (1,3), (2,2)}
 Example

• Find the domain and range of the relation R given by

R = {(x, y) : y = x +6/ x ; where x, y ∈ N and x < 6}.

If x=1, y = 7; if x = 2, y=5; if x=3, y=5; if x=4, y=1.5; if x=5, y=5

6/5.

Thus R = {(1, 7), (2, 5), (3, 5)}, where Domain of R = {1, 2, 3}
Range of R = {7, 5}
Inverse of a Relation
• Another convenient way to represent a relation is to use a
matrix representation. Take a binary relation R from the
set A = {a1,...,am} to the set B = {b1,b2,...,bn}. Create a
matrix whose rows are indexed by the elements of A (thus
m rows) and whose columns are indexed by the elements
of B (thus n columns). Now the entry (i, j) of the matrix,
corresponding to the ith row and jth column, contains aiRbj,
that is, a truth value (True or False, 1 or 0), depending on
whether it is true or not that aiRbj (that is, ai is related to
bj).
• Take A = {2,3,4}, B = {2,6,8} and the relation R defined by
(x,y) ∈ R ↔ x divides y. Then the rows of the matrix are
indexed by 2,3,4, and the columns by 2,6,8.
Matrix Representation
 Properties of Relations

• There are several properties that are used to classify

relations on a set. We will introduce the most important of
these here.
 Reflexive
• A relation R on a set A is called reflexive if (a, a)  R for
every element a  A.
• Using quantifiers we see that the relation R on the set A is
reflexive if a((a, a)  R), where the universe of discourse
is the set of all elements in A.
• We see that a relation on A is reflexive if every element of A
is related to itself.
 EXAMPLE
• Consider the following relations on {l, 2, 3, 4}:
R1 = {(1, 1), (1,2),(2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1,4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 = {(1, 1), (1, 2), (1, 3), (1,4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4,
4)}
R6 = {(3, 4)}
• Solution:
The relations R3 and R5 are reflexive because they both
contain all pairs of the form (a, a), namely, (1, 1), (2, 2),
(3, 3), and (4, 4). The other relations are not reflexive
because they do not contain all of these ordered pairs. In
particular, R 1, R2, R4, and R6 are not reflexive because (3,
3) is not in any of these relations.
• The digraph(directed graph) of a reflexive relation
includes an arrow from every vertex to the vertex
itself(i.e., a loop)
• On the matrix representation of R, reflexivity is shown by
having T (true) or 1 on the main diagonal of the matrix.
 Symmetric
• A relation R on a set A is called symmetric if (b, a)  R
whenever (a, b)  R, for all a, b  A. A relation R on a set
A such that for all a, b  A, if(a, b)  R and (b, a)  R,
then a = b is called antisymmetric.

is symmetric if a  b((a, b)  R → (b, a)  R). Similarly,

• Using quantifiers, we see that the relation R on the set A

b)  R /\ (b, a)  R) → (a = b)).
the relation R on the set A is antisymmetric if a  b ((a,
• That is, a relation is symmetric if and only if a is related to
b implies that b is related to a.
• A relation is anti symmetric if and only if there are no pairs
of distinct elements a and b with a related to b and b
related to a. That is, the only way to have a related to b
and b related to a is for a and b to be the same element.
The terms symmetric and antisymmetric are NOT
opposites.
• A relation can be both symmetric and antisymmetric.
• A relation can be neither symmetric nor antisymmetric.
• Consider the following relations on {l, 2, 3, 4}:
R1 = {(1, 1), (1,2),(2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1,4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 = {(1, 1), (1, 2), (1, 3), (1,4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4,
4)}
R6 = {(3, 4)}
• Solution: The relations R2 and R3 are symmetric, because in
each case (b, a) belongs to the relation whenever (a, b) does.
For R2, the only thing to check is that both (2, 1) and (1,2) are
in the relation. For R3, it is necessary to check that both (1,2)
and (2, 1) belong to the relation, and (1, 4) and (4, 1) belong to
the relation.
• R4, R5, and R6 are all antisymmetric. For each of these
relations there is no pair of elements a and b with a b such
that both (a, b) and (b, a) belong to the relation.
 Transitive
• A relation R on a set A is called transitive if whenever (a, b) 
R and (b, c)  R, then (a, c)  R, for all a, b, c  A.
• Remark: Using quantifiers we see that the relation R on a set

abc((a, b)  R /\ (b, c)  R) → (a, c)  R).

A is transitive if we have
• Consider the following relations on {l, 2, 3, 4}:
R1 = {(1, 1), (1,2),(2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1,4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 = {(1, 1), (1, 2), (1, 3), (1,4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4,
4)}
R6 = {(3, 4)}
• Solution: R4, R5, and R6 are transitive. For each of these
relations, we can show that it is transitive by verifying that if
(a, b) and (b, c) belong to this relation, then (a, c) also does.
For instance, R4 is transitive, because (3, 2) and (2, 1), (4, 2)
and (2, 1), (4, 3) and (3, 1), and (4, 3) and (3, 2) are the only
such sets of pairs, and (3, 1), (4, 1), and (4, 2) belong to R4
• R5 and R6 are transitive. R1 is not transitive because (3, 4)
and (4, 1) belong to R1, but (3, 1) does not.
• R2 is not transitive because (2, 1) and (1, 2) belong to R2, but
(2, 2) does not. R3 is not transitive because (4, 1) and (1, 2)
Informal definitions:
• Reflexive: Each element is related to itself.
• Symmetric: If any one element is related to any other
element, then the second element is related to the first.
• Transitive: If any one element is related to a second and
that second element is related to a third, then the first
element is related to the third.
 Example1
• set {1, 2, 3, 4}
• R = {(2, 2),(2, 3),(2, 4),(3, 2),(3, 3),(3, 4)}

• Not reflexive because we do not have (1, 1), (3, 3), and (4, 4).
• Not symmetric because while we have (3, 4), we do not have (4, 3).
• Not antisymmetric because we have both (2, 3) and (3, 2).
• Transitive
 Example2

set {1, 2, 3, 4}
{(1, 1),(1, 2),(2, 1),(2, 2),(3, 3),(4, 4)}

• Reflexive because (a, a) is in the relation for all a = 1, 2, 3, 4.

• Symmetric because for every (a, b), we have a (b, a).
• Not antisymmetric because we have (1, 2) and (2, 1).
• Transitive because while we have (1, 2) and (2, 1), we also
have (1, 1) and (2, 2) in the relation.
 Example3

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

• Not reflexive because we do not have (a, a) for all a = 1, 2, 3, 4.

• Symmetric because for every (a, b), we have a (b, a).
• Not antisymmetric because we have both (2, 4) and (4, 2).
• Not transitive because we are missing (2, 2) and (4, 4).
 Example4
set {1, 2, 3, 4}
R = {(1, 2),(2, 3),(3, 4)}

• Not reflexive because we do not have (a, a) for all a = 1, 2, 3, 4.

• Not symmetric because we do not have (2, 1),(3, 2), and (4, 3).
• Antisymmetric because for every (a, b), we do not have a (b, a).
• Not transitive because we do not have (1, 3) for (1, 2) and (2, 3).
 Example5
set {1, 2, 3, 4}
R = {(1, 1),(2, 2),(3, 3),(4, 4)}

• Reflexive because we have (a, a) for every a = 1, 2, 3, 4.

• Symmetric because we do not have a case where (a, b) and
a ≠ b.
• Antisymmetric because we do not have a case where (a, b)
and a ≠ b.
• Transitive because we can satisfy (a, b) and (b, c) when a =
b = c.
 Example6
set {1, 2, 3, 4}
R = {(1, 3),(1, 4),(2, 3),(2, 4),(3, 1),(3, 4)}

• Not reflexive because we do not have (a, a) for all a = 1, 2, 3, 4.

• Not symmetric because the relation does not contain (4, 1), (3,
2), (4, 2), and (4, 3).
• Not antisymmetric because we have (1, 3) and (3, 1).
• Not transitive because we do not have (2, 1) for (2, 3) and (3,
1).
 Combining Relations
• Because relations from A to B are subsets of A x B, two
relations from A to B can be combined in any way two sets
can be combined.
• EXAMPLE: Let A = {1, 2, 3} and B = {1, 2, 3, 4}. The
relations R1 = {(1, 1), (2, 2), (3,3)} and R2 = {(1, 1), (1, 2), (1,
3), (1, 4)}

• R1 U R2 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3)}
• R1  R2 = {(1, 1)}
• R1 - R2 = {(2, 2), (3, 3)}
• Suppose that the relations R1 and R2 on a set A are
represented by the matrices

• What are the matrices representing R1 U R2 and R1  R2

• Solution: The matrices of these relations are
Composition of Relations
• Find the matrix representing the relations S o R, where the
matrices representing R and S are

Boolean Product
 Exercise1

• List the ordered pairs in the relation R from A = {0, 1,2,3,

4} to B = {0, 1, 2, 3}, where (a, b)  R if and only if

a) a = b
b) a +b = 4.
c) a > b
d) gcd(a, b) = 1
 Exercise2

• Let R1 = {(1, 2), (2, 3), (3, 4)} and

R2 = {(1, 1), (1,2), (2, 1), (2,2), (2,3), (3, 1), (3,2), (3,3), (3,
4)}
be relations from {1, 2, 3} to {1, 2, 3, 4}.
Find
a) R1 U R2
b) R1  R2
c) R1 - R2
d) R - R
 Exercise3

• Let R be the relation {(1, 2), (1, 3), (2, 3), (2, 4), (3, 1)},
and let S be the relation {(2, 1), (3, 1), (3, 2), (4, 2)}. Find
S o R.
 Exercise4

• Represent each of these relations on {I, 2, 3} with a matrix

(with the elements of this set listed in increasing order).
a) {(1, 1), (1, 2), (1, 3)}
b) {(1, 2), (2,1), (2,2 ), (3, 3)}
c) {(1, 1), (1,2 ), (1, 3), (2,2 ), (2, 3), (3, 3)}
d) {(1, 3), (3, 1)}
 Exercise5

• List the ordered pairs in the relations on {1, 2, 3}

corresponding to these matrices (where the rows and
columns correspond to the integers listed in increasing
order).
 Exercise6

• Let R1 and R2 be relations on a set A represented by the

matrices

• Find the matrices that represent

a. R1 U R2 b. R1  R2
c. R1 0 R2
 Exercise7

• List the ordered pairs in the relations represented by the

directed graph.

1 2