CHAPTER 5

RELATIONS

In discrete mathematics, relations are fun-

1 Relations and Their Properties 88
damental structures that capture the con-
2 n-ary Relations and Their Ap-
nections between elements of a set or across
plications . . . . . . . . . . . 95
multiple sets. A relation is formally defined
3 Representing Relations . . . . 95
as a subset of the Cartesian product of two
4 Closures of Relations . . . . . 95
sets, representing how elements are paired
5 Equivalence Relations . . . . . 95
or associated with one another. Key types
6 Partial Orderings . . . . . . . 95
of relations include equivalence relations,
which partition a set into disjoint equiva-
lence classes based on a notion of similarity,
and partial orders, which impose a hierarchy
among elements. These concepts form the
basis for many advanced topics in discrete
mathematics, such as graph theory, com-
binatorics, and logic, and have widespread
applications in computer science, including
database design and algorithm development.
Understanding relations not only enhances
our theoretical insights but also provides
powerful tools for modeling and solving real-
world problems.

87
88 Relations

1 Relations and Their Properties

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.

Definition 1.1: Binary Relation

Let A and B be sets.

• A binary relation R from A to B is a subset of A → B.

• Mathematically, R ↑ A → B, where

A → B = {(a, b) | a ↓ A ↔ b ↓ B}

denotes
• a R b ↗↗↗↗↘ (a, b) ↓ R

• a R b is read: a is related to b by R.
denotes
• a ≃ R b ↗↗↗↗↘ (a, b) ↓
/R

Example 1.1:
Let A = {0, 1, 2} and B = {a, b}. Then

R = {(0, a), (0, b), (1, a), (2, b)}

is a relation from A to B. This means, for instance, that 0 R a, but that 1 ≃ R b. ↭

Remark.
Relations can be represented graphically, as shown in Figure 5.1,
using arrows to represent ordered pairs. Another way to represent this relation is
to use a table, which is also done in Figure 5.1.

Figure 5.1: A graph and a table illustrating a relation.

Dr. Mahmoud Khalaf BES 114

Relations 89

1.1 Functions as Relations

• Functions:
f :A↘B
assigns exactly one element of B to each element of A.

• The graph of f is the set of ordered pairs (a, b) such that

b = f (a), f ↑ A → B.

Therefore, f is a relation from A to B.

Di!erence between relation and function:

• A relation can be used to express a one-to-many relationship between the elements of

the sets A and B, where an element of A may be related to more than one element of
B.

• A function represents a relation where exactly one element of B is related to each

element of A.

• Relations are a generalization of graphs of functions

1.2 Relations on a Set

Definition 1.2: Relation on a Set

A relation on a set A is a relation from A to A.

• A binary relation R from A to A is a subset of A → A.

• Mathematically, R ↑ A → A, where

A → A = {(a, b) | a ↓ A ↔ b ↓ A}

Example 1.2:
Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation

R = {(a, b) | a divides b} ?

↭
Solution. To determine the ordered pairs in R, we check all pairs (a, b) where a divides b.
The relation R is:

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

Example 1.3:

Dr. Mahmoud Khalaf BES 114

90 Relations

Figure 5.2: A graph and a table illustrating a relation.

Consider these relations on the set of integers:

R1 = {(a, b) | a ⇐ b},
R2 = {(a, b) | a > b},
R3 = {(a, b) | a = b or a = ↗b},
R4 = {(a, b) | a = b},
R5 = {(a, b) | a = b + 1},
R6 = {(a, b) | a + b ⇐ 3}.

Which of these relations contain each of the pairs (1, 1), (1, 2), (2, 1), (1, ↗1), and (2, 2)?
↭
Solution. We analyze each pair and determine which relations it belongs to:

• Pair (1, 1):

– R1 : 1 ⇐ 1 is true. – R3 : 1 = 1 is true. – R5 : 1 = 1 + 1 is false.

– R2 : 1 > 1 is false. – R4 : 1 = 1 is true. – R6 : 1 + 1 = 2 ⇐ 3 is true.

Thus, (1, 1) belongs to R1 , R3 , R4 , R6 .

• Pair (1, 2):

– R1 : 1 ⇐ 2 is true. – R4 : 1 = 2 is false.
– R2 : 1 > 2 is false. – R5 : 1 = 2 + 1 is false.
– R3 : 1 = 2 or 1 = ↗2 is false. – R6 : 1 + 2 = 3 ⇐ 3 is true.

Thus, (1, 2) belongs to R1 , R6 .

• Pair (2, 1):

– R1 : 2 ⇐ 1 is false. – R3 : 2 = 1 or 2 = ↗1 is false.
– R2 : 2 > 1 is true. – R4 : 2 = 1 is false.

Dr. Mahmoud Khalaf BES 114

Relations 91

– R5 : 2 = 1 + 1 is true. – R6 : 2 + 1 = 3 ⇐ 3 is true.

Thus, (2, 1) belongs to R2 , R5 , R6 .

• Pair (1, ↗1):

– R1 : 1 ⇐ ↗1 is false. – R4 : 1 = ↗1 is false.
– R2 : 1 > ↗1 is true. – R5 : 1 = ↗1 + 1 is true.
– R3 : 1 = ↗1 or 1 = ↗(↗1) is true. – R6 : 1 + (↗1) = 0 ⇐ 3 is true.

Thus, (1, ↗1) belongs to R2 , R3 , R5 , R6 .

• Pair (2, 2):

– R1 : 2 ⇐ 2 is true. – R4 : 2 = 2 is true.
– R2 : 2 > 2 is false. – R5 : 2 = 2 + 1 is false.
– R3 : 2 = 2 or 2 = ↗2 is true. – R6 : 2 + 2 = 4 ⇐ 3 is false.

Thus, (2, 2) belongs to R1 , R3 , R4 .

Example 1.4:
How many relations are there on a set with n elements? ↭
Solution.

• If |A| = n elements, then A → A = n → n = n2 elements.

• The number of possible subsets of |A → A| is equal to the number of elements in the

power set of A → A. The power set of a set with m elements has 2m subsets.

• Since A → A = n2 elements, the number of relations on A is:

2
2n .

2
Conclusion: The number of relations on a set with n elements is 2n .

1.3 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.

Definition 1.3: Reflexive Relation

A relation R on a set A is called reflexive if (a, a) ↓ R for every element a ↓ A.

Dr. Mahmoud Khalaf BES 114

92 Relations

Example 1.5:
Consider the following relations on {1, 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)}.

Which of these relations are reflexive? ↭

Solution. Let A = {1, 2, 3, 4}. For a relation to be reflexive, it must contain all pairs
(1, 1), (2, 2), (3, 3), (4, 4).
We check each relation:
R1 : Missing (3, 3). Not reflexive (Irreflexive).
R2 : Missing (2, 2), (3, 3), (4, 4). Not reflexive.
R3 : Contains (1, 1), (2, 2), (3, 3), (4, 4). Reflexive.
R4 : Missing (1, 1), (2, 2), (3, 3), (4, 4). Not reflexive.
R5 : Contains (1, 1), (2, 2), (3, 3), (4, 4). Reflexive.
R6 : Missing (1, 1), (2, 2), (3, 3), (4, 4). Not reflexive.

Thus, the reflexive relations are R3 and R5 .

Example 1.6:
Consider the relations on the set of integers in Example 1.3. Which of the relations are
reflexive? ↭
Solution. A relation R on a set is reflexive if every element is related to itself, i.e., (a, a) ↓ R
for all a in the set.
We analyze each relation:

R1 = {(a, b) | a ⇐ b} : Reflexive, since a ⇐ a for all integers a.

R2 = {(a, b) | a > b} : Not reflexive, since a > a is false for all integers a.
R3 = {(a, b) | a = b or a = ↗b} : Reflexive, since a = a for all integers a.
R4 = {(a, b) | a = b} : Reflexive, since a = a for all integers a.
R5 = {(a, b) | a = b + 1} : Not reflexive, since a = a + 1 is false for all integers a.
R6 = {(a, b) | a + b ⇐ 3} : Not reflexive, since a + a ⇐ 3 is not true for all integers a.

Thus, the reflexive relations are R1 , R3 , and R4 .

Example 1.7:
Is the “divides” relation on the set of positive integers reflexive? ↭
Solution: For the “divides” relation, this means that for every positive integer a, a must
divide a.

Dr. Mahmoud Khalaf BES 114

Relations 93

Since any positive integer a divides itself (i.e., a | a is always true), the “divides” relation is
reflexive on the set of positive integers.

Definition 1.4: Symmetric/Antisymmetric Relation

• A relation R on a set A is called symmetric if (a, b) ↓ R, then (b, a) ↓ R for
all a, b ↓ A.

• A relation R on a set A is called not symmetric if (a, b) ↓ R, then (b, a) ↓

/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.

Remark.
For the condition of the antisymmetric relation is equivalent to the following condition:

If (a, b) ↓ R and a ≃= b, then (b, a) ↓

/R

This statement is the contrapositive of the standard statement in the definition.

Example 1.8:
Which of the relations from Example 1.5 are symmetric and which are antisymmetric?
↭
Solution. Let’s analyze each relation:

• R1 :

– Not symmetric because (3, 4) ↓ R1 but (4, 3) ↓

/ R1 .
– Not antisymmetric because (1, 2) ↓ R1 and (2, 1) ↓ R1 , but 1 ≃= 2.

• R2 :

– Symmetric because (1, 2) ↓ R2 and (2, 1) ↓ R2 .

– Not antisymmetric because (1, 2) ↓ R2 and (2, 1) ↓ R2 , but 1 ≃= 2.

• R3 :

– Symmetric because for every (a, b) ↓ R3 , (b, a) ↓ R3 .

– Not antisymmetric because (1, 2) ↓ R3 and (2, 1) ↓ R3 , but 1 ≃= 2.

• R4 :

– Not symmetric because (2, 1) ↓ R4 but (1, 2) ↓

/ R4 .
– Antisymmetric because there are no pairs (a, b) and (b, a) in R4 with a ≃= b.

Dr. Mahmoud Khalaf BES 114

94 Relations

• R5 :
– Not symmetric because (1, 2) ↓ R5 but (2, 1) ↓
/ R5 .
– Antisymmetric because for any (a, b) ↓ R5 and (b, a) ↓ R5 , it must be that
a = b.
• R6 :
– Not symmetric because (3, 4) ↓ R6 but (4, 3) ↓
/ R6 .
– Antisymmetric because there are no pairs (a, b) and (b, a) in R6 with a ≃= b.
Summary:
• Symmetric relations: R2 , R3 .
• Antisymmetric relations: R4 , R5 , R6 .
Example 1.9:
Which of the relations from Example 1.3 are symmetric and which are antisymmetric?
↭
Solution. We analyze each relation for symmetry and antisymmetry.

1. R1 = {(a, b) | a ⇐ b},

• Symmetry:
Let (a, b) ↓ R1 =⇒ a ⇐ b.
=⇒ But b ⊋ a (unless a = b).
=⇒ (b, a) ↓
/ R1 .
=⇒ R1 is not symmetric.

• Antisymmetry:
Let (a, b) ↓ R1 and (b, a) ↓ R1 =⇒ a ⇐ b and b ⇐ a.
=⇒ a = b.
=⇒ R1 is antisymmetric.

2. R2 = {(a, b) | a > b},

• Symmetry:
Let (a, b) ↓ R2 =⇒ a > b.
=⇒ But b ≃> a.
=⇒ (b, a) ↓
/ R2 .
=⇒ R2 is not symmetric.

Dr. Mahmoud Khalaf BES 114

Relations 95

• Antisymmetry:

Let (a, b) ↓ R2 and (b, a) ↓ R2 =⇒ a > b and b > a.

=⇒ This is impossible unless a = b.
=⇒ R2 is antisymmetric.

3. R3 = {(a, b) | a = b or a = ↗b},

• Symmetry:

Let (a, b) ↓ R3 =⇒ a = b or a = ↗b.

=⇒ b = a or b = ↗a.
=⇒ (b, a) ↓ R3 .
=⇒ R3 is symmetric.

• Antisymmetry:

Let (a, b) ↓ R3 and (b, a) ↓ R3 =⇒ (a = b or a = ↗b) and (b = a or b = ↗a).

=⇒ If a ≃= b, then a = ↗b and b = ↗a, which is possible.
=⇒ R3 is not antisymmetric.

4. R4 = {(a, b) | a = b},

• Symmetry:

Let (a, b) ↓ R4 =⇒ a = b.
=⇒ b = a.
=⇒ (b, a) ↓ R4 .
=⇒ R4 is symmetric.

• Antisymmetry:

Let (a, b) ↓ R4 and (b, a) ↓ R4 =⇒ a = b and b = a.

=⇒ a = b.
=⇒ R4 is antisymmetric.

5. R5 = {(a, b) | a = b + 1},

Dr. Mahmoud Khalaf BES 114

96 Relations

• Symmetry:
Let (a, b) ↓ R5 =⇒ a = b + 1.
=⇒ b = a ↗ 1 ≃= a + 1.
=⇒ (b, a) ↓
/ R5 .
=⇒ R5 is not symmetric.

• Antisymmetry:
Let (a, b) ↓ R5 and (b, a) ↓ R5 =⇒ a = b + 1 and b = a + 1.
=⇒ This is impossible unless a = b + 1 and b = a + 1,
which cannot hold simultaneously.
=⇒ R5 is antisymmetric.

6. R6 = {(a, b) | a + b ⇐ 3}.

• Symmetry:
Let (a, b) ↓ R6 =⇒ a + b ⇐ 3.
=⇒ b + a ⇐ 3.
=⇒ (b, a) ↓ R6 .
=⇒ R6 is symmetric.

• Antisymmetry:
Let (a, b) ↓ R6 and (b, a) ↓ R6 =⇒ a + b ⇐ 3 and b + a ⇐ 3.
=⇒ This does not imply a = b.
=⇒ R6 is not antisymmetric.
Example 1.10:
Is the “divides” relation on the set of positive integers symmetric? Is it antisymmetric?
↭
Solution. Let R be the “divides” relation on the set of positive integers, defined as:
R = {(a, b) | a divides b}.
• Not symmetric:
Counterexample: Consider the example a = 2 and b = 4. Since 2 divides 4, (2, 4) ↓
R. However, 4 does not divide 2, so (4, 2) ↓
/ R. Therefore, R is not symmetric.
• Antisymmetric:

Suppose (a, b) ↓ R and (b, a) ↓ R =⇒ a divides b and b divides a.

=⇒ a = b.
=⇒ R is antisymmetric.

Dr. Mahmoud Khalaf BES 114

Relations 97

Definition 1.5: Transitive Relation

• 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.

• A relation R on a set A is called not transitive if whenever (a, b) ↓ R and

(b, c) ↓ R, then (a, c) ↓
/ R, for all a, b, c ↓ A.

Example 1.11:
Which of the relations from Example 1.5 are transitive? ↭
Solution. We check each relation for transitivity. A relation R is transitive if whenever
(a, b) ↓ R and (b, c) ↓ R, then (a, c) ↓ R.
1. R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}:
Consider (3, 4) ↓ R1 and (4, 1) ↓ R1 =⇒ (3, 1) should be in R1 .
=⇒ (3, 1) ↓
/ R1 .
=⇒ R1 is not transitive.
2. R2 = {(1, 1), (1, 2), (2, 1)}:
Consider (1, 2) ↓ R2 and (2, 1) ↓ R2 =⇒ (1, 1) should be in R2 .
=⇒ (1, 1) ↓ R2 .
Also, (2, 1) ↓ R2 and (1, 2) ↓ R2 =⇒ (2, 2) should be in R2 .
=⇒ (2, 2) ↓
/ R2 .
=⇒ R2 is not transitive.
3. R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}:
Consider (1, 2) ↓ R3 and (2, 1) ↓ R3 =⇒ (1, 1) should be in R3 .
=⇒ (1, 1) ↓ R3 .
Also, (1, 4) ↓ R3 and (4, 1) ↓ R3 =⇒ (1, 1) should be in R3 .
=⇒ (1, 1) ↓ R3 .
=⇒ R3 is transitive.
4. R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}:
Consider (3, 2) ↓ R4 and (2, 1) ↓ R4 =⇒ (3, 1) should be in R4 .
=⇒ (3, 1) ↓ R4 .
Also, (4, 2) ↓ R4 and (2, 1) ↓ R4 =⇒ (4, 1) should be in R4 .
=⇒ (4, 1) ↓ R4 .
=⇒ R4 is transitive.
5. R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}:
For all (a, b) ↓ R5 and (b, c) ↓ R5 , =⇒ (a, c) ↓ R5 .
=⇒ R5 is transitive.

Dr. Mahmoud Khalaf BES 114

98 Relations

6. R6 = {(3, 4)}:

There are no pairs (a, b) and (b, c) in R6 .

=⇒ R6 is transitive.

Example 1.12:
Which of the relations from Example 1.3 are transitive? ↭
Solution. We analyze each relation for transitivity.
1. R1 = {(a, b) | a ⇐ b}:

Let (a, b) ↓ R1 and (b, c) ↓ R1 =⇒ a ⇐ b and b ⇐ c.

=⇒ a ⇐ c.
=⇒ (a, c) ↓ R1 .
=⇒ R1 is transitive.

2. R2 = {(a, b) | a > b}:

Let (a, b) ↓ R2 and (b, c) ↓ R2 =⇒ a > b and b > c.

=⇒ a > c.
=⇒ (a, c) ↓ R2 .
=⇒ R2 is transitive.

3. R3 = {(a, b) | a = b or a = ↗b}:

Let (a, b) ↓ R3 and (b, c) ↓ R3 =⇒ (a = b or a = ↗b) and (b = c or b = ↗c).

=⇒ If a = b and b = c, then a = c.
=⇒ If a = ↗b and b = ↗c, then a = c.
=⇒ (a, c) ↓ R3 .
=⇒ R3 is transitive.

4. R4 = {(a, b) | a = b}:

Let (a, b) ↓ R4 and (b, c) ↓ R4 =⇒ a = b and b = c.

=⇒ a = c.
=⇒ (a, c) ↓ R4 .
=⇒ R4 is transitive.

5. R5 = {(a, b) | a = b + 1}:

Let (a, b) ↓ R5 and (b, c) ↓ R5 =⇒ a = b + 1 and b = c + 1.

=⇒ a = (c + 1) + 1 = c + 2.
=⇒ (a, c) ↓
/ R5 .
=⇒ R5 is not transitive.

Dr. Mahmoud Khalaf BES 114

Relations 99

6. R6 = {(a, b) | a + b ⇐ 3}:
Let (a, b) ↓ R6 and (b, c) ↓ R6 =⇒ a + b ⇐ 3 and b + c ⇐ 3.
=⇒ This does not guarantee a + c ⇐ 3.
=⇒ R6 is not transitive.

Example 1.13:
Is the “divides” relation on the set of positive integers transitive? ↭
Solution.
Let (a, b) ↓ R and (b, c) ↓ R =⇒ a divides b and b divides c.
=⇒ a divides c.
=⇒ (a, c) ↓ R.
=⇒ R is transitive.

Example 1.14:
How many reflexive relations are there on a set with n elements? ↭
Solution.
1. For a set A with n elements, the total number of possible ordered pairs in A → A is n2 .
2. Since R must contain all n pairs of the form (a, a), these are fixed.
3. The remaining n2 ↗ n pairs (where the first and second elements are distinct) can be
included or excluded freely.
4. Each of these n2 ↗ n pairs has 2 choices: either included in R or not.
5. Therefore, the total number of reflexive relations is:
2 →n
2n .

1.4 Combining Relations

Because relations from A to B are subsets of A → B, two relations from A to B can be
combined in any way two sets can be combined.
Example 1.15:
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)} can be combined to obtain

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

R1 ⇓ R2 = {(1, 1)},
R1 ↗ R2 = {(2, 2), (3, 3)},
R2 ↗ R1 = {(1, 2), (1, 3), (1, 4)}.
↭

Dr. Mahmoud Khalaf BES 114

100 Relations

Example 1.16:
Let R1 = {(x, y) | x < y} and R2 = {(x, y) | x > y}. What are R1 ⇑ R2 , R1 ⇓ R2 , R1 ↗ R2 ,
R2 ↗ R1 , and R1 ⇔ R2 ? ↭
Solution: We analyze each operation step by step.
1.

R1 ⇑ R2 = {(x, y) | x < y} ⇑ {(x, y) | x > y}

= {(x, y) | x < y or x > y}
= {(x, y) | x ≃= y}.

2.

R1 ⇓ R2 = {(x, y) | x < y} ⇓ {(x, y) | x > y}

= ↖.

3.

R1 ↗ R2 = {(x, y) | x < y} ↗ {(x, y) | x > y}

= {(x, y) | x < y}.

4.

R2 ↗ R1 = {(x, y) | x > y} ↗ {(x, y) | x < y}

= {(x, y) | x > y}.

5.

R1 ⇔ R2 = (R1 ⇑ R2 ) ↗ (R1 ⇓ R2 )
= {(x, y) | x ≃= y} ↗ ↖
= {(x, y) | x ≃= y}.

Definition 1.6: Composite of Relations

Let R be a relation from a set A to a set B, and S a relation from B to a set C.

• The composite of R and S is the relation consisting of ordered pairs (a, c), where
a ↓ A, c ↓ C,

• There exists an element b ↓ B such that (a, b) ↓ R and (b, c) ↓ S.

• Mathematically,

S ↙ R = {(a, c) | there exists b such that (a, b) ↓ R and (b, c) ↓ S}.

• We denote the composite of R and S by S ↙ R.

Dr. Mahmoud Khalaf BES 114

Relations 101

Example 1.17:
What is the composite of the relations R and S, where R is the relation from {1, 2, 3} to
{1, 2, 3, 4} with
R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)},
and S is the relation from {1, 2, 3, 4} to {0, 1, 2} with

S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}?

↭
Solution:
We compute S ↙ R step by step:
1. For (1, 1) ↓ R:

(1, 1) ↓ R and (1, 0) ↓ S =⇒ (1, 0) ↓ S ↙ R.

2. For (1, 4) ↓ R:

(1, 4) ↓ R and (4, 1) ↓ S =⇒ (1, 1) ↓ S ↙ R.

3. For (2, 3) ↓ R:

(2, 3) ↓ R and (3, 1) ↓ S =⇒ (2, 1) ↓ S ↙ R.

(2, 3) ↓ R and (3, 2) ↓ S =⇒ (2, 2) ↓ S ↙ R.

4. For (3, 1) ↓ R:

(3, 1) ↓ R and (1, 0) ↓ S =⇒ (3, 0) ↓ S ↙ R.

5. For (3, 4) ↓ R:

(3, 4) ↓ R and (4, 1) ↓ S =⇒ (3, 1) ↓ S ↙ R.

Conclusion: (Written in Exam Directly) The composite relation S ↙ R is:

S ↙ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}.

Definition 1.7: Powers of Relation

Let R be a relation on the set A. The powers Rn , n = 1, 2, 3, . . ., are defined recursively
by
R1 = R and Rn+1 = Rn ↙ R.
The definition shows that R2 = R ↙ R, R3 = R2 ↙ R = (R ↙ R) ↙ R, and so on.

Example 1.18:
Let R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Find the powers Rn , n = 2, 3, 4, . . .. ↭
Solution: For n = 2, 3, 4, . . ., we compute Rn as follows:

Dr. Mahmoud Khalaf BES 114

102 Relations

1. R2 = R ↙ R:

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

2. R3 = R2 ↙ R:

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

3. R4 = R3 ↙ R:

R4 = {(1, 1), (2, 1), (3, 2), (4, 3)} ↙ {(1, 1), (2, 1), (3, 1), (4, 1)}
= {(1, 1), (2, 1), (3, 1), (4, 1)}.

4. For n ∝ 3, Rn = R3 :

Rn = {(1, 1), (2, 1), (3, 1), (4, 1)}.

Conclusion: The powers of R are:

R2 = {(1, 1), (2, 1), (3, 1), (4, 2)}, R3 = {(1, 1), (2, 1), (3, 1), (4, 1)}, Rn = R3 for n ∝ 3.

Dr. Mahmoud Khalaf BES 114