7.S: Equivalence Relations (Summary)

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$.