Real coalgebra

[Peter Freyd <pjf@saul.cis.upenn.edu>]

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.

In the category of posets with top and bottom consider the binary
functor, X v Y, obtained by starting with the disjoint union  X;Y,
with everything in  X  ordered below  Y,  and then identifying the 
top of  X  with the bottom of  Y.  The functor  X v X  preserves the 
terminator (the one-element poset) hence the terminator is its final
coalgebra. So restrict to the category of posets with _distinct_ top
and bottom. The functor  X v X  again has a final coalgebra: this time
it's the closed interval, I.  (For Dusko and Vaughan's functor it's 
the half-open interval. For yet another functor, one that ought to
have the open interval as its final coalgebra, but doesn't, see PS
below.)

If  X v Y  is described as the subobject of the product  X x Y
consisting of those pairs  <x,y>  such that either  x  is top or  y 
is bottom, then a coalgebra structure for  X v X  can be described as 
a pair of endo-functions  d,u  such that for each  x  either  d(x)
is top or  u(x)  is bottom. On the interval  [a,b]  the 
final-coalgebra structure is understood to be given by 
d(x) = min (b, 2x - a)  and  u(x) = max (a, 2x - b).

In fact, we didn't need to start in the category of posets. It would
have sufficed to work in the category of sets with distinct top and
bottom (see PPS below for a proof). The final coalgebra is still the
closed interval and, yes, the ordering is implicit: it is the most 
inclusive relation preserved by  d  and  u  that avoids placing top 
below bottom. (It can also be obtained by constructing either of the 
two lattice operations on  I  as the unique coalgebra map  I x I --> I
for an appropriately chosen coalgebra structure on  I x I.  A similar 
construction works for the Pavlovic-Pratt coalgebra.)

Indeed, all of the structure of the closed interval is definable from
this coalgebra definition. Go back to the category of posets with 
distinct top and bottom. It is routine to verify that  X v X  commutes
with the opposite-poset functor hence -- using the fact that that 
functor is an equivalence -- its final coalgebra will be invariant
under that functor. That is, there is an isomorphism from  I  to its
opposite.

It takes more work, but not an infinite amount, to construct a 
coalgebra structure on  I x I  so that the induced binary operation 
I x I --> I  is the midpoint operation, the values of which will be
denoted here as  x|y.  It is pretty much characterized by the 
equations: idempotence, x|x = x; commutativity, x|y = y|x; and middle-
two-interchange, (u|v)|(x|y) = (u|x)|(v|y); together with cancelation:
a|x = a|y  =>  x = y.  If one chooses a zero, then one may prove that
there's an ambient abelian group with unique division by  2, such that 
the given midpoint algebra is a subset closed under the operation
x|y = (x + y)/2.  (There must be an existent reference for this.) 

Actually we want that ambient abelian group for  I;  it's none other
than the reals. The order-duality makes its construction easier than 
in the general case. So let's use  1  to denote the top of the final
coalgebra, I, -1  for the bottom, and  0  for their midpoint, -1|1.
Let  h:I -> I  denote the "halving" map that sends  x  to  0|x.  Note
that  h  is an endomorphism with respect to  0, the ordering, the 
duality, the midpoint structure (and not, of course, the top and 
bottom). For a moment enter the category of endomorphisms, and reflect
the object  <I, h>  into the full subcategory of automorphisms. (The 
reflection may be explicitly constructed as the colimit of the diagram
   h     h     h
I --> I --> I -->...)  The result is a poset-with-0-and-duality-and-
midpoint-operation we'll denote as  R.  The midpoint operation 
respects the order and commutes with duality.  0  is self-dual. By
making  h  an automorphism we know that for all  y  there is a unique
x  such that  0|x = y.  On  R  define  a + b  by the equation
0|(a + b) = a|b  and verify  0 + b = b = b + 0  and 
(a + b) + (c + d) = (a + c) + (b + d).  Use the duality to define  -a
and verify  (-a) + a = 0.  Use  h  to define  a/2  and verify 
a/2 + a/2 = a.  All of this makes  R  an abelian group with unique
division by  2.

Viewing  R  as an ordered abelian group it is easy to verify that any
endomorphism is determined by where it sends  1  (inherited from 
I -> R).  That, of course, allows us to define the multiplication.

Those who heard my CTCS talk last September at Edinburgh, "Path 
Integrals, Bayesian Vision, and Is Gaussian Quadrature Really Good?",
(there's an abstract at the same website as above) can appreciate why 
I'm particularly happy. I started by defining ordinary integration of
continuous functions using -- without knowing it -- this coalgebra
structure on  I.  Let  C  be the functor that assigns to a space  X
the set, C(X), of continuous real-valued functions on  X.  The 
"mean-value" function  M:C(I) -> R  can be characterized -- indeed,
evaluated -- from its order-preservation together with what it does to
constant functions and
                                                MxM
         C(I v I) -->  C(I + I) --> C(I) x C(I) ---> R x R
  
        C(F) |                                         | m
             v                                         v         
                                 M
          C(I)  ------------------------------------>  R

where  F:I -> I v I  is the coalgebra structure and  m  is the
midpoint operation. If  C(F)  is inverted then this diagram can be 
read as a fixed-point definition of  M.  (It's the unique fixed-point 
of an operator acting on the set of all those order-preserving maps 
from  C(I)  to  R  that do the right thing on constant functions.)


PS
Just for comparison, consider the category of posets and the functor
that sends  X  to  X;1;X.  The open interval is an invariant object 
for this functor but it is not the final coalgebra. For that we need
-- as we called it in Cats and Alligators -- Wilson space. Actually,
not the space but the linearly ordered set, most easily defined as the
lexicographically ordered subset, W, of sequences with values in  
{-1, 0, 1}  consisting of all those sequences such that for all  n 
a(n) = 0  =>  a(n+1) = 0  (take a finite word on  {-1,1}  and pad it
out to an infinite sequence by tacking on  0s).

PPS
Given a coalgebra structure described by endo-functions  d  and  u  on
X, let  End(X)  be the monoid of endo-functions on  X.  We will need 
to compose in the diagrammatic order: "ud" means "first  u  then  d".
Let  {0,1}*  be the free monoid with generators named  0  and  1  and
Let  M_X:{0,1}* --> End(X)  be the monoid homomorphism such that  
M_X(0) = d  and  M_X(1) = u.  Given  x  in  X  let  L  be the subset of 
{0,1}*  consisting of those words  w  such that  M_X(w)  sends  x  to
top in  X.  The elements of  {0,1}*  may, of course, be  viewed as
finite words on  0  and  1.  By catenating  "0."  on the left of any
such word we obtain a description -- in binary -- of a dyadic rational
in the half-open unit interval  [0,1).  Define  f:X -> I  by sending
each  x  to the supremum in  [0,1]  of the dyadic rationals, r(L),
named by the words in its corresponding  L.  The  L  corresponding to
d(x)  can thus be obtained by taking each word in  L  that starts with
0  and deleting that  0.  The resulting  r(L)  can be described by
first throwing away each dyadic rational bounded below by  1/2  and
then doubling each dyadic rational that remains, that is,doubling each
dyadic rational bounded above by both  f(x)  and  1/2.  The resulting 
supremum is thus  min (1, 2f(x)).  That's what  f(d(x))  is. And it's 
also what d(f(x)) is. Same sort of argument for  u.

A little too easy. The recipe above does work for  f  but the proof 
that it works requires work. Note that the above argument requires --
among other things -- that  r(L)  be a downdeal. (And note that it 
never invoked the facts that  d  and  u  preserve top and bottom nor 
the fact that  d(x)  is top or  u(x)  is bottom for all  x.)  I think 
a  return to Dedekind works best. Besides defining the "lower" set, L, 
define the "upper" set  U  as the subset of  {0,1}*  consisting of 
those words  w  such that  M_X(w)  sends  x  to bottom. We have the
facts:
              w:L  =>  w0:L  and  w1:L            (using 
              w:U  =>  w0:U  and  w1:U              ":"
         w:{0,1}*  =>  w0:L  or   w1:U        for membership)

We may infer, just from  w:L => w0:L  and  w:U => w0:U, that if a
dyadic rational has a name in either  L  or  U  then it does not have
a name in the other. Thus we obtain a disjoint pair of sets of dyadic
rationals  r(L)  and  r(U).  For any pair of dyadic rationals 
x,y:[0,1)  where  x is _not_ in  r(L)  and  x < y,  it is the case 
that  y  is in  r(U):  it suffices to check, for any word  w, that if
w0  can be prolonged to a name of  x, then  w0  is not in  L  forcing
w1  to be in  U  and, hence, any prolongation of  w1  to be in  U.  It 
follows that  r(U)  is an updeal and if there's a dyadic rational in
[0,1)  that is in neither  r(U)  nor  r(L)  then there's only one such
dyadic rational, to wit, the greatest lower bound of  r(U).  It
follows that  r(L)  is a downdeal. The pair  r(L)  and  r(U)  thus
forms a Dedekind cut and we can use it to name the value of  f(x). 
The compatibility with  d  and  u  is a straightforward computation.

For uniqueness, first verify that for every pair  a < b  in  I  
there's a word  w:{0,1}*  such that  M_I(w)  sends  a  to bottom and
b  to top. If  f,f':X -> I  were both coalgebra maps, and  x:X  were
such that  f(x) < f'(x)  let  w  be as described. Note that  M_I(w0) =
M_I(w) = M_I(w1).  But either M_X(w0)  sends  x  to top or  M_X(w1)  
sends  x  to bottom. The first case contradicts that  M_I(w0)  sends
f(x)  to bottom. The second case contradicts that  M_I(w1)  sends
f'(x)  to top.