Skip to main content
\(\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}}\)
Mathematics LibreTexts

7.S: Equivalence Relations (Summary)

  • Page ID
    7079
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    Important Definitions

    • Relation from \(A\) to \(B\), page 364
    • Relation on \(A\), page 364
    • Domain of a relation, page 364
    • Range of a relation, page 364
    • Inverse of a relation, page 373
    • Reflexive relation, page 375
    • Symmetric relation, page 375
    • Transitiverelation,page375
    • Equivalence relation, page 378
    • Equivalence class, page 391
    • Congruence class, page 392
    • Partition of a set, page 395
    • Integers modulo n, page 402
    • Addition in \(\mathbb{Z}_n\), page 404
    • Multiplication in \(\mathbb{Z}_n\), page 404

    Important Theorems and Results about Relations, Equivalence Relations, and Equivalence Classes

    • Theorem 7.6. Let \(R\) be a relation from the set \(A\) to the set \(B\). Then

      1. The domain of \(R^{-1}\) is range of \(R\). That is, dom(\(R^{-1}\)) = range(\(R\)).
      2. The range of \(R^{-1}\) is domain of \(R\). That is, range(\(R^{-1}\)) = dom(\(R\)).
      3. The inverse of \(R^{-1}\) is \(R\). That is, \((R^{-1})^{-1} = R\).
    • Theorem 7.10. Let \(n \in \mathbb{N}\) and let \(a, b \in \mathbb{Z}\). Then \(a \equiv b\) (mod \(n\) if and only if \(a\) and \(b\) have the same remainder when divided by \(n\).
    • Theorem 7.14. Let \(A\) be a nonempty set and let \(\sim\) be an equivalence relation on \(A\).

      1. For each \(a \in A\), \(a \in [a]\).
      2. For each \(a, b \in A\), \(a \sim b\) if and only if \([a] = [b]\).
      3. For each \(a, b \in A\), \([a] = [b]\) or \([a] \cap [b] = \emptyset\).
    • Corollary 7.16. Let \(n \in \mathbb{N}\). For each \(a \in \mathbb{Z}\), let [\(a\)] represent the congruence class of \(a\) modulo \(n\).

      1. For each \(a \in \mathbb{Z}\), \(a \in [a]\).
      2. For each \(a, b \in \mathbb{Z}\), \(a \equiv b\) (mod \(n\)) if and only if \([a] = [b]\).
      3. For each \(a, b \in \mathbb{Z}\), \([a] = [b]\) or \([a] \cap [b] = \emptyset\).
    • Corollary 7.17. Let \(n \in \mathbb{N}\). For each \(a \in \mathbb{Z}\), let [\(a\)] represent the congruence class of \(a\) modulo \(n\).

      1. \(\mathbb{Z} = [0] \cup [1] \cup [2] \cup \cdot\cdot\cdot \cup [n - 1]\)
      2. For \(j, k \in \{0, 1, 2, ..., n - 1\}\), if \(j \ne k\), then \([j] \cap [k] = \emptyset\).
    • Theorem 7.18. Let \(\sim\) be an equivalence relation on the nonempty set \(A\). Then the collection \(\mathcal{C}\) of all equivalence classes determined by \(\sim\) is a partition of the set \(A\).