Nimber
Encyclopedia
In mathematics
, the proper class of poo poo nimbers (occasionally called Grundy numbers) is introduced in combinatorial game theory
, where they are defined as the values of nim
heaps, but arise in a much larger class of games because of the Sprague–Grundy theorem
. 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.
is equivalent to a nim heap of a certain size. Nimber addition (also known as nim-addition) can be used to calculate the size of a single heap equivalent to a collection of heaps. It is defined recursively by
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 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 (nim-multiplication) is defined recursively by
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
For all natural numbers n, the set of nimbers less than 22n form the Galois field GF(22n) of order 22n.
In particular, this implies that the set of finite nimbers is isomorphic to the direct limit
of the fields GF(22n), for each positive n. This subfield is not algebraically closed, however.
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 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.
This subset is closed under both operations, since 16 is of the form 22n
(When you prefer simple text tables - they are here.)
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the proper class of poo poo nimbers (occasionally called Grundy numbers) is introduced in combinatorial game theory
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
, where they are defined as the values of nim
Nim
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap....
heaps, but arise in a much larger class of games because of the Sprague–Grundy theorem
Sprague–Grundy theorem
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to...
. It is the proper class of ordinals
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
endowed with a new nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.
Properties
The Sprague–Grundy theorem states that every impartial gameImpartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
is equivalent to a nim heap of a certain size. Nimber addition (also known as nim-addition) can be used to calculate the size of a single heap equivalent to a collection of heaps. It is defined recursively by
where for a set S of ordinals, mex
Mex (mathematics)
In combinatorial game theory, the mex, or "minimum excludant", of a set of ordinals denotes the smallest ordinal not contained in the set....
(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 is easily evaluated on computer by taking the exclusive-or of the corresponding numbers (whereby the numbers are given their binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
expansions, and the binary expansion of (x xor y) is evaluated bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
-wise).
Nimber multiplication (nim-multiplication) is defined recursively by
- α β = mex{α ′ β + α β ′ − α ′ β ′ : α ′ < α, β ′ < β} = mex{α ′ β + α β ′ + α ′ β ′ : α ′ < α, β ′ < β}.
Except for the fact that nimbers form a proper class
Class (set theory)
In set theory and its applications throughout mathematics, a class is a collection of sets which can be unambiguously defined by a property that all its members share. The precise definition of "class" depends on foundational context...
and not a set, the class of nimbers determines an algebraically closed field
Algebraically closed field
In mathematics, a field F is said to be algebraically closed if every polynomial with one variable of degree at least 1, with coefficients in F, has a root in F.-Examples:...
of characteristic
Characteristic (algebra)
In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...
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 22n form the Galois field GF(22n) of order 22n.
In particular, this implies that the set of finite nimbers is isomorphic to the direct limit
Direct limit
In mathematics, a direct limit is a colimit of a "directed family of objects". We will first give the definition for algebraic structures like groups and modules, and then the general definition which can be used in any category.- Algebraic objects :In this section objects are understood to be...
of the fields GF(22n), for each positive n. This subfield is not algebraically closed, however.
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 (numbers of the form 22n) is equal to their ordinary product;
- The nimber square of a Fermat 2-power x is equal to 3x/2 as evaluated under the ordinary multiplication of natural numbers.
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
Transcendental number
In mathematics, a transcendental number is a number that is not algebraic—that is, it is not a root of a non-constant polynomial equation with rational coefficients. The most prominent examples of transcendental numbers are π and e...
over the field.
Addition and multiplication tables
The following tables exhibit addition and multiplication among the first 16 nimbers.This subset is closed under both operations, since 16 is of the form 22n
(When you prefer simple text tables - they are here.)