Proof of |HK| = (|H|*|K|)/|H∩K| for subgroups H and K in G

[radou]

Well, I'm stuck on the proof (somehow trivial one, I feel) of this fact:

Let H and K be subgroups of G. Show that |HK|=\frac{|H|\cdot |K|}{|H\cap K|}, whether or not HK is a subgroup of G.

Now, if H\cap K = \left\{1\right\}, where 1 is the identity element, then |H\cap K| = {1}, and, since HK=\left\{hk : h \in H \wedge k \in K\right\}, then |HK|=|H|\cdot|K|, and the fact is obvious. Assume H\cap K \neq \left\{1\right\}. That's the place where I need a push. Thanks in advance.

 

[StatusX]

Why is the case H \cap K=1 obvious? Try proving it, it shouldn't be too different from the general case.

 

[radou]

Why is the case H \cap K=1 obvious? Try proving it, it shouldn't be too different from the general case.

I thought I showed why it is obvious. If not, then I did something terribly wrong, but I don't see what.

 

[StatusX]

Now, if H\cap K = \left\{1\right\}, where 1 is the identity element, then |H\cap K| = {1}, and, since HK=\left\{hk : h \in H \wedge k \in K\right\}, then |HK|=|H|\cdot|K|.

You haven't proven this statement. Please write it out. Maybe you have it right, and it is obvious to you. But then the rest of the problem should be easy, so I think you're thinking about this the wrong way.

 

[radou]

You haven't proven this statement. Please write it out. Maybe you have it right, and it is obvious to you. But then the rest of the problem should be easy, so I think you're thinking about this the wrong way.

I'm 'constructing' the set HK by taking, let's say, an element of H fixed, and letting all the elements from K 'operate themselves' with that fixed element from H. If that element form H is h = 1, then we see that K is a subset of HK. Further on, HK must contain H, too, since every element from H is operated on by the identity. Following this reasoning, I was led to the (false?) conclusion that the cardinal number of HK is |H||K|.

Now, if we assume that the intersection of H and K is non trivial, let's say there are p elements in it, then the upper procedure, for every ai , i = 1 .. p, (from the intersection) generates |K| elements from K (since, when we take h = ai, and 'go through' the whole set K, we'll generate the set K, since K is a finite group). This happens p times, so the cardinal number of HK reduces to |H||K| - p|K|, which is probably false.

I'm obviously missing something huge here, and I need some help. And I hope I didn't write something extremely stupid.

 

[StatusX]

Ok, but how do you know hk is not the same as h'k', so that you're counting the same element twice?

 

[radou]

Ok, but how do you know hk is not the same as h'k', so that you're counting the same element twice?

Good question, amof, I don't. I'll give it a thought and post later.

 

[mathwonk]

well there is an obvious map frpmHxK to HK, namerly multiply. so all you have to do is shw]ow all the fibers of this map are in 1-1 correspondence with HmeetK.

 

[radou]

well there is an obvious map frpmHxK to HK, namerly multiply. so all you have to do is shw]ow all the fibers of this map are in 1-1 correspondence with HmeetK.

I'm ashamed to say that I don't understand what you meant.

 

[Hurkyl]

When you have a function f:A -> B between objects, for any b in B, the fiber of f at b is the set of all elements of A that map to b. That is, it's the inverse image of {b}.

 

[radou]

When you have a function f:A -> B between objects, for any b in B, the fiber of f at b is the set of all elements of A that map to b. That is, it's the inverse image of {b}.

I know the definition, I'm just not sure what mathwonk wanted to point out. I should show that there is a 1-1 correspondence between the fibers of the multiplication map (f : H x K --> HK) and the elements of HK?

So, for every element from HK we have at least one ordered pair (h, k) for which f(h, k) = hk. Further on, confusion arises.

 

[StatusX]

The point is, the natural map from HxK to HK is surjective, but not injective in general. If you can compute the size of its kernel, do you see how this would give you the size of HK?

 

[mathwonk]

to show a sert has size xy, you p[artition it into x subsets each of size y. the easiest waY TO DO this is tO define a function from the set to a set of size x, such that every point in the target hAS EXACTLY y preimaGES.

WE CALL THE SET OF PREIMAges of a point, the "fiber" over thart point.

 

[radou]

The point is, the natural map from HxK to HK is surjective, but not injective in general. If you can compute the size of its kernel, do you see how this would give you the size of HK?

Hm, if the intersection of H and K is {1}, then Ker(f) = {(1, 1)}, but if the intersection contains elements other than 1, then for every element a from the intersection (a, a^-1) and (a^-1, a) belong to the kernel too, since the intersection of H and K is a subgroup, too. So the size of the kernel is 2|H \cap K|-1. Even if this is correct, I still don't see how this would give me the size of HK.

 

[matt grime]

Say I have a 4:1 map, and the image has 3 elements. How many elements does the domain have?

 

[StatusX]

Note if a is in the intersection, so is a^-1, so you don't have to count (a, a^-1) and (a^-1, a) separately. Now look at what mathwonk said. If you have an onto function f from A to B, and for each b in B, there are n elements in A mapping to b, then the size of A is n times the size of B. So, now that you know the size of the kernel of f, how does this relate to the n in the last sentence.

 

[radou]

Note if a is in the intersection, so is a^-1, so you don't have to count (a, a^-1) and (a^-1, a) separately.

I don't understand, aren't they ordered pairs..? At least when talking about the kernel of the multiplication map f : H x K --> HK.

Now look at what mathwonk said. If you have an onto function f from A to B, and for each b in B, there are n elements in A mapping to b, then the size of A is n times the size of B. So, now that you know the size of the kernel of f, how does this relate to the n in the last sentence.

Frankly, I don't see the relation. Further on, why does every b in B have the same number of elements (n) in A mapped to it?

I'm definitely losing the track. The hint in the text says that there are |H||K| choices of an expression hk, and that one needs to show that every element in HK can be expressed as such a product in |H \cap K| different ways. It's obvious that this proves the fact, but I can't get there.

 

[mathwonk]

we have a map from HxK to HK by multip-lying. letsv take one pair (x,y) and multiply them getting xy. niow wehave to ask how many iother pairs (u,v) also have the same product, \

so set uv = xy and try to get some connection to HmeetK.

well let's see, u is in H and also x is in H, while v and y are in K, and both of thiose are clsoed under poroiducts. so multiply the equation xy=uv by something clever and try to get something in h on one side and soemthing in k on the other side. then what can you conclude?

 

[radou]

we have a map from HxK to HK by multip-lying. letsv take one pair (x,y) and multiply them getting xy. niow wehave to ask how many iother pairs (u,v) also have the same product, \

so set uv = xy and try to get some connection to HmeetK.

well let's see, u is in H and also x is in H, while v and y are in K, and both of thiose are clsoed under poroiducts. so multiply the equation xy=uv by something clever and try to get something in h on one side and soemthing in k on the other side. then what can you conclude?

Hm, if I multiply uv = xy with let's say u^-1 from the left, I have v = u^-1 xy, and I can multiply this from the right with y^-1 to obtain vy^-1 = u^-1 x, where vy^-1 is from K and u^-1 x is from H, so they are both from K \cap H. (?)

 

[StatusX]

It's a basic fact of group theory that every homomorphism is exactly k to 1, where k is the size of the kernel. It shouldn't be hard to prove.

 

[radou]

It's a basic fact of group theory that every homomorphism is exactly k to 1, where k is the size of the kernel. It shouldn't be hard to prove.

I only read about group homomorphisms, so I didn't even try to apply anything, since HK is not necassary a group (assuming that we're talking about the multiplication map mentioned above).

Anyway, will think about everything mentioned before and try to come up with something.

 

[morphism]

Here's a different way to look at things.

HK is the union of cosets Hk as k runs over K. When are two such cosets the same? We know that Hx = Hy <=> xy^-1 is in H. Now compare this condition to that of two cosets of H \cap K in K being the same.

In particular, (H \cap K) x = (H \cap K) y <=> xy^-1 is in H \cap K. Since we already know that xy^-1 is in K (because we're looking at cosets in K), this turns out to be the same condition that Hx = Hy. So the number of cosets Hk as k runs over K is the index of H \cap K in K, i.e. |K|/|H \cap K|.

Can you finish it off now?

 

[radou]

Here's a different way to look at things.

HK is the union of cosets Hk as k runs over K. When are two such cosets the same? We know that Hx = Hy <=> xy^-1 is in H. Now compare this condition to that of two cosets of H \cap K in K being the same.

In particular, (H \cap K) x = (H \cap K) y <=> xy^-1 is in H \cap K. Since we already know that xy^-1 is in K (because we're looking at cosets in K), this turns out to be the same condition that Hx = Hy. So the number of cosets Hk as k runs over K is the index of H \cap K in K, i.e. |K|/|H \cap K|.

Can you finish it off now?

That was enlightening. It's easy to finish it off - every coset has |H| elements, so, since HK is the union of cosets Hk, where k is from K, one obtains |HK|= |K||H| / |H \cap K|. Thanks a lot!