home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 16904 < prev    next >
Encoding:
Text File  |  1992-12-14  |  3.3 KB  |  77 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!psinntp!scylla!daryl
  3. From: daryl@oracorp.com (Daryl McCullough)
  4. Subject: Re: Those Naughty Category Theorists
  5. Message-ID: <1992Dec14.170338.4977@oracorp.com>
  6. Organization: ORA Corporation
  7. Date: Mon, 14 Dec 1992 17:03:38 GMT
  8. Lines: 67
  9.  
  10. pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
  11.  
  12. >Category theory:  The ordered pair <a,b> is an entity uniquely
  13. >determined by entities a and b and uniquely determining those same a
  14. >and b via a rule which for every ordered pair determines some a and b.
  15.  
  16. It took me forever to get to the point where the category theory
  17. definitions of cross products, disjoint unions, etc. made sense
  18. to me. (Now, they are all intuitively obvious, of course.) Let
  19. me try my hand at it:
  20.  
  21. First of all, category theory doesn't really define what it means to
  22. be *an* ordered pair, it only defines what it means for one object to
  23. be the cross product of two other objects.
  24.  
  25. I'm going to use type theory, rather than category theory, but the
  26. concepts can all be translated into category theory. Let's write down
  27. some properties we want a cross product to have:
  28.  
  29. If an object C is to act like A x B, then we need to have left and
  30. right projection functions: l: C -> A, and r: C -> B. Given *any*
  31. C and any l and r, we can represent some ordered pairs as elements of
  32. C. Element c of C represents the ordered pair <l(c), r(c)>
  33.  
  34. Now, although any C,l, and r can represent some ordered pairs of A x B,
  35. there can be two kinds of flaws in our representation: (1) Some pairs
  36. may not be represented, and (2) Some pairs may be represented twice--that
  37. is, there may be c1 and c2 such that c1 is not equal to c2, but
  38. the corresponding pairs, <l(c1), r(c1)>, <l(c2),r(c2)> are equal.
  39.  
  40. To take care of the first problem, we demand that C, l, and r can
  41. represent as many pairs as any other representation can. That is, if
  42. we have some other candidate for representing pairs D, f, g, then
  43. there is for every pair represented in D a corresponding pair
  44. represented in C. Mathematically, if D is some object, f: D -> A,
  45. g: D -> B, then D also represents pairs. To say that C represents
  46. as many pairs as D does means that there is a function q: D -> C
  47. such that for any d, q(d) represents the same pair as d. That is,
  48. l(q(d)) = f(d) and r(q(d)) = g(d). This can be written without
  49. mentioning elements by using function composition:
  50.  
  51.    C, l, r represents as many pairs as D, f, g if there is some
  52.    q: D -> C such that l o q = f and r o q = g, (where l o q is
  53.    the function defined by l o q (d) = l(q(d))).
  54.  
  55. (Note, I may have the order wrong for composition; I'm not sure
  56. if the convention is l o q or q o l.)
  57.  
  58. We can then say that C, l, r represents all pairs in A x B if
  59. for all D,f,g it represents as many pairs as D, f, g.
  60.  
  61. To take care of the second problem, we demand that there not be two
  62. different ways of representing the same pair in C, l, r. We can insure
  63. this by asking that for all D, f, and g, there must be a *unique*
  64. function q such that l o q = f and r o q = g.
  65.  
  66. Thus we get the category theory definition of cross-product:
  67. C,l,r represents the cross product A x B if l: C -> A, r: C -> B,
  68. and for all D,f,g such that f: D -> A, g: D -> B, there exists a
  69. unique q: D -> A such that l o q = f and r o q = g.
  70.  
  71. (For category theory, read f: D -> A as "f is a morphism from
  72. D into A")
  73.  
  74. Daryl McCullough
  75. ORA Corp.
  76. Ithaca, NY
  77.