reperiendi

Cartesian categories and the problem of evil

Posted in Category theory, Math by Mike Stay on 2007 September 19

How many one-element sets are there? Well, given any set S, we can construct the one-element set \{S\}, 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 G and H in the category C is

  • an object of C, which we’ll label G\times H, together with
  • two maps, called projections
    • \pi_G:G\times H\to G
    • \pi_H:G\times H\to H

that satisfy the following universal property: for any triple (X, f_G:X\to G, f_H:X \to H), there is a unique map from X to G\times H making the following diagram commute:

Xto Gtimes H making the whole 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:

(X, 1_X, 1_X),

and it’s clearly isomorphic to itself, so the trivial category has products.

3. A preorder is a set S equipped with a \le relation on pairs of elements of S that is transitive and reflexive. Given any preorder, we can construct a category whose

  • objects are the elements of S and
  • there is an arrow from x to y if x \le y.

So a product in a preorder is

  • an element z = x \times y of S together with maps
    • \pi_x:z\to x (that is, z \le x)
    • \pi_y:z \to y (that is. z \le y)

    such that for any other element w \in S, \, w\le x, \, w \le y, we have w \le z.

In other words, a product x \times y in a preorder is the greatest lower bound of x, y.  For example, in the preorder (\mathbb{R}, \le), the product of two numbers x, y is min(x, y).  In the preorder (\mbox{Set}, \subseteq), the product is x \cap y.  In the preorder (\mathbb{N}, |), where “|” is “divides”, the product is gcd(x, y).

Exercise: in what preorder over \mathbb{R} 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.

Advertisements

6 Responses

Subscribe to comments with RSS.

  1. Roshan said, on 2011 March 17 at 9:24 am

    Nice writeup.

    Btw you did mean z <= x in \pi_x instead of z < x (and similarly in \pi_y) didn't you?

  2. a b said, on 2014 December 10 at 12:00 pm

    Can I get a hint on the exercise?

    • Mike Stay said, on 2014 December 10 at 12:37 pm

      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.

  3. Joost Winter said, on 2015 January 28 at 1:53 pm

    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.

  4. Joost Winter said, on 2015 January 28 at 2:18 pm

    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…


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: