Equivalence Relation

EQV#DEF. Equivalence Relation.

A binary relation $\sim$ on $X$ is an equivalence relation if:

1. Reflexivitiy. For all $x\in X$,

   \[x \sim x.\]

2. Symmetry. For all $x$, $y\in X$,

   \[x\sim y \enspace\rimp\enspace y\sim x.\]

3. Transitivity. For all $x$, $y$, $z\in X$,

   \[x\sim y \,\land\, y\sim z \enspace\rimp\enspace x\sim z.\]

EQV#DEF-CLS. Equivalence Class.

Let $\sim$ be an equivalence relation on $X$ and $a\in X$. The equivalence class of $a$ with respect to $\sim$ is

\[[a]_\sim = \{x\in X:a\sim x\}.\]

If there is no ambiguity, $[a]_\sim$ can be simply written as $[a]$.

EQV#DEF-QUO. Quotient Set.

Let $\sim$ be an equivalence relation on $X$. The quotient set of $X$ by $\sim$ is the set

\[X/{\sim} \enspace=\enspace \{[x]:x\in X\}\]

(“$X$ modulo $\sim$”).

EQV#PROP-E.

Let $\sim$ be an equivalence relation on $X$ and $x$, $y\in X$. The following statements are equivalent:

1. \[x \sim y.\]
2. \[[x] = [y].\]
3. \[x \in [y].\]
4. \[[x]\cap[y] \neq \varnothing.\]