Tab Completion

I'm Tab Atkins Jr, and I wear many hats. I work for Google on the Chrome browser as a Web Standards Hacker. I'm also a member of the CSS Working Group, and am either a member or contributor to several other working groups in the W3C. You can contact me here.
Listing of All Posts

Basic Category Theory Terms

Last updated:

Magma: A set of objects that can be "added" or "combined" in some way, so that if you add any two of them the result is also in the set. That's it.

Semigroup: A magma whose "addition" operation obeys associativity: (a + b) + c must give the same answer as a + (b + c). For example, strings form a semigroup with concatenation as their "addition" operator: ("foo" + "bar") + "baz" = "foobarbaz", etc. So do the integers under the min() operation.

Monoid: A semigroup with a "zero" element: something that, when "added" to any element in the group, produces that other element again. For example, the empty string is the "zero" element in the string/concat monoid. The integers with min() aren't a monoid, but they become one if you add infinity as the "zero" element. Lots of interesting things are monoids; it's a very simple and useful constraint to satisfy. If you satisfy "monoid", you get a free version of the reduce function using your operation.

Group: A monoid where every element has an opposite or "negative" version, so that if you "add" an element and its opposite, you get the "zero" element. Strings with concatenation are not a group - concatenation only ever produces larger strings, not smaller ones, so you can't ever take a string like "foo" and add another string to it to get the empty string. On the other hand, integer/addition is a group - the opposite of each member is just the negative integer corresponding to it.

An Alternate Path to a Group

There's an alternate way to get from magma to group. You add different properties along the way, but when they're all combined they add up to the same thing that the previous path did. However, these properties are harder for most things to satisfy, and so they're not generally as useful; most of the things you use that'll satisfy any of these do so because they're all the way to a group already.

Quasigroup: A magma with "divisibility". This property's a little subtle: it means the operation can transform any element of the set to any other element by combining it with an appropriate third element. It has to do so whether the first element is the left or right argument, but the element you choose to combine it with can be different in the two cases.

The integers with subtraction form a quasigroup - if I want to transform "2" into "5", I can do it with 2 − -3 = 5 and 7 − 2 = 5. (So do the integers with addition, but they satisfy so many of these definitions that they're not very interesting to talk about.) On the other hand, strings with concatenation are not a quasigroup - while you can transform some strings, like "foo" to "foobar", you can't generally do it both ways (nothing satisfies the equation X + "foo" = "foobar"), and most strings you can't transform between at all.

Loop: A quasigroup with a "zero" element, which transforms an element into itself regardless of which side it starts on. Or, equivalently, a group without associativity. Integer/subtraction is not a loop: X − 0 = X, which is what we want, but 0 − X = -X, which isn't what we want (and no other number satisfies either side, obviously.) "Natural" examples of loops that aren't groups are a little hard to come by, but the non-zero octonions under multiplication are one (because they're non-associative; omitting the zero octonion is required to keep the "divisibility" quasigroup property, as you can't get from the zero octonion to anything else via multiplication).

Group: Ah, back to group. Along this path, a group is a loop with associativity.

Going Further

Abelian or Commutative X: Any of the above types might have an operation which is commutative - it doesn't matter which order the arguments are. Integer/min is an abelian monoid, because min(1, 10) = 10 and max(10, 1) = 10.

(a limited set of Markdown is supported)

Well, you obviously meant max at the end. :-)

For an example of a proper loop, nonzero octonions with multiplication are nice. Or "positive definite unit quaternions", where you redefine all squares to be 1 (instead of three of them being -1).

Reply?

(a limited set of Markdown is supported)