Cartesian categories and the problem of evil
How many one-element sets are there? Well, given any set we can construct the one-element set so the collection of one-element sets has to be a proper class, a mindbogglingly enormous collection far larger than any mere set could be. However, they’re all the same from the point of view of functions coming out of them: the one element, no matter what it is, maps to a point in the range. The internal nature of a given one-element set is completely irrelevant to the way it behaves as a member of the category Set of all sets and functions.
For a category theorist, making a distinction between one-element sets is evil. Instead of looking inside an object to see how it’s made, we should only care about how it interacts with the world around it. There are certain kinds of objects that are naturally special because of the way they interact with everything else; we say they satisfy universal properties.
Just as it is evil to dwell on the differences between isomorphic one-element sets, it is evil to care about the inner workings of ordered pairs. Category theory elevates an ordered pair to a primitive concept by ignoring all details about the implementation of an ordered pair except how it interacts with the rest of the world. Ordered pairs are called “products” in category theory.
A product of the objects and in the category is
- an object of , which we’ll label together with
- two maps, called projections
that satisfy the following universal property: for any triple there is a unique map from to making the following diagram commute:
In particular, given two different representations of ordered pairs, there’s a unique way to map between them, so they must be isomorphic.
A category will either have products or it won’t:
——————
1. The category Set has the obvious cartesian product.
2. The trivial category has one object and one morphism, the identity, so there’s only one choice for a triple like the one in the definition:
and it’s clearly isomorphic to itself, so the trivial category has products.
3. A preorder is a set equipped with a relation on pairs of elements of that is transitive and reflexive. Given any preorder, we can construct a category whose
- objects are the elements of and
- there is an arrow from to if
So a product in a preorder is
- an element of together with maps
- (that is, )
- (that is. )
such that for any other element we have
In other words, a product in a preorder is the greatest lower bound of . For example, in the preorder , the product of two numbers is min(). In the preorder , the product is . In the preorder , where “|” is “divides”, the product is gcd().
Exercise: in what preorder over is the cartesian product the same as multiplication?
——————
A cartesian category is a category with products. (Note the lowercase ‘c:’ you know someone’s famous if things named after them aren’t capitalized. C.f. ‘abelian.’) You can think of the cartesian coordinate system for the plane with its ordered pair of coordinates to remind you that you can make ordered pairs of objects in a cartesian category.
Nice writeup.
Btw you did mean z <= x in \pi_x instead of z < x (and similarly in \pi_y) didn't you?
Yep. Fixed, thanks!
Can I get a hint on the exercise?
I don’t know if there *is* a preorder where the cartesian product is multiplication. In the category of finite sets and all functions between them, the cartesian product of two sets with cardinality m and n has cartinality mn. Groupoid cardinality (http://ncatlab.org/nlab/show/groupoid+cardinality) generalizes cardinality to a function from groupoids to nonnegative real numbers. We can generalize to other categories as described in http://arxiv.org/abs/math.CT/0212377 and get complex cardinalities; in all of these, the cardinality of the product is the product of the cardinalities. I think there may be a way to consider a real number to be a cardinality-equivalence class of such objects and get an arrow between two numbers if there’s a morphism between any two objects in the corresponding classes, but I haven’t proven it.
Let’s see… Assume there is such a preorder on R.
By reflexivity, we must have 4<=4 in the preorder. Because 2*2 equals 4, 4<2 must hold in the preorder. By a similar argument, 8<4 should hold in the preorder as 4*2 equals 8, however as we already know that 4<=2 and 4<=4 must hold, it follows that 4 is a lower bound of 2 and 4, and as 8<4 holds by one of our assumption, 8 cannot be the glb of 2 and 4. It thus follows that there cannot be a preorder on R (or on N, Q, Z for that matter) s.t. cartesian product/glb is multiplication.
A simpler counterexample is of course given by the fact that in any preorder with glbs, the glb of an element x with itself is always x… so the glb of 2 and 2 is always 2 (or some object isomorphic to 2) in any preorder with domain N/Z/Q/R…
Remarkable exposition!
I have sought a clearer understanding of the compositions of category theory in relation to set theory and number theory for several decades because of the intrinsic tensions with role of forget functor in the natural sciences. THANK YOU!