Date: Wed, 22 Dec 1999 11:49:50 -0500 (EST) From: Peter Freyd 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. 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 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 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. Subject: categories: Re: Real coalgebra Date: Fri, 24 Dec 1999 04:13:57 -0800 From: 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 Subject: categories: Re: Real coalgebra -- replacing equations by geometry Date: Fri, 24 Dec 1999 13:59:52 -0800 From: 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 Date: Sun, 26 Dec 1999 13:45:08 -0500 (EST) From: Peter Freyd Subject: categories: Real midpoints It could well be that Vaughan and I are defining the midpoint structure in the same way. Here's how I described it (using the conventions from my last posting). Let F:I --> I v I be a final coalgebra. We will denote the top of I as T and the bottom as B. Construct the "halving" map, h:I --> I, (on [-1,1] it will send x to x/2) as: T v F v B F'v F' F' I --> 1 v I v 1 ------> I v I v I v I ---> I v I --> I where F' denotes the inverse of F, and, by a little overloading, T and B denote the maps constantly equal to T and B. The leftmost map records the fact that the terminator is a unit for the ordered-wedge functor. Let g be the endo-function on I x I defined recursively by: g = if dx = T and dy = T then else if dx = T and uy = B then h(g(dx,uy>) else if ux = B and dy = T then h(g) else if ux = B and uy = B then . The values of g lie in the first and third quadrants, that is, those points such that either dx = dy = T or ux = uy = B. The two maps g d x d g u x u I x I --> I x I --> I x I and I x I --> I x I --> I x I give a coalgebra structure on I x I. The midpoint operation may be defined as the induced map to the final coalgebra. Subject: categories: Re: Real midpoints Date: Wed, 29 Dec 1999 00:03:53 -0800 From: Vaughan Pratt From: Peter Freyd >It could well be that Vaughan and I are defining the midpoint structure >in the same way. Yes, after changing g(dx,uy) to g(ux,dy) in line 2 of Peter's definition of g and similarly for line 3 (otherwise g(dx,uy) simplifies to the nonsensical g(T,B)) Peter and I have essentially the same coalgebra on IxI, and exactly the same after some inessential permutations within that definition. While I rather like Peter's nonrecursive definition T v F v B F'v F' F' I --> 1 v I v 1 ------> I v I v I v I ---> I v I --> I of the halving map h:I --> I sending x to x/2, it should be remarked that the effect of this map as an operation on sequences is to preserve the empty sequence, and for nonempty sequences simply to prepend a copy of the leading digit, e.g. -++-+000... becomes --++-+000.... (This takes the 3-symbol alphabet for Peter's number system to be {-,0,+}.) In other words, right shift by one with sign extension, a well-known realization of halving. Along the same lines, Peter's d and u maps shift the sequence left. If d (resp. u) shifts a + (resp. -) off the left end, the result is replaced by the constantly + (resp. -) sequence, i.e. "clamp overflow to +1 (resp. -1)". Although the interval [-1,1] goes naturally with Peter's final coalgebra, it occurrs to me that a fragment of Conway's surreal numbers is perfectly matched to it, namely the interval [-\omega,\omega] consisting of the real line plus two endpoints. With respect to the Conway story this can be described as what Conway produces by day omega, modulo infinitesimals (identify those surreals that are only infinitesimally far apart). At no day does exactly the real line appear in Conway's scenario. Prior to day omega only the finite binary rationals have appeared. Day omega sees the sudden emergence of all the reals along with 1/omega added to and subtracted from each rational, as well as -omega and omega. Except for -omega and omega, the quotienting eliminates the 1/omega perturbations, yielding exactly the real line plus endpoints. Exactly the same quotienting happens with Peter's final coalgebra, whose elements are representable as finite and infinite strings over {-,+} (the 0 is eliminated by allowing strings to be finite; if you want all strings to be infinite, put 0 back in the alphabet and use it to pad the infinite strings to infinity). For example ---+++++... and --+----... are identified by both Conway and Freyd. Using Peter's choice of [-1,1] as the represented interval, these are both -1/4. Using Conway's number system, these are respectively -2 - 1/omega and -2 + 1/omega, which with the identification I described above become -2. In Conway's setup the finite constant sequences are the integers, with the empty sequence being 0 and counting being done in unary. At the first sign reversal the bits jump mysteriously from unary to binary, not by fiat but as a surprising consequence of a definition of addition that on the face of is so natural that you would not dream it could cause a radix jump like that. So both [-1,1] and [-omega,omega] each admit a natural final coalgebra structure for Peter's functor, namely Peter's and Conway's respectively, and I would be surprised to see a different final coalgebra in either case that was as natural. In contrast, Dusko and I exhibited a number of more or less equally convincing final coalgebra structures on [0,1) and [0,omega) for the functor product-with-omega, no one of which I would be willing to call *the* right one. Vaughan Date: Fri, 31 Dec 1999 17:54:56 -0500 (EST) From: Peter Freyd Subject: categories: Pre-calculus Starting with the closed interval, regarded as an ordered midpoint algebra with duality, what's the best way to get the reals? My previous answer was first to reflect the midpoint algebra in the subcategory of abelian groups and then define the multiplication via monotonic endomorphisms. I think there's a more natural way. First, a re-cap of the definitions. A midpoint operation is a binary operation, with values here denoted as x|y, satisfying: idempotence, x|x = x; commutativity, x|y = y|x; middle-two-interchange, (u|v)|(x|y) = (u|x)|(v|y); and cancelation, x|y = x|z => y = z. The closed interval is a totally ordered midpoint algebra with anti-involution, with values here denoted as -x. It follows that there's a unique element of the form (-x)|x. We'll call it the center. The middle-two-interchange law is just what is needed to see that the monoid of midpoint-endomorphisms is itself a midpoint algebra (where the midpoint of f and g is defined pointwise: (f|g)(x) = (fx)|(gx)). If f and g are both order-preserving or both order- reversing then it's easy to see that so is f|g. But we'll want all the _monotonic_ endomorphisms (the OED defines "monotonic" as "varying in such a way that it either never increases or never decreases") and there's no apparent reason to expect that monotonicity is preserved by midpointing. The wonderful fact, though, is: Midpoint-preserving functions between intervals are monotonic. (The axiom of choice yields 2^{2^N} counterexamples if the interval is replaced by the reals.) It follows that a midpoint-preserving function is determined by its values on any two points. The monoid of midpoint- and duality- preserving endo-functions on a closed interval is naturally isomorphic (via evaluation at Top) to the closed interval. For the entire reals use the stalk at the center of the germs of such functions. PS For a proof suppose that f:[-1,1] --> [-K,K] preserves midpoints and duality. For any x:[-1,1] and dyadic rational q such that qx:[-1,1], we may uniquely identify qx using just midpoints and duality, hence f(qx) = qf(x). Suppose that f is not monotonic. We wish to reach a contradiction. Let u < v and x < y in [-1,1] be such that fu < fv and fx > fy. Define a = (-u)|v and b = (-x)|y to obtain a,b > 0 and fb < 0 < fa. Let q > 0 be a dyadic rational such that a/b - (fa)/(bK) < q < a/b and define c = (-qb)|a. Let r be a dyadic rational such that (2K)/(fa) < r < 1/c. Then rc is in [-1,1] but f(rc) can not be in [-K,K] (because fc > (fa)/2). The theorem I stated doesn't say anything about preserving duality. So let g be a midpoint-preserving function between intervals. Let a be the dual of the value of g at the center. Then the function \x.a|(gx) preserves the center and continues to preserve midpoints. Since -x may be uniquely identified by (-x)|x = 0 the preservation of the center implies preservation of the duality and \x.a|(gx) is monotonic. Since \y.a|y not only preserves but reflects the order, we know that g is monotonic.