Surreal Numbers and Games/The Beginning

From Wikibooks, open books for an open world
Jump to: navigation, search

Day 0[edit]

We begin with the definition of a surreal number:

Axiom 1
  1. Every surreal number corresponds to two sets of previously created surreal numbers, called the left set and the right set.
  2. No member of the left set may be greater than or equal to any member of the right set.

We will use lowercase letters to denote surreal numbers, and uppercase to denote sets of surreal numbers. If x is a surreal number, then X_L and X_R are its left and right sets respectively, and we denote it as x:=\{X_L|X_R\}

Thus, a surreal number is derived from two sets of previously created ones. So far we don't have any surreal numbers with which to create any new ones, nor do we have a definition of "greater than or equal to" to ensure the ones we do fulfil the second part of Axiom 1. But we already have enough to begin creating surreal numbers, because we can start by taking X_L and X_R to both be the empty set \varnothing, containing no surreal numbers. So we can create \{\varnothing|\varnothing\}, and we can show that it is indeed a surreal number.

Is it true that no member of the left set is greater than or equal to any member of the left set? Yes, it is. It's trivially true, because the left set \varnothing has no members at all, and this is enough to prove that \{\varnothing|\varnothing\} is a well-formed surreal number. It is not even necessary yet to know the meaning of "less than or equal to".

We will call our first surreal number "0", for reasons that will become clear later: 0:=\{\varnothing|\varnothing\}. Do not confuse the zero symbol 0 with the symbol for the empty set \varnothing.

Day 1[edit]

Now that we have created a surreal, we can use it as the left or right sets of new surreal numbers. There are three possibilities: \{0|\varnothing\}, \{\varnothing|0\}, and \{0|0\}. We have to check whether these objects are well-formed. For the first, we need to show that no member of \varnothing is less than or equal to any member of \{0\}, which is again trivially true.

Exercise 1

Show that \{\varnothing|0\} is a well-formed surreal number.

Exercise 2

If x is a surreal number, show that \{\varnothing|x\} and \{x|\varnothing\} are also surreal numbers.

From Exercise 2, it is clear that we can create an infinite amount of surreal numbers. But let's go back to the three objects we were discussing. Is \{0|0\} a surreal number? If so, then no member of \{0\} (the right set of \{0|0\}) is less than or equal to \{0\} (the left set). In other words, \{0|0\} is a surreal number if zero is not less than or equal to itself. We expect that zero is less than or equal to itself (making \{0|0\} not a surreal number), but this has to be proven. Now, finally, we require the definition of "less than or equal to":

Axiom 2

Given two surreal numbers x and y, we say that y is less than or equal to x (y\leq x) if and only if x is greater than or equal to y. We say x is greater than or equal to y (x\geq y) if and only if no member of X_R is less than or equal to y and x is less than or equal to no member of Y_L.

Once again, we find a concept defined in terms of itself, but again we will find that this is enough to get the result we require. Now, is 0\le 0? From Definition 2, that will be true if no member of 0_R is less than or equal to 0 and 0 is less than or equal to no member of 0_L. But both 0_R and 0_L are the empty set so this claim is true. Thus 0\le 0, as we expect, and so \{0|0\} is not a surreal number. It does not satisfy point 2 of Axiom 1. We call such objects pseudo-numbers and not well-formed. This one is called *, and is of importance in game theory. We will encounter it again in a later chapter. Naturally, pseudo-numbers can contain other pseudo-numbers in their left and right sets.

At the end of the first day, therefore, we have a grand total of three surreal numbers: 0, and the two new ones \{\varnothing|0\} and \{0|\varnothing\}. We will give the two new ones names:

  • -1:=\{\varnothing|0\}
  • 1:=\{0|\varnothing\}

Before we move on to Day 2, let us define some more binary relations on surreal numbers.

Definition 1: Binary relations
Symbol Meaning
x\leq y  x is "Less than or equal to" y, as defined in Axiom 2
x\geq y  x is "Greater than or equal to" y, as defined in Axiom 2
x\not\leq y x\leq y is false
x\not\geq y x\geq y is false
 x = y x\leq y and y\leq x
 x < y  x \leq y but  y\not\leq x
 x > y  x \geq y but  y\not\geq x
 x \neq y x = y is false
 x \not < y  x < y is false
 x \not > y  x > y is false
Exercise 3

Show that 0=0.

We can do more with our definitions of inequality than just determine whether an object is a properly formed surreal number. We can also give sets of previously created numbers a proper ordering, that is, sort them into ascending order. Let's take the three surreal numbers we have created; we will show that -1 < 0 < 1. From the definition of "<", we need to show first that 1 \leq 0 and then that 0\not\leq 1.

For the first stage we need to show that no member of 0_R is greater than or equal to 1 (trivially true because 0_R=\varnothing), and that 0 is less than or equal to no member of the left set of 1 (again, trivially true because the left set of 1 is empty). That completes the first stage of the proof. For the second stage, we need to show that

  • at least one member of the right set of 1 is greater than or equal to zero or
  • that 1 is less than or equal to at least one member of the left set of 0.

But you showed as part of Exercise 3 that 0, which is a member of the right set of 1, is greater than or equal to 0. This establishes the second part of the proof; we now know that 0 \leq 1 and that 1 \not\leq 0. In other words, 0<1.

Exercise 4

Show that -1<0.

Exercise 5

Show that -1 < 1. You cannot use the transitive law of inequality because we have not yet proved it for surreal numbers.

Note that we have now established the transitive law of inequality for the first three surreal numbers. That is, for any three surreal numbers x,y,z created on or before Day 1, such that x<y and y<z, we also have x<z. This fact is important. On later days we will use it to prove that the transitive law holds for any three surreal numbers.

Day 2[edit]

Now that we have three surreal numbers, we can create a host of new objects. For completeness, the different sets of surreal numbers are:
\varnothing, \{-1\}, \{0\}, \{1\}, \{-1,0\}, \{-1,1\}, \{0,1\}, and \{-1,0,1\}. That is eight different sets, each of which could possibly form the left or the right sets of a surreal number, so there are potentially 64 objects to be investigated. Some of these, such as \{\varnothing|\varnothing\}, we have seen before, others will turn out not to be properly formed by the criteria of Axiom 1, and still others will turn out to be equal to each other even though their constituent sets are not identical. By the time we have eliminated duplicates and things that are not surreal numbers at all, we will be left with only four new surreal numbers.

Since we know from Axiom 1 that no member of a right set can be less than or equal to any member of a left set, and we already put -1, 0, and 1 in order on Day 1, we can eliminate a few objects. For example, \{0,1|-1\} is out because -1 is less than 0. Similarly \{1|1\} can be discarded because 1\leq 1.

Exercise 6

After eliminating non well-formed objects of this sort, and numbers we have encountered on previous days, how many objects remain to be investigated?

That's still quite a lot, but we can cut them down even further. For instance, we can prove that \{-1,0|\varnothing\}=1; we do this the usual way, by showing that \{-1,0|\varnothing\}\leq 1 and 1\leq \{-1,0|\varnothing\}.

For this to be true we require:

  • (a) No member of 1_R is less than or equal to \{-1,0|\varnothing\}\leq 1, and
  • (b) 1 is less than or equal to no member of \{-1,0|\varnothing\}, and
  • (c) No member of \{-1,0|\varnothing\}_R is less than or equal to 1, and
  • (d) \{-1,0|\varnothing\} is less than or equal to no member of 1_L.

Points (a) and (c) are obviously true because the right sets in question are the empty set. Point (b) is true because we showed on Day 1 that 0<1. Point (d) reduces to showing that \{-1,0|\varnothing\}\not\leq 0. This will be true if:

  • (e) Some member of 0_R is greater than or equal to \{-1,0|\varnothing\}, or
  • (f) 0 is less than or equal to some member of \{-1,0|\varnothing\}_L.

We see that point (f) is true because 0\leq 0, which verifies (d), and this completes the proof.

This has been the lengthiest proof presented so far. If you were able to follow it, well done. If not, work through it slowly; in particular make sure you understand how points (e) and (f) arise from the binary relation \not\leq. You may have noticed that the -1 member of the left set of \{-1,0|\varnothing\} did not play a role in the proof at all. Only the largest member of the left set mattered. This is true in general, and we will shortly prove it.

For the first time we see two surreal numbers that are equal to each other despite their constituent sets not being identical.

Definition 2 - identity

For two numbers x, y

  • x\equiv y if X_L consists of exactly the same elements as Y_L and X_R consist of exactly the same elements as Y_R
  • x\doteq y if x=y but x\not\equiv y

But we won't carry this idea any further. \{0|1\}\equiv\{0|1\} regardless of whether the 0 on the right hand side is identical to the one on the left.

We will now prove two very handy general theorems:

Theorem 1 - the Transitive Law

If x, y, and z are surreal numbers such that x\leq y and y \leq z, then x \leq z.

The proof is by contradiction. By hypothesis the following must be true:

  • (a) No y_R\leq x, and
  • (b) y\leq no x_L, and
  • (c) No z_R\leq y, and
  • (d) z\leq no y_L.

Note that we are using phrases like "No y_R \leq x" as shorthand for "There is no element y_R in the set Y_R such that y_R\leq x".

Because we are assuming that x\not\leq z, one of the following must be true:

  • (e) Some x_L\geq z, or
  • (f)  x\geq some z_R.

If (e), then it follows that y\leq z, z\leq x', and y \not\leq x'.
If (f), then z'\leq x, x\leq y, and z'\not\leq y.

Combining (e) with (b), and (f) with (d) we get that, either

  • x_L\leq y\leq z but x_L\not\leq z
  • x\leq y \leq z_R but x\not\leq z_R.

This appears to be no help at all; we are back to trying to prove the transitive law for another set of three numbers. Luckily there is a way out of this difficulty. Observe that the three numbers we have are simpler than the three we started with. One of them was created earlier. Define d(q) to denote the day on which surreal number q was created. So we have the day-sum d(x_L)+d(y)+d(z)<d(x)+d(y)+d(z), and similarly for the other alternative. (These are normal integers for now, not surreals). The three new "bad" numbers will produce another set of bad numbers with a lower day sum, and those will produce an even lower one. Eventually we will regress to a point where the day sum is less than or equal to 2.

Exercise 7

Show that \{-1,0,1\} are the only three distinct surreal numbers whose day-sum is equal to 2.

But the transitive law is true for those three numbers. Thus we cannot ever get the transitive law to fail. This completes the proof. This inductive proof is of a different character to the ones we've seen previously, but many proofs we will encounter from now on will depend on similar reasoning. Work through the proof slowly until its meaning is clear.

Exercise 8

The following transitive laws are all also valid:

  • (a) If x=y and y=z then x=z.
  • (b) If x<y and y<z then x<z.
  • (c) If x<y and y\leq z then x<z.
  • (d) If x\leq y and y<z then x<z.

Prove (a) and (b), and give an argument why (c) and (d) follows from them.

The corresponding transitive laws for \geq and > also hold; the proofs are very similar.

Theorem 2
  1. If x is a surreal number with nonempty X_L, then x_L<x
  2. If x is a surreal number with nonempty X_R, then x<x_R

We prove the first half; the second will follow by symmetry. We require:

  • (a) x_L\leq x, and
  • (b) x_L\neq x.

But (b) must hold. A surreal number cannot contain itself (or any of its younger representations) in its left set, since all the elements of the left set were previously created (Axiom 1). Therefore, all we need is

  • (c) no x_R\not\leq x_L, and
  • (d)  x \leq no x_{LL},

where x_{LL} is a member of the left set of x_L. Observe that this would follow immediately if the left set of x_L were empty. It would also follow by Theorem 1 if x_{LL}\leq x_{L}, which in turn would follow if x_{LLL}\leq x_{LL} and so forth. Eventually, by induction, we get some x_{LL...L} whose left set is empty; we cannot go earlier than Day 0. This proves the theorem.

Theorem 3
  1. If x=\{X_L|X_R\} is a surreal number and a is another surreal number such that a is less than at least one member of X_L, then \{a,X_L|X_R\}=\{X_L|X_R\}.
  2. Similarly, if b is a surreal number such that b is greater than at least one member of X_R, then \{X_L|X_R,b\}=\{X_L|X_R\}.

As usual, we will show the first half of the theorem by showing that \{a,X_L|X_R\}\leq\{X_L|X_R\} and that \{X_L|X_R\}\not\geq\{a,X_L|X_R\}. The second half will again follow by symmetry. Let w be a number in X_L that is greater than a, which we know must exist by hypothesis. We will also use \hat x as shorthand for \{a,X_L|X_R\}. We require (verify this for yourself!):

  • (a) No x_R\leq x
  • (b) \hat x\leq no x_L
  • (c) No x_R\leq \hat x
  • (d) x\leq no x_L
  • (e) a \leq x.

Points (a) and (d) follow directly from Theorem 2. Point (e) follows from by observing that a\leq w by definition; Theorem 2 shows that w<x and using the transitive law gives us a<x. For (c), observe that Theorem 2 states that x<x_R without referring to X_L at all, so the presence of a in \hat X_L will not change anything. Thus (c) is true. Point (b) will be true by Theorem 2 if the presence of a in \hat X_L does not falsify it. Let's assume that it does falsify Theorem 2. Then we require a\not< x as none of the other possible choices of x_L will do the job. But by construction a<w<x, a contradiction, so (b) must be true. This completes the proof.

The important implication of Theorem 3 is that we are free to discard any member of any left set, except the largest. We can also discard any member of any right set, except the smallest. The surreal numbers formed from these sets will be unchanged. We can, in fact, remove everything from a surreal number except the largest member of its left set and the smallest member of its right set. From this observation, we can reduce the set of surreal numbers created on this day to these:

  • \{\varnothing|-1\}
  • \{\varnothing|1\}
  • \{-1|\varnothing\}
  • \{-1|0\}
  • \{-1|1\}
  • \{0|1\}
  • \{1|\varnothing\}

It has been a long road to get here. To justify throwing out surreal numbers like \{-1,0|1\} we needed Theorem 3. To obtain it we required Theorem 1, the transitive law, and Theorem 2, which tells us that a surreal number lies between its left and right sets. I'm sure you will agree that these are highly valuable in their own right, for more than just arriving at Theorem 3, and that the long digression has been worth it.

The seven remaining surreal numbers are a vast reduction from the 64 possibilities we started with, but it turns out that three of the remaining numbers are actually equal to numbers we've seen before. In fact, they are equal to zero.

Exercise 9

Prove that \{\varnothing|1\}, \{-1|\varnothing\}, and \{-1|1\} are all equal to 0.

The remaining four numbers are not aliases of other ones we've seen. Let us give them names:

  • \{\varnothing|-1\}:=-2
  • \{-1|0\}:=-\frac{1}{2}
  • \{0|1\}:=\frac{1}{2}
  • \{1|\varnothing\}:=2

We can demonstrate that none of these numbers are aliases of others (and that we've picked good names for the new numbers) by showing that this ordering holds:
-2<-1<-\frac{1}{2}<0<\frac{1}{2}<1<2.

We'll begin by showing that 0<\frac{1}{2}. If so, then

  • (a) No element of \left(\frac{1}{2}\right)_R is less than or equal to zero, and
  • (b) \frac{1}{2} is less than or equal to no element of 0_L, and
  • (c) ( Some member of 0_R is less than or equal to \frac{1}{2}, or
  • (d) 0 is less than or equal to some element of \left(\frac{1}{2}\right)_L={0} ).

Note the brackets here; we require both (a) and (b), and at least one of (c) and (d).

(a) is true because \left(\frac{1}{2}\right)_R=\{1\}, (b) is true because 0_L=\varnothing, (c) is false because 0_R=\varnothing, and (d) is true because 0\leq 0. We therefore have (a), (b) and one of (c),(d) and the inequality is proven.

Exercise 10

Show that \frac{1}{2}<1

The proof that -1<-\frac{1}{2}<0 is very similar to the above.

Exercise 11

Show that 1<2. The proof that -2<-1 will follow by symmetry.

Now that we have all this, the transitive law ensures that we can't have nasty surprises like 2 turning out to be less than -1 and the like. But when we go to later days, what guarantee do we have that all the surreal numbers will continue to be sorted into an orderly row? What would happen if a surreal number turned up that was not comparable to the others by our binary relations, or satisfied apparently contradictory relations like x>y,y>x? The next section shows that such a thing cannot happen.

All surreal numbers are related[edit]

Theorem 4- Surreal numbers are always comparable

For any two well-formed surreal numbers, exactly one of the following holds:

  1. x<y
  2. x=y
  3. y<x

We prove this in two stages. First we show that, if one holds, the other two do not. Then we show that, if any two do not hold, the third one must. There are six cases to consider

Case 1- Take x<y to be true. Then we have to show that x\neq y and y\not< x. In other words, we know

  • (a) No y_R\leq x, and
  • (b)  y\leq no x_L, and
  • (c) ( some x_R \leq y or
  • (d) x\leq some y_L),

and we want to show that

  • (e) (x\not\leq y, or
  • (f) y\not\leq x), and
  • (g) (y\not\leq x, or
  • (h) x\leq y).

Items (f) and (g) are identical, but as they have arisen from different binary relations we list them both for completeness. We know that (h) is true because x<y and (e) is false for the same reason. We need to show that (f) is true:

  • (i) (Some x_R\leq y or
  • (j) x\leq some y_L.

But (i) is given, since we already know (c). Thus Case 1 is valid.

Case 2- Take y<x to be true. Then we have to show that y\neq x and x\not< y. The proof is identical to that of Case 1; we just need to exchange x and y.

Case 3- Take x=y to be true. Then we have to show that x\not< y and y\not< x. We know

  • (a) No y_R\leq x, and
  • (b) y\leq no x_L, and
  • (c) No x_R\leq y, and
  • (d) x\leq no y_L.

We want to prove

  • (e) (x\not\leq y, or
  • (f) y\leq x), and
  • (g) (y\not\leq x, or
  • (h) x\leq y).

Observe that we need one of (e,f) and one of (g,h). But, by Definition 1, we have (f) and (h) because x=y. Thus Case 3 is valid.

These three cases show that at most one of the relations holds. Since we did not use the fact that x,y are well-formed, that must be true of pseudo-numbers as well. Now we show that at least one of the inequalities holds.

Case 4- Take x<y and x=y to be false, and show that y<x. We know that

  • (a) (x\not\leq y, or
  • (b) y\leq x), and
  • (c) (x\not\leq y or
  • (d) y\not\leq x).

We want to show that

  • (e) y\leq x, and
  • (f) x\not\leq y.
Exercise 12

If a,b are surreal numbers such that a\not<b and a\neq b, prove that a\not\leq b.

This reduces the problem to showing that y\leq x, given that x\not\leq y. We know that

  • (g) Some y_R\leq x, or
  • (h) y\leq some x_L,

and we want to show that

  • (i) No x_R\leq, and
  • (j) x\leq no y_L.

By contradiction: suppose that some x_R\leq y. Then (g) becomes, by Theorem 2, x_R\leq y\leq y_R\leq x, but we already know from Theorem 2 that x_R\not\leq x. Point (h) becomes x_R\leq y\leq x_L, but that would make x a badly-formed number by Axiom 1.

Now suppose x\leq some y_L. Then (g) and (h) give contradictions of the same kind; show this as an exercise.

Exercise 13

If x\leq y_L, show that y_R\leq x and y\leq x_L are false.

This completes the proof of Case 4.

Case 5- Take y<x and x=y to be false, and show that x<y.

This follows from Case 4 by symmetry; we need only substitute x for y in the proof.

Case 6- Take y<x and x<y to be false, and show that x=y.

We know that

  • (a) (x\not\leq y or
  • (b) y\geq x) and
  • (c) (y\not\leq or
  • (d) x\geq y),

but, by Exercise 12, (a) and (b) are the same thing (provided the numbers are well-formed, which these are), and (c) and (d) are equivalent. So (a,b,c,d) reduce to

  • (e) y\geq x and
  • (f) x\geq y.

This is the definition of equality, so Case 6 is proven.

These three cases show that at least one of the relations holds. Since the proofs required the fact that the numbers are well-formed, there is still a possibility that some pseudo-numbers might be incomparable to some surreal numbers; they are not greater or less or equal.

Day 3 and beyond[edit]

Now we have seven different surreal numbers, created on Day 2 or earlier. There are 128 different subsets that can be formed from these, and 16,384 possibilities for surreal numbers. But we can reduce this quickly straight away, because we have already proved that we need at most one member in the left and right sets. So the only distinct possibilities are 7 objects that have en empty left set, 7 that have an empty right set, one that has both sets empty (our friend zero!), and 49 that have one member of their left and right sets. That's 64 in total, which is still a lot. On later days, the numbers will blow out astronomically unless we find a way of determining which objects created on any day actually correspond to distinct, well-formed surreal numbers.

Since we showed earlier that a number lies between its left and right sets we can at least discard all objects \{x|y\} where x\geq y.

Exercise 14

If a total of n surreal numbers are known, show that from these one can construct n(n-1)/2 well-formed surreal numbers with exactly one member of their left and right sets. Hint: Prove it for n=1 and n=2 and proceed by induction.

So of the 49 possibilities for surreals of the form \{x|y\}, 21 are well-formed and you showed in Exercise 2 that objects like \{\varnothing|x\} and \{x|\varnothing\} are also well-formed surreal numbers. This leaves 36 well-formed surreal numbers of the 16,384 possibilities we started with. Take away the seven that we already know from earlier days, and 29 remain. But the majority of these are different representations of the original seven. How can we eliminate these without having to check them all individually?

Suppose we have a set of n surreal numbers {x_1, x_2, ..., x_n} which are sorted into ascending order, i.e.,
x_1<x_2<...<x_{n-1}<x_n.

Clearly \{\varnothing|x_1\} is a new surreal number not in the set, because it is less than any of them, and \{x_n|\varnothing\} is not in the set because it is greater than any of them. And since x_i<\{ x_i | x_{i+1}\}<x_{i+1} new surreal numbers appear between adjacent numbers in the old set. We will show that these are the only new numbers created.

Theorem 5- The Simplicity Theorem

Given any number y with nonempty left and right sets, if x is the oldest number such that Y_L<x<Y_R, then x=y.

First observe that all X_L< some Y_L, for if not there would be some x_L, older than x, between Y_L and Y_R and we should be using that instead of x. Similarly, all X_R> some Y_R. Now to show that x=y, we only require all of:

  • (a) no y_R\leq x
  • (b) y\leq no  x_L
  • (c) no x_R\leq y
  • (d) x\leq no  y_L.

Points (a) and (d) are given by construction, and (b) follows from the transitive rule and observing that x_L< some y_L<y. Point (c) follows by similar reasoning. The last thing to be shown is that there is only one oldest number between Y_L and Y_R.

Exercise 15

Show that there is only one oldest number between Y_L and Y_R.

This completes the proof.

Now we know that all numbers formed from two nonadjacent numbers have previously been created. All that remains is to deal with numbers like \{-2|\varnothing\}, where the left or right set is empty but which are not the largest or smallest numbers created.

Theorem 6
  • If y=\{Y_L|\varnothing\} and x is the oldest number greater than Y_L then x=y.
  • If z=\{\varnothing|Z_R\} and w is the oldest number smaller than Z_R then w=z.

We show the first part; the second will follow in an analogous manner. We require all of:

  • (a) No y_R\leq x
  • (b) y\leq no  x_L
  • (c) No x_R\leq y
  • (d) x\leq no  y_L.

Again we have (a) and (d) from the construction of the problem. Since x_R would be older than x and greater than Y_L, contrary to hypothesis, we know that X_R=\varnothing and (c) follows vacuously. Finally (b) must be true, for if not, Y_L<y<x_L and we would have some number older than x but greater than Y_L. The proof that there is only one oldest number greater than Y_L follows in a very similar manner to Exercise 15.

Theorems 5 and 6 together show that the only new numbers created on any day are

\{\varnothing|x_1\}, \{x_1|x_2\}, \{x_2|x_3\}, ... , \{x_{n-1}|x_n\}, \{x_n|\varnothing\}, and we already know where they fit in the ordering. So, without any more fuss, here are all numbers known at the end of Day 3:

 -3, -2, -\dfrac{3}{2}, -1, -\dfrac{3}{4}, -\dfrac{1}{2}, -\dfrac{1}{4}, 0, \dfrac{1}{4}, \dfrac{1}{2}, \dfrac{3}{4}, 1, \dfrac{3}{2}, 2, 3.

The End of the Beginning[edit]

We've come a long way in the first few days. From nothing, we have constructed the first number 0 and from that we have built a total of fifteen different numbers. Along the way we obtained useful results like the transitive law and the fact that a number lies between its constituent sets. We have also determined exactly which numbers are created on any day and which are just new representations of old ones. In the next chapter we move on to basic arithmetic on surreal numbers.