不动点

在数学中，函数的不动点（fixed point,fp），指的是在函数定义域内的某一个值，经过函数映射后的值还是其本身。

例子

在googology中，我们一般只关心$\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$的连续递增函数以及$\mathrm{O}\mathrm{r}\mathrm{d}\mathrm{\to }\mathrm{O}\mathrm{r}\mathrm{d}$的连续递增函数。由于前者一般无不动点(即使有也是平凡的，如$\mathrm{f}\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{=}\mathrm{x}$)，因而只有后者的不动点是重要的。

如$\mathrm{f}\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{=}\mathrm{1}\mathrm{+}\mathrm{x}$

注意到当$\mathrm{x}\mathrm{=}\mathrm{\omega }$时，$\mathrm{f}\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{=}\mathrm{1}\mathrm{+}\mathrm{\omega }\mathrm{=}\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{\{}\mathrm{1}\mathrm{+}\mathrm{0},\mathrm{1}\mathrm{+}\mathrm{1},\mathrm{1}\mathrm{+}\mathrm{2},\mathrm{1}\mathrm{+}\mathrm{3},\mathrm{\cdots }\mathrm{\}}\mathrm{=}\mathrm{\omega }$。因此$\omega$是$\mathrm{f}\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{=}\mathrm{1}\mathrm{+}\mathrm{x}$的不动点。

又如$f(x)=\omega \times x$

当$\mathrm{x}\mathrm{=}{\mathrm{\omega }}^{\mathrm{\omega }}$时，$\mathrm{f}\mathrm{(}{\mathrm{\omega }}^{\mathrm{\omega }}\mathrm{)}\mathrm{=}{\mathrm{\omega }}^{\mathrm{\omega }}$，因此${\omega }^{\omega }$是$f(x)=\omega \times x$的不动点。

注意

1. 并非所有的Ord→Ord的连续递增函数都存在不动点。如f(x)=x+1,就不存在不动点。
2. 在googology中，我们一般把f(α)的不动点写作α→f(α)不动点。
3. 一个序数函数可以不只存在一个不动点。如${\omega }^{\omega }\times m$是$f(x)=\omega \times x$的第m个不动点。

不动点与基本列

$\mathrm{O}\mathrm{r}\mathrm{d}\mathrm{\to }\mathrm{O}\mathrm{r}\mathrm{d}$的连续递增函数f(x)$f(x)$且满足f(x)≥x$\mathrm{f}\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{\ge }\mathrm{x}$，存在这样一个定理：

如果X是其第m个不动点，则$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{\{}\mathrm{X}\mathrm{+}\mathrm{1}\mathrm{.}\mathrm{f}\mathrm{(}\mathrm{X}\mathrm{+}\mathrm{1}\mathrm{)},\mathrm{f}\mathrm{(}\mathrm{f}\mathrm{(}\mathrm{X}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{)},\mathrm{f}\mathrm{(}\mathrm{f}\mathrm{(}\mathrm{f}\mathrm{(}\mathrm{X}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{)}\mathrm{)},\mathrm{\cdots }\mathrm{\}}$是其第m+1个不动点

注意到这实际上提供了一种基本列选取的方法。实际上，著名的序数表示法veblen函数的强度就高度依赖于不动点.

相关结论及证明

对于满足如下条件的序数函数 $f:\mathrm{O}\mathrm{r}\mathrm{d}\to \mathrm{O}\mathrm{r}\mathrm{d}$，其不动点呈现出许多良好的性质.

• 单调不减：对任意两个序数 $\alpha <\beta$，有 $f(\alpha )\le f(\beta )$.
• 对任意序数 $\alpha$，有 $f(\alpha )\ge \alpha$.
• 连续性. 对任意递增序数列 ${\alpha }_1,{\alpha }_2,\cdots$，记 $\alpha =\sup \{{\alpha }_1,{\alpha }_2,\cdots \}$，则有

$f(\alpha )=\sup \{f({\alpha }_1),f({\alpha }_2),\cdots \}$

另外，若 $f$ 严格递增，则 $f$ 自动满足前两条性质.

若 $f$ 满足如上条件，那么就可以定义序数函数 $g:\mathrm{O}\mathrm{r}\mathrm{d}\to \mathrm{O}\mathrm{r}\mathrm{d}$，使得 $g(\alpha )$ 表示 $f$ 的第 $\alpha$ 个不动点. 具体定义为

• $g(0)=\sup \{0,f(0),f(f(0)),\cdots \}=\sup \{f^n(0)\mid n\in \mathbb{\mathbb{N}}\}$
• $g(\alpha +1)=\sup \{f^n(g(\alpha )+1)\mid n\in \mathbb{\mathbb{N}}\}$
• $g(\alpha )=\sup \{g(\beta )\mid \beta <\alpha \}$，其中 $\alpha$ 是极限序数.

从定义中不难看出，对任意序数 $\alpha$，$g(\alpha )$ 总是 $f$ 的不动点.

下面证明：$g(0)$ 是 $f$ 的最小不动点；$g(\alpha ),g(\alpha +1)$ 之间没有其他 $f$ 的不动点.

命题 1：$g(0)$ 是 $f$ 的最小不动点.
证明：反证. 设 $\beta <g(0)$ 是 $f$ 的不动点. 
根据 $g(0)$ 的定义，存在 $n\in \mathbb{\mathbb{N}}$ 使得 $f^n(0)>\beta$，不妨设这样的 $n$ 是最小的.
因为 $f^0(0)=0\le \beta$，所以 $n>0$.
那么有 $f^{n-1}(0)\le \beta =f(\beta )<f^n(0)$，这与 $f$ 的单调不减性矛盾.
所以 $g(0)$ 是 $f$ 的最小不动点.

命题 2：$g(\alpha ),g(\alpha +1)$ 之间没有其他 $f$ 的不动点.
证明：与命题 1 思路类似，使用反证法.
设 $g(\alpha )<\beta <g(\alpha +1)$，其中 $\beta$ 是 $f$ 的不动点.
因为 $g(\alpha )+1\le \beta$，所以 $f^n(g(\alpha )+1)\le f^n(\beta )=\beta$.
所以 $g(\alpha +1)=\sup \{f^n(g(\alpha )+1)\mid n\in \mathbb{\mathbb{N}}\}\le \beta$，矛盾.
所以 $g(\alpha ),g(\alpha +1)$ 之间没有其他 $f$ 的不动点.

实际上，由此定义出的序数函数 $g$，同样满足上述三条性质，因此可以继续讨论 $g$ 的不动点. 这就是Veblen函数的基本思路.