Early versions of Lisp programming language and minicomputer and microcomputer BASIC dialects would be examples of the first type. Perl, Raku, Python, MATLAB, and Ruby are examples of the second, while UCSD Pascal
is an example of the third type. Source programs are compiled ahead of
time and stored as machine independent code, which is then linked at run-time and executed by an interpreter and/or compiler (for JIT systems). Some systems, such as Smalltalk and contemporary versions of BASIC and Java may also combine two and three. Interpreters of various types have also been constructed for many languages traditionally associated with compilation, such as Algol, Fortran, Cobol, C and C++.
While interpretation and compilation are the two main means by
which programming languages are implemented, they are not mutually
exclusive, as most interpreting systems also perform some translation
work, just like compilers. The terms "interpreted language" or "compiled language" signify that the canonical implementation of that language is an interpreter or a compiler, respectively. A high-level language is ideally an abstraction independent of particular implementations.
History
Interpreters
were used as early as 1952 to ease programming within the limitations
of computers at the time (e.g. a shortage of program storage space, or
no native support for floating point numbers). Interpreters were also
used to translate between low-level machine languages, allowing code to
be written for machines that were still under construction and tested on
computers that already existed. The first interpreted high-level language was Lisp. Lisp was first implemented by Steve Russell on an IBM 704 computer. Russell had read John McCarthy's
paper, "Recursive Functions of Symbolic Expressions and Their
Computation by Machine, Part I", and realized (to McCarthy's surprise)
that the Lisp eval function could be implemented in machine code.[4]
The result was a working Lisp interpreter which could be used to run
Lisp programs, or more properly, "evaluate Lisp expressions".
General operation
An interpreter usually consists of a set of known commands it can execute, and a list of these commands in the order a programmer wishes to execute them. Each command (also known as an Instruction)
contains the data the programmer wants to mutate, and information on
how to mutate the data. For example, an interpreter might read ADD Books, 5 and interpret it as a request to add five to the Booksvariable.
While compilers (and assemblers) generally produce machine code
directly executable by computer hardware, they can often (optionally)
produce an intermediate form called object code. This is basically the same machine specific code but augmented with a symbol table
with names and tags to make executable blocks (or modules) identifiable
and relocatable. Compiled programs will typically use building blocks
(functions) kept in a library of such object code modules. A linker
is used to combine (pre-made) library files with the object file(s) of
the application to form a single executable file. The object files that
are used to generate an executable file are thus often produced at
different times, and sometimes even by different languages (capable of
generating the same object format).
A simple interpreter written in a low-level language (e.g. assembly)
may have similar machine code blocks implementing functions of the
high-level language stored, and executed when a function's entry in a
look up table points to that code. However, an interpreter written in a
high-level language typically uses another approach, such as generating
and then walking a parse tree, or by generating and executing intermediate software-defined instructions, or both.
Thus, both compilers and interpreters generally turn source code
(text files) into tokens, both may (or may not) generate a parse tree,
and both may generate immediate instructions (for a stack machine, quadruple code,
or by other means). The basic difference is that a compiler system,
including a (built in or separate) linker, generates a stand-alone machine code program, while an interpreter system instead performs the actions described by the high-level program.
A compiler can thus make almost all the conversions from source
code semantics to the machine level once and for all (i.e. until the
program has to be changed) while an interpreter has to do some of
this conversion work every time a statement or function is executed.
However, in an efficient interpreter, much of the translation work
(including analysis of types, and similar) is factored out and done only
the first time a program, module, function, or even statement, is run,
thus quite akin to how a compiler works. However, a compiled program
still runs much faster, under most circumstances, in part because
compilers are designed to optimize code, and may be given ample time for
this. This is especially true for simpler high-level languages without
(many) dynamic data structures, checks, or type checking.
In traditional compilation, the executable output of the linkers
(.exe files or .dll files or a library, see picture) is typically
relocatable when run under a general operating system, much like the
object code modules are but with the difference that this relocation is
done dynamically at run time, i.e. when the program is loaded for
execution. On the other hand, compiled and linked programs for small embedded systems are typically statically allocated, often hard coded in a NOR flash memory, as there is often no secondary storage and no operating system in this sense.
Historically, most interpreter systems have had a self-contained
editor built in. This is becoming more common also for compilers (then
often called an IDE),
although some programmers prefer to use an editor of their choice and
run the compiler, linker and other tools manually. Historically,
compilers predate interpreters because hardware at that time could not
support both the interpreter and interpreted code and the typical batch
environment of the time limited the advantages of interpretation.
Development cycle
During the software development cycle,
programmers make frequent changes to source code. When using a
compiler, each time a change is made to the source code, they must wait
for the compiler to translate the altered source files and link
all of the binary code files together before the program can be
executed. The larger the program, the longer the wait. By contrast, a
programmer using an interpreter does a lot less waiting, as the
interpreter usually just needs to translate the code being worked on to
an intermediate representation (or not translate it at all), thus
requiring much less time before the changes can be tested. Effects are
evident upon saving the source code and reloading the program. Compiled
code is generally less readily debugged as editing, compiling, and
linking are sequential processes that have to be conducted in the proper
sequence with a proper set of commands. For this reason, many compilers
also have an executive aid, known as a Makefile
and program. The Makefile lists compiler and linker command lines and
program source code files, but might take a simple command line menu
input (e.g. "Make 3") which selects the third group (set) of
instructions then issues the commands to the compiler, and linker
feeding the specified source code files.
Distribution
A compiler converts source code into binary instruction for a specific processor's architecture, thus making it less portable.
This conversion is made just once, on the developer's environment, and
after that the same binary can be distributed to the user's machines
where it can be executed without further translation. A cross compiler can generate binary code for the user machine even if it has a different processor than the machine where the code is compiled.
An interpreted program can be distributed as source code. It
needs to be translated in each final machine, which takes more time but
makes the program distribution independent of the machine's
architecture. However, the portability of interpreted source code is
dependent on the target machine actually having a suitable interpreter.
If the interpreter needs to be supplied along with the source, the
overall installation process is more complex than delivery of a
monolithic executable since the interpreter itself is part of what need
to be installed.
The fact that interpreted code can easily be read and copied by humans can be of concern from the point of view of copyright. However, various systems of encryption and obfuscation
exist. Delivery of intermediate code, such as bytecode, has a similar
effect to obfuscation, but bytecode could be decoded with a decompiler or disassembler.
Efficiency
The main disadvantage of interpreters is that an interpreted program typically runs slower than if it had been compiled.
The difference in speeds could be tiny or great; often an order of
magnitude and sometimes more. It generally takes longer to run a program
under an interpreter than to run the compiled code but it can take less
time to interpret it than the total time required to compile and run
it. This is especially important when prototyping and testing code when
an edit-interpret-debug cycle can often be much shorter than an
edit-compile-run-debug cycle.
Interpreting code is slower than running the compiled code because the interpreter must analyze each statement
in the program each time it is executed and then perform the desired
action, whereas the compiled code just performs the action within a
fixed context determined by the compilation. This run-time
analysis is known as "interpretive overhead". Access to variables is
also slower in an interpreter because the mapping of identifiers to
storage locations must be done repeatedly at run-time rather than at compile time.
There are various compromises between the development speed when using an interpreter and the execution speed when using a compiler. Some systems (such as some Lisps)
allow interpreted and compiled code to call each other and to share
variables. This means that once a routine has been tested and debugged
under the interpreter it can be compiled and thus benefit from faster
execution while other routines are being developed. Many interpreters do not execute the source code as it stands but convert it into some more compact internal form. Many BASIC interpreters replace keywords with single bytetokens which can be used to find the instruction in a jump table. A few interpreters, such as the PBASIC
interpreter, achieve even higher levels of program compaction by using a
bit-oriented rather than a byte-oriented program memory structure,
where commands tokens occupy perhaps 5 bits, nominally "16-bit"
constants are stored in a variable-length code
requiring 3, 6, 10, or 18 bits, and address operands include a "bit
offset". Many BASIC interpreters can store and read back their own
tokenized internal representation.
Regression
Interpretation
cannot be used as the sole method of execution: even though an
interpreter can itself be interpreted and so on, a directly executed
program is needed somewhere at the bottom of the stack because the code
being interpreted is not, by definition, the same as the machine code
that the CPU can execute.
There is a spectrum of possibilities between interpreting and
compiling, depending on the amount of analysis performed before the
program is executed. For example, Emacs Lisp is compiled to bytecode,
which is a highly compressed and optimized representation of the Lisp
source, but is not machine code (and therefore not tied to any
particular hardware). This "compiled" code is then interpreted by a
bytecode interpreter (itself written in C). The compiled code in this case is machine code for a virtual machine, which is implemented not in hardware, but in the bytecode interpreter. Such compiling interpreters are sometimes also called compreters.
In a bytecode interpreter each instruction starts with a byte, and
therefore bytecode interpreters have up to 256 instructions, although
not all may be used. Some bytecodes may take multiple bytes, and may be
arbitrarily complicated.
Control tables - that do not necessarily ever need to pass through a compiling phase - dictate appropriate algorithmic control flow via customized interpreters in similar fashion to bytecode interpreters.
Threaded code interpreters are similar to bytecode interpreters but
instead of bytes they use pointers. Each "instruction" is a word that
points to a function or an instruction sequence, possibly followed by a
parameter. The threaded code interpreter either loops fetching
instructions and calling the functions they point to, or fetches the
first instruction and jumps to it, and every instruction sequence ends
with a fetch and jump to the next instruction. Unlike bytecode there is
no effective limit on the number of different instructions other than
available memory and address space. The classic example of threaded code
is the Forth code used in Open Firmware systems: the source language is compiled into "F code" (a bytecode), which is then interpreted by a virtual machine.
In the spectrum between interpreting and compiling, another approach
is to transform the source code into an optimized abstract syntax tree
(AST), then execute the program following this tree structure, or use it
to generate native code just-in-time.
In this approach, each sentence needs to be parsed just once. As an
advantage over bytecode, the AST keeps the global program structure and
relations between statements (which is lost in a bytecode
representation), and when compressed provides a more compact
representation.
Thus, using AST has been proposed as a better intermediate format for
just-in-time compilers than bytecode. Also, it allows the system to
perform better analysis during runtime.
However, for interpreters, an AST causes more overhead than a
bytecode interpreter, because of nodes related to syntax performing no
useful work, of a less sequential representation (requiring traversal of
more pointers) and of overhead visiting the tree.
Further blurring the distinction between interpreters, bytecode
interpreters and compilation is just-in-time (JIT) compilation, a
technique in which the intermediate representation is compiled to native
machine code
at runtime. This confers the efficiency of running native code, at the
cost of startup time and increased memory use when the bytecode or AST
is first compiled. The earliest published JIT compiler is generally
attributed to work on LISP by John McCarthy in 1960. Adaptive optimization
is a complementary technique in which the interpreter profiles the
running program and compiles its most frequently executed parts into
native code. The latter technique is a few decades old, appearing in
languages such as Smalltalk in the 1980s.
Just-in-time compilation has gained mainstream attention amongst language implementers in recent years, with Java, the .NET Framework, most modern JavaScript implementations, and Matlab now including JIT compilers.
Template Interpreter
Making
the distinction between compilers and interpreters yet again even more
vague is a special interpreter design known as a template interpreter.
Rather than implement the execution of code by virtue of a large switch
statement containing every possible bytecode, while operating on a
software stack or a tree walk, a template interpreter maintains a large
array of bytecode (or any efficient intermediate representation) mapped
directly to corresponding native machine instructions that can be
executed on the host hardware as key value pairs (or in more efficient
designs, direct addresses to the native instructions),
known as a "Template". When the particular code segment is executed the
interpreter simply loads or jumps to the opcode mapping in the template
and directly runs it on the hardware.
Due to its design, the template interpreter very strongly resembles a
just-in-time compiler rather than a traditional interpreter, however it
is technically not a JIT due to the fact that it merely translates code
from the language into native calls one opcode at a time rather than
creating optimized sequences of CPU executable instructions from the
entire code segment. Due to the interpreter's simple design of simply
passing calls directly to the hardware rather than implementing them
directly, it is much faster than every other type, even bytecode
interpreters, and to an extent less prone to bugs, but as a tradeoff is
more difficult to maintain due to the interpreter having to support
translation to multiple different architectures instead of a platform
independent virtual machine/stack. To date, the only template
interpreter implementations of widely known languages to exist are the
interpreter within Java's official reference implementation, the Sun
HotSpot Java Virtual Machine, and the Ignition Interpreter in the Google V8 javascript execution engine.
A self-interpreter is a programming language interpreter written in a programming language which can interpret itself; an example is a BASIC interpreter written in BASIC. Self-interpreters are related to self-hosting compilers.
If no compiler
exists for the language to be interpreted, creating a self-interpreter
requires the implementation of the language in a host language (which
may be another programming language or assembler). By having a first interpreter such as this, the system is bootstrapped and new versions of the interpreter can be developed in the language itself. It was in this way that Donald Knuth developed the TANGLE interpreter for the language WEB of the industrial standard TeXtypesetting system.
Defining a computer language is usually done in relation to an abstract machine (so-called operational semantics) or as a mathematical function (denotational semantics).
A language may also be defined by an interpreter in which the semantics
of the host language is given. The definition of a language by a
self-interpreter is not well-founded (it cannot define a language), but a
self-interpreter tells a reader about the expressiveness and elegance
of a language. It also enables the interpreter to interpret its source
code, the first step towards reflective interpreting.
An important design dimension in the implementation of a
self-interpreter is whether a feature of the interpreted language is
implemented with the same feature in the interpreter's host language. An
example is whether a closure in a Lisp-like
language is implemented using closures in the interpreter language or
implemented "manually" with a data structure explicitly storing the
environment. The more features implemented by the same feature in the
host language, the less control the programmer of the interpreter has; a
different behavior for dealing with number overflows cannot be realized
if the arithmetic operations are delegated to corresponding operations
in the host language.
Some languages such as Lisp and Prolog have elegant self-interpreters. Much research on self-interpreters (particularly reflective interpreters) has been conducted in the Scheme programming language, a dialect of Lisp. In general, however, any Turing-complete
language allows writing of its own interpreter. Lisp is such a
language, because Lisp programs are lists of symbols and other lists.
XSLT is such a language, because XSLT programs are written in XML. A
sub-domain of metaprogramming is the writing of domain-specific languages (DSLs).
Clive Gifford introduced a measure quality of self-interpreter (the eigenratio), the limit of the ratio between computer time spent running a stack of N self-interpreters and time spent to run a stack of N − 1 self-interpreters as N goes to infinity. This value does not depend on the program being run.
Microcode typically resides in special high-speed memory and translates machine instructions, state machine
data or other input into sequences of detailed circuit-level
operations. It separates the machine instructions from the underlying electronics
so that instructions can be designed and altered more freely. It also
facilitates the building of complex multi-step instructions, while
reducing the complexity of computer circuits. Writing microcode is often
called microprogramming and the microcode in a particular processor implementation is sometimes called a microprogram.
More extensive microcoding allows small and simple microarchitectures to emulate more powerful architectures with wider word length, more execution units and so on, which is a relatively simple way to achieve software compatibility between different products in a processor family.
Computer processor
Even
a non microcoding computer processor itself can be considered to be a
parsing immediate execution interpreter that is written in a general
purpose hardware description language such as VHDL to create a system that parses the machine code instructions and immediately executes them.
Applications
Interpreters are frequently used to execute command languages, and glue languages since each operator executed in command language is usually an invocation of a complex routine such as an editor or compiler.
Virtualization. Machine code intended for a hardware architecture can be run using a virtual machine. This is often used when the intended architecture is unavailable, or among other uses, for running multiple copies.
Sandboxing:
While some types of sandboxes rely on operating system protections, an
interpreter or virtual machine is often used. The actual hardware
architecture and the originally intended hardware architecture may or
may not be the same. This may seem pointless, except that sandboxes are
not compelled to actually execute all the instructions the source code
it is processing. In particular, it can refuse to execute code that
violates any security constraints it is operating under.
Emulators for running computer software written for obsolete and unavailable hardware on more modern equipment.
The surreals share many properties with the reals, including the
usual arithmetic operations (addition, subtraction, multiplication, and
division); as such, they form an ordered field. If formulated in von Neumann–Bernays–Gödel set theory,
the surreal numbers are a universal ordered field in the sense that all
other ordered fields, such as the rationals, the reals, the rational functions, the Levi-Civita field, the superreal numbers (including the hyperreal numbers) can be realized as subfields of the surreals. The surreals also contain all transfiniteordinal numbers; the arithmetic on them is given by the natural operations. It has also been shown (in von Neumann–Bernays–Gödel set theory) that the maximal class hyperreal field is isomorphic to the maximal class surreal field.
History of the concept
Research on the Go endgame by John Horton Conway led to the original definition and construction of the surreal numbers. Conway's construction was introduced in Donald Knuth's 1974 book Surreal Numbers: How Two Ex-Students Turned On to Pure Mathematics and Found Total Happiness. In his book, which takes the form of a dialogue, Knuth coined the term surreal numbers for what Conway had called simply numbers. Conway later adopted Knuth's term, and used surreals for analyzing games in his 1976 book On Numbers and Games.
A separate route to defining the surreals began in 1907, when Hans Hahn introduced Hahn series as a generalization of formal power series, and Hausdorff introduced certain ordered sets called ηα-sets for ordinals α
and asked if it was possible to find a compatible ordered group or
field structure. In 1962, Norman Alling used a modified form of Hahn
series to construct such ordered fields associated to certain ordinals α
and, in 1987, he showed that taking α to be the class of all ordinals in his construction gives a class that is an ordered field isomorphic to the surreal numbers.
If the surreals are considered as 'just' a proper-class-sized real closed field, Alling's 1962 paper handles the case of strongly inaccessible cardinals which can naturally be considered as proper classes by cutting off the cumulative hierarchy of the universe
one stage above the cardinal, and Alling accordingly deserves much
credit for the discovery/invention of the surreals in this sense. There
is an important additional field structure on the surreals that isn't
visible through this lens however, namely the notion of a 'birthday' and
the corresponding natural description of the surreals as the result of a
cut-filling process along their birthdays given by Conway. This
additional structure has become fundamental to a modern understanding of
the surreal numbers, and Conway is thus given credit for discovering
the surreals as we know them today—Alling himself gives Conway full
credit in a 1985 paper preceding his book on the subject.
Description
In the Conway construction, the surreal numbers are constructed in stages, along with an ordering ≤ such that for any two surreal numbers a and b, a ≤ b or b ≤ a. (Both may hold, in which case a and b
are equivalent and denote the same number.) Each number is formed from
an ordered pair of subsets of numbers already constructed: given
subsets L and R of numbers such that all the members of L are strictly less than all the members of R, then the pair { L | R } represents a number intermediate in value between all the members of L and all the members of R.
Different subsets may end up defining the same number: { L | R } and { L′ | R′ } may define the same number even if L ≠ L′ and R ≠ R′. (A similar phenomenon occurs when rational numbers are defined as quotients of integers: 1/2 and 2/4 are different representations of the same rational number.) So strictly speaking, the surreal numbers are equivalence classes of representations of the form { L | R } that designate the same number.
In the first stage of construction, there are no previously
existing numbers so the only representation must use the empty set: { | }. This representation, where L and R are both empty, is called 0. Subsequent stages yield forms like
{ 0 | } = 1
{ 1 | } = 2
{ 2 | } = 3
and
{ | 0 } = −1
{ | −1 } = −2
{ | −2 } = −3
The integers are thus contained within the surreal numbers. (The
above identities are definitions, in the sense that the right-hand side
is a name for the left-hand side. That the names are actually
appropriate will be evident when the arithmetic operations on surreal
numbers are defined, as in the section below). Similarly,
representations such as
{ 0 | 1 } = 1/2
{ 0 | 1/2 } = 1/4
{ 1/2 | 1 } = 3/4
arise, so that the dyadic rationals (rational numbers whose denominators are powers of 2) are contained within the surreal numbers.
After an infinite number of stages, infinite subsets become available, so that any real numbera can be represented by { La | Ra },
where La is the set of all dyadic rationals less than a and
Ra is the set of all dyadic rationals greater than a (reminiscent of a Dedekind cut). Thus the real numbers are also embedded within the surreals.
There are also representations like
{ 0, 1, 2, 3, ... | } = ω
{ 0 | 1, 1/2, 1/4, 1/8, ... } = ε
where ω is a transfinite number greater than all integers and ε
is an infinitesimal greater than 0 but less than any positive real
number. Moreover, the standard arithmetic operations (addition,
subtraction, multiplication, and division) can be extended to these
non-real numbers in a manner that turns the collection of surreal
numbers into an ordered field, so that one can talk about 2ω or ω − 1 and so forth.
Construction
Surreal numbers are constructed inductively as equivalence classes of pairs
of sets of surreal numbers, restricted by the condition that each
element of the first set is smaller than each element of the second set.
The construction consists of three interdependent parts: the
construction rule, the comparison rule and the equivalence rule.
Forms
A form is a pair of sets of surreal numbers, called its left set and its right set. A form with left set L and right set R is written { L | R }. When L and R are given as lists of elements, the braces around them are omitted.
Either or both of the left and right set of a form may be the empty set. The form { { } | { } } with both left and right set empty is also written { | }.
Numeric forms and their equivalence classes
Construction rule
A form { L | R } is numeric if the intersection of L and R is the empty set and each element of R is greater than every element of L, according to the order relation ≤ given by the comparison rule below.
The numeric forms are placed in equivalence classes; each such equivalence class is a surreal number. The elements of the left and right sets of a form are drawn from the universe of the surreal numbers (not of forms, but of their equivalence classes).
Equivalence rule
Two numeric forms x and y are forms of the same number (lie in the same equivalence class) if and only if both x ≤ y and y ≤ x.
An ordering relationship must be antisymmetric, i.e., it must have the property that x = y (i. e., x ≤ y and y ≤ x are both true) only when x and y are the same object. This is not the case for surreal number forms, but is true by construction for surreal numbers (equivalence classes).
The equivalence class containing { | } is labeled 0; in other words, { | } is a form of the surreal number 0.
Order
The recursive definition of surreal numbers is completed by defining comparison:
Given numeric forms x = { XL | XR } and y = { YL | YR }, x ≤ y if and only if both:
There is no xL ∈ XL such that y ≤ xL. That is, every element in the left part of x is strictly smaller than y.
There is no yR ∈ YR such that yR ≤ x. That is, every element in the right part of y is strictly larger than x.
Surreal numbers can be compared to each other (or to numeric forms)
by choosing a numeric form from its equivalence class to represent each
surreal number.
Induction
This group of definitions is recursive, and requires some form of mathematical induction to define the universe of objects (forms and numbers) that occur in them. The only surreal numbers reachable via finite induction are the dyadic fractions; a wider universe is reachable given some form of transfinite induction.
Induction rule
There is a generation S0 = { 0 }, in which 0 consists of the single form { | }.
Given any ordinal numbern, the generation Sn is the set of all surreal numbers that are generated by the construction rule from subsets of .
The base case is actually a special case of the induction rule, with 0
taken as a label for the "least ordinal". Since there exists no Si with i < 0, the expression is the empty set; the only subset of the empty set is the empty set, and therefore S0 consists of a single surreal form { | } lying in a single equivalence class 0.
For every finite ordinal number n, Sn is well-ordered by the ordering induced by the comparison rule on the surreal numbers.
The first iteration of the induction rule produces the three
numeric forms { | 0 } < { | } < { 0 | } (the form { 0 | 0 } is
non-numeric because 0 ≤ 0). The equivalence class containing { 0 | } is
labeled 1 and the equivalence class containing { | 0 } is labeled −1.
These three labels have a special significance in the axioms that define
a ring;
they are the additive identity (0), the multiplicative identity (1),
and the additive inverse of 1 (−1). The arithmetic operations defined
below are consistent with these labels.
For every i < n, since every valid form in Si is also a valid form in Sn, all of the numbers in Si also appear in Sn (as supersets of their representation in Si). (The set union expression appears in our construction rule, rather than the simpler form Sn−1, so that the definition also makes sense when n is a limit ordinal.) Numbers in Sn that are a superset of some number in Si are said to have been inherited from generation i. The smallest value of α for which a given surreal number appears in Sα is called its birthday. For example, the birthday of 0 is 0, and the birthday of −1 is 1.
A second iteration of the construction rule yields the following ordering of equivalence classes:
Comparison of these equivalence classes is consistent, irrespective of the choice of form. Three observations follow:
S2 contains four new surreal numbers. Two
contain extremal forms: { | −1, 0, 1 } contains all numbers from
previous generations in its right set, and { −1, 0, 1 | } contains all
numbers from previous generations in its left set. The others have a
form that partitions all numbers from previous generations into two
non-empty sets.
Every surreal number x that existed in the previous
"generation" exists also in this generation, and includes at least one
new form: a partition of all numbers other thanx from previous generations into a left set (all numbers less than x) and a right set (all numbers greater than x).
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 informal interpretations of { 1 | } and { | −1 } are "the number
just after 1" and "the number just before −1" respectively; their
equivalence classes are labeled 2 and −2. The informal interpretations
of { 0 | 1 } and { −1 | 0 } are "the number halfway between 0 and 1" and
"the number halfway between −1 and 0" respectively; their equivalence
classes are labeled 1/2 and −1/2. These labels will also be justified by the rules for surreal addition and multiplication below.
The equivalence classes at each stage n of induction may be characterized by their n-complete forms
(each containing as many elements as possible of previous generations
in its left and right sets). Either this complete form contains every
number from previous generations in its left or right set, in which
case this is the first generation in which this number occurs; or it
contains all numbers from previous generations but one, in which case it
is a new form of this one number. We retain the labels from the
previous generation for these "old" numbers, and write the ordering
above using the old and new labels:
−2 < −1 < −1/2 < 0 < 1/2 < 1 < 2.
The third observation extends to all surreal numbers with finite left
and right sets. (For infinite left or right sets, this is valid in an
altered form, since infinite sets might not contain a maximal or minimal
element.) The number { 1, 2 | 5, 8 } is therefore equivalent to { 2 | 5
}; one can establish that these are forms of 3 by using the birthday property, which is a consequence of the rules above.
Birthday property
A form x = { L | R } occurring in generation n represents a number inherited from an earlier generation i < n if and only if there is some number in Si that is greater than all elements of L and less than all elements of the R. (In other words, if L and R are already separated by a number created at an earlier stage, then x does not represent a new number but one already constructed.) If x represents a number from any generation earlier than n, there is a least such generation i, and exactly one number c with this least i as its birthday that lies between L and R; x is a form of this c. In other words, it lies in the equivalence class in Sn that is a superset of the representation of c in generation i.
Arithmetic
The addition, negation (additive inverse), and multiplication of surreal number formsx = { XL | XR } and y = { YL | YR } are defined by three recursive formulas.
Negation
Negation of a given number x = { XL | XR } is defined by
where the negation of a set S of numbers is given by the set of the negated elements of S:
This formula involves the negation of the surreal numbers appearing in the left and right sets of x,
which is to be understood as the result of choosing a form of the
number, evaluating the negation of this form, and taking the equivalence
class of the resulting form. This only makes sense if the result is
the same, irrespective of the choice of form of the operand. This can
be proved inductively using the fact that the numbers occurring in XL and XR are drawn from generations earlier than that in which the form x first occurs, and observing the special case:
Addition
The definition of addition is also a recursive formula:
where
.
This formula involves sums of one of the original operands and a
surreal number drawn from the left or right set of the other. It can be
proved inductively with the special cases:
which by the birthday property is a form of 1. This justifies the label used in the previous section.
Multiplication
Multiplication can be defined recursively as well, beginning from the special cases involving 0, the multiplicative identity 1, and its additive inverse −1:
The formula contains arithmetic expressions involving the operands and their left and right sets, such as the expression that appears in the left set of the product of x and y. This is understood as the set of numbers generated by picking all possible combinations of members of and , and substituting them into the expression.
For example, to show that the square of 1/2 is 1/4:
The definition of division is done in terms of the reciprocal and multiplication:
where
for positive y. Only positive yL are permitted in the formula, with any nonpositive terms being ignored (and yR
are always positive). This formula involves not only recursion in terms
of being able to divide by numbers from the left and right sets of y, but also recursion in that the members of the left and right sets of 1/y itself. 0 is always a member of the left set of 1/y, and that can be used to find more terms in a recursive fashion. For example, if y = 3 = { 2 | }, then we know a left term of 1/3 will be 0. This in turn means 1 + (2 − 3)0/2 = 1/2 is a right term. This means
is a left term. This means
will be a right term. Continuing, this gives
For negative y, 1/y is given by
If y = 0, then 1/y is undefined.
Consistency
It can be shown that the definitions of negation, addition and multiplication are consistent, in the sense that:
Addition and negation are defined recursively in terms of
"simpler" addition and negation steps, so that operations on numbers
with birthday n will eventually be expressed entirely in terms of operations on numbers with birthdays less than n;
Multiplication is defined recursively in terms of additions,
negations, and "simpler" multiplication steps, so that the product of
numbers with birthday n will eventually be expressed entirely in terms of sums and differences of products of numbers with birthdays less than n;
As long as the operands are well-defined surreal number forms (each
element of the left set is less than each element of the right set), the
results are again well-defined surreal number forms;
The operations can be extended to numbers (equivalence classes of forms): the result of negating x or adding or multiplying x and y will represent the same number regardless of the choice of form of x and y; and
These operations obey the associativity, commutativity, additive inverse, and distributivity axioms in the definition of a field, with additive identity 0 = { | } and multiplicative identity 1 = { 0 | }.
With these rules one can now verify that the numbers found in the
first few generations were properly labeled. The construction rule is
repeated to obtain more generations of surreals:
The set of all surreal numbers that are generated in some Sn for finite n may be denoted as . One may form the three classes
of which S∗ is the union. No individual Sn is closed under addition and multiplication (except S0), but S∗ is; it is the subring of the rationals consisting of all dyadic fractions.
There are infinite ordinal numbers β for which the set of surreal
numbers with birthday less than β is closed under the different
arithmetic operations. For any ordinal α, the set of surreal numbers with birthday less than β = ωα (using powers of ω) is closed under addition and forms a group; for birthday less than ωωα it is closed under multiplication and forms a ring; and for birthday less than an (ordinal) epsilon number εα
it is closed under multiplicative inverse and forms a field. The latter
sets are also closed under the exponential function as defined by
Kruskal and Gonshor.
However, it is always possible to construct a surreal number that
is greater than any member of a set of surreals (by including the set
on the left side of the constructor) and thus the collection of surreal
numbers is a proper class. With their ordering and algebraic operations they constitute an ordered field, with the caveat that they do not form a set. In fact it is the biggest ordered field, in that every ordered field is a subfield of the surreal numbers. The class of all surreal numbers is denoted by the symbol .
Infinity
Define Sω as the set of all surreal numbers generated by the construction rule from subsets of S∗.
(This is the same inductive step as before, since the ordinal number ω
is the smallest ordinal that is larger than all natural numbers;
however, the set union appearing in the inductive step is now an
infinite union of finite sets, and so this step can only be performed in
a set theory that allows such a union.) A unique infinitely large
positive number occurs in Sω:
Sω also contains objects that can be identified as the rational numbers. For example, the ω-complete form of the fraction 1/3 is given by:
The product of this form of 1/3
with any form of 3 is a form whose left set contains only numbers less
than 1 and whose right set contains only numbers greater than 1; the
birthday property implies that this product is a form of 1.
Not only do all the rest of the rational numbers appear in Sω; the remaining finite real numbers do too. For example,
The only infinities in Sω are ω and −ω; but there are other non-real numbers in Sω among the reals. Consider the smallest positive number in Sω:
.
This number is larger than zero but less than all positive dyadic fractions. It is therefore an infinitesimal number, often labeled ε. The ω-complete form of ε (respectively −ε) is the same as the ω-complete form of 0, except that 0 is included in the left (respectively right) set. The only "pure" infinitesimals in Sω are ε and its additive inverse −ε; adding them to any dyadic fraction y produces the numbers y ± ε, which also lie in Sω.
One can determine the relationship between ω and ε by multiplying particular forms of them to obtain:
ω · ε = { ε · S+ | ω · S+ + S∗ + ε · S∗ }.
This expression is only well-defined in a set theory which permits transfinite induction up to Sω2. In such a system, one can demonstrate that all the elements of the left set of ωSω·Sωε are positive infinitesimals and all the elements of the right set are positive infinities, and therefore ωSω·Sωε is the oldest positive finite number, 1. Consequently, 1/ε = ω. Some authors systematically use ω−1 in place of the symbol ε.
Contents of Sω
Given any x = { L | R } in Sω, exactly one of the following is true:
L and R are both empty, in which case x = 0;
R is empty and some integer n ≥ 0 is greater than every element of L, in which case x equals the smallest such integer n;
R is empty and no integer n is greater than every element of L, in which case x equals +ω;
L is empty and some integer n ≤ 0 is less than every element of R, in which case x equals the largest such integer n;
L is empty and no integer n is less than every element of R, in which case x equals −ω;
L and R are both non-empty, and:
Some dyadic fraction y is "strictly between" L and R (greater than all elements of L and less than all elements of R), in which case x equals the oldest such dyadic fraction y;
No dyadic fraction y lies strictly between L and R, but some dyadic fraction is greater than or equal to all elements of L and less than all elements of R, in which case x equals y + ε;
No dyadic fraction y lies strictly between L and R, but some dyadic fraction is greater than all elements of L and less than or equal to all elements of R, in which case x equals y − ε;
Every dyadic fraction is either greater than some element of R or less than some element of L, in which case x is some real number that has no representation as a dyadic fraction.
Sω is not an algebraic field, because it is not closed under arithmetic operations; consider ω+1, whose form
does not lie in any number in Sω. The maximal subset of Sω
that is closed under (finite series of) arithmetic operations is the
field of real numbers, obtained by leaving out the infinities ±ω, the
infinitesimals ±ε, and the infinitesimal neighbors y ± ε of each nonzero dyadic fraction y.
This construction of the real numbers differs from the Dedekind cuts of standard analysis in that it starts from dyadic fractions rather than general rationals and naturally identifies each dyadic fraction in Sω with its forms in previous generations. (The ω-complete forms of real elements of Sω
are in one-to-one correspondence with the reals obtained by Dedekind
cuts, under the proviso that Dedekind reals corresponding to rational
numbers are represented by the form in which the cut point is omitted
from both left and right sets.) The rationals are not an identifiable
stage in the surreal construction; they are merely the subset Q of Sω containing all elements x such that xb = a for some a and some nonzero b, both drawn from S∗. By demonstrating that Q
is closed under individual repetitions of the surreal arithmetic
operations, one can show that it is a field; and by showing that every
element of Q is reachable from S∗ by a finite series (no longer than two, actually) of arithmetic operations including multiplicative inversion, one can show that Q is strictly smaller than the subset of Sω identified with the reals.
The set Sω has the same cardinality as the real numbers R. This can be demonstrated by exhibiting surjective mappings from Sω to the closed unit interval I of R and vice versa. Mapping Sω onto I
is routine; map numbers less than or equal to ε (including −ω) to 0,
numbers greater than or equal to 1 − ε (including ω) to 1, and numbers
between ε and 1 − ε to their equivalent in I (mapping the infinitesimal neighbors y±ε of each dyadic fraction y, along with y itself, to y). To map I onto Sω, map the (open) central third (1/3, 2/3) of I onto { | } = 0; the central third (7/9, 8/9) of the upper third to { 0 | } = 1; and so forth. This maps a nonempty open interval of I onto each element of S∗, monotonically. The residue of I consists of the Cantor set2ω,
each point of which is uniquely identified by a partition of the
central-third intervals into left and right sets, corresponding
precisely to a form { L | R } in Sω. This places the Cantor set in one-to-one correspondence with the set of surreal numbers with birthday ω.
Transfinite induction
Continuing to perform transfinite induction beyond Sω
produces more ordinal numbers α, each represented as the largest
surreal number having birthday α. (This is essentially a definition of
the ordinal numbers resulting from transfinite induction.) The first
such ordinal is ω+1 = { ω | }. There is another positive infinite
number in generation ω+1:
ω − 1 = { 1, 2, 3, 4, ... | ω }.
The surreal number ω − 1 is not an ordinal; the ordinal ω is not the
successor of any ordinal. This is a surreal number with birthday ω+1,
which is labeled ω − 1 on the basis that it coincides with the sum of ω = { 1, 2, 3, 4, ... | } and −1 = { | 0 }. Similarly, there are two new infinitesimal numbers in generation ω + 1:
At a later stage of transfinite induction, there is a number larger than ω + k for all natural numbers k:
2ω = ω + ω = { ω+1, ω+2, ω+3, ω+4, ... | }
This number may be labeled ω + ω both because its birthday is ω + ω
(the first ordinal number not reachable from ω by the successor
operation) and because it coincides with the surreal sum of ω and ω; it
may also be labeled 2ω because it coincides with the product of ω = { 1, 2, 3, 4, ... | } and 2 = { 1 | }. It is the second limit ordinal; reaching it from ω via the construction step requires a transfinite induction on
This involves an infinite union of infinite sets, which is a
"stronger" set theoretic operation than the previous transfinite
induction required.
Note that the conventional addition and multiplication of
ordinals does not always coincide with these operations on their surreal
representations. The sum of ordinals 1 + ω equals ω, but the surreal
sum is commutative and produces 1 + ω = ω + 1 > ω. The addition and
multiplication of the surreal numbers associated with ordinals coincides
with the natural sum and natural product of ordinals.
Just as 2ω is bigger than ω + n for any natural number n, there is a surreal number ω/2 that is infinite but smaller than ω − n for any natural number n. That is, ω/2 is defined by
ω/2 = { S∗ | ω − S∗ }
where on the right hand side the notation x − Y is used to mean { x − y : y ∈ Y }. It can be identified as the product of ω and the form { 0 | 1 } of 1/2. The birthday of ω/2 is the limit ordinal ω2.
Powers of ω and the Conway normal form
To classify the "orders" of infinite and infinitesimal surreal numbers, also known as archimedean classes, Conway associated to each surreal number x the surreal number
ωx = { 0, r ωxL | s ωxR },
where r and s range over the positive real numbers. If x < y then ωy is "infinitely greater" than ωx, in that it is greater than r ωx for all real numbers r. Powers of ω also satisfy the conditions
ωx ωy = ωx+y,
ω−x = 1/ωx,
so they behave the way one would expect powers to behave.
Each power of ω also has the redeeming feature of being the simplest
surreal number in its archimedean class; conversely, every archimedean
class within the surreal numbers contains a unique simplest member.
Thus, for every positive surreal number x there will always exist some positive real number r and some surreal number y so that x − rωy is "infinitely smaller" than x. The exponent y is the "base ω logarithm" of x, defined on the positive surreals; it can be demonstrated that logω maps the positive surreals onto the surreals and that
logω(xy) = logω(x) + logω(y).
This gets extended by transfinite induction so that every surreal number has a "normal form" analogous to the Cantor normal form for ordinal numbers. This is the Conway normal form: Every surreal number x may be uniquely written as
x = r0ωy0 + r1ωy1 + ...,
where every rα is a nonzero real number and the yαs
form a strictly decreasing sequence of surreal numbers. This "sum",
however, may have infinitely many terms, and in general has the length
of an arbitrary ordinal number. (Zero corresponds of course to the case
of an empty sequence, and is the only surreal number with no leading
exponent.)
Looked at in this manner, the surreal numbers resemble a power series field,
except that the decreasing sequences of exponents must be bounded in
length by an ordinal and are not allowed to be as long as the class of
ordinals. This is the basis for the formulation of the surreal numbers
as a Hahn series.
Gaps and continuity
In
contrast to the real numbers, a (proper) subset of the surreal numbers
does not have a least upper (or lower) bound unless it has a maximal
(minimal) element. Conway defines a gap as { L | R } such that every element of L is less than every element of R, and ; this is not a number because at least one of the sides is a proper class. Though similar, gaps are not quite the same as Dedekind cuts, but we can still talk about a completion of the surreal numbers with the natural ordering which is a (proper class-sized) linear continuum.
For instance there is no least positive infinite surreal, but the gap
is greater than all real numbers and less than all positive infinite
surreals, and is thus the least upper bound of the reals in . Similarly the gap is larger than all surreal numbers. (This is an esoteric pun: In the general construction of ordinals, α "is" the set of ordinals smaller than α, and we can use this equivalence to write α = { α | } in the surreals; denotes the class of ordinal numbers, and because is cofinal in we have by extension.)
With a bit of set-theoretic care, can be equipped with a topology where the open sets are unions of open intervals (indexed by proper sets) and continuous functions can be defined. An equivalent of Cauchy sequences
can be defined as well, although they have to be indexed by the class
of ordinals; these will always converge, but the limit may be either a
number or a gap that can be expressed as
with aα decreasing and having no lower bound in .
(All such gaps can be understood as Cauchy sequences themselves, but
there are other types of gap that are not limits, such as ∞ and ).
Exponential function
Based on unpublished work by Kruskal, a construction (by transfinite induction) that extends the real exponential function exp(x) (with base e) to the surreals was carried through by Gonshor.
Other exponentials
The powers of ω
function is also an exponential function, but does not have the
properties desired for an extension of the function on the reals. It
will, however, be needed in the development of the base-e exponential, and it is this function that is meant whenever the notation ωx is used in the following.
When y is a dyadic fraction, the power functionx ∈ , x ↦ xy
may be composed from multiplication, multiplicative inverse and square
root, all of which can be defined inductively. Its values are completely
determined by the basic relation xy+z = xy · xz, and where defined it necessarily agrees with any other exponentiation that can exist.
Basic induction
The induction steps for the surreal exponential are based on the series expansion for the real exponential,
more specifically those partial sums that can be shown by basic algebra to be positive but less than all later ones. For x positive these are denoted [x]n and include all partial sums; for x negative but finite, [x]2n+1 denotes the odd steps in the series starting from the first one with a positive real part (which always exists). For x negative infinite the odd-numbered partial sums are strictly decreasing and the [x]2n+1 notation denotes the empty set, but it turns out that the corresponding elements are not needed in the induction.
The relations that hold for real x < y are then
exp x · [y – x]n < exp y
and
exp y · [x – y]2n + 1 < exp x,
and this can be extended to the surreals with the definition
This is well-defined for all surreal arguments (the value exists and does not depend on the choice of zL and zR).
Results
Using this definition, the following holds:
exp is a strictly increasing positive function, x < y ⇒ 0 < exp x < exp y
exp satisfies exp(x+y) = exp x · exp y
exp is a surjection (onto ) and has a well-defined inverse, log = exp–1
exp coincides with the usual exponential function on the reals (and thus exp 0 = 1, exp 1 = e)
For x infinitesimal, the value of the formal power series (Taylor expansion) of exp is well defined and coincides with the inductive definition
When x is given in Conway normal form, the set of
exponents in the result is well-ordered and the coefficients are finite
sums, directly giving the normal form of the result (which has a leading
1)
Similarly, for x infinitesimally close to 1, log x is given by power series expansion of x – 1
For positive infinite x, exp x is infinite as well
If x has the form ωα (α > 0), exp x has the form ωωβ where β is a strictly increasing function of α. In fact there is an inductively defined bijection g: → : α ↦ β whose inverse can also be defined inductively
If x is "pure infinite" with normal form x = Σα<βrαωaα where all aα > 0, then exp x = ωΣα<βrαωg(aα)
Similarly, for x = ωΣα<βrαωbα, the inverse is given by log x = Σα<βrαωg–1(bα)
Any surreal number can be written as the sum of a pure infinite, a
real and an infinitesimal part, and the exponential is the product of
the partial results given above
The normal form can be written out by multiplying the infinite
part (a single power of ω) and the real exponential into the power
series resulting from the infinitesimal
Conversely, dividing out the leading term of the normal form will bring any surreal number into the form (ωΣγ<δtγωbγ)·r·(1 + Σα<βsαωaα), for aα < 0,
where each factor has a form for which a way of calculating the
logarithm has been given above; the sum is then the general logarithm
While there is no general inductive definition of log (unlike
for exp), the partial results are given in terms of such definitions. In
this way, the logarithm can be calculated explicitly, without reference
to the fact that it's the inverse of the exponential.
The exponential function is much greater than any finite power
For any positive infinite x and any finite n, exp(x)/xn is infinite
For any integer n and surreal x > n2, exp(x) > xn. This stronger constraint is one of the Ressayre axioms for the real exponential field
exp satisfies all the Ressayre axioms for the real exponential field
The surreals with exponential is an elementary extension of the real exponential field
For εβ an ordinal epsilon number, the set of surreal numbers with birthday less than εβ constitute a field that is closed under exponentials, and is likewise an elementary extension of the real exponential field
Examples
The surreal exponential is essentially given by its behaviour on positive powers of ω, i.e., the function g(a), combined with well-known behaviour on finite numbers. Only examples of the former will be given. In addition, g(a) = a
holds for a large part of its range, for instance for any finite number
with positive real part and any infinite number that is less than some
iterated power of ω (ωω··ω for some number of levels).
exp ω = ωω
exp ω1/ω = ω and log ω = ω1/ω
exp (ω · log ω) = exp (ω · ω1/ω) = ωω(1 + 1/ω)
This shows that the "power of ω" function is not compatible with exp, since compatibility would demand a value of ωω here
exp ε0 = ωωε0 + 1
log ε0 = ε0 / ω
Exponentiation
A general exponentiation can be defined as xy = exp(y · log x), giving an interpretation to expressions like 2ω = exp(ω · log 2) = ωlog 2 · ω. Again it is essential to distinguish this definition from the "powers of ω" function, especially if ω may occur as the base.
The definition of surreal numbers contained one restriction: each
element of L must be strictly less than each element of R. If this
restriction is dropped we can generate a more general class known as games. All games are constructed according to this rule:
Construction rule
If L and R are two sets of games then { L | R } is a game.
Addition, negation, and comparison are all defined the same way for both surreal numbers and games.
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 xz = yz. However, if x, y, and z are games, and x = y, then it is not always true that xz = yz. Note that "=" here means equality, not identity.
Application to 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 (the game at each step will completely depend on the choices the players make, rather than a random factor)
No hidden information (such as cards or tiles that a player hides)
Players alternate taking turns (the game may or may not allow multiple moves in a turn)
Every game must end in a finite number of moves
As soon as there are no legal moves left for a player, the game ends, and that player loses
For most games, the initial board position gives no great advantage
to either player. As the game progresses and one player starts to win,
board positions will occur in which that player has a clear advantage.
For analyzing games, it is useful to associate a Game with every board
position. The value of a given position will be the Game {L|R}, where L
is the set of values of all the positions that can be reached in a
single move by Left. Similarly, R is the set of values of all the
positions that can be reached in a single move by Right.
The zero Game (called 0) is the Game where L and R are both
empty, so the player to move next (L or R) immediately loses. The sum of
two Games G = { L1 | R1 } and H = { L2 | R2 } is defined as the Game G +
H = { L1 + H, G + L2 | R1 + H, G + R2 } where the player to move
chooses which of the Games to play in at each stage, and the loser is
still the player who ends up with no legal move. One can imagine two
chess boards between two players, with players making moves alternately,
but with complete freedom as to which board to play on. If G is the
Game {L | R}, −G is the Game {−R | −L}, i.e. with the role of the two
players reversed. It is easy to show G – G = 0 for all Games G (where G –
H is defined as G + (–H)).
This simple way to associate Games with games yields a very
interesting result. Suppose two perfect players play a game starting
with a given position whose associated Game is x. We can classify all Games into four classes as follows:
If x > 0 then Left will win, regardless of who plays first.
If x < 0 then Right will win, regardless of who plays first.
If x = 0 then the player who goes second will win.
If x || 0 then the player who goes first will win.
More generally, we can define G > H as G – H > 0, and similarly for <, = and ||.
The notation G || H means that G and H are incomparable. G || H
is equivalent to G − H || 0, i.e. that G > H, G < H and G = H are
all false. Incomparable games are sometimes said to be confused
with each other, because one or the other may be preferred by a player
depending on what is added to it. A game confused with zero is said to
be fuzzy, as opposed to positive, negative, or zero. An example of a fuzzy game is star (*).
Sometimes when a game nears the end, it will decompose into
several smaller games that do not interact, except in that each player's
turn allows moving in only one of them. For example, in Go, the board
will slowly fill up with pieces until there are just a few small islands
of empty space where a player can move. Each island is like a separate
game of Go, played on a very small board. It would be useful if each
subgame could be analyzed separately, and then the results combined to
give an analysis of the entire game. This doesn't appear to be easy to
do. For example, there might be two subgames where whoever moves first
wins, but when they are combined into one big game, it is no longer the
first player who wins. Fortunately, there is a way to do this analysis.
The following theorem can be applied:
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.
A game composed of smaller games is called the disjunctive sum
of those smaller games, and the theorem states that the method of
addition we defined is equivalent to taking the disjunctive sum of the
addends.
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 into an analysis of their disjunctive sum.
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.
Alternative realizations
Alternative approaches to the surreal numbers complement Conway's exposition in terms of games.
Sign expansion
Definitions
In what is now called the sign-expansion or sign-sequence of a surreal number, a surreal number is a function whose domain is an ordinal and whose codomain is { −1, +1 }. This is equivalent to Conway's L-R sequences.
Define the binary predicate "simpler than" on numbers by x is simpler than y if x is a proper subset of y, i.e. if dom(x) < dom(y) and x(α) = y(α) for all α < dom(x).
For surreal numbers define the binary relation < to be
lexicographic order (with the convention that "undefined values" are
greater than −1 and less than 1). So x < y if one of the following holds:
x is simpler than y and y(dom(x)) = +1;
y is simpler than x and x(dom(y)) = −1;
there exists a number z such that z is simpler than x, z is simpler than y, x(dom(z)) = − 1 and y(dom(z)) = +1.
Equivalently, let δ(x,y) = min({ dom(x), dom(y)} ∪ { α :
α < dom(x) ∧ α < dom(y) ∧ x(α) ≠ y(α) }),
so that x = y if and only if δ(x,y) = dom(x) = dom(y). Then, for numbers x and y, x < y if and only if one of the following holds:
For numbers x and y, x ≤ y if and only if x < y ∨ x = y, and x > y if and only if y < x. Also x ≥ y if and only if y ≤ x.
The relation < is transitive, and for all numbers x and y, exactly one of x < y, x = y, x > y, holds (law of trichotomy). This means that < is a linear order (except that < is a proper class).
For sets of numbers, L and R such that ∀x ∈ L ∀y ∈ R (x < y), there exists a unique number z such that
∀x ∈ L (x < z) ∧ ∀y ∈ R (z < y),
For any number w such that ∀x ∈ L (x < w) ∧ ∀y ∈ R (w < y), w = z or z is simpler than w.
Furthermore, z is constructible from L and R by transfinite induction. z is the simplest number between L and R. Let the unique number z be denoted by σ(L,R).
For a number x, define its left set L(x) and right set R(x) by
L(x) = { x|α : α < dom(x) ∧ x(α) = +1 };
R(x) = { x|α : α < dom(x) ∧ x(α) = −1 },
then σ(L(x),R(x)) = x.
One advantage of this alternative realization is that equality is
identity, not an inductively defined relation. Unlike Conway's
realization of the surreal numbers, however, the sign-expansion requires
a prior construction of the ordinals, while in Conway's realization,
the ordinals are constructed as particular cases of surreals.
However, similar definitions can be made that eliminate the need
for prior construction of the ordinals. For instance, we could let the
surreals be the (recursively-defined) class of functions whose domain is
a subset of the surreals satisfying the transitivity rule ∀g ∈ dom f (∀h ∈ dom g (h ∈ dom f )) and whose range is { −, + }. "Simpler than" is very simply defined now—x is simpler than y if x ∈ dom y. The total ordering is defined by considering x and y as sets of ordered pairs (as a function is normally defined): Either x = y, or else the surreal number z = x ∩ y is in the domain of x or the domain of y (or both, but in this case the signs must disagree). We then have x < y if x(z) = − or y(z) = + (or both). Converting these functions into sign sequences is a straightforward task; arrange the elements of dom f in order of simplicity (i.e., inclusion), and then write down the signs that f assigns to each of these elements in order. The ordinals then occur naturally as those surreal numbers whose range is { + }.
Addition and multiplication
The sum x + y of two numbers, x and y, is defined by induction on dom(x) and dom(y) by x + y = σ(L,R), where
L = { u + y : u ∈ L(x) } ∪{ x + v : v ∈ L(y) },
R = { u + y : u ∈ R(x) } ∪{ x + v : v ∈ R(y) }.
The additive identity is given by the number 0 = { }, i.e. the number 0 is the unique function whose domain is the ordinal 0, and the additive inverse of the number x is the number −x, given by dom(−x) = dom(x), and, for α < dom(x), (−x)(α) = −1 if x(α) = +1, and (−x)(α) = +1 if x(α) = −1.
It follows that a number x is positive if and only if 0 < dom(x) and x(0) = +1, and x is negative if and only if 0 < dom(x) and x(0) = −1.
The product xy of two numbers, x and y, is defined by induction on dom(x) and dom(y) by xy = σ(L,R), where
L = { uy + xv − uv : u ∈ L(x), v ∈ L(y) } ∪ { uy + xv − uv : u ∈ R(x), v ∈ R(y) },
R = { uy + xv − uv : u ∈ L(x), v ∈ R(y) } ∪ { uy + xv − uv : u ∈ R(x), v ∈ L(y) }.
The multiplicative identity is given by the number 1 = { (0,+1) }, i.e. the number 1 has domain equal to the ordinal 1, and 1(0) = +1.
Correspondence with Conway's realization
The map from Conway's realization to sign expansions is given by f({ L | R }) = σ(M,S), where M = { f(x) : x ∈ L } and S = { f(x) : x ∈ R }.
The inverse map from the alternative realization to Conway's realization is given by g(x) = { L | R }, where L = { g(y) : y ∈ L(x) } and R = { g(y) : y ∈ R(x) }.
Axiomatic approach
In another approach to the surreals, given by Alling,
explicit construction is bypassed altogether. Instead, a set of axioms
is given that any particular approach to the surreals must satisfy.
Much like the axiomatic approach to the reals, these axioms guarantee uniqueness up to isomorphism.
A triple is a surreal number system if and only if the following hold:
b is a function from onto the class of all ordinals (b is called the "birthday function" on ).
Let A and B be subsets of such that for all x ∈ A and y ∈ B, x < y (using Alling's terminology, 〈 A,B 〉 is a "Conway cut" of ). Then there exists a unique z ∈ such that b(z) is minimal and for all x ∈ A and all y ∈ B, x < z < y. (This axiom is often referred to as "Conway's Simplicity Theorem".)
Furthermore, if an ordinal α is greater than b(x) for all x ∈ A, B, then b(z) ≤ α. (Alling calls a system that satisfies this axiom a "full surreal number system".)
Both Conway's original construction and the sign-expansion construction of surreals satisfy these axioms.
Given these axioms, Alling derives Conway's original definition of ≤ and develops surreal arithmetic.
Simplicity hierarchy
A
construction of the surreal numbers as a maximal binary pseudo-tree
with simplicity (ancestor) and ordering relations is due to Philip
Ehrlich,
The difference from the usual definition of a tree is that the set of
ancestors of a vertex is well-ordered, but may not have a maximal
element (immediate predecessor); in other words the order type of that
set is a general ordinal number, not just a natural number. This
construction fulfills Alling's axioms as well and can easily be mapped
to the sign-sequence representation.
Hahn series
Alling also proves that the field of surreal numbers is isomorphic (as an ordered field) to the field of Hahn series
with real coefficients on the value group of surreal numbers themselves
(the series representation corresponding to the normal form of a
surreal number, as defined above). This provides a connection between
surreal numbers and more conventional mathematical approaches to ordered
field theory.
This isomorphism makes the surreal numbers into a valued field
where the valuation is the additive inverse of the exponent of the
leading term in the Conway normal form, e.g., ν(ω) = −1. The valuation
ring then consists of the finite surreal numbers (numbers with a real
and/or an infinitesimal part). The reason for the sign inversion is that
the exponents in the Conway normal form constitute a reverse
well-ordered set, whereas Hahn series are formulated in terms of
(non-reversed) well-ordered subsets of the value group.
![{\displaystyle \exp z=\{0,\exp z_{L}\cdot [z-z_{L}]_{n},\exp z_{R}\cdot [z-z_{R}]_{2n+1}\mid \exp z_{R}/[z_{R}-z]_{n},\exp z_{L}/[z_{L}-z]_{2}n+1\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/452f965e1233f906dbfccdaa889f85e8bd6d1fa1)
