* Re: A small cartesian closed concrete category
@ 2008-05-16 20:57 Toby Bartels
0 siblings, 0 replies; 12+ messages in thread
From: Toby Bartels @ 2008-05-16 20:57 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-05-25 15:50 Fred E.J. Linton
0 siblings, 0 replies; 12+ messages in thread
From: Fred E.J. Linton @ 2008-05-25 15:50 UTC (permalink / raw)
To: categories
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/
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-05-22 16:27 PETER EASTHOPE
0 siblings, 0 replies; 12+ messages in thread
From: PETER EASTHOPE @ 2008-05-22 16:27 UTC (permalink / raw)
To: categories
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/
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-03-03 21:30 wlawvere
0 siblings, 0 replies; 12+ messages in thread
From: wlawvere @ 2008-03-03 21:30 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-03-03 14:37 peasthope
0 siblings, 0 replies; 12+ messages in thread
From: peasthope @ 2008-03-03 14:37 UTC (permalink / raw)
To: categories
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/
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-02-16 12:21 Thorsten Altenkirch
0 siblings, 0 replies; 12+ messages in thread
From: Thorsten Altenkirch @ 2008-02-16 12:21 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-02-16 1:51 Colin McLarty
0 siblings, 0 replies; 12+ messages in thread
From: Colin McLarty @ 2008-02-16 1:51 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-02-16 0:17 Andrej Bauer
0 siblings, 0 replies; 12+ messages in thread
From: Andrej Bauer @ 2008-02-16 0:17 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-02-15 19:08 Matt Hellige
0 siblings, 0 replies; 12+ messages in thread
From: Matt Hellige @ 2008-02-15 19:08 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-02-15 8:18 Paul Taylor
0 siblings, 0 replies; 12+ messages in thread
From: Paul Taylor @ 2008-02-15 8:18 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: A small cartesian closed concrete category
@ 2008-02-15 3:46 Fred E.J. Linton
0 siblings, 0 replies; 12+ messages in thread
From: Fred E.J. Linton @ 2008-02-15 3:46 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* A small cartesian closed concrete category
@ 2008-02-14 20:06 PETER EASTHOPE
0 siblings, 0 replies; 12+ messages in thread
From: PETER EASTHOPE @ 2008-02-14 20:06 UTC (permalink / raw)
To: categories
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/
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2008-05-25 15:50 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-05-16 20:57 A small cartesian closed concrete category Toby Bartels
-- strict thread matches above, loose matches on Subject: below --
2008-05-25 15:50 Fred E.J. Linton
2008-05-22 16:27 PETER EASTHOPE
2008-03-03 21:30 wlawvere
2008-03-03 14:37 peasthope
2008-02-16 12:21 Thorsten Altenkirch
2008-02-16 1:51 Colin McLarty
2008-02-16 0:17 Andrej Bauer
2008-02-15 19:08 Matt Hellige
2008-02-15 8:18 Paul Taylor
2008-02-15 3:46 Fred E.J. Linton
2008-02-14 20:06 PETER EASTHOPE
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).