Group Theory Primer, part 4: everything you wanted to know about homomorphisms but were afraid to ask.

June 23, 2010

Last time we went over some normal subgroups, how to direct product two groups, and how to quotient out by (normal) subgroups.  As we said before, though, groups (like vector spaces) are pretty boring by themselves.  Yes, studying groups by themselves can give us relations between elements and so on (like what kinds of elements in a particular group have the property such that when you square them they become the identity), but, like vector spaces, we can learn a lot about a group by what it can and can’t map into nicely.

Now, let’s think about this for a second.  What if I said something like the following: let’s take a group $G$ such that the elements are $\mbox{possum}$ and $\mbox{fox}$.  Let’s say that

$\mbox{possum}\times \mbox{possum} = \mbox{possum}$

$\mbox{possum} \times \mbox {fox} = \mbox{fox} \times \mbox{possum} = \mbox{possum}$

$\mbox{fox} \times \mbox{fox} = \mbox{fox}$

and those are all the possible interactions.  You could give any reasonable justification to this group, but it reduces to the fact that it is just a group: it’s just a set of elements and an operation.

Now, it was pretty annoying writing those words over and over — couldn’t we just call foxes something like the number $1$?  And couldn’t we call possums something like the number $0$?  Then what do we get?

$0\times 0 = 0$

$0\times 1 = 1\times 0 = 0$

$1\times 1 = 1$

Now, this is a lot easier to read, and it conveys the exact same information.  We’ve essentially just “renamed the elements.”  This particular map is the nicest of all maps: since the elements in our sets are in one-to-one correspondence — that is, we have

$0 \leftrightarrow \mbox{possum}$

$1 \leftrightarrow \mbox{fox}$

and since our operation $\times$ was also brought down into the new group and has the same properties, we call this kind of mapping an isomorphism.  We’ll get down to defining exactly what this is in a moment, but, for now, this should be pretty good motivation to start studying maps.

Another example of the usefulness of mapping comes up if we try to “squish” a group into another group.  For example, if we wanted to map the integers under addition down into the set $\{\mbox{even}, \mbox{odd}\}$ with a similar additive operation, then we’d have a lot of elements being mapped down to “even” and a lot being mapped down to “odd” — there is no one-to-one correspondence like there is above since there’s many numbers which correspond to “even” and many numbers that correspond to “odd”.  Nonetheless, this tells us quite a bit about the integers which is not clear from investigating their group by itself perhaps.  For example, when we prime factorize, when is something divisible by 2?  When it is even, right.  We know if a number is even, it is divisible by 2.  This may seem obvious to you now, but think back to when you were learning what even numbers were.  Does the number 10 immediately “look” even?

Another kind of mapping we’ll go through is when we want to “shoot” some group into a part of another group.  Say we wanted to take the group of all rational numbers under addition and just place it on top of the group of real numbers under addition; how could we do this?  Well, just think of it as having some kind of transparent paper with a few street names on it and trying to overlay it on a map: you just line things up and everything else falls into place.  This is somewhat similar, but notice there is not a one-to-one correspondence.  In fact, there are an uncountable number of real numbers and a countable number of rational numbers.

Enough with the motivation, let’s get down to business.  For injections, surjections, and bijections below, we don’t consider the operations in the groups but just the underlying sets.  Therefore, these definitions can be used in the less restrictive study of sets.

Injections.

I’m going to use Bourbaki as standard here and call this type of map an injection.  It is also called an “into” map, but this can get confusing at times.  An injective map is like the one that we mentioned with the transparent paper and the map: we want it so that we’re essentially “overlaying” our group onto another one, and the only thing we want to lay on the identity element of the bigger group is the identity element of the smaller group.  Think of it this way: if we wanted to lay the rational numbers on top of the real numbers, we’d align their zero elements and everything else would line up nicely.  We wouldn’t want to fold the rationals and make 0 and 1 lay on top of the real’s origin.  Similarly, for $A$ and $B$ are sets, an injection is a map $f:A\rightarrow B$ such that for $a\in A$, if $f(a) = 0$ then $a = 0$.  In other words, only 0 gets sent to 0.

If a map is an injection, we usually write it the following way on our arrow diagrams: $f:A\hookrightarrow B$.

Surjections.

Like that “even, odd” map above, a surjection is one such that every element in the image (the “range” of the map) has at least one element from the domain going to it.  It would be silly if we made three categories called “even”, “odd”, and “neither” for the integers, since there will be no integers in the “neither” group.  This is the idea behind surjections: we want to hit everything in the target space with something in the domain space.  The formal definition is: a map $f:A\rightarrow B$ is a surjection if for every $b\in B$ we have some $a\in A$ such that $f(a) = b$.  Notice that there can be more than one element, but the stipulation is that there is at least one.  Coo’.

There is no standard notation, I think, for surjections (I may be mistaken) so I may use $f:A\Rightarrow B$, but because this always confuses me into thinking I’m having $A$ imply $B$, I’ll often just use the regular $f:A\rightarrow B$ and note that $f$ is surjective.

Bijections.

Real simple, cat: a bijection is a map $f:A\rightarrow B$ which is both injective and surjective.  Ya dig?  In other words, a map is bijective if it creates a one-to-one correspondence (for each element $a\in A$ there exists exactly one element $b\in B$ such that $f(a) = b$) between the two sets).

There is no standard notion, I don’t think, but we usually say something along the lines of $f: A\leftrightarrow B$ or simply, “$f:A\rightarrow B$ is a bijection.”

Image, Kernel, and All That.

These words kind of sound scary, but they aren’t.  Given some map $f:A\rightarrow B$, we won’t care for the moment if it’s injective or surjective or what, just that it’s a map.  We call the image of $f$ all of the elements that we get when we plug in everything in $A$.  In other words, $Im(f) = \{f(a)|a\in A\}$.  So, for example, the image of that “even and odd” map is just the elements “even” and “odd”.  For the image of that map that overlays the elements of the rationals over the reals, the image is the rationals.

For the curious: Some people will say “range” or “codomain” when they mean “image”, and for the most part no one will care.  There is a subtle distinction, though: consider that map $g:{\mathbb Q}\rightarrow {\mathbb R}$ that takes the rationals and “lays them on top of the reals.”  Specifically, $g(x) = x$ for every $x\in {\mathbb Q}$.  The codomain of this has been defined to be the reals — it is the “right hand term” that the map is going to.  We could, for example, make $g:{\mathbb Q}\rightarrow {\mathbb C}$ and the codomain would be ${\mathbb C}$ instead.  The codomain is sometimes called the range, but this can get confusing as we also use the term range to mean “image.”  The image, on the other hand, is the set of all values that are being mapped into the co-domain.  Confused?

To take a concrete example from your Algebra II days: let’s say we’re given $f:{\mathbb R}\rightarrow {\mathbb R}$ defined as $f(x) = x^{2}$.  The codomain will be ${\mathbb R}$ since that’s the “right-hand-side set” when we defined the function in arrow notation above.  The image will be $\{x|x\geq 0\}$.  Either one could be the range, but in high school we usually call the latter the range for some reason.

The kernel is the set of all values in the domain space that map to the identity in the range space.  In formal speak, for $f:A\rightarrow B$, $Ker(f) = \{a\in A| f(a) = 0\}$.

For example, if we have the function $g:{\mathbb Z}\rightarrow \{0,1\}$ where every even number is mapped to 0 and every odd number is mapped to 1, we have that every single even number is in the kernel of $g$, since they’re all sent to 0.  The image of this map, for the curious reader, is just $\{0,1\}$.

Homomorphisms.

Okay, here’s the deal: yeah, yeah, we’ve got surjections and injections and bijections and whatnot, but that doesn’t tell us anything about what’s happening with the operation in the group.  Take this for example:

Let’s lay the group of integers under addition, $({\mathbb Z}, +)$, over the group of integers numbers under multiplication, $({\mathbb Z}, \cdot)$.  Okay, cool, cool.  So, what’s our map?  Well, it’s obvious, isn’t it?  $f:{\mathbb Z}\rightarrow {\mathbb Z}$ is defined by $f(x) = x$.  That’s it, just send the elements to themselves.  So, $f$ is a bijection.  Sweet.  But, hold on a second.  In the first group if put 3 and 4 together, we’d get 7.  In the second group if we put 3 and 4 together, we’d get 12.  That’s not very nice behavior, and our map doesn’t tell us anything about that!  Stupid map.  We want to find a way to make our map tell us more about how elements interact in a group — after all, addition is a bit different from multiplication!

In comes homomorphisms.  Luckily, they behave the way we’d expect a nice map to behave.  In fact, they’re just set maps with a little bit of extra structure.  For $(A, +)$ is a group and $(B, \dagger)$ is another group, we say that $f:A\rightarrow B$ is a homomorphism if for all $x,y\in A$ we have that:

• $f(1_{A}) = 1_{B}$.
• $f(x + y) = f(x) \dagger f(y)$.

Notice that $+$ is the operation in the group $A$ and $\dagger$ is the operation in the group $B$.  This says that the identity of $A$ should go to the identity of $B$, and that if we operate on elements $x,y\in A$ and take $f$ of that sum, then it should be the same as taking $f(x)$ and $f(y)$ and then operating on them with $B$‘s operation.  Trust me, this is much easier done than said.

Why didn’t our crazy map above work with the integers over the integers?  Well, $3 + 4 = 7$ but $f(3 + 4) = f(3)\cdot f(4) = 3\cdot 4 = 12$ which would imply that $7 = 12$.  But that’s crazy.  That’s why this map was not a homomorphism.

Is $f:({\mathbb Z}, +)\rightarrow ({\mathbb Z}, +)$ defined by $f(x) = x + 1$ a homomorphism?  Well, $f(0) = 1$ and 1 isn’t the identity element in $({\mathbb Z}, +)$.  This violates our first rule of homomorphisms, and so this is not a homomorphism.

Convince yourself that the map $f: ({\mathbb R}, +)\rightarrow ({\mathbb R}, \cdot)$ given by $f(x) = e^{x}$ is a homomorphism between the reals under addition and the reals under multiplication.  You don’t want to?  Then I’ll do it for you here.  So lazy.

• First, note $f(0) = e^{0} = 1$ which is the multiplicative identity.
• Second, note that $f(x + y) = e^{x + y} = e^{x}\cdot e^{y} = f(x)\cdot f(y)$.

This shows that this map is, in fact, a homomorphism.

Isomorphisms.

Homomorphisms, being maps, can obviously be injective, surjective, bijective, or none of these.  There are some standard names for these types of maps (for example, injective homomorphisms are sometimes called monomorphisms or monic morphisms, and surjective homomorphisms are sometimes called epimorphisms or “epic homomorphisms.”  yes, really.) but in general the only one that gets used constantly is isomorphism: a bijective homomorphism.

The idea behind isomorphisms is essentially that if two groups are isomorphic, they behave exactly the same but we just rename their elements and their operation.  For example, when we started this post, we talked about foxes and possums and 0’s and 1’s.  Find a map such between these two sets such that this map is surjective, injective, and a homomorphism and, therefore, an isomorphism.  Two groups are isomorphic if there exists an isomorphism between the two.  If the two groups $A$ and $B$ are isomorphic, then we write $A\cong B$.

A Few Basic Group Theory Theorems.

Okay.  So, for these, we’re gonna let $A, B$ be groups, and we’re going to let $f:A\rightarrow B$ be a homomorphism.  We’re going to use multiplicative notation for the operations of the groups.  Therefore, the identity element in both groups will be denoted as 1.

Theorem: We always have that $f(a^{-1}) = f(a)^{-1}$.

Proof: Note that $1 = f(1) = f(a\cdot a^{-1}) = f(a)\cdot f(a^{-1})$, and so $f(a^{-1})$ is the inverse of $f(a)$.  In other words, $f(a^{-1}) = f(a)^{-1}$.

Theorem: $Ker(f)$ is a normal subgroup of $A$.

Proof: First, we have that $1\in Ker(f)$ since $f(1) = 1$.  If $a,b\in Ker(f)$ then we have that $f(a) = 1$ and $f(b) = 1$ so $f(a\cdot b) = f(a)\cdot f(b) = 1\cdot 1 = 1$.  Therefore, $Ker(f)$ is a subgroup of $A$.  Normal-ness is an exercise for the reader.  Hint: you only need to show that $a\cdot Ker(f) \cdot a^{-1} \subseteq Ker(f)$ (why?).

Theorem: $Im(f)$ is a subgroup of $B$.

Proof: It’s up to you!  Follow the way we did the similar proof above.

Theorem: The homomorphism $f$ is injective if and only if for $x,y\in A$ we have that $f(x) = f(y)$ implies $x = y$.

Proof: Suppose $f$ is injective.  If $f(x) = f(y)$ then this means $f(x) + (-f(y)) = 0$.  This means, as $f$ is a homomorphism, that $f(x + (-y)) = 0$.  Because $f$ is injective, only 0 maps to 0, so we must have that $x + (-y) = 0$ which implies $x = y$.  Now you do the other direction.

Theorem (The First Isomorphism Theorem): Given $f:A\rightarrow B$, we have the isomorphism $A/Ker(f) \cong Im(f)$.

Proof: The proof of this is not really that enlightening, but it is a good chance to think about making bijective maps and proving injectivity, surjectivity, and so on.  This is a big proof, so here’s our battle plan:

1. Make a map that will be used to create the bijection between $A/Ker(f)$ and $Im(f)$.
2. Show that this map is well-defined (optional on the first read-through!  It can be confusing to people new to this stuff).
3. Show that this map is a homomorphism.
4. Show that this map is bijective by showing it is injective and surjective.

(1) The map we’re gonna use to show our bijection is the following map: $g: A/Ker(f) \rightarrow Im(f)$ by $g(a\cdot Ker(f)) = f(a)$.  That is, it takes the coset $a\cdot Ker(f)$ to the image of $a$.

(2) The hard part is showing that this is a well-defined map (that no matter what element we choose to represent the coset, we’ll always get the same image when we apply the function to it) and this is kind of slick.  If you don’t want to get bogged down in this proof, skip the next paragraph.

Think about two elements in the coset $a\cdot Ker(f)$.  Let’s say that $a\cdot Ker(f)$ and $b\cdot Ker(f)$ are the same coset.  Then we have that $a\cdot Ker(f) = b\cdot Ker(f)$ which implies that $(ab^{-1})\cdot Ker(f) = Ker(f)$ which implies that $(ab^{-1}) \in Ker(f)$.  That means that $f(ab^{-1}) = 1$.  This means that $f(a)\cdot f(b^{-1}) = 1$ and this implies $f(a)\cdot f(b)^{-1} = 0$ or in other words $f(a) = f(b)$.  The image under $g$ doesn’t change, and the map is well-defined.

(3) Okay, now, remember: we have the map $g$ defined by $g(a\cdot Ker(f)) = f(a)$.  It’s well-defined, so we just need to show two things: it’s a bijection, and that it’s a homomorphism.  Let’s show homomorphism first.

First, $g(1\cdot Ker(f)) = f(1) = 1$ since $f$ is a homomorphism.  So identity goes to identity.

Next, note $g((a\cdot Ker(f))\cdot (b\cdot Ker(f)) = g((ab)\cdot Ker(f))$

$= f(ab) = f(a)\cdot f(b)$.

And so $g$ is a homomorphism.  By the way, make sure you’re well aware of why all these equalities above work.

(4) Last, we need to show that this is surjective and injective.  Well, let’s show injective first: what goes to 1?  So, we need every element $x$ such that $g(x\cdot Ker(f)) = f(x) = 1$, but by definition if $f(x) = 1$ then $x\in Ker(f)$.  Hence, $x\cdot Ker(f) = Ker(f) = 1\cdot Ker(f)$, and so the kernel of the map $g$ is just 1, or, in other words “trivial.”  This means the map is injective.

To show surjectivity, we need that, for every element $y\in Im(f)$ there exists some element $x\in A/Ker(f)$ such that $g(x\cdot Ker(f)) = f(x) = y$.  But wait a second.  If $y\in Im(f)$, then, by definition of $Im(f)$, there had to have existed some $x_0$ such that $f(x_0) = y$, otherwise $y$ wouldn’t be in the image!  Take this $x_0$, and we then have $g(x_{0}\cdot Ker(f)) = f(x_0) = y$, and this proves the map is surjective.  Therefore, it is bijective.  Therefore, it is an isomorphism.

Therefore, $A/Ker(f) \cong Im(f)$. $\Box$

Note the first isomorphism theorem, because it is really ridic important.  It says that “modding out” by all the elements that are taken to the identity by our function, we get the image of the function.  For now, let’s stop.  Next post will most likely be the last primer on group theory, and we’ll discuss the other three isomorphism theorems.  After that, we’ll be able to talk about vector spaces a little bit better and we’ll be able to go a bit farther into algebraic topology.