Equivalence Classes and Partitions

Equivalence Classes

Definitions

Let R be an equivalence relation on a set A, and let a ∈ A. The equivalence class of a is called the set of all elements of A which are equivalent to a.

The equivalence class of an element a is denoted by [a]. Thus, by definition,

If b ∈ [a] then the element b is called a representative of the equivalence class [a]. Any element of an equivalence class may be chosen as a representative of the class.

The set of all equivalence classes of $$ is called the quotient set of $$ by the relation $$ The quotient set is denoted as $$

Properties of Equivalence Classes

If $$ (also denoted by $$) is an equivalence relation on set $$ then

• Every element $$ is a member of the equivalence class $$
  $$
• Two elements $$ are equivalent if and only if they belong to the same equivalence class.
  $$
• Every two equivalence classes $$ and $$ are either equal or disjoint.
  $$

Example

A well-known sample equivalence relation is Congruence Modulo $$. Two integers $$ and $$ are equivalent if they have the same remainder after dividing by $$

Consider, for example, the relation of congruence modulo $$ on the set of integers $$

The possible remainders for $$ are $$ and $$ An equivalence class consists of those integers that have the same remainder. Hence, there are $$ equivalence classes in this example:

Similarly, one can show that the relation of congruence modulo $$ has $$ equivalence classes $$

Partitions

Let $$ be a set and $$ be its non-empty subsets. The subsets form a partition $$ of $$ if

• The union of the subsets in $$ is equal to $$
  $$
• The partition $$ does not contain the empty set $$
  $$
• The intersection of any distinct subsets in $$ is empty.
  $$

There is a direct link between equivalence classes and partitions. For any equivalence relation on a set $$ the set of all its equivalence classes is a partition of $$

The converse is also true. Given a partition $$ on set $$ we can define an equivalence relation induced by the partition such that $$ if and only if the elements $$ and $$ are in the same block in $$