A small cartesian closed concrete category
Is there a cartesian closed concrete category which is small enough to write out explicitly? It would be helpful in learning about map objects, exponentiation, distributivity and etc. Can such a category be made with binary numbers for instance? Thanks, ... Peter E. http://carnot.yi.org/
On Thu, 14 Feb 2008 10:07:27 PM EST, PETER EASTHOPE <peasthope@shaw.ca> asked:
Is there a cartesian closed concrete category which is small enough to write out explicitly?
How about the full category of finite sets? Or, if that's not small enough, and you really fancy an example
... made with binary numbers for instance ,
try the skeletal version of the full category of "sets of cardinality < 2" having as only objects the ordinal numbers 0 and 1. Here 0 x A = 0, 1 x A = A, 0^1 = 0, 0^0 = 1, 1^A = 1. In other words, B x A = min(A, B), B^A = max(1-A, B). Happy Valentines's Day! -- Fred
Peter Easthope asked,
Is there a cartesian closed concrete category which is small enough to write out explicitly? It would be helpful in learning about map objects, exponentiation, distributivity and etc. Can such a category be made with binary numbers for instance?
How about finite sets and functions? Not just a CCC but an elementary topos. I'm not sure what you mean by "binary numbers", but the powerset of n is 2^n (I wonder why Cantor introduced this notation?), and the subsets of n are n-digit binary numbers. As for more general function spaces, maybe it's worth an undergraduate exercise to see whether there's a neat representation. NBB: You don't need even to have heard of domain theory to find examples of CCCs! Paul Taylor
On Thu, Feb 14, 2008 at 9:46 PM, Fred E.J. Linton <fejlinton@usa.net> wrote:
On Thu, 14 Feb 2008 10:07:27 PM EST, PETER EASTHOPE <peasthope@shaw.ca> asked:
Is there a cartesian closed concrete category which is small enough to write out explicitly?
try the skeletal version of the full category of "sets of cardinality < 2" having as only objects the ordinal numbers 0 and 1.
Here 0 x A = 0, 1 x A = A, 0^1 = 0, 0^0 = 1, 1^A = 1. In other words, B x A = min(A, B), B^A = max(1-A, B).
Or, in case that's too small, what about any short chain? For instance, let S = {0,1,2,3} and say there exists a morphism a -> b iff a < b. I believe this is cartesian closed, and I believe it can easily be understood as concrete. This should be enough to give non-trivial product and exponentiation, but you can still draw the whole diagram. Matt -- Matt Hellige / matt@immute.net http://matt.immute.net
PETER EASTHOPE wrote:
Is there a cartesian closed concrete category which is small enough to write out explicitly? It would be helpful in learning about map objects, exponentiation, distributivity and etc. Can such a category be made with binary numbers for instance?
A Heyting algebra, viewed as a category (every poset is a category), is a CCC. If you take a small Heyting algebra, e.g. the topology of a finite topological space, you can write it out explicitly. If you would like a CCC made from n-bit binary numbers, here is how you can do it: The two-point lattice B = {0, 1} is a Boolean algebra with the usual logical connectives as the operations. Because B is a poset with 0<=1, it is also a category (with two objects 0, 1 and a morphism between them). Since every Boolean algebra is a Heyting algebra, B is cartesian closed, with the following structure: - 1 is the terminal object - the product X x Y is the conjuction X & Y - the exponential Y^X is the implicatoin X => Y The product of n copies of B is the same thing as n-tuples of bits, i.e., the n-bit numbers. This is again a CCC (with coordinate-wise structure). At this late hour I cannot see what can be said about finite CCC's which are not (eqivalent to) posets. Andrej
Every finite category with binary products is a preorder: any two objects A,B have at most one arrow A-->B. Otherwise the successive powers of B would have unboundedly many arrows from A. This is Peter Freyd's proof that small complete categories are preorders. Andrei would have thought of it at a more reasonable hour. Colin
On 16 Feb 2008, at 00:17, Andrej Bauer wrote:
PETER EASTHOPE wrote:
Is there a cartesian closed concrete category which is small enough to write out explicitly? It would be helpful in learning about map objects, exponentiation, distributivity and etc. Can such a category be made with binary numbers for instance?
A Heyting algebra, viewed as a category (every poset is a category), is a CCC. If you take a small Heyting algebra, e.g. the topology of a finite topological space, you can write it out explicitly.
If you would like a CCC made from n-bit binary numbers, here is how you can do it:
The two-point lattice B = {0, 1} is a Boolean algebra with the usual logical connectives as the operations. Because B is a poset with 0<=1, it is also a category (with two objects 0, 1 and a morphism between them). Since every Boolean algebra is a Heyting algebra, B is cartesian closed, with the following structure: - 1 is the terminal object - the product X x Y is the conjuction X & Y - the exponential Y^X is the implicatoin X => Y
The product of n copies of B is the same thing as n-tuples of bits, i.e., the n-bit numbers. This is again a CCC (with coordinate-wise structure).
At this late hour I cannot see what can be said about finite CCC's which are not (eqivalent to) posets.
Indeed, are there any at all? If you have coproducts you can define the infinite collection of objectss 0,1,2,... and if you identify any of those you get equational inconsistency. A similar construction should also work for CCCs. In the simply typed lambda calculus with one base type o you can iterpret n as o^n -> o and you get equational inconsistency if you identify any two finite types. This carries over to a finite collection of base types, and hence there cannot be a finite CCC which isn't a preorder. I am sure there must be a more elegant proof of this. Cheers, Thorsten
Folk, At Thu, 14 Feb 2008 15:06:49 -0500 I wrote, "Is there a cartesian closed concrete category which is small enough to write out explicitly?" At Fri, 15 Feb 2008 08:47:57 +0000 Philip Wadler srote, "... please summarize the replies ... and send ... to the ... list? ... interested to see if you receive a positive reply." I've counted 16 respondents! The question is answered well. With my limited knowledge, the summary probably fails to credit some of the responses adequately but this is not intentional. Thanks to everyone who replied! 5 messages mentioned Hyting-algebras. Never heard of them. Lawvere & Schanuel do not mention them in the 1997 book. Will store the terms for future reference. Fred Linton wrote, "... skeletal version of the full category ... having as only objects the ordinal numbers 0 and 1. Here 0 x A = 0, 1 x A = A, 0^1 = 0, 0^0 = 1, 1^A = 1. In other words, B x A = min(A, B), B^A = max(1-A, B)." My product diagrams are at http://carnot.yi.org/category01.jpg . Now I can try to illustrate the uniqueness of map objects according to L&S, page page 314, Exercise 1. Does this category have a name? Is Boolean Category sensible? Two messages mentioned lambda calculus. Another topic for future reference. Stephen Lack asked "How small is small? How explicit is explicit?" Probably several other readers wondered the same. Fred's reply is small enough and explicit enough to write out in detail. One message addressed the term "concrete". I referred to Concrete Categories in the Wikipedia. Matt Hellige mentioned categories a little bigger than that described by Fred. For instance, objects 0, 1, 2, 3. Map A -> B exists iff A < B. B x A =? min(A, B) I should sketch the details of some of these examples beyond the 0, 1 case above. Andrej Bauer described Fred's category in the context of Heyting algebra and noted a proof by Peter Freyd. Thorsten Altenkirch mentioned an equational inconsistency which is beyond my present grasp. Apologies to anyone who's reply is not addressed adequately. If someone requests, I can revise the summary and resubmit it. Thanks, ... Peter E. Desktops.OpenDoc http://carnot.yi.org/
Peter Easthope points out that in Lawvere & Schanuel there is no mention of Arend Heyting. That is unfortunate, especially since pp 348-352 are devoted to introducing Heyting's Algebras and one of their possible objective origins. The 2nd edition should correct this omission. Summarizing the 16 responses, a common thought of many must have been "If small implies finite then any example must be a poset (category in which any two parallel maps are equal) because of Freyd's theorem. A CC poset is almost by definition a Heying Algebra. There are linearly ordered ones of any size, but if the size is four or more, there are also examples that are not linearly ordered.... On the other hand if infinite examples are allowed, and posetal ones are not, it is hard to think of a CCC smaller than a skeletal category of all finite sets." Bill
5 messages mentioned Hyting-algebras. Never heard of them.Lawvere & Schanuel do not mention them in the 1997 book. Will store the terms for future reference.
Nowadays when I hear "Never heard of x" my subconscious seems to turn it into "never heard of Wikipedia." When five people tell you x is the answer to your question, merely filing it "for future reference" misses the point of the answer. (As one of the five, my examples consisted of the finite nonempty chains and the finite Boolean algebras, which I pointed out to Peter gave an example of every finite positive cardinality, and two for the powers of two. My mistake was to lump these examples together under the common rubric of "Heyting algebra," which appears to have made what was meant to be a simple answer incomprehensible.) As Bill points out, a Heyting algebra is almost the same thing as a CCC in the case of categories that are posets. This is exactly the case when there are finitely many objects (a case where Heyting algebras and distributive lattices are "the same thing" in the sense that they have the same underlying posets), and is close to true modulo existence of joins in the infinite case. In particular a Heyting algebra needs the empty join 0 in order to define negation as x->0, whence the negative integers made a category with its standard ordering is cartesian closed but is not a Heyting algebra for want of a least negative integer. More generally Heyting algebras are required to have all finite joins, not a requirement for posetal cartesian closed categories. Vaughan Pratt
participants (10)
-
Andrej Bauer -
Colin McLarty -
Fred E.J. Linton -
Matt Hellige -
Paul Taylor -
peasthope＠shaw.ca -
PETER EASTHOPE
-
Thorsten Altenkirch -
Vaughan Pratt -
wlawvere＠buffalo.edu