不动点

在数学中，函数的不动点（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 函数的基本思路．

集合论（ZFC）中的形式化定义

在ZFC公理集合论框架下，我们可以给出序数不动点的严格形式化定义与性质

前置定义：正规函数

在ZFC中，$\mathrm{O}\mathrm{r}\mathrm{d}$表示全体序数构成的真类，我们讨论的核心对象是正规函数（normal function），即满足以下两条性质的类函数$f:\mathrm{O}\mathrm{r}\mathrm{d}\to \mathrm{O}\mathrm{r}\mathrm{d}$：

1. 严格递增性：对任意序数$\alpha <\beta$，有$f(\alpha )<f(\beta )$
2. 连续性（保上确界）：对任意极限序数$\lambda$，有$f(\lambda )=\sup \{f(\xi )\mid \xi <\lambda \}$

正规函数具有基础性质：对任意序数$\alpha$，必有$f(\alpha )\ge \alpha$，与前文给出的条件完全一致。同时需注意，不满足连续性的严格递增序数函数不一定存在不动点（例如$f(\alpha )=\alpha +1$），与前文的注意事项对应。

不动点的形式化定义

对于序数函数$f:\mathrm{O}\mathrm{r}\mathrm{d}\to \mathrm{O}\mathrm{r}\mathrm{d}$，序数$\alpha$称为$f$的不动点（fixed point, fp），当且仅当 $f(\alpha )=\alpha$

我们用$\mathrm{Fix}(f)$表示$f$的全体不动点构成的类，其形式化定义为 $\mathrm{Fix}(f)=\{\alpha \in \mathrm{O}\mathrm{r}\mathrm{d}\mid f(\alpha )=\alpha \}$

正规函数的不动点核心定理

对于任意正规函数$f$，其不动点类$\mathrm{Fix}(f)$具有以下核心性质，这些性质构成了不动点迭代构造的公理化基础：

1. 无界性：$\mathrm{Fix}(f)$是$\mathrm{O}\mathrm{r}\mathrm{d}$中的无界类，即对任意序数$\beta$，总存在序数$\alpha >\beta$，使得$\alpha \in \mathrm{Fix}(f)$。

2. 闭性：$\mathrm{Fix}(f)$是$\mathrm{O}\mathrm{r}\mathrm{d}$中的闭类，即对任意极限序数$\lambda$，若$\{{\alpha }_{\xi }\mid \xi <\lambda \}\subseteq \mathrm{Fix}(f)$是递增序数序列，则 $\underset{\xi <\lambda }{\sup }{\alpha }_{\xi }\in \mathrm{Fix}(f)$ 满足闭性与无界性的类称为闭无界类（club class），因此正规函数的不动点类是$\mathrm{O}\mathrm{r}\mathrm{d}$中的闭无界类。

3. 不动点枚举的正规性：按递增顺序枚举$f$的不动点的函数$g:\mathrm{O}\mathrm{r}\mathrm{d}\to \mathrm{O}\mathrm{r}\mathrm{d}$（即前文定义的、$g(\alpha )$为$f$的第$1+\alpha$个不动点的函数），本身也是正规函数。这一性质是Veblen 函数迭代构造高阶不动点的核心基础。

经典不动点类的形式化例子

1. ε-数：指数函数$f(\alpha )={\omega }^{\alpha }$的不动点，即满足$\epsilon ={\omega }^{\epsilon }$的序数，其枚举函数记为${\epsilon }_{\alpha }$，最小的ε-数为 ${\epsilon }_0=\sup \{0,\omega ,{\omega }^{\omega },{\omega }^{{\omega }^{\omega }},\dots \}$ ${\epsilon }_0=\sup \{f^n(0)\mid n\in \mathbb{\mathbb{N}}\}$

2. 阿列夫不动点：阿列夫基数枚举函数$f(\alpha )={\mathrm{\aleph }}_{\alpha }$的不动点，即满足$\kappa ={\mathrm{\aleph }}_{\kappa }$的基数，最小的阿列夫不动点为 ${\kappa }_0=\sup \{{\mathrm{\aleph }}_0,{\mathrm{\aleph }}_{{\mathrm{\aleph }}_0},{\mathrm{\aleph }}_{{\mathrm{\aleph }}_{{\mathrm{\aleph }}_0}},\dots \}$ ${\kappa }_0=\sup \{f^n(0)\mid n\in \mathbb{\mathbb{N}}\}$

3. 加法不动点：左加1函数$f(\alpha )=1+\alpha$的不动点，所有大于等于$\omega$的极限序数均为其不动点。