﻿ ﻿ISOMORPHISM - A Book of Abstract Algebra

## A Book of Abstract Algebra, Second Edition (1982)

### Chapter 9. ISOMORPHISM

Human perception, as well as the “perception” of so-called intelligent machines, is based on the ability to recognize the same structure in different guises. It is the faculty for discerning, in different objects, the same relationships between their parts.

The dictionary tells us that two things are “isomorphic” if they have the same structure. The notion of isomorphism—of having the same structure—is central to every branch of mathematics and permeates all of abstract reasoning. It is an expression of the simple fact that objects may be different in substance but identical in form.

In geometry there are several kinds of isomorphism, the simplest being congruence and similarity. Two geometric figures are congruent if there exists a plane motion which makes one figure coincide with the other; they are similar if there exists a transformation of the plane, magnifying or shrinking lengths in a fixed ratio, which (again) makes one figure coincide with the other. We do not even need to venture into mathematics to meet some simple examples of isomorphism. For instance, the two palindromes are different, but obviously isomorphic; indeed, the first one coincides with the second if we replace M by R, A by O, and D by T.

Here is an example from applied mathematics: A flow network is a set of points, with arrows joining some of the points. Such networks are used to represent flows of cash or goods, channels of communication, electric circuits, and so on. The flow networks (A) and (B), below, are different, but can be shown to be isomorphic. Indeed, (A) can be made to coincide with (B) if we superimpose point 1 on point 6, point 2 on point 5, point 3 on point 8, and point 4 on point 7. (A) and (B) then coincide in the sense of having the same points joined by arrows in the same direction. Thus, network (A) is transformed into network (B) if we replace points 1 by 6, 2 by 5, 3 by 8, and 4 by 7. The one-to-one correspondence which carries out this transformation, namely,  is called an isomorphism from network (A) to network (B), for it transforms (A) into (B).

Incidentally, the one-to-one correspondence is an isomorphism between the two palindromes of the preceding example, for it transforms the first palindrome into the second.

Our next and final example is from algebra. Consider the two groups G1 and G2 described below: Table of G1 Table of G2 G1 and G2 are different, but isomorphic. Indeed, if in G1 we replace 0 by e, 1 by a, and 2 by b, then G1 coincides with G2, the table of G1 being transformed into the table of G2. In other words, the one-to-one correspondence transforms G1 to G2. It is called an isomorphism from G1 to G2. Finally, because there exists an isomorphism from G1 to G2, G1 and G2 are isomorphic to each other.

In general, by an isomorphism between two groups we mean a one-to-one correspondence between them which transforms one of the groups into the other. If there exists an isomorphism from one of the groups to the other, we say they are isomorphic. Let us be more specific:

If G1 and G2 are any groups, an isomorphism from G1 to G2 is a one-to-one correspondence f from G1 to G2 with the following property: For every pair of elements a and b in G1,

If f(a) = a′ and f(b) = b′ then f(ab) = ab′ (1)

In other words, if/matches a with a′ and b with b′ it must match ab with ab′. It is easy to see that if /has this property it transforms the table of G1 into the table of G2: There is another, equivalent way of looking at this situation: If two groups G1 and G2 are isomorphic, we can say the two groups are actually the same, except that the elements of G1 have different names from the elements of G2. G1 becomes exactly G2 if we rename its elements. The function which does the renaming is an isomorphism from G1 to G2. Thus, in our last example, if 0 is renamed e, 1 is renamed a, and 2 is renamed 6, G1 becomes exactly G2, with the same table. (Note that we have also renamed the operation: it was called + in G1 and · in G2.)

By the way, property (1) may be written more concisely as follows:

f(ab) = f(a)f(b) (2)

So we may sum up our definition of isomorphism in the following way:

Definition Let G1 and G2 be groups. A bijective function f : G1G2 with the property that for any two elements a and b in G1,

f(ab) = f(a)f(b) (2)

is called an isomorphism from G1 to G2.

If there exists an isomorphism from G1 to G2, we say that G1 is isomorphic to G2.

If there exists an isomorphism f from G1 to G2, in other words, if G1 is isomorphic to G2, we symbolize this fact by writing

G1G2

to be read, “G1 is isomorphic to G2.”

How does one recognize if two groups are isomorphic? This is an important question, and not quite so easy to answer as it may appear. There is no way of spontaneously recognizing whether two groups G1 and G2 are isomorphic. Rather, the groups must be carefully tested according to the above definition.

G1 and G2 are isomorphic if there exists an isomorphism from G1 to G2. Therefore, the burden of proof is upon us to find an isomorphism from G1 to G2, and show that it is an isomorphism. In other words, we must go through the following steps:

1.Make an educated guess, and come up with a function f : G1 G2 which looks as though it might be an isomorphism.

2.Check that f is injective and surjective (hence bijective).

3.Check that f satisfies the identity

f(ab) = f(a)f(b)

Here’s an example: is the group of the real numbers with the operation of addition. pos is the group of the positive real numbers with the operation of multiplication. It is an interesting fact that and pos are isomorphic. To see this, let us go through the steps outlined above:

1.The educated guess: The exponential function f(x) = ex is a function from to pos which, if we recall its properties, might do the trick.

2.f is injective: Indeed, if f(a) = f(b), that is, ea = eb, then, taking the natural log on both sides, we get a = b.

f is surjective: Indeed, if y ∈ pos, that is, if y is any positive real number, then y = eln y = f(ln y); thus, y = f(x) for x = ln y.

3.It is well known that ea+b = ea · eb, that is,

f(a + b) = f(a) · f(b)

Incidentally, note carefully that the operation of is +, whereas the operation of pos is ·. That is the reason we have to use + on the left side of the preceding equation, and · on the right side of the equation.

How does one recognize when two groups are not isomorphic? In practice it is usually easier to show that two groups are not isomorphic than to show they are. Remember that if two groups are isomorphic they are replicas of each other; their elements (and their operation) may be named differently, but in all other respects they are the same and share the same properties. Thus, if a group G1 has a property which group G2 does not have (or vice versa), they are not isomorphic! Here are some examples of properties to look out for:

1.Perhaps G1 is commutative, and G2 is not.

2.Perhaps G1 has an element which is its own inverse, and G2 does not.

3.Perhaps G1 is generated by two elements, whereas G2 is not generated by any choice of two of its elements.

4.Perhaps every element of G1 is the square of an element of G1, whereas G2 does not have this property.

This list is by no means exhaustive; it merely illustrates the kind of things to be on the lookout for. Incidentally, the kind of properties to watch for are properties which do not depend merely on the names assigned to individual elements; for instance, in our last example, 0 ∈ G1 and 0 ∉ G2, but nevertheless G1 and G2 are isomorphic.

Finally, let us state the obvious: if G1 and G2 cannot be put in one-to-one correspondence (say, G1 has more elements that G2), clearly they cannot be isomorphic.

In the early days of modern algebra the word “group” had a different meaning from the meaning it has today. In those days a group always meant a group of permutations. The only groups mathematicians used were groups whose elements were permutations of some fixed set and whose operation was composition.

There is something comforting about working with tangible, concrete things, such as groups of permutations of a set. At all times we have a clear picture of what it is we are working with. Later, as the axiomatic method reshaped algebra, a group came to mean any set with any associative operation having a neutral element and allowing each element an inverse. The new notion of group pleases mathematicans because it is simpler and more lean and sparing than the old notion of groups of permutations; it is also more general because it allows many new things to be groups which are not groups of permutations. However, it is harder to visualize, precisely because so many different things can be groups.

It was therefore a great revelation when, about 100 years ago, Arthur Cayley discovered that every group is isomorphic to a group of permutations. Roughly, this means that the groups of permutations are actually all the groups there are! Every group is (or is a carbon copy of) a group of permutations. This great result is a classic theorem of modern algebra. As a bonanza, its proof is not very difficult.

Cayley’s Theorem Every group is isomorphic to a group of permutations.

PROOF: Let G be a group; we wish to show that G is isomorphic to a group of permutations. The first question to ask is, “What group of permutations? Permutations of what set?” (After all, every permutation must be a permutation of some fixed set.) Well, the one set we have at hand is the set G, so we had better fix our attention on permutations of G. The way we match up elements of G with permutations of G is quite interesting:

With each element a in G we associate a function πa : GG defined by

πa(x) = ax

In other words, πa is the function whose rule may be described by the words “multiply on the left by a,” We will now show that πa is a permutation of G:

1.πa is injective: Indeed, if πa(x1) = πa(x2), then ax1 = ax2, so by the cancellation law, x1 = x2.

2.πa is surjective: For if yG, then y = a(a1 y) = πa(a1 y). Thus, each y in G is equal to πa(x) for x = a1 y.

3.Since πa is an injective and surjective function from G to G, πa is a permutation of G.

Let us remember that we have a permutation πa for each element a in G; for example, if b and c are other elements in G, πb is the permutation “multiply on the left by b,” πc is the permutation “multiply on the left by c,” and so on. In general, let G* denote the set of all the permutations πa as a ranges over all the elements of G:

G* = {πa : aG}

Observe now that G* is a set consisting of permutations of G—but not necessarily all the permutations of G. In Chapter 7 we used the symbol SG to designate the group of all the permutations of G. We must show now that G* is a subgroup of SG, for that will prove that G* is a group of permutations.

To prove that G* is a subgroup of SG, we must show that G* is closed with respect to composition, and closed with respect to inverses. That is, we must show that if πa and πb are any elements of G*, their composite πaπb is also in G*; and if πa is any element of G*, its inverse is in G*.

First, we claim that if a and b are any elements of G, then

πaπb = πab (3)

To show that πaπb and πab are the same, we must show that they have the same effect on every element x: that is, we must prove the identity [πaπb](x) = πab(x). Well, [πaπb](x) = πa(πb(x)) = πa(bx) = a(bx) = (ab)x = πab(x). Thus, πaπb = πab; this proves that the composite of any two members Za and πb of G* is another member πab of G*. Thus, G* is closed with respect to composition.

It is each to see that πe is the identity function: indeed,

πe(x) = ex = x

In other words, πe is the identity element of SG.

Finally, by Equation (3),

πaπa − 1 = πaa − 1 = πe

So by Theorem 2 of Chapter 4, the inverse of πa is πa1. This proves that the inverse of any member πa of G* is another member πa1 of G*. Thus, G* is closed with respect to inverses.

Since G* is closed with respect to composition and inverses, G* is a subgroup of SG.

We are now in the final lap of our proof. We have a group of permutations G*, and it remains only to show that G is isomorphic to G*. To do this, we must find an isomorphism f : GG*. Let f be the function

f(a) = πa

In other words, f matches each element a in G with the permutation πa in G*. We can quickly show that f is an isomorphism:

1.f is injective: Indeed, if f(a) = f(b) then πa = πb. Thus, πa(e) = πb(e), that is, ae = be, so, finally, a = b.

2.f is surjective: Indeed, every element of G* is some πa, and πa = f(a).

3.Lastly, f(ab) = πab = πaπb = f(a) ∘ f(b).

Thus, f is an isomorphism, and so GG*. ■

EXERCISES

A. Isomorphism Is an Equivalence Relation among Groups

The following three facts about isomorphism are true for all groups:

(i) Every group is isomorphic to itself.

(ii) If G1G2, then G2G1.

(iii) If G1G2 and G2G3, then G1 ≅ G3.

Fact (i) asserts that for any group G, there exists an isomorphism from G to G.

Fact (ii) asserts that, if there is an isomorphism f from G1 to G2, there must be some isomorphism from G2 to G1. Well, the inverse of f is such an isomorphism.

Fact (iii) asserts that, if there are isomorphisms f : G1G2 and g : G2G3, there must be an isomorphism from G1 to G3. One can easily guess that gf is such an isomorphism. The details of facts (i), (ii), and (iii) are left as exercises.

1 Let G be any group. If ε : GG is the identity function, ε(x) = x, show that ε is an isomorphism.

2 Let G1 and G2 be groups, and f : G1G2 an isomorphism. Show that f1: G2G1 is an isomorphism. [HINT: Review the discussion of inverse functions at the end of Chapter 6. Then, for arbitrary elements c, dG2, there exist a, bG1, such that c = f(a) and d = f(b). Note that a = f1(c) and b = f1(d). Show that f1(cd) = f1(c)f1(d).]

3 Let G1, G2, and G3 be groups, and let f: G1G2 and g : G2G3 be isomorphisms. Prove that gf : G1G3 is an isomorphism.

B. Elements Which Correspond under an Isomorphism

Recall that an isomorphism f from G1 to G2 is a one-to-one correspondence between G1 and G2 satisfying f(ab) = f(a)f(b). f matches every element of Gl with a corresponding element of G2. It is important to note that:

(i)f matches the neutral element of G1 with the neutral element of G2.

(ii)If f matches an element x in G1 with y in G2, then, necessarily, f matches xl with y1 That is, if xy, then xly1.

(iii)f matches a generator of G1 with a generator of G2. The details of these statements are now left as an exercise. Let G1 and G2 be groups, and let f : G1G2 be an isomorphism.

1 If e1 denotes the neutral element of G1 and e2 denotes the neutral element of G2, prove that f(e1) = e2. [HINT: In any group, there is exactly one neutral element; show that f(e1) is the neutral element of G2.]

2 Prove that for each element a in G1 f(al) = [f(a)]1. (HINT: You may use Theorem 2 of Chapter 4.)

3 If G1 is a cyclic group with generator a, prove that G2 is also a cyclic group, with generator f(a).

C. Isomorphism of Some Finite Groups

In each of the following, G and H are finite groups. Determine whether or not GH. Prove your answer in either case.

To find an isomorphism from G to H will require a little ingenuity. For example, if G and H are cyclic groups, it is clear that we must match a generator a of G with a generator b of H; that is, f(a) = b. Then f(aa) = bb, f(aaa) = bbb, and so on. If G and H are not cyclic, we have other ways: for example, if G has an element which is its own inverse, it must be matched with an element of H having the same property. Often, the specifics of a problem will suggest an isomorphism, if we keep our eyes open.

To prove that a specific one-to-one correspondence f : GH is an isomorphism, we may check that it transforms the table of G into the table of H.

# 1 G is the checkerboard game group of Chapter 3, Exercise D. H is the group of the complex numbers {i, −i, 1, −1} under multiplication.

2 G is the same as in part 1. H = 4.

3 G is the group P2 of subsets of a two-element set. (See Chapter 3, Exercise C.) H is as in part 1.

# 4 G is S3, H is the group of matrices described on page 28 of the text.

5 G is the coin game group of Chapter 3, Exercise E. H is D4, the group of symmetries of the square.

6 G is the group of symmetries of the rectangle. H is as in part 1.

D. Separating Groups into Isomorphism Classes

Each of the following is a set of four groups. In each set, determine which groups are isomorphic to which others. Prove your answers, and use Exercise A3 where convenient.

1 4 2 × 2 P2 V

[P2 denotes the group of subsets of a two-element set. (See Chapter 3, Exercise C.) V denotes the group of the four complex numbers {i, −i, 1, −1} with respect to multiplication.]

2 S3 6 3 × 2 ( denotes the group {1,2,3,4,5,6} with multiplication modulo 7. The product modulo 7 of a and b is the remainder of ab after division by 7.)

3 8 P3 2 × 2 × 2 D4

(D4 is the group of symmetries of the square.)

4 The groups having the following Cayley diagrams: E. Isomorphism of Infinite Groups

# 1 Let E designate the group of all the even integers, with respect to addition. Prove that E.

2 Let G be the group {10n : n } with respect to multiplication. Prove that G . (Remember that the operation of is addition.)

3 Prove that = × .

4 We have seen in the text that is isomorphic to pos. Prove that is not isomorphic to * (the multiplicative group of the nonzero real numbers). (HINT: Consider the properties of the number −1 in *. Does have any element with those properties?)

5 Prove that is not isomorphic to .

6 We have seen that  pos. However, prove that is not isomorphic to pos. ( pos is the multiplicative group of positive rational numbers.)

F. Isomorphism of Groups Given by Generators and Defining Equations

If a group G is generated, say, by a, b, and c, then a set of equations involving a, b, and c is called a set of defining equations for G if these equations completely determine the table of G. (See end of Chapter 5.) If G′ is another group, generated by elements a′, b′, and c′ satisfying the same defining equations as a, b, and c, then G′ has the same table as G (because the tables of G and G′ are completely determined by the defining equations, which are the same for G as for G′).

Consequently, if we know generators and defining equations for two groups G and G′, and if we are able to match the generators of G with those of G′ so that the defining equations are the same, we may conclude that GG′.

Prove that the following pairs of groups G, G′ are isomorphic.

# 1 G = the subgroup of S4 generated by (24) and (1234); G′ = {e, a, b, b2, b3, ab, ab2, ab3} where a2 = e, b4 = e, and ba = ab3.

2 G = S3; G′ = {e, a, b, ab, aba, abab} where a2 = e, b2 = e, and bab = aba.

3 G = D4; G′ = {e, a, b, ab, aba, (ab)2, ba, bab} where a2 = b2 = e and (ab)4 = e.

4 G = 2 × 2 × 2; G′ = {e, a, b, c, ab, ac, bc, abc} where a2 = b2 = c2 = e and (ab)2 = (bc)2 = (ac)2 = e.

G. Isomorphic Groups on the Set 1 G is the set {x : x ≠ −1} with the operation x * y = x + y + xy. Show that f(x) = x − 1 is an isomorphism from * to G. Thus, * ≅ G.

2 G is the set of the real numbers with the operation x * y = x + y + l. Find an isomorphism f : G and show that it is an isomorphism.

3 G is the set of the nonzero real numbers with the operation x * y = xy/2. Find an isomorphism from * to G.

4 Show that f(x, y) = (−1)y x is an isomorphism from pos × 2 to *. (REMARK: To combine elements of pos × 2, one multiplies first components, adds second components.) Conclude that * ≅ pos × 2.

H. Some General Properties of Isomorphism

1 Let G and H be groups. Prove that G × HH × G.

# 2 If G1G2 and H1H2, then G1 × H1G2 × H2.

3 Let G be any group. Prove that G is abelian iff the function f(x) = x1 is an isomorphism from G to G.

4 Let G be any group, with its operation denoted multiplicatively. Let H be a group with the same set as G and let its operation be defined by x * y = y · x (where · is the operation of G). Prove that GH.

5 Let c be a fixed element of G. Let H be a group with the same set as G, and with the operation x * y = xcy. Prove that the function f(x) = clx is an isomorphism from G to H.

I. Group Automorphisms

If G is a group, an automorphism of G is an isomorphism from G to G. We have seen (Exercise A1) that the identity function ε(x) = x is an automorphism of G. However, many groups have other automorphisms besides this obvious one.

1 Verify that is an automorphism of 6.

2 Verify that and are all automorphisms of 5.

3 If G is any group, and a is any element of G, prove that f(x) = axa’1 is an automorphism of G.

4 Since each automorphism of G is a bijective function from G to G, it is a permutation of G. Prove the set

Aut(G)

of all the automorphisms of G is a subgroup of SG. (Remember that the operation is composition.)

J. Regular Representation of Groups

By Cayley’s theorem, every group G is isomorphic to a group G* of permutations of G. Recall that we match each element a in G with the permutation πa defined by πa = ax, that is, the rule “multiply on the left by a.” We let G* = {πa : aG}; with the operation ∘ of composition it is a group of permutations, called the left regular representation of G. (It is called a “representation” of G because it is isomorphic to G.)

Instead of using the permutations πa, we could just as well have used the permutations ρa defined by ρa(x) = xa, that is, “multiply on the right by a.” The group Gρ = {ρa: aG} is called the right regular representation of G.

If G is commutative, there is no difference between right and left multiplication, so G* and Gρ are the same, and are simply called the regular representation of G. Also, if the operation of G is denoted by +, the permutation corresponding to a is “add a” instead of “multiply by a.”

Example The regular representation of 3 consists of the following permutations: The regular representation of 3 has the following table: The function is easily seen to be an isomorphism from 3 to its regular representation.

Find the right and left regular representation of each of the following groups, and compute their tables. (If the group is abelian, find its regular representation.)

1 P2, the group of subsets of a two-element set. (See Chapter 3, Exercise C.)

2 4.

3 The group G of matrices described on page 28 of the text.

﻿