Nimber
Table Of Contents
- Introduction
- Simplest Group Structure Over Ordinals
- Simplest Group Extension Theorems
- Simplest Field Structure Over Ordinal
- Simplest Field Extension Theorems
- Conclusion
Introduction
안녕하세요, Aeren입니다!
$\oplus$가 bitwise-xor을 나타낼 때, nim game에서 크기 $x$와 $y$인 heap 두개로 이루어진 game과 크기 $x \oplus y$인 heap 한개로 이루어진 game이 동치임은 많이 알려져 있습니다. 그 때문에, $\oplus$를 nim-addition이라 부르기도 합니다. 이번 글에서는 nim-addition및 관련 연산을 game theory가 아닌 순수한 algebra의 관점에서 바라봐 보려고 합니다.
이 글은 John Horton Conway의 “On Numbers and Games”을 바탕으로 작성되었습니다.
Simplest Group Structure Over Ordinals
$\Omega$를 ordinal number들의 proper class라고 하겠습니다. 목표는 $(\Omega, \oplus)$가 group이 되는 가장 간단한 연산 $\oplus: \Omega ^ 2 \rightarrow \Omega$를 찾는 것입니다.
각 ordinal $a, b$를 $(a, b)$가 사전순(lexicographic)으로 증가하는 순서대로 보면서 $a \oplus b$를 가능한 가장 간단한, 즉 가장 작은, 값으로 대응시키는 과정을 생각해 봅시다.
임의의 group $(G, *)$는 cancellation law
$ \forall a , b , c \in G: (a * b = a * c \rightarrow b = c) \land (b * a = c * a \rightarrow b = c)$
가 성립하므로, 임의의 ordinal $a’ < a, b’ < b$에 대하여 $a \oplus b \ne a’ \oplus b$ 그리고 $a \oplus b \ne a \oplus b’$이 성립해야 합니다. 따라서
$a \oplus b = \mathrm{mex} \lbrace a’ \oplus b’ : (a’ < a \land b’ = b) \lor (a’ = a \land b’ < b) \rbrace$
라고 정의해 봅시다. 단, 임의의 $S \subsetneq \Omega$에 대하여 $\mathrm{mex} \space S = \min (\Omega - S)$로 정의합니다. ($\Omega$가 well-ordered되어 있으므로 이 정의는 well-defined 되어 있습니다.)
정의대로 addition table을 채워보면 다음과 같습니다.
위 정의만 보면 $(\Omega, \oplus)$가 group이라는 것이 자명하지 않습니다. 지금부터 그 사실을 증명해 보도록 하겠습니다.
THEOREM (Associativity)
임의의 $a,b,c\in \Omega$에 대하여 다음이 성립한다.
$(a \oplus b) \oplus c = a \oplus (b \oplus c)$
PROOF
정의에 의해
$(a \oplus b) \oplus c = \mathrm{mex} \lbrace d’ \oplus c’ : (d’ < a \oplus b \land c’ = c) \lor (d’ = a \oplus b \land c’ < c) \rbrace $
입니다.
$S = \lbrace d’ \oplus c’ : (d’ < a \oplus b \land c’ = c) \lor (d’ = a \oplus b \land c’ < c) \rbrace $
라고 하면 임의의 $(a \oplus b) \oplus c \notin T$인 $S \subseteq T \subset \Omega$에 대하여 $(a \oplus b) \oplus c = \mathrm{mex} \space T$임을 알 수 있습니다.
$S’ = \mathrm{mex} \lbrace (a’ \oplus b’) \oplus c’ : (a’ < a \land b’ = b \land c’ = c) \lor (a’ = a \land b’ < b \land c’ = c) \lor (a’ = a \land b’ = b \land c’ < c) \rbrace$
라고 정의합시다. Cancellation law에 의해 $S’$이 위 $T$의 조건을 만족합니다. 따라서 $(a \oplus b) \oplus c = \mathrm{mex} \space S’$입니다. 이제 (transfinite) induction hypothesis에 의해 $(a’ \oplus b’ ) \oplus c’ = a’ \oplus (b’ \oplus c’)$이므로
$S’ = \mathrm{mex} \lbrace a’ \oplus (b’ \oplus c’) : (a’ < a \land b’ = b \land c’ = c) \lor (a’ = a \land b’ < b \land c’ = c) \lor (a’ = a \land b’ = b \land c’ < c) \rbrace$
이며, 처음과 같은 논증으로
$(a \oplus b) \oplus c = \mathrm{mex} \space S’ = a \oplus (b \oplus c)$
을 얻습니다.
$\blacksquare$
THEOREM (Existence of an Identity)
임의의 $a \in \Omega$에 대하여 다음이 성립한다.
$a \oplus 0 = 0 \oplus a = a$
PROOF
정의에 의해
$a \oplus 0 = \mathrm{mex}\lbrace a’ \oplus 0 : a’ < a \rbrace$
입니다. 이제 induction hypothesis에 의해 $a’ \oplus 0 = a’$이므로
$a \oplus 0 = \mathrm{mex}\lbrace a’ : a’ < a \rbrace = a$
입니다. $0 \oplus a = a$도 마찬가지 논증으로 성립합니다.
$\blacksquare$
THEOREM (Existence of an Inverse)
임의의 $a \in \Omega$에 대하여 다음이 성립한다.
$a \oplus a = 0$
PROOF
임의의 $a, b\in \Omega$에 대하여 $a \oplus b = 0$일 필요충분조건이 $a = b$임을 보이면 충분합니다.
$a = b$일 경우
$a \oplus a = \mathrm{mex} \lbrace a’ \oplus a’’ : (a’ < a \land a’’ = a) \lor (a’ = a \land a’’ < a) \rbrace$
이며 induction hypothesis에 의해 $a’ \oplus a’’ \ne 0$이므로 $a \oplus a = 0$입니다.
$a \ne b$일 경우
$a \oplus b = \mathrm{mex} \lbrace a’ \oplus b’ : (a’ < a \land b’ = b) \lor (a’ = a \land b’ < b) \rbrace$
이며, induction hypothesis에 의해 $\mathrm{mex}$의 argument에 해당되는 set이 $ \min(a, b) \oplus \min(a, b) = 0 $을 포함하므로 $a \oplus b \ne 0$입니다.
$\blacksquare$
THEOREM (Commutativity)
임의의 $a, b \in \Omega$에 대하여 다음이 성립한다.
$a \oplus b = b \oplus a$
PROOF
정의에 의해
$a \oplus b = \mathrm{mex} \lbrace a’ \oplus b’ : (a’ < a \land b’ = b) \lor (a’ = a \land b’ < b) \rbrace$
입니다. 이제 induction hypothesis에 의해 $a’ \oplus b’ = b’ \oplus a’$이므로
$\begin{align} a \oplus b &= \mathrm{mex} \lbrace a’ \oplus b’ : (a’ < a \land b’ = b) \lor (a’ = a \land b’ < b) \rbrace \newline &= \mathrm{mex} \lbrace b’ \oplus a’ : (a’ < a \land b’ = b) \lor (a’ = a \land b’ < b) \rbrace \newline &= b \oplus a \end{align}$
입니다.
$\blacksquare$
위 theorem들에 의해 $(\Omega, \oplus)$가 $0$을 additive identity로 갖는 commutative group of exponent 2임을 알 수 있습니다.
Simplest Group Extension Theorems
$(\Omega, \oplus)$의 구조를 더 자세히 알기 위한 몇가지 theorem들을 소개하겠습니다.
지금부터 von Neumann의 convention에 따라 임의의 ordinal $a$와 set $\lbrace a’ : a’ < a \rbrace$을 identify시키겠습니다.
THEOREM
임의의 $\Delta \in \Omega$에 대하여, $(\Delta, \oplus)$가 group이 아니라면, $a \oplus b \notin \Delta$인 사전순으로 가장 작은 순서쌍 $(a, b)$에 대하여, $a \oplus b = \Delta$이다.
PROOF
$a \oplus b \notin \Delta$이므로 $a \oplus b \ge \Delta$입니다. 그런데 임의의 ordinal $a’ < a, b’ < b$에 대하여 $a’ \oplus b$와 $a \oplus b’$은 모두 $\Delta$의 원소이므로, $a \oplus b \le \Delta$입니다. 따라서 $a \oplus b = \Delta$입니다.
$\blacksquare$
THEOREM
임의의 $\Delta \in \Omega$에 대하여, $(\Delta, \oplus)$가 group이라면, 임의의 $a \in \Omega, b \in \Delta$에 대하여 다음이 성립한다.
$(\Delta \cdot a)\oplus b = (\Delta \cdot a) + b$
PROOF
$(\Delta \cdot a)\oplus b$에서 제외되어야 할 ordinal들의 set은 모든 $a’ < a, \delta \in \Delta, b’ < b$에 대하여, $((\Delta \cdot a’) + \delta) \oplus b$ 혹은 $(\Delta \cdot a) \oplus b’$꼴로 표현가능한 ordinal들의 set과 같습니다. 그런데 $\Delta$가 group이므로 임의의 $c’ \in \Delta$에 대하여, $\delta \oplus b = c’$이 성립하도록 $\delta$를 잡을 수 있습니다. 따라서, induction hypothesis에 의해
$((\Delta \cdot a’) + \delta) \oplus b = (\Delta \cdot a’ )\oplus (\delta \oplus b) = (\Delta \cdot a’) \oplus c’ = (\Delta \cdot a’) + c’$
이며, 제외되어야 할 ordinal들은 $(\Delta \cdot a’) + c’$ 혹은 $(\Delta \cdot a) + b’$으로 표현가능한 ordinal들의 set과 같습니다. 그런데 이 두 식들은 $(\Delta \cdot a) + b$보다 작은 ordinal들의 일반적인 형태와 같습니다. 따라서
$(\Delta \cdot a)\oplus b = (\Delta \cdot a) + b$
입니다.
$\blacksquare$
$(1, \oplus)$가 group임은 쉽게 알 수 있습니다. 또한 위 theorem에 의해, $(\Delta, \oplus)$가 group이라면, 다음으로 group을 이루는 ordinal은 $\Delta \cdot 2$입니다. 따라서 group을 이루는 ordinal들은 정확히 어떤 ordinal $a$에 대하여 $2 ^ a$꼴로 표현되는 ordinal들입니다.
임의의 ordinal $a$는 finite ordinal $n$과 ordinal $\alpha _ 0 > \alpha _ 1 > \cdots > \alpha _ {n - 1}$에 대하여
$a = 2 ^ {\alpha _ 0} + 2 ^ {\alpha _ 1} + \cdots + 2 ^ {\alpha _ {n - 1}}$
꼴로 표현가능함이 알려져 있습니다. 이제 위 theorem들을 적용하면
$\begin{align}a &= 2 ^ {\alpha _ 0} \oplus (2 ^ {\alpha _ 1} + \cdots + 2 ^ {\alpha _ {n - 1}}) \newline &= 2 ^ {\alpha _ 0} \oplus 2 ^ {\alpha _ 1} \oplus (\cdots + 2 ^ {\alpha _ {n - 1}}) \newline &= \cdots \newline &= 2 ^ {\alpha _ 0} \oplus 2 ^ {\alpha _ 1} \oplus \cdots \oplus 2 ^ {\alpha _ {n - 1}} \end{align}$
이 되어 흔히 알려진 nim addition의 bitwise-xor과의 동치관계가 증명됩니다.
Simplest Field Structure Over Ordinals
목표는 $(\Omega, \oplus, \otimes)$가 field가 되는 가장 간단한 연산 $\otimes: \Omega ^ 2 \rightarrow \Omega$를 찾는 것입니다. $\oplus$가 nim addition이라 불리기 때문에, $\otimes$를 nim multiplication이라 부르도록 하겠습니다.
Addition과 마찬가지로 각 ordinal $a, b$를 $(a, b)$가 사전순(lexicographic)으로 증가하는 순서대로 보면서 $a \otimes b$를 가능한 가장 간단한, 즉 가장 작은, 값으로 대응시키는 과정을 생각해 봅시다.
임의의 field $(F, *, \bullet)$는 zero divisor를 갖지 않습니다. 즉,
$\forall a,b\in F: (a \neq 0 _ F \land b \neq 0 _ F) \rightarrow a \bullet b \neq 0$
이 성립합니다. 그러므로 임의의 ordinal $a’ < a, b’ < b$에 대하여,
$(a \oplus a’) \otimes (b \oplus b’) \neq 0$
이 성립하기를 원합니다. 만약 $(\Omega, \oplus, \otimes)$가 field가 되도록 $\otimes$가 정의되었다면, 위 조건은
$\begin{align} ( a \oplus a ‘ ) \otimes ( b \oplus b ‘ ) &= ( a \otimes b ) \oplus ( a \otimes b ‘ ) \oplus ( a ‘ \otimes b ) \oplus ( a ‘ \otimes b ‘ ) \neq 0 \newline \leftrightarrow a \otimes b &\neq ( a \otimes b ‘ ) \oplus ( a ‘ \otimes b ) \oplus ( a ‘ \otimes b ‘ ) \end{align}$
와 동치가 됩니다. 따라서,
$a \otimes b = \mathrm{mex} \lbrace (a \otimes b’) \oplus (a’ \otimes b) \oplus (a’ \otimes b ‘ ) : a ‘ < a \land b ‘ < b \rbrace$
로 정의해보겠습니다.
정의대로 multiplication table을 채워보면 다음과 같습니다.
Multiplicative inverse의 존재성을 제외한 field axiom들은 addition과 마찬가지로 간단한 induction을 통해 보일 수 있습니다. 따라서 $(\Omega, \oplus, \otimes)$는 integral domain입니다.
Simplest Field Extension Theorems
이제 multiplicative inverse의 존재성 증명 및 $(\Omega, \oplus, \otimes)$의 구조를 더 자세히 알기 위한 theorem들을 소개하겠습니다.
THEOREM
임의의 $\Delta \in \Omega$에 대하여, $(\Delta, \oplus)$가 group이고, $(\Delta, \oplus, \otimes)$가 ring이 아니라면, $a \otimes b \notin \Delta$인 사전순으로 가장 작은 순서쌍 $(a, b)$에 대하여, $a \otimes b = \Delta$이다.
PROOF
$a \otimes b \notin \Delta$이므로 $a \otimes b \ge \Delta$입니다. 그런데 임의의 ordinal $a’ < a, b’ < b$에 대하여
$(a \otimes b’) \oplus (a’ \otimes b) \oplus (a’ \otimes b’ ) \in \Delta$
이므로, $a \otimes b \le \Delta$입니다. 따라서 $a \otimes b = \Delta$입니다.
$\blacksquare$
THEOREM
임의의 $\Delta \in \Omega$에 대하여, $(\Delta, \oplus, \otimes)$가 ring이며, $\Gamma \le \Delta$가 $0$이 아닌 모든 원소가 $\Delta$에서 inverse를 갖는 additive subgroup이라면, 모든 $\gamma \in \Gamma$에 대하여, $\Delta \otimes \gamma = \Delta \cdot \gamma$가 성립한다.
PROOF
$\Delta \otimes \gamma$에서 제외해야할 ordinal들은 임의의 ordinal $\delta < \Delta$와 $\gamma’ < \gamma$에 대하여
$(\Delta \otimes \gamma’) \oplus (\delta \otimes (\gamma \oplus \gamma’))$
꼴입니다. 그런데 $\gamma \oplus \gamma’$이 $\Delta$에서 invertible하므로, 임의의 $\delta’ \in \Delta$에 대하여, 적당한 $\delta$를 잡아 $\delta’ = \delta \otimes (\gamma \oplus \gamma’)$이 성립하게 할 수 있습니다. 따라서 제외해야할 ordinal들의 일반적인 형태는
$(\Delta \otimes \gamma’)\oplus \delta’ = (\Delta \cdot \gamma’) + \delta’$
이 됩니다. 그런데 이는 $\Delta \cdot \gamma$보다 작은 ordinal들의 일반적인 형태이므로,
$\Delta \otimes \gamma = \Delta \cdot \gamma$
이 성립하게 됩니다.
$\blacksquare$
이제 임의의 ordinal $a$와 finite ordinal $n$에 대하여,
$\begin{align} a ^ {\underline{n}} = \bigotimes _ {i = 1} ^ n a \end{align}$
라 정의하겠습니다.
THEOREM
임의의 $\Delta \in \Omega$에 대하여, $(\Delta, \oplus, \otimes)$가 field가 아닌 ring이라면 $\Delta$안에서 inverse를 갖지 않는 가장 작은 0이 아닌 ordinal을 $a$라 하고, $\Gamma$를 $\Gamma \le a$이며 $(\Gamma, \oplus)$가 group인 가장 큰 ordinal 이라 할 때
- $a \otimes \Delta = 1$이고
- 모든 finite ordinal $n$, ordinal $\delta \in \Delta$, 그리고 ordinal $\gamma _ 1, \cdots, \gamma _ n \in \Gamma$에 대하여 $(\Delta ^ \underline{n} \otimes \gamma _ n) \oplus \cdots \oplus (\Delta ^ \underline{1} \otimes \gamma _ 1) \oplus \delta = \Delta \cdot (\Gamma ^ {n - 1} \cdot \gamma _ n + \cdots + \Gamma ^ 0 \cdot \gamma _ 1) + \delta$ 이 성립한다.
PROOF
(1)
$\Delta \otimes \Gamma$의 제외되는 ordinal들의 일반적인 형태는 임의의 $\delta \in \Delta, \gamma \in \Gamma$에 대하여,
$(\Delta \otimes \gamma) \oplus (\delta \otimes (\Gamma \oplus \gamma))$
입니다. $b = a \oplus \Gamma$라고 하면 모든 $\gamma < b$에 대하여 $\Gamma \oplus \gamma$가 $\Delta$에서 invertible하므로, 임의의 $\delta’ \in \Delta$에 대하여
$\delta’ = \delta \otimes (\Gamma \oplus \gamma)$
이 성립하도록 할 수 있습니다. 따라서 $\Delta \otimes b$보다 작은 모든 수는 $b’ < b$에 대하여 $\Delta \cdot b + \delta’$의 형태를 갖기 때문에, $\Delta \otimes \Gamma$에서 제외되며, $\Delta \otimes b = \Delta \cdot b$역시 $\gamma = b, \delta = 0$으로부터 제외됨을 알 수 있습니다. 가장 작은 제외되지 않은 ordinal은 $(\Delta \otimes b) \oplus 1 = (\Delta \cdot b) + 1$이기 때문에,
$\Delta \otimes \Gamma = (\Delta \otimes b) \oplus 1 \leftrightarrow \Delta \otimes a = 1$
이 성립합니다.
(2)
$\Delta ^ \underline{n + 1} = \Delta \cdot \Gamma ^ n$임을 보이면 충분합니다. $\Delta ^ \underline{n + 1}$의 임의의 제외되는 ordinal은 임의의 $\delta _ 0, \cdots, \delta _ n \in \Delta$에 대하여
$(\Delta ^ \underline{n} \otimes (\delta _ 0 \oplus \cdots \oplus \delta _ n)) \oplus (\Delta ^ \underline{n - 1} \otimes ((\delta_0 \otimes \delta _ 1) \oplus \cdots)) \oplus (\delta _ 0 \otimes \cdots \otimes \delta _ n)$
꼴의 형태를 갖습니다. $\Delta ^ \underline{k}$에 곱해지는 각 coefficient들은 어떤 $\gamma \in \Gamma$에 대하여 $\gamma$ 혹은 $\Gamma \oplus \gamma$의 형태만을 갖습니다. 이제 (1)에서 구한 식 $\Delta \otimes \Gamma = (\Delta \otimes b) \oplus 1$으로부터, 위 식을 어떤 $\gamma _ 1, \cdots, \gamma _ n \in \Gamma$와 $\delta \in \Delta$에 대하여
$(\Delta ^ \underline{n} \otimes \gamma _ n) \oplus \cdots \oplus (\Delta ^ \underline{1} \otimes \gamma _ 1) \oplus \delta$
꼴로 표현할 수 있습니다. 이제 induction hypothesis에 의해, 위 값이 $\Delta \cdot \Gamma ^ n$보다 작음이 얻어지므로, $\Delta ^ \underline{n + 1} \le \Delta \cdot \Gamma ^ n$이며, induction hypothesis로부터 $\Delta ^ \underline{n + 1} \ge \Delta \cdot \Gamma ^ n$이므로, $\Delta ^ \underline{n + 1} = \Delta \cdot \Gamma ^ n$임이 보여집니다.
$\blacksquare$
THEOREM
임의의 $\Delta \in \Omega$에 대하여, $(\Delta, \oplus, \otimes)$가 algebraically closed가 아닌 field라면, $\Delta$는 $\Delta$ 안에서 root를 갖지 않는 사전순으로 가장 작은(여기서 두 polynomial을 비교할 때, 높은 차수의 coefficient부터 비교합니다.) polynomial
$P(X) = X ^ \underline{N} \oplus (X ^ \underline{N - 1} \otimes a _ {N - 1}) \oplus \cdots \oplus (X ^ \underline{1} \otimes a _ 1) \oplus a _ 0$
의 root이다. 또한, 모든 ordinal $n < N$과 $\delta _ 0, \cdots, \delta _ n \in \Delta$에 대하여
$(\Delta ^ \underline{n} \otimes \delta _ n)\oplus \cdots \oplus \delta _ 0 = \Delta ^ n \cdot \delta _ n + \cdots + \delta _ 0$
이 성립한다.
PROOF
$\Delta ^ \underline{n}$의 제외되는 ordinal들의 일반적인 형태는 임의의 $\delta _ 1, \cdots \delta _ n \in \Delta$에 대하여
$(\Delta ^ \underline{n - 1} \otimes (\delta _ 1 \oplus \cdots \oplus \delta _ n)) \oplus (\Delta ^ \underline{n - 2} \otimes ((\delta_1 \otimes \delta _ 2) \oplus \cdots)) \oplus (\delta _ 1 \otimes \cdots \otimes \delta _ n)$
입니다. $P(X)$보다 사전순으로 작은 모든 polynomial $Q(X)$는 $\Delta$위에서 적어도 한 개의 root를 가지므로, $Q(X)$는 $\Delta$에서 linear factor들의 곱으로 완전히 분해되며, $n$과 $\delta _ i$를 적절히 잡으면 $Q(X)$가 $\Delta$를 root로 가질 수 없음을 보일 수 있습니다. 또한,
$(\Delta ^ \underline{N - 1} \otimes a _ {N - 1}) \oplus \cdots \oplus (\Delta ^ \underline{1} \otimes a _ 1) \oplus a _ 0 = \Delta ^ {N - 1} a _ {N - 1} + \cdots + a _ 0$
보다 작은 모든 ordinal들은 $\Delta ^ \underline{N}$에서 제외해야 할 ordinal로서 나타나며, $\Delta ^ \underline{N}$자체는 나타나지 않으므로
$\Delta ^ \underline{N} = (\Delta ^ \underline{N - 1} \otimes a _ {N - 1}) \oplus \cdots \oplus (\Delta ^ \underline{1} \otimes a _ 1) \oplus a _ 0$
이 성립하게 되어 $P(\Delta) = 0$입니다.
$\blacksquare$
THEOREM
임의의 $\Delta \in \Omega$에 대하여, $(\Delta, \oplus, \otimes)$가 algebraically closed field라면, $\Delta$는 $(\Delta, \oplus, \otimes)$위에서 transcendental하며, 모든 finite ordinal $n$과 $\delta _ 0, \cdots, \delta _ n \in \Delta$에 대하여
$(\Delta ^ \underline{n} \otimes \delta _ n)\oplus \cdots \oplus \delta _ 0 = \Delta ^ n \cdot \delta _ n + \cdots + \delta _ 0$
이 성립한다.
PROOF
임의의 algebraically closed field에 대하여, field 바깥쪽 원소는 그 field 위에서 transcendental하므로 첫 번째 statement는 자명합니다. 두 번째 statement는 이전 theorem과 마찬가지 과정으로 증명할 수 있습니다.
$\blacksquare$
Conclusion
각각의 ordinal $\Delta$는 $\Delta$미만의 ordinal들의 set을 가장 간단한 형태로 확장시킵니다. 이 때, 확장에는 점차 “복잡해지는” 방법이 쓰입니다. 여기서, “복잡한 정도”는 addition, multiplication, inverse, algebraic extension, transcendental extension순으로 증가합니다.
첫 번째 transcendental전의 임의의 ordinal들은 그 이전의 ordinal들에 대해 algebraic합니다. 따라서 induction에 의해 field $(2, \oplus, \otimes)$위에서 algebraic합니다. 또한, 그러한 extension으로 얻어진 임의의 finite ordinal들은 모두 field를 이룹니다. 그리고 그러한 ordinal들은 $\Delta$자신이 $(\Delta, \oplus, \otimes)$의 algebraic extension을 정의합니다. 현재 extension은 사전순 가장 작은 polynomial에 의해서만 일어나며, 임의의 finite field의 Galois group은 commutative함에 주목합니다. 일단, 처음 일부의 extension들은 모두 quadratic extension입니다. 그 후 field는 모두 quadratically closed되어 있으므로 이후 일부의 extension들은 모두 cubic extension이고, 이후로는 quintic, … 이런 식으로 extension이 일어나게 됩니다.
또한, 임의의 finite field of characteristic 2의 원소는 square root를 가지므로, quadratic extension은 항상 $X ^ \underline{2} \oplus X = a$꼴의 polynomial에 의해서만 일어납니다. 그리고 임의의 odd prime $p$에 대하여 finite field extension of degree $p$ and characteristic 2는 항상 $p$-th root에 의해 일어나게 할 수 있으므로, 이후의 extension은 항상 $X ^ \underline{p} = a$꼴의 polynomial에 의해서만 일어납니다.
THEOREM
임의의 finite ordinal $a$에 대하여, $(a, \oplus, \otimes)$가 field일 필요충분조건은 $a$가 Fermat 2-power인 것이다. 또한, $a \otimes a = a / 2 \cdot 3$가 성립한다.
PROOF
어떤 finite ordinal $n$에 대하여 $(a = 2 ^ {2 ^ n}, \oplus, \otimes)$가 field이고 $P(X) = X ^ \underline2 \oplus X$가 $X = 0, \cdots, a - 1$에 대하여 $0, 1, \cdots a / 2 - 1$의 값들을 갖는다고 가정합시다. 가정으로부터 사전순 가장 작은 irreducible polynomial은 $Q(X) = P(X) \oplus (a / 2)$임을 알 수 있습니다. 따라서
$P(a) \oplus (a / 2) = 0 \leftrightarrow a \otimes a = a \oplus (a / 2) = a / 2 \cdot 3$
가 성립하며 $a$보다 큰 가장 작은 field는 $a ^ 2$입니다.
$a ^ 2$의 임의의 원소는 임의의 $\alpha, \beta \in a$에 대하여 $(a \otimes \alpha) \oplus \beta$꼴의 형태를 갖습니다.
$\begin{align} P((a \otimes \alpha) \oplus \beta) &= (a \otimes a \otimes \alpha \otimes \alpha) \oplus (\beta \otimes \beta) \oplus (a \otimes \alpha) \oplus \beta \newline &= (a \otimes P(\alpha)) \oplus (((a / 2) \otimes \alpha ^ \underline2) \oplus P(\beta)) \end{align}$
이 때, $P(\alpha) = P(\alpha \oplus 1)$임에 주목합니다. $P(\alpha)$와 $P(\beta)$는 $0, 1, \cdots, a / 2 - 1$의 값들을 가질 수 있으며, $(a / 2) \otimes \alpha ^ \underline2$는 $P(\alpha)$값을 변화시키지 않은 채로 $a / 2$만큼 변화를 줄 수 있습니다. 따라서 $P((a \otimes \alpha) \oplus \beta)$는 $0, 1, \cdots , a ^ 2 / 2 - 1$의 모든 값을 가질 수 있으며, induction hypothesis에 의해 증명이 완료됩니다.
$\blacksquare$
위 정리에 의해 흔히 알려진 nim multiplication의 계산공식이 증명됩니다.
이제 $(\omega, \oplus, \otimes)$가 $(2, \oplus, \otimes)$의 quadratic closure임을 알고 있습니다. 따라서 $\omega$는 cubic root를 갖지 않는 가장 작은 finite ordinal의 cubic root가 됩니다. $2$가 finite ordinal을 cubic root로 갖는다면, 그 cubic root의 order는 9가 되는데, 9는 “Fermat prime minus one”형태의 수를 나누지 않습니다. 따라서
$\omega \otimes \omega \otimes \omega = \omega ^ \underline3 = 2$
입니다. 이러한 cubic extension을 반복하면 다음의 ordinal sequence가 얻어집니다.
$2, \omega, \omega ^ 3, \omega ^ 9, \omega ^ {27}, \omega ^ {81}, \cdots$
가장 놀라운 점은 각 non-zero finite ordinal $n$에 대하여, $n$번째 항의 cube를 취하면 $n-1$번째 항이 된다는 것입니다. (반대가 아닙니다!!)
마찬가지로
$4, \omega ^ \omega, \omega ^ {\omega \cdot 5}, \omega ^ {\omega \cdot 25}, \omega ^ {\omega \cdot 125}, \omega ^ {\omega \cdot 625}, \cdots$
에서 각 항의 fifth power가 정확히 그 이전 항이 되고
$\omega + 1, \omega ^ {\omega ^ 2}, \omega ^ {\omega ^ 2 \cdot 7}, \omega ^ {\omega ^ 2 \cdot 49}, \omega ^ {\omega ^ 2 \cdot 343}, \omega ^ {\omega ^ 2 \cdot 2401}, \cdots$
에서 각 항의 seventh power가 정확히 그 이전 항이 됩니다.
일반적으로, $p$가 $k+1$번째 odd prime이면, $(\omega ^ {\omega ^ k}, \oplus, \otimes)$안에서 $p$-th root를 갖지 않는 최소의 ordinal을 $\alpha _ p$라 할 때,
$\alpha _ p, \omega ^ {\omega ^ k}, \omega ^ {\omega ^ k \cdot p}, \omega ^ {\omega ^ k \cdot p ^ 2}, \omega ^ {\omega ^ k \cdot p ^ 3}, \omega ^ {\omega ^ k \cdot p ^ 4}, \cdots$
에서 각 항의 $p$-th power가 정확히 그 이전 항이 됩니다.
이렇게 모든 prime에 대한 closure를 취하면 가장 작은 algebraically closed field $(\omega ^ {\omega ^ \omega}, \oplus, \otimes)$가 얻어집니다. 즉, $\omega ^ {\omega ^ \omega}$는 가장 작은 transcendental입니다. 다음으로 가장 작은 ring은 $(\omega ^ {\omega ^ \omega \cdot \omega}, \oplus, \otimes)$인데, $\omega ^ {\omega ^ \omega}$가 invertible하지 않으므로 field는 아닙니다. 다음으로 가장 작은 field는 $(\omega ^ {\omega ^ {\omega ^ \omega}}, \oplus, \otimes)$에서 나타나며, 마찬가지로 이 field에 대한 algebraic closure를 $\Omega$의 subset으로써 찾을 수 있습니다.
위 과정에서 임의의 ordinal polynomial를 linear factor들로 분해할 수 있으며, 결국 $(\Omega, \oplus, \otimes)$는 algebraically closed field가 됩니다.