Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
- I played around with Mathematica's implementation of PermutationGroup[]. From it, I was able to construct the point group, and $\text{GL}(2,\mathbb{Z}_3)$, so it would be easy to show that the two groups are NOT isomorphic. Here is the notebook.
- We'll examine this page for some examples of the first isomorphism theorem.
- Here is a link to all the problems..
We are now ready to state and prove what mathematicians call the first isomorphism theorem. We've seen the following result several times before, without every fully stating it. When we consider the dihedral group of order 8 and let $N$ be the set of rotations, the identification graph looked a lot like $\mathbb{Z}_2$. The map $f:D_8\to \mathbb{Z}_2$ defined by $f(g)=0$ if $g$ is a rotation and $f(g)=1$ if $g$ is a flip, is a homomorphism from $D_8$ to $\mathbb{Z}_2$. The kernel of this homomorphism is precisely the rotations $N$. So the factor group $G/N$ consists of two cosets and is isomorphic to $\mathbb{Z}_2$. We now formally state the first isomorphism theorem.
Here's a formal statement of the first isomorphism theorem. It's slightly different than the text's, and we'll talk about why it's different in class. The version in the text involves more notation, but is essentially equivalent to this version. The key you need to proving this theorem comes from some of the earlier problems today (which problem has you show that something is an isomorphism?).
Problem 92 (The First Isomorphism Theorem Proof)
Prove the First Isomorphism Theorem.
Theorem (The First Isomorphism Theorem)
Let $f:G\to H$ be a surjective homomorphism with kernel $K$. Because we know that $f(x)=f(y)$ for any $y\in Kx$ (elements in the same coset of the kernel have the same image under $f$), then we can define a map $\phi:G/K\to H$ by defining $\phi(Kg)=f(g)$. This map $\phi$ is always an isomorphism.
We'll start using this theorem almost every day from here on out, as this is one of the biggest ideas in abstract algebra. For now, just make sure you can prove it.
Exercise (The Integers Under Addition Are Isomorphic To The Positive Integers Under Multiplication)
The set $\mathbb{R}^+$ is the set of positive real numbers. Consider the two groups $G=(\mathbb{R},+)$ and $H=(\mathbb{R}^{+},\cdot)$. Show that these two groups are isomorphic by showing that the exponential function $f(x)=\exp(x)$ is a group isomorphism.
Click to see a solution.
You could prove this by showing that the map is a homomorphism, and that it is a bijection by producing the inverse (namely $g(x)=\ln x$) and proving that it is an inverse. We've already done this in class.
Let's instead use the first isomorphism theorem. We know that $\exp(a+b)=\exp(a)\exp(b)$ high school algebra, so $f$ is a homomorphism. Given $y\in \mathbb{R}^{+}$, we let $x=\ln y$ and then $\exp(x)=y$, so the map is surjective. The only value such that $f(x)=1$ is $x=0$, so the kernel is $K=\ker f = \{0\}$. We could stop here and note that this means $f$ is 1 to 1, i.e. injective, and hence a bijection. Alternately, we could notice that $G/K=G$ (the identification graph of $G/K$ is the same as $G$ since $|K|=1$) and the first isomorphism theorem states that $f:G/K\to H$ is an isomorphism.
One of the reasons we care about factor groups is that we can often determine information about large, possibly hard to explore groups, by taking information from the factor group and pulling it back to the larger group. We know that the map $f:G\to G/N$ defined by $f(g)=Ng$ is a homomorphism, so we can often obtain information about $G$ by using this homomorphism to pull back information from $G/N$. The next problem has you show an example of this, namely that if you can find an element of order $k$ in $G/N$, then there must be an element of this order as well in $G$. Your work from last time should make this problem quite fast, provided you remember that $\langle a\rangle$ is a cyclic group, and as such is isomorphic to $\mathbb{Z}_{|a|}$, which we understand quite well.
Problem 93 (If A Factor Group $G/N$ Has An Element Of Order $k$ Then So Does $G$)
Suppose that $N$ is a normal subgroup of a finite group $G$ and that $Na$ has order $k$ as an element of $G/N$. Prove the following two facts.
- The order of $a$ in $G$ is a multiple of the order of $Na$ in $G/N$.
- There exists an element $b\in G$ that has order $k=|Na|$.
In other words, if a factor group has an element of order $k$, the the original group before factoring must have an element of order $k$ as well.
We have already shown that $Ha=aH$ for every $a\in G$ if and only if $aHa^{-1}=H$ for every $a\in G$. So one way to prove that a subgroup is normal is to prove that $aHa^{-1}=H$ for every $a\in G$. However, this requires that for each $a\in G$ you show both $aHa^{-1}\subseteq H$ and $H\subseteq aHa^{-1}$. The next problem simplifies this process even more. It says that if you know $aHa^{-1}\subseteq H$, then the other set inclusion must follow immediately.
Problem 94 (The Normal Subgroup Test)
Suppose that $G$ is a group and $H$ is a subgroup of $G$. Prove that $H$ is a normal subgroup of $G$ if and only if $xHx^{-1}\subseteq H$ for all $x\in G$.
How does normality behave when we look at subgroups? The following problem has you show that if you know $N$ is normal in $G$, and $N$ lies in some subgroup $B$ of $G$, then $N$ must be normal in $B$ as well. However, if we know $N$ is normal in $B$, and $B$ is normal in $G$, this does not guarantee that $N$ is normal in $G$. In symbols, we have $N\leq B\leq G$ and $N\trianglelefteq G$ implies $N\trianglelefteq B$, but we cannot say that $N\trianglelefteq B\trianglelefteq G$ implies $N\trianglelefteq G$. Being normal in a large group is enough to pass down to subgroups, but being normal in a subgroup is not enough to force normality in a larger group.
Problem 95 (Subgroups And Normality)
Suppose that $G$ is a group and that $A\leq B\leq G$.
- If $A$ is normal in $G$, prove that $A$ is normal in $B$.
- If $A$ is normal in $B$ and $B$ is normal in $G$, must $A$ be normal in $G$? Find a counter example to this.
The next problem has you show that when you compute factor groups, lots of properties pass immediately from $G$ to $G/N$. In particular, if $G$ is Abelian then $G/N$ is Abelian. Also, if $G$ is cyclic, then $G/N$ is cyclic. Many other properties follow as well.
Problem 96 (Factor Groups Preserve Being Cyclic And Abelian)
Suppose that $N$ is a normal subgroup of $G$.
- If $G$ is cyclic, prove that $G/N$ is cyclic.
- If $G$ is Abelian, prove that $G/N$ is Abelian.
The previous problem is an application of the bigger idea connected to homomorphism. Namely that the image of an Abelian group is Abelian, and the image of a cyclic group is cyclic.
Problem 97 (Images Of Abelian And Cyclic Groups)
Let $f:G\to H$ be a homomorphism. We have already shown that the image of $f$, written $f(G)$, is a subgroup of $H$.
- Prove that if $G$ is Abelian, then $f(G)$ is Abelian.
- Prove that if $G$ is cyclic, then $f(G)$ is cyclic.
How do the properties of Abelian and cyclic behave when combined with external direct products?
Problem 98 (External Direct Products Of Abelian And Cyclic Groups)
Suppose that $G$ and $H$ are groups.
- Prove or disprove: If both $G$ and $H$ are Abelian, then $G\oplus H$ is Abelian.
- Prove or disprove: If $G\oplus H$ is Abelian,then both $G$ and $H$ are Abelian.
- Prove or disprove: If both $G$ and $H$ are cyclic, then $G\oplus H$ is cyclic.
- Prove or disprove: If $G\oplus H$ is cyclic, then both $G$ and $H$ are cyclic.
The next problem has you prove Fermat's little lemma. We already conjectured this earlier in the semester when we noticed that if $p$ is a prime, then regardless of which $a$ we pick from $U(p)$, we must always have $a^{p-1}=1$. Sometimes, this is the order of $a$, whereas sometimes it is not. First, let's look at another conjecture we made earlier in the semester, to get us back into thinking about the $U$ groups.
Exercise (The Last Element Of UN Is Always Its Own Inverse)
Pick an integer $n$ greater than 1. Prove that $(n-1)\in U(n)$ is always its own multiplicative inverse.
Click to see a solution.
Notice that $(n-1)\pmod n = (-1)\pmod n$, which means $(n-1)^2\pmod n = (-1)^\pmod n = 1\pmod n$. This shows that the order of $n-1$ is 2, and also that $n-1$ is its own inverse.
Problem 99 (Fermat's Little Lemma)
Let $G$ be a finite group. Use Lagrange's theorem to prove the following two corollaries.
- We have $a^{|G|}=e$ for every $a\in G$.
- [Fermat's Little Lemma] Let $p$ be a prime and suppose $a\in U(p)$. Then we must have $a^p\pmod p=a$. (Hint: What is the order of $U(p)$?)
Using Fermat's little lemma and/or Lagrange's theorem, you should be able to rapidly prove the next result.
Exercise (The Order Of A In UP Divides P-1)
Let $p$ be a prime. Let $a\in U(p)$. Then $|a|$ divides $p-1$.
Click to see a solution.
There are several ways to prove this result.
- Since we know $a^p\pmod p = a$, we konw $a^{p-1}\pmod p = 1$. We know that $a^k=e$ in any group only when $k$ is a multiple of the order of $|a|$, so this means $k=p-1$ is a multiple of $|a|$.
- We now that $|U(p)|=p-1$. Hence every subgroup of $U(n)$, in particular $\left<a\right>$, must have an order that divides $p-1$. Since we know $|a|=|\left<a\right>|$, we know that $|a|$ divides $p-1$.
Because we are working with homomorphisms quite a bit in our work, we see the notation $f(g)=g$ quite a bit. We have also seen the notation $f^{-1}(h)$, but because homomomorphisms are not necessarily injective, this is not the inverse of $f$ applied to $h$. We have to remember that when we write $f^{-1}(h)$ we are talking about a set, namely the set of all $x\in G$ such that $f(x)=h$. We are not talking about a single $g$ so that $f(g)=h$. The notation $f^{-1}(h)$ represents the preimage (or inverse image) of $\{h\}$ under $f$. Here's a reminder of the formal definition.
Definition (Preimage Or Inverse Image)
If $f:A\to B$ and $C\subseteq B$, then the preimage of $C$ under $f$ is the set of all $a\in A$ such that $f(a)\in C$, and we write the preimage of $C$ under $f$ as $$f^{-1}(C)=\{a\in A\mid f(a)\in C\}.$$ When $C=\{c\}$ contains a single element, we often write the preimage of $C$ under $f$ as $f^{-1}(c)$ instead of using the more formal cumbersome notation $f^{-1}(\{c\})$.
Preimages and subgroups interact in a very nice way, namely homomorphisms preserve subgroups when computing inverse images. Next time we'll show that preimages preserve normality.
Problem 100 (The Preimage Of A Subgroup Under A Homomorphism Is A Subgroup)
Suppose that $f:G\to H$ is a homomorphism. Let $B$ be a subgroup of $H$. Let $A$ be the preimage of $B$, namely $$A=f^{-1}(B)=\{g\in G\mid f(g)\in B\}.$$ Show that $A$ is a subgroup of $G$.
Problem 101 (Homomorphisms Preserve Normal Subgroups)
Suppose that $f:G\to H$ is a homomorphism. Use The Normal Subgroup Test to prove the following:
- If $N$ is normal in $G$, then $f(N)$ is normal in $f(G)$.
- If $B$ is normal in $H$, then $f^{-1}(B)$ is normal in $G$.
At this point, we've proved quite a large collection of facts about homomorphisms and what they preserve. I strongly suggest that you look at pages 202-204 of your text to see a list of these properties. Then read the remarks on page 204.
The following two facts follow immediately from using the properties of homomorphisms. The first fact shows that any time you have a subgroup that contains half the elements of the group, that subgroup must be a normal subgroup.
Problem 102 (Subgroups Of Index 2 Are Normal)
Suppose that $H$ is a subgroup of $G$ with index $|G:H|=2$. Recall that the index of $H$ in $G$ is the number of distinct cosets of $H$ in $G$.
- Build a surjective homomorphism from $G$ to $\mathbb{Z}_2$.
- Show that $H$ is normal in $G$.
This next fact shows that any time you have subgroup in a factor group $G/N$, it corresponds to a subgroup $H$ in $G$ that contains $N$.
Problem 103 (Subgroups Of A Quotient Group Correspond To Subgroups Of The Original Group)
Suppose that $N$ is a normal subgroup of $G$ and that $B$ is a subgroup of $G/N$. Prove the following:
- There exists a subgroup $H\leq G$ such that $H/N=B$.
- If we know that $n=|N|$ and $m=|B|$ (so $n$ is the order of $N$ in $G$, and $m$ is the order of $B$ in $G/N$), then $G$ must have a subgroup $H$ of order $nm$.
As a suggestion, consider the homomorphism $f:G\to G/N$ given by $f(g)=Ng$ and use some properties of homomorphisms.
To tackle the next problem, you'll want to rely on the fact that $|(g,h)|=\text{lcm}(|g|,|h|)$, together with the fact that two integers are relatively prime if and only if their product is their least common multiple.
Problem 104 (A Direct Product Of Cyclic Groups Is Cyclic If And Only If The Groups Have Relatively Prime Orders)
Suppose that $G$ and $H$ are finite cyclic groups. Prove that $G\oplus H$ is cyclic if and only if $|G|$ and $|H|$ are relatively prime.
Exercise (A Direct Product Of Cyclic Groups Is Cyclic If And Only If The Groups Have Relatively Prime Orders)
Use induction to extend the previous result to the external direct product of $n$ cyclic groups. So prove that if $G_1,G_2,\ldots,G_n$ are $n$ cyclic groups, then $G_1\oplus G_2\oplus \cdots\oplus G_n$ is cyclic if and only if $|G_i|$ and $|G_j|$ are relatively prime when $i\neq j$.
Click to see a hint.
This exercise require that you use induction on an "if $p$ then $q$" statement. In addition, the $q$ part of the statement involves an if and only if. You must be very careful how you tackle this problem.
Problem 105 (An Isomorphism From $U(st)$ To $U(s)\oplus U(t)$ When $s$ And $t$ Are Relatively Prime)
Recall that $\varphi$, the Euler-phi function is defined by $\varphi(n)=|U(n)|$, the order of $U(n)$. Suppose $n=st$ where $s$ and $t$ are relatively prime. In this problem you'll show that $\varphi(st)=\varphi(s)\varphi(t)$.
- Show that $f:U(st)\to U(s)\oplus U(t)$ defined by $f(x)=(x\mod s,x\mod t)$ is an isomorphism.
- Why does $\varphi(st)=\varphi(s)\varphi(t)$ when $s$ and $t$ are relatively prime?
- Use the results above to compute $\varphi(17\cdot 19)$ and $\varphi(15\cdot 63)$.
It's time to use the power of factor groups, together with induction, to prove the first of many powerful theorems that apply to finite groups. The key lies in the fact that the order of a factor group $G/N$ will always be less than the order of $G$, provided $N$ is not trivial. This means that if we use induction on the order of a group, then if we can use a factor group to pull back information to a larger group, induction will provide us with precisely the tool we need to prove some really powerful theorems about groups.
The next theorem is often called Cauchy's theorem (for Abelian groups). The more general version of Cauchy's theorem states that if $p$ is a prime that divides the order of the group, then $G$ must have an element of order $p$. Because it's an Abelian group, every subgroup is normal, which means we can quickly create factor groups any time we obtain a subgroup. If we remove the Abelian condition, then we have to prove that a subgroup is normal before we can create a factor group. The Abelian condition is a simplifying assumption, which can be removed with much more work.
Problem 106 (Abelian Groups Have An Element Of Order $p$ For Every Prime That Divides The Order Of The Group)
Let $G$ be an Abelian group and let $p$ be a prime. Prove that if $p$ divides the order of $G$, then there exists $a\in G$ with order $p$.
Hint: This problem is done by induction on the order of $G$.
For each integer $k\geq 2$, let $P(k)$ be the statement, "For every positive integer $n<k$, if $|G|=n$ and $p$ divides $|G|$ then $G$ has an element of order $p$." Use induction to prove that $P(k)$ is a true statement for every integer $k\geq 2$. This will require you to do two things.
- Is the statement $P(2)$ true? Is the statement $P(3)$ true?
- If you assume for some specific $k\geq 2$ that the statement $P(k)$ is true, then prove that the statement $P(k+1)$ is true. To prove $P(k+1)$ is a true statement, you have to prove that if $n<k+1$ and $|G|$ has order $n$ with $p$ dividing $G$, then $G$ has an element of order $p$. This is quite a lot of facts to prove. However, the induction assumption should prove every single one of them instantly except for when $n=k$. So you must show that if $|G|=k$ and $p$ divides $|G|$, then $G$ has an element of order $p$. You know for sure that $G$ has an element of some order other than 1, say $m=|a|$, which means that it has an element $b$ of some prime order $q$ (why?). If $q=p$ we're done. Otherwise, consider the factor group $G/\left<b\right>$. What is the order of $G/\left<b\right>$? Does $p$ divide $G/\left<b\right>$? What does the induction assumption then tell you? How does problem 103 help?
- To continue more problems (or see past ones), please follow this link.
For more problems, see AllProblems