---- > [!definition] Definition. ([[equivalence relation]]) > An **equivalence relation** on a set $A$ is a [[relation]] $\sim$ on $A$ satisfying >1. (Reflexivity) $x \sim x$ for all $x \in A$; >2. (Symmetry) $x \sim y \implies y \sim x$; >3. (Transitivity) $x \sim y$ and $y \sim z \implies x \sim z$. > **Remark.** Keep in mind that $\sim$, being a [[relation]], is a set! \ The [[equivalence relation]] **generated by** a [[relation]] is defined to be the smallest [[equivalence relation]] containing it. > [!basicnonexample] > Let $P$ denote the set of all people. The *descendent relation* $B \subset P \times P$ given by $B=\{ (x,y): x \text{ is a descendent of }y \}$ is not symmetric, and the *blood relation* $D=\{ (x,y) : x \text{ and }y \text{ share an ancestor}\}$ is not transitive. > [!basicexample] > The *sibling relation* $S \subset P \times P$ given by $S:= \{ (x,y): \text{ the parents of } x \text{ are those of } y \}$ is an **equivalence relation** on $P$. > [!basicexample] > Let $\sim$ be the [[relation]] on $\mathbb{R}$ such that for all $x,y \in \mathbb{R}$, we have $x \sim y$ if and only if there exists $k \in \mathbb{Z}$ s.t. $x=y+k$. > We show that $\sim$ is an [[equivalence relation]]: >1. Given $x \in \mathbb{R}$, set $k=0 \in \mathbb{Z}$ to witness $x \sim x$. >2. Let $x \sim y$; fix $k \in \mathbb{Z}$ s.t. $x=y+k$. Then $y=x + (-k)$ for $(-k) \in \mathbb{Z}$ and thus $y \sim x$. >3. Let $x,y,z \in \mathbb{R}$ and suppose $x \sim y$ and $y \sim z$: fix $k_{1},k_{2}$ s.t. $x=y+k_{1}$ and $y=z+k_{2}$. Then $x=z+(k_{1}+k_{2})$ for $(k_{1}+k_{2}) \in \mathbb{Z}$ and thus $x \sim z$. ^c896ee > [!basicexample] > How many equivalence relations can be placed on the set $\{ 1,2,3 \}$? To begin, an [[equivalence relation]] must shade the diagonal: > $\begin{matrix}* & 0 & 0 \\ 0 & * & 0 \\ 0 & 0 & * \end{matrix}.$ One [[equivalence relation]] is the one which stops there: declares $1 \sim 1$, $2 \sim 2$, $3 \sim 3$, but nothing else. Three more relations are those which declare additionally (solely) that $1 \sim 2$ (or $2 \sim 1$): $\begin{matrix} * & * & 0 \\ * & * & 0 \\ 0 & 0 & * \end{matrix}$ that $2 \sim 3$ (or $3 \sim 2$): $\begin{matrix}* & 0 & 0 \\0 & * & * \\ 0 & * & * \end{matrix}$ or that $1 \sim 3$ (or $3 \sim 1$): > $\begin{matrix}* & 0 & * \\0 & * & 0 \\* & 0 & * \end{matrix}.$ We can see that in these last three figures, adding another $*$ will give 'three in a row' (or column), from which transitivity shall enforce that actually the whole array must be filled: $\begin{matrix} * & * & * \\ * & * & * \\ * & * & * \end{matrix}.$ We conclude that there are $\textcolor{Thistle}{5}$ possible [[equivalence relation|equivalence relations]] to place an a $3$-element set. > Alternatively, using [[partitions are always determined uniquely by equivalence relations]], one could list out all the possible partitions on three elements (of which there are 5). ^basic-example ---- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```