Dependencies

The rank \(\operatorname {bd}(x)\in \mathbb N\) is defined recursively by

Thus our convention is \(\operatorname {bd}(0)=1\).

For \(x_1\prec x_2\), the two forms needed to compare product options are

For arbitrary games \(x_1,x_2,y_1,y_2\), define the weak and strict four-product relations by

Thus \(C_L(x_1,x_2;y,y^L)\) is \(\operatorname {Cross}_{\prec }(x_1,x_2;y^L,y)\), while \(C_R(x_1,x_2;y,y^R)\) is \(\operatorname {Cross}_{\prec }(x_1,x_2;y,y^R)\).

Three kinds of induction goal are used:

Their measures are the multisets

The goal order is the pullback of the Dershowitz–Manna multiset extension \({\lt}_{\rm DM}\) of \({\lt}\) on \(\mathbb N\) along these measures. For example, if \(a'{\lt}a\) and \(a_1,a_2{\lt}a\), then

The first two comparisons replace one birthday by a smaller birthday, the third replaces one birthday by two smaller birthdays, and the fourth deletes one birthday. Lemma 2.3, transitivity, and permutation invariance of multisets reduce the recursive dependencies in the \(A\)-, \(B\)-, and \(C\)-cases to these examples. Since \({\lt}\) on \(\mathbb N\) is well founded, so is the resulting goal order.

Let \(\mathcal{G}\) denote the collection of all finite (or short) combinatorial games. An element \(x\in \mathcal{G}\) is a finite rooted tree written \(x=\{ X^L\mid X^R\} \), where the left- and right-option collections \(X^L\) and \(X^R\) are finite lists of games. The basic games are

For games \(x=\{ X^L\mid X^R\} \) and \(y=\{ Y^L\mid Y^R\} \), define

with one option for every member of the indicated finite lists.

Two games \(x,y\in \mathcal{G}\) are equivalent, written \(x\sim y\), when each is weakly below the other:

This is the relation used later to identify games with the same game value. Equivalent games need not be literally equal as rooted trees or have identical option lists.

The development uses the following relations on one, two, three, and four games. For \(q=(q_1,q_2,q_3,q_4)\) and \(q'=(q'_1,q'_2,q'_3,q'_4)\), set

Each relation is well founded because it is the inverse image of the well-founded order \({\lt}\) on \(\mathbb N\) under the corresponding sum-of-birthdays measure. They will be used for well-founded induction on one, two, three, and four games, respectively; replacing any coordinate by an option strictly decreases the relevant measure.

Put

For \(x=\{ X^L\mid X^R\} \) and \(y=\{ Y^L\mid Y^R\} \), multiplication is the recursive cut

with all choices of the displayed options. By Lemma 2.3, each selected option has smaller birthday than its parent. Hence the two-game induction relation of Definition 2.6 decreases in every recursive call.

Negation interchanges the two option lists and recursively negates every option:

In particular, \(-0=0\) as a literal equality of game trees.

The relation \(x\preceq y\) is defined recursively by

Strict comparison is

By Theorem 2.7, game equivalence is an equivalence relation. Define \(\mathcal{G}/{\sim }\) to be the quotient of \(\mathcal{G}\) by game equivalence, and write \([a]\) for the equivalence class of a game \(a\). Thus \([a]=[b]\) if and only if \(a\sim b\).

A game \(x=\{ X^L\mid X^R\} \) is surreal when every option is surreal and no right option is weakly below a left option:

The games \(0\) and \(1\) are surreal, and every option of a surreal game is surreal.

The type \(\mathbf{No}_{\mathrm{short}}\) is the quotient of surreal representatives by \(a\sim b\). Addition, zero, one, and negation descend to this quotient.

Define multiplication on \(\mathbf{No}_{\mathrm{short}}\) by taking the game product of any two representatives and then passing to the quotient.

Let \(a,b\in \mathcal{S}\), and write \(\{ a,b\} \) for the formal two-coordinate object with entries \(a\) and \(b\). For \(a',b'\in \mathcal{S}\), define

This relation is well founded. Replacing either coordinate by any left or right option produces a smaller pair, by Lemma 2.3.

Let \(\mathcal{S}\) denote the collection of all surreal representatives:

For \(s,s'\in \mathcal{S}\), representative equivalence is induced by game equivalence:

The surreal games \(0\) and \(1\) give canonical elements of \(\mathcal{S}\). If \(s\in \mathcal{S}\), then each left or right option of \(s_{\mathrm{game}}\), equipped with the inherited surrealness proof from Definition 2.9, is again an element of \(\mathcal{S}\). Equivalent representatives are related by \(\sim \), but are not yet identified as equal elements of a quotient.

If \(u\in X^L\) or \(u\in X^R\), then \(\operatorname {bd}(u){\lt}\operatorname {bd}(x)\).

For all games \(u,v\),

The following statements hold:

The following assertions hold simultaneously for all games satisfying the displayed hypotheses:

1. \(A(x,y)\): if \(x,y\) are surreal, then \(xy\) is surreal;

2. \(B(x_1,x_2,y)\): if \(x_1\sim x_2\) and all three games are surreal, then \(x_1y\sim x_2y\);

3. \(C(x_1,x_2,y)\): if \(x_1\prec x_2\) and all three games are surreal, then \(C_L(x_1,x_2;y,y^L)\) holds for every \(y^L\), and \(C_R(x_1,x_2;y,y^R)\) holds for every \(y^R\).

If \(x\) is surreal, then

The short surreal numbers \(\mathbf{No}_{\mathrm{short}}\) form a commutative ring.

If \(x\) and \(y\) are surreal games, then \(xy\) is surreal.

If \(x_1,x_2,y\) are surreal and \(x_1\sim x_2\), then \(x_1y\sim x_2y\).

If \(x_1,x_2,y\) are surreal and \(x_1\prec x_2\), then all the conditions \(C_L(x_1,x_2;y,y^L)\) and \(C_R(x_1,x_2;y,y^R)\) hold.

Let \(\mathrel {\bowtie }\) denote either \(\preceq \) or \(\prec \). If \(\operatorname {Cross}_{\bowtie }(a,c;d,e)\) holds, then

For the strict relation, the transpose, composition, and two endpoint-replacement rules are

Every game satisfies

For all games \(a,b,c\),

The zero and associativity identities hold as literal equalities of game trees; commutativity is asserted up to game equivalence.

Addition preserves and reflects weak order in either variable. In particular,

and

If either input comparison is strict and the other weak, the resulting comparison is strict. Addition also respects \(\sim \), i.e.

For all games \(a,b,c\),

If \(a,b,c\) are surreal games, then

If \(x_1\sim x_2\) and \(y_1\sim y_2\), and all four games are surreal, then

For all games \(a,b\),

In fact, multiplication by zero on either side and multiplication on the right by one satisfy literal game-tree equalities.

If \(x,y\) are surreal games and \(0\prec x\), \(0\prec y\), then

For all games \(a,b\),

For all games \(x,a,b,c\), reflexivity and transitivity are the assertions

Consequently \(\sim \) is an equivalence relation, \(\prec \) is transitive, and strict and weak inequalities compose in either order.

For finite games \(a,b\), define

and

These formulas are independent of the chosen representatives. With these operations and this order, \(\mathcal{G}/{\sim }\) is a partially ordered additive commutative group, and addition is order preserving in each variable.

The short surreal numbers constructed above form a linear ordered commutative ring.

Let \(a=\{ A^L\mid A^R\} \) and \(b=\{ B^L\mid B^R\} \) be games. Suppose

Then \(a\sim b\).

The quotient \(\mathbf{No}_{\mathrm{short}}\) is a linearly ordered additive commutative group, and addition is compatible with its order.

The ring \(\mathbf{No}_{\mathrm{short}}\) is nontrivial; addition reflects order, multiplication by a nonnegative element preserves weak inequalities, and multiplication by a positive element preserves strict inequalities, on either side.

For \(a,b,c\in \mathbf{No}_{\mathrm{short}}\),

Multiplication on \(\mathbf{No}_{\mathrm{short}}\) is associative and commutative, has identity \(1\), and has \(0\) as an absorbing element.

Multiplication by a nonnegative short surreal number preserves weak inequalities on either side, and multiplication by a positive short surreal number preserves strict inequalities on either side.

For \(a,b\in \mathbf{No}_{\mathrm{short}}\),

and \(0\leq 1\).

If \(a,b\) are surreal representatives, then the games \(a+b\) and \(-a\) are surreal. Hence addition and negation define operations on surreal representatives.

If \(a,b\) are surreal representatives, their game product is surreal. Moreover, replacing either representative by an equivalent one does not change the equivalence class of the product. Thus multiplication is a well-defined operation on representatives modulo \(\sim \).

If \(x\) and \(y\) are surreal, then

and one of the three alternatives \(x\prec y\), \(x\sim y\), or \(y\prec x\) holds.