1
$\begingroup$

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)}))$.

2 Answers 2

3

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.

  • 0
    @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$.2010-09-21
1

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.

  • 0
    Thank you, I see how it works for groups. For a more general case, I tried drawing from your original suggestion, and defined $a_1\sim b_1$ iff $f^U(a_1)=f^U(b_1)=c$. Then $f^{U/\sim}([a_1])=f^{U/\sim}([b_1])=[c]$ where we interpret the final equality to be the interpretation of $f$ in $U/\sim$. Perhaps I'm completely wrong, and even if I'm not, I don't know how to extend it to functions of arity greater than 1. Maybe some like $a_1\sim b_1$ and $a_2\sim b_2$ iff $f^U(a_1,a_2)=f^U(b_1,b_2)=c$. Regardless, I'll keep thinking about it.2010-09-21