Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
Definition (Normal Subgroup $N\trianglelefteq G$)
We say that a subgroup $N$ of $G$ is a normal subgroup of $G$ if for each $a\in G$ the right coset $Na$ and left coset $aN$ are equal, so we have $Na=aN$ for every $a\in G$. We write $N\trianglelefteq G$ to mean that $N$ is a normal subgroup of $G$.
The next problem helps you refresh your memory about the definitions of homomorphism and order of an element. The problem has you show that if $f$ is a homomorphism from $G$ to $H$, then while $f$ may not preserve the order of elements in $a$, it has to send an element of order $n$ to an element whose order divides $n$. This must happen on an element by element basis. So if we know something about the order of $f(a)$, then we know that $|a|$ must be a multiple of $|f(a)|$.
Problem 89 (The order of $a$ is a multiple of the order of $f(a)$, or $|a|=k|f(a)|$)
Suppose that $f:G\to H$ is a homomorphism. Prove that if $a\in G$ has order $n$, show that $|f(a)|$ divides $n$, i.e. show that $|a|$ is a multiple of $|f(a)|$.
In addition to homomorphisms interacting nicely with elements and orders, even more can be said. In particular, if you know that there are $n$ things that map to the indentity $e$ in the codomain, then the homomorphism must carry exactly $n$ elements from the domain to each element of the codomain. For this reason, we say that a homomorphism is an $n$-to-one map. If you look back at last week's problems, you should see somewhere that we showed a result very similar to this, namely when we showed that the kernel of $f$ is a normal subgroup. Please look back at that problem before tackling this one.
Problem 90 (A homomorphism is an $n$-to-one map)
Let $f:G\to H$ be a homomorphism.
- Suppose that $\ker f$ has order $n$. If we know that $f(g)=h$ for some $g\in G$, prove that there are exactly $n$ different elements in $G$ that map to $h$, so we know that the preimage of $h$, namely $f^{-1}(h)$, is a set with $n$ elements. This shows that $f$ is an $n$-to-one map.
- Prove that $f$ is injective if and only if the kernel of $f$ is trivial, i.e. $\ker f = \{e\}$.
- Prove that if $f$ is surjective and the kernel of $f$ is trivial, then $f$ is an isomorphism.
Here are some comment's about these problems.
- This should follow without any additional work from a previous problem. Just figure out which problem.
- This is why in linear algebra we know that $A\vec x = b$ has a single solution if and only if the only solution to $A\vec x=\vec 0$ is $\vec x= 0$, which means the columns of $A$ are linearly independent. Finding the kernel, or null space, is crucial in linear algebra.
- This is why in linear algebra we know that when the kernel of a square matrix is trivial, then the matrix is invertible.
We now know that a homomorphism is an $n$-to-one map. This fact is basically a directly result of the fact that the kernel of a homomorphism is normal. The next exercise shows that every normal subgroup is the kernel of some homomorphism. This shows that studying normal subgroups is precisely equivalent to studying kernels of homomorphisms. We've actually been using the result below without every stating it formally. Given a Cayley graph, we can easily build a map from the Cayley graph to the corresponding identification graph using right cosets of $N$ by sending $a$ to $Na$. This exercise just has you shows that this map is indeed a homomorphism whose kernel is $N$.
Exercise (A Subgroup Is Normal If And Only If It Is The Kernel Of Some Homomorphism)
Prove that $N$ is a normal subgroup of $G$ if and only if $N$ is the kernel of some homomorphism $f:G\to H$ from $G$ to another group $H$.
Click to see a solution.
We already know that if $N$ is the kernel of a homomorphism, then it is normal. So one direction of this if and only if proof is complete.
If we know $N$ is normal, then we can let $H=G/N$ and define $f:G\to H$ by $f(g)=Ng$. This map is a homomorphism because we already showed that $f(ab)=N(ab)=(Na)(Nb) = f(a)f(b)$ when we showed that the set product is a binary operation on cosets of a normal subgroup. The kernel of this map is the set of elements $g\in G$ such that $f(g)=N$. This is precise the set of $g\in G$ such that $Ng=N$ which is true if and only if $g\in N$ by the properties of cosets. Hence the kernel of this map is $N$.
This next problem has you practice using Lagrange's theorem. Both facts in the problem should follow immediately from applying Lagrange's theorem and another observation. These facts are often considered corollaries of Lagrange's theorem.
Problem 91 (The Order Of An Element Divides The Order Of A Group)
Let $G$ be a finite group. Use Lagrange's theorem to prove the following two corollaries.
- Let $a\in G$. The order of $a$ divides the order of $G$.
- If $|G|=p$ for some prime $p$, then $G$ is cyclic.
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$.
For more problems, see AllProblems