# Lagrange's theorem

Dear, I don't understand left coset and Lagrange's theorem... I'm working on some project so please write me anything what could help me understand it better... milica from montenegro

-
What is your background? Are you studying some introductory course on group theory? –  Pandora Jan 8 '11 at 14:19
yes yes :):):):):):):):):) –  Milica Jan 8 '11 at 16:42
I wrote some course notes on cosets once, which are posted at math.uconn.edu/~kconrad/blurbs/grouptheory/coset.pdf. Maybe that will have something useful in it. –  KCd Jan 9 '11 at 7:03

Suppose $G$ is a group, and $H$ is any subgroup of $G$. I would like to try to define something similar to "congruence modulo $n$" for integers, but for this arbitrary group $G$ and subgroup $H$.

In the integers, we say that $a\equiv b\pmod{m}$ if and only if $a-b$ is an element of the subgroup $m\mathbb{Z}$. So we are going to try something similar for $H$ and $G$, taking into account that $G$ need not be abelian.

I'm not going to assume the group is finite until I say so explicitly.

Definition. Let $G$ be a group and let $H$ be a subgroup. If $x,y\in G$, we say that $x$ and $y$ are congruent on the right modulo $H$ if and only if $xy^{-1}\in H$. We write this $x\equiv_H y$.

Proposition. $\equiv_H$ is an equivalence relation on $G$.

Proof. We need to show that the relation is reflexive, symmetric, and transitive. Let $x\in G$. Then $xx^{-1} = e\in H$ (since $H$ is a subgroup, hence contains $e$), so $x\equiv_H x$.

Now let $x,y\in G$, and suppose that $x\equiv_H y$; we want to show that $y\equiv_H x$ holds as well. Since $x\equiv_H y$, then $xy^{-1}\in H$. Since $H$ is a subgroup, it is closed under taking inverses, so $(xy^{-1})^{-1} = (y^{-1})^{-1}x^{-1} = yx^{-1}\in H$. By defintion, this means that $y\equiv_H x$, as desired.

Finally, suppose that $x,y,z\in G$ and that $x\equiv_H y$ and $y\equiv_Hz$. We want to show that $x\equiv_H z$. The first congruence implies $xy^{-1}\in H$; the second that $yz^{-1}\in H$. Since $H$ is a subgroup, it is closed under products, so $(xy^{-1})(yz^{-1})=xz^{-1}\in H$, hence $x\equiv_H z$, as desired. QED

Notice that the three basic properties of a subgroup are precisely needed for the three basic properties of an equivalence relation: $H$ contains the identity is used for reflexivity; $H$ is closed under inverses is used for symmetry; and $H$ is closed under products is used for transitivity.

Now, since $\equiv_H$ is an equivalence relation on $G$, by the Fundamental Theorem of Equivalence Relations, $\equiv_H$ induces a partition on $G$; that is, $G$ is broken up into disjoint parts, one for each equivalence class. Our next goal is to figure out if we have some description of the equivalence classes that is independent of the equivalence relation (this is very useful in general). Indeed, we do:

Theorem. Let $G$ be a group and let $H$ be a subgroup; let $x\in G$. The equivalence class of $x$ under the relation $\equiv_H$ is equal to the set $Hx = \{hx\mid h\in H\}$. That is, $$[x]_H = \{y\in G\mid x\equiv_Hy\} = \{hx\mid h\in H\} = Hx.$$

Proof. We need to show that each element in $Hx$ is in $[x]_H$, and that each element in $[x]_H$ is in $Hx$.

Let $z\in Hx$; that means that $z = hx$ for some $h\in H$. Then $$xz^{-1} = x(hx)^{-1} = x(x^{-1}h^{-1}) = h^{-1}\in H,$$ so by definition we have that $x\equiv_H z$. Thus, if $z\in Hx$, then $z\in[x]_H$. So $Hx\subseteq[x]_H$.

Conversely, let $y\in [x]_H$. Then $x\equiv_H y$, so $xy^{-1}\in H$. Thus, there exists $h\in H$ such that $xy^{-1}=h$. Multiplying on the right by $y$ we get $x=hy$, and multiplying on the left by $h^{-1}$ we get $h^{-1}x = y$. Since $h^{-1}\in H$, we get $y = h^{-1}x \in Hx$. Thus, if $y\in[x]_H$ then $y\in Hx$, so $[x]_H\subseteq Hx$.

Putting the two inclusions together, we conclude that $[x]_H = Hx$ for each $x\in G$. QED

Corollary. Let $G$ be a group, $H$ a subgroup. Then:

1. $Hx$ is nonempty for each $x\in G$.
2. $\displaystyle G = \mathop{\cup}_{x\in G} Hx$.
3. For all $x,y\in G$, if $Hx\cap Hy\neq\emptyset$, then $Hx=Hy$.

Proof. This follows from the fact that since the sets of the form $Hx$ are exactly the equivalence classes of the equivalence relation $\equiv_H$, they form a partition of $G$. QED

Corollary. Let $G$ be a group, $H$ a subgroup. For all $x,y\in G$, $x\equiv_H y$ if and only if $Hx = Hy$.

We give the sets of the form $Hx$ a name:

Definition. Let $G$ be a group, $H$ a subgroup, and $x\in G$. The set $$Hx = \{ hx\mid h\in H\}$$ is called the right coset of $x$ modulo $H$.

"Coset" is short for "congruence set", because the right coset is exactly the set of all things that are congruent on the right to $x$ modulo $H$.

In general, when you have an equivalence relation, the equivalence classes can have different sizes. But not so with these equivalence relation: because they are obtained by taking all possible products with elements of $H$, all equivalence classes are bijectable.

Theorem. Let $G$ be a group and $H$ a subgroup. Let $x,y\in G$ be any two elements. Then there is a bijection between the sets $Hx$ and $Hy$, given by \begin{align*} \psi\colon Hx &\to Hy\\ hx&\mapsto hy \end{align*}

Proof. To show that $\psi$ is one-to-one, let $hx,h'x\in Hx$ be such that $\psi(hx)=\psi(h'x)$. Then $hy = h'y$. Multiplying on the right by $y^{-1}$, we get $h=h'$, so $hx=h'x$. Thus, $\psi$ is one-to-one.

To show $\psi$ is onto, let $hy\in H$. Then $hx\in Hx$, and $\psi(hx)=hy$. Thus, $\psi$ is one-to-one and onto, so it is a bijection. QED

Now, let's assume that $G$ is finite, and $H$ is a subgroup. Then the equivalence relation $\equiv_H$ partitions $G$ into equivalence classes; each equivalence class is of the form $Hx$ for some $x\in G$, and by the previous theorem, they are all bijectable with one another, so they all have the same size, $k$. If there are $m$ distinct equivalence classes, each of size $k$, and they partition $G$, then the size of $G$ is the sum of the sizes of the distinct equivalence classes; that is, $|G|=mk$.

But what is $k$? $k$ is the size of the equivalence classes; they are all the same size. In particular, the equivalence class $He$ has size $k$. But what is $He$? Well, $$He = \{ he\mid h\in H\} = \{h\mid h\in H\} = H.$$ That is, $He = H$, so that $H$ itself has size $k$.

Since $|G|=mk = m|H|$, that means that $|H|$ divides $|G|$. That is:

Corollary [Lagrange's Theorem]. If $G$ is a finite group, and $H$ is a subgroup, then the size of $H$ divides the size of $G$.

You might ask if you can define a "congruence on the left"; yes, you can. We say $x$ and $y$ are congruent on the left modulo $H$ if $x^{-1}y\in H$, and we write $x{}_H\equiv y$. If we proceed as above, then we get that the equivalence class of $x$ modulo $H$ on the left is $xH$ (instead of $Hx$); the process is completely analogous; these are called left cosets of $H$. Turns out that there is a bijection between left and right cosets. One is tempted to define the bijection by sending the coset $xH$ to the coset $Hx$, but it turns out that this is not well defined (you can have $xH = yH$, but also have $Hx\neq Hy$). However, mapping $xH$ to the coset $Hx^{-1}$ works out (I'll leave it to you to work it out), so that the number of left cosets and the number of right cosets of $H$ in $G$ are the same, and the size of any left coset is the same as the size of any right coset of $H$. In general, the equivalence relation "congruent on the left modulo $H$" is not the same as the equivalence relation "congruent on the right modulo $H$"; the case when they are the same is interesting in its own right, and corresponds to the case when $H$ is a normal subgroup, which has a lot of important consequences all of its own that you will no doubt discover soon.

-
Arturo, where did you learn that etymology for coset? I'd never heard any etymology for it at all, so this is quite interesting. –  KCd Jan 9 '11 at 7:06
@KCd: I first learned all of this in Spanish, where cosets are "lateral classes" (left or right, as appropriate). I can't pinpoint in my memory when I learned this for English, seems like I've always known it. I'm at the JMM, so I can't look up to see if the etymology is in any of my basic references, but I will look it up tomorrow. –  Arturo Magidin Jan 9 '11 at 13:34
@KCd: I've been unable to find the etymology in any of my books; I hope I didn't make it up! I did however tracked down the apparent first use of the term: a paper by Miller, in the Quarterly Journal, published in 1910 (volume 41). I'm trying to see if I can track down a copy, though it is not available in my local library, to see if what he meant when he coined it. –  Arturo Magidin Jan 10 '11 at 19:40
I finished my project... –  Milica Jan 12 '11 at 13:59
@Milica: $ah$ is just the group product of $a$ and $h$. –  Zhen Lin Jan 8 '11 at 15:39