Calculus

Set Theory

Set Theory Logo

Equivalence Classes and Partitions

Equivalence Classes

Definitions

Let \(R\) be an equivalence relation on a set \(A,\) and let \(a \in 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 \(\left[ a \right].\) Thus, by definition,

\[{\left[ a \right] = \left\{ {b \in A \mid aRb} \right\} }={ \left\{ {b \in A \mid a \sim b} \right\}.}\]

If \(b \in \left[ a \right]\) then the element \(b\) is called a representative of the equivalence class \(\left[ a \right].\) Any element of an equivalence class may be chosen as a representative of the class.

The set of all equivalence classes of \(A\) is called the quotient set of \(A\) by the relation \(R.\) The quotient set is denoted as \(A/R.\)

\[A/R = \left\{ {\left[ a \right] \mid a \in A} \right\}.\]

Properties of Equivalence Classes

If \(R \) (also denoted by \(\sim\)) is an equivalence relation on set \(A,\) then

  • Every element \(a \in A\) is a member of the equivalence class \(\left[ a \right].\) \[\forall\, a \in A,a \in \left[ a \right]\]
  • Two elements \(a, b \in A\) are equivalent if and only if they belong to the same equivalence class. \[\forall\, a,b \in A,a \sim b \text{ iff } \left[ a \right] = \left[ b \right]\]
  • Every two equivalence classes \(\left[ a \right]\) and \(\left[ b \right]\) are either equal or disjoint. \[\require{AMSsymbols}{\forall\, a,b \in A,\left[ a \right] = \left[ b \right] \text{ or } \left[ a \right] \cap \left[ b \right] = \varnothing}\]

Example

A well-known sample equivalence relation is Congruence Modulo \(n\). Two integers \(a\) and \(b\) are equivalent if they have the same remainder after dividing by \(n.\)

Consider, for example, the relation of congruence modulo \(3\) on the set of integers \(\mathbb{Z}:\)

\[R = \left\{ {\left( {a,b} \right) \mid a \equiv b\;\left( \kern-2pt{\bmod 3} \right)} \right\}.\]

The possible remainders for \(n = 3\) are \(0,1,\) and \(2.\) An equivalence class consists of those integers that have the same remainder. Hence, there are \(3\) equivalence classes in this example:

\[\left[ 0 \right] = \left\{ { \ldots , – 9, – 6, – 3,0,3,6,9, \ldots } \right\}\]

\[\left[ 1 \right] = \left\{ { \ldots , – 8, – 5, – 2,1,4,7,10, \ldots } \right\}\]

\[\left[ 2 \right] = \left\{ { \ldots , – 7, – 4, – 1,2,5,8,11, \ldots } \right\}\]

Similarly, one can show that the relation of congruence modulo \(n\) has \(n\) equivalence classes \(\left[ 0 \right],\left[ 1 \right],\left[ 2 \right], \ldots ,\left[ {n – 1} \right].\)

Partitions

Let \(A\) be a set and \({A_1},{A_2}, \ldots ,{A_n}\) be its non-empty subsets. The subsets form a partition \(P\) of \(A\) if

  • The union of the subsets in \(P\) is equal to \(A.\) \[\bigcup\limits_{i = 1}^n {{A_i}} = {A_1} \cup {A_2} \cup \ldots \cup {A_n} = A\]
  • The partition \(P\) does not contain the empty set \(\varnothing.\) \[{A_i} \ne \varnothing \;\forall \,i\]
  • The intersection of any distinct subsets in \(P\) is empty. \[{A_i} \cap {A_j} = \varnothing \;\forall \,i \ne j\]
Partition of a set A.
Figure 1.

There is a direct link between equivalence classes and partitions. For any equivalence relation on a set \(A,\) the set of all its equivalence classes is a partition of \(A.\)

The converse is also true. Given a partition \(P\) on set \(A,\) we can define an equivalence relation induced by the partition such that \(a \sim b\) if and only if the elements \(a\) and \(b\) are in the same block in \(P.\)


Solved Problems

Click or tap a problem to see the solution.

Example 1

Which of the following collections of subsets are partitions of \(\left\{ {0,1,2,3,4,5} \right\}?\)
  1. \(\left\{ {0,1,2} \right\},\left\{ {4,3} \right\},\left\{ {5,4} \right\}\)
  2. \(\left\{{}\right\},\left\{ {0,2,1} \right\},\left\{ {4,3,5} \right\}\)
  3. \(\left\{ {5,4,0,3} \right\},\left\{ 2 \right\},\left\{ 1 \right\}\)
  4. \(\left\{ 5 \right\},\left\{ {4,3} \right\},\left\{ {0,2} \right\}\)
  5. \(\left\{ 2 \right\},\left\{ 1 \right\},\left\{ 5 \right\},\left\{ 3 \right\},\left\{ 0 \right\},\left\{ 4 \right\}\)

Example 2

List all the partitions of the following sets:
  1. \(A = \left\{ {1,2} \right\}\)
  2. \(B = \left\{ {1,2,3} \right\}\)

Example 3

List the ordered pairs in the equivalence relation \(R\) induced by the partition \(P = \left\{ {\left\{ {a,b,c} \right\},\left\{ d \right\},\left\{ e \right\}} \right\}\) of the set \(\left\{ {a,b,c,d,e} \right\}.\)

Example 4

A relation \(R\) on the set \(A = \left\{ {a,b,c,d,e} \right\}\) is defined as follows: \(R = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {b,a} \right),\left( {b,b} \right),\left( {c,c} \right),}\right.\) \(\kern-2pt\left.{\left( {c,d} \right),\left( {c,e} \right),}\right.\) \(\kern-2pt\left.{\left( {d,c} \right),\left( {d,d} \right),}\right.\) \(\kern-2pt\left.{\left( {d,e} \right),\left( {e,c} \right),}\right.\) \(\kern-2pt\left.{\left( {e,d} \right),\left( {e,e} \right)} \right\}.\)
Determine the equivalence classes of \(R.\)

Example 5

The relation \(R = \left\{ {\left( {a,b} \right) \mid \left| {a + 1} \right| = \left| {b + 1} \right|} \right\}\) is defined on the set of integers \(\mathbb{Z}.\) Find the equivalence classes for \(R.\)

Example 6

Suppose \(R\) is an equivalence relation on a finite set \(A,\) and every equivalence class has the same cardinality \(m.\) Express the cardinality of the relation \(\left| R \right|\) in terms of \(\left| A \right|\) and \(m.\)

Example 1.

Which of the following collections of subsets are partitions of \(\left\{ {0,1,2,3,4,5} \right\}?\)
  1. \(\left\{ {0,1,2} \right\},\left\{ {4,3} \right\},\left\{ {5,4} \right\}\)
  2. \(\left\{{}\right\},\left\{ {0,2,1} \right\},\left\{ {4,3,5} \right\}\)
  3. \(\left\{ {5,4,0,3} \right\},\left\{ 2 \right\},\left\{ 1 \right\}\)
  4. \(\left\{ 5 \right\},\left\{ {4,3} \right\},\left\{ {0,2} \right\}\)
  5. \(\left\{ 2 \right\},\left\{ 1 \right\},\left\{ 5 \right\},\left\{ 3 \right\},\left\{ 0 \right\},\left\{ 4 \right\}\)

Solution.

  1. The collection of subsets \(\left\{ {0,1,2} \right\},\left\{ {4,3} \right\},\left\{ {5,4} \right\}\) is not a partition of \(\left\{ {0,1,2,3,4,5} \right\}\) since the element \(4\) is contained in two blocks.
  2. The subsets \(\left\{{}\right\},\left\{ {0,2,1} \right\},\left\{ {4,3,5} \right\}\) are not a partition because they have the empty set.
  3. The collection of subsets \(\left\{ {5,4,0,3} \right\},\left\{ 2 \right\},\left\{ 1 \right\}\) is a partition of \(\left\{ {0,1,2,3,4,5} \right\}.\)
  4. The subsets \(\left\{ 5 \right\},\left\{ {4,3} \right\},\left\{ {0,2} \right\}\) are not a partition of \(\left\{ {0,1,2,3,4,5} \right\}\) because the element \(1\) is missing.
  5. The subsets \(\left\{ 2 \right\},\left\{ 1 \right\},\left\{ 5 \right\},\left\{ 3 \right\},\left\{ 0 \right\},\left\{ 4 \right\}\) form a partition of the set \(\left\{ {0,1,2,3,4,5} \right\}.\)

Example 2.

List all the partitions of the following sets:
  1. \(A = \left\{ {1,2} \right\}\)
  2. \(B = \left\{ {1,2,3} \right\}\)

Solution.

  1. The set \(A = \left\{ {1,2} \right\}\) has \(2\) partitions: \[\left\{ 1 \right\},\left\{ 2 \right\}\] \[\left\{ {1,2} \right\}\]
  2. The set \(B = \left\{ {1,2,3} \right\}\) has \(5\) partitions: \[\left\{ 1 \right\},\left\{ 2 \right\},\left\{ 3 \right\}\] \[\left\{ {1,2} \right\},\left\{ 3 \right\}\] \[\left\{ {1,3} \right\},\left\{ 2 \right\}\] \[\left\{ 1 \right\},\left\{ {2,3} \right\}\] \[\left\{ {1,2,3} \right\}\]

Example 3.

List the ordered pairs in the equivalence relation \(R\) induced by the partition \(P = \left\{ {\left\{ {a,b,c} \right\},\left\{ d \right\},\left\{ e \right\}} \right\}\) of the set \(\left\{ {a,b,c,d,e} \right\}.\)

Solution.

The partition \(P\) includes \(3\) subsets which correspond to \(3\) equivalence classes of the relation \(R.\) We can denote these classes by \(E_1,\) \(E_2,\) and \(E_3.\) They contain the following pairs:

\[{{E_1} = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {a,c} \right),}\right.}\kern0pt{\left.{\left( {b,a} \right),\left( {b,b} \right),}\right.}\kern0pt{\left.{\left( {b,c} \right),\left( {c,a} \right),}\right.}\kern0pt{\left.{\left( {c,b} \right),\left( {c,c} \right)} \right\}}\]

\[{E_2} = \left\{ {d,d} \right\}\]

\[{E_3} = \left\{ {e,e} \right\}\]

So, the relation \(R\) in roster form is given by

\[{R = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {a,c} \right),}\right.}\kern0pt{\left.{\left( {b,a} \right),\left( {b,b} \right),}\right.}\kern0pt{\left.{\left( {b,c} \right),\left( {c,a} \right),}\right.}\kern0pt{\left.{\left( {c,b} \right),\left( {c,c} \right),}\right.}\kern0pt{\left.{\left( {d,d} \right),\left( {e,e} \right)} \right\}.}\]

Example 4.

A relation \(R\) on the set \(A = \left\{ {a,b,c,d,e} \right\}\) is defined as follows: \(R = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {b,a} \right),\left( {b,b} \right),\left( {c,c} \right),}\right.\) \(\kern-2pt\left.{\left( {c,d} \right),\left( {c,e} \right),}\right.\) \(\kern-2pt\left.{\left( {d,c} \right),\left( {d,d} \right),}\right.\) \(\kern-2pt\left.{\left( {d,e} \right),\left( {e,c} \right),}\right.\) \(\kern-2pt\left.{\left( {e,d} \right),\left( {e,e} \right)} \right\}.\)
Determine the equivalence classes of \(R.\)

Solution.

First we check that \(R\) is an equivalence relation.

\(R\) is reflexive since it contains all identity elements \(\left( {a,a} \right),\left( {b,b} \right), \ldots ,\left( {e,e} \right).\)

\(R\) is symmetric. For each non-reflexive element its reverse also belongs to \(R:\)

\[{\left( {a,b} \right),\left( {b,a} \right) \in R,\;\;}\kern0pt{\left( {c,d} \right),\left( {d,c} \right) \in R,\;\; \ldots }\]

\(R\) is transitive. For example, the relation contains the overlapping pairs \(\left( {a,b} \right),\left( {b,a} \right)\) and the element \(\left( {a,a} \right).\) Thus, we conclude that \(R\) is an equivalence relation.

Consider the elements related to \(a.\) The relation \(R\) contains the pairs \(\left( {a,a} \right)\) and \(\left( {a,b} \right).\) Hence \(a\) and \(b\) are related to \(a.\) Similarly we find that \(a\) and \(b\) related to \(b.\) There are no other pairs in \(R\) containing \(a\) or \(b.\) So these items form the equivalence class \(\left\{ {a,b} \right\}.\) Notice that the relation \(R\) has \(2^2=4\) ordered pairs within this class.

Take the next element \(c\) and find all elements related to it. There are \(3\) pairs with the first element \(c:\) \({\left( {c,c} \right),}\) \({\left( {c,d} \right),}\) \({\left( {c,e} \right).}\) Similarly, we find pairs with the elements related to \(d\) and \(e:\) \({\left( {d,c} \right),}\) \({\left( {d,d} \right),}\) \({\left( {d,e} \right),}\) \({\left( {e,c} \right),}\) \({\left( {e,d} \right),}\) and \({\left( {e,e} \right).}\) This set of \(3^2 = 9\) pairs corresponds to the equivalence class \(\left\{ {c,d,e} \right\}\) of \(3\) elements.

Thus, the relation \(R\) has \(2\) equivalence classes \(\left\{ {a,b} \right\}\) and \(\left\{ {c,d,e} \right\}.\)

Example 5.

The relation \(R = \left\{ {\left( {a,b} \right) \mid \left| {a + 1} \right| = \left| {b + 1} \right|} \right\}\) is defined on the set of integers \(\mathbb{Z}.\) Find the equivalence classes for \(R.\)

Solution.

It’s easy to make sure that \(R\) is an equivalence relation. The equivalence classes of \(R\) are defined by the expression \(\left\{ { – 1 – n, – 1 + n} \right\},\) where \(n\) is an integer.

Below are some examples of the classes \(E_n\) for specific values of \(n\) and the corresponding pairs of the relation \(R\) for each of the classes:

\[{n = 0:\;{E_0} = \left[ { – 1} \right] = \left\{ { – 1} \right\},\;}\kern0pt{{R_0} = \left\{ {\left( { – 1, – 1} \right)} \right\}}\]

\[{n = 1:\;{E_1} = \left[ { – 2} \right] = \left\{ { – 2,0} \right\},\;}\kern0pt{{R_1} = \left\{ {\left( { – 2, – 2} \right),\left( { – 2,0} \right),}\right.}\kern0pt{\left.{\left( {0, – 2} \right),\left( {0,0} \right)} \right\}}\]

\[{n = 2:\;{E_2} = \left[{ – 3} \right] = \left\{ { – 3,1} \right\},\;}\kern0pt{{R_2} = \left\{ {\left( { – 3, – 3} \right),\left( { – 3,1} \right),}\right.}\kern0pt{\left.{\left( {1, – 3} \right),\left( {1,1} \right)} \right\}}\]

\[{n = – 2:\;{E_{ – 2}} = \left[ 1 \right] = \left\{ {1, – 3} \right\},\;}\kern0pt{{R_{ – 2}} = \left\{ {\left( {1,1} \right),\left( {1, – 3} \right),}\right.}\kern0pt{\left.{\left( { – 3,1} \right),\left( { – 3, – 3} \right)} \right\}}\]

\[{n = 10:\;{E_{10}} = \left[ { – 11} \right] = \left\{ { – 11,9} \right\},\;}\kern0pt{{R_{10}} = \left\{ {\left( { – 11, – 11} \right),\left( { – 11,9} \right),}\right.}\kern0pt{\left.{\left( {9, – 11} \right),\left( {9,9} \right)} \right\}}\]

\[{n = – 10:\;{E_{ – 10}} = \left[ { – 11} \right] = \left\{ {9, – 11} \right\},\;}\kern0pt{{R_{ – 10}} = \left\{ {\left( {9,9} \right),\left( {9, – 11} \right),}\right.}\kern0pt{\left.{\left( { – 11,9} \right),\left( { – 11, – 11} \right)} \right\}}\]

As it can be seen, \({E_{2}} = {E_{- 2}},\) \({E_{10}} = {E_{ – 10}}.\) It follows from here that we can list all equivalence classes for \(R\) by using non-negative integers \(n.\)

Example 6.

Suppose \(R\) is an equivalence relation on a finite set \(A,\) and every equivalence class has the same cardinality \(m.\) Express the cardinality of the relation \(\left| R \right|\) in terms of \(\left| A \right|\) and \(m.\)

Solution.

Consider an equivalence class consisting of \(m\) elements.

The relation \(R\) is symmetric and transitive. Therefore each element of an equivalence class has a direct path of length \(1\) to another element of the class. This gives us \(m\left( {m – 1} \right)\) edges or ordered pairs within one equivalence class.

The relation \(R\) is reflexive. This adds \(m\) more pairs, so the total number of ordered pairs within one equivalence class is

\[\require{cancel}{m\left( {m – 1} \right) + m }={ {m^2} – \cancel{m} + \cancel{m} }={ {m^2}.}\]

Determine now the number of equivalence classes in the relation \(R.\) Since the classes form a partition of \(A,\) and they all have the same cardinality \(m,\) the total number of elements in \(A\) is equal to

\[\left| A \right| = nm,\]

where \(n\) is the number of classes in \(R.\)

Hence, the number of pairs in the relation \(R\) is given by

\[{\left| R \right| = n{m^2} }={ \frac{{\left| A \right|}}{\cancel{m}}{m^{\cancel{2}}} }={ \left| A \right|m.}\]