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}}} \)\(\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}}\)
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\).