Links
Football, video games, math, food, other stuff.
Monday, April 25, 2005
Over the past few days I've gone through a fair bit of category theory to try and understand the problem I'm looking at. I thought I'd try and write up all the background stuff that gets to my topic. If you don't like math, feel free to ignore :)
Category Theory
I was trying to think of how to describe category theory as I walked home this afternoon, and I came up with this: category theory is a formalized language for meta-mathematics. In other words, category theory is a way to make concrete a lot of the connections that one sorts of suspects between different areas of mathematics. The way it can do this is by being very, very general. A category is (a) a collection of objects, (b) a collection of arrows, each of which has a starting object and an ending object, and (c) a composition operation: if f is an arrow which goes from object A to object B, and g an arrow that goes from object B to object C, then there exists an arrow (g)(f) that goes from A to C. The objects, arrows, and composition object must satisfy two axioms: (i) Each object A has an identity arrow 1A which goes from A to A, and for any appropriate arrow f satisfies (f)(1A) = f = (1A)f, and (ii) for appropiate arrows f, g, h, f(gh) = (fg)h (associativity).
This is about as minimal a set of rules as one can imagine. The first nice thing about these rules is how many different things can be a category. The standard example is set: the category whose objects are sets, and arrows are functions. As a much smaller example, a surpisingly useful category is 2: the category which has only two objects, call them A and B, and three arrows: an identity for A, an identity for B, and arrow from A --> B. Other standard examples are grp: objects are groups, and arrows group homomorphisms, top, whose objects are topological spaces and arrows continuous functions, and ring, which has objects rings and arrows ring homomorphisms.
I think these standard examples lead to a common misconception of category theory: that it is nothing more than a useless generalization of algebraic and analytic structures. It includes a lot more, however. A good example is how the natural numbers can be made into a category, N. Take as your set of objects the set of natural numbers, and say that there is an arrow from a number x to another number y if and only if x <= y. The composition operation works because of transitity: if x <= y and y <= z, then x <= z, and the identity arrow axiom works because of reflexity, x <= x for all x. In fact, any partially ordered set can be made into a category in this way.
Here's an interesting example of how category theory can be useful: it shows how taking a product is the opposite of taking a sum. The idea of taking the product of sets is well known. If you have a set A and a set B, the product set AxB is simply all ordered pairs (a, b), where a is in A, and b is in B. Moreover, taking products of sets is well-behaved with respect to cardinality: if A has 5 elements and B has 4 elements, AxB has 5x4 = 20 elements.
Is there a similar idea for sums? Is there a set A+B such that the cardinality(|.|) of A+B is |A| + |B|? The natural thing is to try and take union: define A+B as A union B. However, if A and B share any elements, then |A union B| < |A| + |B|, so that does not work. Instead, one takes the "disjoint union": for each a in A, write it as (a, 1), for each b in B, write it as (b, 2), and define A+B to be the union of those two sets. Then indeed one will have |A+B| = |A| + |B|.
Now we need to look at the relations of the sets A, B to their products AxB and sum A+B. There are two nice functions out of AxB: a function p: AxB -> A which sends (a, b) to a, and a function q: AxB -> B which sends (a, b) to b - the standard projection functions. In a certain sense, these functions, together with AxB, are "universal". Suppose there was another set P with functions i: P -> A and j: P-> B. Then there exists a unique function m: P -> AxB which sends x to (i(x), j(x)), so that (pm)(x) = (i)(x), and (qm)(x) = (j)(x). There is where drawing a diagram comes in handy :) The "universality" is that any time we have another set P which "pretends" to be a product by having projection functions, then it must factor through the "real" product AxB in a unique way.
Now look at sums. There are two nice functions into A+B: a function p: A -> A+B which sends a to (a, 1) and q: B -> A+B which sends b to (b, 2). Moreover, we get the opposite universal property in this case. For any set S with functions i: A -> S and j: B -> S, one gets a a unique function m: A+B -> S which sends (a, 1) to i(a) and (b, 2) to j(b), and has the property that (mp)(x) = i(x) and (mq)(x) = j(x).
The importance of all this is that AxB and A+B are actually characterized by these properties. AxB is the only set (up to isomorphism) that has projections p and q and that universal property, and A+B is the only set that has anti-projections p, q and the opposite universal property. In a very real way, products are opposite to sums.
The reason anyone found this is because of an attempt to characterize products simply through functions, in other words, an attempt to make products a categorical notion. Thus one takes the universal property of AxB as the definition of the product of two objects in a category (if it exists). In category theory, it is always easy to take the opposite idea: just reverse all the arrows in a definition, and add a "co-" to the name. Hence the idea of a coproduct was born. As we've just seen, in the category set, coproducts turn out to be simply be sums, so products and sums really are opposite notions: to get a sum, one simply reverses all the arrows that defines a product.
More to come!!!
Category Theory
I was trying to think of how to describe category theory as I walked home this afternoon, and I came up with this: category theory is a formalized language for meta-mathematics. In other words, category theory is a way to make concrete a lot of the connections that one sorts of suspects between different areas of mathematics. The way it can do this is by being very, very general. A category is (a) a collection of objects, (b) a collection of arrows, each of which has a starting object and an ending object, and (c) a composition operation: if f is an arrow which goes from object A to object B, and g an arrow that goes from object B to object C, then there exists an arrow (g)(f) that goes from A to C. The objects, arrows, and composition object must satisfy two axioms: (i) Each object A has an identity arrow 1A which goes from A to A, and for any appropriate arrow f satisfies (f)(1A) = f = (1A)f, and (ii) for appropiate arrows f, g, h, f(gh) = (fg)h (associativity).
This is about as minimal a set of rules as one can imagine. The first nice thing about these rules is how many different things can be a category. The standard example is set: the category whose objects are sets, and arrows are functions. As a much smaller example, a surpisingly useful category is 2: the category which has only two objects, call them A and B, and three arrows: an identity for A, an identity for B, and arrow from A --> B. Other standard examples are grp: objects are groups, and arrows group homomorphisms, top, whose objects are topological spaces and arrows continuous functions, and ring, which has objects rings and arrows ring homomorphisms.
I think these standard examples lead to a common misconception of category theory: that it is nothing more than a useless generalization of algebraic and analytic structures. It includes a lot more, however. A good example is how the natural numbers can be made into a category, N. Take as your set of objects the set of natural numbers, and say that there is an arrow from a number x to another number y if and only if x <= y. The composition operation works because of transitity: if x <= y and y <= z, then x <= z, and the identity arrow axiom works because of reflexity, x <= x for all x. In fact, any partially ordered set can be made into a category in this way.
Here's an interesting example of how category theory can be useful: it shows how taking a product is the opposite of taking a sum. The idea of taking the product of sets is well known. If you have a set A and a set B, the product set AxB is simply all ordered pairs (a, b), where a is in A, and b is in B. Moreover, taking products of sets is well-behaved with respect to cardinality: if A has 5 elements and B has 4 elements, AxB has 5x4 = 20 elements.
Is there a similar idea for sums? Is there a set A+B such that the cardinality(|.|) of A+B is |A| + |B|? The natural thing is to try and take union: define A+B as A union B. However, if A and B share any elements, then |A union B| < |A| + |B|, so that does not work. Instead, one takes the "disjoint union": for each a in A, write it as (a, 1), for each b in B, write it as (b, 2), and define A+B to be the union of those two sets. Then indeed one will have |A+B| = |A| + |B|.
Now we need to look at the relations of the sets A, B to their products AxB and sum A+B. There are two nice functions out of AxB: a function p: AxB -> A which sends (a, b) to a, and a function q: AxB -> B which sends (a, b) to b - the standard projection functions. In a certain sense, these functions, together with AxB, are "universal". Suppose there was another set P with functions i: P -> A and j: P-> B. Then there exists a unique function m: P -> AxB which sends x to (i(x), j(x)), so that (pm)(x) = (i)(x), and (qm)(x) = (j)(x). There is where drawing a diagram comes in handy :) The "universality" is that any time we have another set P which "pretends" to be a product by having projection functions, then it must factor through the "real" product AxB in a unique way.
Now look at sums. There are two nice functions into A+B: a function p: A -> A+B which sends a to (a, 1) and q: B -> A+B which sends b to (b, 2). Moreover, we get the opposite universal property in this case. For any set S with functions i: A -> S and j: B -> S, one gets a a unique function m: A+B -> S which sends (a, 1) to i(a) and (b, 2) to j(b), and has the property that (mp)(x) = i(x) and (mq)(x) = j(x).
The importance of all this is that AxB and A+B are actually characterized by these properties. AxB is the only set (up to isomorphism) that has projections p and q and that universal property, and A+B is the only set that has anti-projections p, q and the opposite universal property. In a very real way, products are opposite to sums.
The reason anyone found this is because of an attempt to characterize products simply through functions, in other words, an attempt to make products a categorical notion. Thus one takes the universal property of AxB as the definition of the product of two objects in a category (if it exists). In category theory, it is always easy to take the opposite idea: just reverse all the arrows in a definition, and add a "co-" to the name. Hence the idea of a coproduct was born. As we've just seen, in the category set, coproducts turn out to be simply be sums, so products and sums really are opposite notions: to get a sum, one simply reverses all the arrows that defines a product.
More to come!!!
