6
$\begingroup$

I've found this problem in a book and devised my own proof. (took me like 5 hours and it seems trivial - just build a bijection). I am not sure that I haven't made any errors though. Perhaps some other proof would be simpler.

Statement:

$G$ is a group and $H,K,HK \subseteq G$

Prove that $|HK|=\frac{|H||K|}{|H \cap K|}$

Proof:

The statement above is equivalent to: $\frac{|HK|}{|K|}=\frac{|H|}{|H \cap K|}$

So now we look at the cosets of $K$ in $HK$ - ie. the elements of $HK/K$. They are exactly $\frac{|HK|}{|K|}$ because of Lagrange's theorem.
Then we look at the cosets of $H \cap K$ in $H$ - ie. the elements of $H/H \cap K$. They are exactly $\frac{|H|}{|H \cap K|}$ because of Lagrange's theorem.

So if we could find a bijection from $HK/K$ to $H/H \cap K$, we are done.

So let's look at the elements of $HK/K$, they are cosets of the form: $h_1k_1K$, but $k_1K=K$, so we get $h_1K$.

Then lets look at the elements of $H/H \cap K$, they are cosets of the form: $h_1H \cap K$.

So let's define $f: HK/K \to H/H \cap K$, $f(hK)=hH \cap K$.

To see that it's a function we need to show that it's well defined.

Let $h_1K=h_2K$, ie. $h_2^{-1}h_1 \in K$ which also implies $h_2^{-1}h_1 \in H \cap K$

Then we need to show that $f(h_1K)=f(h_2K)$.

So $f(h_1K)=h_1H \cap K$ and $f(h_2K)=h_2H \cap K$

To prove that $h_1H \cap K = h_2H \cap K$ we need $h_2^{-1}h_1 \in H \cap K$.

But we've already shown that.

Hence f is well defined.

Now we need to show that it's injective.

Suppose $f(h_1K)=f(h_2K)$, but $h1K \neq h2K$.

Ie. $h_1H \cap K = h_2H \cap K$ but $h_1K \neq h_2K$.

$h_1K \neq h_2K$ implies $h_2^{-1}h_1 \notin K$ which implies $h_2^{-1}h_1 \notin H \cap K$.

Hence $h_1H \cap K \neq h_2H \cap K$.

So we know f is injective.

Now to check for surjectivity:

Since $H/H \cap K$ has elements of the form $h_1H \cap K$, for each of them we have, $f(h_1K)=h_1H \cap K$.

QED

$\endgroup$
7
  • 1
    $\begingroup$ Use $h_2$ for $h_2$. $\endgroup$
    – Shaun
    Sep 23, 2020 at 0:15
  • 2
    $\begingroup$ You can't quite use Lagrange's theorem on $HK/K$, because $HK$ isn't necessarily a group. (You can repeat the argument in the proof of Lagrange's theorem and check that it still works here - essentially, showing that $HK$ is a union of $|HK|/|K|$ cosets of $K$ in $G$ - but that's an extra step.) $\endgroup$ Sep 23, 2020 at 0:23
  • $\begingroup$ I wrote in the title that $HK$ is a subgroup of $G$. Yes, I know that generally $HK$ is not a subgroup of $G$. So you're saying this statement is true, even if $HK$ is not a subgroup of $G$? $\endgroup$ Sep 23, 2020 at 0:26
  • 1
    $\begingroup$ The statement is still true if $HK$ is not a subgroup. If $H$ or $K$ is infinite, then $HK$ is also infinite (because it contains both $H$ and $K$), and then you have $\infty = \infty$, so there's nothing to prove; if $H$ and $K$ are both finite, then $HK$ is also finite. $\endgroup$ Sep 23, 2020 at 0:33
  • 1
    $\begingroup$ JCAA's proof works whether or not it's a subgroup (so does yours, except for the Lagrange's theorem statement). $\endgroup$ Sep 23, 2020 at 1:32

4 Answers 4

4
$\begingroup$

The best and standard way to prove it is to consider the map from $H\times K$ to $HK$ which sends $(h,k)$ to $hk$ and look at the equivalence classes of pairs mapped to the same element of $HK$. That is for every $(h,k)$ count pairs $(h',k')$ such that $hk=h'k'$.

Edit To make it complete, $hk=h'k'$ is equivalent to $h^{-1}h'=k'k^{-1}$. The LHS is in $H$, the RHS is in $K$, so both are in $K\cap H$. So the number of pairs $(h',k')$ such that $hk=h'k'$ is the same as the number of elements in $h(H\cap K)$ which is $|H\cap K|$.

$\endgroup$
11
  • $\begingroup$ I don't know why, but this proof seems more complex to me. Ie. the proof I wrote seems trivial to me, like I could follow it and understand it without thinking. But maybe that's just cause I wrote it and everyone understands his proofs easily. $\endgroup$ Sep 23, 2020 at 0:08
  • 1
    $\begingroup$ That is not "my" proof. It is in every abstract algebra book. But yes, usually proofs made by yourself seem easier. For me it is the easiest probably because I came up with it many years ago. $\endgroup$
    – markvs
    Sep 23, 2020 at 0:15
  • $\begingroup$ I see. Then what about my proof? Is it a standard proof too? Or perhaps not, because it's too long or I made some mistake? Also are there other interesting proofs? $\endgroup$ Sep 23, 2020 at 0:21
  • $\begingroup$ Your proof does not seem to be correct because some phrases are hard to understand. Say, "we look at the cosets of $K$ as a subgroup of $HK$". Second, the statement you are proving is not general enough: the set $HK$ does not need to be assumed a subgroup. So this proof cannot be "standard". But other than that it is or is very close to a correct proof. $\endgroup$
    – markvs
    Sep 23, 2020 at 0:42
  • 1
    $\begingroup$ $HK$ is already partitioned into cosets $hK$ each of which has $|K|$ elements. You need to show that the number of cosets is $|H|/|(H\cap K)|$. I think it can be done as in your proof. But it is longer than "my" proof. $\endgroup$
    – markvs
    Sep 23, 2020 at 1:01
1
$\begingroup$

There is a quite easy way to prove this problem. If you understand chinese, there is a classic proof on Yang Zixu's 'Abstract Algebra'. Here is the proof:

Since $H\cap K\le H$, let $|H|/|H\cap K|=m$ and $H = h_1(H\cap K)\cup h_2(H\cap K)\cup \cdots \cup h_m(H\cap K),$ here $h_i\in H, h_i^{-1} h_j \notin K,i\neq j.$ Clearly, $HK=h_1K\cup h_2K\cup\cdots\cup h_m K,$ while $h_iK\cap h_jK = \varnothing,i\neq j,$ thus $|HK|=m|K|,$ which means $|HK|=|H||K|/|H\cap K|.$ QED

It is an application of coset decomposition theory. There is no need of considering the bijection or maps etc.

$\endgroup$
5
  • $\begingroup$ Why $HK= h_1K\cup...$ etc.? $\endgroup$
    – user810157
    Sep 23, 2020 at 5:39
  • 1
    $\begingroup$ Since $H$ is some union of $h_i (H\cap K)$,$HK$ is the sets of all $h_i \in H$ left times $k_j\in K$, thus it is the union of $h_i K$ $\endgroup$ Sep 23, 2020 at 5:54
  • $\begingroup$ This proof only satisfies the case that $H,K$ are finite groups. $\endgroup$ Sep 23, 2020 at 6:09
  • $\begingroup$ So you "mimic Lagrange's" even in the case $HK$ not a subgroup of $G$, nice. +1 $\endgroup$
    – user810157
    Sep 23, 2020 at 8:16
  • $\begingroup$ Interesting. Also it seems I have to mimic Lagrange too in my proof, if HK is not a subgroup of G as another poster has noted in his comments. $\endgroup$ Sep 23, 2020 at 20:48
1
$\begingroup$

The equivalence relation $(h,k)\sim (h',k')\stackrel{(def.)}{\iff} hk=h'k'$ induces a partition of $H\times K$ into equivalence classes each of cardinality $|H\cap K|$, and the quotient set $(H\times K)/\sim$ has cardinality $|HK|$. Therefore, if $H$ and $K$ are finite (in particular if they are subgroups of a finite group), we get: $|H\times K|=|H||K|=|H\cap K| |HK|$, whence the formula in the OP. Hereafter the details.

(The formula holds irrespective of $HK$ being a subgroup.)


Let's define in $H\times K$ the equivalence relation: $(h,k)\sim (h',k')\stackrel{(def.)}{\iff} hk=h'k'$. The equivalence class of $(h,k)$ is given by:

$$[(h,k)]_\sim=\{(h',k')\in H\times K\mid h'k'=hk\} \tag 1$$

Now define the following map from any equivalence class:

\begin{alignat*}{1} f_{(h,k)}:[(h,k)]_\sim &\longrightarrow& H\cap K \\ (h',k')&\longmapsto& f_{(h,k)}((h',k')):=k'k^{-1} \\ \tag 2 \end{alignat*}

Note that $k'k^{-1}\in K$ by closure of $K$, and $k'k^{-1}\in H$ because $k'k^{-1}=h'^{-1}h$ (being $(h',k')\in [(h,k)]_\sim$) and by closure of $H$. Therefore, indeed $k'k^{-1}\in H\cap K$.

Lemma 1. $f_{(h,k)}$ is bijective.

Proof.

\begin{alignat}{2} f_{(h,k)}((h',k'))=f_{(h,k)}((h'',k'')) &\space\space\space\Longrightarrow &&k'k^{-1}=k''k^{-1} \\ &\space\space\space\Longrightarrow &&k'=k'' \\ &\stackrel{h'k'=h''k''}{\Longrightarrow} &&h'=h'' \\ &\space\space\space\Longrightarrow &&(h',k')=(h'',k'') \\ \end{alignat}

and the map is injective. Then, for every $a\in H\cap K$, we get $ak\in K$ and $a=f_{(h,k)}((h',ak))$, and the map is surjective. $\space\space\Box$

Now define the following map from the quotient set:

\begin{alignat}{1} f:(H\times K)/\sim &\longrightarrow& HK \\ [(h,k)]_\sim &\longmapsto& f([(h,k)]_\sim):=hk \\ \tag 3 \end{alignat}

Lemma 2. $f$ is well-defined and bijective.

Proof.

  • Good definition: $(h',k')\in [(h,k)]_\sim \Rightarrow f([(h',k')]_\sim)=h'k'=hk=f([(h,k)]_\sim)$;
  • Injectivity: $f([(h',k')]_\sim)=f([(h,k)]_\sim) \Rightarrow h'k'=hk \Rightarrow (h',k')\in [(h,k)]_\sim \Rightarrow [(h',k')]_\sim=[(h,k)]_\sim$;
  • Surjectivity: for every $ab\in HK$ , we get $ab=f([(a,b)]_\sim)$. $\space\space\Box$

Finally, the formula holds irrespective of $HK$ being a subgroup, which was never used in the proof.

$\endgroup$
-1
$\begingroup$

In the case that$H\triangleleft G$, this follows immediately from the second isomorphism theorem.

But, actually your result is well known, and called the product formula. Neither $H$ nor $K$ is required to be normal. See "Product of group subsets - Wikipedia" https://en.m.wikipedia.org/wiki/Product_of_group_subsets

$\endgroup$
6
  • $\begingroup$ Isn't it needed for H to be normal? Hm, I know that $HK=KH$ is equiv to $HK$ being a group. Btw a comment above said that $HK$ doesn't have to be a group for this statement to be true. $\endgroup$ Sep 23, 2020 at 0:33
  • $\begingroup$ But do we need $HK$ to be a group for the statement to be true? A comment above is saying that we don't. $\endgroup$ Sep 23, 2020 at 0:39
  • $\begingroup$ That I would have to think about. $\endgroup$
    – user403337
    Sep 23, 2020 at 0:40
  • $\begingroup$ Neither $H$ nor $K$ needs to be normal for $HK$ to be a subgroup. For example in a solvable group products of Sylow subgroups can be a subgroup (a Hall subgroup) even if the Sylow subgroups are not normal. This can be seen in $S_4$. It has a Sylow 2-subgroup $H$ of order $8$ (three of them, none of them normal) and $4$ subgroups $K$ of order $3$ (none of them normal), but $HK$ contains $8\cdot 3=24$ elements so $HK$ is a subgroup, in fact equal to $S_4$. $\endgroup$
    – markvs
    Sep 23, 2020 at 1:18
  • $\begingroup$ @JCAA you're correct. So this is more general than the Second Isomorphism Theorem, meaning you need other things to happen for it to be not just a bijection but a morphism. $\endgroup$ Sep 23, 2020 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.