Feeds:
Posts

## Internal equivalence relations

For the last few weeks I’ve been working as a counselor at the PROMYS program. The program runs, among other things, a course in abstract algebra, which was a good opportunity for me to get annoyed at the way people normally introduce normal subgroups, which is via the following unmotivated

Definition: A subgroup $N$ of a group $G$ is normal if $gNg^{-1} \subset N$ for all $g \in G$.

It is then proven that normal subgroups are precisely the kernels $N = \phi^{-1}(e)$ of surjective group homomorphisms $\phi : G \to G/N$. In other words, they are precisely the subgroups you can quotient by and get another group. This strikes me as backwards. The motivation to construct quotient groups should come first.

Today I’d like to present an alternate conceptual route to this definition starting from equivalence relations and quotients. This route also leads to ideals in rings and, among other things, highlights the special role of the existence of inverses in the theory of groups and rings (in the latter I mean additive inverses). The categorical setting for this discussion is the notion of a kernel pair and of an internal equivalence relation in a category, but for the sake of accessibility we will not use this language explicitly.

Equivalence relations and quotients of sets

Let $S$ be a set and let $\phi : S \to T$ be a function. We can think of $\phi$ as capturing some property of the objects of $S$ with values in $T$. If $\phi$ is not injective, then $\phi$ doesn’t completely capture all properties of elements of $S$, but it does capture something. What exactly does it capture?

Consider the relation $a \sim b \Leftrightarrow \phi(a) = \phi(b)$. This relation inherits the following properties from the properties of ordinary equality:

1. reflexivity: $a \sim a$,
2. transitivity: $a \sim b, b \sim c \Rightarrow a \sim c$,
3. symmetry: $a \sim b \Leftrightarrow b \sim a$.

A relation on a set with these properties is an equivalence relation, and the above axioms are in fact enough to describe precisely the relations we can get in this way. To see this, note that an equivalence relation on a set $S$ partitions it into disjoint subsets, the equivalence classes, which consist of maximal collections of elements which are equivalent to each other. We may write the set of equivalence classes as $S/\sim$, and then there is a canonical surjective function

$\phi : S \to S/\sim$

assigning an element of $S$ its equivalence class. Moreover, the procedure above which constructs an equivalence relation from a function outputs $\sim$ here. Thus talking about surjective functions out of $S$ (or quotient sets of $S$), up to a suitable notion of isomorphism, is equivalent to talking about equivalence relations on $S$, and what a given surjective function on $S$ captures is precisely the equivalence class an element of $S$ belongs to.

Equivalence relations and quotients of groups

Let $G$ be a group and let $\phi : G \to H$ be a group homomorphism. As before, the relation $g \sim h \Leftrightarrow \phi(g) = \phi(h)$ is an equivalence relation on $G$. However, because $\phi$ is also a group homomorphism, if $\phi(g_1) = \phi(h_1)$ and $\phi(g_2) = \phi(h_2)$ then $\phi(g_1 g_2) = \phi(h_1 h_2)$. This gives an additional axiom:

1. compatibility with multiplication: if $g_1 \sim h_1$ and $g_2 \sim h_2$ then $g_1 g_2 \sim h_1 h_2$.

This defines, in the terminology of universal algebra, a congruence relation on groups. Note that compatibility with multiplication, in the presence of the other axioms defining an equivalence relation, is equivalent to the condition that the equivalence relation, as a subset

$\{ (g, h) \in G \times G : g \sim h \}$

of $G \times G$, is a subgroup.

Compatibility with multiplication is precisely the condition needed for multiplication in $G$ to be well-defined on the equivalence classes $G/\sim$, so given a congruence relation on a group we can recover a quotient map $\phi : G \to G/\sim$ which is a group homomorphism. However, due to inverses we can say more. Compatibility with multiplication shows that

$\displaystyle g \sim h \Leftrightarrow h^{-1} g \sim e \Leftrightarrow g h^{-1} \sim e$.

In other words, a congruence relation is completely determined by which elements are congruent to the identity; call these elements $N$. (The corresponding relation might be called congruence $\bmod N$ by analogy with the case of $G = \mathbb{Z}, N = n \mathbb{Z}$.) Then:

1. $N$ having an identity is equivalent to $\sim$ being reflexive,
2. $N$ being closed under multiplication is equivalent to $\sim$ being transitive, and
3. $N$ being closed under inverses is equivalent to $\sim$ being symmetric.

In other words, $\sim$ is an equivalence relation if and only if $N$ is a subgroup. This is fairly special to groups; it highlights a close relation between groups, group actions, and equivalence relations which motivates the definition of a groupoid.

But we also want compatibility under multiplication, and since

$\displaystyle g \sim e \Leftrightarrow hg \sim h \Leftrightarrow hgh^{-1} \sim e$

it follows that $N$ has another property: it is closed under conjugation, so it is a normal subgroup. Conversely, if we define an equivalence relation by $g \sim h \Leftrightarrow h^{-1} g \in N$ where $N$ is a normal subgroup, then

$g_1 \sim h_1 \Leftrightarrow h_1^{-1} g_1 \in N, g_2 \sim h_2 \Leftrightarrow g_2 h_2^{-1} \in N$

hence

$g_1 \sim h_1, g_2 \sim h_2 \Rightarrow h_1^{-1} g_1 g_2 h_2^{-1} \in N \Leftrightarrow h_2^{-1} h_1^{-1} g_1 g_2 \in N \Leftrightarrow g_1 g_2 \sim h_1 h_2$

so normality of $N$ is equivalent to $\sim$ being compatible with multiplication. Thus talking about surjective group homomorphisms out of $G$ (or quotient groups of $G$), up to a suitable notion of isomorphism, is equivalent to talking about congruence relations on $G$, which is in turn equivalent to talking about normal subgroups of $G$.

Equivalence relations and quotients of rings

Let $R$ be a ring and let $\phi : R \to S$ be a ring homomorphism. As before, the relation $r \sim s \Leftrightarrow \phi(r) = \phi(s)$ is an equivalence relation on $R$. But since it must also respect addition and multiplication, $\sim$ satisfies

1. compatibility with addition: if $r_1 \sim s_1$ and $r_2 \sim s_2$ then $r_1 + r_2 \sim s_1 + s_2$,
2. compatibility with multiplication: if $r_1 \sim s_1$ and $r_2 \sim s_2$ then $r_1 r_2 \sim s_1 s_2$.

This defines a congruence relation on rings. Since addition has inverses, we conclude that $\sim$ is equivalence modulo $I$ for some normal subgroup $I$ of $R$ (under addition), namely the kernel $\phi^{-1}(0)$ of $\phi$ as a homomorphism of additive groups. Since addition is commutative, we can drop the adjective “normal.” Note that compatibility with addition and multiplication, in the presence of the other axioms, is equivalent to the condition that the equivalence relation, as a subset

$\{ (r, s) \in R \times R : r \sim s \}$

of $R \times R$, is a subring.

As before, we get a quotient map $R \to R/\sim \cong R/I$ of rings. In addition, compatibility with multiplication implies that

$\displaystyle r \sim 0 \Rightarrow rs = sr = 0 \forall s \in R$.

Thus $I$ is closed under left and right multiplication by elements of $R$: it is a two-sided ideal. Conversely, if $I$ is a two-sided ideal, then the corresponding equivalence relation $\sim$ has the following property: if $r_1 \sim s_1, r_2 \sim s_2$, then

$r_2 - s_2 \in I \Rightarrow r_1 r_2 - r_1 s_2 \in I$

and similarly

$r_1 - s_1 \in I \Rightarrow r_1 s_2 - s_1 s_2 \in I$

from which it follows that

$(r_1 r_2 - r_1 s_2) + (r_1 s_2 - s_1 s_2) = r_1 r_2 - s_1 s_2 \in I$

hence $r_1 r_2 \sim s_1 s_2$. So $I$ being a two-sided ideal is equivalent to $\sim$ being compatible with multiplication. Thus talking about surjective ring homomorphisms out of $R$ (or quotient rings of $R$) is equivalent to talking about congruence relations on $R$, which is in turn equivalent to talking about two-sided ideals of $R$.

Equivalence relations and quotients for monoids

When we try to repeat the above discussion in the setting of monoids we run into the problem that a congruence on a monoid $M$ is not completely determined by what is equivalent to the identity since we can no longer rely on inverses.

Example. Consider the monoids $M_{i, j} = \langle m | m^i = m^j \rangle$. The monoid $M_{3, 1}$ admits a surjective homomorphism to $M_{2, 1}$ sending a generator to a generator. It is not injective, but the kernel is trivial.

Thus monoids resemble more closely the situation for sets and topological spaces: we have to talk about congruence relations (namely submonoids of $M \times M$ which are also equivalence relations) and talking about these isn’t equivalent to talking about special kinds of submonoids of $M$.

Equivalence relations and quotients for topological spaces

We close with a less algebraic example. Let $X$ be a topological space and let $\phi : X \to Y$ be a continuous function to another topological space $Y$. As before, the relation $x \sim y \Leftrightarrow \phi(x) = \phi(y)$ is an equivalence relation $\sim$ on $X$. In the setting of general topological spaces, we cannot say any more about $\sim$ since it can in fact be arbitrary: the set of equivalence classes with respect to any equivalence relation may be given the quotient topology, which is by definition the universal topology such that the quotient map $X \to X/\sim$ is continuous.

However, if $Y$ is Hausdorff (in particular if we are working in a subcategory of the category of Hausdorff spaces), then the equivalence relation, as a subset

$\{ (x, y) \in X \times X : x \sim y \}$

of $X \times X$, is the preimage of the diagonal $(y, y) \in Y \times Y$ under the map

$\displaystyle X \times X \ni (x, y) \mapsto (f(x), f(y)) \in Y \times Y$.

Since $Y$ is Hausdorff, the diagonal is closed (this is equivalent to $Y$ being Hausdorff!), so its preimage is also closed. Thus the equivalence relation itself must be a closed subspace of $X \times X$. If we restrict ourselves to the category of compact Hausdorff spaces, then it follows that the equivalence relation is a compact Hausdorff subspace of $X \times X$.