An Introduction to Surreal Numbers - Report

An Introduction to Surreal Numbers Introduction Mathematician John Horton Conway first invented surreal numbers, and Donald Knuth introduced them to the public in 1974 in his mathematical novelette, Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. In his novel, two college graduates, Bill and Alice, are stranded on a deserted island when they find an ancient stone with the mysterious writing, “In the beginning everything was void, and J.H.W.H. Conway began to create numbers. Conway said, ‘Let there be two rules which bring forth all numbers large and small...’” [1]. Bill and Alice then spend their days working through the stone’s inscriptions to develop the theory behind surreal numbers. In this paper, I formalize Bill and Alice’s results, and investigate some further properties of the surreal numbers. As well as Conway’s two rules, the stone dictates that starting with nothing at all we can create the number zero, which has an empty left set and an empty right set. We call the day that zero is created on day 0. The next day, day 1, we can create more numbers by putting zero in the left set of one number and the right set of another, and we can then use these new numbers to create even more numbers on day 2, and so on. In this way, all surreal numbers are created; to each number, we can associate its “day of creation.” We begin our investigation of the surreals by looking at what numbers are created on the first few days, and then verifying some basic properties of all numbers. We then define addition and multiplication for surreal numbers, and conclude that they form a totally ordered field. Using addition and multiplication we can map out exactly what numbers are created on which days, and we discover that after a finite number of days we get all of the real numbers, plus more. We then look at some structures within the surreals, including integers and real numbers. We end the 1 paper by introducing how surreal numbers can be used to analyze games, in particular the game of Hackenbush. 1 1.1 What Are Surreal Numbers? Conway’s Two Rules As the stone states, every surreal number is created on a certain day and corresponds to two sets of numbers. For a surreal number, x, we write x = {XL |XR } and call XL and XR the left and right set of x, respectively. In this section we will build the surreal numbers, which we denote S, from the ground up based on two axioms defined by Conway. Axiom 1. Every number corresponds to two sets of previously created numbers, such that no member of the left set is greater than or equal to any member of the right set [1]. So if x = {XL |XR } then for each xL ∈ XL and xR ∈ XR , xL  xR . We write this as XL  XR . Axiom 2. 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 no member of the second number’s right set is less than or equal to the first number [1]. So x = {XL |XR } ≤ y = {YL |YR } if and only if XL  y and x  YR . If every number corresponds to two sets of previously created numbers, then what do we start with on the zeroth day? If we let ∅ be the empty set then we define zero as 0 = {∅|∅}, which we write more simply as 0 = {|}. Clearly, 0 is consistent with Axiom 1 since the empty set contains no elements. We also note that 0 ≤ 0, since no element of the empty set is greater than or equal to 0, and 0 is not greater than or equal to any element of the empty set. Now that we have defined 0, we can create some new numbers on the next day, day 1. We can put 0 in the left set of a number to get x = {0|}, and we can put 0 in the right set to get y = {|0}. Note that {0|0} is not consistent with Axiom 1, since it has an element in its left set that is greater than or equal to an element in its right set, thus it is not a number. How do x and y compare with 0? It is not hard to check that 0 ≤ x, since the left set of 0 is empty and the right set of x is empty, but the possibility that x = 0 seems rather silly. Using Axiom 2 we can show that x ≤ 0 is impossible, for if x ≤ 0 then we must have that 0  0, a contradiction. Thus 0 is less than but not equal to x. Similarly we can see that y  0. We call x one and we call y negative one. So on day 1 we get the numbers 2 1 = {0|} and −1 = {|0}. In this case, we know that 0 was created earlier than 1 and -1, but in general we can deduce that if some number x is in either the left or right set of a number y, then x must have been created before y. Definition 1.1. We say that a number x is simpler than a number y if x was created before y. Thus 0 is simpler than 1 and -1. We can now put any of −1, 0, or 1, into the left of right set of a number to create 18 new numbers on day 2. The numbers created through day 2 are 0 = {|} 1 = {0|} −1 = {|0} {1|} {−1|} {0, 1|} {0, −1|} {−1, 1|} {−1, 0, 1|} {|1} {| − 1} {|0, 1} {|0, −1} {| − 1, 1} {| − 1, 0, 1} {−1|0} {−1|1} {−1|0, 1} {0|1} {−1, 0|1}. Using these numbers we will be able to create even more numbers on the third day, and so on. Since we will eventually have exhaustingly many numbers to work with we would like to check to see if some basic properties that hold for real numbers also hold for surreal numbers. 1.2 Basic Proofs and Properties Suppose x, y, and z are surreal numbers such that x ≤ y and y ≤ z. Is it necessarily true that x ≤ z? That is, does the Transitive Law hold? Theorem 1.1 (Transitive Law). If x ≤ y and y ≤ z, then x ≤ z. Proof. We will use proof by contradiction. Let x = {XL |XR }, y = {YL |YR }, and z = {ZL |ZR } be the earliest numbers created such that x ≤ y, y ≤ z and x  z. Then either of the following two cases occur: i.) There exists an xL ∈ XL such that xL ≥ z, or ii.) There exists some zR ∈ ZR such that zR ≤ x. 3 In case (i.) we would have three numbers (y, z, xL ) that do not obey the Transitive Law, since y ≤ z and z ≤ xL but y  xL . We note that xL is a simpler number than x since xL ∈ XL . In case (ii.) we also have a different set of three numbers (zR , x, y) that do not obey the Transitive Law. Similarly, zR is a simpler number than z. In either case we have a simpler set of three numbers that do not obey the Transitive Law, which is a contradiction since we assumed that x, y, and z were the earliest numbers created that do not obey the Transitive Law. Here we see how induction plays a major role in proving properties of surreal numbers. Since the numbers are formed in a somewhat recursive manner we can use induction on the day that a number, or set of numbers, is created to trace properties of arbitrary numbers back to the earliest created numbers, of which we have a solid understanding. In the previous proof, we saw how for any set of numbers, {x, y, z}, that do not obey the Transitive Law, we get a set of simpler numbers, {x0 , y 0 , z 0 }, that do not obey the Transitive Law. In other words, if we let d(k) be the day that a number, k, was created on, then d(x0 ) + d(y 0 ) + d(z 0 ) < d(x) + d(y) + d(z). However, we cannot continue to find sets with smaller and smaller day sums that do not obey the Transitive Law since the three simplest numbers (0, 1, and -1) do (this fact is not hard to check and is left for the reader). Therefore, all numbers must obey the Transitive Law. In proofs to come, we will use this day sum argument implicitly. Earlier we showed that 0 ≤ 0. We can use day induction to extend this result to all numbers. Theorem 1.2. x ≤ x. Proof. Let x be the earliest created number such that x  x. Then, by Axiom 2, either i.) there exists some xL ∈ XL such that x ≤ xL , or ii.) there exists some xR ∈ XR such that xR ≤ x. Consider case (i.). Then, by definition we would have that XL  xL , which implies that xL  xL since xL ∈ XL . But this is impossible since xL was created before x. Similarly, we arrive at a contradiction if we assume case (ii.). How does x compare to its left and right set? Suppose XR ≤ x. Then, by Axiom 2, we must have that XR  XR , which is a contradiction because xR ≤ xR for each xR ∈ XR . Thus XR  x. We can also show that x  XL in the same way. We can show that every number lies between its left and right set. Theorem 1.3. If x is a number, then XL ≤ x ≤ XR . Proof. Suppose there is some xL ∈ XL such that xL  x. Then either there is a number xLL ∈ XLL such that xLL ≥ x, or there is a number xR ∈ XR such that xR ≤ xL . The latter case is clearly impossible by Axiom 1. By induction, we can assume that xLL ≤ xL . Thus we have x ≤ xLL and xLL ≤ xL , meaning that x ≤ xL , by the Trasitive Law. But x ≤ xL implies that XL  xL , which is a contradiction since xL ∈ XL . Thus no such xL exists, which implies that XL ≤ x. We can show that x ≤ XR in an analogous manner. 4 We have shown that every number is related to itself, and we can also prove that all numbers are related to each other in some way. Theorem 1.4. For all numbers x and y, if y  x then x ≤ y. Proof. We will use proof by contradiction. Suppose there exist numbers x and y such that y  x and x  y. Then either i.) xL ≥ y, or ii.) x ≥ yR must be true. Consider case (i.). We know that xL ≤ x, so by the Transitive Law y ≤ x. But we have assumed that y  x, thus we have a contradiction. Similarly, we reach a contradiction with case (ii.). Theorem 1.4 means that the the surreal numbers are totally ordered. With this knowledge we can say x < y instead of x  y. Thus we have the following, stronger statement for how a number relates to its left and right sets. Theorem 1.5. If x is a number then XL < x < XR . Is it possible to have an x and y such that x ≤ y and y ≤ x? Consider the number {−1|1}, created on the second day. If we compare this number with 0 we see that {−1|1} ≤ 0 and {−1|1} ≥ 0. Thus it behaves the same as 0, but it is not equal to 0 since its left and right sets are not identical to those of 0. In general, we say that a number x is like a number y, written x ≡ y, if x ≤ y and y ≤ x. If the left and right sets of two number are like, then those two numbers are also like. That is, if xL ≡ yL and xR ≡ yR , then x ≡ y where x = {xL |xR } and y = {yL |yR }. We verify that this is indeed true with the following theorem. Theorem 1.6. Let x and y be numbers whose left and right parts are “like” but not identical. Formally, let fL : XL → YL , gL : YL → XL , fR : XR → YR , gR : YR → XR be functions such that fL (xL ) ≡ xL , fR (xR ) ≡ xR , gL (yL ) ≡ yL , and gR (yR ) ≡ yR . Then x ≡ y [1]. Proof. We want to show that x ≤ y and y ≤ x. For x ≤ y to hold we need to show that XL < y and x < YR . Consider xL ∈ XL . We have that xL ≡ fL (xL ). Note that fL (xL ) ∈ YL . Since y is a number YL < y, meaning that fL (xL ) < y. Thus xL < y, and since xL is an arbitrary element of XL we have that XL < y. Now consider yR ∈ YR . We have that yR ≡ gR (yR ). Since gR (yR ) ∈ XR and x is a number we have that x < gR (yR ). Thus x < yR , and since yR is an arbitrary element of YR we can conclude that x < YR . Therefore x ≤ y. We can show that y ≤ x in an analagous manner. 5 2 Developing The Pattern of the Surreal Numbers If {−1|1} ≡ 0, then are any of the other 17 numbers created on the second day like 0, 1, or -1? This leads us to explore which of these numbers are truly unique, which will give us an idea of how the surreal numbers form in general. 2.1 Uniqueness Recall the twenty numbers that we have by the second day. 0 = {|} 1 = {0|} −1 = {|0} {1|} {−1|} {0, 1|} {−1, 0|} {−1, 1|} {−1, 0, 1|} {|1} {| − 1} {|0, 1} {| − 1, 0} {| − 1, 1} {| − 1, 0, 1} {−1|0} {−1|1} {−1|0, 1} {0|1} {−1, 0|1}. It would be rather tedious to check every number created on the second day to see if it is both less than or equal to and greater than or equal to 0, 1, or -1 (and this process would get even more tedious by day 3, day 4, etc.). Thus we would like to be able to determine if a given number is like another in a more efficient way. Consider a number x = {XL |XR }. When we compare x to other numbers, we are really only worried about the greatest element of XL and the smallest element of XR . We notice that adding numbers to XL that are smaller than x and adding numbers to XR that are greater than x do not effectively change x. Thus if YL and YR are any sets such that YL < x < YR , we would expect that x is like z where z = {XL ∪ YL |XR ∪ YR }. For example, {1|} ≡ {0, 1|} ≡ {−1, 1|} ≡ {−1, 0, 1|}. Thich leads us to the Simplicity Theorem [2]. Theorem 2.1 (The Simplicity Theorem). Given any number y = {YL |YR }, if x is the first number created with the property that YL < x and x < YR , then x ≡ y. Proof. Suppose y is a number and x is the simplest number such that YL < x and x < YR . Consider the number z = {XL ∪ YL |XR ∪ YR }. We first prove that x ≡ z by showing that z ≤ x and x ≤ z. To prove z ≤ x we need that XL ∪ YL < x and z < XR . We know that XL < x and YL < x, thus XL ∪ YL < x. We defined z such that z < XR ∪ YR , so it must be that z < XR and thus z ≤ x. Similarly, we can show that x ≤ z. Thus x ≡ z. We now prove that y ≡ z, and it follows from the Transitive Law that x ≡ y. To show that y ≤ z we need that YL < z and y < ZR . From our hypothesis YL < x, and we have just shown that x ≤ z. It follows from the Transitive Law that YL < z. Again, from our hypothesis y < YR , and YR ≤ ZR since YR ⊆ ZR . Thus y < ZR , which means that y ≤ z. We can show that z ≤ y in an analagous manner. 6 Using the Simplicity Theorem we can see that {−1, 0|1} ≡ {0|1}, {| − 1, 0, 1} ≡ {| − 1, 0} ≡ {| − 1}, and so on. The only numbers created by the second day that are essentially different, listed in order, are {| − 1} < −1 < {−1|0} < 0 < {0|1} < 1 < {1|}. Notice that there seems to be a pattern. On day 0 we had 0 = {|}, and on day 1 the numbers {|0} and {0|} were created. We called these numbers −1 and 1, respecively, so by day 1 we had the numbers −1 < 0 < 1. On day 2 the new numbers that were formed were {| − 1}, {−1|0}, {0|1}, and {1|}. In general, the pattern of how numbers form are mapped out in the following theorem. Theorem 2.2. Suppose that the different numbers at the end of n days are x1 < x2 < · · · < xm . Then the only new numbers that will be created on the (n + 1)st day are {|x1 }, {x1 |x2 }, . . . , {xm−1 |xm }, {xm |}. Proof. Using the Simplicity Theorem we know that if either or both of XL and XR are sets with more than one element, then {XL |XR } ≡ {max{XL }| min{XR }}. Thus we want to show that if a number created on the (n + 1)st day is not of the form {|x1 }, {xm |}, or {xi |xi+1 }, where i = 1, 2, . . . m − 1, then it is like a number already created by the nth day. There are four cases to consider. Case 1 Consider the number {xi−1 |xi+1 }, where i = 2 . . . m−1. If xi = {xiL |xiR } then xiL ≤ xi−1 and xiR ≥ xi+1 since xi−1 < xi < xi+1 . So, by the Simplicity Theorem, xi ≡ {xiL , xi−1 |xiR , xi+1 }. Similarly, {xi−1 |xi+1 } ≡ {xiL , xi−1 |xiR , xi+1 }. Thus, by the Transitive Law, xi ≡ {xi−1 |xi+1 }. Case 2 Consider the number {xi−1 |xj+1 }, where i < j. If there is a number x = {xL |xR } such that xL ≤ xi−1 and xR ≥ xj+1 , then {xi−1 |xj+1 } ≡ x by the same reasoning as in case (1). If we let x be the first number created of xi , xi+1 , . . . , xj , then its left and right sets cannot include any of the other numbers in this list, which means it satisfies our requirements. Case 3 Consider the number {|xj+1 }. Then, as before, {|xj+1 } ≡ x where x is the first number created of x1 , x2 , . . . , xj . 7 Case 4 Finally, if we have {xi−1 |}, then {xi−1 |} ≡ x where x is the first number created of xi , xi+1 , . . . , xm . So from Theorem 2.2 we essentially know all numbers that will be created through a finite number of days. Note that by day 0 we have 1 = 21 − 1 numbers, by day 1 we have 3 = 22 − 1 numbers, and by day 2 we have 7 = 23 − 1 numbers. Suppose we have 2n+1 − 1 numbers after the nth day. Then the next day we will get 2n+1 − 1 + 1 numbers, which means that by the (n + 1)th day there will be 2 · 2n+1 − 1 = 2n+2 − 1 numbers. Thus the pattern holds for all finite n. Theorem 2.3. If n is a finite integer, then by the nth day, 2n+1 −1 numbers will have been created. 2.2 Pseudo-Numbers What would happen if we had something that resembled a surreal number, but did not satisfy Axiom 1? For example {0| − 1} does not obey Axiom 1 since 0 > −1, and neither does {0|0} since 0 ≥ 0. We call these numbers pseudo-numbers. We can verify relationships involving psuedonumbers using Axiom 2. For example, we can see that {0|0} ≤ 1 since 0 < 1, and because the right set of 1 = {0|} is empty. Now consider the pseudo-number {1|0}. Using Axiom 2 we see that {1|0}  0, since 1 > 0, and 0  {1|0}, since 0 ≤ 0. Thus 0 and {1|0} are not related at all. Here we see that unlike numbers, pseudo-numbers are not completely ordered. Although pseudo-numbers do not behave quite as nicely as numbers, we can still verify certain properties for them. Since the Transitive Law and Theorem 1.2 do not rely on Axiom 1, they hold for pseudo-numbers as well as numbers. Note that for the rest of the paper when we are talking about a number, we mean that it obeys Axiom 1. If we are talking about pseudo-numbers then we will explicitly say so. 2.3 Addition We define the negative of a surreal number, x, as follows. Definition 2.1. If x = {XL |XR }, then −x = {−XR | − XL }. Theorem 2.4. −(−x) = x. Proof. Using induction we see that for x = {XL |XR }, −(−x) = −({−XR | − XL }) = {−(−XL )| − (−XR )} 8 = {XL |XR } = x. To check that the negative of a number is well defined we need to make sure that if x is a number then −x is. That is, if XL < XR then we must have that −XR < −XL . Note that this fact follows directly from the following theorem. Theorem 2.5. x ≤ y if and only if −y ≤ −x. Proof. By our definition of negation, for any number, x, −XL = (−X)R and −XR = (−X)L . Suppose that x ≤ y. By Axiom 2, XL < y and x < YR and thus −(−X)R < y and x < −(−Y )L . Since both pairs of numbers {(−X)R , y} and {x, (−Y )L } have a smaller day sum than {x, y}, we can assume that −y < (−X)R and (−Y )L < −x by induction. Therefore, by Axiom 2, −y ≤ −x. We can prove the converse in the same manner. Using our definition for negation we can see that −{1|} = {| − 1} and −{0|1} = {−1|0}. Thus we can re-write the seven numbers created by the second day as −a < −1 < −b < 0 < b < 1 < a, where a = {1|} and b = {0|1}. How would we define addition for surreal numbers? In Knuth’s book the stone states, “The left set of the sum of two numbers shall be the sums of all left parts of each number with the other; and in like manner the right set shall be from the right parts, each according to its kind,” [1]. In symbols, we define addition between two surreal numbers x and y as follows. Definition 2.2. x + y = {XL + y, x + YL |XR + y, x + YR }. To check that addition is well defined we need to make sure that if x and y are numbers then (x + y)L < (x + y)R . The following inequalities must hold: XL + y < XR + y XL + y < x + YR x + YL < XR + y x + YL < x + YR . All of the inequalities above would hold if addition is transitive. For example in proving the second inequality we could suppose that XL + y ≥ x + YR . Since XL < x we could use that addition is 9 transitive to deduce that XL + y < x + y. Similarly, since y < YR , x + y < x + YR . Thus, by the transitive law we have that XL + y < x + YR , a contradiction. Note that even though we don’t know yet that XL + y, x + y, and x + YR are numbers, we know that even pseudo-numbers obey the transitive law. We would like to prove the following theorem. Theorem 2.6 (Transitive Law for Addition). x ≤ y if and only if x + z ≤ y + z. Proof. We assume that addition is commutative, which we will prove shortly. We begin the proof as introduced by Knuth in Surreal Numbers. let I(x, y, z) denote the statement: if x ≤ y then x + z ≤ y + z, and let II(x, y, z) denote its converse: if x + z ≤ y + z then x ≤ y [1]. If x ≤ y, then for I(x, y, z) to be true we must have that {XL +z}∪{x+ZL } < y+z and x+z < {YR +z}∪{y+ZR }. Thus the following inequalites must hold. XL + z < y + z (1) x + ZL < y + z (2) x + z < YR + z (3) x + z < y + ZR . (4) Suppose there exists some xL ∈ XL such that y + z ≤ xL + z. Since {y, xL , z} has a smaller day sum than {x, y, z}, by induction we can use II(y, xL , z) to conclude that y ≤ xL . But xL < x ≤ y; thus we have a contradiction, which means that inequality (1) holds. Similarly, we can deduce inequality (3) from II(yR , x, z). To prove inequality (2), suppose there exists some zL ∈ ZL such that y + z ≤ x + zL . Since x ≤ y and {x, y, zL } has a smaller day sum than {x, y, z}, by induction we can use I(x, y, zL ) to conclude that x + zL ≤ y + zL . Thus, by the transitive law y + z ≤ y + zL . Recall that y + z = {YL + z, y + ZL |YR + z, y + ZR }. By Axiom 2, y + z ≤ y + zL means that y + ZL < y + zL , a clear contradiction since zL ∈ ZL and each number and pseudo-number is less than or equal to itself. Therefore, inequality (2) holds. Similarly, we can deduce inequality (4) using II(x, y, zR ). To prove II(x, y, z) we must show that if x + z ≤ y + z, then x ≤ y. The following inequalities must hold. XL < y (5) x < YR . (6) Suppose there exists some xL ∈ XL such that y ≤ xL . Since {y, xL , z} has a smaller day sum than {x, y, z}, by induction we can use I(y, xL , z) to conclude that y + z ≤ xL + z. However this is a contradiction since x + z ≤ y + z implies that {XL + z} ∪ {x + ZL } < y + z by Axiom 2, meaning xL + z < y + z. Thus inequality (5) holds. Similarly we can deduce inequality (6) using I(yR , x, z). Now that we have proved the Transitive Law for addition we conclude that addition is well defined. Verifying that addition is also commutative and associative is relatively straightforward. Theorem 2.7 (Commutative Law for Addition). x + y = y + x. 10 Proof. Using the definition of addition and induction we see that x + y = {XL + y, x + YL |XR + y, x + YR } = {YL + x, y + XL |YR + x, y + XR } = y + x. Theorem 2.8 (Associative Law for Addition). (x + y) + z = x + (y + z). Proof. Using induction and the fact that addition is commutative we can conclude (x + y) + z = {XL + y, x + YL |XR + y, x + YR } + z = {(XL + y) + z, (x + YL ) + z, (x + y) + ZL |(XR + y) + z, (x + YR ) + z, (x + y) + ZR } = {XL + (y + z), x + (YL + z), x + (y + ZL )|XR + (y + z), x + (YR + z), x + (y + ZR )} = x + {YL + z, y + ZL |YR + z, y + ZR } = x + (y + z). We would like for there to be an additive identity, and indeed, we can verify that x + 0 = x for all x. Consider x + 0 = {XL + 0|XR + 0}. Since each xL ∈ XL is simpler than x, we can assume that XL + 0 = XL by induction. Similarly, XR + 0 = XR , thus we have the following theorem. Theorem 2.9. x + 0 = x. We can also show that each x has an additive inverse, −x. Theorem 2.10. x + (−x) ≡ 0. Proof. We have x + (−x) = {XL + (−x), x + (−X)L |XR + (−x), x + (−X)R } = {XL + (−x), x + (−XR )|XR + (−x), x + (−XL )}. To show that x + (−x) ≡ 0 we need to prove that x + (−x) ≤ 0 and x + (−x) ≥ 0. From Axiom 2 we deduce that x + (−x) ≤ 0 if and only if XL + (−x) < 0 and x + (−XR ) < 0, and x + (−x) ≥ 0 if and only if XR + (−x) > 0 and x + (−XL ) > 0. Suppose that XL + (−x) ≥ 0, then by Axiom 2, {XLR + (−x)} ∪ {XL + (−X)R } > 0, meaning xL +(−X)R > 0 for some xL ∈ XL . Furthermore, (−X)R = −(XL ), thus we have that xL +−(XL ) > 0. Since −xL ∈ −(XL ), this implies that xL + (−xL ) > 0. But xL is simpler than x, so we can assume that xL + (−xL ) ≡ 0 by induction. Thus we have a contradiction, meaning XL + (−x) < 0. We can prove the other three inequalities analogously. 11 In general we define subtraction as follows. Definition 2.3. x − y = x + (−y). In conclusion we have shown that • Addition is associative • Addition is commutative • Each surreal number x has an additive inverse, which is −x, and • There exists an additive identity, which is 0. Thus the surreals form an abelian group under addition! 2.4 Multiplication The stone states, “Let part of one number be multiplied by another and added to the product of the first number by part of the other, and let the product of the parts be subtracted. This shall be done in all possible ways, yielding a number in the left set of the product when the parts are of the same kind, but in the right set when they are of opposite kinds.” [1] In other words we need a definition for xy such that elements its left set are less than x · y and elements in its right set are greater than x · y. We define mulitplication as follows. Definition 2.4. x·y = {XL ·y +x·YL −XL ·YL , XR ·y +x·YR −XR ·YR |XL ·y +x·YR −XL ·YR , XR ·y +x·YL −XR ·YL }. Like we had to do with addition, we must verify some basic properties of multiplication before we can actually prove that it is well defined. By the definition of multiplication we can easily check that x · 0 = 0 and 0 · x = 0 for any x, since the left and right set of 0 is the empty set and anything added to or multiplied by the empty set is the empty set. Thus we have the following theorem. Theorem 2.11. x · 0 = 0 and 0 · x = 0. We would also like for there to be a multiplicative identity. As we expect, we can check that the identity is 1. Theorem 2.12. 1 · y = y and y · 1 = y. Proof. Using induction we see that for all y, 1 · y = {0 · y + 1 · YL − 0 · YL , 1 · YR |0 · y + 1 · YR − 0 · YR , 1 · YL } = {YL , YR |YR , YL } ≡ {YL |YR } = y. Similarly we can show that y · 1 = y for all y. 12 We can also prove that multiplication is commutative, associative, that it distributes over addition, and that the product of two positive, or negative, numbers is positive. These proofs all rely on induction and are straightforward to check, thus they are omitted. They can be found in On Numbers and Games [2]. We can re-write our definition of multiplication in the following form. xy = {xy − (x − XL )(y − YL ), xy − (XR − x)(YR − y)|xy + (x − XL )(YR − y), xy + (XR − x)(y − YL )} Although this form may not look much simpler, it is easier to see that multiplication is well defined. We need to verify that xy is greater than its left set and less than its right set. Thus the following inequalities should hold: xy > xy − (x − XL )(y − YL ) xy > xy − (XR − x)(YR − y) xy < xy + (x − XL )(YR − y) xy < xy + (XR − x)(y − YL ). Simplifying, we have (x − XL )(y − YL ) > 0 (XR − x)(YR − y) > 0 (x − XL )(YR − y) > 0 (XR − x)(y − YL ) > 0. Since the product in each inequality is either a product of two negative numbers or two positive numbers, it must be greater than zero. Therefore we can conclude that xy is a well defined number. In Conway’s On Numbers and Games he gives a definition of division for surreal numbers, and shows that each number x has a multiplicative inverse x1 such that x · x1 = 1. The notation for division is rather tedious, thus we won’t go into it in this paper, but with this knowledge we conclude that the surreals form a totally ordered field. 2.5 Day Two and Beyond Recall that by Day 2 we have the numbers −a < −1 < −b < 0 < b < 1 < a, where a = {1|} and b = {0|1}. Using our well-behaved definition of addition we can investigate sums of these numbers. For example, 1 + 1 = {0 + 1, 0 + 1|} = {1|} = a. Thus a must be 2. We would like for b to be 1 2 , which we can check by evaluating b + b. We have b + b = {b + 0|b + 1} = {b|b + 1}, but this number does not resemble anything in our list, meaning it has not yet been created. However, using 13 Figure 1: Day 0 to infinity [2] the Simplicity Theorem we see that 1 is the first number created between b and b + 1, therefore b + b = {b|b + 1} ≡ 1, as we hoped. So the seven numbers created by the second day are 1 1 −2 < −1 < − < 0 < < 1 < 2. 2 2 From Theorem 2.2 we know that on day 3 we will get the numbers {| − 2}, {−2| − 1}, {−1| − 21 }, {− 12 |0}, {0| 12 }, { 12 |1}, {1|2}, and {2|}. As with the new numbers from day 2, we can find the value of these numbers by adding them to themselves and other numbers. Since 1 + 2 = {2|}, we see that {2|} is 3. If we let x = {1|2}, then x + x = {x + 1|x + 2}. Since x is a number we know that 1 < x < 2, thus x + 1 > 2. The only number created by day 3 that is bigger than 2 is 3, and 3 = 1 + 2 < x + 2; therefore 3 is the simplest number between x + 1 and x + 2. Thus x + x = 3 and thus x = {1|2} ≡ 32 . Similarly we find that {0| 21 } is 14 and { 21 |1} is 34 . So the numbers created after four days are 3 1 1 1 1 3 3 3 −3 < −2 < − < −1 < − < − < − < 0 < < < < 1 < < 2 < 3. 2 4 2 4 4 2 4 2 Note that the value of a number created on day 3 is the arithmetic mean of its left and right set, which are adjacent numbers from day 2. Similarly, the value of a number created on day 4 is the mean of two adjacent numbers from day 3. In general, this pattern continues into infinite days and is pictured in Figure 1. Theorem 2.13. If the numbers at the end of n days are −xm < −xm−1 < · · · < −x2 < −x1 < x0 = 0 < x1 < x2 < · · · < xm−1 < xm , 14 then the new numbers created on the (n + 1)st day are {|−xm } < {−xm |−xm−1 } < · · · < {−x2 |−x1 } < {−x1 |0} < {0|x1 } < {x1 |x2 } < · · · < {xm−1 |xm } < {xm |}. Furthermore, for positive numbers, {xm |} ≡ xm + 1 and {xi |xi+1 } ≡ xi +xi+1 , 2 for i = 0, . . . m − 1. Thus for negative numbers, {| − xm } ≡ −(xm + 1) and i+1 {−xi+1 | − xi } ≡ − xi +x , for i = 0, . . . m − 1. 2 Proof. From Theorem 2.2 we know that the numbers created on the (n + 1)st day are {| − xm }, {−xm | − xm−1 }, . . . , {−x2 | − x1 }, {−x1 |0}, {0|x1 }, {x1 |x2 }, . . . , {xm−1 |xm }, {xm |}. To prove the order of the positive numbers, suppose that there exist some y = {xi−1 |xi } and z = {xi |xi+1 } such that y ≥ z. Then by Axiom 2, xi < y. But this is a contradiction because we know that xi−1 < y < xi , since y is a number. Thus {xi−1 |xi } < {xi |xi+1 }. Now let x = {xm |} and y = {xm−1 |xm }, and suppose that x ≤ y. Then by Axiom 2, xm < y, but this is a contradiction since xm−1 < y < xm . Thus {xm |} is the largest number created after n + 1 days. The order of the negative numbers follows in the same way. To prove that {xm |} is the integer xm +1, Consider the sum xm +1 = {xmL +1, xm +0|}. By induction we can assume that xm = {xmL |} is an integer where xmL = xm −1. Thus xmL +1 = xm −1+1 = xm and it follows that xm + 1 = {xm |}. Now consider a number, x, of the form x = {xi |xi+1 } created on the (n + 1)st day. Doubling x we see that {xi |xi+1 } + {xi |xi+1 } = {xi + x|xi+1 + x}. Since x is a number we know that xi < x < xi+1 . Thus xi + x < xi + xi+1 < xi+1 + x. If xi + xi+1 is the simplest number between xi + x and xi+1 + x, then {xi + x|xi+1 + x} ≡ xi + xi+1 by the Simplicity Theorem. Suppose there exists some number z simpler than xi + xi+1 such that xi + x < z < xi+1 + x. Then z = x + y for some y, which implies that xi < y < xi+1 . But xi and xi+1 are adjacent numbers, thus no such y exists. Therefore {xi |xi+1 } + {xi |xi+1 } = {xi + x|xi+1 + x} ≡ xi + xi+1 , which means that {xi |xi+1 } ≡ xi +xi+1 . 2 The result for negative numbers immediately follows by the definition of negation. 15 2.6 Day ω and Beyond We now see more generally the pattern of how numbers are formed: on the nth day the extreme numbers created are the integers −n and n, and each other number created is the arithmetic mean of the two previously created numbers that are closest to it in value. However, when will numbers such as 13 be formed? So far, all the numbers that we have looked at have been dyadic rational numbers, meaning that they are of the form 2mn , where m and n are integers. In other words, they have terminating decimal expansions. So when would 13 = 0.333333 . . . be formed? If we let the left and right set of a surreal number contain infinitely many numbers, then we can form numbers other than the dyadic rationals. To form 13 we need a sequence of numbers that approaches 13 from below as its left set, and a sequence of numbers that approaches it from above as its right set. Thus it seems probable that 5 21 11 the number x = { 14 , 16 , 64 , . . . | 12 , 38 , 32 , . . .} would be 13 . To verify this claim, we calculate x + x + x. First, note that 1 5 21 1 3 11 x + x = { + x, + x, + x, . . . | + x, + x, + x, . . .}, 4 16 64 2 8 32 and thus 1 5 21 1 3 11 (x + x) + x = { + x + x, + x + x, + x + x, . . . | + x + x, + x + x, + x + x, . . .}. 4 16 64 2 8 32 Every element of the left set of x + x + x is a positive number less than 1 and every element of the right set of x + x + x is a positive number greater than 1. For example, 12 + x + x is in the right set of x + x + x and we have that 12 + x + x > 12 + 14 + 14 = 1, since 14 is in the left set of x. Thus x + x + x ≡ 1, which means that x is 31 . We call the day that 13 and the rest of the reals are created on day ω, where ω is the earliest number greater than all the finite counting numbers [2]. Another familiar number created on day ω is π. Noting that the binary representation of π is π = 11.00100100001111 . . ., we can see that π = {11.001, 11.001001, 11.00100100001, . . . |11.1, 11.01, 11.0011, 11.00101, . . .}. We get ΠL by stopping at every 1 in the binary expansion of π, and we get ΠR by stopping at every 0 and chaging it to a 1 [1]. As well as the reals, we also get some interesting infinite numbers on the ω day. One number is ω itself, which is ω = {1, 2, 3, 4, . . . |}. We can show that it is larger than all the other numbers created through day ω. Suppose there exists some x = {XL |XR } such that x ≥ ω. Then by Axiom 2, for all n ∈ {1, 2, 3, 4, . . .}, n < x. But this is clearly a contradiction since the set {1, 2, 3, 4, . . .} has no upper bound. Thus x < ω for all x. Note that ω has many other forms such as ω = {1, 2, 4, 8, 16, . . . |}, or ω = {all dyadic numbers|} [2]. Similarly, −ω = {| − 1, −2, −3, . . .} is the most negative number created by day ω. In addition,  = {0|1, 21 , 14 , 81 , . . .} is the smallest positive number created on or before day ω. Using Axiom 2, it is not hard to see that  > 0 since the left set of  is 0, and 0 ≤ 0. Now, suppose there exists a nonzero real number x = {XL |XR } such that x ≤ . Then x < { 12 , 14 , 18 , . . .}. But this is impossible since x is a nonzero real number. Thus  < x. 16 Consider the product 1 1 ω = {ω − (ω − {1, 2, 4, . . .})|ω + ({1, , , . . .} − )(ω − {1, 2, 4, . . .})} 2 4 1 1 = {, 2, 4, . . . |ω + ({1 − , − , − , . . .})({ω − 1, ω − 2, ω − 4, . . .})}. 2 4 Since  is positive, yet smaller than any real number, the left set of ω is greater than 0, but less than 1. We also have that 1 1 ω + ({1 − , − , − , . . .})({ω − 1, ω − 2, ω − 4, . . .}) > ω + ({ω − 1, ω − 2, ω − 4, . . .}) > ω + 1 2 4 since ω is greater than any finite counting number. Thus the right set of ω is greater than 1. Therefore, by the Simplicity Theorem, ω = 1, which means that  is the reciprocal of ω. 1 We also have numbers such as {1|1 21 , 1 14 , 1 18 , 1 16 , . . .}, which is just barely bigger than 1. Thus surreal numbers fill in the tiny gaps between the reals, and they even continue to fill in the gaps between themselves. For example, from Theorem 2.13 we know that on the ω + 1 day we will get the number 2 = {0|} between  and 0, and the next day we will get 4 = {0| 2 }, which lies between  2 and 0, and so on and so on. From Theorem 2.13 we also see that we will get bigger and bigger infinites as the days go on. For example on the ω + 1 day we can create {ω|}, which turns out to be ω + 1, since ω + 1 = {2, 3, 4, 5, . . . , ω|} ≡ {ω|}. On the ω + 2 day we have ω + 2 = {3, 4, 5, . . . , ω + 1|} ≡ {ω + 1|}, on the ω + 3 day we have ω + 3 ≡ {ω + 2|}, and so on. Since ω + n is created on the (ω + n)th day for each integer n, on the 2ω day we have the number {ω + 1, ω + 2, ω + 3, ω + 4, . . . |}. Note that ω + ω = {ω + 1, ω + 2, ω + 3, ω + 4, . . . |}, thus this number must be 2ω. Similarly, 3ω = {2ω + 1, 2ω + 2, 2ω + 3, . . . |} is created on the 3ω day, and so on. Eventually, we can even create ω 2 = {ω, 2ω, 3ω, . . . |} and ω ω = {ω, ω 2 , ω 3 , . . .}. Note that we will also get infinite numbers between infinities. For example on the ω + 2 day we have ω + 21 = {1 12 , 2 12 , 3 21 , . . . , ω|ω + 1} ≡ {ω|ω + 1}, which is between ω and ω + 1. What happens when we subtract 1 from ω? We get ω − 1 = {0, 1, 2, 3, 4, . . . |ω}, which must be created on the ω + 1 day and is larger than all the integers, yet less than ω. Similarly, on the ω + 2 day we have ω − 2 = {0, 1, 2, . . . |ω, ω − 1}, which is larger than all the integers yet less than ω − 1. On the ω + 3 day we have ω − 3 = {0, 1, 2, |ω, ω − 1, ω − 2}, and so on. Consider the number z = {0, 1, 2, . . . |ω, ω − 1, ω − 2, . . .} [2]. If we calculate z + z then we find that z + z = {z, z + 1, z + 2, . . . |z + ω, z + ω − 1, z + ω − 2, . . .}. Note that for any positive integer, n, z + n < ω − n + n = ω, and z + ω − n > z + ω > ω. So ω lies in between the left and right set of z + z. Furthermore, by defintion, z is greater than any finite number, and thus the left set of z + z is greater than any finite number. Since ω is the simplest number greater than any finite number, we conclude that z + z ≡ ω, by the Simplicity Theorem. Thus z must be ω2 . 2.7 Induction with Infinite Day Sums Since we now know that a set of numbers could have an infinite day sum, we need to check that the proofs we have completed using day induction still hold. In the induction process we 17 noted that if a theorem fails for some x then it must fail for some xL ∈ XL , meaning that it fails for some xLL ∈ XLL , and so on. In each proof we have completed, every such sequence is eventually finite, meaning we reach a case in which XLLL...L is empty and we have the desired contradiction. For example, in proving that x + 0 = x, we have x + 0 = {XL + 0|XR + 0} and we need to assume that xL + 0 = xL for each xL ∈ XL by induction. If this assumption is false then XL + 0 = {XLL + 0|XLR + 0} 6= XL , meaning that either XLL + 0 6= XLL or XLR + 0 6= XLR , which would mean that either XLLL + 0 6= XLLL , XLLR + 0 6= XLLR , XLRL + 0 6= XLRL , or XLRR + 0 6= XLRR , and so on. Notice that any counterexample would imply an infinite sequence of counterexamples if there existed a sequence of numbers x1 , x2 , x3 , x4 , . . . such that xi+1 ∈ XiL ∪ XiR . We need to show that no such sequence exists. We can do this by using Axiom 1, which states that each number is created using previously created numbers. Whenever we create a number x we can prove that there does not exist an infinite sequence starting with x = x1 , since we would need to find an x2 in either the left or right set of x that is also the start of an infinite sequence. But because x2 ∈ XL ∪ XR , it must have been created before x, meaning that we have already proved that no such sequence exists. Thus our proofs by induction still hold for numbers with infinite day sums because any sequence of counterexamples is eventually finite. Also, we do not need to prove a base case as with traditional mathematical induction because we eventually get to a case involving the empty set. 3 3.1 Structures within S Generalized Integers Call x a generalized integer if x ≡ {x − 1|x + 1} [1]. For example, 0 is a generalized integer since 0 ≡ {−1|1}, by the Simplicity Theorem. Since −2 ≡ {−3| − 1}, −2 is a generalized integer. However, 41 is not a generalized integer since the simplest number between − 43 and 54 is clearly 0, meaning that 14 6≡ {− 34 | 45 }. In general, consider an integer n ≥ 1. From Theorem 2.13 we know that n − 1 was created on the (n − 1)st day and that the only number greater than n − 1 created through the nth day is n. On the (n + 1)st day the only two numbers greater than n − 1 that are formed are (n−1)+n and 2 (n−1)+n n + 1. Since n is simpler than , it is the simplest number between n − 1 and n + 1, meaning 2 that n ≡ {n − 1|n + 1}. Thus all positive integers are generalized integers. We can prove that all negative integers are generalized integers in the same way. On the other hand, consider the irreducible fraction ab , where a and b are non-generalized integers and b > 1. From Theorem 2.13 we know that the numbers between any integers n and n + 1 are formed on days after the (n + 1)st day. Thus for any two fractions that differ by at least 1, the simplest number between them will be an integer. Since ab −1 and ab +1 differ by 2, { ab −1| ab +1} ≡ n 18 for some integer n. Therefore { ab − 1| ab + 1} 6≡ ab , meaning that no proper fraction is a generalized integer. Along with the familiar integers, generalized integers also include some infinite numbers. Recall that on day ω we have the number ω = {0, 1, 2, . . . |}, and that on the (ω + 1)st day we have the numbers ω−1 = {0, 1, 2, . . . |ω} and ω+1 = {ω|}. Since ω is the only number between between ω−1 and ω + 1 by the (ω + 1)st day, ω ≡ {ω − 1|ω + 1}. Consider ω + n for any integer n ≥ 1. Similar to our investigation of finite generalized integers, ω + n − 1 was created on the (ω + n − 1)st day, ω + n was created on the (ω + n)th day, and the only two numbers greater than ω + n − 1 created on the (ω + n + 1)st day are (ω+n−1)+(ω+n) = ω + n − 12 and ω + n + 1. Thus ω + n ≡ {ω + n − 1|ω + n + 1}. 2 We can show that ω − n is a generalized integer for n ≥ 1 in the same way. What about ω2 = {1, 2, 3, . . . |ω, ω − 1, ω − 2, . . .}, created on day 2ω? Calculating ω2 − 1 = {0, 1, 2, . . . | ω2 } and ω2 + 1 = { ω2 |ω + 1, ω, ω − 1}, we see that both of these numbers must have been created on the 2ω + 1 day and that ω2 is the only number between ω2 − 1 and ω2 + 1 by the 2ω + 1 day. Thus ω2 ≡ { ω2 − 1| ω2 + 1}. So fractions involving ω are also generalized integers. Suppose x and y are generalized integers. Then x ≡ {x − 1|x + 1} and y ≡ {y − 1|y + 1}. It is not hard to check that the generalized integers are closed under addition, x + y = {x − 1 + y, y − 1 + x|x + 1 + y, y + 1 + x} = {x + y − 1|x + y + 1} subtraction, x − y = {x − 1 − y, −y − 1 + x|x + 1 − y, −y + 1 + x} = {x − y − 1|x − y + 1} and multiplication xy = {(x − 1)y + x(y − 1) − (x − 1)(y − 1), . . . |(x − 1)y + x(y + 1) − (x − 1)(y + 1), . . .} = {xy − 1|xy + 1}. Thus the generalized integers form a subring of the surreals, just as the integers form a subring of the real numbers. 3.2 Real Numbers Call x a *real number if −n < x < n for some (nongeneralized) integer n, and if x ≡ {x − 1, x − 12 , x − 14 , . . . |x + 1, x + 12 , x + 41 , . . .} [2]. It is clear that ω and other infinities are not *real since they are not bounded, but what about  = {0|1, 21 , 41 , 18 , . . .}, since −1 <  < 1? Consider 1 1 1 1 x = { − 1,  − ,  − , . . . | + 1,  + ,  + , . . .}. 2 4 2 4 19 Since  is smaller than every positive number, the left set of x is less than 0. Since  is positive, the right set of x is greater than 0. Thus 1 1 1 1 { − 1,  − ,  − , . . . | + 1,  + ,  + , . . .} ≡ 0, 2 4 2 4 which means that  is not a *real number, as we expected. Suppose x and y are *real numbers. Then we have the following three equalities: 1 1 1 1 x+y = {x−1+y +x− +y, . . . , x+y −1, x+y − , . . . |x+1+y, x+ +y, . . . , x+y +1, x+y + , . . .} 2 2 2 2 1 1 = {x + y − 1, x + y − , . . . |x + y + 1, x + y + , . . .}, 2 2 1 1 1 1 x−y = {x−1−y +x− −y, . . . , x−y −1, x−y − , . . . |x+1−y, x+ −y, . . . , x−y +1, x−y + , . . .} 2 2 2 2 1 1 = {x − y − 1, x − y − , . . . |x − y + 1, x − y + , . . .}, 2 2 1 1 1 1 xy = {{(x − 1)y, (x − )y, . . .} + {x(y − 1), x(y − ), . . .} − {x − 1, x − , . . .}{y − 1, y − , . . .}, . . . | 2 2 2 2 1 1 1 1 |{(x − 1)y, (x − )y, . . .} + {x(y + 1), x(y + ), . . .} − {x − 1, x − , . . .}{y + 1, y + , . . .}, . . .} 2 2 2 2 1 1 = {xy − 1, xy − , . . . |xy + 1, xy + , . . .}. 2 2 Since the *real numbers are closed under addition, subtraction, and multiplication, they form a subring of the surreals. It appears that the *real numbers of the surreals are essentially the same as the real numbers that we are more familiar with, which leads us to look for an isomorphism between the two. Consider the function f which maps R to the *real numbers of the surreals, defined by 1 1 1 1 f (x) = {x − 1, x − , x − , . . . |x + 1, x + , x + , . . .}. 2 4 2 4 We would like to show that f is bijective. Suppose that for real numbers x and y, f (x) = f (y). Then 1 1 1 1 {XL |XR } = {x − 1, x − , . . . |x + 1, x + , x . . .} = {y − 1, y − , . . . |y + 1, y + , . . .} = {YL |YR }. 2 2 2 2 If we take an xL ∈ XL , then xL < x − n1 for some n. Thus xL + 21n < x − n1 + 21n < x. Thus xL + 21n ∈ XL , which means that XL has no greatest element. Similarly YL has no greatest element. If we take an xR ∈ XR , then xR > x + n1 for some n. Thus xR − 21n > x + n1 − 21n > x. Since xR − 21n ∈ XR , we see that XR has no least element. Similarly YR has no least element. Thus 20 {x − 1, x − 12 , . . . |x + 1, x + 21 , x . . .} ≡ x and {y − 1, y − 21 , . . . |y + 1, y + 21 , . . .} ≡ y, which means that x = y. Therefore f is injective. We see that f is surjective since every *real number is of the form {x − 1, x − 12 , x − 41 , . . . |x + 1, x + 21 , x + 14 , . . .}, which is clearly the image of x under f . In addition, we note that for real numbers x and y, 1 1 f (x + y) = {x + y − 1, x + y − , . . . |x + y + 1, x + y + , . . .} = f (x) + f (y), 2 2 and 1 1 f (xy) = {xy − 1, xy − , . . . |xy + 1, xy + , . . .} = f (x)f (y). 2 2 Therefore f is a ring isomorphism from the reals to the *reals. Thus the real numbers of the surreals are an isomorphic copy of the real numbers that we are more familar with, meaning that we no longer have to distinguish them with a pesky asterisk! Note that we have also shown that the real numbers are contained within the surreal numbers. 3.3 A FUNction Defined on S We now investigate a function defined for surreal numbers. Assume g is a function from numbers to numbers such that x ≤ y implies g(x) ≤ g(y), and define f (x) = {f (XL ) ∪ {g(x)}|f (XR )} [1]. We can show that f is monotonically increasing, which means that f (x) ≤ f (y) if and only if x ≤ y. Suppose that f (x) ≤ f (y). Then by Axiom 2, f (XL ) < f (y), {g(x)} < f (y), and f (x) < f (YR ). To prove x ≤ y we need that i.) XL < y, and ii.) x < YR . For (i.) we take an arbitrary xL ∈ XL and note that f (xL ) < f (y). Since xL and y have a smaller day sum than x and y we can use induction to conclude that xL < y. We can prove (ii.) in the same way. Now suppose that x ≤ y. Then by Axiom 2, XL < y and x < YR . To prove f (x) ≤ f (y) we need that i.) f (XL ) < f (y), ii.) {g(x)} < f (y), and iii.) f (x) < f (YR ). 21 For (i.) we take an arbitrary xL ∈ XL . Since x is a number we have that xL < x ≤ y, and since xL and y have a smaller day sum than x and y, we can conclude that f (xL ) < f (y) by induction. We can prove (iii.) in the same way. To prove (ii.) we note that g(x) ≤ g(y). We can conclude that g(x) ≤ g(y) < f (y) if f (y) is a number, thus we must prove that f (x) is a number for all x. To show that f (x) is a number, we must show that its left set is strictly less than its right set. The following equalities must hold. iv.) f (XL ) < f (XR ), and v.) {g(x)} < f (XR ). Inequality (iv.) follows from induction since xL < xR for all xL and xR . To prove (v.), assume the contrary: that there exists some g(x) and f (xR ) such that g(x) ≥ f (xR ). Then, by definition, we have that g(x) < g(x), which is a contradiction since x ≤ x implies that g(x) ≤ g(x). Thus inequality (v.) holds, and it follows that f (x) is a number for all x. Furthermore, we can conclude that inequality (ii.) holds, completing our proof that f is monotonically increasing. What does this function actually look like? We can get an idea by computing values for a set function, g. Suppose we let g(x) = 0 for each surreal number x. Then f (x) is defined by f (x) = {f (XL ), 0|f (XR )}. Since f (x) is a number and 0 will be in the left set of every output of f , we can immediately see that f (x) > 0 for all x. If we assume that f (∅) = ∅ we find that f (0) = {f (∅), 0|f (∅)} = {0|} = 1. We can now compute 1 2 f (1) = {f (0), 0|f (∅)} = {1, 0|} ≡ 2, f (−1) = {f (∅), 0|f (0)} = {0|1} = and eventually we get the values of f (x) for all x created through the third day, shown in the table and plot below. x f (x) −3 −2 − 23 −1 − 43 − 21 − 41 0 1 8 1 4 3 8 1 2 5 8 3 4 7 8 1 1 4 1 2 3 4 5 4 3 2 7 4 1 2 3 2 5 2 2 3 3 4 f (x)     22            x We see that f is somewhat like the exponential fuction defined for real numbers in the domain (−∞, 0) of the surreals. However, in [0, ∞), f is the simple linear function f (x) = x + 1. 4 Surreal Numbers and Games We can think of any number g = {a, b, c, . . . |d, e, f, . . .}[2] as a game where the elements of the left set represent moves that one player can make, and the elements in the right set represent the moves that another player can make. For example, if g was a game between players Left and Right, then Left could move from some starting point, g, to any of a, b, c, . . ., and Right could move from g to any of d, e, f, . . .. If Left starts the game and moves to a, then the representation of the game is changed to a = {A, B, C, . . . |D, E, F, . . .}. Thus Right can now move to any of D, E, F, . . .. If she moves to E = {α, β, γ, . . . |, δ, ζ, . . .}, then Left can then move to any of , δ, ζ, . . ., and so on. The last person to make a move wins the game. Figure 2: A Hackenbush game [3] One specific game that we can consider is Hackenbush (Figure 2 provides a fancy example). Hackenbush is a two-player game played with a picture of nodes joined by edges that are colored with two different colors (we will use red and blue). The picture must be constructed so that you can reach the ground (which is the dotted line in Figure 2) from any node by travelling along a series of adjacent edges. The two players, Left and Right, take turns alternately. Left can delete only blue edges and Right can delete only red edges. After one edge is deleted, any edges no longer connected to the ground are also deleted. The last player to delete an edge wins. 4.1 Basic Games We will now analyze some simple games. If there are no red or blue edges then neither player has any moves, meaning that the game would be {∅|∅} = 0. We call this state endgame [2]. Note that the first person to move automatically loses. 23 If there is just one blue edge, then Left can move to 0 while Right has no moves; thus the game would be {0|} = 1. In this case, Left automatically wins since there are no legal moves for Right. If there were just one red edge, then Left would have no moves while Right could move to 0. Thus the game would be {|0} = −1, and Right would win. If there are two blue edges stacked on top of one another, then Left can pull the bottom edge to form game 0, or the top edge to form 1. Thus the game would be {0, 1|} ≡ {1|} = 2. Again, Left automaticallly wins. If we had two red edges stacked on top of each other then we would have the game {|0, −1} ≡ {| − 1} = −2. In general, if we have a chain n blue edges then the game will have a value of n, and if we have a chain of n red edges then the game will have a value of −n, where n is a positive integer. If there is one red edge and one blue edge coming from one node, then the game would be {−1|1}. Since the second player to move will cause an endgame, we see that the first player to move will lose. Thus this game is equivalent to 0, meaning the game 0 has multiple forms. If there is one red edge on top of one blue edge, then Left can delete the bottom edge to form game 0, while Right can delete the top edge to form game 1. Thus the game would be {0|1} = 12 . We note that Left will win regardless of who goes first. If we had one blue edge stacked on top of one red edge, then Left could delete the top edge to form −1 while Right could delete the bottom to form 0. Thus we would have {−1|0} = − 12 , and Right would win regardless of who goes first. In general we use the following notations from On Numbers and Games [2]: G > 0 (G is positive) if there is a winning strategy for Left 24 G < 0 (G is negative) if there is a winning strategy for Right G ≡ 0 (G is like 0) if there is a winning strategy for the second person to move G k 0 (G is fuzzy) if there is a winning stategy for the first person to move G ≥ 0 if G > 0 or G ≡ 0, which means that if Right starts there is a winning strategy for Left, since Left would then be the second to move. G ≤ 0 if G < 0 or G ≡ 0, which means that if Left starts there is a winning strategy for Right. G q> 0 if G > 0 or G k 0, which means if Left starts then there is a winning strategy for Left, since they would be the first to move. G h means that g is more favorable to Left than h, g < h means that g is less favorable to Left than h, and g k h means that g is only more favorable to Left if Left is the first to move. 26 From our studies of numbers we can conclude that all of the usual order relations hold. For example, if we have three games g, h, and k such that g < h and h < k, then g < k. We know that 1 > 12 , so the game 1 is more favorable to Left than 12 . However, recall how in both games Left won regardless, so how could one be more favorable than the other? Observe what happens if we give Right an extra move in 21 . If Left goes first, then Right will surely win. If Right goes first, she can win by first deleting the red edge in 12 . Since adding -1 to 12 turned the game to Right’s favor, Left had less than a one-move advantage in 21 ; whereas Left clearly has a one-move advantage in 1. Thus 1 > 21 . 4.4 Sums of Games If we have two games, g and h, then the sum g + h is the compound game that we get by playing both g and h simultaneously side by side, as we did with 12 and 1 in the previous section. For example consider the game 12 + 12 . We see that Left can move to 0 + 12 or 21 + 0, and Right can move to 1 + 12 or 21 + 1. Thus 1 1 1 1 1 1 2 + 2 = { 2 |1 + 2 } ≡ 1. We can also verify that the compound game 2 + 2 is 1 by adding −1 to it. Although we leave it to the interested reader, it is not hard to deduce that in 12 + 12 + (−1), the second player to move will win, and thus 12 + 12 + (−1) = 0. Suppose we have the sum of any two games g = {GL |GR } and h = {HL |HR }. Then the legal moves for Left will be GL + h ∪ g + HL and the legal moves for Right will be GR + h ∪ g + HR . Thus g + h = {GL + h, g + HL |GR + h, g + HR }, and we see that addition for games is consistent with our definition of addition for numbers. This means that we can apply the properites of addition that we have proved for numbers to two-color Hackenbush games. For example it is not hard to see that the game below is really just 12 , since adding a zero game to any other game will not change its outcome. 27 If we have any Hackenbush game, then we get the negative of that game by interchanging red and blue edges. When we negate g = {GL |GR }, the possible moves in GR become moves for Left, and the moves in GL become moves for Right. Thus −g = {−GR | − GL }, and we see that our definition is consistent with our definition for numbers. Thus we can conclude that g − g is a zero game for any two-color Hackenbush game g. For example, the game 41 − 14 pictured below is a zero game. 4.5 Hackenbush Hotchpotch So far we have been looking at two-color Hackenbush games in which each player can only delete edges of a certain color. Consider the following simple game, in which either player could delete the single green edge. We see that both players can move to 0. Thus the game has value {0|0}. By Axiom 1, since 0 ≤ 0, {0|0} is not a number, but a pseudo-number. Hackenbush Hotchpotch is just like Hackenbush except that there can be green edges in a picture, which either player can delete. Since every green edge represents a move for both Left and Right, we see that in every Hackenbush Hotchpotch game, g = {GL |GR }, there will be some x corresponding to the resulting position from deleting a green edge such that x ∈ GL and x ∈ GR . Thus GL 6< GR , which means that G is not a number by Axiom 1. Thus every Hackenbush Hotchpotch game is a pseudo-number. Consider the game, g, below. 28 Since the first player to move can delete the green edge, causing endgame, we see that whoever moves first will win. Thus g k 0. Since there is no particular advantage to Left or Right, why are these games not equal to zero? Consider the sum g + g below. Whether Left or Right starts, Right has enough edges so that she can force Left to delete one of the green edges first. Right can then win by taking the second green edge. Thus the sum g + g is negative. Clearly, a zero game plus a zero game cannot be negative. In fact, fuzzy games are neither equal to, greater than, or less than zero, but rather “confused” with zero [3]. Consider what 1 happens when we add a small positive number to g, like 64 . 1 The game g + 64 is positive, since Left will win either by deleting the green edge or, if Right deletes 1 the green edge, by deleting the blue edge from the component 64 . If we add a small negative 1 number, like − 64 , to g then we get the game pictured below. 29 This game is negative since Right will always win by either taking the green edge or her red edge of 1 1 1 − 64 . Thus − 64 < g < 64 . It is not hard to see that this argument will hold for smaller and smaller fractions, thus g will be greater than all negative numbers and less than all positive numbers. In fact, any Hackenbush picture in which all of the edges directly connected to the ground are green has a value that lies strictly between all negative and positive numbers [3]. However, such a game can still have a value that is positive or negative. Consider the house below. The first person forced to delete one of the green edges will lose, since the other player can then end the game by deleting the second green edge. Since Right can force Left to delete the first green edge by deleting her red edges on her first one or two turns (depending on who goes first), Right 1 can always win. Thus the game has a negative value. However, as before, if we add 64 , Left will 1 1 win. Thus house + 64 > 0, which means that the house is greater than − 64 . Again, this will hold for any negative number, which means that the house has a negative value, but is greater than any negative number. Conclusion Although we have just scratched the surface of game theory, we get an idea of how surreal numbers can be used to analyze games. In addition to Hackenbush, they can be applied to all sorts of two-player games, examples of which can be found in On Numbers and Games and Winning Ways. As well as looking deeper into game theory, interested readers can look into more advanced topics involving surreal numbers, such as number theory, algebra, and analysis. For example, how would √ polynomials with surreal coefficients behave? Or what would the field S[i] look like, where i = −1? Conway explores all of these topics, and more, in On Numbers and Games. References [1] Donald E. Knuth. Surreal Numbers. Reading, MA: Addison-Wesley Pub., 1974. Print. [2] John H. Conway. On Numbers and Games. London: Academic, 1976. Print. [3] Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning Ways, for Your Mathematical Plays. London: Academic, 1982. Print. 30