Apropos of Tom Leinster's attribution to Peter Freyd of the self-similar construction of the continuum, I hope people won't consider it inappropriate to repost the first paragraph of Peter's original posting to this list about his functor.
Date: Wed, 22 Dec 1999 11:49:50 -0500 (EST) From: Peter Freyd <pjf@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: Real coalgebra
I've been looking at the Proceedings of the Second Workshop on Coalgebraic Methods in Computer Science (CMCS'99), Electronic Notes in Theoretical Computer Science, Volume 19, to be found at
www.elsevier.nl:80/cas/tree/store/tcs/free/noncas/pc/menu.htm
There's a nice paper by Dusko Pavlovic and Vaughan Pratt. It's entitled On Coalgebra of Real Numbers and it has turned me on. Their abstract begins:
We define the continuum up to order isomorphism (and hence homeomorphism) as the final coalgebra of the functor X x omega, ordinal product with omega. This makes an attractive analogy with the definition of the ordinal omega itself as the initial algebra of the functor 1;X, prepend unity, with both definitions made in the category of posets.
I thought of using another functor. And damned if it isn't just what I should have had for my CTCS talk last September at Edinburgh.
Self-similarity is a common feature of both functors, indeed it is intrinsic to the construction of the continuum as a final coalgebra. As our functor makes clear, we constructed the continuum as omega many copies of itself abutted without overlap, based on the idea that the ordinal omega is in a sense closed below but open above, a sufficient condition on intervals of reals to abut to form an interval of reals. Peter's very nice contribution was to realize that by allowing the copies to overlap, two copies sufficed. We slapped ourselves on the forehead for not thinking of that. Our nonoverlapping self-similar construction is treated in @InProceedings( PP99, Author="D.~Pavlovi\'c and V.~Pratt", Title="On coalgebra of real numbers", BookTitle="Proc. Coalgebraic Methods in Computer Science", Series="Electronic Notes in Theoretical Computer Science", Volume="19", Address="Amsterdam", Pages="133-147", Year=1999) The longer journal version appeared as @Article( PP02, Author="D.~Pavlovi\'c and V.~Pratt", Title="The continuuum as a final coalgebra", Journal=TCS, Volume=280, Number="1-2", Pages="105-122", Year=2002) Vaughan Pratt PS. I hope people aren't strongly opposed to inventors sticking up for themselves. In the case of the original modal mu-calculus, described in "A Decidable Mu-Calculus," FOCS'81, 442-447, I felt that the judgment of originality should be left to others, it being self-serving for the inventor to so judge. The outcome persuaded me that the alternatives for an author in such a situation were to speak up promptly or run the risk of being forgotten indefinitely (but hopefully not permanently since history constantly rewrites itself to reflect the research, interests, and whims of the historians). De Morgan made a similar judgment call in his celebrated published debate with the other William Hamilton, not only setting the record straight but inspiring Boole to write his even more celebrated 1847 pamphlet introducing Boolean logic. 23-Nov-2004 20:40:13 -0400,27131;000000000000-00000000