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, 즉 동치 관계는 사실상 두 원소가 같음을 보장해주는 관계로 이해할 수 있다.
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$.