Surreal number
The surreal numbers are a class of numbers in mathematics that includes all of the real numbers and additional "infinite" numbers that are larger or smaller than any real number. They also include "infinitesimal" numbers that are closer to zero than any real number, and each real number is surrounded by surreals that are closer to it than any real number. The surreals are similar to the hyperreal numbers, but their construction is very different and the class of surreals is larger and contains the hyperreals as a subset. Mathematicians have praised the surreal numbers for being simpler, more general, and more cleanly constructed than the more common real number system.Surreal numbers were first proposed by John Conway and later detailed by Donald Knuth in his 1974 book Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. This book is a mathematical novelette, and is notable as one of the rare cases where a new mathematical idea was first presented in a work of fiction. In his book, which takes the form of a dialogue, Knuth coined the term surreal numbers for what Conway had simply called numbers originally. Conway liked the new name, and later adopted it himself. Conway then described the surreal numbers and used them for analyzing games in his 1976 book On Numbers and Games.
Constructing Surreal Numbers
The two rules are recursive, so we need some form of induction to put them to work. An obvious candidiate would be finite induction, i.e., generate all numbers that can be constructed by applying the construction rule a finite number of times, but, as will be explained later on, things get really interesting if we also allow transfinite induction, i.e., apply the rule more often than that. If we want the generated numbers to represent numbers then the ordering that is defined upon them should be a total order. However, the relation ≤ defines only a total preorder, i.e., it is not antisymmetric. To remedy this we define the binary relation == over the generated surreal numbers such that
- x == y iff x ≤ y and y ≤ x.
Let us now consider some examples and see how they behave under the ordering. The most simple example is of course
- { | } ie: { {} | {} }
- { 0 | }, { | 0 } and { 0 | 0 }
- { | 0\ } < 0 < { 0 | }
- { | 0 } < 0 < { 0 | }
- -1 < 0 < 1.
- { | -1 }
{ | -1, 0 }
{ | -1, 1 } == { | -1, 0, 1 } < - { | 0, 1 } == -1 <
- { -1 | 0 } == { -1 | 0, 1 } <
- { -1 | }
{ | 1 }
{ -1 | 1 } == 0 < - { 0 | 1 } == { -1, 0 | 1 } <
- { -1, 0 | } == 1 <
- { 1 | }
{ 0, 1 | }
{ -1, 1 | } == { -1, 0, 1 | }
- We have found four new equivalence classes, viz., [{ | -1 }], [{ -1 | 0 }], [{ 0 | 1 }] and [{ 1 | }].
- All equivalence classes now contain more than one element.
- The equivalence class of a number depends only on the maximal element of its left set and the minimal element of the right set.
The second observation raises the question if we can still replace the surreal numbers with their equivalence classes. Fortunately the answer is yes because it can be shown that
- if [X_{L}] = [Y_{L}] and [X_{R}] = [Y_{R}] then [{ X_{L} | X_{R} }] = [{ Y_{L} | Y_{R} }]
- { | -1 }
{ | -1, 0 }
{ | -1, 1 } == { | -1, 0, 1 } < - { |0, 1 } == -1 <
- { -1 | 0 } == { -1| 0, 1 } <
- { -1 | }
{ | 1 }
{ -1 | 1 } == 0 < - { 0 | 1 } == { -1, 0 | 1 } <
- { -1, 0 | } == 1 <
- { 1 | }
{ 0, 1 | }
{ -1, 1 | } == { -1, 0, 1 | }
- -2 < -1 < -1/2 < 0 < 1/2 < 1 < 2.
Computing with Surreal Numbers
The addition and multiplication of surreal numbers are defined by the following three rules:
;Addition: x + y = { X_{L} + y ∪ x + Y_{L} | X_{R} + y ∪ x + Y_{R} }
where X + y = { x + y | x in X } and x + Y = { x + y | y in Y }.
;Negation: -x = { -X_{R} | -X_{L} }
where XY = { xy | x in X and y in Y }, Xy = X{y} and xY = {x}Y.
Finally it can be shown that the generalized operations on the equivalence classes have the desired algebraic properties, i.e., the equivalence classes plus their ordering and the algebraic operations constitute an ordered field, with the caveat that they do not form a set but a proper class, see below. In fact, it is a very special ordered field: the biggest one. Every other ordered field can be embedded in the surreals. (See also the definition of rational numbers and real numbers.)From now on we don't distinguish a surreal number from its equivalence class, and call the equivalence class itself a surreal number.
Generating Surreal Numbers using Finite Induction
- S_{0} = {0}
- S_{i + 1} is S_{i} plus the set of all surreal numbers that are generated by the construction rule from subsets of S_{i}.
- S_{0} = { 0 }
- S_{1} = { -1 < 0 < 1 }
- S_{2} = { -2 < -1 < -1/2 < 0 < 1/2 < 1 < 2}
- S_{3} = { -3 < -2 < -1 1/2 < -1 < -3/4 < -1/2 < -1/4 < 0 < 1/4 < 1/2 < 3/4 < 1 < 1 1/2 < 2 < 3 }
- S_{4} = ...
- In every step the maximum (minimum) is increased (decreased) by 1.
- In every step we find the numbers that are in the middle of two consecutive numbers from the previous step.
- a / 2^{b}
"To Infinity and Beyond"
In fact, we can define a set S_{a} for any ordinal number a by transfinite induction. The first time a given surreal number appears in this process is called its birthday. Every surreal number has an ordinal number as its birthday. For example, the birthday of 0 is 0, and the birthday of 1/2 is 2.
Already in S_{ω+1} will we find the fractions that were missing in S_{ω}. For example, the fraction 1/3 can be defined as
- 1/3 = { { a / 2^{b} in S_{ω} | 3a < 2^{b} } | { a / 2^{b} in S_{ω} | 3a > 2^{b} } }.
- 3(1 / 3) == 1.
Not only do all the rest of the rational numbers appear in S_{ω+1}; the remaining finite real numbers do too. For example
- &pi = {3, 25/8, 201/64, ... | ..., 101/32, 51/16, 13/4, 7/2, 4}.
- ε = { 0 | ..., 1/16, 1/8, 1/4, 1/2, 1 }.
- 2ε = { ε | ..., ε + 1/16, ε + 1/8, ε + 1/4, ε + 1/2, ε + 1 } and
- ε / 2 = { 0 | ε }.
Next to infinitely small numbers also infinitely big numbers are generated such as
- ω = { S_{ω} | }.
- ω = [{ 1, 2, 3, 4, ... | }]
- ω + 1 = { ω | } and
- ω - 1 = { S_{ω} | ω }.
- ω + 2 = { ω + 1 | },
- ω + 3 = { ω + 2 | },
- ω - 2 = { S_{ω} | ω - 1 } and
- ω - 3 = { S_{ω} | ω - 2 }
- ω + ω = { ω + S_{ω} | }
- ω/2 = { S_{ω} | ω - S_{ω} }
- 1 / ε = ω
Since every surreal number is constructed from surreal numbers "older" than itself, we can prove many theorems about surreals using transfinite induction: We show that a theorem holds for 0, and then show that it holds for x = { X_{L} | X_{R} } if it holds for all elements of X_{L} and X_{R}.
Lots of numbers can be generated this way; in fact so many that no set can hold them all. The surreal numbers, like the ordinal numbers, form a proper class.
Games
;Construction Rule: If L and R are two sets of games then { L | R } is a game.
Every surreal number is a game, but not all games are surreal numbers, e.g. the game { 0 | 0 } is not a surreal number. The class of games is more general than the surreals, and has a simpler definition, but lacks some of the nicer properties of surreal numbers. The class of surreal numbers forms a field, but the class of games does not. The surreals have a total order: given any two surreals, they are either equal, or one is greater than the other. The games have only a partial order: there exist pairs of games that are neither equal, greater than, nor less than each other. Each surreal number is either positive, negative, or zero. Each game is either positive, negative, zero, or fuzzy (incomparable with zero, such as {1|-1}).
A move in a game involves the player whose move it is choosing a game from those available in L (for the left player) or R (for the right player) and then passing this chosen game to the other player. A player who cannot move because the choice is from the empty set has lost. A positive game represents a win for the left player, a negative game for the right player, a zero game for the second player to move, and a fuzzy game for the first player to move.
If x, y, and z are surreals, and x=y, then x z=y z. However, if x, y, and z are games, and x=y, then it is not always true that x z=y z. Note that "=" here means equality, not identity.
Surreal numbers and combinatorial game theory
The surreal numbers were originally motivated by studies of the game Go, and there are numerous connections between popular games and the surreals. In this section, we will use a capitalized Game for the mathematical object {L|R}, and the lowercase game for recreational games like Chess or Go.
We consider games with these properties:
- Two players (named Left and Right)
- Deterministic (no dice or shuffled cards)
- No hidden information (such as cards or tiles that a player hides)
- Players alternate taking turns
- Every game must end in a finite number of moves, even when the players don't alternate, and one player can move multiple times in a row
- As soon as there are no legal moves left for a player, the game ends, and that player loses
- If x>0 then Left will win
- If x<0 then Right will win
- If x=0 then the player who goes second will win
- If x is fuzzy then the player who goes first will win
- If a big game decomposes into two smaller games, and the small games have associated Games of x and y, then the big game will have an associated Game of x+y.
Historically, Conway developed the theory of surreal numbers in the reverse order of how it has been presented here. He was analyzing Go endgames, and realized that it would be useful to have some way to combine the analyses of non-interacting subgames. From this he invented the concept of a Game and the addition operator for it. From there he moved on to developing a definition of negation and comparison. Then he noticed that a certain class of Games had interesting properties; this class became the surreal numbers. Finally, he developed the multiplication operator, and proved that the surreals are actually a field, and that it includes both the reals and ordinals. It is amazing that all this came out of the study of Go!
Further reading
- A gentle yet thorough introduction by Claus Tøndering can be found at http://www.tondering.dk/claus/surreal.html
- Donald Knuth's original exposition: Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. 1974, ISBN 0201038129. More information can be found at the book's official homepage http://www-cs-faculty.stanford.edu/~knuth/sn.html
- An update of the classic 1976 book defining the surreal numbers, and exploring their connections to games: On Numbers And Games, 2nd ed., John Conway, 2001, ISBN 1568811276.
- An update of the first part of the 1981 book that presented surreal numbers and the analysis of games to a broader audience: Winning Ways for Your Mathematical Plays, vol. 1, 2nd ed., Berlekamp, Conway, and Guy, 2001, ISBN 1568811306.
- Martin Gardner Penrose Tiles to Trapdoor Ciphers chapter 4 — not especially technical overview; reprints the 1976 Scientific American article
Topics in mathematics related to quantity | Edit |
Numbers | Natural numbers | Integers | Rational numbers | Real numbers | Complex numbers | Hypercomplex numbers | Quaternions | Octonions | Sedenions | Hyperreal numbers | Surreal numbers | Ordinal numbers | Cardinal numbers | p-adic numberss | Integer sequences | Mathematical constants | Infinity | |