Chapter 9

Chapter Summary
 Relations and Their Properties
 Representing Relations
 Equivalence Relations
 Partial Orderings
Section 9.1
Section Summary
 Relations and Functions
 Properties of Relations
 Reflexive Relations
 Symmetric Relations
 Antisymmetric Relations
 Transitive Relations
 Irreflexive Relations
 Asymmetric Relations
 Combining Relations
 Recall, Function is…
 Let A and B be nonempty sets Function f from A to B is an
assignment of exactly one element of B to each element of A.
 By defining using a relation, a function from A to B
contains unique ordered pair (a, b) for every element a ∈ A.
What is Relation?
Binary Relations
Definition: A binary relation R from a set A to a set B is a
subset R ⊆ A × B.
 Recall, for example:
A = {a1, a2} and B = {b1, b2, b3}
A x B = { (a1, b1), (a1, b2), (a1, b3),
(a2, b1), (a2, b2), (a2, b3)}
 Ordered pairs, which
 First element comes from A
 Second element comes from B
 aRb: (a, b) ∈ R
 : (a, b) ∉ R
Moreover, when (a, b) belongs to R, a is said to be related to b
by R.
Binary Relations
Example:
 Let A = {0,1,2} and B = {a,b}
 {(0, a), (0, b), (1,a) , (2, b)} is a relation from A to B.
 We can represent relations from a set A to a set B
graphically or using a table:
Binary Relations
EXAMPLE:
 Let A = {eggs, milk, corn} and B = {cows, goats, hens}

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

 Thus, with respect to this relation eggs R hens , milk R
cows, etc.
Binary Relations
EXAMPLE #1:
 Domain and Range of a Relation
DOMAIN OF A 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
by Dom(R).
Symbolically, Dom (R) = {a ∈A | (a, b) ∈R}
RANGE OF A 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}
 Domain and Range of a Relation
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
 a. Find the ordered pairs in R.
 b. Find the Domain and Range of R.
 c. Is 1R3, 2R2?
SOLUTION:
Given A = {1, 2}, B = {1, 2, 3},
A × B = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)}
 a. R = {(a, b) ∈A × B | a < b}
R = {(1,2), (1,3), (2,3)}
Domain and Range of a Relation
Given A = {1, 2}, B = {1, 2, 3},
A × B = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)}
 a. R = {(a, b) ∈A × B | a < b}
R = {(1,2), (1,3), (2,3)}
 b. Find the Domain and Range of R.
Solution:
Dom(R) = {1,2} and Ran(R) = {2, 3}

 c. Is 1R3, 2R2?
Solution:
c. Since (1, 3)∈R so 1R3.
Since (2, 2) is not ∈R so 2R2 is not a relation.
Representing Relations Using Digraphs
Definition: A directed graph, or digraph, consists of a set V of
vertices (or nodes) together with a set E of ordered pairs of
elements of V called edges (or arcs). The vertex a is called the
initial vertex of the edge (a,b), and the vertex b is called the
terminal vertex of this edge.
 An edge of the form (a,a) is called a loop.

Example: A drawing of 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 shown here.
 Representing Relations Using Matrices
 A relation between finite sets can be represented using a
zero-one matrix.
 Suppose R is a relation from A = {a1, a2, …, am} to
B = {b1, b2, …, bn}.
 The elements of the two sets can be listed in any particular
arbitrary order. When A = B, we use the same ordering.
 The relation R is represented by the matrix
MR = [mij], where

 The matrix representing R has a 1 as its (i,j) entry when ai is

related to bj and a 0 if ai is not related to bj.
Examples of Representing
Relations Using Matrices
Example 1: Suppose that A = {1,2,3} and B = {1,2}. Let
R be the relation from A to B containing (a,b) if a ∈ A,
b ∈ B, and a > b. What is the matrix representing R
(assuming the ordering of elements is the same as the
increasing numerical order)?
Solution: Because R = {(2,1), (3,1),(3,2)}, the matrix is
Binary Relations
EXAMPLE #1: (cont.)
Binary Relation on a Set
Definition: A binary relation R on a set A is a subset of
A × A or a relation from A to A.
Example:
 Suppose that A = {a,b,c}. Then R = {(a,a),(a,b), (a,c)} is a
relation on A.
 Let A = {1, 2, 3, 4}. The ordered pairs in the relation
R = {(a,b) | a divides b} are
{(1,1), (1, 2), (1,3), (1, 4), (2, 2), (2, 4), (3, 3), and (4, 4)}.
REMARK:
For any set A
1. A × A is known as the universal relation.
2. ∅ is known as the empty relation.
Binary Relation on a Set
Binary Relation on a Set (cont.)
Question: How many different relations are there on a
set A with n elements?
Solution:
 Suppose A has n elements
 Recall, a relation on a set A is a subset of A x A.
 A x A has 𝑛2 elements.
 If a set has m element, its has 2𝑚 subsets.
𝑛2
 Therefore, the answer is 2 .
Reflexive Relations
Definition: R is reflexive iff (a,a) ∊ R for every element
a ∊ A. Written symbolically, R is reflexive if and only if
∀a[a∊U ⟶ (a,a) ∊ R]

If A = ∅ then the empty

relation is reflexive
vacuously. That is the
empty relation on an
empty set is reflexive!

Needed for equivalence

relations and partial
orders.
 Reflexive Relations
EXAMPLE: Let A = {1, 2, 3, 4} and determine whether
relations R1, R2, R3, and R4 are Reflexive?
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)}
Solution:
 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.
Symmetric Relations
Definition: R is symmetric iff (b,a) ∊ R whenever (a,b) ∊ R
for all a,b ∊ A. Written symbolically, R is symmetric if and
only if
Accordingly, R is symmetric if the
∀a∀b [(a,b) ∊R ⟶ (b,a) ∊ R] elements in the ith row are the
same as the elements in the ith
column of the matrix M
 More precisely, M is a representing R. More precisely, M
is a symmetric matrix
 symmetric matrix i.e. M = M t i.e. M = 𝑀𝑡

•Models mutual relationships

(e.g., “is a friend of”).
•Helps define equivalence
classes (like grouping objects
with equal property).
 Symmetric Relations
EXAMPLE: Let A = {1, 2, 3, 4} and determine whether
relations R1, R2, R3, and R4 are Symmetric?
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)}
Solution:
 R1 is Symmetric, since (a, b) and (b, a) ∈R1 for all (a, b) ∈A.
 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.
Transitive Relations
Definition: 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. Written symbolically, R is transitive if and only if
∀a∀b ∀c[(a,b) ∊R ∧ (b,c) ∊ R ⟶ (a,c) ∊ R ] 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.
Essential for reasoning
and inference
Critical in reachability
problems (like paths in
graphs, inheritance in
OOP).
 Transitive Relations
EXAMPLE: Let A = {1, 2, 3, 4} and determine whether
relations R1, R2 and R3 are Transitive?
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)}
Solution:
 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.
 R2 is not transitive since (1,2) and (2,3) ∈ R2 but (1,3) ∉ R2.
 R3 is transitive.(check by definition) (2,1) vacuously True
 Irreflexive Relations
Definition: 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.
Written symbolically, R is irreflexive if and only if
∀a [(a ∊A) ⟶ (a , a)∉ R]
R is not irreflexive
iff there is an
element a∈A such
that (a,a) ∈R.

Nobody strictly prefers an

option to itself.
“Event A happened before event
B” is irreflexive and transitive.
 Irreflexive Relations
EXAMPLE: Let A = {1, 2, 3, 4} and determine whether
relations R1, R2 and R3 are Irreflexive?
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:
 R1 is irreflexive since no element of A is related to itself in
R1. i.e. (1,1)∉ R1, (2,2) ∉ R1, (3,3) ∉ R1,(4,4) ∉ R1.
 R2 is not irreflexive, since all elements of A are related to
themselves in R2.
 R3 is not irreflexive since (3,3) ∈R3. Note that R3 is not
reflexive.
 Symmetric: R is symmetric iff (b,a) ∊ R whenever
(a,b) ∊ R for all a,b ∊ A.

Antisymmetric Relations
Definition: 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. Written symbolically, R is antisymmetric if
and only if ∀a∀b [(a,b) ∊R ∧ (b,a) ∊ R ⟶ a = b]
Note: (a,a) may be an element in R. Let R be an anti-
symmetric relation on a
set A = {a1, a2, …, an}.
Then if (ai, aj) ∈R for
i ≠ j then (ai, aj) ∉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
Necessary for partial orders (e.g., “≤”, “subset
column contains 0 vice
of”).
versa.
Helps avoid circular contradictions (e.g., in
hierarchy or dependency structures).
 Symmetric: R is symmetric iff (b,a) ∊ R whenever
(a,b) ∊ R for all a,b ∊ A.

Antisymmetric Relations
EXAMPLE: Let A = {1, 2, 3, 4} and determine whether relations R1,
R2, R3, and R4 are Antisymmetric?
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)}
Solution: ∀a∀b [(a,b) ∊R ∧ (b,a) ∊ R ⟶ a = b]
 R1 is anti-symmetric and symmetric.
 R2 is anti-symmetric but not symmetric because (1,2) ∈ R2 but
(2,1) ∉ R2.
 R3 is not anti-symmetric since (1,3) & (3,1) ∈ R3 but 1 ≠ 3. Note
that R3 is symmetric.
 R4 is neither anti-symmetric because (1,3) & (3,1) ∈ R4 but 1 ≠ 3
nor symmetric because (2,4) ∈ R4 but (4,2) ∉R4.
 Asymmetric Relations
Definition: R is Asymmetric iff for all (a,b) ∊R than (b ,a)∉R.
Written symbolically, R is Asymmetric if and only if
∀a ∀b[((a,b) ∊R)) ⟶ ((b , a)∉ R)]
Note:(a,a) cannot be an element in R.

If Alice is parent of Bob, then Bob cannot be Asymmetry =

parent of Alice. Antisymmetry +
n a directed graph, an asymmetric relation Irreflexivity
corresponds to a graph with no bidirectional
edges and no self-loops.
 Asymmetric Relations ∀a ∀b[((a,b) ∊R)) ⟶ ((b , a)∉ R)]

 EXAMPLE: Let A = {1, 2, 3, 4} and determine whether

relations R1, R2 and R3 are Asymmetric?
R1 = {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}
R2 = {(1,2),(2,3),(3,4)}
R3 = {(2,3),(3,3),(3,4)}
Solution:
 R1 is not Asymmetric since R1 is neither Antisymmetric
nor Irreflexive.
 R2 is Asymmetric since R2 is both Antisymmetric and
Irreflexive.
 R3 is not Asymmetric since it is Antisymmetric but not
irreflexive.
Activity Time
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)}.

Determine which of these relation are Reflexive, Symmetric, Transitive,

Antisymmetric, Irreflexive and Asymmetric.
Combining Relations
As R is a subsets of A x B, the set operations can be
applied
 Union (U)
 Intersection (∩)
 Difference (-)
 Symmetric Complement (⊕)
Given two relations R1 and R2, we can combine them
using basic set operations to form new relations such as
R1 ∪ R2, R1 ∩ R2, R1 − R2, R2 − R1 and R1 ⊕ R2.
Combining Relations
Given, A = {1,2,3}, B = {1,2,3,4}
R1 = {(1,1),(2,2),(3,3)},
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)}
 R2 - R1 = {(1,2),(1,3),(1,4)}
 R1 ⊕ R2 = {(1,2),(1,3),(1,4),(2,2),(3,3)}
Composition of Relations
Definition: Suppose
 R1 is a relation from a set A to a set B.
 R2 is a relation from B to a set C.
Then the composition (or composite) of R2 with R1, is a
relation from A to C where
 if (x,y) is a member of R1 and (y,z) is a member of R2,
then (x,z) is a member of R2∘ R1.
 Composition of Relations
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)}
 S is the relation from {1,2,3,4} to {0,1,2} with
S = {(1,0),(1,2),(2,0),(3,1),(3,2),(4,1)}?
 S o R = {(1,0),(1,2),(1,1), (2,2),(2,1), (3,0),(3,2),(3,1)}
INVERSE OF A RELATION
Let R be a relation from A to B. The inverse relation
𝑅 −1 from B to A is defined as:
𝑅−1 = {(b,a) ∈B×A | (a,b) ∈R}
More simply, the inverse relation 𝑅 −1 of R is obtained by
interchanging the elements of all the ordered pairs in R.
 Example
X = {a, b, c} and Y={1, 2}
R = {(a, 1), (b, 2), (c, 1)}
 𝑅 −1 = {(1, a), (2, b), (1, c)}
 INVERSE OF A RELATION
The relation
R = {(2,2), (2,6), (2,8), (3,6), (4,8)} is
represented by the arrow diagram.

Then inverse of the above relation

can be obtained simply changing
the directions of the arrows and
hence the diagram is
Equivalence Relations
Definition 1: A relation on a set A is called an
equivalence relation if it is reflexive, symmetric, and
transitive.

Definition 2: Two elements a, and b that are related

by an equivalence relation are called equivalent. The
notation a ∼ b is often used to denote that a and b are
equivalent elements with respect to a particular
equivalence relation.
Strings
Example:
Suppose that R is the relation on the set of strings of
English letters such that aRb if and only if l(a) = l(b), where
l(x) is the length of the string x. Is R an equivalence
relation?

Solution: Show that all of the properties of an equivalence

relation hold.
 Reflexivity: Because l(a) = l(a), it follows that aRa for all
strings a.
 Symmetry: Suppose that aRb. Since l(a) = l(b), l(b) = l(a)
also holds and bRa.
 Transitivity: Suppose that aRb and bRc. Since l(a) = l(b),
and l(b) = l(c), l(a) = l(c) also holds and aRc.
Partial Orderings
Definition 1: A relation R on a set S is called a partial
ordering, or partial order, if it is:
 reflexive,
 antisymmetric, and
 transitive.
A set together with a partial ordering R is called a
partially ordered set, or poset, and is denoted by (S, R).
Members of S are called elements of the poset.
Partial Orderings (continued)
Example 1: Show that the “greater than or equal”
relation (≥) is a partial ordering on the set of integers.
 Reflexivity: a ≥ a for every integer a.
 Antisymmetry: If a ≥ b and b ≥ a , then a = b.
 Transitivity: If a ≥ b and b ≥ c , then a ≥ c.
Partial Orderings (continued)
Example 2: Show that the divisibility relation (∣) is a
partial ordering on the set of integers.
 Reflexivity: a ∣ a for all integers a. (see Example 9 in
Section 9.1)
 Antisymmetry: If a and b are positive integers with a | b
and b | a, then a = b. (see Example 12 in Section 9.1)
 Transitivity: Suppose that a divides b and b divides c.
Then there are positive integers k and l such that b = ak
and c = bl. Hence, c = a(kl), so a divides c. Therefore, the
relation is transitive.
 (Z+, ∣) is a poset.
The Professor is not happy, when you can't sleep.
 P: "You can sleep."
 Q: "The Professor is happy."

This implies that

“if you can't sleep, then the Professor is not happy.”
 In logical notation, this can be written as:
 ¬P→¬Q
Where:
 ¬P: "You can't sleep" (negation of S).
 ¬Q: "The Professor is not happy" (negation of P).