Real coalgebra

Real coalgebra

[Peter Freyd]

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.

Re: Real coalgebra

[Vaughan Pratt]

Apropos of Peter's kind remarks, the journal version of our paper
should be in TCS soon, entitled The continuum as a final coalgebra.
Meanwhile it's on the web as

        http://boole.stanford.edu/pub/continuum.ps.gz

Abstract:
We define the continuum up to order isomorphism, and hence up to
homeomorphism via the order topology, in terms of the final coalgebra
of either the functor NxX, product with the set of natural numbers, or
the functor 1 + NxX.  This makes an attractive analogy with the
definition of N itself as the initial algebra of the functor 1 + X,
disjoint union with a singleton.  We similarly specify Baire space and
Cantor space in terms of these final coalgebras.  We identify two
variants of this approach, a coinductive definition based on final
coalgebraic structure in the category of sets, and a direct definition
as a final coalgebra in the category of posets.  We conclude with some
paradoxical discrepancies between continuity and constructiveness in
this setting.


PF>So restrict to the category of posets with _distinct_ top and bottom.

...which has no final object, making the following all the nicer:

PF>The functor  X v X  again has a final coalgebra:

The bipointed-set version of this seems like *the* right way to generate
the topology of the continuum.  Verry nice.

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

In other words the continuum plus *two* additional copies of each rational
(as opposed to Cantor space's one additional copy).

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

Here I should be understood as [-1,1].  Peter's implicit definition
of this coalgebra structure on I x I has the following equivalent
five-equation explicit definition (or seven if you count each of (3)
and (4) as two equations).  My apologies to anyone reading this with a
variable-width font.

                  x + y        y + x
(1)               -----    =   -----
                    2            2

                  0 + 0
(2)               -----    =   0
                    2
                                   
                xo1            x + t
                --- + 0        -----o1    where the 2 o's are + and t is -1
(3)              2         =     2           or the 2 o's are - and t is 1
                --------       -------    (o = operator, t = terminator)
                    2             2

               xo1   yo1       x + y
               --- + ---       -----o1       where the 3 o's are either
(4)             2     2    =     2             all - or all +
                -------        -------
                   2              2

                x-1   y+1      x + y
                --- + ---      ----- + 0
(5)              2     2   =     2
                 -------       ---------
                    2              2

All these equations clearly hold on I; the question is, what is their
content?  Well, spacing around + and - is significant: without a space the form
x-1        x+1
--- (resp. --- )  denotes a non-middle (nonzero) element of I which when
 2          2
represented as a string over {-1,0,1} has head -1 (resp. 1) and tail x,
                            x + y
while with a space the form ----- denotes a pair (x,y) of I x I.
                              2
Finally, if -1, 0, or 1 (which includes t) are preceded by a space then
they denote the respective infinite constant sequences -1,-1,-1,... or
0,0,0,.. or 1,1,1... (each of which has that constant as its value).
(Once a sequence hits a zero it stays zero.)

The left hand side always has exactly one spaced +, and at the outermost
level, since that's what we're trying to define.  On the right hand
side, each occurrence of a spaced + denotes a corecursive call (so two
corecursive calls in the last equation --- it might seem like a lot of
bother to do a corecursive call merely to add 0, but the real point of
the second call is of course to divide the result of the first call by 2,
which we can do by taking the mean with 0.)

Equation (1) merely ensures that any pair (x,y) will match the left
hand side of one of (2)-(5) one way round or the other.  Equations
(2)-(4) provide instant gratification inasmuch as they allow immediate
production of the first "trit" (ternary digit) of the mean of x and y
given only the first trit of each of them, thereby explicitly defining
the desired coalgebra structure on I x I.  But if you hit equation (5)
you may be in for a long or even infinite wait (consider taking the mean
of -1,1,-1,1,...  (= -2/3) with 1,-1,1,-1,... (= 2/3), which to us is
obviously zero but not so obviously to equation (5)).  So equation (5)
does not give the coalgebra structure at this part of I x I explicitly,
one must regrettably deduce it by corecursion.

Vaughan

Re: Real coalgebra -- replacing equations by geometry

[Vaughan Pratt]

The continuum is intrinsically geometrical, so it is a shame to specify
Peter's midpoint coalgebra on IxI with a mess of algebraic-looking
equations as per my previous message when it has a relatively short and
transparent geometric specification.  (I must have got this idea from
the paper on higher dimensional automata that I'm just finishing up.)

Incidentally there were two ambiguities in my equations, arising from
respectively equations (1) and (5).  I was going to offer fixes for
these, but one of the degeneracies that made these ambiguities possible
in the first place (that with (5)) does not even arise in the geometric
presentation, while the other, arising with (1), is just as readily
dealt with geometrically as algebraically.

In the following I'll refer to this coalgebra as Fm for Freyd's midpoint
(unrelated to Scott's bottom).  (For listeners who just tuned in to Fm,
its role is to promote the final coalgebra I of Peter's fusion functor
X v X from a linear order, and hence a topological space via the order
topology, to a metric space understood as the real interval [-1,1].
It does this by furnishing IxI with a coalgebra, which determines a
unique coalgebra homomorphism from IxI to I, I being the final coalgebra.
This homomorphism is then taken to be (x+y)/2, while the endpoints of
I are taken to be -1 and 1, thereby uniquely determining a continuous
metric on I qua topological space.)

For both the equational and geometric specifications, here's what the
domain and codomain of Fm look like.


                                                    (1,1)
                IxI                                   ^
                                                     / \
                                                    /   \
                (1,1)                        (1,-1)<  1  >(-1,1)
                 /\                                 \   /
                /  \                Fm               \ /
         (1,-1)<    >(-1,1)   ------------->          0      IxI v IxI
                \  /                                 / \
                 \/                                 /   \
              (-1,-1)                        (1,-1)< -1  >(-1,1)
                                                    \   /
                                                     \ /
                                                      V
                                                   (-1,-1)

So Fm maps pairs of the form (x,-x) to 0 (where the two copies of IxI
are fused) and all other pairs (x,y) to a pair (h,(x',y')) whose head h
specifies which copy of IxI to land in, 1 for upper and -1 for lower, and
(x',y') gives the landing point within that copy.  Here -1 <= x,y,x',y' <= 1, 
-x is defined by changing all the signs on the sequence representing x
and h is unproblematically determined by whether (x,y) is in the upper
or lower half of IxI oriented as shown.  The tricky part is to specify x'
and y' reasonably.

(Although it is convenient to think of x and y as reals in [1,-1], at
this stage they are merely infinite sequences over {-1,0,1} with the
properties that once zero alway zero and infinite runs of -1 or 1 are
only allowed in constant sequences.)

The domain of Fm, namely I x I, can be blown up as


			    (1,1)
			     /\
			    /  \
			 (1,0) (0,1)
			  / \  / \
			 /   \/   \
		  (1,-1)<   (0,0)  >(-1,1)
			 \   /\   /
			  \ /  \ /
			(0,-1)  (0,1)
			    \  /
			     \/
			  (-1,-1)


In my previous mess-age, my five equations implicitly decomposed this
domain into nine regions, namely the midpoint (0,0) (equation (2)), the
four lines leading out of it (equation (3)), the upper and lower diamonds
(equation (4)), and the left and right diamonds (equation (5)).

For the geometric description of Fm, a simpler decomposition suffices,
namely three regions: the upper and lower diamonds as one region, call
it M for Middle, and the interior of each side diamond along with its
outer sides, call them L and R.  (So M is closed and L + R = IxI - M.)


			       (1,1)
				/\
			       /  \
	       .            (1,0) (0,1)          .
	      / .              \  /             . \
	     /   .              \/             .   \
      (1,-1)<  L  .         M  (0,0)          .  R  >(-1,1)
	     \   .              /\             .   /
	      \ .              /  \             . /
	       .           (0,-1)  (0,1)         .
			       \  /
				\/
			     (-1,-1)


In addition we need one more region, S for Shrunk, as a subregion of
IxI v IxI, shown below.  S is simply IxI v IxI shrunk in half (or pushed
twice as far away).

                                /\
                               /  \
                              /    \
                             /      \
                             \  /\  /
                              \/S \/
                               \  /
                                \/     IxI v IxI
                                /\
                               /  \
                              /\ S/\
                             /  \/  \
                             \      /
                              \    /
                               \  /
                                \/


We now describe Fm as follows.  Its restriction to M is the evident
similarity between M and IxI v IxI.  And its restriction to each of L
and R lands in S, and in each case is the whole of Fm shrunk in half
(the corecursion is essential, not even geometry can eliminate it).

Note that these maps are defined on sequences, i.e. we are not assuming
the metric we set out to construct.

Fm as defined is not commutative, but can be made so by composing its
restriction to L with commutativity of (x+y)/2, viz. reflection of L about
its central vertical axis, thereby symmetrizing Fm.  (This commutativity
ambiguity also arose via equation (1) of my 5-equation approach.)
This symmetrical Fm would appear to be the canonical choice for Freyd's
midpoint coalgebra.  (The apparent competitor obtained by reflecting
R instead of L is slightly more discontinuous, if that's a reasonable
tie breaker.)

This coalgebra is of course not final, nor is it even injective, though
it is surjective, witness subdomain M.  It is also not continuous:
points near (1,0) in L go to points near (1,(0,0)) in IxI v IxI, while
points near (1,0) in M go to points near (1,(1,-1)) in IxI x IxI.
On the other hand points near (1/2,0) in both M and L.M (the M of L)
go to points near (1/2,0) in IxI v IxI, which has no counterpart in the
above-mentioned competitor.

Question.  Is there a corecursively defined Freyd midpoint coalgebra
that is continuous?

(x,y) |--> ((x+y)/2,(x+y)/2) (projection onto the center axis) is a
continuous midpoint coalgebra, but that assumes the metric before we've
defined it.  What corecursion would define this?

Vaughan