7.S: Equivalence Relations (Summary)

Last updated
Save as PDF

Page ID: 86141

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

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