MATH 415 Lecture 7

« previous | Tuesday, September 17, 2013 | next »

Additional Office Hours:

• TR 13:15–14:00
• After 17:00 by appointment
• W 11:15–12:00

Section 10: Cosets and Lagrange's Theorem

Given $H<G$, where $G$ is finite, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left|H\right|\mid \left|G\right|} .

Define two Equivalence relations: $\sim _{L}$ (left) and $\sim _{R}$ (right)

Theorem 10.1

Let $H\leq G$.

• Let $a\sim _{L}b$ iff $a^{-1}\,b\in H$
• Let $a\sim _{R}b$ iff $a\,b^{-1}\in H$

Then $\sim _{L}$ and $\sim _{R}$ are equivalence relations

Proof. For $\sim _{L}$

• Reflexivity: $a^{-1}\,a=e\in H$
• Symmetry: $a^{-1}\,b\in H$ implies $(a^{-1}\,b)^{-1}=b^{-1}\,a\in H$
• Transitivity: $a^{-1}\,b\in H$ and $b^{-1}\,c\in H$ give $(a^{-1}\,b)\,(b^{-1}\,c)=a^{-1}\,c\in H$.

For $\sim _{R}$

• Reflexivity: $a\,a^{-1}=e\in H$
• Symmetry: $a\,b^{-1}\in H$ implies $(a\,b^{-1})^{-1}=b\,a^{-1}\in H$
• Transitivity: $a\,b^{-1}\in H$ and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle b\,c^{-1}\in H} give Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (a\,b^{-1})\,(b\,c^{-1})=a\,c^{-1}\in H} .

quod erat demonstrandum

Cosets

The defined relation means that if $a\sim _{L}b$, then there exists a $h\in H$ such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle b=a\,h} . Respectively, if $a\sim _{R}b$, then there exists a $h\in H$ such that $b=h\,a$. In shorthand, let $a\,H=\left\{a\,h~\mid ~h\in H\right\}$ and $H\,a=\left\{h\,a~\mid ~h\in H\right\}$, then

${\begin{aligned}a\sim _{L}b&\iff b\in a\,H\\a\sim _{R}b&\iff b\in H\,a\end{aligned}}$

• $a\,H$ is called a left coset of $H$ containing $a$, and
• $H\,a$ is called a right coset of $H$ containing $a$.

In general, $a\,H\neq H\,a$. For abelian (commutative) groups, $a\,H=H\,a$, so we will use $\sim$ for these groups.

Example 10.4

Take $n\,\mathbb {Z} <\mathbb {Z}$. If we have $a\sim b$ (or $b-a\in \mathbb {Z}$ and $a-b\in \mathbb {Z}$), then we can say that $a$ and $b$ are congruent modulo $n$.

Cosents correspond to elements of $\mathbb {Z} _{n}$. For example, when $n=6$ and $H=\left\{0,3\right\}$, we get

• coset containing 0 is Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\{0,3\right\}}
• coset containing 1 is $\left\{1,4\right\}$
• coset containing 2 is $\left\{2,5\right\}$

Take a look at the following addition table:

+6	0	3	1	4	2	5
0	0	3	1	4	2	5
3	3	0	4	1	5	2
1	1	4	2	5	3	0
4	4	1	5	2	0	3
2	2	5	3	0	4	1
5	5	2	0	3	1	4

Example 10.7

Take group $S_{3}=\left\{\rho _{0},\rho _{1},\rho _{2},\mu _{1},\mu _{2},\mu _{3}\right\}$, where each $\rho$ is a triangular rotation and each $\mu$ is a transposition. Note that $e=\rho _{0}$, and note that $S_{3}$ is non-abelian. Let $H=\left\{\rho _{0},\mu _{1}\right\}$. Then

• left coset containing $\rho _{0}$ is $\rho _{0}\,H=\left\{\rho _{0},\mu _{1}\right\}$
• left coset containing $\rho _{1}$ is $\rho _{1}\,H=\left\{\rho _{1}\,\rho _{0},\rho _{1}\,\mu _{1}\right\}=\left\{\rho _{1},\mu _{3}\right\}$
• left coset containing $\rho _{2}$ is $\rho _{2}\,H=\left\{\rho _{2}\,\rho _{0},\rho _{2}\,\mu _{1}\right\}=\left\{\rho _{2},\mu _{2}\right\}$

Notice the differences between left and right cosets

• right coset containing $\rho _{0}$ is $H\,\rho _{0}=\left\{\rho _{0},\mu _{1}\right\}$
• right coset containing $\rho _{1}$ is $H\,\rho _{1}=\left\{\rho _{1},\mu _{2}\right\}$
• right coset containing $\rho _{2}$ is $H\,\rho _{2}=\left\{\rho _{2},\mu _{3}\right\}$

The Theorem of Lagrange

Let $H<G$ where $G$ is a finite group. Then the order of $H$ is a divisor of the order of $G$:

$\left|H\right|\mid \left|G\right|\,\!$

Proof. Given a finite group Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1 \in G} be the identity element, and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_2 \, H} , $a_{3}\,H$, … $a_{k}\,H$ be cosets.

Observe that either Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i \, H = a_j \, H} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i \, H \cap a_j \, H = \emptyset} .

For all $a,b$, we have $\left|a\,H\right|=\left|b\,H\right|=\left|H\right|$.

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} be a function from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \, H} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(h) = a \, h} . $\phi$ a bijection.

We have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is a union of distinct subsets Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} , where all orders Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |H_i|} are equal. Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| G \right| = k \, \left| H \right|} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |H|} divides Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |G|} .

quod erat demonstrandum

We denote the number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\left| G \right|}{\left| H \right|} = \left( G : H \right)} as the index of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} .

Corollary. Every group of prime order is cyclic.

Suppose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} has prime order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} , and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \ne e} be generator for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H = \left\langle a \right\rangle} . Then either Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |H| = 1} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |H| = p} . The first case is impossbile because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |H| \ge 2} (namely, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} must be elements). Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |H| = p} , and its cyclic generator is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} . So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} must be cyclic.

quod erat demonstrandum

Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K \le H \le G} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (H:K)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (G:H)} are finite, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (G:K)} is finite and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (G:K) = (G:H) \, (H:K)} .