Why do we define quotient groups for normal subgroups only?
$begingroup$
Let $G in mathbf{Grp}$, $H leq G$, $G/H := lbrace gH: g in G rbrace$. We can then introduce group operation on $G/H$ as $(xH)*(yH) := (xy)H$, so that $G/H$ becomes a quotient group when $H$ is a normal subgroup.
But why do we only work with quotient groups by normal subgroups? If we introduce the notion of left quotient group in the above manner, how much good properties of a quotient group do we lose?
UPD: fixed confusing notation: from $(xH)(yH)$ to $(xH)*(yH)$.
group-theory normal-subgroups quotient-group
$endgroup$
|
show 2 more comments
$begingroup$
Let $G in mathbf{Grp}$, $H leq G$, $G/H := lbrace gH: g in G rbrace$. We can then introduce group operation on $G/H$ as $(xH)*(yH) := (xy)H$, so that $G/H$ becomes a quotient group when $H$ is a normal subgroup.
But why do we only work with quotient groups by normal subgroups? If we introduce the notion of left quotient group in the above manner, how much good properties of a quotient group do we lose?
UPD: fixed confusing notation: from $(xH)(yH)$ to $(xH)*(yH)$.
group-theory normal-subgroups quotient-group
$endgroup$
7
$begingroup$
That operation on cosets is well-defined if and only if H is a normal subgroup. If H is just a subgroup, what you call "left quotient group" has the more standard name "set with a left group action". More precisely, the coset spaces G/H describe essentially all the examples of sets with transitive left G-actions. It is part of the general theory of groups acting on sets.
$endgroup$
– KCd
Dec 14 '10 at 12:20
$begingroup$
What do you mean by well-defined? It is a group, which is trivial to show.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 12:22
6
$begingroup$
To define the group operation, you have to fix coset representatives. You need to check that the coset you get as a result of the group operation is independent of the coset representatives you chose. But that is only true if the subgroup is normal. So before you "trivially show" that your operation gives a group, you should check that you have a well-defined operation on cosets in the first place.
$endgroup$
– Alex B.
Dec 14 '10 at 12:30
$begingroup$
Do you mean that if $xH = zH$ then it is necessary for $H$ to be a normal subgroup in order for the equality $(xy)H = (zy)H$ to hold for all $y in G$?
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:02
2
$begingroup$
Yes (as is easily checked).
$endgroup$
– Matt E
Dec 14 '10 at 14:09
|
show 2 more comments
$begingroup$
Let $G in mathbf{Grp}$, $H leq G$, $G/H := lbrace gH: g in G rbrace$. We can then introduce group operation on $G/H$ as $(xH)*(yH) := (xy)H$, so that $G/H$ becomes a quotient group when $H$ is a normal subgroup.
But why do we only work with quotient groups by normal subgroups? If we introduce the notion of left quotient group in the above manner, how much good properties of a quotient group do we lose?
UPD: fixed confusing notation: from $(xH)(yH)$ to $(xH)*(yH)$.
group-theory normal-subgroups quotient-group
$endgroup$
Let $G in mathbf{Grp}$, $H leq G$, $G/H := lbrace gH: g in G rbrace$. We can then introduce group operation on $G/H$ as $(xH)*(yH) := (xy)H$, so that $G/H$ becomes a quotient group when $H$ is a normal subgroup.
But why do we only work with quotient groups by normal subgroups? If we introduce the notion of left quotient group in the above manner, how much good properties of a quotient group do we lose?
UPD: fixed confusing notation: from $(xH)(yH)$ to $(xH)*(yH)$.
group-theory normal-subgroups quotient-group
group-theory normal-subgroups quotient-group
edited Jan 22 at 4:34
Martin Sleziak
44.9k10122276
44.9k10122276
asked Dec 14 '10 at 11:54
Alexei AverchenkoAlexei Averchenko
4,18112551
4,18112551
7
$begingroup$
That operation on cosets is well-defined if and only if H is a normal subgroup. If H is just a subgroup, what you call "left quotient group" has the more standard name "set with a left group action". More precisely, the coset spaces G/H describe essentially all the examples of sets with transitive left G-actions. It is part of the general theory of groups acting on sets.
$endgroup$
– KCd
Dec 14 '10 at 12:20
$begingroup$
What do you mean by well-defined? It is a group, which is trivial to show.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 12:22
6
$begingroup$
To define the group operation, you have to fix coset representatives. You need to check that the coset you get as a result of the group operation is independent of the coset representatives you chose. But that is only true if the subgroup is normal. So before you "trivially show" that your operation gives a group, you should check that you have a well-defined operation on cosets in the first place.
$endgroup$
– Alex B.
Dec 14 '10 at 12:30
$begingroup$
Do you mean that if $xH = zH$ then it is necessary for $H$ to be a normal subgroup in order for the equality $(xy)H = (zy)H$ to hold for all $y in G$?
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:02
2
$begingroup$
Yes (as is easily checked).
$endgroup$
– Matt E
Dec 14 '10 at 14:09
|
show 2 more comments
7
$begingroup$
That operation on cosets is well-defined if and only if H is a normal subgroup. If H is just a subgroup, what you call "left quotient group" has the more standard name "set with a left group action". More precisely, the coset spaces G/H describe essentially all the examples of sets with transitive left G-actions. It is part of the general theory of groups acting on sets.
$endgroup$
– KCd
Dec 14 '10 at 12:20
$begingroup$
What do you mean by well-defined? It is a group, which is trivial to show.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 12:22
6
$begingroup$
To define the group operation, you have to fix coset representatives. You need to check that the coset you get as a result of the group operation is independent of the coset representatives you chose. But that is only true if the subgroup is normal. So before you "trivially show" that your operation gives a group, you should check that you have a well-defined operation on cosets in the first place.
$endgroup$
– Alex B.
Dec 14 '10 at 12:30
$begingroup$
Do you mean that if $xH = zH$ then it is necessary for $H$ to be a normal subgroup in order for the equality $(xy)H = (zy)H$ to hold for all $y in G$?
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:02
2
$begingroup$
Yes (as is easily checked).
$endgroup$
– Matt E
Dec 14 '10 at 14:09
7
7
$begingroup$
That operation on cosets is well-defined if and only if H is a normal subgroup. If H is just a subgroup, what you call "left quotient group" has the more standard name "set with a left group action". More precisely, the coset spaces G/H describe essentially all the examples of sets with transitive left G-actions. It is part of the general theory of groups acting on sets.
$endgroup$
– KCd
Dec 14 '10 at 12:20
$begingroup$
That operation on cosets is well-defined if and only if H is a normal subgroup. If H is just a subgroup, what you call "left quotient group" has the more standard name "set with a left group action". More precisely, the coset spaces G/H describe essentially all the examples of sets with transitive left G-actions. It is part of the general theory of groups acting on sets.
$endgroup$
– KCd
Dec 14 '10 at 12:20
$begingroup$
What do you mean by well-defined? It is a group, which is trivial to show.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 12:22
$begingroup$
What do you mean by well-defined? It is a group, which is trivial to show.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 12:22
6
6
$begingroup$
To define the group operation, you have to fix coset representatives. You need to check that the coset you get as a result of the group operation is independent of the coset representatives you chose. But that is only true if the subgroup is normal. So before you "trivially show" that your operation gives a group, you should check that you have a well-defined operation on cosets in the first place.
$endgroup$
– Alex B.
Dec 14 '10 at 12:30
$begingroup$
To define the group operation, you have to fix coset representatives. You need to check that the coset you get as a result of the group operation is independent of the coset representatives you chose. But that is only true if the subgroup is normal. So before you "trivially show" that your operation gives a group, you should check that you have a well-defined operation on cosets in the first place.
$endgroup$
– Alex B.
Dec 14 '10 at 12:30
$begingroup$
Do you mean that if $xH = zH$ then it is necessary for $H$ to be a normal subgroup in order for the equality $(xy)H = (zy)H$ to hold for all $y in G$?
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:02
$begingroup$
Do you mean that if $xH = zH$ then it is necessary for $H$ to be a normal subgroup in order for the equality $(xy)H = (zy)H$ to hold for all $y in G$?
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:02
2
2
$begingroup$
Yes (as is easily checked).
$endgroup$
– Matt E
Dec 14 '10 at 14:09
$begingroup$
Yes (as is easily checked).
$endgroup$
– Matt E
Dec 14 '10 at 14:09
|
show 2 more comments
4 Answers
4
active
oldest
votes
$begingroup$
I cannot comment yet, but I thought I would elaborate on what is meant by being well-defined.
In your definition of the multiplication in $G/H$, you take cosets $xH$ and $yH$ and multiply by setting their product equal to $(xy)H$. But this means that you have chosen $x$ and $y$, and there will in general be other choices of $x$ and $y$ that give the same cosets. So if you have $xH$ = $x'H$ and $yH$ = $y'H$, you want to be sure that you also have $(xy)H = (x'y')H$, and it can be shown that this holds for all elements of $G$ iff $H$ is normal in $G$, so this is the only case where this multiplication is well-defined.
$endgroup$
add a comment |
$begingroup$
Added. So, what is the problem? Let's look at the simplest example of a non-normal subgroup. Take $G=S_3$, and $H={e,(1,2)}$. If we compose permutations right to left, the left cosets of $H$ in $G$ are:
begin{align*}
eH = (1,2)H &= { e, (1,2)};\
(1,2,3)H = (1,3)H &= {(1,2,3), (1,3)};\
(1,3,2)H = (2,3)H &= {(1,3,2), (2,3)}.
end{align*}
If we try multiplying cosets term-by-term, we run into problems. Multiplying by $eH$ is not a problem, but take $(1,2,3)H$ multiplied by itself. The products are:
$${ (1,2,3)(1,2,3), (1,2,3)(1,3), (1,3)(1,2,3), (1,3)(1,3)} = {(1,3,2), (2,3), (1,2), e}$$
which is not a coset. If we multiply using representatives, as in the original question,we also run into problems: if we multiply $(1,2,3)Hcdot(1,3,2)H$ as $(1,2,3)(1,3,2)H$, we get $eH$. But $(1,2,3)H = (1,3)H$, and $(1,3,2)H = (2,3)H$, and if we multiply them by looking at these alternative representatives/names, we get $(1,3)Hcdot (2,3)H = (1,3)(2,3)H = (1,3,2)Hneq eH$. That is, the multiplication rule depends on the name we give the coset, rather than on what the coset is. This means that the rule is not well-defined.
We can let $G$ act on the set of left cosets of $H$, by $g(xH) = gxH$; this is not a group, but a group action. We can also, separately, put group structures on the set of cosets of $H$ in $G$, since it will be a set, and every nonempty set can be given a group structure (assuming the Axiom of Choice; in fact, equivalent to the Axiom of Choice). But that structure will generally have nothing to do with the operation in $G$.
If we want an operation on the set of cosets, and have the operation in the cosets to be induced by the operation in $G$, then we have:
THEOREM. Let $G$ be a group and $H$ a subgroup. Let $G/H = { gHmid gin G}$ be the set of left cosets of $H$ in $G$. The operation
$$cdot colon G/H times G/H to G/Hqquadtext{defined by}qquad (xH)cdot(yH) = (xy)H$$
is well defined (that is, if $xH = x'H$ and $yH=y'H$ then $xyH = x'y'H$) if and only if $H$ is normal in $G$.
Proof. Suppose $H$ is normal. Then $gH=Hg$ for every $gin G$. If $xH=x'H$ and $yH=y'H$, then
$$xyH = x(yH) = x(Hy) = x(Hy') = (xH)y' = (x'H)y' = x'(Hy') = x'(y'H) = x'y'H$$
so the operation is well defined.
Conversely, suppose the operation is well defined so that whenever $xH=x'H$ and $yH=y'H$, then $xyH = x'y'H$. We want to show that $g^{-1}Hgsubseteq H$ for all $gin G$. For each $hin H$, since $hH = eH$, we have $eHgH = egH=gH$ is equal to $hHgH = hgH$. So $gH = hgH$, hence $H=g^{-1}hgH$, so $g^{-1}hgin H$ for each $hin H$. Thus, $g^{-1}Hgsubseteq H$. This holds for any $gin G$, so $g^{-1}Hgsubseteq H$ for all $gin G$, hence $Htriangleleft G$, as claimed. QED
And now I'm going to hijack your question a bit and go on a long excursion to a closely related subject which is not necessary to answer your question, but which I think is interesting. (Sorry!)
This is really connected to the notion of a congruence on an algebra (in the sense of universal algebra). A subgroup $H$ defines an equivalence relation on $G$ by $xsim y$ if and only if $xH = yH$ (it also defines the equivalence relation of right congruence, but ignore that for now). Being an equivalence relation, it corresponds to a subset $Phi$ of $Gtimes G$, with $(x,y)inPhi$ if and only if $xsim y$, if and only if $xH=yH$.
But $Gtimes G$ also has a natural group structure inherited from $G$. Since $Phi$ is a subset of the group $Gtimes G$, it makes sense to ask whether $Phi$ is a subgroup of $Gtimes G$ or not.
THEOREM. $Phi$ is a subgroup of $Gtimes G$ if and only if $H$ is normal in $G$.
Proof. Note that $Phi$ always contains $(e,e)$ (in fact, the entire diagonal). Assume first that $H$ is normal. If $(x,y)in Phi$, then $xH=yH$. Hence, $Hx = Hy$, and taking inverses of each element we get $x^{-1}H = y^{-1}H$, so $(x^{-1},y^{-1})inPhi$; thus, $Phi$ is closed under inverses. If $(x,y),(z,w)inPhi$, then $xH=yH$, $zH=wH$, so by what we proved above we have $xzH = ywH$, so $(xz,yw)=(x,y)(z,w)inPhi$. Thus, $Phi$ is closed under products, so $Phi$ is a subgroup of $Gtimes G$.
Conversely, suppose that $Phi$ is a subgroup. If $xH=yH$ and $zH=wH$, then $(x,y),(z,w)in Phi$, hence $(x,y)(z,w)=(xz,yw)inPhi$; thus, $xzH = ywH$. This proves that the operation $xHcdot zH mapsto xzH$ is well-defined, so by the theorem above $H$ is a normal subgroup of $G$. QED
Added. (Stuff between the two horizontal lines was added in this edit).
Okay, how about this? Can we define some equivalence relation $sim$ on a group $G$ so that we can multiply equivalence classes through representatives, have it be well-defined, but not have $sim$ "come from" a normal subgroup?
That is: suppose $sim$ is an equivalence relation on the group $G$ (any equivalence relation; all we require is that it be reflexive, symmetric, and transitive on the underlying set of $G$), and let $[x]$ denote the equivalence class of $x$ for each $x$ in $G$. We want to define a multiplication on the quotient set $G/sim$ by $[x][y] = [xy]$. When is this well defined?
THEOREM. Let $G$ be a group, and let $sim$ be an equivalence relation on $G$. Then the multiplication on $G/sim$ defined by $[x][y]=[xy]$ is well defined if and only if $sim$ is a subgroup of $Gtimes G$.
Proof. If $sim$ is a subgroup of $Gtimes G$ and $[x]=[z]$, $[y]=[w]$, then $(x,z),(y,w)in sim$, so $(x,z)(y,w) = (xy,zw)in sim$, hence $[xy]=[zw]$, so multiplication is well defined.
Conversely, suppose the multiplication is well defined. Since $sim$ is an equivalence relation, $(e,e)insim$. Also, if $(x,z), (y,w)insim$, then $[x]=[z]$, $[y]=[w]$, so $[x][y]=[xy]$ equals $[z][w]=[zw]$, so $(xy,zw)=(x,y)(z,w)insim$. Thus, $sim$ is a submonoid of $Gtimes G$. It only remains to show that $sim$ is closed under inverses. Suppose that $(x,y)insim$. Multiplying by $(x^{-1},x^{-1})$ on the left and $(y^{-1},y^{-1})$ on the right (both elements of $sim$) we have $(y^{-1},x^{-1})insim$. Since $sim$ is an equivalence relation, it is reflexive, so $(x^{-1},y^{-1})insim$. Thus, $sim$ is a subgroup of $Gtimes G$, as claimed. QED
Okay, so we can define the multiplication on the quotient set if and only if the equivalence relation is a subgroup of $Gtimes G$. Do all such equivalence relations "come" from subgroups? Yes:
THEOREM. Let $sim$ be an equivalence relation on $G$ that is a subgroup of $Gtimes G$, and let $H={gin Gmid gsim e}$. Then $H$ is a normal subgroup of $G$, and $xsim y$ if and only if $xH=yH$.
Proof. We can identify $G$ with the subgroup $Gtimes{e}$ of $Gtimes G$; then $H$ corresponds to the intersection of the subgroup $sim$ and the subgroup $Gtimes{e}$, hence is a subgroup of $G$.
To see that $sim$ is in fact left congruence modulo $H$, simply note that $xH=yH$ if and only if $y^{-1}xin H$, if and only if $(y^{-1}x,e)in sim$, if and only if $(y,y)(y^{-1}x,e)insim$, if and only if $(x,y)in sim$, if and only if $xsim y$. That $H$ is normal now follows because multiplication of cosets (equivalently, of equivalence classes modulo $sim$) is well defined. QED
When we generalize this to an arbitrary algebra (in the sense of universal algebra; examples include magmas, monoids, semigroups, groups, rings, $K$-algebras, lattices, etc), we get the notion of congruence:
Definition. Let $A$ be an algebra (in the sense of universal algebra). A congruence on $A$ is an equivalence relation $Phi$ on $A$ such that $Phi$ is a subalgebra of $Atimes A$.
THEOREM. Let $A$ and $B$ be algebras of the same type, and let $fcolon Ato B$ be a homomorphism; define $Phi_f = {(x,y)in Atimes Amid f(x)=f(y)}$. Then $Phi_f$ is a congruence on $A$. Conversely, if $Psi$ is a congruence on $A$, then there exists an algebra $mathcal{B}$ and a homomorphism $picolon Ato mathcal{B}$ such that $Psi=Phi_{pi}$.
Special case. Let me do the proof with semigroups. First, let $fcolon Ato B$ be a semigroup homomorphism; then $Phi_f$ is an equivalence relation on $A$. To show it is a subsemigroup of $Atimes A$, suppose $(x,y),(z,w)in Phi_f$. Then $f(xz) = f(x)f(z) = f(y)f(w) = f(yw)$, so $(xz,yw)inPhi_f$. Thus, $Phi_f$ is a subsemigroup of $Atimes A$, hence a congruence.
Conversely, suppose that $Psi$ is a congruence. Let $mathcal{B}=A/Psi$, the set of equivalence classes of $Psi$ in $A$. Let $[x]$ denote the class of $x$. We define a multiplication on $mathcal{B}$ by $[a][b]=[ab]$. We must prove that this is well defined: suppose $[x]=[y]$ and $[z]=[w]$. Then $(x,y),(z,w)inPsi$, so $(xz,yw)inPsi$ (since $Psi$ is a congruence). Therefore, $[xz]=[yw]$, so multiplication is well-defined. It is now easy to verify that multiplication is associative:
$$[x]([y][z]) = [x][yz] = [x(yz)]=[(xy)z] = [xy][z] = ([x][y])[z].$$
Thus, $mathcal{B}$ is a semigroup. The map $picolon Ato mathcal{B}$ given by $pi(a)=[a]$ is easily verified to be a homomorphism, and $Phi_{pi}=Psi$.
The proof for an arbitrary algebra with operations $f_1,ldots,f_k$ of arities $a_1,ldots,a_k$ (or even an infinite number of operations, each with finite arities) is essentially the same.
QED
One can then prove the Isomorphism Theorems for "congruences" in exactly the analogous manner as for groups and rings, for any class of algebras.
In Groups and Rings, we can "get away" with not studying congruences because if $Phi$ is a congruence on $G$, then we can let $N = { gin Gmid (g,e)inPhi}$, and it turns out that $Phi$ is the equivalence relation induced by $N$. Essentially, a congruence tells you that certain things are equal, but in groups (and rings), instead of saying "$x$ is equal to $y$", we can say "$xy^{-1}$ is the identity". The normal subgroup (resp. the ideal) is the set of elements equivalent to the identity. In more general classes, such as semigroups, we don't have the luxury of expressing any identity in the form $w=e$, so we must actually keep track of both sides of the equality.
This is all part of Universal Algebra. I cannot recommend George Bergman's book highly enough if you want a great introduction to the subject (with a Category Theory flavor).
$endgroup$
4
$begingroup$
Wow, you really wanted to get a point across, didn't you? :D Thumbs up!
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 3:47
12
$begingroup$
@Alexei: Not "get a point across", but rather take the opportunity to point out a bunch of ideas that come together and happen to show that "normal subgroups" is the only game in town when you want to define "quotient groups". I happen to like the idea of congruences better than normal subgroups because they are more "natural": you just define $asim b Longleftrightarrow f(a)=f(b)$; it is a bit of a historical accident that in the first two abstract structures it turns out we can "codify" the congruence with a substructure-with-something-extra (normal subgroups for groups, ideals for rings).
$endgroup$
– Arturo Magidin
Dec 15 '10 at 3:51
$begingroup$
Yes, these are pretty interesting ideas. Thank you :)
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 9:19
4
$begingroup$
This was an awesome answer, and your reference of Bergman's text looks great. Thank you.
$endgroup$
– Hans Parshall
Dec 16 '10 at 1:28
add a comment |
$begingroup$
(Sorry, new here, can't comment.)
To expand on Alex's answer, if we demand that $(xh)(yh) in (xy)H$ for any coset representative $h$, then this is equivalent to asking that $y^{-1}hyh in H$ for all $h in H$. But the conjugate $y^{-1}hy$ need not lie in $H$ if $H$ isn't normal, hence the claim that the operation in your "left quotient group" isn't well defined.
$endgroup$
$begingroup$
$(xH)(yH) mapsto (xy)H$ need not be generated by the group operation of $G$; sure, if you constrain yourself to such an operation you do need a normal subgroup. I probably confused you with my notation :) However, another kind of problem arises, see my response to Alex.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:00
$begingroup$
This doesn't fix the problem. See Tobais's answer. No matter how we look at the group operation, it has to be independent of which coset representatives we choose. The problem is easiest to see if you just consider the product $(xh)(yh)$ like I do above, but expand Tobais's $(xy)H=(x'y')H$ and you'll still get a term like $y^{-1}hyh$ which needs to be in $H$. Therefore $H$ must be normal.
$endgroup$
– Jon
Dec 14 '10 at 13:46
$begingroup$
Unfortunately, if we just think of cosets as of elements of $G/H$ your answer doesn't get the point :P
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 14:56
2
$begingroup$
It seems like some of the confusion is coming from whether or not we can put a different group structure on the set of cosets $G/H$. Perhaps we can, but we certainly wouldn't call it the quotient group of $G$ by $H$ because it has nothing to do with $G$ or $H$ as groups.
$endgroup$
– Sean Tilson
Dec 14 '10 at 16:26
3
$begingroup$
@Sean Tilson: It is equivalent to the Axiom of Choice that every nonempty set can be given a group structure. Certainly, the set of cosets is a set, so we can give it a group structure (assuming AC), but which will likely have nothing to do with the operation in $G$.
$endgroup$
– Arturo Magidin
Dec 14 '10 at 18:05
|
show 3 more comments
$begingroup$
To elaborate on a comment made by another user in the above, if the operation $(xH)ast(yH):=(xy)H$ is well-defined, then $(G/H,ast)$ is a group. Hence $f:Gto G/H$ defined by $f(g)=gH$ is a homomorphism and $H=ker f$. However, the kernel of a group homomorphism is always normal. Therefore $H$ has to be normal.
(As shown by Arturo Magidin's answer, actually $(xH)ast(yH):=(xy)H$ is well-defined if and only if $H$ is normal.)
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f14282%2fwhy-do-we-define-quotient-groups-for-normal-subgroups-only%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I cannot comment yet, but I thought I would elaborate on what is meant by being well-defined.
In your definition of the multiplication in $G/H$, you take cosets $xH$ and $yH$ and multiply by setting their product equal to $(xy)H$. But this means that you have chosen $x$ and $y$, and there will in general be other choices of $x$ and $y$ that give the same cosets. So if you have $xH$ = $x'H$ and $yH$ = $y'H$, you want to be sure that you also have $(xy)H = (x'y')H$, and it can be shown that this holds for all elements of $G$ iff $H$ is normal in $G$, so this is the only case where this multiplication is well-defined.
$endgroup$
add a comment |
$begingroup$
I cannot comment yet, but I thought I would elaborate on what is meant by being well-defined.
In your definition of the multiplication in $G/H$, you take cosets $xH$ and $yH$ and multiply by setting their product equal to $(xy)H$. But this means that you have chosen $x$ and $y$, and there will in general be other choices of $x$ and $y$ that give the same cosets. So if you have $xH$ = $x'H$ and $yH$ = $y'H$, you want to be sure that you also have $(xy)H = (x'y')H$, and it can be shown that this holds for all elements of $G$ iff $H$ is normal in $G$, so this is the only case where this multiplication is well-defined.
$endgroup$
add a comment |
$begingroup$
I cannot comment yet, but I thought I would elaborate on what is meant by being well-defined.
In your definition of the multiplication in $G/H$, you take cosets $xH$ and $yH$ and multiply by setting their product equal to $(xy)H$. But this means that you have chosen $x$ and $y$, and there will in general be other choices of $x$ and $y$ that give the same cosets. So if you have $xH$ = $x'H$ and $yH$ = $y'H$, you want to be sure that you also have $(xy)H = (x'y')H$, and it can be shown that this holds for all elements of $G$ iff $H$ is normal in $G$, so this is the only case where this multiplication is well-defined.
$endgroup$
I cannot comment yet, but I thought I would elaborate on what is meant by being well-defined.
In your definition of the multiplication in $G/H$, you take cosets $xH$ and $yH$ and multiply by setting their product equal to $(xy)H$. But this means that you have chosen $x$ and $y$, and there will in general be other choices of $x$ and $y$ that give the same cosets. So if you have $xH$ = $x'H$ and $yH$ = $y'H$, you want to be sure that you also have $(xy)H = (x'y')H$, and it can be shown that this holds for all elements of $G$ iff $H$ is normal in $G$, so this is the only case where this multiplication is well-defined.
edited Jul 24 '18 at 18:03
Namaste
1
1
answered Dec 14 '10 at 13:33
Tobias KildetoftTobias Kildetoft
16.9k14274
16.9k14274
add a comment |
add a comment |
$begingroup$
Added. So, what is the problem? Let's look at the simplest example of a non-normal subgroup. Take $G=S_3$, and $H={e,(1,2)}$. If we compose permutations right to left, the left cosets of $H$ in $G$ are:
begin{align*}
eH = (1,2)H &= { e, (1,2)};\
(1,2,3)H = (1,3)H &= {(1,2,3), (1,3)};\
(1,3,2)H = (2,3)H &= {(1,3,2), (2,3)}.
end{align*}
If we try multiplying cosets term-by-term, we run into problems. Multiplying by $eH$ is not a problem, but take $(1,2,3)H$ multiplied by itself. The products are:
$${ (1,2,3)(1,2,3), (1,2,3)(1,3), (1,3)(1,2,3), (1,3)(1,3)} = {(1,3,2), (2,3), (1,2), e}$$
which is not a coset. If we multiply using representatives, as in the original question,we also run into problems: if we multiply $(1,2,3)Hcdot(1,3,2)H$ as $(1,2,3)(1,3,2)H$, we get $eH$. But $(1,2,3)H = (1,3)H$, and $(1,3,2)H = (2,3)H$, and if we multiply them by looking at these alternative representatives/names, we get $(1,3)Hcdot (2,3)H = (1,3)(2,3)H = (1,3,2)Hneq eH$. That is, the multiplication rule depends on the name we give the coset, rather than on what the coset is. This means that the rule is not well-defined.
We can let $G$ act on the set of left cosets of $H$, by $g(xH) = gxH$; this is not a group, but a group action. We can also, separately, put group structures on the set of cosets of $H$ in $G$, since it will be a set, and every nonempty set can be given a group structure (assuming the Axiom of Choice; in fact, equivalent to the Axiom of Choice). But that structure will generally have nothing to do with the operation in $G$.
If we want an operation on the set of cosets, and have the operation in the cosets to be induced by the operation in $G$, then we have:
THEOREM. Let $G$ be a group and $H$ a subgroup. Let $G/H = { gHmid gin G}$ be the set of left cosets of $H$ in $G$. The operation
$$cdot colon G/H times G/H to G/Hqquadtext{defined by}qquad (xH)cdot(yH) = (xy)H$$
is well defined (that is, if $xH = x'H$ and $yH=y'H$ then $xyH = x'y'H$) if and only if $H$ is normal in $G$.
Proof. Suppose $H$ is normal. Then $gH=Hg$ for every $gin G$. If $xH=x'H$ and $yH=y'H$, then
$$xyH = x(yH) = x(Hy) = x(Hy') = (xH)y' = (x'H)y' = x'(Hy') = x'(y'H) = x'y'H$$
so the operation is well defined.
Conversely, suppose the operation is well defined so that whenever $xH=x'H$ and $yH=y'H$, then $xyH = x'y'H$. We want to show that $g^{-1}Hgsubseteq H$ for all $gin G$. For each $hin H$, since $hH = eH$, we have $eHgH = egH=gH$ is equal to $hHgH = hgH$. So $gH = hgH$, hence $H=g^{-1}hgH$, so $g^{-1}hgin H$ for each $hin H$. Thus, $g^{-1}Hgsubseteq H$. This holds for any $gin G$, so $g^{-1}Hgsubseteq H$ for all $gin G$, hence $Htriangleleft G$, as claimed. QED
And now I'm going to hijack your question a bit and go on a long excursion to a closely related subject which is not necessary to answer your question, but which I think is interesting. (Sorry!)
This is really connected to the notion of a congruence on an algebra (in the sense of universal algebra). A subgroup $H$ defines an equivalence relation on $G$ by $xsim y$ if and only if $xH = yH$ (it also defines the equivalence relation of right congruence, but ignore that for now). Being an equivalence relation, it corresponds to a subset $Phi$ of $Gtimes G$, with $(x,y)inPhi$ if and only if $xsim y$, if and only if $xH=yH$.
But $Gtimes G$ also has a natural group structure inherited from $G$. Since $Phi$ is a subset of the group $Gtimes G$, it makes sense to ask whether $Phi$ is a subgroup of $Gtimes G$ or not.
THEOREM. $Phi$ is a subgroup of $Gtimes G$ if and only if $H$ is normal in $G$.
Proof. Note that $Phi$ always contains $(e,e)$ (in fact, the entire diagonal). Assume first that $H$ is normal. If $(x,y)in Phi$, then $xH=yH$. Hence, $Hx = Hy$, and taking inverses of each element we get $x^{-1}H = y^{-1}H$, so $(x^{-1},y^{-1})inPhi$; thus, $Phi$ is closed under inverses. If $(x,y),(z,w)inPhi$, then $xH=yH$, $zH=wH$, so by what we proved above we have $xzH = ywH$, so $(xz,yw)=(x,y)(z,w)inPhi$. Thus, $Phi$ is closed under products, so $Phi$ is a subgroup of $Gtimes G$.
Conversely, suppose that $Phi$ is a subgroup. If $xH=yH$ and $zH=wH$, then $(x,y),(z,w)in Phi$, hence $(x,y)(z,w)=(xz,yw)inPhi$; thus, $xzH = ywH$. This proves that the operation $xHcdot zH mapsto xzH$ is well-defined, so by the theorem above $H$ is a normal subgroup of $G$. QED
Added. (Stuff between the two horizontal lines was added in this edit).
Okay, how about this? Can we define some equivalence relation $sim$ on a group $G$ so that we can multiply equivalence classes through representatives, have it be well-defined, but not have $sim$ "come from" a normal subgroup?
That is: suppose $sim$ is an equivalence relation on the group $G$ (any equivalence relation; all we require is that it be reflexive, symmetric, and transitive on the underlying set of $G$), and let $[x]$ denote the equivalence class of $x$ for each $x$ in $G$. We want to define a multiplication on the quotient set $G/sim$ by $[x][y] = [xy]$. When is this well defined?
THEOREM. Let $G$ be a group, and let $sim$ be an equivalence relation on $G$. Then the multiplication on $G/sim$ defined by $[x][y]=[xy]$ is well defined if and only if $sim$ is a subgroup of $Gtimes G$.
Proof. If $sim$ is a subgroup of $Gtimes G$ and $[x]=[z]$, $[y]=[w]$, then $(x,z),(y,w)in sim$, so $(x,z)(y,w) = (xy,zw)in sim$, hence $[xy]=[zw]$, so multiplication is well defined.
Conversely, suppose the multiplication is well defined. Since $sim$ is an equivalence relation, $(e,e)insim$. Also, if $(x,z), (y,w)insim$, then $[x]=[z]$, $[y]=[w]$, so $[x][y]=[xy]$ equals $[z][w]=[zw]$, so $(xy,zw)=(x,y)(z,w)insim$. Thus, $sim$ is a submonoid of $Gtimes G$. It only remains to show that $sim$ is closed under inverses. Suppose that $(x,y)insim$. Multiplying by $(x^{-1},x^{-1})$ on the left and $(y^{-1},y^{-1})$ on the right (both elements of $sim$) we have $(y^{-1},x^{-1})insim$. Since $sim$ is an equivalence relation, it is reflexive, so $(x^{-1},y^{-1})insim$. Thus, $sim$ is a subgroup of $Gtimes G$, as claimed. QED
Okay, so we can define the multiplication on the quotient set if and only if the equivalence relation is a subgroup of $Gtimes G$. Do all such equivalence relations "come" from subgroups? Yes:
THEOREM. Let $sim$ be an equivalence relation on $G$ that is a subgroup of $Gtimes G$, and let $H={gin Gmid gsim e}$. Then $H$ is a normal subgroup of $G$, and $xsim y$ if and only if $xH=yH$.
Proof. We can identify $G$ with the subgroup $Gtimes{e}$ of $Gtimes G$; then $H$ corresponds to the intersection of the subgroup $sim$ and the subgroup $Gtimes{e}$, hence is a subgroup of $G$.
To see that $sim$ is in fact left congruence modulo $H$, simply note that $xH=yH$ if and only if $y^{-1}xin H$, if and only if $(y^{-1}x,e)in sim$, if and only if $(y,y)(y^{-1}x,e)insim$, if and only if $(x,y)in sim$, if and only if $xsim y$. That $H$ is normal now follows because multiplication of cosets (equivalently, of equivalence classes modulo $sim$) is well defined. QED
When we generalize this to an arbitrary algebra (in the sense of universal algebra; examples include magmas, monoids, semigroups, groups, rings, $K$-algebras, lattices, etc), we get the notion of congruence:
Definition. Let $A$ be an algebra (in the sense of universal algebra). A congruence on $A$ is an equivalence relation $Phi$ on $A$ such that $Phi$ is a subalgebra of $Atimes A$.
THEOREM. Let $A$ and $B$ be algebras of the same type, and let $fcolon Ato B$ be a homomorphism; define $Phi_f = {(x,y)in Atimes Amid f(x)=f(y)}$. Then $Phi_f$ is a congruence on $A$. Conversely, if $Psi$ is a congruence on $A$, then there exists an algebra $mathcal{B}$ and a homomorphism $picolon Ato mathcal{B}$ such that $Psi=Phi_{pi}$.
Special case. Let me do the proof with semigroups. First, let $fcolon Ato B$ be a semigroup homomorphism; then $Phi_f$ is an equivalence relation on $A$. To show it is a subsemigroup of $Atimes A$, suppose $(x,y),(z,w)in Phi_f$. Then $f(xz) = f(x)f(z) = f(y)f(w) = f(yw)$, so $(xz,yw)inPhi_f$. Thus, $Phi_f$ is a subsemigroup of $Atimes A$, hence a congruence.
Conversely, suppose that $Psi$ is a congruence. Let $mathcal{B}=A/Psi$, the set of equivalence classes of $Psi$ in $A$. Let $[x]$ denote the class of $x$. We define a multiplication on $mathcal{B}$ by $[a][b]=[ab]$. We must prove that this is well defined: suppose $[x]=[y]$ and $[z]=[w]$. Then $(x,y),(z,w)inPsi$, so $(xz,yw)inPsi$ (since $Psi$ is a congruence). Therefore, $[xz]=[yw]$, so multiplication is well-defined. It is now easy to verify that multiplication is associative:
$$[x]([y][z]) = [x][yz] = [x(yz)]=[(xy)z] = [xy][z] = ([x][y])[z].$$
Thus, $mathcal{B}$ is a semigroup. The map $picolon Ato mathcal{B}$ given by $pi(a)=[a]$ is easily verified to be a homomorphism, and $Phi_{pi}=Psi$.
The proof for an arbitrary algebra with operations $f_1,ldots,f_k$ of arities $a_1,ldots,a_k$ (or even an infinite number of operations, each with finite arities) is essentially the same.
QED
One can then prove the Isomorphism Theorems for "congruences" in exactly the analogous manner as for groups and rings, for any class of algebras.
In Groups and Rings, we can "get away" with not studying congruences because if $Phi$ is a congruence on $G$, then we can let $N = { gin Gmid (g,e)inPhi}$, and it turns out that $Phi$ is the equivalence relation induced by $N$. Essentially, a congruence tells you that certain things are equal, but in groups (and rings), instead of saying "$x$ is equal to $y$", we can say "$xy^{-1}$ is the identity". The normal subgroup (resp. the ideal) is the set of elements equivalent to the identity. In more general classes, such as semigroups, we don't have the luxury of expressing any identity in the form $w=e$, so we must actually keep track of both sides of the equality.
This is all part of Universal Algebra. I cannot recommend George Bergman's book highly enough if you want a great introduction to the subject (with a Category Theory flavor).
$endgroup$
4
$begingroup$
Wow, you really wanted to get a point across, didn't you? :D Thumbs up!
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 3:47
12
$begingroup$
@Alexei: Not "get a point across", but rather take the opportunity to point out a bunch of ideas that come together and happen to show that "normal subgroups" is the only game in town when you want to define "quotient groups". I happen to like the idea of congruences better than normal subgroups because they are more "natural": you just define $asim b Longleftrightarrow f(a)=f(b)$; it is a bit of a historical accident that in the first two abstract structures it turns out we can "codify" the congruence with a substructure-with-something-extra (normal subgroups for groups, ideals for rings).
$endgroup$
– Arturo Magidin
Dec 15 '10 at 3:51
$begingroup$
Yes, these are pretty interesting ideas. Thank you :)
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 9:19
4
$begingroup$
This was an awesome answer, and your reference of Bergman's text looks great. Thank you.
$endgroup$
– Hans Parshall
Dec 16 '10 at 1:28
add a comment |
$begingroup$
Added. So, what is the problem? Let's look at the simplest example of a non-normal subgroup. Take $G=S_3$, and $H={e,(1,2)}$. If we compose permutations right to left, the left cosets of $H$ in $G$ are:
begin{align*}
eH = (1,2)H &= { e, (1,2)};\
(1,2,3)H = (1,3)H &= {(1,2,3), (1,3)};\
(1,3,2)H = (2,3)H &= {(1,3,2), (2,3)}.
end{align*}
If we try multiplying cosets term-by-term, we run into problems. Multiplying by $eH$ is not a problem, but take $(1,2,3)H$ multiplied by itself. The products are:
$${ (1,2,3)(1,2,3), (1,2,3)(1,3), (1,3)(1,2,3), (1,3)(1,3)} = {(1,3,2), (2,3), (1,2), e}$$
which is not a coset. If we multiply using representatives, as in the original question,we also run into problems: if we multiply $(1,2,3)Hcdot(1,3,2)H$ as $(1,2,3)(1,3,2)H$, we get $eH$. But $(1,2,3)H = (1,3)H$, and $(1,3,2)H = (2,3)H$, and if we multiply them by looking at these alternative representatives/names, we get $(1,3)Hcdot (2,3)H = (1,3)(2,3)H = (1,3,2)Hneq eH$. That is, the multiplication rule depends on the name we give the coset, rather than on what the coset is. This means that the rule is not well-defined.
We can let $G$ act on the set of left cosets of $H$, by $g(xH) = gxH$; this is not a group, but a group action. We can also, separately, put group structures on the set of cosets of $H$ in $G$, since it will be a set, and every nonempty set can be given a group structure (assuming the Axiom of Choice; in fact, equivalent to the Axiom of Choice). But that structure will generally have nothing to do with the operation in $G$.
If we want an operation on the set of cosets, and have the operation in the cosets to be induced by the operation in $G$, then we have:
THEOREM. Let $G$ be a group and $H$ a subgroup. Let $G/H = { gHmid gin G}$ be the set of left cosets of $H$ in $G$. The operation
$$cdot colon G/H times G/H to G/Hqquadtext{defined by}qquad (xH)cdot(yH) = (xy)H$$
is well defined (that is, if $xH = x'H$ and $yH=y'H$ then $xyH = x'y'H$) if and only if $H$ is normal in $G$.
Proof. Suppose $H$ is normal. Then $gH=Hg$ for every $gin G$. If $xH=x'H$ and $yH=y'H$, then
$$xyH = x(yH) = x(Hy) = x(Hy') = (xH)y' = (x'H)y' = x'(Hy') = x'(y'H) = x'y'H$$
so the operation is well defined.
Conversely, suppose the operation is well defined so that whenever $xH=x'H$ and $yH=y'H$, then $xyH = x'y'H$. We want to show that $g^{-1}Hgsubseteq H$ for all $gin G$. For each $hin H$, since $hH = eH$, we have $eHgH = egH=gH$ is equal to $hHgH = hgH$. So $gH = hgH$, hence $H=g^{-1}hgH$, so $g^{-1}hgin H$ for each $hin H$. Thus, $g^{-1}Hgsubseteq H$. This holds for any $gin G$, so $g^{-1}Hgsubseteq H$ for all $gin G$, hence $Htriangleleft G$, as claimed. QED
And now I'm going to hijack your question a bit and go on a long excursion to a closely related subject which is not necessary to answer your question, but which I think is interesting. (Sorry!)
This is really connected to the notion of a congruence on an algebra (in the sense of universal algebra). A subgroup $H$ defines an equivalence relation on $G$ by $xsim y$ if and only if $xH = yH$ (it also defines the equivalence relation of right congruence, but ignore that for now). Being an equivalence relation, it corresponds to a subset $Phi$ of $Gtimes G$, with $(x,y)inPhi$ if and only if $xsim y$, if and only if $xH=yH$.
But $Gtimes G$ also has a natural group structure inherited from $G$. Since $Phi$ is a subset of the group $Gtimes G$, it makes sense to ask whether $Phi$ is a subgroup of $Gtimes G$ or not.
THEOREM. $Phi$ is a subgroup of $Gtimes G$ if and only if $H$ is normal in $G$.
Proof. Note that $Phi$ always contains $(e,e)$ (in fact, the entire diagonal). Assume first that $H$ is normal. If $(x,y)in Phi$, then $xH=yH$. Hence, $Hx = Hy$, and taking inverses of each element we get $x^{-1}H = y^{-1}H$, so $(x^{-1},y^{-1})inPhi$; thus, $Phi$ is closed under inverses. If $(x,y),(z,w)inPhi$, then $xH=yH$, $zH=wH$, so by what we proved above we have $xzH = ywH$, so $(xz,yw)=(x,y)(z,w)inPhi$. Thus, $Phi$ is closed under products, so $Phi$ is a subgroup of $Gtimes G$.
Conversely, suppose that $Phi$ is a subgroup. If $xH=yH$ and $zH=wH$, then $(x,y),(z,w)in Phi$, hence $(x,y)(z,w)=(xz,yw)inPhi$; thus, $xzH = ywH$. This proves that the operation $xHcdot zH mapsto xzH$ is well-defined, so by the theorem above $H$ is a normal subgroup of $G$. QED
Added. (Stuff between the two horizontal lines was added in this edit).
Okay, how about this? Can we define some equivalence relation $sim$ on a group $G$ so that we can multiply equivalence classes through representatives, have it be well-defined, but not have $sim$ "come from" a normal subgroup?
That is: suppose $sim$ is an equivalence relation on the group $G$ (any equivalence relation; all we require is that it be reflexive, symmetric, and transitive on the underlying set of $G$), and let $[x]$ denote the equivalence class of $x$ for each $x$ in $G$. We want to define a multiplication on the quotient set $G/sim$ by $[x][y] = [xy]$. When is this well defined?
THEOREM. Let $G$ be a group, and let $sim$ be an equivalence relation on $G$. Then the multiplication on $G/sim$ defined by $[x][y]=[xy]$ is well defined if and only if $sim$ is a subgroup of $Gtimes G$.
Proof. If $sim$ is a subgroup of $Gtimes G$ and $[x]=[z]$, $[y]=[w]$, then $(x,z),(y,w)in sim$, so $(x,z)(y,w) = (xy,zw)in sim$, hence $[xy]=[zw]$, so multiplication is well defined.
Conversely, suppose the multiplication is well defined. Since $sim$ is an equivalence relation, $(e,e)insim$. Also, if $(x,z), (y,w)insim$, then $[x]=[z]$, $[y]=[w]$, so $[x][y]=[xy]$ equals $[z][w]=[zw]$, so $(xy,zw)=(x,y)(z,w)insim$. Thus, $sim$ is a submonoid of $Gtimes G$. It only remains to show that $sim$ is closed under inverses. Suppose that $(x,y)insim$. Multiplying by $(x^{-1},x^{-1})$ on the left and $(y^{-1},y^{-1})$ on the right (both elements of $sim$) we have $(y^{-1},x^{-1})insim$. Since $sim$ is an equivalence relation, it is reflexive, so $(x^{-1},y^{-1})insim$. Thus, $sim$ is a subgroup of $Gtimes G$, as claimed. QED
Okay, so we can define the multiplication on the quotient set if and only if the equivalence relation is a subgroup of $Gtimes G$. Do all such equivalence relations "come" from subgroups? Yes:
THEOREM. Let $sim$ be an equivalence relation on $G$ that is a subgroup of $Gtimes G$, and let $H={gin Gmid gsim e}$. Then $H$ is a normal subgroup of $G$, and $xsim y$ if and only if $xH=yH$.
Proof. We can identify $G$ with the subgroup $Gtimes{e}$ of $Gtimes G$; then $H$ corresponds to the intersection of the subgroup $sim$ and the subgroup $Gtimes{e}$, hence is a subgroup of $G$.
To see that $sim$ is in fact left congruence modulo $H$, simply note that $xH=yH$ if and only if $y^{-1}xin H$, if and only if $(y^{-1}x,e)in sim$, if and only if $(y,y)(y^{-1}x,e)insim$, if and only if $(x,y)in sim$, if and only if $xsim y$. That $H$ is normal now follows because multiplication of cosets (equivalently, of equivalence classes modulo $sim$) is well defined. QED
When we generalize this to an arbitrary algebra (in the sense of universal algebra; examples include magmas, monoids, semigroups, groups, rings, $K$-algebras, lattices, etc), we get the notion of congruence:
Definition. Let $A$ be an algebra (in the sense of universal algebra). A congruence on $A$ is an equivalence relation $Phi$ on $A$ such that $Phi$ is a subalgebra of $Atimes A$.
THEOREM. Let $A$ and $B$ be algebras of the same type, and let $fcolon Ato B$ be a homomorphism; define $Phi_f = {(x,y)in Atimes Amid f(x)=f(y)}$. Then $Phi_f$ is a congruence on $A$. Conversely, if $Psi$ is a congruence on $A$, then there exists an algebra $mathcal{B}$ and a homomorphism $picolon Ato mathcal{B}$ such that $Psi=Phi_{pi}$.
Special case. Let me do the proof with semigroups. First, let $fcolon Ato B$ be a semigroup homomorphism; then $Phi_f$ is an equivalence relation on $A$. To show it is a subsemigroup of $Atimes A$, suppose $(x,y),(z,w)in Phi_f$. Then $f(xz) = f(x)f(z) = f(y)f(w) = f(yw)$, so $(xz,yw)inPhi_f$. Thus, $Phi_f$ is a subsemigroup of $Atimes A$, hence a congruence.
Conversely, suppose that $Psi$ is a congruence. Let $mathcal{B}=A/Psi$, the set of equivalence classes of $Psi$ in $A$. Let $[x]$ denote the class of $x$. We define a multiplication on $mathcal{B}$ by $[a][b]=[ab]$. We must prove that this is well defined: suppose $[x]=[y]$ and $[z]=[w]$. Then $(x,y),(z,w)inPsi$, so $(xz,yw)inPsi$ (since $Psi$ is a congruence). Therefore, $[xz]=[yw]$, so multiplication is well-defined. It is now easy to verify that multiplication is associative:
$$[x]([y][z]) = [x][yz] = [x(yz)]=[(xy)z] = [xy][z] = ([x][y])[z].$$
Thus, $mathcal{B}$ is a semigroup. The map $picolon Ato mathcal{B}$ given by $pi(a)=[a]$ is easily verified to be a homomorphism, and $Phi_{pi}=Psi$.
The proof for an arbitrary algebra with operations $f_1,ldots,f_k$ of arities $a_1,ldots,a_k$ (or even an infinite number of operations, each with finite arities) is essentially the same.
QED
One can then prove the Isomorphism Theorems for "congruences" in exactly the analogous manner as for groups and rings, for any class of algebras.
In Groups and Rings, we can "get away" with not studying congruences because if $Phi$ is a congruence on $G$, then we can let $N = { gin Gmid (g,e)inPhi}$, and it turns out that $Phi$ is the equivalence relation induced by $N$. Essentially, a congruence tells you that certain things are equal, but in groups (and rings), instead of saying "$x$ is equal to $y$", we can say "$xy^{-1}$ is the identity". The normal subgroup (resp. the ideal) is the set of elements equivalent to the identity. In more general classes, such as semigroups, we don't have the luxury of expressing any identity in the form $w=e$, so we must actually keep track of both sides of the equality.
This is all part of Universal Algebra. I cannot recommend George Bergman's book highly enough if you want a great introduction to the subject (with a Category Theory flavor).
$endgroup$
4
$begingroup$
Wow, you really wanted to get a point across, didn't you? :D Thumbs up!
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 3:47
12
$begingroup$
@Alexei: Not "get a point across", but rather take the opportunity to point out a bunch of ideas that come together and happen to show that "normal subgroups" is the only game in town when you want to define "quotient groups". I happen to like the idea of congruences better than normal subgroups because they are more "natural": you just define $asim b Longleftrightarrow f(a)=f(b)$; it is a bit of a historical accident that in the first two abstract structures it turns out we can "codify" the congruence with a substructure-with-something-extra (normal subgroups for groups, ideals for rings).
$endgroup$
– Arturo Magidin
Dec 15 '10 at 3:51
$begingroup$
Yes, these are pretty interesting ideas. Thank you :)
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 9:19
4
$begingroup$
This was an awesome answer, and your reference of Bergman's text looks great. Thank you.
$endgroup$
– Hans Parshall
Dec 16 '10 at 1:28
add a comment |
$begingroup$
Added. So, what is the problem? Let's look at the simplest example of a non-normal subgroup. Take $G=S_3$, and $H={e,(1,2)}$. If we compose permutations right to left, the left cosets of $H$ in $G$ are:
begin{align*}
eH = (1,2)H &= { e, (1,2)};\
(1,2,3)H = (1,3)H &= {(1,2,3), (1,3)};\
(1,3,2)H = (2,3)H &= {(1,3,2), (2,3)}.
end{align*}
If we try multiplying cosets term-by-term, we run into problems. Multiplying by $eH$ is not a problem, but take $(1,2,3)H$ multiplied by itself. The products are:
$${ (1,2,3)(1,2,3), (1,2,3)(1,3), (1,3)(1,2,3), (1,3)(1,3)} = {(1,3,2), (2,3), (1,2), e}$$
which is not a coset. If we multiply using representatives, as in the original question,we also run into problems: if we multiply $(1,2,3)Hcdot(1,3,2)H$ as $(1,2,3)(1,3,2)H$, we get $eH$. But $(1,2,3)H = (1,3)H$, and $(1,3,2)H = (2,3)H$, and if we multiply them by looking at these alternative representatives/names, we get $(1,3)Hcdot (2,3)H = (1,3)(2,3)H = (1,3,2)Hneq eH$. That is, the multiplication rule depends on the name we give the coset, rather than on what the coset is. This means that the rule is not well-defined.
We can let $G$ act on the set of left cosets of $H$, by $g(xH) = gxH$; this is not a group, but a group action. We can also, separately, put group structures on the set of cosets of $H$ in $G$, since it will be a set, and every nonempty set can be given a group structure (assuming the Axiom of Choice; in fact, equivalent to the Axiom of Choice). But that structure will generally have nothing to do with the operation in $G$.
If we want an operation on the set of cosets, and have the operation in the cosets to be induced by the operation in $G$, then we have:
THEOREM. Let $G$ be a group and $H$ a subgroup. Let $G/H = { gHmid gin G}$ be the set of left cosets of $H$ in $G$. The operation
$$cdot colon G/H times G/H to G/Hqquadtext{defined by}qquad (xH)cdot(yH) = (xy)H$$
is well defined (that is, if $xH = x'H$ and $yH=y'H$ then $xyH = x'y'H$) if and only if $H$ is normal in $G$.
Proof. Suppose $H$ is normal. Then $gH=Hg$ for every $gin G$. If $xH=x'H$ and $yH=y'H$, then
$$xyH = x(yH) = x(Hy) = x(Hy') = (xH)y' = (x'H)y' = x'(Hy') = x'(y'H) = x'y'H$$
so the operation is well defined.
Conversely, suppose the operation is well defined so that whenever $xH=x'H$ and $yH=y'H$, then $xyH = x'y'H$. We want to show that $g^{-1}Hgsubseteq H$ for all $gin G$. For each $hin H$, since $hH = eH$, we have $eHgH = egH=gH$ is equal to $hHgH = hgH$. So $gH = hgH$, hence $H=g^{-1}hgH$, so $g^{-1}hgin H$ for each $hin H$. Thus, $g^{-1}Hgsubseteq H$. This holds for any $gin G$, so $g^{-1}Hgsubseteq H$ for all $gin G$, hence $Htriangleleft G$, as claimed. QED
And now I'm going to hijack your question a bit and go on a long excursion to a closely related subject which is not necessary to answer your question, but which I think is interesting. (Sorry!)
This is really connected to the notion of a congruence on an algebra (in the sense of universal algebra). A subgroup $H$ defines an equivalence relation on $G$ by $xsim y$ if and only if $xH = yH$ (it also defines the equivalence relation of right congruence, but ignore that for now). Being an equivalence relation, it corresponds to a subset $Phi$ of $Gtimes G$, with $(x,y)inPhi$ if and only if $xsim y$, if and only if $xH=yH$.
But $Gtimes G$ also has a natural group structure inherited from $G$. Since $Phi$ is a subset of the group $Gtimes G$, it makes sense to ask whether $Phi$ is a subgroup of $Gtimes G$ or not.
THEOREM. $Phi$ is a subgroup of $Gtimes G$ if and only if $H$ is normal in $G$.
Proof. Note that $Phi$ always contains $(e,e)$ (in fact, the entire diagonal). Assume first that $H$ is normal. If $(x,y)in Phi$, then $xH=yH$. Hence, $Hx = Hy$, and taking inverses of each element we get $x^{-1}H = y^{-1}H$, so $(x^{-1},y^{-1})inPhi$; thus, $Phi$ is closed under inverses. If $(x,y),(z,w)inPhi$, then $xH=yH$, $zH=wH$, so by what we proved above we have $xzH = ywH$, so $(xz,yw)=(x,y)(z,w)inPhi$. Thus, $Phi$ is closed under products, so $Phi$ is a subgroup of $Gtimes G$.
Conversely, suppose that $Phi$ is a subgroup. If $xH=yH$ and $zH=wH$, then $(x,y),(z,w)in Phi$, hence $(x,y)(z,w)=(xz,yw)inPhi$; thus, $xzH = ywH$. This proves that the operation $xHcdot zH mapsto xzH$ is well-defined, so by the theorem above $H$ is a normal subgroup of $G$. QED
Added. (Stuff between the two horizontal lines was added in this edit).
Okay, how about this? Can we define some equivalence relation $sim$ on a group $G$ so that we can multiply equivalence classes through representatives, have it be well-defined, but not have $sim$ "come from" a normal subgroup?
That is: suppose $sim$ is an equivalence relation on the group $G$ (any equivalence relation; all we require is that it be reflexive, symmetric, and transitive on the underlying set of $G$), and let $[x]$ denote the equivalence class of $x$ for each $x$ in $G$. We want to define a multiplication on the quotient set $G/sim$ by $[x][y] = [xy]$. When is this well defined?
THEOREM. Let $G$ be a group, and let $sim$ be an equivalence relation on $G$. Then the multiplication on $G/sim$ defined by $[x][y]=[xy]$ is well defined if and only if $sim$ is a subgroup of $Gtimes G$.
Proof. If $sim$ is a subgroup of $Gtimes G$ and $[x]=[z]$, $[y]=[w]$, then $(x,z),(y,w)in sim$, so $(x,z)(y,w) = (xy,zw)in sim$, hence $[xy]=[zw]$, so multiplication is well defined.
Conversely, suppose the multiplication is well defined. Since $sim$ is an equivalence relation, $(e,e)insim$. Also, if $(x,z), (y,w)insim$, then $[x]=[z]$, $[y]=[w]$, so $[x][y]=[xy]$ equals $[z][w]=[zw]$, so $(xy,zw)=(x,y)(z,w)insim$. Thus, $sim$ is a submonoid of $Gtimes G$. It only remains to show that $sim$ is closed under inverses. Suppose that $(x,y)insim$. Multiplying by $(x^{-1},x^{-1})$ on the left and $(y^{-1},y^{-1})$ on the right (both elements of $sim$) we have $(y^{-1},x^{-1})insim$. Since $sim$ is an equivalence relation, it is reflexive, so $(x^{-1},y^{-1})insim$. Thus, $sim$ is a subgroup of $Gtimes G$, as claimed. QED
Okay, so we can define the multiplication on the quotient set if and only if the equivalence relation is a subgroup of $Gtimes G$. Do all such equivalence relations "come" from subgroups? Yes:
THEOREM. Let $sim$ be an equivalence relation on $G$ that is a subgroup of $Gtimes G$, and let $H={gin Gmid gsim e}$. Then $H$ is a normal subgroup of $G$, and $xsim y$ if and only if $xH=yH$.
Proof. We can identify $G$ with the subgroup $Gtimes{e}$ of $Gtimes G$; then $H$ corresponds to the intersection of the subgroup $sim$ and the subgroup $Gtimes{e}$, hence is a subgroup of $G$.
To see that $sim$ is in fact left congruence modulo $H$, simply note that $xH=yH$ if and only if $y^{-1}xin H$, if and only if $(y^{-1}x,e)in sim$, if and only if $(y,y)(y^{-1}x,e)insim$, if and only if $(x,y)in sim$, if and only if $xsim y$. That $H$ is normal now follows because multiplication of cosets (equivalently, of equivalence classes modulo $sim$) is well defined. QED
When we generalize this to an arbitrary algebra (in the sense of universal algebra; examples include magmas, monoids, semigroups, groups, rings, $K$-algebras, lattices, etc), we get the notion of congruence:
Definition. Let $A$ be an algebra (in the sense of universal algebra). A congruence on $A$ is an equivalence relation $Phi$ on $A$ such that $Phi$ is a subalgebra of $Atimes A$.
THEOREM. Let $A$ and $B$ be algebras of the same type, and let $fcolon Ato B$ be a homomorphism; define $Phi_f = {(x,y)in Atimes Amid f(x)=f(y)}$. Then $Phi_f$ is a congruence on $A$. Conversely, if $Psi$ is a congruence on $A$, then there exists an algebra $mathcal{B}$ and a homomorphism $picolon Ato mathcal{B}$ such that $Psi=Phi_{pi}$.
Special case. Let me do the proof with semigroups. First, let $fcolon Ato B$ be a semigroup homomorphism; then $Phi_f$ is an equivalence relation on $A$. To show it is a subsemigroup of $Atimes A$, suppose $(x,y),(z,w)in Phi_f$. Then $f(xz) = f(x)f(z) = f(y)f(w) = f(yw)$, so $(xz,yw)inPhi_f$. Thus, $Phi_f$ is a subsemigroup of $Atimes A$, hence a congruence.
Conversely, suppose that $Psi$ is a congruence. Let $mathcal{B}=A/Psi$, the set of equivalence classes of $Psi$ in $A$. Let $[x]$ denote the class of $x$. We define a multiplication on $mathcal{B}$ by $[a][b]=[ab]$. We must prove that this is well defined: suppose $[x]=[y]$ and $[z]=[w]$. Then $(x,y),(z,w)inPsi$, so $(xz,yw)inPsi$ (since $Psi$ is a congruence). Therefore, $[xz]=[yw]$, so multiplication is well-defined. It is now easy to verify that multiplication is associative:
$$[x]([y][z]) = [x][yz] = [x(yz)]=[(xy)z] = [xy][z] = ([x][y])[z].$$
Thus, $mathcal{B}$ is a semigroup. The map $picolon Ato mathcal{B}$ given by $pi(a)=[a]$ is easily verified to be a homomorphism, and $Phi_{pi}=Psi$.
The proof for an arbitrary algebra with operations $f_1,ldots,f_k$ of arities $a_1,ldots,a_k$ (or even an infinite number of operations, each with finite arities) is essentially the same.
QED
One can then prove the Isomorphism Theorems for "congruences" in exactly the analogous manner as for groups and rings, for any class of algebras.
In Groups and Rings, we can "get away" with not studying congruences because if $Phi$ is a congruence on $G$, then we can let $N = { gin Gmid (g,e)inPhi}$, and it turns out that $Phi$ is the equivalence relation induced by $N$. Essentially, a congruence tells you that certain things are equal, but in groups (and rings), instead of saying "$x$ is equal to $y$", we can say "$xy^{-1}$ is the identity". The normal subgroup (resp. the ideal) is the set of elements equivalent to the identity. In more general classes, such as semigroups, we don't have the luxury of expressing any identity in the form $w=e$, so we must actually keep track of both sides of the equality.
This is all part of Universal Algebra. I cannot recommend George Bergman's book highly enough if you want a great introduction to the subject (with a Category Theory flavor).
$endgroup$
Added. So, what is the problem? Let's look at the simplest example of a non-normal subgroup. Take $G=S_3$, and $H={e,(1,2)}$. If we compose permutations right to left, the left cosets of $H$ in $G$ are:
begin{align*}
eH = (1,2)H &= { e, (1,2)};\
(1,2,3)H = (1,3)H &= {(1,2,3), (1,3)};\
(1,3,2)H = (2,3)H &= {(1,3,2), (2,3)}.
end{align*}
If we try multiplying cosets term-by-term, we run into problems. Multiplying by $eH$ is not a problem, but take $(1,2,3)H$ multiplied by itself. The products are:
$${ (1,2,3)(1,2,3), (1,2,3)(1,3), (1,3)(1,2,3), (1,3)(1,3)} = {(1,3,2), (2,3), (1,2), e}$$
which is not a coset. If we multiply using representatives, as in the original question,we also run into problems: if we multiply $(1,2,3)Hcdot(1,3,2)H$ as $(1,2,3)(1,3,2)H$, we get $eH$. But $(1,2,3)H = (1,3)H$, and $(1,3,2)H = (2,3)H$, and if we multiply them by looking at these alternative representatives/names, we get $(1,3)Hcdot (2,3)H = (1,3)(2,3)H = (1,3,2)Hneq eH$. That is, the multiplication rule depends on the name we give the coset, rather than on what the coset is. This means that the rule is not well-defined.
We can let $G$ act on the set of left cosets of $H$, by $g(xH) = gxH$; this is not a group, but a group action. We can also, separately, put group structures on the set of cosets of $H$ in $G$, since it will be a set, and every nonempty set can be given a group structure (assuming the Axiom of Choice; in fact, equivalent to the Axiom of Choice). But that structure will generally have nothing to do with the operation in $G$.
If we want an operation on the set of cosets, and have the operation in the cosets to be induced by the operation in $G$, then we have:
THEOREM. Let $G$ be a group and $H$ a subgroup. Let $G/H = { gHmid gin G}$ be the set of left cosets of $H$ in $G$. The operation
$$cdot colon G/H times G/H to G/Hqquadtext{defined by}qquad (xH)cdot(yH) = (xy)H$$
is well defined (that is, if $xH = x'H$ and $yH=y'H$ then $xyH = x'y'H$) if and only if $H$ is normal in $G$.
Proof. Suppose $H$ is normal. Then $gH=Hg$ for every $gin G$. If $xH=x'H$ and $yH=y'H$, then
$$xyH = x(yH) = x(Hy) = x(Hy') = (xH)y' = (x'H)y' = x'(Hy') = x'(y'H) = x'y'H$$
so the operation is well defined.
Conversely, suppose the operation is well defined so that whenever $xH=x'H$ and $yH=y'H$, then $xyH = x'y'H$. We want to show that $g^{-1}Hgsubseteq H$ for all $gin G$. For each $hin H$, since $hH = eH$, we have $eHgH = egH=gH$ is equal to $hHgH = hgH$. So $gH = hgH$, hence $H=g^{-1}hgH$, so $g^{-1}hgin H$ for each $hin H$. Thus, $g^{-1}Hgsubseteq H$. This holds for any $gin G$, so $g^{-1}Hgsubseteq H$ for all $gin G$, hence $Htriangleleft G$, as claimed. QED
And now I'm going to hijack your question a bit and go on a long excursion to a closely related subject which is not necessary to answer your question, but which I think is interesting. (Sorry!)
This is really connected to the notion of a congruence on an algebra (in the sense of universal algebra). A subgroup $H$ defines an equivalence relation on $G$ by $xsim y$ if and only if $xH = yH$ (it also defines the equivalence relation of right congruence, but ignore that for now). Being an equivalence relation, it corresponds to a subset $Phi$ of $Gtimes G$, with $(x,y)inPhi$ if and only if $xsim y$, if and only if $xH=yH$.
But $Gtimes G$ also has a natural group structure inherited from $G$. Since $Phi$ is a subset of the group $Gtimes G$, it makes sense to ask whether $Phi$ is a subgroup of $Gtimes G$ or not.
THEOREM. $Phi$ is a subgroup of $Gtimes G$ if and only if $H$ is normal in $G$.
Proof. Note that $Phi$ always contains $(e,e)$ (in fact, the entire diagonal). Assume first that $H$ is normal. If $(x,y)in Phi$, then $xH=yH$. Hence, $Hx = Hy$, and taking inverses of each element we get $x^{-1}H = y^{-1}H$, so $(x^{-1},y^{-1})inPhi$; thus, $Phi$ is closed under inverses. If $(x,y),(z,w)inPhi$, then $xH=yH$, $zH=wH$, so by what we proved above we have $xzH = ywH$, so $(xz,yw)=(x,y)(z,w)inPhi$. Thus, $Phi$ is closed under products, so $Phi$ is a subgroup of $Gtimes G$.
Conversely, suppose that $Phi$ is a subgroup. If $xH=yH$ and $zH=wH$, then $(x,y),(z,w)in Phi$, hence $(x,y)(z,w)=(xz,yw)inPhi$; thus, $xzH = ywH$. This proves that the operation $xHcdot zH mapsto xzH$ is well-defined, so by the theorem above $H$ is a normal subgroup of $G$. QED
Added. (Stuff between the two horizontal lines was added in this edit).
Okay, how about this? Can we define some equivalence relation $sim$ on a group $G$ so that we can multiply equivalence classes through representatives, have it be well-defined, but not have $sim$ "come from" a normal subgroup?
That is: suppose $sim$ is an equivalence relation on the group $G$ (any equivalence relation; all we require is that it be reflexive, symmetric, and transitive on the underlying set of $G$), and let $[x]$ denote the equivalence class of $x$ for each $x$ in $G$. We want to define a multiplication on the quotient set $G/sim$ by $[x][y] = [xy]$. When is this well defined?
THEOREM. Let $G$ be a group, and let $sim$ be an equivalence relation on $G$. Then the multiplication on $G/sim$ defined by $[x][y]=[xy]$ is well defined if and only if $sim$ is a subgroup of $Gtimes G$.
Proof. If $sim$ is a subgroup of $Gtimes G$ and $[x]=[z]$, $[y]=[w]$, then $(x,z),(y,w)in sim$, so $(x,z)(y,w) = (xy,zw)in sim$, hence $[xy]=[zw]$, so multiplication is well defined.
Conversely, suppose the multiplication is well defined. Since $sim$ is an equivalence relation, $(e,e)insim$. Also, if $(x,z), (y,w)insim$, then $[x]=[z]$, $[y]=[w]$, so $[x][y]=[xy]$ equals $[z][w]=[zw]$, so $(xy,zw)=(x,y)(z,w)insim$. Thus, $sim$ is a submonoid of $Gtimes G$. It only remains to show that $sim$ is closed under inverses. Suppose that $(x,y)insim$. Multiplying by $(x^{-1},x^{-1})$ on the left and $(y^{-1},y^{-1})$ on the right (both elements of $sim$) we have $(y^{-1},x^{-1})insim$. Since $sim$ is an equivalence relation, it is reflexive, so $(x^{-1},y^{-1})insim$. Thus, $sim$ is a subgroup of $Gtimes G$, as claimed. QED
Okay, so we can define the multiplication on the quotient set if and only if the equivalence relation is a subgroup of $Gtimes G$. Do all such equivalence relations "come" from subgroups? Yes:
THEOREM. Let $sim$ be an equivalence relation on $G$ that is a subgroup of $Gtimes G$, and let $H={gin Gmid gsim e}$. Then $H$ is a normal subgroup of $G$, and $xsim y$ if and only if $xH=yH$.
Proof. We can identify $G$ with the subgroup $Gtimes{e}$ of $Gtimes G$; then $H$ corresponds to the intersection of the subgroup $sim$ and the subgroup $Gtimes{e}$, hence is a subgroup of $G$.
To see that $sim$ is in fact left congruence modulo $H$, simply note that $xH=yH$ if and only if $y^{-1}xin H$, if and only if $(y^{-1}x,e)in sim$, if and only if $(y,y)(y^{-1}x,e)insim$, if and only if $(x,y)in sim$, if and only if $xsim y$. That $H$ is normal now follows because multiplication of cosets (equivalently, of equivalence classes modulo $sim$) is well defined. QED
When we generalize this to an arbitrary algebra (in the sense of universal algebra; examples include magmas, monoids, semigroups, groups, rings, $K$-algebras, lattices, etc), we get the notion of congruence:
Definition. Let $A$ be an algebra (in the sense of universal algebra). A congruence on $A$ is an equivalence relation $Phi$ on $A$ such that $Phi$ is a subalgebra of $Atimes A$.
THEOREM. Let $A$ and $B$ be algebras of the same type, and let $fcolon Ato B$ be a homomorphism; define $Phi_f = {(x,y)in Atimes Amid f(x)=f(y)}$. Then $Phi_f$ is a congruence on $A$. Conversely, if $Psi$ is a congruence on $A$, then there exists an algebra $mathcal{B}$ and a homomorphism $picolon Ato mathcal{B}$ such that $Psi=Phi_{pi}$.
Special case. Let me do the proof with semigroups. First, let $fcolon Ato B$ be a semigroup homomorphism; then $Phi_f$ is an equivalence relation on $A$. To show it is a subsemigroup of $Atimes A$, suppose $(x,y),(z,w)in Phi_f$. Then $f(xz) = f(x)f(z) = f(y)f(w) = f(yw)$, so $(xz,yw)inPhi_f$. Thus, $Phi_f$ is a subsemigroup of $Atimes A$, hence a congruence.
Conversely, suppose that $Psi$ is a congruence. Let $mathcal{B}=A/Psi$, the set of equivalence classes of $Psi$ in $A$. Let $[x]$ denote the class of $x$. We define a multiplication on $mathcal{B}$ by $[a][b]=[ab]$. We must prove that this is well defined: suppose $[x]=[y]$ and $[z]=[w]$. Then $(x,y),(z,w)inPsi$, so $(xz,yw)inPsi$ (since $Psi$ is a congruence). Therefore, $[xz]=[yw]$, so multiplication is well-defined. It is now easy to verify that multiplication is associative:
$$[x]([y][z]) = [x][yz] = [x(yz)]=[(xy)z] = [xy][z] = ([x][y])[z].$$
Thus, $mathcal{B}$ is a semigroup. The map $picolon Ato mathcal{B}$ given by $pi(a)=[a]$ is easily verified to be a homomorphism, and $Phi_{pi}=Psi$.
The proof for an arbitrary algebra with operations $f_1,ldots,f_k$ of arities $a_1,ldots,a_k$ (or even an infinite number of operations, each with finite arities) is essentially the same.
QED
One can then prove the Isomorphism Theorems for "congruences" in exactly the analogous manner as for groups and rings, for any class of algebras.
In Groups and Rings, we can "get away" with not studying congruences because if $Phi$ is a congruence on $G$, then we can let $N = { gin Gmid (g,e)inPhi}$, and it turns out that $Phi$ is the equivalence relation induced by $N$. Essentially, a congruence tells you that certain things are equal, but in groups (and rings), instead of saying "$x$ is equal to $y$", we can say "$xy^{-1}$ is the identity". The normal subgroup (resp. the ideal) is the set of elements equivalent to the identity. In more general classes, such as semigroups, we don't have the luxury of expressing any identity in the form $w=e$, so we must actually keep track of both sides of the equality.
This is all part of Universal Algebra. I cannot recommend George Bergman's book highly enough if you want a great introduction to the subject (with a Category Theory flavor).
edited Feb 14 '12 at 6:06
Srivatsan
21k371126
21k371126
answered Dec 14 '10 at 17:26
Arturo MagidinArturo Magidin
266k34590920
266k34590920
4
$begingroup$
Wow, you really wanted to get a point across, didn't you? :D Thumbs up!
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 3:47
12
$begingroup$
@Alexei: Not "get a point across", but rather take the opportunity to point out a bunch of ideas that come together and happen to show that "normal subgroups" is the only game in town when you want to define "quotient groups". I happen to like the idea of congruences better than normal subgroups because they are more "natural": you just define $asim b Longleftrightarrow f(a)=f(b)$; it is a bit of a historical accident that in the first two abstract structures it turns out we can "codify" the congruence with a substructure-with-something-extra (normal subgroups for groups, ideals for rings).
$endgroup$
– Arturo Magidin
Dec 15 '10 at 3:51
$begingroup$
Yes, these are pretty interesting ideas. Thank you :)
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 9:19
4
$begingroup$
This was an awesome answer, and your reference of Bergman's text looks great. Thank you.
$endgroup$
– Hans Parshall
Dec 16 '10 at 1:28
add a comment |
4
$begingroup$
Wow, you really wanted to get a point across, didn't you? :D Thumbs up!
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 3:47
12
$begingroup$
@Alexei: Not "get a point across", but rather take the opportunity to point out a bunch of ideas that come together and happen to show that "normal subgroups" is the only game in town when you want to define "quotient groups". I happen to like the idea of congruences better than normal subgroups because they are more "natural": you just define $asim b Longleftrightarrow f(a)=f(b)$; it is a bit of a historical accident that in the first two abstract structures it turns out we can "codify" the congruence with a substructure-with-something-extra (normal subgroups for groups, ideals for rings).
$endgroup$
– Arturo Magidin
Dec 15 '10 at 3:51
$begingroup$
Yes, these are pretty interesting ideas. Thank you :)
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 9:19
4
$begingroup$
This was an awesome answer, and your reference of Bergman's text looks great. Thank you.
$endgroup$
– Hans Parshall
Dec 16 '10 at 1:28
4
4
$begingroup$
Wow, you really wanted to get a point across, didn't you? :D Thumbs up!
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 3:47
$begingroup$
Wow, you really wanted to get a point across, didn't you? :D Thumbs up!
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 3:47
12
12
$begingroup$
@Alexei: Not "get a point across", but rather take the opportunity to point out a bunch of ideas that come together and happen to show that "normal subgroups" is the only game in town when you want to define "quotient groups". I happen to like the idea of congruences better than normal subgroups because they are more "natural": you just define $asim b Longleftrightarrow f(a)=f(b)$; it is a bit of a historical accident that in the first two abstract structures it turns out we can "codify" the congruence with a substructure-with-something-extra (normal subgroups for groups, ideals for rings).
$endgroup$
– Arturo Magidin
Dec 15 '10 at 3:51
$begingroup$
@Alexei: Not "get a point across", but rather take the opportunity to point out a bunch of ideas that come together and happen to show that "normal subgroups" is the only game in town when you want to define "quotient groups". I happen to like the idea of congruences better than normal subgroups because they are more "natural": you just define $asim b Longleftrightarrow f(a)=f(b)$; it is a bit of a historical accident that in the first two abstract structures it turns out we can "codify" the congruence with a substructure-with-something-extra (normal subgroups for groups, ideals for rings).
$endgroup$
– Arturo Magidin
Dec 15 '10 at 3:51
$begingroup$
Yes, these are pretty interesting ideas. Thank you :)
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 9:19
$begingroup$
Yes, these are pretty interesting ideas. Thank you :)
$endgroup$
– Alexei Averchenko
Dec 15 '10 at 9:19
4
4
$begingroup$
This was an awesome answer, and your reference of Bergman's text looks great. Thank you.
$endgroup$
– Hans Parshall
Dec 16 '10 at 1:28
$begingroup$
This was an awesome answer, and your reference of Bergman's text looks great. Thank you.
$endgroup$
– Hans Parshall
Dec 16 '10 at 1:28
add a comment |
$begingroup$
(Sorry, new here, can't comment.)
To expand on Alex's answer, if we demand that $(xh)(yh) in (xy)H$ for any coset representative $h$, then this is equivalent to asking that $y^{-1}hyh in H$ for all $h in H$. But the conjugate $y^{-1}hy$ need not lie in $H$ if $H$ isn't normal, hence the claim that the operation in your "left quotient group" isn't well defined.
$endgroup$
$begingroup$
$(xH)(yH) mapsto (xy)H$ need not be generated by the group operation of $G$; sure, if you constrain yourself to such an operation you do need a normal subgroup. I probably confused you with my notation :) However, another kind of problem arises, see my response to Alex.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:00
$begingroup$
This doesn't fix the problem. See Tobais's answer. No matter how we look at the group operation, it has to be independent of which coset representatives we choose. The problem is easiest to see if you just consider the product $(xh)(yh)$ like I do above, but expand Tobais's $(xy)H=(x'y')H$ and you'll still get a term like $y^{-1}hyh$ which needs to be in $H$. Therefore $H$ must be normal.
$endgroup$
– Jon
Dec 14 '10 at 13:46
$begingroup$
Unfortunately, if we just think of cosets as of elements of $G/H$ your answer doesn't get the point :P
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 14:56
2
$begingroup$
It seems like some of the confusion is coming from whether or not we can put a different group structure on the set of cosets $G/H$. Perhaps we can, but we certainly wouldn't call it the quotient group of $G$ by $H$ because it has nothing to do with $G$ or $H$ as groups.
$endgroup$
– Sean Tilson
Dec 14 '10 at 16:26
3
$begingroup$
@Sean Tilson: It is equivalent to the Axiom of Choice that every nonempty set can be given a group structure. Certainly, the set of cosets is a set, so we can give it a group structure (assuming AC), but which will likely have nothing to do with the operation in $G$.
$endgroup$
– Arturo Magidin
Dec 14 '10 at 18:05
|
show 3 more comments
$begingroup$
(Sorry, new here, can't comment.)
To expand on Alex's answer, if we demand that $(xh)(yh) in (xy)H$ for any coset representative $h$, then this is equivalent to asking that $y^{-1}hyh in H$ for all $h in H$. But the conjugate $y^{-1}hy$ need not lie in $H$ if $H$ isn't normal, hence the claim that the operation in your "left quotient group" isn't well defined.
$endgroup$
$begingroup$
$(xH)(yH) mapsto (xy)H$ need not be generated by the group operation of $G$; sure, if you constrain yourself to such an operation you do need a normal subgroup. I probably confused you with my notation :) However, another kind of problem arises, see my response to Alex.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:00
$begingroup$
This doesn't fix the problem. See Tobais's answer. No matter how we look at the group operation, it has to be independent of which coset representatives we choose. The problem is easiest to see if you just consider the product $(xh)(yh)$ like I do above, but expand Tobais's $(xy)H=(x'y')H$ and you'll still get a term like $y^{-1}hyh$ which needs to be in $H$. Therefore $H$ must be normal.
$endgroup$
– Jon
Dec 14 '10 at 13:46
$begingroup$
Unfortunately, if we just think of cosets as of elements of $G/H$ your answer doesn't get the point :P
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 14:56
2
$begingroup$
It seems like some of the confusion is coming from whether or not we can put a different group structure on the set of cosets $G/H$. Perhaps we can, but we certainly wouldn't call it the quotient group of $G$ by $H$ because it has nothing to do with $G$ or $H$ as groups.
$endgroup$
– Sean Tilson
Dec 14 '10 at 16:26
3
$begingroup$
@Sean Tilson: It is equivalent to the Axiom of Choice that every nonempty set can be given a group structure. Certainly, the set of cosets is a set, so we can give it a group structure (assuming AC), but which will likely have nothing to do with the operation in $G$.
$endgroup$
– Arturo Magidin
Dec 14 '10 at 18:05
|
show 3 more comments
$begingroup$
(Sorry, new here, can't comment.)
To expand on Alex's answer, if we demand that $(xh)(yh) in (xy)H$ for any coset representative $h$, then this is equivalent to asking that $y^{-1}hyh in H$ for all $h in H$. But the conjugate $y^{-1}hy$ need not lie in $H$ if $H$ isn't normal, hence the claim that the operation in your "left quotient group" isn't well defined.
$endgroup$
(Sorry, new here, can't comment.)
To expand on Alex's answer, if we demand that $(xh)(yh) in (xy)H$ for any coset representative $h$, then this is equivalent to asking that $y^{-1}hyh in H$ for all $h in H$. But the conjugate $y^{-1}hy$ need not lie in $H$ if $H$ isn't normal, hence the claim that the operation in your "left quotient group" isn't well defined.
answered Dec 14 '10 at 12:34
JonJon
1,35711623
1,35711623
$begingroup$
$(xH)(yH) mapsto (xy)H$ need not be generated by the group operation of $G$; sure, if you constrain yourself to such an operation you do need a normal subgroup. I probably confused you with my notation :) However, another kind of problem arises, see my response to Alex.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:00
$begingroup$
This doesn't fix the problem. See Tobais's answer. No matter how we look at the group operation, it has to be independent of which coset representatives we choose. The problem is easiest to see if you just consider the product $(xh)(yh)$ like I do above, but expand Tobais's $(xy)H=(x'y')H$ and you'll still get a term like $y^{-1}hyh$ which needs to be in $H$. Therefore $H$ must be normal.
$endgroup$
– Jon
Dec 14 '10 at 13:46
$begingroup$
Unfortunately, if we just think of cosets as of elements of $G/H$ your answer doesn't get the point :P
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 14:56
2
$begingroup$
It seems like some of the confusion is coming from whether or not we can put a different group structure on the set of cosets $G/H$. Perhaps we can, but we certainly wouldn't call it the quotient group of $G$ by $H$ because it has nothing to do with $G$ or $H$ as groups.
$endgroup$
– Sean Tilson
Dec 14 '10 at 16:26
3
$begingroup$
@Sean Tilson: It is equivalent to the Axiom of Choice that every nonempty set can be given a group structure. Certainly, the set of cosets is a set, so we can give it a group structure (assuming AC), but which will likely have nothing to do with the operation in $G$.
$endgroup$
– Arturo Magidin
Dec 14 '10 at 18:05
|
show 3 more comments
$begingroup$
$(xH)(yH) mapsto (xy)H$ need not be generated by the group operation of $G$; sure, if you constrain yourself to such an operation you do need a normal subgroup. I probably confused you with my notation :) However, another kind of problem arises, see my response to Alex.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:00
$begingroup$
This doesn't fix the problem. See Tobais's answer. No matter how we look at the group operation, it has to be independent of which coset representatives we choose. The problem is easiest to see if you just consider the product $(xh)(yh)$ like I do above, but expand Tobais's $(xy)H=(x'y')H$ and you'll still get a term like $y^{-1}hyh$ which needs to be in $H$. Therefore $H$ must be normal.
$endgroup$
– Jon
Dec 14 '10 at 13:46
$begingroup$
Unfortunately, if we just think of cosets as of elements of $G/H$ your answer doesn't get the point :P
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 14:56
2
$begingroup$
It seems like some of the confusion is coming from whether or not we can put a different group structure on the set of cosets $G/H$. Perhaps we can, but we certainly wouldn't call it the quotient group of $G$ by $H$ because it has nothing to do with $G$ or $H$ as groups.
$endgroup$
– Sean Tilson
Dec 14 '10 at 16:26
3
$begingroup$
@Sean Tilson: It is equivalent to the Axiom of Choice that every nonempty set can be given a group structure. Certainly, the set of cosets is a set, so we can give it a group structure (assuming AC), but which will likely have nothing to do with the operation in $G$.
$endgroup$
– Arturo Magidin
Dec 14 '10 at 18:05
$begingroup$
$(xH)(yH) mapsto (xy)H$ need not be generated by the group operation of $G$; sure, if you constrain yourself to such an operation you do need a normal subgroup. I probably confused you with my notation :) However, another kind of problem arises, see my response to Alex.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:00
$begingroup$
$(xH)(yH) mapsto (xy)H$ need not be generated by the group operation of $G$; sure, if you constrain yourself to such an operation you do need a normal subgroup. I probably confused you with my notation :) However, another kind of problem arises, see my response to Alex.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:00
$begingroup$
This doesn't fix the problem. See Tobais's answer. No matter how we look at the group operation, it has to be independent of which coset representatives we choose. The problem is easiest to see if you just consider the product $(xh)(yh)$ like I do above, but expand Tobais's $(xy)H=(x'y')H$ and you'll still get a term like $y^{-1}hyh$ which needs to be in $H$. Therefore $H$ must be normal.
$endgroup$
– Jon
Dec 14 '10 at 13:46
$begingroup$
This doesn't fix the problem. See Tobais's answer. No matter how we look at the group operation, it has to be independent of which coset representatives we choose. The problem is easiest to see if you just consider the product $(xh)(yh)$ like I do above, but expand Tobais's $(xy)H=(x'y')H$ and you'll still get a term like $y^{-1}hyh$ which needs to be in $H$. Therefore $H$ must be normal.
$endgroup$
– Jon
Dec 14 '10 at 13:46
$begingroup$
Unfortunately, if we just think of cosets as of elements of $G/H$ your answer doesn't get the point :P
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 14:56
$begingroup$
Unfortunately, if we just think of cosets as of elements of $G/H$ your answer doesn't get the point :P
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 14:56
2
2
$begingroup$
It seems like some of the confusion is coming from whether or not we can put a different group structure on the set of cosets $G/H$. Perhaps we can, but we certainly wouldn't call it the quotient group of $G$ by $H$ because it has nothing to do with $G$ or $H$ as groups.
$endgroup$
– Sean Tilson
Dec 14 '10 at 16:26
$begingroup$
It seems like some of the confusion is coming from whether or not we can put a different group structure on the set of cosets $G/H$. Perhaps we can, but we certainly wouldn't call it the quotient group of $G$ by $H$ because it has nothing to do with $G$ or $H$ as groups.
$endgroup$
– Sean Tilson
Dec 14 '10 at 16:26
3
3
$begingroup$
@Sean Tilson: It is equivalent to the Axiom of Choice that every nonempty set can be given a group structure. Certainly, the set of cosets is a set, so we can give it a group structure (assuming AC), but which will likely have nothing to do with the operation in $G$.
$endgroup$
– Arturo Magidin
Dec 14 '10 at 18:05
$begingroup$
@Sean Tilson: It is equivalent to the Axiom of Choice that every nonempty set can be given a group structure. Certainly, the set of cosets is a set, so we can give it a group structure (assuming AC), but which will likely have nothing to do with the operation in $G$.
$endgroup$
– Arturo Magidin
Dec 14 '10 at 18:05
|
show 3 more comments
$begingroup$
To elaborate on a comment made by another user in the above, if the operation $(xH)ast(yH):=(xy)H$ is well-defined, then $(G/H,ast)$ is a group. Hence $f:Gto G/H$ defined by $f(g)=gH$ is a homomorphism and $H=ker f$. However, the kernel of a group homomorphism is always normal. Therefore $H$ has to be normal.
(As shown by Arturo Magidin's answer, actually $(xH)ast(yH):=(xy)H$ is well-defined if and only if $H$ is normal.)
$endgroup$
add a comment |
$begingroup$
To elaborate on a comment made by another user in the above, if the operation $(xH)ast(yH):=(xy)H$ is well-defined, then $(G/H,ast)$ is a group. Hence $f:Gto G/H$ defined by $f(g)=gH$ is a homomorphism and $H=ker f$. However, the kernel of a group homomorphism is always normal. Therefore $H$ has to be normal.
(As shown by Arturo Magidin's answer, actually $(xH)ast(yH):=(xy)H$ is well-defined if and only if $H$ is normal.)
$endgroup$
add a comment |
$begingroup$
To elaborate on a comment made by another user in the above, if the operation $(xH)ast(yH):=(xy)H$ is well-defined, then $(G/H,ast)$ is a group. Hence $f:Gto G/H$ defined by $f(g)=gH$ is a homomorphism and $H=ker f$. However, the kernel of a group homomorphism is always normal. Therefore $H$ has to be normal.
(As shown by Arturo Magidin's answer, actually $(xH)ast(yH):=(xy)H$ is well-defined if and only if $H$ is normal.)
$endgroup$
To elaborate on a comment made by another user in the above, if the operation $(xH)ast(yH):=(xy)H$ is well-defined, then $(G/H,ast)$ is a group. Hence $f:Gto G/H$ defined by $f(g)=gH$ is a homomorphism and $H=ker f$. However, the kernel of a group homomorphism is always normal. Therefore $H$ has to be normal.
(As shown by Arturo Magidin's answer, actually $(xH)ast(yH):=(xy)H$ is well-defined if and only if $H$ is normal.)
answered May 13 '18 at 20:45
community wiki
user1551
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f14282%2fwhy-do-we-define-quotient-groups-for-normal-subgroups-only%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
7
$begingroup$
That operation on cosets is well-defined if and only if H is a normal subgroup. If H is just a subgroup, what you call "left quotient group" has the more standard name "set with a left group action". More precisely, the coset spaces G/H describe essentially all the examples of sets with transitive left G-actions. It is part of the general theory of groups acting on sets.
$endgroup$
– KCd
Dec 14 '10 at 12:20
$begingroup$
What do you mean by well-defined? It is a group, which is trivial to show.
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 12:22
6
$begingroup$
To define the group operation, you have to fix coset representatives. You need to check that the coset you get as a result of the group operation is independent of the coset representatives you chose. But that is only true if the subgroup is normal. So before you "trivially show" that your operation gives a group, you should check that you have a well-defined operation on cosets in the first place.
$endgroup$
– Alex B.
Dec 14 '10 at 12:30
$begingroup$
Do you mean that if $xH = zH$ then it is necessary for $H$ to be a normal subgroup in order for the equality $(xy)H = (zy)H$ to hold for all $y in G$?
$endgroup$
– Alexei Averchenko
Dec 14 '10 at 13:02
2
$begingroup$
Yes (as is easily checked).
$endgroup$
– Matt E
Dec 14 '10 at 14:09