Example

The relation $x = y$ is symmetric and transitive. The relation $X \subset Y$ is transitive but not symmetric. The relation $X \cap Y = \emptyset$ is symmetric but not transitive.

If $R\{x, y\}$ is both symmetric and transitive it is said to be an equivalence relation (with respect to the letters $x$ and $y$). In this case the notation $x \equiv y \pmod{R}$ is sometimes used as a synonym of $R\{x, y\}$; it is read "*x is equivalent to y modulo* $R$". If $R$ is an equivalence relation, we have $R\{x, y\} \Rightarrow (R\{x, x\}$ and $R\{y, y\})$, because $R\{x, y\}$ implies $R\{y, x\}$, and $(R\{x, y\}$ and $R\{y, x\})$ implies $(R\{x, x\}$ and $R\{y, y\})$ by virtue of the definitions.

¶ Let $R\{x, y\}$ be a relation; it is said to be reflexive on $E$ (with respect to the letters $x, y$) if the relation $R\{x, x\}$ is equivalent to $x \in E$. If there is no possible ambiguity about $E$, one says simply, by abuse of language, that $R$ is reflexive.

¶ An equivalence relation on $E$ is defined to be an equivalence relation which is reflexive on $E$. If $R\{x, y\}$ is an equivalence relation on $E$, we have $R\{x, y\} \Rightarrow ((x, y) \in E \times E)$, hence $R$ has a graph (with respect to the letters $x, y$). Conversely, suppose that the equivalence relation $R\{x, y\}$ has a graph $G$. Observe that the relation $R\{x, x\}$ is equivalent to the relation $(\exists y)R\{x, y\}$; for the former implies the latter (Chapter I, § 4, no. 2, scheme S5), and conversely, since $R\{x, y\}$ implies $R\{x, x\}$, $(\exists y) R\{x, y\}$ implies $(\exists y) R\{x, x\}$ and therefore also $R\{x, x\}$. Thus $R\{x, x\}$ is equivalent to $x \in \mathrm{pr}_1 G$, and hence $R$ is an equivalence relation on $\mathrm{pr}_1 G$.

¶ An equivalence on a set E is a correspondence whose source and target are both equal to E, and whose graph F is such that the relation $(x, y) \in F$ is an equivalence relation on E.

Examples