Skip to main content
Mathematics LibreTexts

7.3: Equivalence Classes

  • Page ID
    23922
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    If we are interested in first names (as in Example \(7.2.2(1)\)), then we may also be interested in the set of all people who have the same first name as you. This is called your “equivalence class.”

    Definition \(7.3.1\).

    Suppose \(\sim\) is an equivalence relation on a set \(A\). For each \(a \in A\), the equivalence class of \(a\) is the following subset of \(A\): \[[a]=\left\{a^{\prime} \in A \mid a^{\prime} \sim a\right\} .\]

    Example \(7.3.2\).

    For the equivalence relation \(N\) described in Example \(7.2.2(1)\), we have \[[\text {Justin Timberlake}] = \{ x \in \text {People } \mid \text {FirstName}(x) = \text {FirstName}(\text{Justin Timberlake}) \} .\)

    In other words, \(\text { [Justin Timberlake] }\) is the set of all people whose first name is Justin.

    WARNING.

    The notation \([a]\) does not tell us which equivalence relation is being used. This can be confusing if more than one equivalence relation is under consideration.

    Example \(7.3.3\).

    Suppose \(A=\{1,2,3,4,5\}\) and \[R=\left\{\begin{array}{c}
    (1,1),(1,3),(1,4),(2,2),(2,5),(3,1),(3,3), \\
    (3,4),(4,1),(4,3),(4,4),(5,2),(5,5)
    \end{array}\right\} .\]

    One can verify that \(R\) is an equivalence relation on \(A\). The equivalence classes are:

    Solution

    \[\begin{gathered}
    {[1]=\{1,3,4\}, \quad[2]=\{2,5\}, \quad[3]=\{1,3,4\}} \\
    {[4]=\{1,3,4\}, \quad[5]=\{2,5\}}.
    \end{gathered}\]

    Exercise \(7.3.4\).

    You do not need to show your work.

    1. Let \(B=\{1,2,3,4,5\}\) and \[S=\left\{\begin{array}{c}
      (1,1),(1,4),(2,2),(2,3),(3,2) \\
      (3,3),(4,1),(4,4),(5,5)
      \end{array}\right\} .\]
      Find the equivalence class of each element of \(B\). (You may assume without proof that \(S\) is an equivalence relation on \(B\).)
    2. Let \(C = \{1,2,3,4,5\}\) and define \(T\) by \[x T y \text { iff } x+y \text { is even. }\]
      Find the equivalence class of each element of \(C\). (You may assume without proof that \(T\) is an equivalence relation on \(C\).)

    The following theorem presents some very important properties of equivalence classes:

    Theorem \(\PageIndex{1}\)

    Suppose \(\sim\) is an equivalence relation on a set \(A\). Then:

    1. For all \(a \in A\), we have \(a \in [a]\).
    2. For all \(a \in A\), we have \([a] \neq \varnothing\).
    3. The union of the equivalence classes is all of \(A\). That is, we have \(A=\bigcup_{a \in A}[a]\), where \[\bigcup_{a \in A}[a]=\{x \mid \exists a \in A,(x \in[a])\} .\]
    4. For any \(a_{1}, a_{2} \in A\), such that \(a_{1} \sim a_{2}\), we have \([a_{1}] = [a_{2}]\).
    5. For any \(a_{1}, a_{2} \in A\), such that \(a_{1} \nsim a_{2}\), we have \(\left[a_{1}\right] \cap\left[a_{2}\right]=\varnothing\).

    Exercise \(7.3.6\).

    Prove Theorem \(7.3.5\).
    [Hint: Use the fact that \(\sim\) is reflexive, symmetric and transitive.]

    Remark \(7.3.7\).

    Suppose \(\sim\) is an equivalence relation on a set \(A\). The above theorem implies that any two equivalence classes are either equal or disjoint; that is, either they have exactly the same elements, or they have no elements in common.

    Proof

    Given two equivalence classes \([a_{1}]\) and \([a_{2}]\) that are not disjoint, we wish to show \([a_{1}] = [a_{2}]\). Since the equivalence classes are not disjoint, their intersection is nonempty, thus, there is some \(a \in\left[a_{1}\right] \cap\left[a_{2}\right]\). Hence, \(a \in [a_{1}]\) and \(a \in [a_{2}]\). By definition of the equivalence classes, this means \(a \sim a_{1}\) and \(a \sim a_{2}\). Hence, Theorem \(7.3.5(4)\) tells us that \([a] = [a_{1}]\) and \([a] = [a_{2}]\). Therefore \([a_{1}] = [a] = [a_{2}]\), as desired


    This page titled 7.3: Equivalence Classes is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.

    • Was this article helpful?