From: daryl@oracorp.com (Daryl McCullough)
Subject: Re: Those Naughty Category Theorists
Organization: ORA Corporation
Date: Mon, 14 Dec 1992 17:03:38 GMT

pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:

>Category theory:  The ordered pair <a,b> is an entity uniquely
>determined by entities a and b and uniquely determining those same a
>and b via a rule which for every ordered pair determines some a and b.

It took me forever to get to the point where the category theory
definitions of cross products, disjoint unions, etc. made sense
to me. (Now, they are all intuitively obvious, of course.) Let
me try my hand at it:

First of all, category theory doesn't really define what it means to
be *an* ordered pair, it only defines what it means for one object to
be the cross product of two other objects.

I'm going to use type theory, rather than category theory, but the
concepts can all be translated into category theory. Let's write down
some properties we want a cross product to have:

If an object C is to act like A x B, then we need to have left and
right projection functions: l: C -> A, and r: C -> B. Given *any*
C and any l and r, we can represent some ordered pairs as elements of
C. Element c of C represents the ordered pair <l(c), r(c)>

Now, although any C,l, and r can represent some ordered pairs of A x B,
there can be two kinds of flaws in our representation: (1) Some pairs
may not be represented, and (2) Some pairs may be represented twice--that
is, there may be c1 and c2 such that c1 is not equal to c2, but
the corresponding pairs, <l(c1), r(c1)>, <l(c2),r(c2)> are equal.

To take care of the first problem, we demand that C, l, and r can
represent as many pairs as any other representation can. That is, if
we have some other candidate for representing pairs D, f, g, then
there is for every pair represented in D a corresponding pair
represented in C. Mathematically, if D is some object, f: D -> A,
g: D -> B, then D also represents pairs. To say that C represents
as many pairs as D does means that there is a function q: D -> C
such that for any d, q(d) represents the same pair as d. That is,
l(q(d)) = f(d) and r(q(d)) = g(d). This can be written without
mentioning elements by using function composition:

   C, l, r represents as many pairs as D, f, g if there is some
   q: D -> C such that l o q = f and r o q = g, (where l o q is
   the function defined by l o q (d) = l(q(d))).

(Note, I may have the order wrong for composition; I'm not sure
if the convention is l o q or q o l.)

We can then say that C, l, r represents all pairs in A x B if
for all D,f,g it represents as many pairs as D, f, g.

To take care of the second problem, we demand that there not be two
different ways of representing the same pair in C, l, r. We can insure
this by asking that for all D, f, and g, there must be a *unique*
function q such that l o q = f and r o q = g.

Thus we get the category theory definition of cross-product:
C,l,r represents the cross product A x B if l: C -> A, r: C -> B,
and for all D,f,g such that f: D -> A, g: D -> B, there exists a
unique q: D -> A such that l o q = f and r o q = g.

(For category theory, read f: D -> A as "f is a morphism from
D into A")

Daryl McCullough
ORA Corp.
Ithaca, NY
Newsgroups: sci.math