1. Preliminaries.

Definition (1.1). A \underline{game} is a pair (S, ρ), where S is a set and ρ is a binary relation on S that is well-founded. The elements of S are called the \underline{configurations} of the game, and the relation ρ is called the \underline{evolution} relation.

Here, “well-founded” means that for every ∅ ≠ A ⊆ S there exists a ∈ A such that xρa holds for no x ∈ A. Using the axiom of dependent choices, this is equivalent to saying that there is no (infinite) sequence (a_{n}) of elements of S such that a_{n+1}ρa_{n} for every natural number n. The relation aρb reads “configuration a can be reached from configuration b”, and the well-foundedness means that any play must stop.

Definition (1.2). A \underline{pointed game} is a triple (S, ρ, x_{0}) where (S, ρ) is a game and x_{0} is an element of S called the \underline{initial configuration}. A \underline{play} in a pointed game (S, ρ, x_{0}) is a (necessarily finite) sequence (a_{n}) that starts with the initial configuration a_{0} = x_{0} and obeys the rules of the game a_{n+1}ρa_{n} for every n. The \underline{length} of the play is the number of terms in the sequence minus one (that is, the index of the last term, or the number of moves). We say that a play is \underline{won by player A} iff its length is odd, \underline{won by player B} iff its length is even.

We can consider a pointed game as a game by just forgetting about the initial configuration: we then speak of the \underline{underlying} game of a pointed game. We can also extend a game S to a pointed game by adding a new configuration ϖ and extending the evolution relation by decreeing that aρϖ for every a ∈ S.

Definition (1.3). An \underline{isomorphism} (S, ρ) → (S′, ρ′) of games is a bijective map f: S → S′ such that aρb iff f(a)ρf(b). An isomorphism of pointed games is an isomorphism of the underlying games that preserves the initial configuration.

Actually, isomorphism is a too strong notion, and it is not very interesting. We shall later on define for pointed games a more interesting notion, that of equivalence.

Definition (1.4). If (S, ρ) is a game, and x ∈ S is a configuration of S, then we define the \underline{extension} (or the \underline{extent}) of x as the set ext(x) = \{y ∈ S : yρx\} of configurations that can be reached from x. A game (S, ρ) is said to be \underline{extensional} iff two configurations with the same extension are equal.

Theorem (1.5, well-founded induction). Let (S, ρ) be a game, E = {ext(x) : x ∈ S} the set of the extensions of the elements of S, and A a set or a class. Let G: S ×A^{E} → A be a function. Then there exists a unique function F: S → A such that F (x) = G(x, F | ext(x)) for each x ∈ S. In other words, it is permissible to define a function on S in terms not only of x but also of the (“previously calculated”) values of F on the extension of x.

We now use this theorem to define a few important functions by well-founded induction:

Definition (1.6). Given a game (S, ρ), we define:

(i) The \underline{rank} of x ∈ S as the smallest ordinal number greater than the rank of every y ∈ S such that yρx.

(ii) The \underline{Grundy function} of x ∈ S as the smallest ordinal number not equal to the Grundy

function of any y ∈ S such that yρx. (iii) The \underline{equivalent set} of x ∈ S as the set whose elements are the equivalent sets of the

y ∈ S such that yρx.

We correspondingly define the rank (resp. the Grundy function, resp. the equivalent set) of a pointed game as the rank (resp. the Grundy function, resp. the equivalent set) of the initial configuration.

Definition (1.7). Two pointed games are said to be \underline{equivalent} iff their equivalent sets are equal. A property on games is said to be \underline{invariant under equivalence} iff any game equivalent to a game which has the property also has the property (similarily for a function on games).

The rank of a pointed game, and its Grundy function (and of course its equivalent set) are invariant under equivalence, since they are defined only in terms of the extension of x.

Definition (1.8). Let X be a set. Then we define a pointed game (S, ρ, x_{0}), called the \underline{game of X} in the following way: S is the transitive closure of \{X\} (that is, S is the set consisting of X, of the elements of X, of the elements of the elements of X, and so on), ρ is the relation belonging relation ∈ restricted to S, and x_{0} = X.

Proposition (1.9). Let X be a set. Then the game of X is, up to isomorphism, the unique extensional pointed game that has X for equivalent set. In particular, equivalent extensional games are isomorphic.

We shall therefore identify a pointed game with its equivalent set, and a set with its game. We then have the definition of the rank (resp. the Grundy function) of a set as the smallest ordinal that is greater than (resp. not equal to) the rank (resp. Grundy function) of any element of the set.

Proposition (1.10). Let α be an ordinal. Then the rank and the Grundy function of α are both equal to α.

∵ Obvious by induction on α, since the elements of α are precisely the ordinals less than α. ∴ 2. Plays and winning strategies.

Definition (2.1). Let (S, ρ) be a game. Then a \underline{terminal configuration} is a configuration x with empty extent, in other words such that there exists no y ∈ S with yρx. A configuration which is not terminal is called \underline{nonterminal}.

Definition (2.2). Let (S, ρ) be a game. Then a \underline{strategy} is a function f: S → S ∪ \{♣\} (where ♣, read as “forfeit”, is not an element in S) such that for every x ∈ S either f(x) = ♣ or f(x)ρx. If (S, ρ, x_{0}) is a pointed game and f, g are strategies of S, then we define a play ⟨f | g⟩ in the following way:

• a_{0} = x_{0}.

• If a_{n} is defined and n is even, then we let a_{n+1} = f(a_{n}) except if f(a_{n}) = ♣ in which case a_{n+1} is not defined.

• If a_{n} is defined and n is odd, then we let a_{n+1} = g(a_{n}) except if g(a_{n}) = ♣ in which case a_{n+1} is not defined. We say that f is a \underline{winning strategy for player A} iff the play ⟨f | g⟩ is won by player A

for every strategy g. We say that g is a \underline{winning strategy for player B} iff the play ⟨f | g⟩ is won by player B for every strategy f. (Recall that the play is said to be won by player A or B according as its length is respectively odd or even.)

Definition (2.3). If (S, ρ) is a game, we define the \underline{kernel} of S as the set of configurations x ∈ S whose Grundy function is 0. Correspondingly, a pointed game (S, ρ, x_{0}) is said to be \underline{in the kernel} iff its initial configuration x_{0} is in the kernel of (S, ρ). And a set is said to be \underline{in the kernel} iff its (pointed) game is.

Lemma (2.4). Let (S, ρ) be a game. Then we have x ∈ N iff ext x ∩ N = ∅. In other words, a configuration is in the kernel iff it leads only to configurations that are not in the kernel. Correspondingly, a set is in the kernel iff none of its elements are (and this defines “the kernel”).

∵ If x ∈ N then the Grundy function of x is 0, and therefore any y in the extent of x has Grundy function greater than 0, which means that it is not in the kernel, so that ext x ∩ N = ∅. Conversely, if ext x ∩ N = ∅, then any y in the extent of x has Grundy function greater than 0, so that the smallest ordinal which is not the Grundy function of a y ∈ ext x is 0, and therefore x is in the kernel. ∴

Theorem (2.5). Let (S, ρ, x_{0}) be a pointed game, and N its kernel. Let f be a strategy for S such that f(x) ∈ N whenever x ∉ N. Then f is a winning strategy for A (resp. for B) according as x_{0} ∉ N (resp. x_{0} ∈ N). Moreover, there exists such an f. Therefore, in any pointed game, at least one player has a winning strategy. Furthermore, both cannot have a winning strategy.

∵ Assume x_{0} ∉ N, and let g be any strategy. Put (a_{n}) = ⟨f | g⟩. We prove by induction that a_{n} ∉ N iff n is even. Indeed, we have a_{0} = x_{0} ∉ N. If n is even and a_{n} is defined, then a_{n} ∉ N, and therefore a_{n+1} = f(a_{n}) is defined (is not forfeit), and a_{n+1} ∈ N. On the other hand, if n is odd and a_{n} is defined, then a_{n} ∈ N, and therefore either g(a_{n}) = ♣ and we are done, or else a_{n+1} = g(a_{n})ρa_{n}, in which case a_{n+1} ∉ N by lemma (2.4). This concludes the induction. Now consider the last n such that a_{n} is defined (the length of the play) : then n cannot be even for else a_{n} ∉ N and f(a_{n}) ∈ N (is not forfeit). So n is odd and the play is won by player A. This shows that f is a winning strategy for player A. The situation where x_{0} ∈ N is exactly similar.

To show that such an f exists, we let f(x) = ♣ if x ∈ N, and we have finished when we have proven that for any x ∉ N there exists y such that yρx and y ∈ N: but this is a consequence of the lemma (2.4). Finally, if both players A and B had a winning strategy, call them f and g, then ⟨f | g⟩ would be won both by player A and by player B, a contradiction. ∴

3. Operations on games.

Definition (3.1). Let (S, ρ) and (S′, ρ′) be two games. Then we define the product (resp. the normal product, resp. the sum) of (S, ρ) and (S′, ρ′) as the game having the configuration space S × S′ and the relation ρ′′ where (y, y′)ρ′′(x, x′) iff yρx and (resp. inclusive or, resp. exclusive or) y′ρ′x′. We define the product (resp. the normal product, resp. the sum) of pointed games by taking the initial configuration to be (x_{0}, x′_{0}), where x_{0} and x′_{0} are the initial configurations of the pointed games one started with.

In other words, to play the product game, each player plays exactly one move on each of the two games. To play the normal product game, each player plays one move on the game of his choice, or, if he wishes, one move on each. To play the sum game, each player plays one move on the game of his choice (but not both).

Note that these operations are compatible with isomorphism of games, isomorphism of pointed games, and equivalence of pointed games. As concerns the latter, in fact:

Definition (3.1.1). Let X and X′ be two sets. Then we define their game product (resp. their game normal product, resp. their game sum) as the set, written X ∗X′ (resp. X † X′, resp. X ⊕ X′) whose elements are precisely the x ∗ x′ with x ∈ X and x′ ∈ X′ (resp. the x†X′, the X †x′ and the x†x′ with x ∈ X and x′ ∈ X′, resp. the x†X′ with x ∈ X and the X † x′ with x′ ∈ X′). In other words, it is the equivalent set of the product (resp. normal product, resp. sum) of the games of X and X′.

Also note that the operations we defined on (pointed) games are commutative and associative up to isomorphism, hence in particular up to equivalence, and therefore the operations we defined on sets are commutative and associative (up to nothing!).

Definition (3.2). If α_{1}, …, α_{k} are ordinals, we define the \underline{game of Nim} starting from the configuration (α_{1}, …, α_{k}) as the game whose space of configurations is the set of (β_{1}, …, β_{k}) where each β_{i} is less or equal to α_{i}, and where the evolution relation is given as follows: (γ_{1}, …, γ_{k})ρ(β_{1}, …, β_{k}) iff γ_{i} = β_{i} for all i except exactly one for which γ_{i} < β_{i}. In other words, the game of Nim starting from the configuration (α_{1}, …, α_{k}) is the sum of the games of the ordinals α_{1}, …, α_{k}. Its equivalent set is therefore α_{1} ⊕ ⋯ ⊕ α_{k}.

Definition (3.3). We define α_{1}# ⋯ #α_{k} (where α_{1}, …, α_{k} are ordinals) as the Grundy function of the game of Nim α_{1} ⊕ ⋯ ⊕ α_{k}. In other words, α#α′ is inductively defined as the smallest ordinal not equal to β#α′ for β < α, nor to α#β′ for β′ < α′.

Proposition (3.4). The operation # on ordinals is commutative and associative (in the sense that (⋯ (α_{1}#α_{2})# ⋯)#α_{k} = α_{1}# ⋯ #α_{k} = α_{1}#(⋯ #(α_{k−1}#α_{k}) ⋯)). The ordinal 0 acts as a unit element. For any ordinal α we have α#α = 0. For any ordinals α, β, there exists a unique ordinal γ such that α#γ = β.

∵ Commutativity and associativity come from the facts that corresponding properties on the sum of games. That 0 is a unit element is trivial. We then prove by induction on α that α#α = 0. Indeed, assume this is true for β < α. Then for any β < α, the ordinal α#β must be different from β#β = 0, and so also β#α ≠ 0, which then shows that α#α = 0. This concludes the induction. Finally, if α, β are ordinals, we have α#(α#β) = β, and conversely, if α#γ = β then γ = α#(α#γ) = α#β, which proves the last statement. ∴

In other words, the operation # makes the class of all ordinals into an 𝔽_{2}-vector space!

Theorem (3.5). Let X and X′ be two sets, and α and α′ their Grundy functions. Then the Grundy function of the game sum X ⊕ X′ of X and X′ is α#α′.

∵ By well-founded induction, we can assume this is true with either X or X′ replaced by one its elements. We must now show two things. First, if x ∈ X (resp. if x′ ∈ X′) then the Grundy function of x ⊕ X′ (resp. of X ⊕ x′) is not equal to α#α′. Indeed, if we let β ≠ α (resp. β′ ≠ α′) be the Grundy function of x (resp. x′) then that of x ⊕ X′ (resp. of X ⊕ x′) is β#α′ (resp. α#β′) by the induction hypothesis; and by proposition (3.4) (the last statement), this cannot be equal to α#α′. Second, if γ < α#α′, we must show that there exists x ∈ X such that γ is the Grundy function of x ⊕ X′, or that there exists x′ ∈ X′ such that γ is the Grundy function of X ⊕ x′. But if γ < α#α′, then by the definition of α#α′ there exists β < α such that γ = β#α′ or β′ < α′ such that γ = α#β′. In the first case, we can find (by the definition of the Grundy function) an x ∈ X whose Grundy funciton is β and then the Grundy function of x⊕X′, by the induction hypothesis, is α#β′, hence the result. The second case is similar. This concludes the proof. ∴

Note in particular that the Grundy function of X ⊕ X′ depends only on the Grundy functions of X and X′. However, whether X ⊕ X′ is in the kernel (that is, whether its Grundy function is zero) does not depend only on whether X and X′ are.

Criterion (3.6). (Recall that a set S is called transitive when any element of an element of S is an element of S.) Suppose that S is transitive and so is every element of S; then S is an ordinal. Equivalently, if (S, ρ, x_{0}) is a pointed game in which the relation ρ is transitive, then its equivalent set is an ordinal.

Proposition (3.7). If α_{1}, …, α_{k} are ordinals, then their game normal product is an ordinal.

∵ This is a simple consequence of criterion (3.6). ∴

Recall (3.8). We define α_{1} † ⋯ † α_{k} (where α_{1}, …, α_{k} are ordinals) as the game normal product of α_{1}, …, α_{k}. In other words, α † α′ is inductively defined as the smallest ordinal not equal to β † α′, nor to α † β′, nor to β † β′ for β < α and β′ < α′. More generally, when X_{1}, …, X_{k} are sets, we will write X_{1} † ⋯ † X_{k} for their game normal product.

Proposition (3.9). The operation † on ordinals is commutative and associative (in the sense that (⋯ (α_{1} † α_{2}) † ⋯) † α_{k} = α_{1} † ⋯ † α_{k} = α_{1} † (⋯ † (α_{k−1} † α_{k}) ⋯)). The ordinal 0 acts as a unit element. If α, α′ and β, β′ are ordinals and we have β ≤ α and β′ ≤ α′ with one at least of these inequalities strict, then β † β′ < α † α′.

∵ Commutativity and associativity come from the facts that corresponding properties on the norma products of games. That 0 is a unit element is trivial. The last statement is an immediate consequence of the definition (α † α′ is precisely the set of such β † β′). ∴

In a way, the † operation is a much better kind of sum on ordinals than the ordinary sum.

We might hope for a result analogous to theorem (3.5); unfortunately, the Grundy function of X † X′ does not depend only on the Grundy functions of X and X′. However, we have the following result :

Proposition (3.10). Let X and X′ be sets. Then X † X′ is in the kernel iff X and X′ both are.

∵ By well-founded induction. If X and X′ are in the kernel, then for any element x of X and x′ of X′, the sets x and x′ are not in the kernel, and therefore (by induction) neither are any of the sets x † X′, X † x′, x † x′. So no element of X † X′ is in the kernel, and X † X′ is in the kernel. On the other hand, if X is not in the kernel, there is an x ∈ X that is in the kernel, and then either X′ is in the kernel, in which case x † X′ is too (by induction), or else there is x′ ∈ X′ that is in the kernel, in which case x † x′ is too (by induction), and so in any case there is an element of X † X′ that is in the kernel, so that X † X′ is not. ∴

The game product, on the other hand, is much less interesting. Though it is true that α ∗ β is an ordinal when α and β are ordinals — in fact, it is precisely the smaller of α and β, yet there is no (known) simple way of calculating either the Grundy function or the kernel of the game product of two sets.

4. The Conway product.

Definition (4.1). Let X, X′ be two sets. Then we define their \underline{Conway product} X ⊙ X′ by well-founded induction in the following way: X ⊙ X′ is the set whose elements are the (x ⊙ X′) ⊕ (X ⊙ x′) ⊕ (x ⊙ x′) with x ∈ X and x′ ∈ X′. If α_{1}, …, α_{k} are ordinals, then we define α_{1}@ ⋯ @α_{k} as the Grundy function of the set α_{1} ⊙ ⋯ ⊙ α_{k}. In other words, α@α′ is the smallest ordinal not equal to (β@α′)#(α@β′)#(β@β′) for all β < α and β′ < α′.

Proposition (4.2). The operation @ on ordinals is commutative and associative (in the sense that (⋯ (α_{1}@α_{2})@ ⋯)@α_{k} = α_{1}@ ⋯ @α_{k} = α_{1}@(⋯ @(α_{k−1}@α_{k}) ⋯)). The ordinal 1 acts as a unit element, and the ordinal 0 is absorbing. The operation @ is distributive over the operation #. We have α@α′ = 0 iff α = 0 or α′ = 0.

∵ Commutativity and associativity come from the facts that corresponding properties on the sum of games. That 0@α = 0 for any α is trivial from the definition. We prove by induction on α that 1@α = α: by definition, 1@α is the smallest ordinal not equal to 0@α#1@β#0@β, that is, β, for all β < α, so it is α which concludes the induction.

We now note that if β ≠ α (not necessarily β < α) and β′ ≠ α′ then we have α@α′ ≠ (β@α′)#(α@β′)#(β@β′) (indeed, this is part of the definition if β < α and β′ < α′, but since in this expression α and β play symmetric roles (because of the properties we already know of the operation #), and similarily for α′ and β′, this is true in all cases).

Let us now prove distributivity: we prove α@(α′#α′′) = (α@α′)#(α@α′′), and by induction we may suppose that this is true if any one of α, α′, α′′ is replaced by a smaller ordinal. Now if γ < α@(α′#α′′) then there exist β < α and β̃ < α′#α′′ such that γ = (β@(α′#α′′))#(α@β̃)#(β@β̃). Now because β̃ < α′#α′′, there exists, say, a β′ < α′ such that β̃ = β′#α′′. Then, using the induction hypothesis to expand the expression of γ, and also the fact that (β@α′′)#(β@α′′) = 0, we see that γ = (β@α′)#(α@β′)#(β@β′)#(α@α′′). Now since β < α and β′ < α′, we must have (β@α′)#(α@β′)#(β@β′) ≠ (α@α′), and by regularity of the operation # we conclude that γ ≠ (α@α′)#(α@α′′) (for any γ < α@(α′#α′′)). Conversely, suppose γ < (α@α′)#(α@α′′). Then we have, say γ = β̄#(α@α′′) for some ordinal β̄ < α@α′, which can then be written (β@α′)#(α@β′)#(β@β′) for some β < α and β′ < α′. Now by letting β̃ = β′#α′′, we see (this is the reverse calculation as previously) that γ = (β@(α′#α′′))#(α@β̃)#(β@β̃). Since β ≠ α and β̃ ≠ α′#α′′, by the previous comment, we have γ ≠ α@(α′#α′′). So we have proven that any ordinal less than one of the two ordinals α@(α′#α′′) and (α@α′)#(α@α′′) cannot be equal to the other one — evidently this shows that the two ordinals in question are equal, and this concludes the induction and the proof of distributivity.

If α = 0 or α′ = 0 then we already know that α@α′ = 0. Conversely, if α > 0 and α′ > 0 then α@α′ must be not equal to (0@α′)#(α@0)#(0@0) = 0. ∴

Theorem (4.3). For every ordinal α > 0, there exists a unique ordinal β such that α@β = 1. In other words, the operations # and @ make the class of all ordinals into a field of characteristic 2.

∵ Suppose on the contrary that there is an ordinal other than zero which has no @-inverse, and let α be the smallest such ordinal. Now let β be an ordinal such that the set of all ordinals less than β (which is none other than β itself!) contains α (and therefore any ordinal γ ≤ α), contains the @-inverse of every ordinal 0 < γ < α, and is closed under the two operations # and @. Such an ordinal β exists: indeed, it can be constructed as follows. Let β_{0} be the least upper bound of α and the @-inverse of every ordinal 0 < γ < α, let β_{1} be the least upper bound of the δ#δ′ and the δ@δ′ for δ, δ′ < β_{0}, and β_{2} be the least upper bound of the δ#δ′ and the δ@δ′ for δ, δ′ < β_{1}, and so on. Then the limit (the least upper bound) of the nondecreasing sequence β_{0}, β_{1}, … of ordinals is the desired ordinal β.

Now if 0 < γ < α then there exists an ordinal δ < β such that γ@δ = 1. I claim that γ@β ≥ β. Indeed, were this not the case, we would have β = (γ@β)@δ < β, since γ@β < β and δ < β, and this is a contradiction. Now for any ordinal γ′ < β, we have α@γ′ < β and γ@γ′ < β, therefore (α@γ′)#(γ@γ′) < β, and therefore (γ@β)#(α@γ′)#(γ@γ′) ≥ β (because otherwise we would have γ@β = ((α@γ′)#(γ@γ′))#((γ@β)#(α@γ′)#(γ@γ′)) < β, and we have proven the contrary). In particular, we have shown that for 0 < γ < α and γ′ < β we have (γ@β)#(α@γ′)#(γ@γ′) ≠ 1. But on the other hand if γ = 0, this is also true because α is supposed to have no @-inverse. Hence this is true for all γ < α and γ′ < β. By definition of α@β, this shows that α@β ≤ 1. But since α@β cannot be zero, we have α@β = 1, a contradiction to the fact that α was reputed to have no @-inverse. ∴

We shall write α^{@i} for the ordinal α@ ⋯ @α, with α appearing i times (here, i is a natural number, and, of course, we put α^{@0} = 1). We also call α^{@−i} the @-inverse of α^{@i}.

Theorem (4.4). For every ordinal numbers α_{0}, …, α_{n−1} (where n ≥ 1) there exists an ordinal ξ such that α_{0}#α_{1}@ξ# ⋯ #α_{n−1}@ξ^{@(n−1)}#ξ^{@n} = 0. In other words, the operations # and @ make the class of all ordinals into an algebraically closed field of characteristic 2.

∵ Call an ordinal β “algebraically stable” iff it is closed under the operations #, @ and taking the inverse, and, moreover, whenever α_{0}, …, α_{n−1} < β and ξ are such that α_{0}#α_{1}@ξ# ⋯ #ξ^{@n} = 0 then necessarily ξ < β. In other words, β is a subfield of the class of ordinals that is relatively algebraically closed. Now note that for any ordinal γ there is an algebraically stable ordinal β such that γ < β. The reasoning is similar to that used in theorem (4.3): start with β_{0} = γ + 1, and call β_{n+1} the least upper bound of all the δ#δ′, of all δ@δ′, of all δ^{@−1}, with δ, δ′ < β_{n}, and of all roots of all algebraic equations with all coefficients < β_{n}, and take for β the least upper bound of the β_{n} (this makes sense since an algebraic equation has only finitely many solutions).

Now consider α_{0}#α_{1}@ξ# ⋯ #ξ^{@n} = 0 an algebraic equation which we want to solve, and let β be an algebraically stable ordinal greater than all the α_{i}. Then we must have α_{0}#α_{1}@β# ⋯ #β^{@n} ≠ 0, for otherwise β < β (because β is algebraically stable), a contradiction. Then by definition of #, there exists an i and a γ < α_{i}@β^{@i} such that α_{0}# ⋯ #γ# ⋯ #β^{@n} = 0. Suppose for the moment that i ≠ n. Now since γ < α_{i}@β^{@i}, by the definition of @, there exist δ < α_{i} and δ′ < β^{@i} such that γ = δ@β^{@i}#α_{i}@δ′#δ@δ′. Then keep using the definition of @, starting with δ′ < β^{@i} this time, and we finally find that γ can be written as a polynomial in β with coefficients < β, and therefore that 0 can be written as a polynomial in β with coefficients < β, and leading coefficient 1. But this is absurd.

There remains the case where i = n. In other words, there exists γ < β^{@n} such that α_{0}# ⋯ #α_{n−1}@β^{@(n−1)}#γ = 0. But by using repeatedly the definition of @ on γ < β^{@n}, we find that there are δ_{1}, …, δ_{n} < β such that γ = (δ_{1}# ⋯ #δ_{n})@β^{n−1}# ⋯ #(δ_{1}@ ⋯ @δ_{n}) (where the terms we haven’t written are the usual symmetric polynomials of the δ_{i}). Now putting this value of γ in the equation we found above, we find that a polynomial in β, with all coefficients < β, is zero, and therefore the polynomial must be identically zero, which means that α_{0} = δ_{1}@ ⋯ @δ_{n}, and so on up to α_{n−1} = δ_{1}# ⋯ #δ_{n}. But it is well known that this means that δ_{1}, …, δ_{n} are the roots of the equation α_{0}#α_{1}@ξ# ⋯ #ξ^{@n} = 0. Therefore, it does have solutions, QED. ∴

The field thus obtained is called the Conway field. One of its interests is the following analogue to theorem (3.5):

Theorem (4.5). Let X and X′ be two sets, and α and α′ their Grundy functions. Then the Grundy function of the game sum X ⊙ X′ of X and X′ is α@α′.

∵ By well-founded induction, we can assume this is true with either X or X′ replaced by one its elements. We must now show two things. First, if x ∈ X and x′ ∈ X′, then the Grundy function of (x ⊙ X′) ⊕ (X ⊙ x′) ⊕ (x ⊙ x′) is not equal to α@α′. Indeed, if we let β ≠ α (resp. β′ ≠ α′) be the Grundy function of x (resp. x′) then that of x ⊙ X′ (resp. of X ⊙ x′, resp. of x ⊙ x′) is β@α′ (resp. α@β′, resp. β@β′) by the induction hypothesis; and by theorem (3.5), the Grundy function of (x ⊙ X′) ⊕ (X ⊙ x′) ⊕ (x ⊙ x′) is (β@α′)#(α@β′)#(β@β′) = ((α#β)@(α′#β′))#(α@α′). But since α#β ≠ 0 (because β ≠ α) and α′#β′ ≠ 0 (becuase β′ ≠ α′), we have (α#β)@(α′#β′) ≠ 0 and therefore (β@α′)#(α@β′)#(β@β′) cannot be equal to α@α′. Second, if γ < α@α′, we must show that there exist x ∈ X and x′ ∈ X′ such that the Grundy function of (x ⊙ X′) ⊕ (X ⊙ x′) ⊕ (x ⊙ x′) is γ. But if γ < α@α′, then by the definition of α@α′ there exists β < α and β′ < α′ such that γ = (α@β′)#(β@α′)#(β@β′). Now we can find (by the definition of the Grundy function) an x ∈ X whose Grundy function is β and an x′ ∈ X′ whose Grundy function is β′. By the induction hypothesis, the Grundy function of x ⊙ X′ is α@β′, that of X ⊙ x′ is β@α′, and that of x ⊙ x′ is β@β′. And by theorem (3.5), the Grundy function of (x ⊙ X′) ⊕ (X ⊙ x′) ⊕ (x ⊙ x′) is then γ. This concludes the proof. ∴ 5. Reduced game sums.

Definition (5.1). Let X, X′ be two sets. Then we define the \underline{reduced game sum} of X and X′, written X⊞X′ as the symmetric difference of {x⊞X′ : x ∈ X} and {X⊞x′ : x′ ∈ X′} (that is, its elements are those sets which can be written x⊞X′ with x ∈ X, or X⊞x′ with x′ ∈ X′, but not both).

Proposition (5.2). The reduced game sum is commutative and associative. The set ∅ acts as a unit element, and moreover X⊞X = ∅ for every set X. Furthermore, the Grundy function of X⊞X′ is α#α′ where α is the Grundy function of X and α′ that of X′.

∵ Commutativity and associativity are easy by induction by making use of the corresponding properties of the symmetric difference. That ∅⊞X = X⊞∅ = X and X⊞X = ∅ for every set X is trivial from the definitions.

We now prove the assertion concerning the Grundy function, by induction. Any element of X⊞X′ can be written x⊞X′, say, so its Grundy function is β#α′ where β is the Grundy function of x, and this is not equal to α#α′ since β ≠ α. This shows that the Grundy function of X⊞X′ is at less or equal to α#α′. Now if γ < α#α′ then we can write γ = β#α′, say, where β < α. Now β is the Grundy function of an x ∈ X, and then the Grundy function of x⊞X′ is β#α′ = γ. There are two cases: either x⊞X′ is an element of X⊞X′, in which case its Grundy function is not γ. Or there exists x′ ∈ X′ such that x⊞X′ = X⊞x′, in which case by making use of the properties already proven, we have X⊞X′ = x⊞x′, so the Grundy function of X⊞X′ is that of x⊞x′, viz. β#β′ where β′ is the Grundy function of x′, and since β#β′ ≠ β#α′ (because β′ ≠ α′), the Grundy function of X⊞X′ is not equal to β#α′ = γ in that case also. So the Grundy function of X⊞X′ is at least equal to α#α′, and finally it is equal to it, which proves the statement. ∴

Definition (5.3). Let X, X′ be two sets. Then we define their \underline{reduced Conway product} X⊡X′ by induction in the following way: X⊡X′ is the set whose elements are the (x⊡X′)⊞(X⊡x′)⊞(x⊡x′) with x ∈ X and x′ ∈ X′.

Theorem (5.4). Let X and X′ be two sets, and α and α′ their Grundy functions. Then the Grundy function of the game sum X⊡X′ of X and X′ is α@α′.

∵ Repeat exactly the proof of theorem (4.5), replacing ⊕ by ⊞, ⊙ by ⊡, and the reference to theorem (3.5) by one to proposition (5.2). ∴ 6. Turning games.

Definition (6.1). Let α be an ordinal. Then we write 2^{α} for the set of functions from α = {β : β < α} to 2 = {0, 1} with finite support (that is, which are equal to zero except on a finite number of β). We well order 2^{α} lexicographically, in other words, we put f < g iff f and g differ, and the largest β for which f(β) ≠ g(β) satisfies f(β) < g(β); with this order, 2^{α} is isomorphic (as a well-ordered set) to the ordinal 2^{α}. For β < α, we shall identify 2^{β} with a subset (indeed, an initial segment) of 2^{α}, namely those functions with support in β. Moreover, we define an operation ⊞ on 2^{α} in the following way: (f⊞g)(β) is 0 iff f(β) = g(β), and 1 otherwise. Finally, for β < α, we define an element e_{β} of 2^{α} by e_{β}(γ) = 1 iff γ = β, 0 otherwise.

Definition (6.2). Let 𝔐 be a subset of 2^{α} not containing 0 : we call such a set a \underline{system of moves}. Then we define the \underline{turning game} associated to 𝔐 as the game whose configuration space is 2^{α} and whose evolution relation is given by fρg iff g < f and f⊞g ∈ 𝔐. Note that 𝔐 is determined by the game as the set of those f for which fρ0, so it makes sense to talk of the system of moves of a given turning game.

Think an element of 2^{α} as representing an α-sequence of coins, all but a finite number of which are on tails. 𝔐 tells us which sets of coins a player is allowed to turn, subject to the constraint that the right-most coin turned must change from heads to tails.

Proposition (6.3). Let 𝔐 be a system of moves. Then in the turning game (2^{α}, ρ) associated to 𝔐, for every f, f′ ∈ 2^{α}, the configuration f⊞f′ is the reduced sum of f and f′ (in other words, the set of the pointed game (2^{α}, ρ, f⊞f′) is precisely the reduced game sum of that of (2^{α}, ρ, f) and that of (2^{α}, ρ, f′)).

∵ We have (f⊞f′)ρg iff f⊞g⊞f′ ∈ 𝔐 and g < (f⊞f′). Now if g < (f⊞f′), for the greatest β for which g(β) and (f⊞f′)(β) differ we have g(β) = 0 and (f⊞f′)(β) = 1; the latter means that exactly one of f(β) and f′(β) is 1 and the other one is 0, and therefore exactly one of (g⊞f′) < f and (f⊞g) < f′ holds. Conversely, if exactly one of (g⊞f′) < f and (g⊞f) < f′ holds then one sees easily that g < (f⊞f′). Now this proves that (f⊞f′)ρg iff exactly one of fρ(g⊞f′) and f′ρ(f⊞g) holds. We now proceed by induction with respect to the canonical order of 2^{α}, and we write X_{h} for the set of the pointed game (2^{α}, ρ, h). What we have just shown is that ext(f⊞f′) is the symmetric difference of {h⊞f′: h ∈ ext(f)} and {f⊞h: h ∈ ext(f′)}. Using the induction hypothesis, we then see that X_{f⊞f′} is the symmetric difference of {x⊞X_{f′}: x ∈ X_{f}} and {X_{f}⊞x′: x′ ∈ X_{f′}}, and this is precisely X_{f}⊞X_{f′}, hence the desired result. ∴

Corollary (6.4). Let 𝔐 be a system of moves. Then in the game (2^{α}, ρ) associated to 𝔐, for every f, f′ ∈ 2^{α}, the Grundy function of f⊞f′ is α#α′, where α is the Grundy function of f and α′ that of f′.

∵ This follows immediately from propositions (6.3) and (5.2) (the last statement). ∴

Definition (6.5). Let 𝔐 be a system of moves on an ordinal α. Then for each β < α we write 𝔐_{β}, and we call the \underline{β-stratum} of 𝔐, the set of the g ∈ 2^{β} ⊆ 2^{α} such that g⊞e_{β} ∈ 𝔐. In other words, 𝔐_{β} consists of those g ∈ 2^{α} such that e_{β}ρg. Note that conversely if for each β < α we are given a subset 𝔐_{β} of 2^{β} (in any way whatsoever), then there exists a unique system of moves 𝔐 on α such that 𝔐_{β} is the β-stratum of 𝔐.

Sophistication (6.6). Let α be an ordinal. The operation ⊞ endows 2^{α} with the structure of an 𝔽_{2}-vector space. Now consider 𝔐 a system of moves on α. Corollary (6.4) tells us that the function taking an element of 2^{α} to its Grundy function is a linear map of 𝔽_{2}- vector spaces (from 2^{α} to the class of ordinals). In particular, it is uniquely determined by its values on the canonical basis (e_{β}) of 2^{α}, where e_{β} is defined by e_{β}(γ) = 1 iff γ = β, 0 otherwise: if we write ϕ(β) for the Grundy function of e_{β}, then the Grundy function of f is ϕ(β_{1})# ⋯ #ϕ(β_{k}), where β_{1}, …, β_{k} are the distinct β < α such that f(β) = 1. Moreover, ϕ(β) can be computed as follows: it is the smallest ordinal that is not as above, where f ranges the elements of the set 𝔐_{β}. We shall (somewhat abusively) call ϕ the Grundy function of 𝔐.

For example, let 𝔐 be the set of those f ∈ 2^{α} such that f(β) = 1 for exactly two β < α. In other words, the game consists of turning exactly two coins, the right-most of which must change from heads to tails. Then for any β, the set of elements of e_{β}⊞𝔐 that are less than e_{β} is precisely the set of the e_{γ} such that γ < β, and so ϕ(β) is the smallest ordinal unequal to ϕ(γ) for γ < β. Therefore ϕ(β) = β for all β < α. This game is related to the game of Nim: when f ∈ 2^{α}, then f(β) indicates the parity of the set of Nim piles with β stones.