Your rich uncle wants you!
For motivation, let's consider this practical question. Your uncle owns a necklace shop. He wants to know how many different models of necklaces he can make that have two red beads and two blue beads. You've been going around telling people that you're pretty good at math, so he asks you to help him out. After trying out many configurations, you find that there're only two configurations as the following.
All the "other" configurations can be obtained by these two basic configurations by rotating them or flipping them. But what if you have $5$ beads to make a necklace of $3$ colors. Naturally, you're interested in a general theory that allows you to compute everything of this sort very quickly. To do this, we're gonna immersed ourselves in a ton of group theory. But don't be intimidated, by the end of the day your rich uncle needs you!
Coset and Lagrange's Theorem
Watch the excellent following video for a quick grasp of cosets.
Here's the recap for the video. First, we define what a subgroup $H$ of a group $G$ is. If $H$ is a subgroup of the group $G$, it basically means that $H$ is itself a group contained in this "super-group-kind-of-thing" called $G$. Now, let's learn about cosets. Cosets are the subsets of a group that are constructed by a subgroup $H$. First you pick a random element $g_0$ in group $G$ to put in the first set called the coset. Then you add all the $g_0h$, with $h$ running through all the elements of $H$, to the coset containing $g_0$. Naturally, you would expect that your first coset is not big enough to cover the whole group $G$, as your subgroup $H$ is most likely to be smaller than $G$ to begin with. So there would be some leftovers outside the first coset. Pick one such element called $g_1$ and construct the second coset in the same way (i.e. putting all the $g_1h$ in the same set). Repeat this process until we have all the elements in $G$ lying on some cosets. The following example is for $G$ and $H$ that give three cosets.
Now, we're gonna show that $G$ is evenly and disjointly partitioned into these cosets. In other words, the cosets are distinct from each other and equal in their number of elements. First, we show distinctness by proving that there is no element that is shared by two cosets. For the proof, we use contradiction. A little digression on how this technique works. You pretends that you believe what your braggart friend is telling you. But slowly you show him how his story leads to a ridiculousness. Then you say, "Gotcha!"
In our problem, assume that there exists an element called $c$ that belong to both coset $i$ and $j$. This means that $c= g_ih_i = g_jh_j$. This implies that $g_i = g_j(h_jh_i^{-1})=g_jh_k$. This is because $h_i$ and $h_j$ belong to subgroup $H$ that is itself a group, from which we have inverse and closure properties. So $g_i = g_jh_k$, and this implies that $g_i$ is in the coset of $g_j$, which is not true because of the way we choose $g_i$ and $g_j$. Therefore, we have a contradiction, and indeed all the cosets are "disjoint". Now we prove that the cosets are equal in size. Specifically, we demonstrate that all the elements of a coset are distinct. This is easy. If $g_ih_j =g_ih_k$, we multiply both sides by $g_i^{-1}$ to get $h_j = h_k$. So with $h_i$ and $h_k$ distinct, all the elements of the coset must be distinct. So the size of the coset is just the size of $H$. Therefore, all the cosets have the same size (i.e. the size of $H$).
No comments:
Post a Comment