Section 1.4
Equivalence classes
Equivalence classes provide us with a way of saying that two things are the “same”. Consider the set $\lbrace 1, 2, 3, 4, 5\rbrace $. If we care about these numbers as they are, we can just work with them. But if we only care about the parity of the numbers, whether they are even or odd, $1$ and $3$ make no difference at all. Then we may as well say that $1$ is the “same” as $3$, in this perspective. We want this notion of “same” to satisfy these properties:
- (i)
Always, $x$ is the same as $x$.
- (ii)
If $x$ is the same as $y$, then $y$ is the same as $x$.
- (iii)
If $x$ is the same as $y$ and $y$ is the same as $z$, then $x$ is the same as $z$.
These are reasonable requirements for what we would like to call the same. This motivates the definition of equivalence relations.
Let $X$ be a set. An equivalence relation $R$ is a subset $R \subseteq X \times X$ satisfying the following properties: (we are going to denote $(x, y) \in R$ as $x \sim_R y$, because this is indicative of it being a relation rather than a subset)
- (EQ1)
For all $x \in X$, $x \sim_R x$.
- (EQ2)
For all $x, y \in X$, $x \sim_R y$ if and only if $y \sim_R x$.
- (EQ3)
For all $x, y, z \in X$, if $x \sim_R y$ and $y \sim_R z$ then $x \sim_R z$.
Imagine that there is a point corresponding to each element of $X$, and the two dots corresponding to $x, y \in X$ are connected by an edge if $x \sim_R y$, as in Figure 1.1. Then you could visualize the set of points forming groups, so that no two points in different groups are connected, while every two points in the same group are connected.
Points are arranged into disjoint clusters. Every pair of points within a cluster is connected, while no points in different clusters are connected, illustrating equivalence classes.
For $x \in X$, we define its equivalence class as
$$ [x] = \lbrace y \in X : x \sim_R y \rbrace \subseteq X. $$
This is going to be the group which contains $x$, or the set of things that are the “same” as $x$.
Show that if $x \sim_R y$, then $[x] = [y]$. (Hint: show $[x] \subseteq [y]$ and $[y] \subseteq [x]$.) Show that, on the other hand, if $x \not\sim_R y$, then $[x]$ and $[y]$ are disjoint, i.e., $[x] \cap [y] = \emptyset$.
We can now consider collapsing these sets like $[x]$ into a single point.
Let $X$ be a subset with an equivalence relation $R$. Given a subset $S \subseteq X$, if there exists an element $x \in X$ such that $S = [x]$, then we say that $S$ is an equivalence class. We define the quotient of $X$ by $R$ as
$$ X / R = \lbrace \text{equivalence classes of } X \text{ with respect to } R \rbrace . $$
There is always a canonical projection map
$$ \pi : X \to X / R; \quad x \mapsto [x]. $$
Let $X$ be a set with an equivalence relation $R$, and let $f : X \to Y$ be a function satisfying $f(x_1) = f(x_2)$ if $x_1 \sim_R x_2$. Show that $f$ factors uniquely through $\pi$, i.e., there exists a unique function $g : X / R \to Y$ such that $f = g \circ \pi$.
X maps to Y by f and down to X modulo R by pi. A unique dashed map g goes from the quotient to Y so that f equals g after pi.
Sometimes, we would want to force some elements to be equal, but the elements we want to collapse might not be an equivalence relation. Consider the set $\lbrace 1, 3, 5\rbrace $, and suppose that for some reason we want to identify $1 = 3$ and also $3 = 5$. The solution is easy. We collapse all $1, 3, 5$ into a single element.
Take an arbitrary subset $S \subseteq X \times X$. The equivalence relation generated by $S$ is the following equivalence relation: $x \sim_R y$ if and only if there exists an $n \ge 0$ and a sequence $x = x_0, x_1, \ldots, x_n = y$ of elements in $X$ such that for each $0 \le j \le n-1$, either $(x_j, x_{j+1}) \in S$ or $(x_{j+1}, x_j) \in S$. (Here, if $n = 0$ we get $x \sim_R x$.)
If $X = \lbrace 1, 2, 3, 4, 5\rbrace $ and $S = \lbrace (1, 3), (3, 5) \rbrace $, then
$$ R = \lbrace (1, 1), \ldots, (5, 5), (1, 3), (3, 1), (1, 5), (5, 1), (3, 5), (5, 3) \rbrace . $$
Check that the $R$ constructed as above is indeed an equivalence relation on $X$. (That is, verify the three axioms EQ1, EQ2, and EQ3.)
If $R^\prime$ is another equivalence relation on $X$ such that $S \subseteq R^\prime$, show that $R \subseteq R^\prime$. This means that $R$ is the minimal (under inclusion) equivalence relation containing $S$.
Because we are lazy, for an arbitrary $S \subseteq X \times X$ we will write
$$ X / S = X / R $$
where $R$ is the equivalence relation generated by $S$. Because $X / S$ is a quotient, it comes with a map $\pi : X \to X / R = X / S$.
Let $X$ be a set and let $S \subseteq X \times X$ be an arbitrary subset. Let $f : X \to Y$ be a function satisfying $f(x_1) = f(x_2)$ if $x_1 \sim_S x_2$. Show that $f$ factors uniquely through $\pi : X \to X/S$, i.e., there exists a unique function $g : X / S \to Y$ such that $f = g \circ \pi$.
X maps to Y by f and down to X modulo S by pi. A unique dashed map g goes from the quotient to Y so that f equals g after pi.
Equivalence relations can be used to construct many different objects. Here is the dual version of Exercise 1.3.B.
Fix sets $A, B, C$ and maps $\alpha : C \to A$ and $\beta : C \to B$. Recall that there are inclusion maps $\iota_1 : A \to A \amalg B$ and $\iota_2 : B \to A \amalg B$. Define the set
$$ P = A \amalg B / (\iota_1(\alpha(c)) \sim \iota_2(\beta(c)) \text{ for all } c \in C) $$
which will come with maps
$$ j_1 : A \xrightarrow{\iota_1} A \amalg B \to P, \quad j_2 : B \xrightarrow{\iota_2} A \amalg B \to P. $$
Show that for arbitrary maps $f : A \to W$ and $g : B \to W$ satisfying $f \circ \alpha = g \circ \beta$, there exists a unique map $h : P \to W$ such that $f = h \circ j_1$ and $g = h \circ j_2$.
C maps to A and B by alpha and beta, which map into P by j one and j two. Compatible maps f and g to W induce a unique dashed map h from P to W.
(This $P$ is called the fiber coproduct of $A$ and $B$ over $C$.)
Let's try to construct the integers $\mathbb{Z}$ from the natural numbers $\mathbb{Z}_{\ge 0}$. Consider the relation
$$ (a, b) \sim (c, d) \quad \Leftrightarrow \quad a + d = b + c $$
on $\mathbb{Z}_{\ge 0}^2$. Check that this is an equivalence relation. There is a map $s : \mathbb{Z}_{\ge 0}^2 \to \mathbb{Z}$ given by $(a, b) \mapsto a - b$, and check that $(a, b) \sim (c, d)$ implies $s(a, b) = s(c, d)$. This shows that the map $s$ factors as
$$ s : \mathbb{Z}_{\ge 0}^2 \xrightarrow{\pi} (\mathbb{Z}_{\ge 0}^2 / \sim) \xrightarrow{t} \mathbb{Z}. $$
Show that this map $t$ is a bijection. This shows that we may construct the integers $\mathbb{Z}$ by taking the quotient of $\mathbb{Z}_{\ge 0}^2$ by this equivalence relation.
We can similarly construct $\mathbb{Q}$ from $\mathbb{Z}$. Consider the relation
$$ (a, b) \sim (c, d) \quad \Leftrightarrow \quad ad = bc $$
on the set $\mathbb{Z} \times (\mathbb{Z} \setminus \lbrace 0\rbrace )$, and check that this is an equivalence relation. Show that we can identify $\mathbb{Q}$ with the quotient $(\mathbb{Z} \times (\mathbb{Z} \setminus \lbrace 0\rbrace )) / \sim$.