Lesson 30: Homomorphisms: Moving Between Groups

As you may have noticed by now, our discussion of groups has closely paralleled that of sets.  This is hopefully not surprising or confusing, since after all groups are nothing but sets with a very particular and well-defined sense of “extra structure”.  To see how our current discussion has paralleled the earlier one, I’ll just quickly note that we first talked about sets, then gave examples, then talked about subsets, then gave examples.  Similarly, we talked about groups, then gave examples, then talked about subgroups, then gave examples.  To continue with this trend, let us now talk about functions between groups and the special ways that groups can interact with each other, just as we did with sets.  As we’ll continue to see, much of doing abstract mathematics is nothing but finding interesting mathematical structures and then seeing how they interact, and oftentimes these interactions are nothing short of miraculous.  So lest I shoot off into a wandering philosophical tangent about the beauty of math, let’s just dive in to actual math.

On the surface of things it seems like this lesson is completely unnecessary.  After all, we’ve already learned about functions from sets to sets, and groups are nothing but special kinds of sets, and so in principle we’ve already learned about functions from groups to groups.  Thus, writing a lesson about functions from groups to groups might seem like a waste of time.  However, due to the extra structure that we know we have around when we work with groups, there are natural “special functions” that we can define when we know that our domain and codomain are both groups.  Moreover, these “special functions” can’t be defined when we’re only dealing with sets, i.e., without the extra structure provided to us by groups.  In other words, there exists a type of function between groups that is inherently “group-theoretic”.

To make the above paragraph a bit more precise, suppose that we have two groups G and H.  We can then form the set of all functions from G to H, which we’ll denote as S, so that S=\{f:G\rightarrow H\}.  Let me clarify that these are all the usual, set-theoretic functions that we get by simply considering G and H as sets and forgetting about their group structure momentarily.  What I am claiming in the previous paragraph is that once we do recall that G and H are in fact groups, then we can pick out a certain subset of S, i.e. a certain set of “special functions”, in a very natural and profitable way (what I mean by “profitable” here will become clearer as we move through more lessons, but in short “profitability” in math simply means the extent to which an idea lends itself to further study (and referring to this quality of mathematical investigations as “profitability” is by no means standard, so don’t expect to see it in textbooks or in lectures)).

As usual, our general and abstract definitions will be motivated strongly by particular examples, so let me construct a couple examples to illuminate the ideas that we’ll be getting at.  Consider the two groups \mathbb{Z}_8=\{0,1,2,3,4,5,6,7\} and \mathbb{Z}_4=\{0,1,2,3\}, with their group products being addition modulo 8 and modulo 4, respectively.  Let us use S for the name of the set of functions from \mathbb{Z}_8 to \mathbb{Z}_4, as we did above for the groups G and H.  The set S will be large, as there are many functions from \mathbb{Z}_8 to \mathbb{Z}_4.  In fact, we can calculate exactly how many there are, so let’s do this very quickly just for fun.  We need to send each of the 8 elements in \mathbb{Z}_8 to one of the 4 elements in \mathbb{Z}_4.  This means that we get 4 options for each of the 8 elements in the domain, and we note that where we send one element is completely independent of where we send any of the other elements.  We also note that each different choice for any of the 8 elements in the domain corresponds to a different function.  Thus, since we get four options for where to send 0 (4 options so far), and for each of those options we get four more options for where to send 1 (4\times 4 options so far), and for each of those options we get four more options for where to send 2 (4\times 4\times 4 options so far), and for each of those options we get four more options for where to send 3 (4\times 4\times 4\times 4 options so far), and for each …(continue in this way)… we get four more options for where to send 7, we find ourselves with a total of 4^8=65,536 distinct choices—i.e., distinct functions.  That’s a lot of functions.

There are, however, a few functions within this gigantic collection of functions that stand out as being special in a very particular way.  But before we find these special functions, we have to try to imagine what we might possibly even mean by a function being “special” in the first place.  All we have are two groups and a function between them, so what possible questions might we ask about this setup whose possible positive or negative answer may motivate us to deem certain functions “special”?  Well, after enough thought we find that there really only is one natural question to ask, and that is about how the function “preserves” the structure of the two groups involved.  Namely, the only thing that is different now than in the case of a function between two boring sets is that we can now combine elements in the domain to get another element in the domain, and we can also combine elements in the codomain to get another element in the codomain.  We can then use the function that we have at our disposal to map elements from one group to another.  It then becomes clear that what we want to do is ask how the process of sending elements in one group to another (using the function) interacts with the process of combining elements within the respective groups (using the respective group multiplications).

In particular, there really is only one question that we can ask.  Unfortunately, I can’t think of a succinct way to ask it, even though the ideas involved are simple.  Thus, I’ll state the question in the next sentence, and it will be extremely wordy, but fear not, we’ll spend the rest of this and the next lesson clarifying and answering it.  So here it is: is it the case that combining two elements in the domain (using the domain’s group multiplication) and then sending this product over to the codomain (using the function) gives the same element (in the codomain) as first sending the two elements in the domain over to the codomain (using the function) and then combining them in the codomain (using the codomain’s group multiplication)?  Whoa, that sentence may need a re-reading or two (or maybe it doesn’t).  These words can be manifested with mathematical notation in various ways, and some may be more enlightening than others depending on one’s temperament.  We’ll explore a couple different ways in this and the next couple of lessons.

Let’s go back to the case where we have two groups G and H and a function f from G to H (i.e., f:G\rightarrow H).  Let’s now break apart and analyze each step in the question that we asked in the previous paragraph.  We’re first asking about the product of two elements in the domain, which in this case is G.  Thus, if we let a and b be two elements in G, then we’re asking about the product a\cdot b\in G (where we’re using the “\cdot” symbol as the group product, and we won’t use a different symbol for the group product in H even though we recall that the two groups don’t necessarily have to have the same group product (but we also recall that this is an abuse of notation that we like to use and have used before)).  We then want to know where the element a\cdot b in G is sent to in H under the function f, so we’re asking about the element f(a\cdot b)\in H.  Now, in the second half of our question we’re asking about where each individual element a and b are sent to in H, so we’re asking about the two elements f(a) and f(b) in H.  We then ask about what happens when we combine them in H, so that we’re asking about the element f(a)\cdot f(b)\in H (note the abuse of notation: this “\cdot” symbol is the group product in H (!!) and we’re just using the same notation for it because we’re lazy).  The question in the previous paragraph is then asking whether or not the process of “combining then sending” is the same as the process of “sending then combining”.  Thus, what we’re asking is whether or not f(a\cdot b)=f(a)\cdot f(b) for all a,b\in G.  Purely in symbols, this question is phrased as

f(a\cdot b)\stackrel{?}{=} f(a)\cdot f(b)\ \ \forall a,b\in G.

This is a helpful way of manifesting our question using mathematical symbols because it tells us exactly what we need to calculate in order to answer the question.  There is a cooler way to phrase the question in terms of symbols, but we’ll save this for the next lesson.  For now, let’s see how the above expression applies to our example of \mathbb{Z}_8 and \mathbb{Z}_4 lest we get bogged down in abstract nonsense.

Let’s first define the function f_1:\mathbb{Z}_8\rightarrow \mathbb{Z}_4 to be the function that sends all elements except the number 1 in \mathbb{Z}_8 to 0\in \mathbb{Z}_4, and sends 1\in \mathbb{Z}_8 to 1\in \mathbb{Z}_4.  In other words, f(1)=1 and f_1(a)=0 \ \ \forall a\in \mathbb{Z}_8 such that a\neq 1.  This is depicted in figure 1, with \mathbb{Z}_8 on the left and \mathbb{Z}_4 on the right.

function1

figure 1

We can then ask the question that we asked above: does combining and then sending always give the same result as sending then combining?

The answer for f_1 defined above is no, which we can easily check.  For example, let’s say we considered the case where a=b=1.  Then a\cdot b=1+1=2 in \mathbb{Z}_8, and so f_1(a\cdot b)=f_1(2)=0 from our definition of f_1.  However, if we first send 1 over to \mathbb{Z}_4 using f_1, we land at 1 again (only now in \mathbb{Z}_4), so that f_1(1)=1, and so that we have f_1(a)\cdot f_1(b)=f_1(1)\cdot f_1(1)=1\cdot 1=1+1=2 in \mathbb{Z}_4.  However, 0\neq 2, so that f(1\cdot 1)\neq f(1)\cdot f(1), and we’ve therefore found one choice of a,b\in \mathbb{Z}_8 such that the answer to the question

f_1(a\cdot b)\stackrel{?}{=} f_1(a)\cdot f_1(b)

is no.  This then means that the answer to our original question is no, since the original question is simply whether or not f_1(a\cdot b)=f_1(a)\cdot f_1(b) for any choice of a,b\in \mathbb{Z}_8.

Let us now find a function that does satisfy the above requirement to show that a) such functions do exist and consequently that b) they are indeed special.  Let’s define the function f (no subscript) from \mathbb{Z}_8 to \mathbb{Z}_4 to be the function that takes odd numbers in \mathbb{Z}_8 to 2\in \mathbb{Z}_4, and even numbers in \mathbb{Z}_8 to 0\in \mathbb{Z}_4.  In other words, f(1)=f(3)=f(5)=f(7)=2\in \mathbb{Z}_4 and f(0)=f(2)=f(4)=f(6)=0\in \mathbb{Z}_4.  This is depicted in figure 2.

figure 2

figure 2

I now want to show that for any choice of elements a,b\in \mathbb{Z}_8, we’ll have that f(a\cdot b)=f(a)\cdot f(b).  I could do this a couple of ways.  First, I could explicitly calculate out every possible pair, i.e. every choice of a and b.  However, there are a lot of choices and I’m lazy.  A better way would be to calculate a couple explicit examples, make sure they work, and then look for a better way to do things more abstractly.  Let’s start with the particular examples.  Consider the choice a=1 and b=2.  Then a\cdot b=1+2=3\in \mathbb{Z}_8 so that f(a\cdot b)=f(1\cdot 2)=f(1+2)=f(3)=2\in \mathbb{Z}_4, where in the last equality we simply used the definition of f.  Similarly, f(1)=2\in \mathbb{Z}_4 and f(2)=0\in \mathbb{Z}_4, so that f(a)\cdot f(b)=f(1)\cdot f(2)=2+0=2\in \mathbb{Z}_4, so that f(1\cdot 3)=f(1)\cdot f(3), which is a good start.

Let’s do one more example.  Choose a=b=5\in \mathbb{Z}_8.  Then a\cdot b=5+5=2\in \mathbb{Z}_8, so f(5\cdot 5)=f(2)=0\in \mathbb{Z}_4.  Similarly, f(5)=2 so that f(5)\cdot f(5)=2+2=0\in \mathbb{Z}_4, so that again we have f(5\cdot 5)=f(5)\cdot f(5), which is still in line with my claim.

Now let’s see if we can prove this in general, and if we can do so quickly.  We first notice that each choice of a and b that we make will land itself in three categories: either i) both a and b are even, ii) they are both odd, or iii) one is even and one is odd.  If we can prove that the condition we’re after holds for each of these three cases, we’ll be done.

Let’s start with case i).  If both a and b are even, then a\cdot b will also be even, since the group product is just addition and the sum of even things is even.  Thus, f(a\cdot b)=0 in this case, since f is defined to send even numbers to 0.  But we also know that f(a)=f(b)=0 when a and b are even, by definition of f.  Since 0\cdot 0=0, we have that f(a\cdot b)=0=0\cdot 0=f(a)\cdot f(b), which is what we wanted to show.  Thus we’ve proven case i).

Let’s now go to case ii).  If both a and b are odd, then a\cdot b is even since “odd plus odd equals even”.  Thus, f(a\cdot b)=0 by definition of f.  Additionally, since a and b are both odd, f(a)=f(b)=2, so that f(a)\cdot f(b)=2+2=0\in \mathbb{Z}_4.  Thus again we have f(a\cdot b)=f(a)\cdot f(b), as desired.

Let’s now go to case iii).  Without loss of generality we can assume that a is the odd one and b is the even one (otherwise we can simply rename what we call a and b).  Then a\cdot b is also odd, since an odd plus an even is odd, so that f(a\cdot b)=2\in \mathbb{Z}_4.  Additionally, f(a)=2 since a is odd, and f(b)=0 since b is even.  Thus, f(a)\cdot f(b)=2+0=2, so that alas we have f(a\cdot b)=2=f(a)\cdot f(b).

We’ve therefore established the fact that f(a\cdot b)=f(a)\cdot f(b) in each of the three cases, and therefore for all possible cases, and thus we’ve proved that the f that we’ve defined is the kind of “special” that we’re after.

We’re now in a position to end this lesson, and we’ll do so by giving a name to these special functions from groups to groups.  It is important to at least take a look at the exercises and solutions to this lesson (even if you don’t do them yourselves), since they’ll help us get comfortable with this new definition as well as with the process of defining our own mathematical objects.

Definition 30.1 Let G and H be groups, and let f be a function from G to H, i.e. f:G\rightarrow H.  If f has the special property that, for all a,b\in G it is true that f(a\cdot b)=f(a)\cdot f(b), then f is called a homomorphism.\\

Let us make a few quick comments before heading to the exercises.  First, let’s abandon our middle school immaturity and give no special attention to the fact that the word “homo” is in this definition (I’ve taught this material to high school students and unfortunately this was an issue).  We’re mathematicians now and any possible humor that one might find in the above definition is counterproductive at best and hateful at worst.  Second, let me note that we have included the aforementioned abuse of notation regarding the fact that the same “\cdot” symbol is used for group multiplication both in G and in H.  I won’t apologize for that, but rather simply note it and count on our ability to remember it and adjust our mathematical behavior accordingly whenever the appropriate time arises.  Finally, let me note the logic behind this definition.  Namely, we are supposing that the enemy hands us two groups and a function from one to the other.  We now suppose that we want to ask whether or not this function is a homomorphism.  To answer this question, we simply take any possible pair of elements in the domain (including the possibility of choosing the same element twice) and compose them in the domain, then send this product (a single element) over to the codomain.  We then go back to the pair of elements that we chose in the domain and first use the function to send them both over to the codomain.  We then combine these two elements (possibly the same) in the codomain.  We’ve now landed on two (possibly different) elements in the codomain via two different avenues: “combing then sending” and “sending then combining”.  If, no matter which pair we begin with in the domain, the results of these two processes are always the same, then the function the enemy handed us is a homomorphism.  If, however, there is (at least) one pair of elements in the codomain for which these two processes give two different elements in the codomain, then the function the enemy handed us is indeed not a homomorphism.  Let’s see some examples in the exercises.

Exercises:

1) Define a homomorphism from \mathbb{Z}_8 to \mathbb{Z}_4, different from that defined in the lesson.

2) Define a homomorphism from \mathbb{Z} to \mathbb{Z} (i.e., to itself).

Solutions to Exercises

On to Lesson 31

Back to Lesson 29

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s