11
$\begingroup$

When dealing with the domain theoretic categories (say CPO and $\omega$CPO), I frequently wish for a dictionary for the language of category theory in domain theory.

That is, given a concept, say monic arrow, I could look it up in the dictionary and see what are the known characterisations of it in the different domain categories.

I realise this wish is too much to hope for, but is there any text or resource approximating it?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
6
$\begingroup$

The best resource for this is Abramsky and Jung's handbook chapter. I recall they had a table which cross-referenced various constructions and categories of domains, with the entries saying whether the construction worked in that category and what properties it had. However, properties of arrows like being a monic tended not to have terribly slick characterizations, because the availability of flat domains tends to ensure that they are often not terribly different from their set-theoretic counterpart. OTOH, properties that make some use of the order structure (like being an embedding-projection pair) tend to have fairly pretty characterizations.

A minor point to watch out for is that there are actually two definitions of CPO in common use! Consumers of domain theory (like me) often prefer to work with omega-chains, since chains are pretty concrete objects; whereas producers of domain theory (like, er, your advisor) tend to prefer to work with directed sets, which are more general and have better algebraic properties. (Offhand I'm not sure if restricting to directed sets having countable base is equivalent to the omega-chain condition.)

Something I found very helpful in building this kind of dictionary is to work through the solution of recursive domain equations in some category of things that aren't exactly domains. Two good choices are categories of PERs (eg, in models of polymorphism) and presheaves (eg, for name allocation). Metric spaces are another possibility, but I found them to be too similar to domains to help me build intuition.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yes, I'm familiar with Abramsky et al.'s chapter, and in particular said table. As you said, they describe the fundamental structures (products, sums, exponentials, etc.), but the list is far from comprehensive. $\endgroup$
    – Ohad Kammar
    Nov 19, 2010 at 15:16
  • $\begingroup$ The question arose in my mind when I was discussing several possibilities for a definition, and we needed to compare different categorical concepts (several notions of monic arrows, to be exact). I was a bit surprised when I realised that our methodology was either to quickly work out convenient characterisations using intuition, old articles, and any book the popped into our mind, especially when the notions were not such obscure categorical notions. Of course, this method is called "expertise" (which I lack), but as a programmer I felt that there could be a better way to do it. $\endgroup$
    – Ohad Kammar
    Nov 19, 2010 at 15:21
  • $\begingroup$ Oh, and by the way, regarding said producer --- how many of those issues with DCPOs are due to research timeline? If you look at Scott's original models of the $\lambda$-calculus, he used continuous lattices, which are even stronger than DCPOs (right?). In retrospect, we know that continuous lattices are not the best notion, and work with $\omega$CPOs, or whatever flavour suitable (pointed CPOs or over PERs, etc). Indeed, that's where the full advantage of category theory manifests itself. I know that nowadays he's perfectly content to work with $\omega$CPO when we need to consume something. $\endgroup$
    – Ohad Kammar
    Nov 19, 2010 at 15:29
  • $\begingroup$ You might want to look at Smyth and Plotkin 1982, "On the Category-Theoretic Solution of Recursive Domain Equations", or some of Paul Taylor's papers (I forget exact refs), or Andy Pitts's 1996 "Relational Properties of Domains". These papers all do things via top-down abstract characterizations of the needed properties. Me, I found these papers a little too abstract for me until I had worked through the concrete details in a couple of examples. Then they were clear! $\endgroup$
    – Neel Krishnaswami
    Nov 19, 2010 at 15:53
  • $\begingroup$ Markowsky 1977, Categories of chain-complete posets has a nice table for some variants of CPOs. $\endgroup$
    – Ohad Kammar
    Aug 6, 2012 at 12:14
5
$\begingroup$

I'm not sure there is one. There are however many good books on Category Theory and even more sets of lecture notes, of varying quality. Wikipedia also has quite a lot of reliable information on Category Theory and Domain Theory. Another good internet resource is nCatLab, though it drifts more into higher-dimensional category theory.

A good domain theory reference is S. Abramsky, A. Jung (1994). "Domain theory". In S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, editors, (PDF). Handbook of Logic in Computer Science. III. Oxford University Press. ISBN 0-19-853762-X.

Books on category theory I've actually looked at are:

  • Awodey, Steve (2006). Category Theory (Oxford Logic Guides 49). Oxford University Press. 2nd edition, 2010. A good recent introduction, slanted towards computer science

  • Barr, Michael; Wells, Charles "Category Theory for Computing Science." Hard to get, that is, not available from Amazon

  • Lawvere, William; Schanuel, Steve (1997). Conceptual mathematics: a first introduction to categories. Cambridge University Press. Delightful introduction, perhaps not deep enough

  • Mac Lane, Saunders (1998). Categories for the Working Mathematician. Graduate Texts in Mathematics 5 (2nd ed.). Springer-Verlag. ISBN 0-387-98403-8. Perhaps too mathematical

  • Pierce, Benjamin (1991). Basic Category Theory for Computer Scientists. MIT Press. Perhaps too basic

  • Taylor, Paul (1999). Practical Foundations of Mathematics. Cambridge University Press. Quite comprehensive; takes a logical perspective

Other books are available online such as Barr & Well's Toposes, Triples, and Theories and Jiri Adámek, Horst Herrlich, and George E. Strecker's Abstract and Concrete Categories – The Joy of Cats. These are likely to contain all the definitions you need, at least from the category theory side.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the comprehensive answer. However, as you said, it's easy enough to find material on domain theory and on category theory. And, in fact, quite a lot of it. But that's the problem, the knowledge is spread across so many pages of books, conventions and notations, that accessing it (even with Google) becomes non-trivial. I guess that the difference is between having a shelf full of text books versus a good reference book that just quotes the relationships and citations. $\endgroup$
    – Ohad Kammar
    Nov 19, 2010 at 15:05
  • $\begingroup$ One approach to solving this problem for future generations is to write your own dictionary of such terms as you come across them. $\endgroup$
    – Dave Clarke
    Nov 22, 2010 at 9:08
  • 1
    $\begingroup$ Perhaps develop our own version of ncatlab? $\endgroup$
    – Uday Reddy
    Mar 7, 2012 at 17:09
3
$\begingroup$

How about asking your advisor? He invented a good portion of domain theory.

Improve this answer
$\endgroup$
1
  • $\begingroup$ chuckles As I said above, the thought came to mind when we were discussing some category theoretic notions in different domains. My exact thought was: surely there should be a better way than asking an expert skimming through the entire literature or downright guesswork... $\endgroup$
    – Ohad Kammar
    Nov 20, 2010 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.