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

In summary, the conversation discusses the proof for the fact that the cardinality of the product of two subgroups H and K is equal to the product of their individual cardinalities divided by the cardinality of their intersection. The initial proof for the case where the intersection is trivial is deemed incomplete, leading to a discussion on the definition of fibers and how they can be used to show the size of a set. The conversation then progresses to discussing the size of the kernel of a function and how it relates to the size of the image. Ultimately, the conversation ends with a clearer understanding of how to prove the given fact.
  • #1
radou
Homework Helper
3,149
8
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 [tex]|HK|=\frac{|H|\cdot |K|}{|H\cap K|}[/tex], whether or not HK is a subgroup of G.

Now, if [tex]H\cap K = \left\{1\right\}[/tex], where 1 is the identity element, then [tex]|H\cap K| = {1}[/tex], and, since [tex]HK=\left\{hk : h \in H \wedge k \in K\right\}[/tex], then [tex]|HK|=|H|\cdot|K|[/tex], and the fact is obvious. Assume [tex]H\cap K \neq \left\{1\right\}[/tex]. That's the place where I need a push. Thanks in advance.
 
Physics news on Phys.org
  • #2
Why is the case [itex]H \cap K=1[/itex] obvious? Try proving it, it shouldn't be too different from the general case.
 
  • #3
StatusX said:
Why is the case [itex]H \cap K=1[/itex] 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.
 
  • #4
radou said:
Now, if [tex]H\cap K = \left\{1\right\}[/tex], where 1 is the identity element, then [tex]|H\cap K| = {1}[/tex], and, since [tex]HK=\left\{hk : h \in H \wedge k \in K\right\}[/tex], then [tex]|HK|=|H|\cdot|K|[/tex].

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.
 
Last edited:
  • #5
StatusX said:
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.
 
  • #6
Ok, but how do you know hk is not the same as h'k', so that you're counting the same element twice?
 
  • #7
StatusX said:
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.
 
  • #8
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.
 
  • #9
mathwonk said:
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.
 
  • #10
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}.
 
  • #11
Hurkyl said:
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. :uhh:
 
  • #12
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?
 
  • #13
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.
 
  • #14
StatusX said:
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 [tex]2|H \cap K|-1[/tex]. Even if this is correct, I still don't see how this would give me the size of HK.
 
  • #15
Say I have a 4:1 map, and the image has 3 elements. How many elements does the domain have?
 
  • #16
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.
 
  • #17
StatusX said:
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.

StatusX said:
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 [tex]|H \cap K|[/tex] different ways. It's obvious that this proves the fact, but I can't get there.
 
  • #18
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?
 
  • #19
mathwonk said:
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 [tex]K \cap H[/tex]. (?)
 
Last edited:
  • #20
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.
 
  • #21
StatusX said:
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.
 
  • #22
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 [itex]H \cap K[/itex] in K being the same.

In particular, [itex](H \cap K) x = (H \cap K) y[/itex] <=> xy-1 is in [itex]H \cap K[/itex]. 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 [itex]H \cap K[/itex] in K, i.e. |K|/|[itex]H \cap K[/itex]|.

Can you finish it off now?
 
  • #23
morphism said:
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 [itex]H \cap K[/itex] in K being the same.

In particular, [itex](H \cap K) x = (H \cap K) y[/itex] <=> xy-1 is in [itex]H \cap K[/itex]. 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 [itex]H \cap K[/itex] in K, i.e. |K|/|[itex]H \cap K[/itex]|.

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| / [itex]|H \cap K|[/itex]. Thanks a lot!
 

1. What is "Proof of |HK| = (|H|*|K|)/|H∩K| for subgroups H and K in G"?

Proof of |HK| = (|H|*|K|)/|H∩K| is a mathematical formula that describes the relationship between the size of a subgroup formed by the combination of two smaller subgroups in a group G, and the sizes of the individual subgroups and their intersection.

2. Why is this formula important in mathematics?

This formula is important because it helps us understand the structure and behavior of groups in mathematics. It allows us to make predictions about the size of subgroups and their intersections, which can then be applied to various mathematical problems and proofs.

3. How is this formula derived?

This formula is derived using basic principles of group theory, specifically the Lagrange's Theorem, which states that the order (size) of a subgroup must divide the order of the group. By applying this theorem to the intersection of two subgroups, we can derive the formula for the size of the combined subgroup.

4. Can this formula be applied to any type of group?

Yes, this formula can be applied to any type of group, as long as the group satisfies the requirements for subgroups and their intersections. It is a fundamental concept in group theory and can be used in a wide range of mathematical problems and proofs.

5. What are some real-world applications of this formula?

This formula has many real-world applications, particularly in computer science and physics. It is used in cryptography to analyze the security of encryption algorithms, and in particle physics to understand the symmetries and interactions of subatomic particles. It is also used in economics to model the behavior of markets and in social networks to study the relationships between individuals.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
652
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
730
Replies
8
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
19
Views
3K
  • Linear and Abstract Algebra
Replies
19
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
885
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
Back
Top