previous up next
Go up to 7.1 Equivalence Relations and Partitions
Go forward to 7.1.2 Modular Arithmetic
RISC-Linz logo

7.1.1 Basic Notions

Equivalence relations are binary relations that have many (but not all) of the properties of the equality relation. First we name these properties.


Definition 98 (Relation Properties)  R is  reflexive (reflexiv),  symmetric (symmetrisch), respectively  transitive (transitiv) on a set S, if it satisfies the following properties:
R is reflexive on S : <=>
   forall x in S: <x, x> in R;
R is symmetric on S : <=>
   forall x, y: <x, y> in R => <y, x> in R;
R is transitive on S : <=>
   forall x, y, z: (<x, y> in R /\  <y, z> in R) => <x, z> in R.


Definition 99 (Equivalence Relation) Let R be a binary relation on S. R is an  equivalence relation (Äquivalenzrelation) on S, if it is reflexive, symmetric, and transitive on S:
R is equivalence relation on S: <=>
   R subset S x S /\ 
   R is reflexive on S /\ 
   R is symmetric on S /\ 
   R is transitive on S.


Example 

The visualization of an equivalence relation by a directed graph has the following properties:


Example  The following graph denotes an equivalence relation:
The equivalence relation imposed on the set of six nodes determines three partitions in each of which every node is connected to every other node. Actually, there is a close relationship between equivalence relations and set partitions that will be elaborated later.

We demonstrate how to prove that a relation is an equivalence relation.


Proof  Let p(x, y) : <=> x+y is even. We prove that p is an equivalence relation on N.
  1. p is clearly a binary relation on N.
  2. We prove p is reflexive on N. Take arbitrary x in N. We have to show x+x is even, i.e, 2x is even, which clearly holds.
  3. We prove p is symmetric on N. Take arbitrary x in N and y in N. We assume x+y is even. Then y+x is even, because x+y = y+x.
  4. We prove p is transitive on N. Take arbitrary x in N, y in N, and z in N. We assume
    (1) x+y is even /\  y+z is even.
    We have to show
    (2) x+z is even
    From (1), we have some a in N and b in N such that
    (3) 2a = x+y /\  2b = y+z.
    Thus we know
    x+z = (x+y) + (y+z) - 2y = 2a + 2b - 2y = 2(a+b-y)
    such that (2) holds.

Logic Evaluator  Above definitions can be implemented as shown below, see Appendix equiv.txt.

We may construct the group of all objects that are related to some object.


Definition 100 (Class) The  class (Klasse) of x with respect to R is the set of all elements that are related to x by R:
[x]R := {y in range(R): <x, y> in R}.

We may just write [x], if R is clear from the context. If R is an equivalence relation, we call [x]R the  equivalence class (Äquivalenzklasse) of x with respect to R.

In the visualization of an (equivalence) relation by a directed graph, the (equivalence) class of a node is the set of all nodes to which the node is connected:

By the reflexivity of an equivalence relation, we have the following result.


Proposition 114 (Non-Empty Equivalence Classes) If R is an equivalence relation on S, then [x]R contains x, for every x in S:
forall S, R: R is equivalence class on R => x in [x]R.


Example 

As illustrated by the example, different equivalences classes do not overlap.


Proposition 115 (Disjoint Equivalence Classes) Let R be an equivalence relation on S and x and y be elements of S. The equivalence classes of x and y with respect to R are either identical or disjoint:
forall S, R: R is equivalence relation on S =>
   forall x in S, y in S:
      [x]R = [y]R \/ [x]R intersection [y]R = 0.


Proof  Take arbitrary S, an equivalence relation R on S, x in S and y in S. We assume
(1) [x]R != [y]R,
(2) [x]R intersection [y]R != 0
and show a contradiction. From (2), we have some z such that
(3) z in [x]R /\  z in [y]R.
We thus know
(4) <x, z> in R,
(5) <y, z> in R.
We will now show
(6) [y]R subset [x]R,
(7) [x]R subset [y]R
which contradicts (1).

We show (6): From (5) and the symmetry of R, we know

(8) <z, y> in R.
From (4), (8), and the transitivity of R, we know
(9) <x, y> in R.
From (9) we know by the transitivity of R that
(10) forall z: <y, z> in R => <x, z> in R
and therefore by definition of [y]R
(11) forall z in [y]R: <x, z> in R
and thus by definition of [x]R
(12) forall z in [y]R: z in [x]R
which gives us (6).

With the same line of reasoning, we can show (7) and are done.


As a consequence of Propositions Non-Empty Equivalence Classes and Disjoint Equivalence Classes, we can decompose every set S by an equivalence relation into a set of non-empty disjoint subsets.


Definition 101 (Quotient Set) The  quotient set (Quotientenmenge) of S with respect to R is the set of all classes induced on S by R:
S/R := {[x]R: x in S}.

Logic Evaluator  The quotient set construction can be implemented as shown below, see Appendix equiv.txt.

We use in this example a relation on S := Nn x Nn whose elements are interpreted as points in a plane. Since the computation of C := S/R takes too long, we resort to an equivalent but faster construction C' where a representative of each equivalence class is manually selected, and the relation R as a set has been replaced by predicate r. Each color in the resulting picture denotes an equivalence class on S.

We expect this decomposition to satisfy the following properties.


Definition 102 (Partition)  D is a  partition (Partitionierung) or  decomposition (Zerlegung) of S, if its elements, the  blocks (Blöcke), are non-empty and disjoint and their union equals S:
D is partition of S : <=>
   (forall x in D: x != 0) /\ 
   (forall x in D, y in D: x = y \/ x intersection y = 0) /\ 
   union D = S.


Example 

The following result shows that an equivalence relation indeed defines a partition.


Proposition 117 (Equivalence Relation Defines Partition) Let R be an equivalence relation on S. The quotient set of S with respect to R is a partition of S:
forall S, R: R is equivalence relation on S =>
   S/R is partition of S.


Proof  Take arbitrary S and equivalence relation R on S. We show S/R is a partition of S:
  1. Take arbitrary x in S/R. By definition of S/R, we have some a in S such that x = [a]R. By Proposition Non-Empty Equivalence Classes, a in [a]R, therefore x != 0.
  2. Take arbitrary x in S/R and y in S/R. By definition of S/R, we have some a in S and b in S such that x = [a]R and y = [b]R. By Proposition Disjoint Equivalence Classes, [a]R = [b]R \/ [a]R intersection [b]R = 0.
  3. By definition of S/R, union S/R subset S. We show S subset union S/R. Take arbitrary x in S. Then from Proposition Non-Empty Equivalence Classes we have x in [x]R and from the definition of S/R we have [x]R in S/R, thus x in union S/R.

We can also proceed in the other direction and construct a relation from a partition.


Definition 103 (Induced Relation) The relation induced by a partition D is the set of all pairs of elements of the same block of D:
x ~ D y : <=> exists d in D: x in d /\  y in d.

The constructed relation is an equivalence relation.


Proposition 119 (Partition Defines Equivalence Relation) Let D be a partition of S. The relation induced by D is an equivalence relation on S:
forall S, D: D is partition of S =>
    ~ D is equivalence relation on S.


Proof  Take arbitrary S and partition D on S. We show that ~ D is an equivalence relation on S.
Binary Relation
By definition, ~ D is a binary relation. If x ~ D y, then we have some d in D such that x in d and y in d. Since union D = S, we have x in S and y in S and ~ D is a relation on S.
Reflexivity
Take arbitrary x in S. Since union D = S, we have some d in D such that x in d and thus x ~ D x.
Symmetry
Take arbitrary x in S and y in S and assume x ~ D y. Then we have some d in D such that x in d /\  y in d which gives us y ~ d x.
Transitivity
Take arbitrary x in S, y in S, and z in S and assume x ~ D y and y ~ D z. Then we have some d in D such that x in d /\  y in d and some e in D such that y in d /\  z in d. Since y in d and y in e, Proposition Disjoint Equivalence Classes gives us d = e and thus x ~ D z.

As shown above, equivalence relations and partitions are just different notions for the same concept; we can always construct from one description the other one. Actually, each construction is the inverse of the other one as stated by the following result (which can be easily proved).


Proposition 121 (Equivalence Relations and Partitions) Let R be an equivalence relation on S. Then R is the relation induced by the quotient set of S with respect to R:
forall S, R: R is equivalence relation on S =>
   R = ~ S/R.
Let D be a partition of S. Then D is the quotient set of the relation induced by D:
forall S, D: D is partition of S =>
   D = S/ ~ D.

Logic Evaluator  We can implement the new notions as shown below, see Appendix equiv.txt.

The partitioning of sets into equivalence classes is an important methodology with many applications some of which are demonstrated in the following subsections.


Author: Wolfgang Schreiner
Last Modification: October 4, 1999

previous up next