Topics

Relations: Binary Relation

Relation on a Set
Properties of Relations: Reflexive, Symmetric, Antisymmetric,
Transitive
Combining Relations
Composite of Relations and Power of Relation
Composite of Relations and Matrix Manipulation
The Inverse of a Relation

Mufleh Al-Shatnawi, Ph.D., [Link]., 1

Introduction
A function 𝑓𝑓: 𝐴𝐴 → 𝐵𝐵 assigns one element of B to each
element of A.
Recall that a function 𝑓𝑓 from a set A to a set B assigns exactly
one element of B to each element of A
This definition restricts what a function can express. For
example, it cannot express an assignment in which:
Some elements of A are not assigned any element of B,
Some elements of A are assigned more than one element
of B.

Mufleh Al-Shatnawi, Ph.D., [Link]., 2

Example
We have a student database where we want to store,
for every student, the courses the student is taking this
term.
This assignment Registered cannot be a function from
the set of students to the set of courses since:
Some students are not taking any courses this term.
Some students are taking more than one course this term.
This type of assignment often occurs in computer
applications. Thus, we need something that
generalizes the concept of a function.
Mufleh Al-Shatnawi, Ph.D., [Link]., 3
Relations and their
Properties

Mufleh Al-Shatnawi, Ph.D., [Link]., 4

Functions as Relations
A function 𝑓𝑓: 𝐴𝐴 → 𝐵𝐵 can be seen as a set of
ordered pairs
𝑥𝑥, 𝑓𝑓 𝑥𝑥 ∶ 𝑥𝑥 ∈ 𝐴𝐴 𝑎𝑎𝑎𝑎𝑎𝑎 𝑓𝑓 𝑥𝑥 ∈ 𝐵𝐵
Thus, a function is a subset of 𝐴𝐴 × 𝐵𝐵.
However not every subset of 𝑨𝑨 × 𝑩𝑩 is a
function.
We define a binary relation from A to B as a
generalization of a function.
Mufleh Al-Shatnawi, Ph.D., [Link]., 5
Relations
Relationships between elements of sets are
represented using the structure called a relation
A subset of a Cartesian product of the sets
Example: a student and his/her ID

Mufleh Al-Shatnawi, Ph.D., [Link]., 6

Binary Relation
The most direct way to express a relationship between
elements of two sets is to use ordered pairs made up
of two related elements
Binary relation: Let A and B be sets. A binary relation
from A to B is a subset of 𝐴𝐴 × 𝐵𝐵
A binary relation from A to B is a set R of ordered pairs
where the 1st element comes from A and the 2nd
element comes from B

Mufleh Al-Shatnawi, Ph.D., [Link]., 7

Recall: Cartesian Product of Two Sets

Mufleh Al-Shatnawi, Ph.D., [Link]., 8

Recall: Cartesian Product of Two Sets

Mufleh Al-Shatnawi, Ph.D., [Link]., 9

Binary Relation
Let 𝑅𝑅 be a relation from A to B then for a pair (a, b)
in the relation R we write
𝑎𝑎, 𝑏𝑏 ∈ 𝑅𝑅 or 𝑎𝑎𝑎𝑎𝑎𝑎 or 𝑅𝑅(𝑎𝑎, 𝑏𝑏)
(read it as: 𝑎𝑎 is related to 𝑏𝑏 by relation R)
E.g., < can be seen as {(n,m) | n < m}
E.g., a<b and < (a,b) both mean (a,b)∈ <
If A = B we say that R is a relation on A

Mufleh Al-Shatnawi, Ph.D., [Link]., 10

Example
Let A be the set of students and B be the set of courses
Let R be the relation that consists of those pairs (a, b)
where 𝑎𝑎 ∈ 𝐴𝐴 and 𝑏𝑏 ∈ 𝐵𝐵
If Mark is enrolled only in Math101, and Eric is enrolled in
Math101 and Math102
The pairs (Mark, Math101), (Eric, Math101), (Eric,
Math102) belong to R
But (Mark, Math102) does not belong to R, i.e.,
(Mark, Math102) ∉ R

Mufleh Al-Shatnawi, Ph.D., [Link]., 11

Example
Let A={0, 1, 2} and B={a, b}. Then 0, 𝑎𝑎 , 0, 𝑏𝑏 , 1, 𝑎𝑎 , 2, 𝑏𝑏 is a
relation from A to B
That is 0Ra but not 1Rb

Mufleh Al-Shatnawi, Ph.D., [Link]., 12

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 13

Mufleh Al-Shatnawi, Ph.D., [Link].,
Complementary Relations
Let R: A, B be any binary relation.
Then, R: A×B, the complement of R, is the binary relation
defined by
� ≡ { 𝑎𝑎, 𝑏𝑏 ∈ 𝐴𝐴 × 𝐵𝐵 | (𝑎𝑎, 𝑏𝑏)∉𝑅𝑅} = (𝐴𝐴 × 𝐵𝐵) − 𝑅𝑅
𝑅𝑅:
Note this is just 𝑅𝑅� if the universe of discourse is U = A×B; thus
the name complement.
Note the complement of 𝑅𝑅� is 𝑅𝑅.
Example: < = {(a,b) | (a,b)∉<} = {(a,b) | ¬(a<b)} = ≥

Mufleh Al-Shatnawi, Ph.D., [Link]., 15

Recall: Functions as Relations
A relation can be used to express the 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 functions
A relation does not have to be defined for all 𝑎𝑎 ∈ 𝐴𝐴.
A relation does not have to be single-valued.
Mufleh Al-Shatnawi, Ph.D., [Link]., 16
Relation on a Set
RELATIONS FROM A SET 𝑨𝑨 TO ITSELF ARE OF SPECIAL
INTEREST

Mufleh Al-Shatnawi, Ph.D., [Link]., 17

Relation on a Set
A relation on the set A is a relation from A to A, i.e., a subset of
𝐴𝐴 × 𝐴𝐴
Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the
relation R={(a,b)| a divides b} ?
𝑅𝑅 = 1,1 , 1,2 , 1,3 , 1,4 , 2,2 , 2,4 , 3,3 , 4,4

Mufleh Al-Shatnawi, Ph.D., [Link]., 18

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 19

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 20

Example
Consider these relations on 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)?
(1,1) is in R1, R3, R4 and R6; (1,2) is in R1 and R6; (2,1) is in R2, R5,
and R6; (1,-1) is in R2, R3, and R6; (2,2) is in R1, R3, and R4
Mufleh Al-Shatnawi, Ph.D., [Link]., 21
Example
How many relations are there on a set with 𝒏𝒏 elements?
A relation on a set A is a subset of 𝐴𝐴 × 𝐴𝐴
𝑛𝑛2
As 𝐴𝐴 × 𝐴𝐴 has n2 elements, there are 2 subsets
𝑛𝑛2
Thus, there are 2 relations on a set with 𝑛𝑛 elements
𝑛𝑛2 32
That is, there are 2 =2 = 29 = 512 relations on the
set {𝑎𝑎, 𝑏𝑏, 𝑐𝑐}

Mufleh Al-Shatnawi, Ph.D., [Link]., 22

Representing
Relations using
Graphs
DIRECTED GRAPH (DIGRAPH)

Mufleh Al-Shatnawi, Ph.D., [Link]., 23

Representing Relations using Graphs
A relation 𝑅𝑅 ⊆ 𝐴𝐴 × 𝐴𝐴 can be represented by a
graph that has
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)
One point (node) for each element of A, and
An arc (edge/link) from node 𝑎𝑎 to node 𝑏𝑏 whenever
𝑎𝑎, 𝑏𝑏 ∈ 𝑅𝑅.
An edge of the form (a,a) is called a loop
Mufleh Al-Shatnawi, Ph.D., [Link]., 24
Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 25

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 26

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 shown

0 1 0 1
0 1 0 
1
MR = 
1 1 0 0
 
0 1 0 0

Mufleh Al-Shatnawi, Ph.D., [Link]., 27

Representing
Relations using
Matrices

Mufleh Al-Shatnawi, Ph.D., [Link]., 28

Representing Relations using Matrices

Mufleh Al-Shatnawi, Ph.D., [Link]., 29

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 30

Properties of
Relations

Mufleh Al-Shatnawi, Ph.D., [Link]., 31

Properties of Relations: Reflexive
In some relations an element is always related to
itself
Let R be the relation on the set of all people consisting of
pairs (x,y) where x and y have the same mother and the
same father. Then x R x for every person x
A relation R on a set A is called reflexive if 𝑎𝑎, 𝑎𝑎 ∈ 𝑅𝑅
for every element 𝑎𝑎 ∈ 𝐴𝐴
The relation R on the set 𝐴𝐴 is reflexive if
∀𝑎𝑎( 𝑎𝑎, 𝑎𝑎 ∈ 𝑅𝑅)
Mufleh Al-Shatnawi, Ph.D., [Link]., 32
Example
Consider these 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?
R3 and R5 are reflexive as both contain all pairs of the (a, a)
Is the “divides” relation on the set of positive integers reflexive?

Mufleh Al-Shatnawi, Ph.D., [Link]., 33

Example: Which of these relations are reflexive?

a reflexive relation Not a reflexive relation

Mufleh Al-Shatnawi, Ph.D., [Link]., 34
Irreflexivity
Consider a reflexive relation: <
One which every element is not related to itself
Let A = { 1, 2, 3, 4, 5 }

1 2
If every node does
not have a loop, a
relation is irreflexive
5 3

4
35
Fact about
Reflexive
Relation

Mufleh Al-Shatnawi, Ph.D., [Link]., 36

Binary Relation: irreflexive
A relation R on A is reflexive iff ∀a∈A(aRa).
E.g., the relation ≥ :≡ {(a,b) | a≥b} is reflexive.
R is irreflexive iff ∀a∈A(¬(aRa))
Note “irreflexive” does NOT mean “not reflexive”,
which is just ¬∀a∈A(aRa).
Theorem: A relation R is irreflexive iff its
complementary relation R is reflexive.

Mufleh Al-Shatnawi, Ph.D., [Link]., 37

 Irreflexivity
Consider a reflexive relation: <
One which every element is not related to itself
Let A = { 1, 2, 3, 4, 5 }

0 1 1 11
0 0 1 1
1

M ≤ = 0 0 0 11 If the center (main) diagonal is
 
0 0 0 10 all 0’s, a relation is irreflexive
0 0 0 0 0

Mufleh Al-Shatnawi, Ph.D., [Link]., 38

Symmetric
In some relations an element is related to a second
element if and only if the 2nd element is also related to
the 1st element
A relation R on a set A is called symmetric if (b,a) ∊ R
whenever (a,b) ∊ R for all a, b ∊ A
The relation R on the set A is symmetric if
∀a ∀b ((a,b)∊R→(b,a) ∊R)
A relation is symmetric if and only if a is related to b
implies that b is related to a

Mufleh Al-Shatnawi, Ph.D., [Link]., 39

Symmetric Vs. Asymmetric
A binary relation R on A is symmetric if
∀a ∀b ((a,b)∊R→(b,a) ∊R)
E.g., = (equality) is symmetric. < is not.
A binary relation R is asymmetric if
∀a,b((a,b)∈R → (b,a)∉R)
E.g., < is asymmetric

Mufleh Al-Shatnawi, Ph.D., [Link]., 40

 Antisymmetric
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
Similarly, the relation R is antisymmetric if
∀a∀b(((a,b)∊R∧(b,a)∊R)→(a=b))
A relation is antisymmetric 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
Alternatively:
∀𝑎𝑎∀𝑏𝑏 ∈ 𝑅𝑅 𝑎𝑎, 𝑏𝑏 ∈ 𝑅𝑅 ∧ 𝑎𝑎 ≠ 𝑏𝑏 → 𝑏𝑏, 𝑎𝑎 ∉ 𝑅𝑅

Mufleh Al-Shatnawi, Ph.D., [Link]., 41

Symmetric and Antisymmetric
The terms symmetric and antisymmetric are not
opposites as a relation can have both of these
properties or may lack both of them
A relation cannot be both symmetric and antisymmetric
if it contains some pair of the form (a, b) where a ≠ b

Mufleh Al-Shatnawi, Ph.D., [Link]., 42

Example
Consider the relation x≤y
It is not symmetric. (For instance, 5≤6 but not 6≤5)
It is not asymmetric. (For instance, 5 ≤5)
You might say it’s nearly symmetric since the only
symmetries occur when x=y
This is called antisymmetry.

Mufleh Al-Shatnawi, Ph.D., [Link]., 43

Example
Consider these 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 symmetric or antisymmetric?
R2 and R3 are symmetric: each (a,b)  (b,a) in the relation
R4, R5, and R6 are all antisymmetric: no pair of elements a and b with a ≠ b s.t. (a, b) and
(b, a) are both in the relation

Mufleh Al-Shatnawi, Ph.D., [Link]., 44

Example
Which are symmetric and antisymmetric
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}
Symmetric: R3, R4, R6. R3 is symmetric, if a=b (or a=-b), then b=a (b=-a), R4 is symmetric as a=b
implies b=a, R6 is symmetric as a+b≤3 implies b+a≤3
Antisymmetric: R1, R2, R4, R5 . R1 is antisymmetric as a≤b and b≤a imply a=b. R2 is antisymmetric
as it is impossible to have a>b and b>a, R4 is antisymmteric as two elements are related w.r.t. R4 if
and only if they are equal. R5 is antisymmetric as it is impossible to have a=b+1 and b=a+1

Mufleh Al-Shatnawi, Ph.D., [Link]., 45

Example: Which of these relations are symmetric?

a symmetric relation Not a symmetric relation

Mufleh Al-Shatnawi, Ph.D., [Link]., 46
Example: Which of these relations are antisymmetric?

Not an antisymmetric relation

a antisymmetric relation Not a symmetric
Mufleh Al-Shatnawi, Ph.D., [Link]., 47
Asymmetry
Consider an asymmetric relation: <
One which if a is related to b then b is not related to a for all (a,b)
Let A = { 1, 2, 3, 4, 5 }
A digraph is asymmetric if:
1 2
1. If, for every edge, there is not
an edge in the other direction,
then the relation is asymmetric
5 3
2. Loops are not allowed in an
asymmetric digraph (recall it
4
must be irreflexive)

48
Fact about
Symmetric
Relation
If, for every value, it is
equal to the value in
its transposed
position, then the
relation is symmetric

Mufleh Al-Shatnawi, Ph.D., [Link]., 49

Fact about
Anitsymmetric
Relation
 If, for every value
and the value in its
transposed position,
if they are not both 1,
then the relation is
antisymmetric
 The center diagonal
can have both 1’s
and 0’s

Mufleh Al-Shatnawi, Ph.D., [Link]., 50

Asymmetry
Consider an asymmetric relation: <
One which if a is related to b then b is not related to a for all (a,b)
Let A = { 1, 2, 3, 4, 5 }
 If, for every value and the value
0 1 1 1 1 in its transposed position, they
0 0 1 1 1 are not both 1, then the relation
 is asymmetric
M ≤ = 0 0 0 1 1  An asymmetric relation must
 
also be irreflexive
0 0 0 0 1
0 0 0 0 0  Thus, the main diagonal must be
all 0’s

Mufleh Al-Shatnawi, Ph.D., [Link]., 51

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
Using quantifiers, we see that a relation R is transitive
if we have
∀a∀b∀c (((a,b)∊R ∧ (b,c)∊R)→ (a,c)∊R)

Mufleh Al-Shatnawi, Ph.D., [Link]., 52

Example
Which one is transitive?
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)}
R4 R5 R6 are transitive
R1 is not transitive as (3,1) is not in R1
R2 is not transitive as (2,2) is not in R2
R3 is not transitive as (4,2) is not in R3

Mufleh Al-Shatnawi, Ph.D., [Link]., 53

Example
Which are symmetric and antisymmetric
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}
R1 is transitive as a≤b and b≤c implies a≤c. R2 is transitive
R3 , R4 are transitive
R5 is not transitive (e.g., (2,1), (1,0)). R6 is not transitive (e.g. (2,1),(1,2))
Mufleh Al-Shatnawi, Ph.D., [Link]., 54
Example: Which of these relations are transitive?

a transitive relation Not a transitive relation

Mufleh Al-Shatnawi, Ph.D., [Link]., 55
Fact about Transitive Relation
There is no simple way of determining whether a
relation is transitive from its matrix or graph
representation.
However, once we know how to compute the transitive
closure of a relation, we can determine if a relation is
transitive or not.

Mufleh Al-Shatnawi, Ph.D., [Link]., 56

Example about Transitive Relation
Consider an transitive relation: ≤
One which if a is related to b and b is related to c then a is related to c for
all (a,b), (b,c) and (a,c)
Let A = { 1, 2, 3, 4, 5 }
 If, for every spot (a,b) and (b,c)
1 1 1 1 1 that each have a 1, there is a 1 at
0 1 1 1 
1 (a,c), then the relation is transitive

M ≤ = 0 0 1 1 1
   Matrices don’t show this property
0 0 0 1 1 easily
0 0 0 0 1
Mufleh Al-Shatnawi, Ph.D., [Link]., 57
Example about Transitive Relation
Consider an transitive relation: ≤
One which if a is related to b and b is related to c then a is related to c for
all (a,b), (b,c) and (a,c)
Let A = { 1, 2, 3, 4, 5 }

1 2 A digraph is transitive if, for

there is an edge from a to c
when there is an edge from
5 3
a to b and from b to c
4

58
Combining Relations

Mufleh Al-Shatnawi, Ph.D., [Link]., 59

Combining Relations
Relations from A to B are subsets of 𝑨𝑨 × 𝑩𝑩, two relations
can be combined in any way that two sets can be combined

Mufleh Al-Shatnawi, Ph.D., [Link]., 60

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)} can be combined
R1⋃R2={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(3,3)}
R1∩R2={(1,1)}
R1–R2={(2,2),(3,3)}
R2-R1={(1,2),(1,3),(1,4)}

Mufleh Al-Shatnawi, Ph.D., [Link]., 61

Example
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?
Symmetric difference of A and B: denoted by A⊕B, is the
set containing those elements in either A or B, but not in both
A and B
We note that (x,y)∊ R1⋃R2, if and only if (x,y)∊ R1 or (x,y)∊
R2,it follows that R1⋃R2={(x,y)|x≠y}
Likewise, R1⋂R2= ∅,R1-R2=R1, R2-R1=R2,
R1⊕R2= R1⋃R2-R1⋂R2={(x,y)|x≠y}
Mufleh Al-Shatnawi, Ph.D., [Link]., 62
Composite of
Relations

Mufleh Al-Shatnawi, Ph.D., [Link]., 63

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 and for which there exists an element
b∊B s.t. (a,b)∊R and (b,c)∊S. We denote the composite of R
and S by S∘R
𝑆𝑆 ∘ 𝑅𝑅 ≡ 𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹 𝑅𝑅 𝑡𝑡𝑡𝑡𝑡𝑡𝑡 𝑆𝑆
SR = {(a,c) | ∃b: aRb ∧ bSc}
Need to find the 2nd element of the ordered pair in R the same
as the 1st element of the ordered pair in S

Mufleh Al-Shatnawi, Ph.D., [Link]., 64

Composite of Relations

Mufleh Al-Shatnawi, Ph.D., [Link]., 65

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
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)}?
Need to find the 2nd element in the ordered pair in
R is the same as the 1st element of order pair in S
S∘R={(1,0),(1,1),(2,1),(2,2),(3,0),(3,1)}
Mufleh Al-Shatnawi, Ph.D., [Link]., 66
Visualization of Construction of 𝑺𝑺 ∘ 𝑹𝑹

Mufleh Al-Shatnawi, Ph.D., [Link]., 67

Example: What is 𝑺𝑺 ∘ 𝑹𝑹

Mufleh Al-Shatnawi, Ph.D., [Link]., 68

Example: What is 𝑺𝑺 ∘ 𝑹𝑹

Mufleh Al-Shatnawi, Ph.D., [Link]., 69

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 70

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 71

Mufleh Al-Shatnawi, Ph.D., [Link].,
Composition of
Relation is
Associative

Mufleh Al-Shatnawi, Ph.D., [Link]., 73

Composition of
Relation is
Associative

Mufleh Al-Shatnawi, Ph.D., [Link]., 74

Power of Relation

Mufleh Al-Shatnawi, Ph.D., [Link]., 75

Power 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
Example: Let R={(1,1),(2,1),(3,2),(4,3)}. Find the
powers Rn, n=2,3,4,…
R2=R∘R, we find R2={(1,1),(2,1),(3,1),(4,2)}, R3=R2∘R,
R3={(1,1),(2,1),(3,1),(4,1)}, R4={(1,1),(2,1),(3,1),(4,1)}.
It also follows Rn=R3 for n=5,6,7,…
Mufleh Al-Shatnawi, Ph.D., [Link]., 76
Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 77

Mufleh Al-Shatnawi, Ph.D., [Link].,
The Power of Transitive Relation
Theorem: The relation R on a set A is transitive
if and only if Rn⊆R

Mufleh Al-Shatnawi, Ph.D., [Link]., 79

Composite of
Relations and Matrix
Manipulation

Mufleh Al-Shatnawi, Ph.D., [Link]., 80

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 81

Mufleh Al-Shatnawi, Ph.D., [Link].,
Mufleh Al-Shatnawi, Ph.D., [Link].,
Proposition

Mufleh Al-Shatnawi, Ph.D., [Link]., 84

Proof

Mufleh Al-Shatnawi, Ph.D., [Link]., 85

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 86

The Inverse of a
Relation

Mufleh Al-Shatnawi, Ph.D., [Link]., 87

The Inverse of a Relation

Mufleh Al-Shatnawi, Ph.D., [Link]., 88

Example

Mufleh Al-Shatnawi, Ph.D., [Link]., 89

Mufleh Al-Shatnawi, Ph.D., [Link].,
Example: What is the Inverse of R

Mufleh Al-Shatnawi, Ph.D., [Link]., 91

Example: What is the Inverse of R

Mufleh Al-Shatnawi, Ph.D., [Link]., 92

References
Kenneth H. Rosen. Discrete Mathematics and Its Applications,
Eighth Edition. McGraw Hill, 2019. The textbook is required.
[Link]
crete_Mathematics
[Link] [look for EECS
1028]

Mufleh Al-Shatnawi, Ph.D., [Link]., 93