Relations

Definition. A relation $R$ on $X$ specifies some kind of relationship between two elements in the set. Formally, a relation is a subset $R \subseteq X \times X$. We write $xRy$ iff $(x, y) \in R$.

Definition. A relation is reflexive if

\[(\forall x)\, xRx\]

Definition. A relation is symmetric if

\[(\forall x, y)\, xRy \iff yRx\]

Definition. A relation is antisymmetric if

\[(\forall x, y)\, xRy \land yRx \implies x = y\]

Definition. A relation is transitive if

\[(\forall x, y, z)\, xRy \land yRz \implies xRz\]

Equivalence Relation

Definition. An equivalence relation is a relation that is reflexive, symmetric and transitive.

Definition. Let $\sim$ be an equivalence relation on $X$. The equivalence class, denoted by $[x]$, is the set of all elements that are related to $x$ by $\sim$.

Lemma. Any two equivalence classes are either the same or disjoint, i.e. if $x \sim y$, then $[x] = [y]$.

Proof.

Let $\sim$ be an equivalence relation with $x \sim y$ and $y \sim x$ (symmetric). For any $x’ \in [x]$, $x’ \sim x \land x \sim y \implies x’ \sim y$ (transitive), so $x’ \in [y]$ and $[x] \subseteq [y]$. For any $y’ \in [y]$, $y’ \sim y \land y \sim x \implies y’ \sim x$ (transitive), so $y’ \in [x]$ and $[y] \subseteq [x]$. Hence, $[x]$ and $[y]$ can only overlap if they coincide, otherwise they are disjoint.

Definition. A partition of a set $X$ is a decomposition of the set into non-empty subsets, no two of which overlaps and whose union is all of $X$.

Theorem. The distinct equivalence classes of an equivalence relation on $X$ form a partition of $X$.

Proof.

Each equivalence class is non-empty because $[x]$ contains $x$ (reflexive). Also, $[x]$ and $[y]$ are either the same or disjoint. Furthermore, every $x \in X$ is in its own equivalence class $[x]$, so the union includes all of $X$. Hence, by definition, they form a partition of $X$.

Definition. The quotient map maps each element in $X$ to the equivalence class containing $x$, i.e. $x \mapsto [x]$.

References