Coming back from games to numbers, I promised earlier that I would define
division. Division in surreal numbers is, unfortunately, ugly. We start with
a simple, basic identity: if a=b×c, and a is not zero, then c=a×(1/b). So if we can define how to take the reciprocal of a surreal number, then division falls out naturally from combining it the reciprocal with multiplication.
This is definitely one of my weaker posts; I’ve debated whether or not to post it at all, but I promised that I’d show how surreal division is defined, and I don’t foresee my having time to do a better job of explaining it in a reasonable time frame.. So my apologies if this is harder to follow than my usual posts.
We can define the reciprocal for surreals. It’s an iterative process, which will eventually converge on a solution, where eventually is defined in surreal terms… meaning
that it might take forever to get the exactly answer. (After all, many simple reciprocals – e.g., 1/3, aren’t born until generation ω, so starting from 3 (which is a third generation number), we need to follow the procedure until we can get to generation ω numbers.)
To make notations easier, let’s say we have a number x. What we want to do is
find a number y such that xy=1.
We’ll define reciprocal only for positive numbers – we can derive it for negative numbers using multiplication. Our first step is to “normalize” x. What that means is, convert x into a form where ∀n∈xL, 0≤n. The normal form
of any positive number contains 0 and other positive numbers in its left set – and obviously, only positive number in its right set.
So if we have x in normal form, then we can say y={0,L1,L2|R1,R2} where:
- L1 = (1+(xR-x)yL)/xR
- L2= (1+(xL-x)yR)/xL
- R1=(1+(xL-x)yL)/xL
- R2=(1+(xR-x)yR)/xR
Just looking at that, you can see the recursion in it – it involves divisions by xL and xR; and the definition of y itself involves the left or right sets of y. Basically, you keep computing values of Y – each step, you get closer.
Conway uses 1/3 as an example. Start with x=3={0,1,2|}. y={0,1/2(1-yR)) | 1/2(1-yL). If we start with yL=0, and then iterate, we’ll get y={0,1/4,5/16,…|1/2,3/8, …}.
Unfortunately, I can’t give you much in the way of intuition for why this works. I can barely wrap my head around it. The only way to really get it is to work through some
examples; but even doing example, the book-keeping is a nightmare. I tried to do an example on my own to show you how it works for a number where it will converge relatively quickly, but I keep losing track of where I am…
Fortunately, in some sense, it doesn’t matter. The important thing to know is that you can define division in a valid way for the surreal numbers; you can prove that the reciprocal exists for any surreal number except zero; the reciprocal of zero is undefined using this definition; and that the result of surreal division using surreal reciprocals is provably exactly the same as the result of division using the traditional version of the real numbers.
Oh ye master of the quick Haskell program, wouldn’t this be a great place to write a program that did surreal arithmetic, and use the output as your example? 🙂
Billb:
Yes,It would, when I have time… I’m just not sure when that will be.
As for an intuition of why this works, you’re simply generating a series whose limit is the required element. Since you want to use finitely generated numbers, and it is easiest to comprehend the sequence if it is increasing (on the left sequence) and decreasing (on the right sequence), you can simply check each denominator which is a power of two and check what the correct numerator closest to the goal is.
Example:
Starting with 2, there is no positive fraction with denominator 2 less than 1/3, so we skip that. Then for four, we have 1/4 is less than 1/3, so that is the first number in the series. Then for 8, the nearest fraction with denominator 8 that is less than 1/3 is 2/8, but we already included that as 1/4. So we move to 16. 5/16 is the closest fraction over 16 that is less than 1/3. At 32, we would have 10/32, but this is 5/16, so we’ll skip that, and move on to 21/64, etc.
On the right, the same process occurs. 1/2 is greater than 1/3. The closest fraction over 4 that is greater than 1/3 is 2/4, already included. The closest fraction over 8 that is greater than 1/3 is 3/8. The closest fraction of 16 that is greater than 1/3 is 6/16, already included. The closest fraction of 32 that is greater than 1/3 is 11/32.
SO we get {1/4, 5/16, 21/64, etc | 1/2, 3/8, 11/32, etc.} for 1/3.
You can generate any real number in the same fashion via pen and paper, by either converting it to binary decimals and simply taking successively more binary decimal digits that end in 1 (for the left side) or by taking successively more digits that end in 0 and turning the final zero into a 1 (for the right side).
Alternatively, you can od it by converting the fractions over powers of two to decimal form and choosing succesively closer ones to your goal (for either side).
And to further expand my comment, that is why the example for 1/3 works the way it does.
In general, you want to create a series of *previously created* numbers whose limit is the number desired. fractions where the divisor is a power of 2, they are created by a finite process, so we can just list the last number on each side (the ones of the previous generation bigger and smaller than it). IE, if we’re expressing the fraction a / 2^b, we express it as { (a-1)/2^(b-1) | (a+1)/2^(b-1)}.
For any real number fraction not of this form, it is in the generation w+1, and so can be expressed as I showed above, using the infinite series of fractions over a power of 2 approaching it from both the right and the left.