Re: Real interval halving

[Vaughan Pratt <pratt@cs.stanford.edu>]

Thanks, Peter.  One of these days I'll learn to stop sending email after
midnight.  Continued fractions provide equally good coalgebraic structure
for both our product-with-omega functor (it's one of the examples in
our paper) and Peter F.'s X v X functor.  Either midnight madness or
sheer forgetfulness must have possessed me to malign its applicability
to the latter.

While I have that excuse handy let me also repair my description (in
the same message) of halving nonzero reals as right-shifting with sign
extension: following the shift the second bit must then be complemented.
Thus + (1/2) halves to +- (1/2 - 1/4 = 1/4) while +++ (1/2 + 1/4 + 1/8
= 7/8) halves to +-++ (1/2 - 1/4 + 1/8 + 1/16 = 7/16).  In the special
case of 1 as ++++... forever, +-+++... equals + (1/2), and dually for -1.

Contorted fractions make an earlier appearance in Conway's On Numbers
and Games (1976) (Winning Ways is 1983).  I hadn't realized Norton was
involved there: Conway credits several things to Norton in ONAG but I
guess he must have forgotten that one.

At the risk of turning this thread into a complete tangent space, yet
another construction of the group of reals is as the quotient G/H of the
pointwise-additive group G of bounded integer sequences by the subgroup H
consisting of those sequences b of the form b_0 = a_0, b_{i+1} = a_{i+1}
- 2a_i for some a in G.  This definition, which avoids detouring through
the rationals, resulted from my mulling over a talk at MIT by Gian-Carlo
Rota in the early 1970's on representing reals as sequences of bits.
I mentioned it at a recent theory lunch talk and Don Knuth mulled it
over and came up with the idea of modifying the boundedness condition
to allow G to be a ring thus making G/H a field (as an alternative to
taking product to be the unique bilinear operation * satisfying 1*1 =
1), see Problem 10689, American Mathematical Monthly, 105(1998), p.769.

I would love to know whether this construction can exploited in a
coalgebraic setting.

Vaughan Pratt