Equivalence Relation
Definition 1. Let $R$ be a relation in a set $X$. Then we say that
(a) $R$ is reflexive $\iff$ $\forall x \in X, xRx$.
(b) $R$ is symmetric $\iff$ $xRy \Longrightarrow yRx$.
(c) $R$ is transitive $\iff$ $xRy \wedge yRz \Longrightarrow xRz$.
(d) $R$ is an equivalence relation $\iff$ $R$ is reflexive, symmetric, and transitive.
Equivalence relation, 즉 동치 관계는 특정한 수학적 관점에서 볼 때 두 원소가 사실상 같음을 보장해주는 관계로 이해할 수 있다. 예컨대 $\equiv$ (mod $3$)는 동치 관계인데, 합동이라는 관점에서 볼 때 $5$와 $2$는 합동이고 같은 성질을 공유하므로 사실상 같은 원소로 생각할 수 있다는 것이다.
Example
Given a nonempty set $X$, there always exist at least two equivalence relations in $X$.
(1) The smallest of all the equivalence relations is the diagonal relation $\Delta_X$ (also called the identity relation), defined by $\Delta_X = \{ (x, x) | x \in X \}$.
(2) The largest of all the equivalence relations is $R = X \times X$ on $X$.