Nimber
In
mathematics, the
proper class of
nimbers is introduced in
combinatorial game theory. It is the proper class of
ordinals endowed with a new
nimber addition and
nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.
Nimber addition is defined recursively by
- α + β = mex{α ′ + β : α ′ < α, α + β ′ : β ′ < β},
where for a
set S of ordinals, mex(
S) is defined to be the "minimum excluded ordinal", i.e. mex(
S) is the smallest ordinal which is not an element of
S. For finite ordinals, the
nim sum (see
nim) is easily evaluated on computer by taking the exclusive-or of the corresponding numbers (whereby the numbers are given their
binary expansions, and the binary expansion of
x xor
y is evaluated
bit-wise).
Nimber multiplication is defined recursively by
- α β = mex{α ′ β + α β ′ − α ′ β ′ : α ′ < α, β ′ < β} = mex{α ′ β + α β ′ + α ′ β ′ : α ′ < α, β ′ < β}.
Except for the fact that nimbers form a
proper class and not a
set, the class of nimbers determines an
algebraically closed field of
characteristic 2. The nimber additive identity is the ordinal 0, and the nimber multiplicative identity is the ordinal 1. In keeping with the characteristic being 2, the nimber additive inverse of the ordinal α is α itself. The nimber multiplicative inverse of the nonzero ordinal α is given by 1/α = mex(
S), where
S is the smallest set of ordinals (nimbers) such that
- 0 is an element of S;
- if 0 < α ′ < α and β ′ is an element of S, then [1 + (α ′ − α) β ′ ]/α ′ is also an element of S.
For all natural numbers
n, the set of nimbers less than 2
2n form the
Galois field GF(2
2n) of order 2
2n.
Just as in the case of nimber addition, there is a means of computing the nimber product of finite ordinals. This is determined by the rules that
- the nimber product of distinct Fermat 2-powers (i.e. numbers of the form 22n for natural numbers n) is equal to their ordinary product;
- The nimber square of a Fermat 2-power x is equal to the standard value of 3x/2.
The smallest algebraically closed field of nimbers is the set of nimbers less than the ordinal ω
ωω, where ω is the smallest infinite ordinal. It follows that as a nimber, ω
ωω is
transcendental over the field.
References
J.H. Conway, On Numbers and Games, Academic Press Inc. (London) Ltd., 1976