Calculus

Set Theory

Set Theory Logo

Equivalence Classes and Partitions

Solved Problems

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),\left( {b,a} \right),\left( {b,b} \right),\left( {b,c} \right),\left( {c,a} \right),\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),\left( {b,a} \right),\left( {b,b} \right),\left( {b,c} \right),\left( {c,a} \right),\left( {c,b} \right),\left( {c,c} \right),\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),}\right.\) \(\left( {b,b} \right),\left( {c,c} \right),\) \(\left.{\left( {c,d} \right),\left( {c,e} \right),}\right.\) \(\left.{\left( {d,c} \right),\left( {d,d} \right),}\right.\) \(\left.{\left( {d,e} \right),\left( {e,c} \right),}\right.\) \(\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,\;\;\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\},\;{R_0} = \left\{ {\left( { - 1, - 1} \right)} \right\}\]
\[n = 1:\;{E_1} = \left[ { - 2} \right] = \left\{ { - 2,0} \right\},\;{R_1} = \left\{ {\left( { - 2, - 2} \right),\left( { - 2,0} \right),\left( {0, - 2} \right),\left( {0,0} \right)} \right\}\]
\[n = 2:\;{E_2} = \left[{ - 3} \right] = \left\{ { - 3,1} \right\},\;{R_2} = \left\{ {\left( { - 3, - 3} \right),\left( { - 3,1} \right),\left( {1, - 3} \right),\left( {1,1} \right)} \right\}\]
\[n = - 2:\;{E_{ - 2}} = \left[ 1 \right] = \left\{ {1, - 3} \right\},\;{R_{ - 2}} = \left\{ {\left( {1,1} \right),\left( {1, - 3} \right),\left( { - 3,1} \right),\left( { - 3, - 3} \right)} \right\}\]
\[n = 10:\;{E_{10}} = \left[ { - 11} \right] = \left\{ { - 11,9} \right\},\;{R_{10}} = \left\{ {\left( { - 11, - 11} \right),\left( { - 11,9} \right),\left( {9, - 11} \right),\left( {9,9} \right)} \right\}\]
\[n = - 10:\;{E_{ - 10}} = \left[ { - 11} \right] = \left\{ {9, - 11} \right\},\;{R_{ - 10}} = \left\{ {\left( {9,9} \right),\left( {9, - 11} \right),\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.\]
Page 1 Page 2