Properties of Relations

•We will now look at some useful ways to classify relations.

•Definition: A relation R on a set A is called reflexive if (a,
a)R for every element aA.
•Are the following relations on {1, 2, 3, 4} reflexive?

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

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

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

Definition: A relation on a set A is called irreflexive if (a, a) R for every element a A.

 Properties of Relations

•Definitions:
•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 is called antisymmetric if
a = b whenever (a, b)R and (b, a)R.
•A relation R on a set A is called asymmetric if
(a, b)R implies that (b, a)R for all a, bA.
 Properties of 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 a, b,
cA.
•Are the following relations on {1, 2, 3, 4}
transitive?

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

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

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

 Counting Relations
•Example: How many different reflexive relations can be
defined on a set A containing n elements?
•Solution: Relations on R are subsets of AA, which
contains n2 elements.
•Therefore, different relations on A can be generated by
choosing different subsets out of these n2 elements, so
2
there are 2n relations.
•A reflexive relation, however, must contain the n
elements (a, a) for every aA.
•Consequently, we can only choose among n2 – n =
n(n – 1) elements to generate reflexive relations, so there
are 2n(n – 1) of them.
 Combining Relations

•Relations are sets, and therefore, we can apply the usual

set operations to them.
•If we have two relations R1 and R2, and both of them are
from a set A to a set B, then we can combine them to R1 
R2, R1  R2, or R1 – R2.
•In each case, the result will be another relation from A to
B.
 Combining Relations
•… and there is another important way to combine
relations.
•Definition: 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 such that (a,
b)R and
(b, c)S. We denote the composite of R and S by
SR.
•In other words, if relation R contains a pair (a, b) and
relation S contains a pair (b, c), then SR contains a pair (a,
c).
 Combining Relations
•Example: Let D and S be relations on A = {1, 2, 3, 4}.
•D = {(a, b) | b = 5 - a} “b equals (5 – a)”
•S = {(a, b) | a < b} “a is smaller than b”
•D = {(1, 4), (2, 3), (3, 2), (4, 1)}
•S = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
•SD = { (2, 4), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)}

D maps an element a to the element (5 – a), and afterwards S maps (5 – a) to all elements
larger than (5 – a), resulting in S D = {(a,b) | b > 5 – a} or S D = {(a,b) | a + b > 5}.
 Combining Relations
•Another Example: Let X and Y be relations on
A = {1, 2, 3, …}.
•X = {(a, b) | b = a + 1} “b equals a plus 1”
•Y = {(a, b) | b = 3a} “b equals 3 times a”
•X = {(1, 2), (2, 3), (3, 4), (4, 5), …}
•Y = {(1, 3), (2, 6), (3, 9), (4, 12), …}
•XY = { (1, 4), (2, 7), (3, 10), (4, 13), …}

Y maps an element a to the element 3a, and afterwards X maps 3a to 3a + 1.

X Y = {(a,b) | b = 3a + 1}
 Combining Relations

•We already know that functions are just special

cases of relations (namely those that map each
element in the domain onto exactly one element in
the codomain).

•If we formally convert two functions into relations,

that is, write them down as sets of ordered pairs,
the composite of these relations will be exactly the
same as the composite of the functions (as defined
earlier).
 Combining Relations

•Definition: Let R be a relation on the set A. The powers Rn,

n = 1, 2, 3, …, are defined inductively by
•R1 = R
•Rn+1 = RnR

•In other words:

•Rn = RR … R (n times the letter R)
 Closures of Relations:
Transitive Closure and Partitions
Sections 8.4 and 8.5

11
 Concept of “closure”
• The natural numbers N (counting numbers)
are not closed under subtraction: when we
close them under subtraction, we get Z, the
integers (positive and negative).
• When we close Z under the operation of
division, we get Q, the
“Closing” rational
a relation hasnumbers.
important
applications.
 Transitive closure
• Computing the transitive closure of a digraph
is an important problem in many computer
science applications:
– Evaluation of recursive database queries.
– Analysis of reachability (connectivity) of transition
graphs in communication networks.
– Construction of parsing automata in compilers.

13
 Introduction
• Closure of relation properties
– When a property does not hold for a relation, how
could we minimally augment the relation so that
the property would hold?

14
 Reflexive Closure
• Example: Consider the relation
R = {(1,1), (1,2), (2,1), (3,2)} on set {1,2,3}
– Is it reflexive?
– How can we produce a reflective relation
containing R that is as small as possible?

15
 Reflexive Closure – cont.
• When a relation R on a set A is not reflexive:
– How to minimally augment R (adding the
minimum number of ordered pairs) to make it a
reflexive relation?
• The reflexive closure of R.
• The reflexive closure of R can be formed by adding all of the
pairs of the form (a,a) to R. In other words we should find:

R    R  {(a, a) | a  A}

R = { (1,1), (1,2), (2,1), (3,2) } U { (1,1), (2,2), (3,3) }

16
 Reflexive Closure – Cont.
• The diagonal relation on A is:
 = {(a,a) | a  A}.
• The reflexive closure of R is then:
R  .
• Properties:
– R  (R  );
– R   is reflexive;
–  S (R  S  S is reflexive)  (R  )  S.
• In zero-one matrix notation: MR  M
• Turn on all the diagonal bits!

17
 Example
• Consider R = {(a,b)ZZ | a < b}
• The reflexive closure of relation R is:
R
= {(a,b)ZZ | a < b}  {(a,a) | a Z}
= {(a,b)ZZ | a  b}

18
 Symmetric Closure (optional)
• Example: Consider
R ={(1,1), (1,2), (2,2), (2,3), (3,1), (3,2)}
– R is not symmetric; the pairs missing are:
(2,1), (1,3).
– If we add those, we obtain the new relation:
{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2)}.
The new relation is symmetric.

19
 Symmetric Closure (optional)
• When a relation R on a set A is not symmetric:
– How to minimally augment R (adding the
minimum number of ordered pairs) to have a
symmetric relation?
– The symmetric closure of R.

20
 Symmetric Closure (optional)
• The inverse of R is:
R-1 = {(b,a) | (a, b)  R}.
• The symmetric closure of R is then:
R  R-1.
• Properties:
– R  (R  R-1);
– R  R-1 is symmetric;
–  S (R  S  S is symmetric)  (R  R-1)  S.
• In zero-one matrix notation: MR  MRt

21
 Example (optional)
• Consider R = {(a,b)ZZ | a < b}
• The symmetric closure of relation R is:
R  R-1
= {(a,b)ZZ | a < b}  {(a,b)ZZ | b < a}
= {(a,b)ZZ | a  b}

22
 Transitive Closures
• Consider R = {(1,3), (1,4), (2,1), (3,2)}.
– R is not transitive;
– What are the missing terms?
• Few are: (1,2), (2,3), (2,4), (3,1).
– If we add those, we obtain the new relation:
{(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2)}.
– Is the above relation transitive?
– No, it is not. Missing terms such as (1,1), (2,2)…
Transitive closure is more complicated to
build. 23
 Transitive Closure
• When a relation R on a set A is not transitive:
– How to minimally augment R (adding the
minimum number of ordered pairs) to have a
transitive relation?
– The transitive closure of R.

24
 Paths in Directed Graphs
• Definition: A path from a to b in a digraph G is
a sequence of 1 or more adjacent arcs
(a,x1), (x1,x2), (x2,x3), …, (xn-1, b).
– Denoted: a, x1, x2, x3, …, xn-1, b
– Has length n.
– If a = b, the path is called a circuit or a cycle, since
theDoes
patha path appearto
returns to be
its“transitive”?
start.

25
 Example
•  a path of length 2 from 1 to 2:
arcs (1,3), (3,2).
•  a path of length 3 from 3 to 4:
1 2 (3,2), (2,1), (1,4).
• There are no paths from
– 4 to 1
– 4 to 2
– 4 to 3

4 3

26
 Paths in Relations
• There is a path from a to b in R if there is a sequence of
elements: x1, x2, …, xn-1 with (a,x1)R, (x1,x2)R, …,
(xn-1, b)R.
• Example. R = {(1,3), (1,4), (2,1), (3,2)}
–  a path in R (len. 2) from 1 to 2: (1,3), (3,2)R.
–  a path in R (len. 3) from 3 to 4: (3,2), (2,1), (1,4)R.
– There is no path in R from 4 to 1, nor to 2, nor to 3.

27
 Theorem 1
• Theorem: Let R be a relation on a set A.
 a path in R of length n from a to b  (a,b)
Rn .
Proof

28
 Transitive Closure
• Definition: Let R be a relation on a set A.
The connectivity relation is the relation R*
defined as:
R* ={(a,b) |  a path in R from a to b}.
• From the above definition of R* and the
previous theorem, R* can be written as:
We used this notion ofk “connectivity” in the graphics Fill algorithm.
R* =  k=1 R .

Also, we used it the airplane flights example.

29
 Transitive Closure – Cont.
• Theorem 2 The transitive closure of R is R*.
• Proof:
1. R  R*, because if there is an edge from a to b then there is
a path from a to b.
2. R* is transitive, because if  a path from a to b and  a path
from b to c then  a path from a to c.
3. S (R  S  S is transitive)  R*  S.
Proof. Let S be a transitive relation, and assume RS.
So R* S* because RS.
Also k Sk  S, because S is transitive (see last theorem of
sect. 6.1) SoS*  S. Therefore, R* S.

30
 Transitive Closure – Cont.
• Lemma: Let A be a set with n elements, and R
be a relation on A.
If there is a path in R from a to b (with ab),
then there is such a path with length  n-1.
R* = R  R2  R3  …  Rn.

31
 Transitive Closure – Cont.
Theorem: Let MR be the zero-one matrix of
relation R on a set with n elements.
The zero-one matrix of the transitive closure
R* is:
MR* = MR  MR[2]  MR[3]  …  MR[n].

32
•
Transitive
Find the matrix M * of the
Closure - Example
• Solution:
R
transitive closure of R: 1 1 1
0 1 0 
MR[2] =  
MR = 1 1 1

1 0 1 1 1 1
0 1 0  MR[3] = 0 1 0 
   
1 1 1
1 1 0
MR*= MRMR[2]MR[3] =

1 1 1
1 2 0 1 0 
 
1 1 1

3
33
 Algorithm 1 for TC
• Procedure for computing transitive closure:
A = MR;
B = A;
For i=2 to n do the following:
A = A o MR; // Boolean product
B = B  A; // Join operation

34
•
Transitive
Find the matrix M * of the
Closure - Example
R
transitive closure of R:
1 0 1
Solution: 0 1 0 
 
MR = B1= A1= MR = 1 1 0

Ak=Ak-1o MR Bk=Bk-1Ak
1 0 1 1 1 1 1 1 1
0 1 0  A2=MR[2]= 0 1 0  B2= 0 1 0 
     
1 1 1 1 1 1
1 1 0 1 1 1
A3=MR = [3]
0 1 0 
 
1 1 1
1 2 MR*=B3= 1 1 1
0 1 0 
1 1 1

3
35
 Transitive Closure – optional
• Toward a more efficient algorithm (Warshall’s)

• Definition: Let R be a relation on S={v1,v2,…,

vn}.
The interior vertices of a path of length m
from a to b: a, x1, x2, x3, …, xm-1, b are:
x1, x2, x3, …, xm-1.

36
 Transitive Closure – optional
• Warshall’s Alg. iteratively constructs 0-1 matrices:
W0 = MR;
W1=[w[1]ij], where w[1]ij=1   a path from vi to vj
with interior vertices in {v1};
W2=[w[2]ij], where w[2]ij=1   a path from vi to vj
with interior vertices in {v1,v2}…
Wk=[w[k]ij], where w[k]ij=1   a path from vi to vj
with interior vertices in {v1,v2, …, vk}…
MR* = Wn.

37
•
Transitive
Find the matrix M * of the
Closure - Example
R • Solution: W0 = MR
transitive closure of R:
1 0 1 
W1 = 0 1 0 
MR =  
1 1 1
1 0 1 1 0 1
0 1 0  W2 = 0 1 0 
   
1 1 0 1 1 1

MR* = W3 = 1 1 1
0 1 0

1 2 1 1 1

3
38
 Transitive Closure – optional
• Lemma: Let R be a relation on
S={v1,v2,…,vn}, and let Wk=[w[k]ij] be the 0-1
matrix | w[k]ij=1   a path from vi to vj
with interior vertices in {v1, v2, …, vk}.
Then
i,j,kn w[k]ij = w[k-1]ij  (w[k-1]ikw[k-1]kj).

39
 Algorithm 2 - Warshall’s Algorithm

• Procedure for computing transitive closure:

W = MR;
For k=1 to n do the following:
For i=1 to n do the following:
For j=1 to n do the following:
wij = wij  (wik  wkj);
// That is, at step k: add row k to all other rows
which have 1 as intersection with kth column.

40
•
Warshall’s Algorithm
Find the matrix M * of the
- Example
• Solution: W = M
0 R
R
transitive closure of R: Add row 1 to row 3:
1 0 1
1 0 1 0 1 0 
0 1 0  W1 = 
MR =
 
1 1 1
1 1 0 Add row 2 to row 3:
1 0 1
0 1 0 
W2 =  
1 1 1
Add row 3 to row 1:
1 1 1
0 1 0
MR* = W3 = 
1 1 1

41
 Conclusions: transitive closure
• Computing the transitive closure of a digraph
is an important problem in many computer
science applications:
– Evaluation of recursive database queries.
– Analysis of reachability (connectivity) of transition
graphs in communication networks.
– Construction of parsing automata in compilers.

42
 Equivalence relations

These are reflexive, symmetric, and

transitive. They partition the set of all
elements into equivalence classes.
 Examples
• Locations(points, cities) connected by bi directional roads. All
cities connected to each other form an equivalence class –
points on Mackinaw Is.
• People related by speaking the same FIRST language
(assuming you can only have one).
• The real numbers related by absolute value: (5,5)(-5,5)(-π, π)
…
• The set of all students partitioned according to major,
assuming each student has ONE major.
 Example: the integers mod m
• a R b = { (a, b) | a ≡ b (mod m) }
• If m=5 then we have 5 classes induced by R
• [0]R = { 0, 5, -5, 10, -10, 15, -15, …}
• [1]R = { 1, -1, 6, -6, 11, -11, …}
• [2]R = { 2, -2, 7, -7, 12, -12, …}
• [3]R = { 3, -3, 8, -8, 13, -13, …}
• [4]R = { 4, -4, 9, -9, 14, -14, …}
• Note that every integer belongs to one and
only one of these classes – R partitions Z.