Let \(A\) be a non-empty set, and let \(R\) be a relation on \(A\text{.}\)
The relation \(R\) is reflexive if \(x R x\text{,}\) for all \(x\in A\text{.}\)
The relation \(R\) is symmetric if \(x R y\) implies \(y R x\text{,}\) for all \(x, y\in A\text{.}\)
The relation \(R\) is transitive if \(x R y\) and \(y R z\) imply \(x R z\text{,}\) for all \(x, y, z\in A\text{.}\)
Example4.25.
The relation \(\leq \) on \(R\) is reflexive and transitive, but not symmetric.
The relation of one person being the cousin of another is symmetric, but neither reflexive nor transitive.
The relation of one person being the daughter of another person is neither reflexive, symmetric nor transitive.
Definition4.26.
Let \(A\) be a set, and let \(\sim \) be a relation on \(A\text{.}\) The relation \(\sim \) is an equivalence relation if it is reflexive, symmetric and transitive.
Convention4.27.
We use \(\sim\) for equivalence relations.
Example4.28.
Equality
Being the same age
Corollary4.29.
Congruence module \(n\) for any \(n\in\N\) is an equivalene relation on \(\Z\text{.}\)
Definition4.30.
Let \(A\) be a non-empty set, and let \(\sim\) be an equivalence relation on \(A\text{.}\) The relation classes of \(A\) with respect to \(\sim\) are called equivalence classes.
Definition4.31.
Let \(A\) be a non-empty set, and let \(\sim\) be an equivalence relation on \(A\text{.}\) The quotient set of \(A\) with respect to \(\sim\text{,}\) denoted \(A/\sim\text{,}\) is the set defined by \(A/\sim = \{[x] | x\in A\}\text{.}\)
Definition4.32.
Let \(A\) be a non-empty set, and let \(\sim\) be an equivalence relation on \(A\text{.}\) The canonical map for \(A\) and \(\sim\) is the function \(\gamma : A \to A/\sim\) defined by \(\gamma (x) = [x]\) for all \(x\in A\text{.}\)
Definition4.33.
Let \(A\) be a non-empty set. A partition of \(A\) is a family \(\cD\) of non-empty subsets of \(A\) such that
if \(P, Q\in\cD\) and \(P \neq Q\text{,}\) then \(P \cap Q = \es\text{;}\)
\(\bigcup _{P\in \cD} P = A\text{.}\)
Example4.34.
Let \(\E\) denote the set of even integers, and let \(\O\) denote the set of odd integers. Then \(\cD = {\E, \O}\) is a partition of \(\Z\text{.}\)
Let \(\cC = \{[n, n + 1)\}_{n\in \Z}\text{.}\) Then \(C\) is a partition of \(\R\text{.}\)
Let \(\cG = \{(n - 1, n + 1)\}_{n\in \Z}\text{.}\) Then \(G\) is not a partition of \(\R\text{,}\) because it is not pairwise disjoint. For example, we observe that \((1 - 1, 1 + 1) \cap (2 - 1, 2 + 1) = (1, 2)\text{.}\)
Theorem4.35.
Let \(A\) be a non-empty set, and let \(\sim\) be an equivalence relation on \(A\text{.}\) Then \(A/\sim\) is a partition of \(A\text{.}\)
Corollary4.36.
Let \(A\) be a non-empty set, let \(\sim\) be an equivalence relation on \(A\) and let \(x, y\in A\text{.}\) Then \([x] = [y]\) if and only if \(x \sim y\text{.}\)
