Chapter 9: Relations

Done by: Dr. Raja’a Masa’deh

Information Technology Faculty
The World Islamic Sciences and Education University
 Relations
 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:

 In other words, a binary relation from A to B is a set R of ordered

pairs where the first element of each ordered pair comes from A
and the second element comes from B. We use the notation to
denote that and to denote that . Moreover, when belongs to , a is
said to be related to b by R.
 Example
Let and Then is a relation from A to B. This means, for instance, that ,
but that .

Displaying the Ordered Pairs in the Relation

R
 Relations on a Set
Relations from a set A to itself are of special interest.

Definition:
In other words, a relation on a set A is a subset of A
× A.

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

the relation ?

Soluti Because is in R if and only if a and b are positive integers

on: not exceeding 4 such that a divides b, we see that
 Example:
Consider these relations on the set of integers:

Which of these relations contain each of the pairs and ?

Soluti
on: The pair is in ;

is in ;

is in ;

is in ;

and finally, is in .
 Properties of Relations
In some relations an element is always related to itself. For instance, let
R be the relation on the set of all people consisting of pairs where x and
y have the same mother and the same father. Then for every person x.

Definition:

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

is reflexive if where the universe of discourse is the set of
all elements in A.

Example:
Consider the following relation on {1, 2, 3,
4}:
. Reflexive
𝑅 2={ ( 𝟏 , 𝟏 ) , ( 1, 2 ) , ( 2 ,1 ) , ( 3 , 4 ) , ( 4 ,1 ) , ( 4 , 4 ) } . Not reflexive
Example:
Consider the following relations on {1, 2, 3,
4}:

Which of these relations are reflexive?

Soluti  The relations because they both contain all pairs of the
on: form (a, a), namely, (1, 1), (2, 2), (3, 3), and (4, 4).
 In particular, because (3, 3) is not in any of these
relations.
Example:
Consider these relations on the set of integers:

Which of these relations are reflexive?

Soluti The reflexive relations are (because a ≤ a for every

on: integer a), , and . For each of the other relations in this
example it is easy to find a pair of the form (a, a) that is
not in the relation.
Definition:

Remark:
Using quantifiers, we see that the relation R on the set A is
symmetric if Similarly, the relation R on the set A is
antisymmetric if
 Example:
Consider the following relations on {1, 2, 3,
4}, which of these are antisymmetric?:

Soluti
on: is not antisymmetric because (1,2) belongs to R and
(2,1) belongs to R, but .
The relation

 The relation is not antisymmetric because (1,3) belongs to R and

(3,1) belongs to R, but .
 The relation is not antisymmetric because (1,2) belongs to R and
(2,1) belongs to R, but . And also (1,4) belongs to R and (4,1)
belongs to R, but
 The relation is antisymmetric because (1,1) belongs to R and (1,1)
belongs to R, thus
 Example:
Consider the following relations on {1, 2, 3,
4}:

Which of these relations are symmetric and which are

antisymmetric?

Soluti • The relations , because in each case . For , the only thing to
on: check is that both (2, 1) and (1, 2) are in the relation. For , 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

• . For each of these relations there is such that both (a, b) and (b, a)
belong to the relation. The reader should verify that none of the other
relations is antisymmetric. This is done by finding a pair (a, b) with a =
b such that (a, b) and (b, a) are both in the relation.

• The relations neither symmetric nor antisymmetric.

 Example:
Consider these relations on the set of integers:

Which of these relations are symmetric and which are

antisymmetric?
Soluti
on:

R3 is symmetric, for if a = b or a = −b, then b = a or b = −a.
The relations .

R4 is symmetric , because a = b implies that b = a.

R6 is symmetric, because a + b ≤ 3 implies that b + a ≤ 3.
 The relations .
R1 is antisymmetric because the inequalities a ≤ b and b ≤ a imply that

R2 is antisymmetric because it is impossible that a>b and b>a.

a = b.

R4 is antisymmetric, because two elements are related with respect to

R5 is antisymmetric because it is impossible that a = b + 1 and b = a +

R4 if and only if they are equal.
 Definition:

Remark:
Using quantifiers, we see that the relation R on a set A is
transitive if we have

Examp
le: { }
𝑹= ( 𝟏,𝟏) , ( 𝟏,𝟐) , ( 𝟏,𝟒 ) , ( 𝟐,𝟏) , ( 𝟐,𝟐) , ( 𝟐,𝟒 ) , ( 𝟑,𝟑) , ( 𝟒,𝟏) , ( 𝟒,𝟐 ) , ( 𝟒,𝟒 ) .
𝟏 ) ∧ (𝟏 , 𝟐)⟶ (𝟏 , 𝟐)
( 𝟐 ,(𝟏 𝟏 ),∧ (𝟏 , 𝟏)⟶ (𝟒 , 𝟐 (𝟏 ) ∧, (𝟐 𝟏) , 𝟏) ⟶ (𝟒
𝟏 ) ∧ (𝟏 , 𝟒) ⟶ 𝟒)
( 𝟐 , 𝟏 ) ∧ (𝟏 , 𝟐)⟶ (𝟒 , 𝟐 (𝟐 ) ∧, (𝟐 𝟐) , 𝟐) ⟶ (𝟒
𝟐 ) ∧ (𝟐 , 𝟏)⟶ (𝟏 , 𝟏)
( 𝟐 , 𝟏 ) ∧ (𝟏 , 𝟒)( 𝟒 ⟶ ,𝟐 (𝟐 ) ∧, (𝟐 𝟒) , 𝟒)⟶ ( 𝟒
𝟐 ) ∧ (𝟐 , 𝟐)⟶ (𝟏 , 𝟐) ( 𝟒 (𝟐 ,𝟒 ) ∧ (𝟒 , 𝟏)⟶ (𝟒
( 𝟐 , 𝟐 ) ∧(𝟐 , 𝟏)⟶ , 𝟏)
𝟒 ) ∧ (𝟒 , 𝟏)⟶ (( 𝟐 𝟏, ,𝟐𝟏) ) ∧(𝟐 , 𝟒) ⟶(𝟐 ( 𝟒 , 𝟒, 𝟒) ) ∧ (𝟒 , 𝟐)⟶ (𝟒
𝟒 ) ∧ (𝟒 , 𝟐)⟶ ( 𝟒 ,(𝟏 𝟏) ,∧ 𝟐) (𝟏 , 𝟏) ⟶ (𝟒 , 𝟏) Tran
𝟏 , 𝟒 ) ∧ (𝟒 , 𝟒)⟶ (𝟒 (𝟏, ,𝟏 𝟒)) ∧ (𝟏 , 𝟐) ⟶ (𝟒 , 𝟐) sitiv
( 𝟒 , 𝟏 ) ∧ (𝟏 , 𝟏) ⟶ (𝟒 , 𝟏) e
 Example:
Consider the following relations on {1, 2, 3,
4}:

Which of these relations are transitive?

Soluti
on:
. 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. The reader should verify that 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) belong to R3,
but (4, 2) does not.
 Example:
Consider these relations on the set of integers:

Which of these relations are transitive?

Soluti
on:
The relations . R1 is transitive because a ≤ b and b ≤ c imply that a ≤ c.
R2 is transitive because a>b and b>c imply that a>c. R3 is transitive
because a = ±b and b = ±c imply that a = ±c. R4 is clearly transitive, as
the reader should verify
because (2, 1) and (1, 0) belong to R5, but (2, 0) does not.
because (2, 1) and (1, 2) belong to R6, but (2, 2) does not.
 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:
Let . The relations and can be combined to obtain:
 Definition:

Example:
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 and S is the relation from {1, 2, 3, 4}
to {0, 1, 2} with

Soluti ( 𝟏 , 𝟏 ) ∧(𝟏 , 𝟎)⟶(𝟏 , 𝟎)

( 𝟑 , 𝟏 ) ∧(𝟏 , 𝟎)⟶(𝟑 , 𝟎)
on: ( 𝟏 , 𝟒 ) ∧(𝟒 , 𝟏)⟶(𝟏 ,𝟏)
( 𝟑 , 𝟒 ) ∧(𝟒 , 𝟏)⟶(𝟑 ,𝟏)
( 𝟐 , 𝟑 ) ∧(𝟑 , 𝟏)⟶ (𝟐 , 𝟏)
( 𝟐 , 𝟑 ) ∧(𝟑 , 𝟐)⟶ (𝟐 , 𝟐)

𝑺◦ 𝑹={(𝟏 , 𝟎),(𝟏 ,𝟏),(𝟐 , 𝟏), (𝟐 ,𝟐),(𝟑 , 𝟎),(𝟑 , 𝟏)}.

Definition:

The definition shows that ,and so on.

Example:
Let Find the powers

Because, we find that Furthermore, because ,Additional computation

shows that is the same as , so It also follows that for

𝑹={(𝟏 , 𝟏) ,(𝟐 , 𝟏) ,( 𝟑 ,𝟐) ,(𝟒 ,𝟑) }.

𝑹={(𝟏 , 𝟏) ,(𝟐 , 𝟏) ,( 𝟑 ,𝟐) ,(𝟒 ,𝟑) }.

𝑹={(𝟏 , 𝟏) ,(𝟐 , 𝟏) ,( 𝟑 ,𝟐) ,(𝟒 ,𝟑) }.

𝑹={(𝟏 , 𝟏) ,(𝟐 , 𝟏) ,( 𝟑 ,𝟐) ,(𝟒 ,𝟑) }.

 Representing Relations

 Representing Relations Using

Matrices
A relation between finite sets can be represented using a zero–one
matrix. Suppose that R is a relation from to (Here the elements of the
sets A and B have been listed in a particular, but arbitrary, order.
Furthermore, when we use the same ordering for A and B.) The relation R
can be represented by the matrix where
Example:
Suppose that and Let R be the relation from A to B containing . What is
the matrix representing R if ?

Soluti Because the matrix for R is

on: 1 2

𝟎 1 𝟎
𝑴 𝑹=
2 𝟏 𝟎
3 𝟏 𝟏

𝟎 𝟎
𝑴 𝑹=𝟏 𝟎
𝟏 𝟏
Example:

Let and Which ordered pairs are in the relation R represented by the
matrix:

𝒃
𝒃
𝒃𝒃
𝒃𝟏
𝟐
𝟑𝟒
𝟓
𝒂 𝟏
𝒂 𝟐
𝒂 𝟑

Soluti 𝑹={(𝒂𝟏,𝒃𝟐),(𝒂𝟐,𝒃𝟏),(𝒂𝟐,𝒃𝟑),(𝒂𝟐,𝒃𝟒),(𝒂𝟑 ,𝒃𝟏),(𝒂𝟑,𝒃𝟑),(𝒂𝟑,𝒃𝟓)}.

on:
Exercise:
Suppose that the relation R on a set is represented by the
matrix

Is R reflexive, symmetric, and/or antisymmetric?

Soluti Because all the diagonal elements of this matrix are equal to
on: 1, R is . Moreover, because MR is , it follows that R is
symmetric. It is also easy to see that R is because .
Example:
Suppose that the relations R1 and R2 on a set A are represented by the
matrices

What are the matrices representing ?

Soluti
on:
 Representing Relations Using
Digraphs

Example:
The directed graph with vertices a, b, c, and d, and edges (a, b), (a, d),
(b, b), (b, d), (c, a), (c, b), and (d, b) is displayed in the following figure.
Example:

The directed graph of the relation R = {(1, 1), (1, 3), (2, 1), (2, 3), (2,
4), (3, 1), (3, 2), (4, 1)} on the set {1, 2, 3, 4} is shown in Figure
 Exercises
 Represent each of these relations on {1, 2, 3, 4} with a matrix

 List the ordered pairs in the relations on {1, 2, 3} corresponding to

these matrices

 Let R be the relation represented by the

matrix

Find the matrices that represent:

a. . b. . c.