# Proof about cardinality of subgroups

1. Sep 29, 2013

### bonfire09

1. The problem statement, all variables and given/known data
Let $G$ be a finite group where $H$ and $K$ are subgroups of $G$. Prove that $|HK|=\frac{|H||K|}{|H \cap K|}$.

2. Relevant equations
set $HK=\{x\in G| x=st, s\in H and t\in K\}$

3. The attempt at a solution
I am a bit lost with this problem. What I did was break this proof into two cases. Since H and K are subgroups then $|H \cap K|$ is a subgroup. So case 1: $|H \cap K|=1$ Thus the only common element between H and K is the identity element call it e. It follows that e repeats only once in set $HK$. Thus $|HK|=\frac{|H||K|}{|H \cap K|}$. For case 2 Im lost here where $|H \cap K|>1$. I'm not sure if case 1 is correct it seems correct but for case 2 I need some help. I know case 2 is similar to case 1. So I was thinking let $r=|H \cap K|$. Then I know that $r$ repeats r times in $HK$ since those are the only elements in common between H and K. Plus $H$and$K$are nonempty since their subgroups. So that means that there are r of these elements in $H$ and $K$. Thus $r| |H||K|$. These are my ideas but I don't know how to put them together. Thanks.

Last edited: Sep 29, 2013
2. Sep 29, 2013

### jbunniii

You don't really need to handle two separate cases. Consider the map $f: H \times K \rightarrow HK$ defined by $f(h,k) = hk$. Under what circumstances does $f(h_1, k_1) = f(h_2, k_2)$?

3. Sep 29, 2013

### bonfire09

Oh I wanted to do the proof without using a mapping. Would it be possible to do it the way I was trying to do it? The book apparently puts this problem right after subgroups. I havent really learned isomorphisms, cosets, and homomorphisms yet since they are later sections. Not sure if that stuff applies to this it looks like cossets does but I haven't gotten there,

Last edited: Sep 29, 2013
4. Sep 29, 2013

### jbunniii

You don't have to formally construct a mapping, and you don't need any notions like homomorphisms or cosets. They wouldn't help here anyway since $HK$ is not generally a subgroup. (It is a subgroup if and only if $H$ or $K$ is a normal subgroup.)

Here is a hint. Suppose $h\in H$, $k \in K$, and $x \in H \cap K$. Consider defining $h_1 = hx$ and $k_1 = x^{-1}k$. What can you say about $h_1$, $k_1$, and $h_1 k_1$?

5. Sep 29, 2013

### bonfire09

Well I know that $h_1k_1=hk$. Oh $h_1$ and $k_1$ are both elements of $H\cap K$. And earlier when you said under what circumstances is $f(h_1,k_1)=f(h_2,k_2)$? That only happens when $h_1k_1=hk$ and $h_2k_2=hk$. I think. I never would really have thought of defining a function like this. I wonder how I would be able to see these things on my own.

Last edited: Sep 29, 2013
6. Sep 29, 2013

### jbunniii

Don't worry, it will become second nature to define functions like that after you have started working with homomorphisms. You will see two groups and your first question will be, what is the most natural mapping between these two? And usually that will be the right one to use.

7. Sep 29, 2013

### bonfire09

Should I just hold off on this problem till I get to homomorphisms?

8. Sep 29, 2013

### jbunniii

No, you don't need homomorphisms here. And you can do it without constructing a mapping. Take another look at my hint. We want to know how many different ways you can take an element from $H$ and multiply it by an element of $K$ to get $hk$. Certainly $hk$ is one such way. Let's see if there are others.

Suppose we have $hk = h_1 k_1$ with $h,h_1 \in H$ and $k,k_1 \in K$. Rearranging the equality, we get $h_1^{-1}h = k_1 k^{-1}$. Assuming this equality is true, let's give the common value a name: $x = h_1^{-1}h = k_1 k^{-1}$. What can you say about $x$?

We can also rearrange the equalities as follows: $h_1 = h x^{-1}$ and $k_1 = x k$.

If you interpret these facts the right way, you should be able to conclude that there are exactly $|H \cap K|$ distinct ways to choose $h_1 \in H$ and $k_1 \in K$ such that $h_1 k_1 = hk$.

9. Sep 29, 2013

### bonfire09

oh ok thanks for the hint. I will try to figure it out from here and ill post what i get so far.

10. Sep 29, 2013

### bonfire09

Here is what I got so far. I tried thinking of all the possible cases. So I let $x\in H\cap K$. Let $h_1,h_2\in H$ and $k_1,k_2\in K$. Then by closure $\forall x\in H\cap K, x=h_1h_2=k_1k_2$ for some $h_1,h_2\in H$ and $k_1,k_2\in K$. Thus we know that $x$ appears atleast $|H\cap K|$ many times. Now we look at other ways that x can be expressed and we check those. Since $h_1h_2=k_1k_2$ we also have inverses to deal with too. $h_1=xh_2^{-1}$. Thus $h_1$ appears a total of $|H\cap K|$ times. Similarly $h_2=h_1^{-1}x$ we get the same thing. And since
$x=k_1k_2$ we also see $xk_2^{-1}=k_2$ or $xk_2^{-1}=k_1$. Thus we see those elements appear a total of $|H\cap K|$ times. Lastly since $h_1h_2=k_1k_2 \implies h_2 k_2^{-1}=h_1^{-1}k_1=h_1^{-1}xk_2^{-1}$. Thus $h_1^{-1} xk_2^{-1}$ appears $|H\cap K|$ times too. Thus we see that any element from $H$ or $K$ using all elements from $H\cap K$ can be combined $|H\cap K|$ distinct times. I think i get the idea. I think I showed more combinations then I had to I think.

Last edited: Sep 29, 2013
11. Sep 29, 2013

### jbunniii

While it's true that you can express $x$ as a product of two elements in $H$ or two elements in $K$, I don't see how this helps you. In particular, I don't see how it implies the following:
Can you explain this in more detail?

Also, it's certainly not true that for FIXED $h_1,h_2\in H$ and $k_1,k_2 \in K$, every $x\in H\cap K$ can be written as $h_1 h_2$ or $k_1 k_2$. So something is not right with what you wrote above.

12. Sep 29, 2013

### bonfire09

Dang it. I give up ill try again tomorrow. I've been thinking about on and off today but I don't seem to see it yet.

13. Sep 29, 2013

### jbunniii

No worries, sometimes taking a break is the best way to make progress. Look at it with fresh eyes in the morning. I'll check in tomorrow to see how it's going.

14. Sep 30, 2013

### bonfire09

So I tried reading over what you said again I know that $hk$ means the product of two elements where $h\in H$ and $k\in K$. For your first question where you said suppose $hk=h_1k_1$ and we rearranged it and let $x=h^{-1} h_1=kk^{-1}$. Then that would mean $x \in H\cap K$. And if we rearrange one more time we see $h_1 = h x^{-1}$ and $k_1 = x k$ and since $H\cap K$ is a subgroup $x^{-1}\in H\cap K$. But from here im having trouble concluding that there are $|H\cap K|$ distinct ways?

15. Oct 1, 2013

### jbunniii

OK, we've established that if $hk = h_1 k_1$ then this is equivalent to $h_1^{-1} h = k_1 k^{-1}$, and we may call the common value $x$. Thus $x = h_1^{-1}h$ and $x = k_1 k^{-1}$.

From this, we can conclude several things. First, as you noted it means that $x \in H \cap K$. Second, we have $h_1 = hx^{-1}$. Third, we have $k_1 = xk$.

Conversely, if $x \in H \cap K$ and $h_1 = hx^{-1}$ and $k_1 = xk$, then $h_1 k_1 = hx^{-1}xk = hk$.

This shows that $h_1 k_1 = hk$ if and only if $h_1$ and $k_1$ are related to $h$ and $k$ by equations of the form $h_1 = hx^{-1}$ and $k_1 = xk$, where $x \in H \cap K$. Since there are $|H \cap K|$ elements of $H \cap K$, that means there are at most $|H \cap K|$ distinct choices for $h_1, k_1$. It remains to show that there are exactly $|H \cap K|$ choices. To do this, you need to show that if $x$ and $y$ are distinct values from $H \cap K$, they result in distinct values for $h_1$ and $k_1$.

16. Oct 1, 2013

### bonfire09

I think I understand where I over complicated the proof was the beginning assumption. That is assume that $hk=h_1k_1$. I figured we did that because we have elements that are in $H \cap K$ are also in $H$ and $K$. Thus in the numerator we get another we get an extra replication and that's why we set $hk=h_1k_1$ because we get twice as many replications. And I think I can take it from thanks for you help.

Last edited: Oct 1, 2013