Help with Knuth's Surreal Numbers

Question

I'm reading D. E. Knuth's book "Surreal Numbers". And I'm completely stuck in chap. 6 (The Third Day) because there is a proof I don't understand. Alice says

Suppose at the end of $n$ days, the numbers are $$x_1<x_2<\dots<x_m$$

She demonstrates that $x_i \equiv (\{x_{i-1}\},\{x_{i+1}\})$ and she begins the proof by saying

Look, each element of $X_{iL}$ is $\le x_{i-1}$, and each element of $X_{iR}$ is $\ge x_{i+1}$.

That first step of the proof is the one I don't understand. Can someone show me how to demonstrate that statement?

Answer 1

Conway's second rule says that

One number is less than or equal to another number if and only if no member of the first number's left set is greater than or equal to the second number, and [other stuff].

So $x_i=x_i$ implies that no member of $X_{iL}$ is $\ge x_i$; hence every member of $X_{iL}$ is strictly less than $x_i$. With the additional assumption that the only numbers created so far are $x_1 < x_2 < \ldots <x_m$, this means that every member of $X_{iL}$ is $\le x_{i-1}$. The proof that every member of $X_{iR}$ is $\ge x_{i+1}$ is exactly analogous.

Answer 2

An ordered list of numbers in the universe after each day:

Day 0: empty
Day 1: 0
Day 2: -1, 0, 1
Day 3: -2, -1, -1/2, 0, 1/2, 1, 2

New numbers:

Day 1: 0
Day 2: -1, 1
Day 3: -2, -1/2, 1/2, 2

On any given day the universe can be sorted:

$$x_1<x_2<\dots<x_m$$

Sorted list of number on day 3:

-2 < -1 < -1/2 < 0 < 1/2 < 1 < 2

which we assign to be $x_1<x_2<x_3<x_4<x_5<x_6<x_7$

The new numbers on day 3 being:

-2, -1/2, 1/2, 2

which are the value of elements x1, x3, x5, x7 from our sorted list

The book says: $x_i \equiv (\{x_{i-1}\},\{x_{i+1}\})$

For day 3, it means:

x1 = {  {},{x2}}
x3 = {{x2},{x4}}
x5 = {{x4},{x6}}
x7 = {{x6},{}  }

Which can be written with values as:

-2 = {|-1}
-1/2 = {-1|0}
1/2 = {0|1}
2 = {1|}

Each element of $X_{iL}$ is $\le x_{i-1}$, and each element of $X_{iR}$ is $\ge x_{i+1}$.

This says that there is a longer form for writting these left and right sets:

x1 = {{},{x2,x4,x6}
x3 = {{x2},{x4,x6}}
x5 = {{x2,x4},{x6}
x7 = {{x2,x4,x6},{}}

Which can be written with values as:

-2 = {|-1,0,1}
-1/2 = {-1|0,1}
1/2 = {-1,0|1}
2 = {-1,0,1|}

I don't have the book, but I think the conclusion it is getting to is that each finite surreal number has a short representation with only one number in the left set and one number in the right set.

This means for example that we could write the finite surreal number -1/2 as:

-1/2 = {-1|0,1}

but that we only need to write:

-1/2 = {-1|0}

Any finite surreal value is fully defined by the single greatest number from its left set and a single smallest number from the right set

Since the entire universe of numbers available on the previous day are place into either the right and left set of new numbers, the full representations become very large. And since all mathematical operations on the shortened versions work the same as using the longer versions, there is an incentive to use this short form while operating with finite surreal numbers.

For example I could write a surreal representation:

3/256 = { 1/128 | 1/64 }

Where left and right are the decrement and increment of the numerator of the original number:

3/256 = { (3-1)/256 | (3+1)/256 }

While the long form would involve writing 1023 numbers instead of two