## Friday, June 17, 2005

### Math Post the Sixth: Isomorphism

This is going to verge on the philosophical, since I'll have to justify a "why" inside, but I'll kick off with the answer to the question from last time: describe all the groups of prime order. Start with the hint; pick an element g in a group G of prime order p, and say that g is not the identity. Now, g generates a subgroup, say H, and it has some nonidentity element in it, since g is such an element. Now Lagrange's theorem tells us that the order of H divides the order of G, but the order of G is prime, so H must have order either 1 or p. Since H has at least two elements (the identity and g), H has order p, so H=G. This argument shows that any group of prime order is generated by any element not the identity, has no nontrivial subgroups, and is "structurally the same" as the group where we add hours on a p-hour clock. Now the only issue is what I mean by "structurally the same."

Consider two groups: one is the group S_3 (underscore is ASCII for subscript) of permutations of three elements (i.e. all the moves the three-card-monte-guy can do) and the other is D_3, the rigid symmetries of an equilateral triangle. Both of these groups have six elements, and they have much in common in terms of structure, since they both can achieve any configuration of three things being moved around (you can reflect the triangle on an axis as well as rotate it, and think of it as acting on the corners). I want to say that they're the same, but I can't quite; after all, they're given in different ways, written with different letters, and so on. On the other hand, the situation is the same as if I took a clock and rubbed off all the numbers, replacing them with fruits -- I might now be saying that pear plus strawberrry equals pineapple, but that doesn't stop it from being a clock. So the question is how to capture this notion of "identical except in name."

The first part of the answer starts with the notion of a homomorphism. A homomorphism is a "nice"* function between two groups, and the buzzword is that it "preserves the group structure." Homomorphisms are traditionally written with Greek letters which I'm not sure how to render here, so until I find a better way I'm going to do it with LaTeX (math typesetting) notation, which should be pretty straightforward: a small phi will be written \alpha, a capital one \Alpha, and so on. The symbolic way to write a map \phi from a set G to a set H is like this: \phi : G->H, where the arrow-looking thing is in fact an arrrow. If G and H are groups, the map \phi is said to be a homomorphism if for any g and g' in G, \phi(gg')=\phi(g)\phi(g'). The trick to this simpleminded equation is that the multiplication is carried out in G on the left and H on the right. Now, say we have two homomorphisms which are inverses, say \phi:G->H and \psi:H->G such that doing \psi first then \phi gets you back to where you started in H and doing \phi first then \psi gets you back where you started in G (\phi(\psi(h))=h and \psi(\phi(g))=g for all g in G and h in H); then we can multiply in G by going over to H, multiplying there, and coming back and vice versa. This means that we can think of either G or H as just alternate names for the other group, which tells you that they're really the same.

Before concluding I'll define quickly some relevent terms. A map is said to be one-to-one or injective if no element gets hit twice; symbolically, if f(x)=f(y) implies x=y. For people who remember precalculus, this is the "horizontal line test" for a graph. A map is onto or surjective if everything gets hit. A map which is both injective and surjective is bijective. Bijective maps are invertible**, and bijective homomorphisms have inverses and are called isomorphisms.

To restate the conclusion of the first paragraph in nicer language, we classified all groups of prime order up to isomorphism: a group of order p is isomorphic to a clock arithmetic (or cyclic) group of order p, via the isomorphism defined by taking any nonidentity element to the generator 1.

Next time: what groups are homomorphic images of other groups.

*Practically every definition in math is a definition of "nice," though the connotation that goes with it can be anything from "super duper extra bonus spiffy" to "not something you made up just to annoy me." Most branches of math have a fundamental definition of "nice function" that follows shortly after the definition of the objects under discussion; in most algebraic disciplines what this definition should include is obvious to anybody who's been doing algebra for a while. Geometry and topology have it slightly harder.

**If you need to convince yourself of this, draw two collections of dots and some arrows from one side to the other to make a function (each dot on one side gets exactly one outgoing arrow). Also, there is no short phrase for "one-to-one and onto," however little sense that may seem to make.

Anonymous said...

Isn't the short way to say 'one-to-one and onto' just "bijective"?

Anyhow: I really like your characterization of the different types of "nice".

—AJD

11:21 AM
Anonymous said...

"identical except in name"
I like your 3-dimensional grasp of maths. Regrettably I can be classed as an idiot in this subject so will confess to understanding the "first and crusty layer" of the onion skin and then, only at a distance!
However, I do see a resonance with a subject that I have sought a maths consort with - that of a search algorithm. I have a theory (pet and unproven) which I have loosely termed CRSAlis (for Cohesive Random Search Algorithm)- a read through some of your postings has made me think you would be good to run it past (and run with it if you considered it worthy!). Any interest?
- Andrew T.

7:07 PM