Relations

Section 8.1, 8.3—8.5 of Rosen

CSC2901 Discrete Structures
 Outline
• Relation:
– Definition, representation, relation on a set
• Properties
– Reflexivity, symmetry, antisymmetric, irreflexive, asymmetric
• Combining relations
– , , \, composite of relations
• Representing relations
– 0-1 matrices, directed graphs
• Closure of relations
– Reflexive closure, diagonal relation, Warshall’s Algorithm,
• Equivalence relations:
– Equivalence class, partitions,
 Introduction
• A relation between elements of two sets is a subset
of their Cartesian products (set of all ordered pairs
• Definition: A binary relation from a set A to a set B is
a subset R  AB ={ (a,b) | aA, bB}
• Relation versus function
– In a relation, each aA can map to multiple elements in B
– Relations are more general than functions
• When (a,b)R, we say that a is related to b.
• Notation: aRb, aRb $aRb$, $a\notR b$
 Relations: Representation
• To represent a relation, we can enumerate every element of R
• Example
– Let A={a1,a2,a3,a4,a5} and B={b1,b2,b3}
– Let R be a relation from A to B defined as follows
R={(a1,b1),(a1,b2),(a1,b3),(a3,b1),(a3,b2),(a3,b3),(a5,b1)}
• We can represent this relation graphically
A a1 b1 B
a2 b2
a3 b3
a4
a5
 Relations on a Set
• Definition: A relation on the set A is a relation from A
to A and is a subset of AA
• Example: The following are binary relations on N
R1={ (a,b) | a  b }
R2={ (a,b) | a,bN, a/bZ }
R3={ (a,b) | a,bN, a-b=2 }
• Question: Give some examples of ordered pairs (a,b)
N2 that are not in each of these relations
 Properties
• We will study several properties of relations
– Reflexive
– Symmetric
– Transitive
– Antisymmetric
– Asymmetric
 Properties: Reflexivity
• In a relation on a set, if all ordered pairs (a,a)
for every aA appears in the relation, R is
called reflexive
• Definition: A relation R on a set A is called
reflexive iff
aA (a,a)R
 Reflexivity: Examples
• Recall the relations below, which is reflexive?
R1={ (a,b) | a  b }
R2={ (a,b) | a,bN, a/bZ }
R3={ (a,b) | a,bN, a-b=2 }

• R1 is reflexive since for every aN, a  a

• R2 is reflexive since a/a=1 is an integer
• R3 is not reflexive since a-a=0 for every aN
 Properties: Symmetry
• Definitions:
– A relation R on a set A is called symmetric if
a,bA ( (b,a)R  (a,b)R )

– A relation R on a set A is called antisymmetric if

a,bA [(a,b)R  (b,a)R  a=b]
 Symmetry versus Antisymmetry
• In a symmetric relation aRb  bRa
• In an antisymmetric relation, if we have aRb and bRa hold only
when a=b
• An antisymmetric relation is not necessarily a reflexive
relation
• A relation can be
– both symmetric and antisymmetric
– or neither
– or have one property but not the other
• A relation that is not symmetric is not necessarily asymmetric
 Symmetric Relations: Example
• Consider R={(x,y)R2|x2+y2=1}, is R
– Reflexive?
– Symmetric?
– Antisymmetric?
• R is not reflexive since for example (2,2)R2
• R is symmetric because
x,yR, xRyx2+y2=1  y2+x2=1  yRx
• R is not antisymmetric because (1/3,8/3)R
and (8/3,1/3)R but 1/38/3
 Properties: Transitivity
• 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
a,b,cA ((aRb)(bRc))  aRc
 Transitivity: Examples (1)
• Is the relation R={(x,y)R2| xy} transitive?
Yes, it is transitive because xRy and yRz  xy
and yz  xz  xRz

• Is the relation R={(a,b),(b,a),(a,a)} transitive?

No, it is not transitive because bRa and aRb
but bRb
 Transitivity: Examples (2)
• Is the relation {(a,b) | a is an ancestor of b}
transitive?
Yes, it is transitive because aRb and bRc  a is an ancestor of
b and b is an ancestor of c  a is an ancestor of c  aRc

• Is the relation {(x,y)R2| x2y} transitive?

No, it is not transitive because 2R4 and 4R10 but 2R10

 More Properties
• Definitions
– A relation on a set A is irreflexive if
aA (a,a)R
– A relation on a set A is asymmetric if
a,bA ( (a,b)R  (b,a)  R )
• Lemma: A relation R on a set A is asymmetric if and
only if
– R is irreflexive and
– R is antisymmetric
 Outline
• Relation:
– Definition, representation, relation on a set
• Properties
– Reflexivity, symmetry, antisymmetric, irreflexive, asymmetric
• Combining relations
– , , \, composite of relations
• Representing relations
– 0-1 matrices, directed graphs
• Closure of relations
– Reflexive closure, diagonal relation, Warshall’s Algorithm,
• Equivalence relations:
– Equivalence class, partitions,
 Combining Relations
• Relations are simply… sets (of ordered pairs); subsets of the
Cartesian product of two sets
• Therefore, in order to combine relations to create new
relations, it makes sense to use the usual set operations
– Intersection (R1R2)
– Union (R1R2)
– Set difference (R1\R2)
• Sometimes, combining relations endows them with the
properties previously discussed. For example, two relations
may be not transitive, but their union may be
 Combining Relations: Example
• Let
– A={1,2,3,4}
– B={1,2,3,4}
– R1={(1,2),(1,3),(1,4),(2,2),(3,4),(4,1),(4,2)}
– R2={(1,1),(1,2),(1,3),(2,3)}
• Let
– R 1  R2 =
– R1  R2 =
– R1 \ R2 =
– R2 \ R1 =
 Composite of Relations
• Definition: Let R1 be a relation from the set A
to B and R2 be a relation from B to C, i.e.
R1  AB and R2BC
the composite of R1 and R2 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)R1 and (b,c)R2. We
denote the composite of R1 and R2 by
R2  R 1
 Powers of Relations
• Using the composite way of combining relations
(similar to function composition) allows us to
recursively define power of a relation R on a set A
• Definition: Let R be a relation on A. The powers Rn,
n=1,2,3,…, are defined recursively by
R1 = R
Rn+1 = Rn  R
 Powers of Relations: Example
• Consider R={(1,1),(2,1),(3,2),(4,3)}
• R2=
• R3=
• R4=
• Note that Rn=R3 for n=4,5,6,…
 Powers of Relations & Transitivity
• The powers of relations give us a nice
characterization of transitivity
• Theorem: A relation R is transitive if and only
if Rn  R for n=1,2,3,…
 Outline
• Relation:
– Definition, representation, relation on a set
• Properties
– Reflexivity, symmetry, antisymmetric, irreflexive, asymmetric
• Combining relations
– , , \, composite of relations
• Representing relations
– 0-1 matrices, directed graphs
• Closure of relations
– Reflexive closure, diagonal relation, Warshall’s Algorithm,
• Equivalence relations:
– Equivalence class, partitions,
 Representing Relations
• We have seen ways to graphically represent a
function/relation between two (different) sets
—Specifically a graph with arrows between
nodes that are related
• We will look at two alternative ways to
represent relations
– 0-1 matrices (bit matrices)
– Directed graphs
 0-1 Matrices (1)
• A 0-1 matrix is a matrix whose entries are 0 or 1
• Let R be a relation from A={a1,a2,…,an} and B={b1,b2,
…,bn}
• Let’s impose an ordering on the elements in each set.
Although this ordering is arbitrary, it is important that
it remain consistent. That is, once we fix an ordering,
we have to stick to it.
• When A=B, R is a relation on A and we choose the
same ordering in the two dimensions of the matrix
 0-1 Matrix (2)
• The relation R can be represented by a (nm)
sized 0-1 matrix MR=[mi,j] as follows
1 if (ai,bi)  R
mi,j =

0 if (ai,bi)  R
• Intuitively, the (i,j)-th entry if 1 if and only if
aiA is related to biB
 0-1 Matrix (3)
• An important note: the choice of row or column-
major form is important. The (i,j)-th entry refers to
the i-th row and the j-th column. The size, (nm),
refers to the fact that MR has n rows and m columns
• Though the choice is arbitrary, switching between
row-major and column-major is a bad idea, because
when AB, the Cartesian Product AB  BA
• In matrix terms, the transpose, (MR)T does not give
the same relation. This point is moot for A=B.
0-1 Matrix (4)
B
b1 b2 b3 b4

a1 0 0 1 0
a2 1 1 1 1
A a3 0 0 1 1
a4 1 0 1 1
 Matrix Representation: Example
• Consider again the example
– A={a1,a2,a3,a4,a5} and B={b1,b2,b3}
– Let R be a relation from A to B as follows:
R={(a1,b1),(a1,b2),(a1,b3),(a3,b1),(a3,b2),(a3,b3),(a5,b1)}
• Give MR
– What is the size of the matrix?
 Using the Matrix Representation (1)
• A 0-1 matrix representation makes it very easy to
check whether or not a relation is
– Reflexive
– Symmetric
– Antisymmetric
• Reflexivity
– For R to be reflexive, a (a,a)R
– In MR, R is reflexive iff mi,i=1 for i=1,2,…,n
– We check only the diagonal
 Using the Matrix Representation (2)
• Symmetry
– R is symmetric iff for all pairs (a,b) aRbbRa
– In MR, this is equivalent to mi,j=mj,i for every pair i,j=1,2,
…,n
– We check that MR=(MR)T
• Antisymmetry
– R is antisymmetric if mi,j=1 with ij, then mj,i=0
– Thus, i,j=1,2,…, n, ij (mi,j=0)  (mj,i=0)
– A simpler logical equivalence is
i,j=1,2,…, n, ij ((mi,j=1)  (mj,i=1))
 Matrix Representation: Example
• Is R reflexive? Symmetric? Antisymmetric?
0 0 1
1 1 1

MR= 0 0 1

• Clearly R is not reflexive: m2,2=0

• It is not symmetric because m2,1=1, m1,2=0
• It is however antisymmetric
 Matrix Representation: Combining Relations

• Combining relations is also simple: union and intersection of

relations are nothing more than entry-wise Boolean opertions
• Union: An entry in the matrix of the union of two relations
R1R2 is 1 iff at least one of the corresponding entries in R1 or
R2 is 1. Thus
MR1R2 = MR1 MR2
• Intersection: An entry in the matrix of the intersection of two
relations R1R2 is 1 iff both of the corresponding entries in R1
and R2 are 1. Thus
MR1R2 = MR1  MR2
• Count the number of operations
 Combining Relations: Example
• What is MR1R2 and MR1R2?
1 0 1 0 0 0
0 1 1 1 1 1

MR1 = 1 1 0
MR2 = 0 1 1

1 0 1 0 0 0
1 1 1 0 1 1
MR1R2= 1 1 1 MR1R2= 0 1 0

• How does combining the relations change their properties?

 Composing Relations: Example
• 0-1 matrices are also useful for composing matrices.
If you have not seen matrix product before, read
Section 3.8
1 0 1 0 0 0
0 1 1 1 1 1

MR1 = 1 1 0
MR2 = 0 1 1

0 1 1
1 1 1
1 1 1
MR2 R1=MR1 MR2=
.
 Composite Relations: R n

• Remember that recursively composing a relation Rn  R for

n=1,2,3,… gives a nice characterization of transitivity
• Theorem: A relation R is transitive if and only if Rn  R for
n=1,2,3,…
• We will use
– this idea and
– the composition by matrix multiplication
to build the Warshall (a.k.a. Roy-Warshall) algorithm, which
computed the transitive closure (discussed in the next
section)
Directed Graphs Representation (1)
• We will study graphs in details towards the end of
the semester
• We briefly introduce them here to use them to
represent relations
• We have already seen directed graphs to represent
functions and relations (between two sets). Those
are special graphs, called bipartite directed graphs
• For a relation on a set A, it makes more sense to use
a general directed graph rather than having two
copies of the same set A
 Definition: Directed Graphs (2)
• Definition: A G graph consists of
– A set V of vertices (or nodes), and
– A set E of edges (or arcs)
– We note: G=(V,E)
• Definition: A directed G graph (digraph) consists of
– A set V of vertices (or nodes), and
– A set E of edges of ordered pairs of elements of V (of
vertices)
Directed Graphs Representation (2)
• Example:
– Let A= {a1,a2,a3,a4} and B={b1,b2,b3}
– Let R be a relation on A defined as follows
R={(a1,a2),(a1,a3),(a1,a4),(a2,a3),(a2,a4),(a3,a1),(a3,a4),
(a4,a3),(a4,a4)}
• Draw the digraph representing this relation
(see white board)
 Using the Digraphs Representation (1)

• A directed graph offers some insight into the

properties of a relation
• Reflexivity: In a digraph, the represented
relation is reflexive iff every vertex has a self
loop
• Symmetry: In a digraph, the represented
relation is symmetric iff for every directed
edge from a vertex x to a vertex y there is also
an edge from y to x
Using the Digraphs Representation (2)
• Antisymmetry: A represented relation is
antisymmetric iff there is never a back edge
for any directed edges between two distinct
vertices
• Transitivity: A digraph is transitive if for every
pair of directed edges (x,y) and (y,z) there is
also a directed edge (x,z)
 This may be harder to visually verify in more
complex graphs
 Outline
• Relation:
– Definition, representation, relation on a set
• Properties
– Reflexivity, symmetry, antisymmetric, irreflexive, asymmetric
• Combining relations
– , , \, composite of relations
• Representing relations
– 0-1 matrices, directed graphs
• Closure of relations
– Reflexive closure, diagonal relation, Warshall’s Algorithm,
• Equivalence relations:
– Equivalence class, partitions,
 Closures: Definitions
• If a given relation R
– is not reflexive (or symmetric, antisymmetric, transitive)
– How can we transform it into a relation R’ that is?
• Example: Let R={(1,2),(2,1),(2,2),(3,1),(3,3)}
– How can we make it reflexive?
– In general we would like to change the relation as little as
possible
– To make R reflexive, we simply add (1,1) to the set
• Inducing a property on a relation is called its closure.
• Above, R’=R {(1,1)} is called the reflexive closure
 Reflexive Closure
• In general, the reflexive closure of a relation R
on A is R where ={ (a,a) | aA}
•  is the diagonal relation on A
• Question: How can we compute the diagonal
relation using
– 0-1 matrix representation?
– Digraph representation?
 Symmetric Closure
• Similarly, we can create the symmetric closure
using the inverse of the relation R.
• The symmetric closer is, RR’ where
R’={ (b,a) | (a,b)R }
• Question: How can we compute the
symmetric closure using
– 0-1 matrix representation?
– Digraph representation?
 Transitive Closure
• To compute the transitive closure we use the theorem
• Theorem: A relation R is transitive if and only if Rn  R
for n=1,2,3,…
• Thus, if we compute Rk such that Rk  Rn for all nk,
then Rk is the transitive closure
• The Warshall’s Algorithm allows us to do this efficiently
• Note: Your textbook gives much greater details in terms of graphs and
connectivity relations. It is good to read this material, but it is based on
material that we have not yet seen.
 Warshall’s Algorithm: Key Ideas
• In any set A with |A|=n, any transitive relation will be built
from a sequence of relations that has a length of at most n.
Why?
• Consider the case where the relation R on A has the ordered
pairs (a1,a2),(a2,a3),…,(an-1,an). Then, (a1,an) must be in R for R
to be transitive
• Thus, by the previous theorem, it suffices to compute (at
most) Rn
• Recall that Rk=RRk-1 is computed using a bit-matrix product
• The above gives us a natural algorithm for computing the
transitive closure: the Warshall’s Algorithm
 Warshall’s Algorithm
Input: An (nn) 0-1 matrix MR representing a relation R on A, |A|=n
Output: An (nn) 0-1 matrix W representing the transitive closure of R on A
1. W MR
2. FOR k=1,…, n DO
1. FOR i=1,…,n DO
2. FOR j=1,…,n DO
3. wi,j  wi.j  (wi,k  wk,j)
4. END
5. END
6. END
7. RETURN W
 Warshall’s Algorithm: Example
• Compute the transitive closure of
– The relation R={(1,1),(1,2),(1,4),(2,2),(2,3),(3,1),
(3,4),(4,1),(4,4)}
– On the set A={1,2,3,4}
 Outline
• Relation:
– Definition, representation, relation on a set
• Properties
– Reflexivity, symmetry, antisymmetric, irreflexive, asymmetric
• Combining relations
– , , \, composite of relations
• Representing relations
– 0-1 matrices, directed graphs
• Closure of relations
– Reflexive closure, diagonal relation, Warshall’s Algorithm
• Equivalence relations:
– Equivalence class, partitions,
 Equivalence Relation
• Consider the set of every person in the world
• Now consider a R relation such that (a,b)R if a and
b are siblings.
• Clearly this relation is
– Reflexive
– Symmetric, and
– Transitive
• Such as relation is called an equivalence relation
• Definition: A relation on a set A is an equivalence
relation if it is reflexive, symmetric, and transitive
 Equivalence Class (1)
• Although a relation R on a set A may not be an
equivalence relation, we can define a subset of A
such that R does become an equivalence relation (on
the subset)
• Definition: Let R be an equivalence relation on a set
A and let a A. The set of all elements in A that are
related to a is called the equivalence class of a. We
denote this set [a]R. We omit R when there is not
ambiguity as to the relation.
[a]R = { s | (a,s)R, sA}
 Equivalence Class (2)
• The elements in [a]R are called representatives of the
equivalence class
• Theorem: Let R be an equivalence class on a set A.
The following statements are equivalent
– aRb
– [a]=[b]
– [a] [b] 
• The proof in the book is a circular proof
 Partitions (1)
• Equivalence classes partition the set A into
disjoint, non-empty subsets A1, A2, …, Ak
• A partition of a set A satisfies the properties
–  k
A =A
i=1 i

– Ai  Aj =  for ij
– Ai   for all i
 Partitions (2)
• Example: Let R be a relation such that (a,b)R if a
and b live in the same state, then R is an equivalence
relation that partitions the set of people who live in
the US into 50 equivalence classes
• Theorem:
– Let R be an equivalence relation on a set S. Then the
equivalence classes of R form a partition of S.
– Conversely, given a partition Ai of the set S, there is a
equivalence relation R that has the set Ai as its equivalence
classes
 Partitions: Visual Interpretation
• In a 0-1 matrix, if the elements are ordered into their
equivalence classes, equivalence classes/partitions
form perfect squares of 1s (with 0s everywhere else)
• In a diargh, equivalence classes form a collections of
disjoint complete graphs
• Example: Let A={1,2,3,4,5,6,7} and R be an
equivalence relation that partitions A into A1={1,2},
A2={3,4,5,6} and A3={7}
– Draw the 0-1 matrix
– Draw the digraph
 Equivalence Relations: Example 1
• Example: Let R={ (a,b) | a,bR and ab}
– Is R reflexive?
– Is it transitive?
– Is it symmetric?
No, it is not. 4 is related to 5 (4  5)
but 5 is not related to 4
Thus R is not an equivalence relation
 Equivalence Relations: Example 2
• Example: Let R={ (a,b) | a,bZ and a=b}
– Is R reflexive?
– Is it transitive?
– Is it symmetric?
– What are the equivalence classes that partition Z?
 Equivalence Relations: Example 3
• Example: For (x,y),(u,v) R2, we define
R={ ((x,y),(u,v)) | x2+y2=u2+v2}
• Show that R is an equivalence relation.
• What are the equivalence classes that R
defines (i.e., what are the partitions of R2)?
 Equivalence Relations: Example 4
• Example: Given n,rN, define the set
nZ + r = { na + r | a Z }
– For n=2, r=0, 2Z represents the equivalence class of all
even integers
– What n, r give the class of all odd integers?
– For n=3, r=0, 3Z represents the equivalence class of all
integers divisible by 3
– For n=3, r=1, 3Z represents the equivalence class of all
integers divisible by 3 with a remainder of 1
– In general, this relation defines equivalence classes that
are, in fact, congruence classes (See Section 3.4)