ch7 5

Section 7.
5
Equivalence Relations
Longin Jan Latecki

Temple University, Philadelphia
latecki@temple.edu
We can group properties of relations together to define new types of
important relations.
_________________
Definition: A relation R on a set A is an equivalence relation iff R is
• reflexive
• symmetric
• transitive
Two elements related by an equivalence relation are called equivalent.
Examples of equivalence relations:

• Ex. 1, p. 508
• Ex. 4, p. 509
An equivalence class of an element x:
[x] = {y | <x, y> is in R}
[x] is the subset of all elements related to [x] by R.
The element in the bracket is called a representative

of the equivalence class. We could have chosen any one.
Theorem: Let R be an equivalence relation on A. Then either

[a] = [b] or [a] ∩[b] = Φ
The number of equivalence classes is called the rank of the equivalence

relation.
Let A={a,b,c} and R be given by a digraph:

Theorem: Let R be an equivalence relation on a set A.
The equivalence classes of R partition the set A into disjoint nonempty
subsets whose union is the entire set.
This partition is denoted A/R and called
• the quotient set, or
• the partition of A induced by R, or,
• A modulo R.
Definition: Let S1, S2, . . ., Sn be a collection of subsets of a set A. Then

the collection forms a partition of A if the subsets are nonempty,
disjoint and exhaust A:
Note that { {}, {1,3}, {2} } is not a partition (it contains the empty set).
{ {1,2}, {2, 3} } is not a partition because ….
{ {1}, {2} } is not a partition of {1, 2, 3} because none of its blocks contains 3.
It is easy to recognize equivalence relations using digraphs:
• The equivalence class of a particular element forms a universal relation
(contains all possible arcs) between the elements in the equivalence class.
The (sub)digraph representing the subset is called a complete (sub)digraph,
since all arcs are present.
Example: All possible equivalence relations on a set A with 3 elements:
1. Determine whether the relations represented by these zero-one matrices
are equivalence relations. If yes, with how many equivalence classes?
1 0 1 0 1 1 1 0
1 1 1 0 1 0 1 1 1 1 0
M  0 1 1 P   R
1 0 1 0 1 1 1 0
1 1 1    
0 1 0 1 0 0 0 1
2. What are the equivalence classes (sets in the partition) of the integers
arising from congruence modulo 4?
3. Can you count the number of equivalence relations on a set A with n

elements. Can you find a recurrence relation?
The answers are
• 1 for n = 1
• 2 for n = 2
• 5 for n = 3
How many for n = 4?
Theorem (Bell number)
Let p(n) denotes the number of different equivalence relations on a set with n elements
(which is equivalent to the number of partitions of the set with n elements). Then
n 1
p (n)   C (n  1, j ) p (n  j  1)
j 0
p(n) is called Bell number, named in honor of Eric Temple Bell
Examples:
p(0)=1, since there is only one partition of the empty set:
into the empty collection of subsets
p(1)=C(0,0)p(0)=1, since {{1}} is the only partition of {1}
p(2)=C(1,0)p(1)+C(1,1)p(0)=1+1=5, since portions of {1,2} are {{1,2}} and

{{1},{2}}
p(3)=5, since, the set { 1, 2, 3 } has these five partitions.

{ {1}, {2}, {3} }, sometimes denoted by 1/2/3.
{ {1, 2}, {3} }, sometimes denoted by 12/3.
{ {1, 3}, {2} }, sometimes denoted by 13/2.
{ {1}, {2, 3} }, sometimes denoted by 1/23.
n 1
p (n)   C (n  1, j ) p (n  j  1)
j 0
Proof (Bell number) :
We want to portion {1, 2, …, n}.

For a fixed j, A is a subset of j elements from {1, 2, …, n-1} union {n}.
Note that j can have values from 0 to n-1.
We can select a subset of j elements from {1, 2, …, n-1} in C(n-1,j) ways,

and we have p(n-1-j) partitions of the remaining n-1-j elements. ■
Theorem: If R1 and R2 are equivalence relations on A,
then R1∩R2 is an equivalence relation on A.
Proof: It suffices to show that the intersection of
• reflexive relations is reflexive,
• symmetric relations is symmetric, and
• transitive relations is transitive.

Definition: Let R be a relation on A.
Then the reflexive, symmetric, transitive closure of R, tsr(R), is an
equivalence relation on A, called the equivalence relation induced by R.
Example:
Theorem: tsr(R) is an equivalence relation.
Proof:
We need to show that tsr(R) is still symmetric and reflexive.
• Since we only add arcs vs. deleting arcs when computing closures it
must be that tsr(R) is reflexive since all loops <x, x> on the diagraph
must be present when constructing r(R).
• If there is an arc <x, y> then the symmetric closure of r(R) ensures
there is an arc <y, x>.
• Now argue that if we construct the transitive closure of sr(R) and we

add an edge <x, z> because there is a path from x to z, then there
must also exist a path from z to x (why?) and hence we also must add
an edge <z, x>.
Hence the transitive closure of sr(R) is symmetric.

ch7 5

Uploaded by

Copyright:

Available Formats

ch7 5

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ch7 5

Uploaded by

Copyright:

Available Formats

Section 7.

Longin Jan Latecki

Two elements related by an equivalence relation are called equivalent.

Examples of equivalence relations:

[x] = {y | <x, y> is in R}

[x] is the subset of all elements related to [x] by R.

The element in the bracket is called a representative

Theorem: Let R be an equivalence relation on A. Then either

The number of equivalence classes is called the rank of the equivalence

Let A={a,b,c} and R be given by a digraph:

Definition: Let S1, S2, . . ., Sn be a collection of subsets of a set A. Then

3. Can you count the number of equivalence relations on a set A with n

p(1)=C(0,0)p(0)=1, since {{1}} is the only partition of {1}

p(2)=C(1,0)p(1)+C(1,1)p(0)=1+1=5, since portions of {1,2} are {{1,2}} and

p(3)=5, since, the set { 1, 2, 3 } has these five partitions.

Proof (Bell number) :

We want to portion {1, 2, …, n}.

We can select a subset of j elements from {1, 2, …, n-1} in C(n-1,j) ways,

Proof: It suffices to show that the intersection of

• reflexive relations is reflexive,

• symmetric relations is symmetric, and

• transitive relations is transitive.

• Now argue that if we construct the transitive closure of sr(R) and we

You might also like