<p>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.</p>

<p>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.)</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-19T15:16:44.527Z
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.
Ohad Kammar
CC BY-SA 2.5
2010-11-19T15:21:52.463Z
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.
Ohad Kammar
CC BY-SA 2.5
2010-11-19T15:29:17.303Z
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.
Ohad Kammar
CC BY-SA 2.5
2010-11-19T15:53:32.093Z
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!
Neel Krishnaswami
CC BY-SA 3.0
2012-08-06T12:14:41.283Z
Markowsky 1977, [Categories of chain-complete posets](http://www.sciencedirect.com/science/article/pii/0304397577900317) has a nice table for some variants of CPOs.
Ohad Kammar
CC BY-SA 2.5
2010-11-19T12:16:28.267Z
2010-11-19T12:16:28.267Z
Neel Krishnaswami
<p>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 <a href="http://en.wikipedia.org/wiki/Category_theory">Category Theory</a> and <a href="http://en.wikipedia.org/wiki/Domain_theory">Domain Theory</a>. Another good internet resource is <a href="http://ncatlab.org/nlab/">nCatLab</a>, though it drifts more into higher-dimensional category theory.</p>

<p>A good  domain theory reference is <a href="http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf">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.</a></p>

<p>Books on category theory I've actually looked at are:</p>

<ul>
<li><p>Awodey, Steve (2006). Category Theory (Oxford Logic Guides 49). Oxford University Press. 2nd edition, 2010. 
<strong>A good recent introduction, slanted towards computer science</strong></p></li>
<li><p>Barr, Michael; Wells, Charles  "Category Theory for Computing Science." <strong>Hard to get, that is, not available from Amazon</strong></p></li>
<li><p>Lawvere, William; Schanuel, Steve (1997). Conceptual mathematics: a first introduction to categories. Cambridge University Press. <strong>Delightful introduction, perhaps not deep enough</strong></p></li>
<li><p>Mac Lane, Saunders (1998). Categories for the Working Mathematician. Graduate Texts in Mathematics 5 (2nd ed.). Springer-Verlag. ISBN 0-387-98403-8. <strong>Perhaps too mathematical</strong></p></li>
<li><p>Pierce, Benjamin (1991). Basic Category Theory for Computer Scientists. MIT Press. <strong>Perhaps too basic</strong></p></li>
<li><p>Taylor, Paul (1999). Practical Foundations of Mathematics. Cambridge University Press.
<strong>Quite comprehensive; takes a logical perspective</strong></p></li>
</ul>

<p>Other books are available online such as Barr &amp; Well's <a href="http://www.case.edu/artsci/math/wells/pub/pdf/ttt.pdf">Toposes, Triples, and Theories</a> and Jiri Adámek, Horst Herrlich, and George E. Strecker's <a href="http://katmat.math.uni-bremen.de/acc/acc.pdf">Abstract and Concrete Categories – The Joy of Cats</a>. These are likely to contain all the definitions you need, at least from the category theory side.</p>

CC BY-SA 3.0
2012-03-07T17:09:00.463Z
Perhaps develop our own version of [ncatlab](http://ncatlab.org/nlab/show/HomePage)?
Uday Reddy
CC BY-SA 2.5
2010-11-19T15:05:17.863Z
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.
Ohad Kammar
CC BY-SA 2.5
2010-11-22T09:08:14.043Z
One approach to solving this problem for future generations is to write your own dictionary of such terms as you come across them.
Dave Clarke
CC BY-SA 2.5
2010-11-19T08:37:29.977Z
2010-11-19T08:37:29.977Z
Dave Clarke
<p>How about asking your advisor? He invented a good portion of domain theory.</p>

CC BY-SA 2.5
2010-11-20T17:01:21.427Z
*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...
Ohad Kammar
CC BY-SA 2.5
2010-11-19T21:33:54.247Z
2010-11-19T21:33:54.247Z
Andrej Bauer
<p>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. </p>

<p>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.</p>

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

<ct.category-theory><semantics><denotational-semantics><domain-theory>
What is a good Category Theory-Domain Theory dictionary?
Ohad Kammar
# What is a good Category Theory-Domain Theory dictionary?

(Asked by: username_0 on 2010-11-19)

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?

**Tags:** ct.category-theory, semantics, denotational-semantics, domain-theory

---

## 3 answers

### Answer by username_1 on 2010-11-19. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_1**: 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!  
> **username_0**: Markowsky 1977, [Categories of chain-complete posets](http://www.sciencedirect.com/science/article/pii/0304397577900317) has a nice table for some variants of CPOs.  

---

### Answer by username_2 on 2010-11-19. Score: 5

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](http://en.wikipedia.org/wiki/Category_theory) and [Domain Theory](http://en.wikipedia.org/wiki/Domain_theory). Another good internet resource is [nCatLab](http://ncatlab.org/nlab/), 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.](http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf)

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](http://www.case.edu/artsci/math/wells/pub/pdf/ttt.pdf) and Jiri Adámek, Horst Herrlich, and George E. Strecker's [Abstract and Concrete Categories – The Joy of Cats](http://katmat.math.uni-bremen.de/acc/acc.pdf). These are likely to contain all the definitions you need, at least from the category theory side.

> **Comments:**
> **username_0**: 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.  
> **username_2**: One approach to solving this problem for future generations is to write your own dictionary of such terms as you come across them.  
> **username_3**: Perhaps develop our own version of [ncatlab](http://ncatlab.org/nlab/show/HomePage)?  

---

### Answer by username_4 on 2010-11-19. Score: 3

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

> **Comments:**
> **username_0**: *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...  

---

