不动点

在数学中，函数的不动点（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}$ 的递增函数．由于前者一般无不动点（即使有也是平凡的，如 $f(x)=x$），因而只有后者的不动点是重要的．

例如 $f(x)=1+x$：

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

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

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

注意

1. 并非所有的 $\mathrm{O}\mathrm{r}\mathrm{d}\mathrm{\to }\mathrm{O}\mathrm{r}\mathrm{d}$ 的递增函数都存在不动点．如 $f(x)=x+1$，就不存在不动点．
2. $f(\alpha )$ 的不动点可以更清晰地写作 $\alpha \mapsto f(\alpha )$ 的不动点．
3. 一个序数函数可以存在不止一个不动点．如 ${\omega }^{\omega }\times m$ 是 $f(x)=\omega \times x$ 的第 $1+m$ 个不动点．

不动点与基本列

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

如果 $X$ 是其第 $m$ 个不动点，则 $\sup \{X+1,f(X+1),f(f(X+1)),f(f(f(X+1))),\cdots \}$ 是其第 $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$ 的第 $1+\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 函数的基本思路．