Lagrange's Theorem: Understanding Cosets of H in G

  • Thread starter Thread starter fk378
  • Start date Start date
  • Tags Tags
    Theorem
fk378
Messages
366
Reaction score
0
In Lagrange's Theorem, it states that the order of G is the number of cosets of H in G multiplied by the order of H.


What I don't understand is what if H is just a subgroup among other elements in G? Let's say there is some k in G then kH consists of all the left cosets of H. But there is also m in G that do not go into any cosets. Then how can the order of G only include the left cosets?
 
Physics news on Phys.org
fk378 said:
In Lagrange's Theorem, it states that the order of G is the number of cosets of H in G multiplied by the order of H.


What I don't understand is what if H is just a subgroup among other elements in G? Let's say there is some k in G then kH consists of all the left cosets of H.
Have you misunderstood what a left coset is? If k is a member of G then kH is one left coset of G, not "all the left cosets of H". kH is defined as the set {kh} where h runs through all member of H. kH cannot have more member than H since we get, at most, one member of kH for each H. In order that there be less, we would have to have kh= kh' for h and h' distinct members of H. But that can't be true: multiplying both sides of kh= kh' by the inverse of k (and every member of a group has an inverse) gives h= h' contradicting the hypothesis that they were distinct. That is: kH is a single subset of G having the same number of members as H.

But there is also m in G that do not go into any cosets.[/quote]
No, there isn't. Since H is a subgroup, it includes the indentity, e, so mH includes me= m. Every member, m, of G is in at least one left coset, mH itself.

Now, suppose m were in some other coset, say kH for some k in G, k not equal to m. Then we must have m= kn for some n in H. Then k= mh-1 so that any member of kH, ka, say, is equal to (mh-1)a= m(h-1a) and since h-1 and a are both members of H, so is h-1a. Every member of kH is of the form mb for b some member of H and so is also a member of mH. Of course, the opposite way is true for exactly the same reasons: if kH and mH have a single member in common, they have all members in common: they are exactly the same.

Then how can the order of G only include the left cosets?
Your assumptions are incorrect. There is NO k in G such that "kH consists of all the left cosets of H", kH is always a single left coset, never all of them (unless G itself contains only a single member). There is no "m in G that do not go into any cosets", every member of G is in exactly one coset. Suppose H has N left cosets. Then every member of G is in exactly one of the cosets all of which have |H| members: |G|= N|H| which leads immediately to Lagrange's theorem that the order of any subset of G must evenly divide the order of G.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top