Surreal Numbers and Games/The Beginning

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

Day 0[edit | edit source]

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 is a surreal number, then and are its left and right sets respectively, and we denote it as

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 and to both be the empty set , containing no surreal numbers. So we can create , 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 has no members at all, and this is enough to prove that 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: . Do not confuse the zero symbol 0 with the symbol for the empty set .

Day 1[edit | edit source]

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: , , and . We have to check whether these objects are well-formed. For the first, we need to show that no member of is less than or equal to any member of , which is again trivially true.

Exercise 1

Show that is a well-formed surreal number.

Exercise 2

If is a surreal number, show that and 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 a surreal number? If so, then no member of (the right set of ) is less than or equal to (the left set). In other words, 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 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 and , we say that is less than or equal to if and only if is greater than or equal to . We say is greater than or equal to if and only if no member of is less than or equal to and is less than or equal to no member of .

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 ? From Definition 2, that will be true if no member of is less than or equal to 0 and 0 is less than or equal to no member of . But both and are the empty set so this claim is true. Thus , as we expect, and so 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 and . We will give the two new ones names:

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

Definition 1: Binary relations
Symbol Meaning
is "Less than or equal to" , as defined in Axiom 2
is "Greater than or equal to" , as defined in Axiom 2
is false
is false
and
but
but
is false
is false
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 . From the definition of "<", we need to show first that and then that .

For the first stage we need to show that no member of is greater than or equal to 1 (trivially true because ), and that 0 is less than or equal to no member of the left set of (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 and that . In other words, .

Exercise 4

Show that .

Exercise 5

Show that . 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 created on or before Day 1, such that and , we also have . 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 | edit source]

Now that we have three surreal numbers, we can create a host of new objects. For completeness, the different sets of surreal numbers are:
and . 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 , 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, is out because -1 is less than 0. Similarly can be discarded because .

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 ; we do this the usual way, by showing that and .

For this to be true we require:

  • (a) No member of is less than or equal to , and
  • (b) is less than or equal to no member of , and
  • (c) No member of is less than or equal to , and
  • (d) is less than or equal to no member of .

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 . Point (d) reduces to showing that . This will be true if:

  • (e) Some member of is greater than or equal to , or
  • (f) is less than or equal to some member of .

We see that point (f) is true because , 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 . You may have noticed that the -1 member of the left set of 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

  • if consists of exactly the same elements as and consist of exactly the same elements as
  • if but

But we won't carry this idea any further. regardless of whether the 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 and are surreal numbers such that and , then .

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

  • (a) No , and
  • (b) no , and
  • (c) No , and
  • (d) no .

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

Because we are assuming that , one of the following must be true:

  • (e) Some , or
  • (f) some .

If (e), then it follows that and .
If (f), then , and .

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

  • but
  • but .

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 to denote the day on which surreal number was created. So we have the day-sum , 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 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 and then .
  • (b) If and then .
  • (c) If and then .
  • (d) If and then .

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

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

Theorem 2
  1. If is a surreal number with nonempty , then
  2. If is a surreal number with nonempty , then

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

  • (a) , and
  • (b) .

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 , and
  • (d) no ,

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

Theorem 3
  1. If is a surreal number and is another surreal number such that is less than at least one member of , then .
  2. Similarly, if is a surreal number such that is greater than at least one member of , then .

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

  • (a) No
  • (b) no
  • (c) No
  • (d) no
  • (e) .

Points (a) and (d) follow directly from Theorem 2. Point (e) follows from by observing that by definition; Theorem 2 shows that and using the transitive law gives us . For (c), observe that Theorem 2 states that without referring to at all, so the presence of in will not change anything. Thus (c) is true. Point (b) will be true by Theorem 2 if the presence of in does not falsify it. Let's assume that it does falsify Theorem 2. Then we require as none of the other possible choices of will do the job. But by construction , 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:

It has been a long road to get here. To justify throwing out surreal numbers like 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 , , and are all equal to 0.

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

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:
.

We'll begin by showing that . If so, then

  • (a) No element of is less than or equal to zero, and
  • (b) is less than or equal to no element of , and
  • (c) ( Some member of is less than or equal to , or
  • (d) is less than or equal to some element of ).

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

(a) is true because , (b) is true because , (c) is false because , and (d) is true because . We therefore have (a), (b) and one of (c),(d) and the inequality is proven.

Exercise 10

Show that

The proof that is very similar to the above.

Exercise 11

Show that . The proof that 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 ? The next section shows that such a thing cannot happen.

All surreal numbers are related[edit | edit source]

Theorem 4- Surreal numbers are always comparable

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

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 to be true. Then we have to show that and . In other words, we know

  • (a) No , and
  • (b) no , and
  • (c) ( some or
  • (d) some ),

and we want to show that

  • (e) (, or
  • (f) ), and
  • (g) (, or
  • (h) ).

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 and (e) is false for the same reason. We need to show that (f) is true:

  • (i) (Some or
  • (j) some .

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

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

Case 3- Take to be true. Then we have to show that and . We know

  • (a) No , and
  • (b) no , and
  • (c) No , and
  • (d) no .

We want to prove

  • (e) (, or
  • (f) ), and
  • (g) (, or
  • (h) ).

Observe that we need one of (e,f) and one of (g,h). But, by Definition 1, we have (f) and (h) because . 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 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 and to be false, and show that . We know that

  • (a) (, or
  • (b) ), and
  • (c) ( or
  • (d) ).

We want to show that

  • (e) , and
  • (f) .
Exercise 12

If are surreal numbers such that and , prove that .

This reduces the problem to showing that , given that . We know that

  • (g) Some , or
  • (h) some ,

and we want to show that

  • (i) No , and
  • (j) no .

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

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

Exercise 13

If , show that and are false.

This completes the proof of Case 4.

Case 5- Take and to be false, and show that .

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

Case 6- Take and to be false, and show that .

We know that

  • (a) ( or
  • (b) ) and
  • (c) ( or
  • (d) ),

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) and
  • (f) .

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 | edit source]

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 where .

Exercise 14

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

So of the 49 possibilities for surreals of the form , 21 are well-formed and you showed in Exercise 2 that objects like and 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 surreal numbers {x_1, x_2, ..., x_n} which are sorted into ascending order, i.e.,
.

Clearly is a new surreal number not in the set, because it is less than any of them, and is not in the set because it is greater than any of them. And since 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 with nonempty left and right sets, if is the oldest number such that , then .

First observe that all some , for if not there would be some , older than , between and and we should be using that instead of . Similarly, all some . Now to show that , we only require all of:

  • (a) no
  • (b) no
  • (c) no
  • (d) no .

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

Exercise 15

Show that there is only one oldest number between and .

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 , where the left or right set is empty but which are not the largest or smallest numbers created.

Theorem 6
  • If and is the oldest number greater than then .
  • If and is the oldest number smaller than then .

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

  • (a) No
  • (b) no
  • (c) No
  • (d) no .

Again we have (a) and (d) from the construction of the problem. Since would be older than and greater than , contrary to hypothesis, we know that and (c) follows vacuously. Finally (b) must be true, for if not, and we would have some number older than but greater than . The proof that there is only one oldest number greater than 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

, 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:

.

The End of the Beginning[edit | edit source]

We've come a long way in the first few days. From nothing, we have constructed the first number 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.