Section B.13 Equivalence Relations
A binary relation \(R\) is symmetric if \((x,y)\in R\) implies \((y,x)\in R\) for all \(x,y\in X\text{.}\)
A binary relation \(R\) on a set \(X\) is called an equivalence relation when it is reflexive, symmetric, and transitive. Typically, symbols like, \(=\text{,}\) \(\cong\text{,}\) \(\equiv\) and \(\sim\) are used to denote equivalence relations. An equivalence relation, say \(\cong\text{,}\) defines a partition on the set \(X\) by setting
\begin{equation*}
\langle x\rangle =\{y\in X: x\cong y\}.
\end{equation*}
Note that if \(x,y\in X\) and \(\langle x\rangle\cap\langle y\rangle \neq\emptyset\text{,}\) then \(\langle x\rangle=\langle y\rangle\text{.}\) The sets in this partition are called equivalence classes.
When using the ordered pair notation for binary relations, to indicate that a pair \((x,y)\) is not in the relation, we simply write \((x,y)\notin R\text{.}\) When using the alternate notation, this is usually denoted by using the negation symbol from logic and writing \(\lnot (xRy)\text{.}\) Many of the special symbols used to denote equivalence relations come with negative versions: \(x\neq y\text{,}\) \(x\ncong y\text{,}\) \(x\nsim y\text{,}\) etc.
