# Quotienting a Set by an Equivalence Relation such that the Natural Projection is a Homomorphism

When studying group theory, I was interested to learn that a the quotient set $G/N$ of a group $G$ is again a group with $\pi\colon G\to G/N$ a homomorphism when $N$ is a normal subgroup of $G$.

Is there a more general set of criteria for this situation outside of group theory? As in, for any set $U$ and an equivalence relation $\sim$ on $U$, is there a similar set of criteria for $\sim$ such that $\pi\colon U\to U/\sim$ is a homomorphism in that it respects all functions and relations on $U$? Where by this I mean that $R^{U}(a_1,\dots,a_{\nu_L(R)})\Leftrightarrow R^{U/\sim}(\pi(a_1),\dots,\pi(a_{\nu_L(R)}))$ and $\pi(f^U(a_1,\dots,a_{\nu_L(f)}))=f^{U/\sim}(\pi(a_1),\dots,\pi(a_{\nu_L(f)}))$.

-

Assuming I've understood your question correctly and you are only interested in equivalence relations that respect some given operations and/or relations (as opposed to "all" operations and relations at the same time, which I suspect would lead you to only the identity or the total relation), let me give you the punchline first: an equivalence relation will "respect the operations and the relations" if and only if it is a substructure when considered as a subset of $U\times U$, where $U\times U$ is given the "coordinatewise" structure in the obvious way.

The concept you are looking for is that of a congruence, and is studied in universal algebra.

Suppose that you have a set $U$ with operators $\{f_i\}_{i\in I}$, with $f_i$ of arity $n_i$; and relations $\{R_j\}_{j\in J}$ with $R_j$ and $m_j$-ary relation. Let $\sim$ be an equivalence relation which "respects the operations", so that if $a_1,\ldots,a_{n_i},b_1,\ldots,b_{n_i}\in U$, $a_k\sim b_k$, then $f_i(a_1,\ldots,a_{n_i})\sim f_i(b_1,\ldots,b_{n_i})$, and and if $c_1,\ldots,c_{m_j},d_1,\ldots,d_{m_j}\in U$ with $c_k\sim d_k$ and $(c_1,\ldots,c_{m_j})\in R_j$, then $(d_1,\ldots,d_{m_j})\in R_j$. Then $\sim$, considered as subset of $U\times U$ is closed under each of $f_i\times f_i$, and the restrictions of $R_j\times R_j$ work just as needed to make $\sim$ into a substructure of $U\times U$.

Conversely, if $\sim$ is an equivalence relation that is also a substructure of $U\times U$, then if $a_k\sim b_k$ you have $(a_1,b_1),\ldots,(a_{n_i},b_{n_i})\in \sim$, so $$f_i\times f_i\bigl((a_1,b_1),\ldots,(a_{n_i},b_{n_i})\bigr) = \bigl(f_i(a_1,\ldots,a_{n_i}),f_i(b_1,\ldots,b_{n_i})\bigr)\in\sim,$$ hence $f_i(a_1,\ldots,a_{n_i})\sim f_i(b_1,\ldots,b_{n_i})$; similarly with the relations.

So an equivalence relation "respects the operations and relations" if and only if it is a substructure of $U\times U$.

There is a theorem that is completely analogous to the usual Isomorphism Theorems for groups and rings, for congruences (in fact, the theorems for groups and rings are special cases). If you are interested in this, you can see Gratzer's book (titled "Universal Algebra"), or George Bergman's An Invitation to General Algebra and Universal Constructions. (Though the material on universal algebra is in Chapter 8; Gratzer will get to this much quicker).

P.S. You need to be careful with relational algebras; in general, defining a substructure is a bit tricky; if you think of functions as special kinds of relations, you can see that you need some kind of "relational closure" for your set to be a substructure; but if you define substructures adequately, then the condition on $\sim$ that it be a substructure of $U\times U$ will take care of it.

-
Thank you Arturo! This was quite helpful. I apologize to you and Qiaochu for such a poorly worded question. I think I asked about something a little over my head. –  yunone Sep 21 '10 at 4:27
@yunone: You're welcome. One problem with groups and rings is that they actually obscure the situation somewhat by focusing on normal subgroups and ideals; you are really "coding" the equivalence relation by considering all things that are equivalent to $e$ or $0$. You can do this there because of inverses. If you work in semigroups, on the other hand, you cannot "code" the relations with a subsemigroup, and you really need to consider the equivalence relations as equivalence relations; this makes it clearer that you are dealing with subsemigroups of $S\times S$. –  Arturo Magidin Sep 21 '10 at 4:47
Any homomorphism $A \to B$ of structured sets which is surjective has this property. This is because any function $f : A \to B$ defines an equivalence relation on $A$ whose equivalence classes are the subsets $f^{-1}(b), b \in B$. So write down all the conditions necessary for $f$ to be a morphism and you'll get all the conditions you need on the corresponding equivalence relation.
For example, for a surjective function $f : G \to H$ between groups we require that $f(ab) = f(a) f(b)$. This implies that the preimage of the identity in $H$ is a subgroup $F$ of $G$, and from there it follows that the preimage of $h \in H$ is the coset $g F = F g$ for any $g \in f^{-1}(h)$, hence that $F$ is normal.
Sorry, I've been struggling to understand your answer. Looking to respect all functions, I take $f$ interpreted in $U$, $f^U$, and suppose $f^U(a_1,\dots,a_{\nu_L(f)})=a$, so that $\pi(a)=[a]$. Then wouldn't $[a]=${$(a_1,\dots,a_{\nu_L(f)})\in U^{\nu_L(f)} \ | \ f^U(a_1,\dots,a_{\nu_L(f)})=a$}? How does this define an equivalence relation on just $U$? Moreover, if I want $\pi(f^U(a_1,\dots,a_{\nu_L(f)}))=f^{U/\sim}(\pi(a_1),\dots,\pi(a_{\nu_L(f)})$ I would want $f$ interpreted in $U/\sim$ to map the classes $[a_1],\dots,[a_{\nu_L(f)}]$ to the class $[a]$? –  yunone Sep 21 '10 at 1:33
I apologize if I wasn't entirely clear. I'm looking at general structures $M$ and $N$ where $U$ is the universe of $M$ and $U/\sim$ is the universe of $N$. Here the relations $R$ and functions $f$ are nonlogical symbols in the structures, and the arity of $f$ is denoted $\nu_L(f)$, and the domain of $f$ interpreted in $U$ would be the cartesian product of $U$ $\nu_L(f)$ times. If that's the case, I don't see how the equivalence class of an element in $U^{\nu_L(f)}$ could exist in $U/\sim$. –  yunone Sep 21 '10 at 1:56
For the language of groups, I would have functions $Fs_L=${$*,^{-1}$} and constants $Cs_L=${$e$}. If the equivalence relation is defined such that $g\sim h$ iff $gh^{-1}\in N$, then $\pi$ is a homomorphism that respects the binary function $*$, since $\pi(*^G(g_1,g_2))=*^{G/N}(\pi(g_1),\pi(g_2))$ and the unary function $^{-1}$ since $\pi({^{-1}}^G(g_1))={^{-1}}^{G/N}(g_1)$. There are no usual relations defined on a group structure. In that case if $g_1*g_2=g_3$, wouldn't $(g_1,g_2)\in *^{-1}([g_3])$? –  yunone Sep 21 '10 at 2:26