Re: A small cartesian closed concrete category

Re: A small cartesian closed concrete category

[Fred E.J. Linton]

Is it worth noting, in this jpeg, that the arithmetical

> max(1-A, B) 

for B^A coincides here with the Boolean

> {not}-A or B 

for the classical B => A?

Cheers, -- Fred

------ Original Message ------
Received: Thu, 22 May 2008 08:54:54 PM EDT
From: PETER EASTHOPE <peasthope@shaw.ca>
To: categories@mta.ca
Subject: categories: Re: A small cartesian closed concrete category

> Folk,
> 
> At Fri, 16 May 2008 00:29:16 -0700 Robert L Knighten wrote,
> .. no morphism from 1 to 0 -- these are sets after all ...
> 
> At Fri, 16 May 2008 13:57:40 -0700 Toby Bartels wrote,
> .. map from 1 to 0.  Surely ... a mistake?
> 
> Right oh, thanks.  The diagram is patched.
>    http://carnot.yi.org/FLcategory.jpg
> 
> Sorry for the poor quality.  I kept the file small for sake
> of anyone using an old modem.
> 
> How about someone suggesting a name for this category.
> Seems worth posting as a SVG or PostScript for benefit
> of other novices such as me.
> 
> Thanks,             ... Peter E.
> 
> -- 
> http://carnot.yi.org/
> http://carnot.pathology.ubc.ca/
> http://members.shaw.ca/peasthope/

Re: A small cartesian closed concrete category

[PETER EASTHOPE]

Folk,

At Fri, 16 May 2008 00:29:16 -0700 Robert L Knighten wrote,
... no morphism from 1 to 0 -- these are sets after all ...

At Fri, 16 May 2008 13:57:40 -0700 Toby Bartels wrote,
... map from 1 to 0.  Surely ... a mistake?

Right oh, thanks.  The diagram is patched.
   http://carnot.yi.org/FLcategory.jpg

Sorry for the poor quality.  I kept the file small for sake
of anyone using an old modem.

How about someone suggesting a name for this category.
Seems worth posting as a SVG or PostScript for benefit
of other novices such as me.

Thanks,             ... Peter E.

-- 
http://carnot.yi.org/
http://carnot.pathology.ubc.ca/
http://members.shaw.ca/peasthope/

Re: A small cartesian closed concrete category

[Toby Bartels]

Peter easthope wrote in part:

>http://carnot.pathology.ubc.ca/FLcategory.jpg
>If anyone can point out an error, that will help.

This says that there is a map from 1 to 0.  Surely that is a mistake?


--Toby

Re: A small cartesian closed concrete category

[wlawvere]

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

Re: A small cartesian closed concrete category

[peasthope]

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/

Re: A small cartesian closed concrete category

[Thorsten Altenkirch]

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

Re: A small cartesian closed concrete category

[Colin McLarty]

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

Re: A small cartesian closed concrete category

[Andrej Bauer]

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

Re: A small cartesian closed concrete category

[Matt Hellige]

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

Re: A small cartesian closed concrete category

[Paul Taylor]

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

Re: A small cartesian closed concrete category

[Fred E.J. Linton]

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

A small cartesian closed concrete category

[PETER EASTHOPE]

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/