Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 6.2.2 Equivalence classes and partitions

Definition 6.2.2.1.

Let \(R\) be an equivalence relation on \(A\text{,}\) and let \(a\) be an element of \(A\text{.}\) The equivalence class of \(a\text{,}\) denoted \([a]_R\) is the set of elements that are related to \(a\text{.}\) In other words,
\begin{equation*} [a] = \{b \in A \given a\,R\,b\}. \end{equation*}
🔗
🔗

Remark 6.2.2.2.

Since equivalence relations are symmetric, this is the same as
\begin{equation*} [a] = \{b \in A \given bRa\}. \end{equation*}
🔗
🔗

Example 6.2.2.3. Congruence classes.

Let \(R\) denote the congruent modulo \(7\) equivalence relation. That is, \(a\,R\,b\) when \(a\equiv b\pmod{7}\text{.}\) Then
\begin{align*} [0] \amp = \{\dots, -14, -7, 0, 7, 14, \dots\} \\ [14] \amp = \{\dots, -14, -7, 0, 7, 14, \dots\} \\ [3] \amp = \{\dots, -11, -4, 3, 10, 17, \dots\} \end{align*}
We \([a] = [a']\) precisely when \(aRa'\text{.}\)
🔗
Equivalence classes of this kind are called congruence classes 5.1.2.4.
🔗
🔗

Definition 6.2.2.4.

A partition of a set \(A\) is a collection of non-empty subsets \(A_i \subseteq A\text{,}\) \(i \in I\text{,}\) such that
  1. \(A_i \cap A_j = \emptyset\) for all \(i \neq j\text{;}\)
    🔗
    🔗
  2. \(\displaystyle{A = \bigcup_{i \in I} A_i}\text{.}\)
    🔗
    🔗
🔗
🔗
Figure 6.2.2.5. Partition of a set into the sets \(A_1\text{,}\) \(A_2\text{,}\) \(A_3\text{,}\) \(A_4\text{,}\) and \(A_5\text{.}\)
🔗

Proof.

We prove \(1 \implies 2 \implies 3 \implies 1\text{.}\)
\(1 \implies 2\)
🔗
Suppose \(a \sim b\text{.}\) Let \(c \in [a]\text{.}\) Then \(c \sim a\text{.}\) By transitivity, we have \(c \sim b\text{.}\) Thus \(c \in [b]\text{.}\) Therefore \([a] \subseteq [b]\text{.}\) Now let \(c \in [b]\text{.}\) Then \(b \sim c\text{.}\) By transitivity, we have \(a \sim c\text{.}\) Thus \(c \in [a]\text{.}\) Therefore \([b] \subseteq [a]\text{.}\) Then \([a] = [b]\text{,}\) as desired.
🔗
\(2 \implies 3\)
🔗
Suppose \([a] = [b]\text{.}\) Since \(\sim\) is reflexive, \(a\in [a]\text{,}\) so \([a]\neq\emptyset\text{.}\) Then \([a] \cap [b] = [a]\text{.}\)
🔗
\(3 \implies 1\)
🔗
Suppose \([a] \cap [b] \neq \emptyset\text{.}\) Let \(c\in [a] \cap [b]\text{.}\) Then \(a \sim c\) and \(c \sim b\text{.}\)By transitivity, we have \(a \sim b\text{.}\)
🔗
🔗
🔗

Example 6.2.2.8. Same birthday.

Consider the equivalence relation \(R\) on the set of people in the world defined by \(a\,R\,b\) if and only if \(a\) has the same birthday (month and date).
🔗
Then \([\text{Thom Yorke}]\) is the set of all people with a birthday on October 7. The equivalence relation partitions the set of all people into equivalence classes, where each equivalence class contains all the people with a given birthday. Specifically, there are 366 equivalence classes (don’t forget February 29!).
🔗
🔗
Given a partition of a set \(A\text{,}\) we compute the corresponding equivalence relation \(R\) on \(A\) using the subsets in the partition as equivalence classes.
🔗

Example 6.2.2.9. Partitions.

Suppose \(A = \{1, 2, 3, 4, 5, 6\}\text{.}\) Given the partition \(A_1 = \{1, 2\}\text{,}\) \(A_2 = \{3, 5, 6\}\text{,}\) and \(A_3 = \{4\}\text{,}\) the ordered pairs in the equivalence relation \(R\) produced by this partition is
\begin{equation*} R = \{(1,1),(1, 2), (2,2), (2, 1), (3,3),(3, 5), (3, 6),(5, 3),(5,5), (6, 3), (5, 6), (6, 5), (6,6), (4,4)\}. \end{equation*}
🔗
🔗

Example 6.2.2.10. Number of equivalence relations.

How many different equivalence relations are there on \(A = \{1,2,3\}\) ?
🔗
Solution.
By Theorem 6.2.2.7, it is enough to enumerate partitions of \(A\text{.}\)
🔗
  1. \(\displaystyle A = \{1, 2, 3\}\)
    🔗
    🔗
  2. \(\displaystyle A = \{1, 2\} \cup \{3\}\)
    🔗
    🔗
  3. \(\displaystyle A = \{1\} \cup \{2, 3\}\)
    🔗
    🔗
  4. \(\displaystyle A = \{1, 3\} \cup \{2\}\)
    🔗
    🔗
  5. \(\displaystyle A = \{1\} \cup \{2\} \cup \{3\}\)
    🔗
    🔗
Thus there are five equivalence relations on \(A\text{.}\)
🔗
🔗
🔗
🔗
PrevTopNext