Subject: categories: Re: squares and cubes

From: Dusko Pavlovic <[email-masked]>
Date: Sat, 15 Jan 2000 21:35:47 -0800

hi.

i somehow managed to unsubscribe from this list at some point, and almost
missed the thread about coalgebra of reals. i am not sure that i have seen
all the relevant postings, but here are my 2p of thoughts.

if i am not misunderstanding anything, peter freyd's closed interval
coalgebra achieves something that vaughan pratt's and mine do not. we work
with lists and streams and get *irredundant* representations of reals.
however, without redundancy, the algebraic operations on reals are
undecidable. peter's bipointed approach, however, induces a *redundant*
representation. this allows him to extract the algebraic operations
coinductively.

in the talk at the 1998 lisbon workshop on coalgebra (and later in some
seminar talks), i described a redundant coalgebra of conway reals, where
conway's definitions of the field operations were derivable as coalgebra
homomoprhisms. however, the setting seemed too complicated, probably due
to me. peter's definition of the midpoint algebra is considerably simpler,
although the resulting operations are probably still computationally quite
inefficient.

the coalgebra of alternating dyadics, described in the paper with vaughan,
was derived from this 'conway' coalgebra. as explained in sec 3.4, it
provides the best dyadic approximation, while the continued fraction
coalgebra, provides the best rational approximation. presumably, it can be
derived from the 'norton' coalgebra (contorted fractions), mentioned by
peter johnstone. there are as many redundant coalgebras of reals, as there
are corresponding irredundant ones (one for every interval partition), for
fast outputs.

i think that some of the mentioned *mysteries* about the maps between
these various representations boil down to the fact that they are
coalgebra isomorphisms, that do not preserve the derived structure, but
rather *transform* it. eg, the laplace transform is a coalgebra
isomorphism between the coalgebra of analytic functions and a dual
coalgebra of meromorphic functions --- whereby the convolution ring gets
transformed into a multiplicative domain, etcetc.

in any case, when you are done with reals, you may be interested to have a
look int my paper with martin escardo "calculus in coinductive form",
LICS98, or
ftp://ftp.kestrel.edu/pub/papers/pavlovic/LAPL.ps.gz

all the best,
-- dusko

PS along the lines of peter's bipointed construction (and also to check
whether i understood it):

* bipointed sets are the algebras for the functor 2+(-) :
Set -> Set.

* bipointed sets with two _distinct_ points are the free such algebras. so
lets work in the kleisli category *K* for 2+(-). write 2 = {0,1}

* the bifunctor (-) v (-) : *K* --> *K* maps

    * the objects X, Y to X + {m} + Y
    * the arrows X --f-->2+U and Y--g-->2+V to

        h : X+{m}+Y ---> 2 + U+{m}+V

        h(x) = f(x) if f(x) = 0  or f(x) in U
        h(x) = m if f(x) = 1
        h(M) = m
        h(y) = g(y) if g(y) = 1 or g(y) in V
        h(y) = m if g(y) = 0

* now (0,1) is the final coalgebra for the functor X v X on *K*. the
coalgebra structure

        (0,1) ---> 2+(0,1) +{m}+(0,1)

maps 1/2 to m, x<1/2 to 2x and x>1/2 to 2x-1.

* the finality is now easy to prove directly, by displaying the
anamorphism for any given coalgebra X -r-> 2+X+{m}+X. ditto for the
algebraic structure.

---

From: Vaughan Pratt <[email-masked]>
Date: Sun, 16 Jan 2000 21:45:50 -0800

From: Dusko Pavlovic <[email-masked]>
>representation. this allows him to extract the algebraic operations

I am deeply embarrassed at not drawing this inference myself.  I noticed
the felicitous identification of 0111... and 1000... but the importance of
the resulting redundancy didn't click.  That the whole process happened
in one step led me to think that the representation was as irredundant
as all extant one-step constructions.  The fact that addition is easier
to define with Peter's functor than with ours should have been a big hint.

Redundant representations for fast computer arithmetic have been in wide
use since the 1960's.  The Wallace tree, long available in chip form,
leverages the idea to multiply n bit integers with log n circuit delay.
(Chris Wallace is an Australian computer scientist who came up with
this idea while working on Illiac 2 at the University of Illinois.)
The actual multiplication takes half the time, the other half is spent
performing the identification step at the end, namely by putting the
result into canonical form.

All redundant representations of the reals that are or could be used
in computer architecture require a separate step to identify the
redundant representations.  For example Schanuel's recently discussed
almost-additive sequences of integers redundantly represent the reals,
and must be quotiented in order to represent them irredundantly.  By the
same token the group of bounded sequences that I mentioned does the
same, and it too must be quotiented in a separate step, in this case by
a subgroup expressing 2(x/2) = x.

Peter's final coalgebra performs the identification in the same step in
which the reals are created.  I am fairly confident there is no precedent
for such a one-step construction of the reals in which the representation
is redundant.

Vaughan Pratt

---

From: Vaughan Pratt <[email-masked]>
Date: Sun, 16 Jan 2000 21:45:50 -0800

Vaughan Pratt

---

From: Vaughan Pratt <[email-masked]>
Date: Mon, 17 Jan 2000 16:57:47 -0800

>to define with Peter's functor than with ours should have been a big hint.

Well, maybe not so embarrassed after all.  Although there is some
redundancy, as Peter Selinger pointed out to me (in the same message where
he pointed out the problem with 1->3) there isn't enough redundancy to
make the function constituting Peter F.'s midpoint coalgebra computable,
at least not corecursively.

Given say -++---+-++... and +--+++-+--... (two complementary reals x and
-x, which must therefore sum to zero), if they stay complementary forever
one can output either of +---------... or -+++++++++... forever, with
one output bit per input bit.  These two infinite sequences redundantly
represent zero (as does the empty sequence).  Furthermore if one pictures
oneself as outputting both infinite sequences (justified by the idea that
in the limit they become the same real), then one can discard the "wrong"
one when it is discovered that the two inputs aren't complementary.
Addition defined corecursively in this way is effective.

But while this is computationally appealing, technically speaking it
isn't quite coinduction, which makes no provision for hedging one's bets
by carrying along both possibilities when you can't make up your mind.
To make traditional redundant computer arithmetic work coinductively,
more redundancy is needed.

To that end I tried tripointed sets, calling the constants -,0,+, along
with a functor 3(X) that makes not two but three copies of X and pastes
their constants together as follows:

	-  0  +
	   -  0  +
	      -  0  +
	-------------
	-  .  0  .  +

The idea is that the constants denote -1, 0, and 1 respectively and that
3(I) somehow is isomorphic to I, with the two dots becoming -1/2 and 1/2
respectively.  But for that to work 3(-) would have to paste a lot more
points than it does.

So this seems like a nice question: is there a category C and a functor
F:C->C whose final coalgebra is the continuum with sufficiently redundant
coalgebraic structure to permit addition to be defined coinductively?

Vaughan