Sprague-Grundy theorem and nimber multiplication
Явная конструкция алгебраического замыкания
поля из двух элементов
http://en.wikipedia.org/wiki/Nimber

Оказывается, на множестве ординалов
можно определить сложение и умножение.
Сложение на конечных ординалах определяется
как бинарное исключительное "или", умножение -
на разных числах вида $2^{2^n}$ как
нормальное умножение, на одинаковых -
по формуле $2^{2^n} * 2^{2^n} = 3 (2^{2^n-1})$.
Оказывается, что это поле.

При этом ординалы меньше $\omega^{\omega^\omega}$
образуют алгебраическое замыкание $\Z/2\Z$.

Эти операции определил Конуэй.
Вот тут излагается, каким образом их
можно получить: 0 | 1 | 2 | 3.

Определение Конуэя происходит из комбинаторной теории
игр. Игра - это направленный граф, то есть набор "позиций",
соединенных "ходами", при этом "ходы" помечены
"L" и "R" - "L" это ходы, которые может
сделать левый игрок, "R" - ходы правого
игрока. Игра "заканчивается" в позиции,
из которой нет ходов для "L" и "R".
Одна из "позиций" отмечена как "стартовая".
Игроки ходят из стартовой позиции по очереди.

К этому накладывается условие - любая
игра заканчивается за конечное число ходов,
при любой стратегии игроков "L" и "R" и независимо
от порядка ходов.

"Левая опция" $G^L$ для игры $G$ - это подигра,
начинающаяся с какой-то из позиций, в которую со старта
ведет стрелка "L". "Правая опция" $G^R$ определяется
аналогично. В силу того, что игры заканчиваются, правая
и левая опция всегда строго меньше самой игры.

Имеет место "принцип индукции Конуэя". Предположим,
что свойство $P$ выполнено для $G$ в том случае, если
оно выполнено для $G^R$ и $G^L$. Тогда оно выполнено
для любой игры $G$.

Игроки ходят по очереди, выбирая из данной позиции
стрелку, помеченную их именем. Игрок проигрывает,
если у него нет хода.

Хороший пример игры - множество всех ординалов,
со стрелками, ведущими из ординала в строго меньший
ординал. Такая игра всегда кончается, хотя
множество позиций несчетно.

Игры можно задавать рекурсивно, перечисляя левые и
правые опции: $G=\{ G^L, ... | G^R, ... \}$.

На играх можно определить сложение и вычитание,
следующим образом:
\[
G+H = \{ G^L+ H, H^L+G, ... | G^R+ H, H^R+G, ...\}
\]
Сумма "шашек и шахмат" состоит в том, что на каждом
ходу можно сделать ход в шашки, на одной доске,
а можно в шахматы, на другой доске.
\[
-G = \{ -G^R, ... | -G^L, ... \}
\]
Это определение рекурсивное и использует индукцию
Конуэя. Довольно понятно, что сложение
ассоциативно и коммутативно. Если второй игрок
имеет выигрышную стратегию, независимо от того,
правый он или левый, это обозначается $G=0$.
Легко видеть, что $G-G=0$. Игра "G-G" составлена
из двух досок, каждый игрок играет на одной
за "R" по правилам $G$, на второй за "L".
Ясно, что второй игрок в игре $G-G$ может
всегда копировать ход первого. Поэтому
классы эквивалентности игр по модулю
соотношения $G=0$ образуют группу.

Игра называется impartial (не знаю,
как это по-русски, Яндекс не говорит; возможно,
"беспристрастная"), если опции левого игрока и правого игрока
одинаковы. Крестики-нолики, например, не таковы (один игрок
рисует нолики, другой крестики). А игра в ординалы,
описанная выше, такова: переход от ординала
к ординалу поменьше приводит к тому же результату,
если это делает правый или левый игрок. Для
беспристрастной игры $G$, имеем $G=-G$.

Оказывается, что любая impartial game
эквивалентна, в вышеуказанном смысле, какому-то
ординалу (Sprague-Grundy theorem; 1935, 1939).
Доказать это весьма просто.

Игра, эквивалентная игре в ординал $n$, называется
нимбером. Такую игру обозначают $*n$.

Сумма ординалов приводит к известной игре "ним":
перед игроками лежит конечный набор куч с
вполне упорядоченными предметами, каждый игрок
может взять одну из куч и выкинуть оттуда
все элементы, большие заданного; проигрывает
тот, кто не сможет выкинуть.

Во-первых, два разных ординала не эквивалентны:
действительно, если ординал $*n$ не равен $*k$,
первый игрок может выиграть, уравняв эти ординалы,
и после этого копируя все ходы второго игрока.
Значит, $*n+*k = *n-*k\neq 0$.

Теорема о богусном ниме.
Пусть задана игра $G$, все опции $G_\alpha$ которой
эквивалентны ординалам вида $*n$. Тогда $G$ эквивалентна нимберу
$mex(G_{\alpha})$, где $mex(G_{\alpha})$ - минимальный
ординал, который не содержится в множестве $\{G_\alpha\}$.

Доказательство
Нужно доказать, что $G+mex(G_{\alpha})=0$.
В игре $G+mex(G_{\alpha})$ первый игрок может
сделать один из следующих ходов:

1. Перейти к $G + *k$, где $*k < mex(G_{\alpha})$.
Но в этом случае $*k$ есть одна из опций $G$,
и второй игрок отвечает ему, переходя к $*k+*k$.
После этого он может выиграть, повторяя
ходы первого игрока.

2. Перейти к $*n + mex(G_{\alpha})$,
где $*n$ - одна из опций $G$. Эти два ординала
не равны, второй игрок их уравнивает, и выигрывает,
всякий раз повторяя ход первого.
\endproof

Тепрема Шпрага-Гранди следует из теоремы о богусном
ниме и индукции Конуэя: действительно, пусть задана
какая-то impartial game $G$; по предположению индукции,
мы можем считать, что все ее опции $G_\alpha$ - ординалы,
но тогда $G=mex(G_{\alpha})$.

Умножение на нимберах определено индуктивно,
следующим образом
\[
xy = mex(\{ x'y + xy' + x'y' \}),
\]
где $\{ x'y + xy' + x'y' \}$ обозначает множество всех
ординалов вида $x'y + xy' + x'y'$, для всех $x'< x$, $y' < y$.
На языке теории игр, игра $xy$ есть игра с опциями
$(x y', x' y, x'y')$, где $x', y'$ - все опции для $x$ и $y$.
Поэтому $x(yz)$ и $(xy)z$ - игры с опциями
$(x y z', x y'z, xy z', x y'z', x' y z', x' y' z, x'y'z')$
Пользуясь индукцией Конуэя, скобки можно не расставлять -
для всех опций $x$ и $y$ умножение уже ассоциативно).
Дистрибутивность умножения тоже очевидна.
Мы доказали, что нимберы образуют кольцо.
Единица - это ординал 1, ноль - ординал 0.

Почему это будет поле, и алгебраически
замкнутое поле к тому же, мне не ясно.

Привет