Proposition 1

A correspondence $\Gamma$ between X and X is an equivalence on X if and only if it satisfies the following conditions : (a) X is the domain of $\Gamma$; (b) $\Gamma = \overset{-1}{\Gamma}$; (c) $\Gamma \circ \Gamma = \Gamma$. Let $\Gamma$ be a correspondence between X and X, and let G be its graph. If $\Gamma$ is an equivalence on X, then $(x, x) \in G$ for all $x \in X$; hence X is the domain of $\Gamma$. The relation $(x, y) \in G$ is equivalent to $(y, x) \in G$, hence to $(x, y) \in \overset{-1}{G}$, so that $G = \overset{-1}{G}$ and therefore $\Gamma = \overset{-1}{\Gamma}$. The relations $(x, y) \in G$ and $(y, z) \in G$ imply $(x, z) \in G$, so that $G \circ G \subset G$; conversely, $(x, y) \in G$ implies $(x, x) \in G$ and therefore $(x, y) \in G \circ G$, so that $G \subset G \circ G$; hence $G = G \circ G$ and consequently $\Gamma = \Gamma \circ \Gamma$. ¶ Conversely, suppose that conditions (a), (b), and (c) are satisfied. The relation $(x, y) \in G$ is symmetric (by (b)) and transitive (by (c)); hence it is an equivalence relation, and by (a) it is an equivalence relation on X.