序数 Nimber——ω^ω^ω之后的故事
zhuzhu2891
·
·
算法·理论
前情提要
本文主要介绍 \omega^{\omega^\omega} 及之后（我也不知道会写到哪里，现在到 \omega^{\omega^{\omega^\omega}}）的序数 Nimber 运算。
由于作者是 OIer （不会且懒得写证明），所以本文会主要以感性理解为主，不会很严谨，大家可以当乐子看。
本文中会以 集合/环/域 x 来表示由 <x 的所有序数组成的 集合/环/域。
本文中的幂次运算默认是普通幂次而非 Nimber 幂，且指数上使用。
一些重要的定理
定理 1.1： 域 \omega^{\omega^\omega} 代数闭（即代数基本定理成立）
证明：这个不是我应该写的，等 @Galois_Field_1048576 更新吧。
定理 1.2： 若集合 x 在加法下形成群，但存在 a,b<x 使 a\times b\ge x 则对于任何极小的这样的 a,b 都有 x=a\times b。
证明：这个 @Galois_Field_1048576 应该会写。
定理 1.3： 若环 x 中存在 a 使得在 x 中没有 a 的逆元，则对于最小的这样的 a 有 a\times x=1。
证明：虽然这个他用不到，但是 @Galois_Field_1048576 应该会写。
定理 1.4： 若域 x 中存在无解多项式方程，则对于字典序最小的无解多项式方程 a_0+a_1x+a_2x^2+\cdots=0 有 x 作为它的根。
证明：这个 @Galois_Field_1048576 应该会写。
定理 1.5： 对于域 x，以及 a<x 有 a\times x=[ax]。
证明：这个 @Galois_Field_1048576 应该会写。
让我们开始吧
以下均称 \omega^{\omega^\omega}=t。
定理 2.1： 对于任意非 0 且系数 \in t 的多项式函数 f(x)，均有 f(t)\neq 0。
证明：这个域代数基本定理成立，所以显然不可能有 t 作为它的根。
定理 2.2： t\times t=t^2。
证明：考察 t\times t\neq at+b 其中 a,b\in t，因此 (t,t) 是极小的 a,b<x 使 a\times b\ge t^2 由 1.2 知 t\times t=t^2
定理 2.3： t\times t^2=t^3。
证明：类似。
定理 2.3： t\times t^3=t^4。
证明：类似。
……
啊？
若无特殊说明，以下的 a,b,c 均为非负整数。
定理 3.1： t 在 t^{\omega} 下没有逆元。以及集合 t^{\omega} 是环。
证明：考虑这里的数都可以写成 t 的多项式，所以没有 t 的逆元。后一条显然。
定理 3.2： t^\omega\times t=1。
证明：由 1.3 显然。
定理 3.3： t^{\omega+1}=t^\omega\times t^\omega。
证明：由 1.2 显然。
定理 3.4： t^{\omega+a+1}\times t=t^{\omega+a}。
证明：由 1.2 显然。
定理 3.5： 集合 t^{2\omega} 也是环。
证明：显然。
定理 3.6： t^{2\omega}\times(t+1)=1。
证明：由 1.3 显然。
定理 3.7： 集合 t^{3\omega} 也是环。
证明：显然。 这个其实你仔细思考就会发现 t^{2\omega}\times t^\omega=\frac1t\times\frac1{t+1} 好像没出现啊？但是我们发现 \frac1t\times\frac1{t+1}=\frac1{t(t+1)}=\frac{t+(t+1)}{t(t+1)}=\frac1t+\frac1{t+1}。类似地，\frac1t\times\frac1{(t+1)^2}=\frac1t+\frac{t}{(t+1)^2}=\frac1t+\frac1{(t+1)^2}+\frac1{t+1}，类似内容还会出现在 4.1。
定理 3.8： t^{2\omega+a+1}\times(t+1)=t^{2\omega+a}。
证明：由 1.2 显然。
定理 3.9： t^{(b+1)\omega+a+1}\times(t+b)=t^{(b+1)\omega+a}，t^{(b+1)\omega}\times(t+b)=1
证明：显然。
定理 3.10： t^{(1\oplus c)\omega}\times(t+c)=1，以及 t^{(1\oplus c)\omega+a+1}\times(t+c)=t^{(1\oplus c)\omega+a}，这里的 \oplus 是序数上的非对称加法（就是强制展开右边的加法）。
证明：显然。
终于遇到域了
定理 4.1： 集合 t^{\omega^{\omega^{\omega}}}=\omega^{\omega^{\omega^{\omega}}} 是域。
证明：证明是环是容易的。首先证明对于 x<t^\omega 均有逆元，设 x=\prod_{i=1}^k(t+c_i)^{a_i}，则我们发现 \frac1x 可以写成 \frac1{c_i^{b}}（其中 1\le b\le a_i）的线性组合，于是有逆元，而对于许多分数的和的逆，考虑通分之后上下颠倒再进行一些计算即可得到它的逆元，因此这是域。
定理 4.2： \omega^{\omega^{\omega^{\omega}}}\times \omega^{\omega^{\omega^{\omega}}}=t。
证明：由 1.4 显然。
定理 4.3： 集合 (\omega^{\omega^{\omega^{\omega}}})^2=\omega^{2\omega^{\omega^{\omega}}} 是域。
证明：考虑 a+b\sqrt{t}\neq0（a,b<\omega^{\omega^{\omega^{\omega}}}）如何求逆，显然有 \frac1{a+b\sqrt{t}}=\frac{a+b\sqrt{t}}{a^2+tb^2}，显然分母非 0 且分母 <\omega^{\omega^{\omega^{\omega}}}，因此有逆元。
定理 4.4： (\omega^{\omega^{\omega^{\omega}}})^{2^n}=\sqrt[2^{n+1}]{t}。
证明：显然。
定理 4.5： (\omega^{\omega^{\omega^{\omega}}})^\omega 是 x^2+x=t 的根。
证明：首先考虑证明这个方程在 (\omega^{\omega^{\omega^{\omega}}})^\omega 下无解。考虑若有解，显然解 \ge t，然后显然解 \ge t^{\omega}（考虑次数最高项的显然它的平方没人跟它抵消）；然后若 t^{\omega}\le x<t^{\omega^{\omega^{\omega}}}，则将其分解为一堆分数后考虑分母次数最高的项，显然它的平方也没人跟它抵消；再否则它里面包含根号，考虑层数最多的项，显然它不会被 x^2 抵消，因此任何一个数都不是 x^2+x=t 的解。然后任何字典序比它小的多项式方程有解是显然的。（这个证明其实对于方程 x^2+x+at=0（a<t）都成立）
定理 4.6： 集合 (\omega^{\omega^{\omega^{\omega}}})^{2\omega} 是环。
证明：显然。
定理 4.7： 环 (\omega^{\omega^{\omega^{\omega}}})^{2\omega} 是域。
证明：显然。 这个证明还是需要少量脑洞的，称 y=(\omega^{\omega^{\omega^{\omega}}})^\omega，则 \frac1{ay+b}=\frac{ay+a+b}{(ay+b)(ay+a+b)}=\frac{ay+a+b}{ta+a^2+ab}。因此每个数都有逆元（a,b<y）。
定理 4.8： (\omega^{\omega^{\omega^{\omega}}})^{2\omega} 是 x^2+x=2t 的解。
证明：显然在 (\omega^{\omega^{\omega^{\omega}}})^{\omega} 下无解（证明与前面的类似）。然后若解 \ge (\omega^{\omega^{\omega^{\omega}}})^{\omega} 则设它为 \alpha y+\beta（y=(\omega^{\omega^{\omega^{\omega}}})^\omega），易知 \alpha=1，于是 \beta 是 x^2+x=3t 的解，易证这样的 \beta 不存在。然后任何字典序比它小的多项式方程有解是显然的。
定理 4.9： 集合 (\omega^{\omega^{\omega^{\omega}}})^{4\omega} 是域。
证明：类似 4.7。
定理 4.10： (\omega^{\omega^{\omega^{\omega}}})^{2^\alpha\omega}（\alpha<\omega^\omega）是 x^2+x+2^\alpha t=0 的解。
证明：类似 4.8。
定理 4.11： 我们会依照大小顺序逐个加入 x^2+x+v=0 的解，其中 v\in\{2^\alpha t^{2a+1},\frac{2^\alpha}{ (t+\beta)^{2a+1}}|\alpha<\omega^\omega,\beta<\omega^{\omega^\omega}\}（本集合目前不完善，会是接下来主要更新的内容，但我会尽可能保证集合恰好是应有的集合与集合 \gamma 的并（\gamma 是序数））
证明：在这里我只能证明我们干这件事是正确的，但是证明我正确地干了这件事实在是太繁琐了（所以咕掉）。
首先考虑每次加入一个解之后仍会形成一个域（参考 4.7），然后在这个域中每个数都有平方根（显然），因此接下来还是要加入 x^2+x+v=0 的根，至于 v 具体是什么，我认为是上面那个集合中未加入的最小序数。（这一点的正确性，也就是我是否正确地干了这件事，的证明，会十分繁琐（涉及到必要性与最小性的讨论，暂且不展开了））