No account? Create an account ewin
31 March 2009 @ 10:43 pm
Homomorphisms

Caveat emptor.  I am not a licensed practitioner of abstract algebra.

Let's start with one of the constructs of abstract algebra:  the semigroup.  A semigroup is nothing more than a set closed under an associative binary operation.

Yeah, that's pretty much what I said, too.  Let's break it down:

First of all, a semigroup is a set.  That means it's a group of numbers, usually expressed as follows:
S = {A, B, C}

In this case, our semigroup, named S, contains the numbers A, B, and C.  It's considered utterly tasteless to use actual numbers in abstract algebra.  You lose many coolness points if you let a number creep in anywhere.  Just let A, B, and C be "numbers" *nudge nudge wink wink*.  In fact, we don't even call them numbers... since they're in a set, we call them elements.

A binary operation is some unspecified mathematical operator such as times, addition, multiplication, etc. between two elements.  Again, being too specific is SO uncool.  So instead of saying A x B, we use symbols to indicate these operators... so you get happy fun things like A ◊ B, or A • B, or A ♥ B.  A * B is a fantastic one, because I don't have to use an html code to type it.  Just remember:  it doesn't matter what the operation is.  It's just Bob the Operator.

So our set S is closed under one of those binary operations, say * (which is pronounced "bob") .  What that means is, if you take any two elements from A, B, and C, and use that operation to make them into an equation, the result of the equation will be A, B, or C.  In other words, any way you use that operator, you still stay inside the set.  Let's say that the following applies:

A * A = A
A * B = B
A * C = C
B * A = B
B * B = C
B * C = A
C * A = C
C * B = A
C * C = B

Everything on the left sides of the equations is an element of the set.  Everything on the right side of the equations is an element of the set.  Therefore, the set is "closed" under the operation * .  So in the above, S is closed under bob.  A closed set is often written like this:  (S,*) .

Those of you who are actually paying attention will note that A * B ≠ B * A .  But but but...
No, this is not algebra.  This is abstract algebra.  There's no law that A bob B has to equal B bob A.  And there's no crying in abstract algebra.

(It was pointed out to me by the illustrious that the above example is, in fact, commutative. Oops. My bad. But bear in mind: semigroups do not HAVE to be commutative.)

If you think way back to gradeschool, you may remember the term "commutative".  Addition and multiplication are commutative, that means that x + y = y + x, and xy = yx.  Remember how stupid that seemed, the first time you learned it?  How fargin' obvious it was?  Well, it's only obvious in algebra.  It is not necessary that an operation on a semigroup be commutative, and in the above example, it's not.

If you think way back again and if you just went back and re-read the description of a semigroup again, you'll remember another word:  "associative".  Associative operations, if you recall way back when you learned about them, were even stupider than commutative ones.  Basically, associative means you can move parentheses around.  I.e., (a + b) + c = a + (b + c), and (xy)z = x(yz) .

Now, while the above operation * is not commutative, it IS associative.
For example, using the equations above given for the set (and NO OTHER MATHEMATICAL RULES WHATSOEVER, trust me, JUST USE THE EQUATIONS ABOVE):

(A * B) * C = B * C = A
A * (B * C) = A * A = A

Note how even when you move the parentheses around, the result stays the same.  You can try that on any combination of the three elements above and it will work; this is a set that was given to us in class as an example of an associative set.  I should note that figuring out whether a set is fully associative under a particular operation is a long and painful business (the above set would take 27 equations to prove associativity), and these days, we let computers do it.  Yay, computers.

So if you've gotten this far, I can repeat:  A semigroup is nothing more than a set closed under an associative binary operation.

Now let's talk about functions.  If you're anything like me, you hate functions.

A function is a type of expression that maps an element of one set to an element of another set.  So for instance, say you have the set of Real numbers, and on the other hand, you have the set of Real numbers again.  If f(x) = x³ then f maps the number 2 on one side to the number 8 on the other side, because f(2) = 2³ = 8 .

Frequently in higher level mathematics, you don't even get a function.  You just get the letter "f" which means "this is some function we don't really need to define explicitly because if you've gotten this far in mathematics, you know that specificity of numbers and equations is for weenies".  And you don't get anything so concrete as the set of Real numbers; instead, you get some set A.  Or some set B.  Or some set A and B, with f mapping A to B, complete with a sketch of A and B as amorphous blobs and f labelling a little arrow that goes from A blob to B blob.  These sketches are highly informative.  They're so useful, in fact, that I won't bother to provide one.  Just picture it:  a blob, another blob, and a little arrow pointing from one to the other.  There.  You have experienced half of my math class this semester.

There are some special properties of functions that you've heard me blab about on here before.  One of them is "well-defined" -- if a function is well-defined, it will map each element in A to only one element in B.  One of them is "one-to-one" -- if a function is one-to-one, there will only be one element in A that maps to each element in B (it's really just the reverse of well-defined).  And if a function is onto, that means no element in B is left out; all of them have some element in A that maps to them.

There are lots of these little rules, and they let you prove specific things about functions.

So you have your function f, and two sets A and B.  What if those sets are semigroups?  (Why, that would mean that those sets are each closed under some binary bob.)

Let's say we have semigroup A, which is closed under *.  And then we have semigroup B, which is closed under •.  f is some function that maps A to B.  (Picture those blobs, now.  Particularly blob A, which is a closed blob on bob.)

A has lots of elements in it.  Let's pick out two of them and name them a1 and a2.  (Note:  A is closed under *, so a1 * a2 is going to end up being some element in A.)

B likewise, so let's pick out two elements from it and name them b1 and b2.  (Note:  B is closed under •, so b1 • b2 is going to end up being some element in B.)

We'll say the following is true:
f(a1) = b1
f(a2) = b2

If this is also true:
f(a1 * a2) = f(b1) • f(b2)

Then f is a homomorphism.

It's not entirely unlike an equivalence.  What it is is just another little rule about functions, that happens to apply to groups in abstract algebra.  "Say f is a homomorphism", we can prove all kinds of things.

We should also note here that what I've just given you is the definition of a particular kind of homomorphism, that is, a "group homomorphism".  It works on groups!  Here, it happens to work on semigroups.  Wikipedia has a nice sketch of it here:  http://en.wikipedia.org/wiki/Group_homomorphism

I should also note that our prof made it quite clear to us that a semigroup is not quite a group.  It is almost a group.  But not quite.

(* is not actually pronounced "bob".)

Comments left here were deleted, because I was being emo and weird. (Is it Wednesday already?)

Current Mood: quixotic
Current Music: Various Artists - Pone on April 1st, 2009 02:53 am (UTC)
I have to say. HOLY F S Batman, that's some piece of work you got yourself there. I can't even begin to understand. This is in English? :-) I am impressed that you typed all this out. Even more impressed that you understand it. on April 1st, 2009 04:38 am (UTC)
Wow. My boo is smarter than me! on April 1st, 2009 02:30 pm (UTC)
Okay, I just remembered what part of Sneakers originally made you wonder what homomorphisms are. It's in Janos's talk, isn't it. on April 1st, 2009 03:40 pm (UTC)
Yup. 