• Support PF! Buy your school textbooks, materials and every day products Here!

Proof about cardinality of subgroups

  • Thread starter bonfire09
  • Start date
  • #1
248
0

Homework Statement


Let [itex] G [/itex] be a finite group where [itex] H [/itex] and [itex] K [/itex] are subgroups of [itex] G [/itex]. Prove that [itex] |HK|=\frac{|H||K|}{|H \cap K|} [/itex].

Homework Equations


set [itex] HK=\{x\in G| x=st, s\in H and t\in K\}[/itex]


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 [itex]|H \cap K|[/itex] is a subgroup. So case 1: [itex]|H \cap K|=1[/itex] 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 [itex] HK [/itex]. Thus [itex] |HK|=\frac{|H||K|}{|H \cap K|} [/itex]. For case 2 Im lost here where [itex]|H \cap K|>1[/itex]. 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 [itex] r=|H \cap K| [/itex]. Then I know that [itex] r[/itex] repeats r times in [itex] HK [/itex] since those are the only elements in common between H and K. Plus [itex] H [/itex]and[itex] K [/itex]are nonempty since their subgroups. So that means that there are r of these elements in [itex] H[/itex] and [itex] K[/itex]. Thus [itex] r| |H||K|[/itex]. These are my ideas but I don't know how to put them together. Thanks.
 
Last edited:

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
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
248
0
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:
  • #4
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
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
248
0
Well I know that [itex] h_1k_1=hk[/itex]. Oh [itex] h_1[/itex] and [itex] k_1[/itex] are both elements of [itex] H\cap K[/itex]. And earlier when you said under what circumstances is [itex] f(h_1,k_1)=f(h_2,k_2)[/itex]? That only happens when [itex] h_1k_1=hk[/itex] and [itex] h_2k_2=hk[/itex]. 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:
  • #6
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
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
248
0
Should I just hold off on this problem till I get to homomorphisms?
 
  • #8
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
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
248
0
oh ok thanks for the hint. I will try to figure it out from here and ill post what i get so far.
 
  • #10
248
0
Here is what I got so far. I tried thinking of all the possible cases. So I let [itex] x\in H\cap K[/itex]. Let [itex]h_1,h_2\in H[/itex] and [itex] k_1,k_2\in K[/itex]. Then by closure [itex] \forall x\in H\cap K, x=h_1h_2=k_1k_2[/itex] for some [itex]h_1,h_2\in H[/itex] and [itex] k_1,k_2\in K[/itex]. Thus we know that [itex] x [/itex] appears atleast [itex] |H\cap K|[/itex] many times. Now we look at other ways that x can be expressed and we check those. Since [itex]h_1h_2=k_1k_2[/itex] we also have inverses to deal with too. [itex] h_1=xh_2^{-1} [/itex]. Thus [itex] h_1 [/itex] appears a total of [itex] |H\cap K|[/itex] times. Similarly [itex] h_2=h_1^{-1}x [/itex] we get the same thing. And since
[itex] x=k_1k_2 [/itex] we also see [itex] xk_2^{-1}=k_2 [/itex] or [itex] xk_2^{-1}=k_1 [/itex]. Thus we see those elements appear a total of [itex] |H\cap K| [/itex] times. Lastly since [itex] h_1h_2=k_1k_2 \implies h_2 k_2^{-1}=h_1^{-1}k_1=h_1^{-1}xk_2^{-1} [/itex]. Thus [itex] h_1^{-1} xk_2^{-1} [/itex] appears [itex] |H\cap K|[/itex] times too. Thus we see that any element from [itex] H [/itex] or [itex] K [/itex] using all elements from [itex] H\cap K [/itex] can be combined [itex] |H\cap K|[/itex] distinct times. I think i get the idea. I think I showed more combinations then I had to I think.
 
Last edited:
  • #11
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
Here is what I got so far. I tried thinking of all the possible cases. So I let [itex] x\in H\cap K[/itex]. Let [itex]h_1,h_2\in H[/itex] and [itex] k_1,k_2\in K[/itex]. Then by closure [itex] \forall x\in H\cap K, x=h_1h_2=k_1k_2[/itex] for some [itex]h_1,h_2\in H[/itex] and [itex] k_1,k_2\in K[/itex].
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:
Thus we know that [itex] x [/itex] appears atleast [itex] |H\cap K|[/itex] many times.
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
248
0
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
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
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
248
0
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##.
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
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
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?
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
248
0
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:

Related Threads on Proof about cardinality of subgroups

Replies
1
Views
962
Replies
2
Views
1K
Replies
3
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
11
Views
6K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
17
Views
2K
  • Last Post
Replies
2
Views
3K
Top