查看“︁不动点”︁的源代码

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

=== 例子 ===
在 [[Googology|googology]] 中，我们一般只关心 <math>\mathbb N \rightarrow \mathbb N</math> 的递增函数以及 <math>\rm{Ord \rightarrow Ord}</math> 的递增函数．由于前者一般无不动点（即使有也是平凡的，如 <math>f(x)=x</math>），因而只有后者的不动点是重要的．

例如 <math>f(x)=1+x</math>：

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

又如 <math>f(x)=\omega \times x</math>：

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

=== 注意 ===
# 并非所有的 <math>\rm{Ord \rightarrow Ord}</math> 的递增函数都存在不动点．如 <math>f(x)=x+1</math>，就不存在不动点．
# <math>f(\alpha)</math> 的不动点可以更清晰地写作 <math>\alpha\mapsto f(\alpha)</math> 的不动点．
# 一个序数函数可以存在不止一个不动点．如 <math>\omega^{\omega}\times m</math> 是 <math>f(x)=\omega \times x</math> 的第 <math>1+m</math> 个不动点．

=== 不动点与基本列 ===
<math>\rm{Ord \rightarrow Ord}</math> 的连续递增函数 <math>f(x)</math> 且满足 <math>f(x)\ge x</math>，存在这样一个定理：

如果 <math>X</math> 是其第 <math>m</math> 个不动点，则 <math>\sup \{ X+1,f(X+1),f(f(X+1)),f(f(f(X+1))),\cdots \}</math> 是其第 <math>m+1</math> 个不动点．

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

=== 相关结论及证明 ===
对于满足如下条件的序数函数 <math>f:\mathrm{Ord}\to\mathrm{Ord}</math>，其不动点呈现出许多良好的性质．

* 单调不减：对任意两个序数 <math>\alpha<\beta</math>，有 <math>f(\alpha)\le f(\beta)</math>．
* 对任意序数 <math>\alpha</math>，有 <math>f(\alpha)\ge\alpha</math>．
* 连续性．对任意递增序数列 <math>\alpha_1,\alpha_2,\cdots</math>，记 <math>\alpha=\sup\{\alpha_1,\alpha_2,\cdots\}</math>，则有 <math>f(\alpha)=\sup\{f(\alpha_1),f(\alpha_2),\cdots\}</math>．

另外，若 <math>f</math> 严格递增，则 <math>f</math> 自动满足前两条性质．

若 <math>f</math> 满足如上条件，那么就可以定义序数函数 <math>g:\mathrm{Ord}\to\mathrm{Ord}</math>，使得 <math>g(\alpha)</math> 表示 <math>f</math> 的第 <math>1+\alpha</math> 个不动点．具体定义为

* <math>g(0)=\sup\{0,f(0),f(f(0)),\cdots\}=\sup\{f^n(0)\mid n\in\N\}</math>．
* <math>g(\alpha+1)=\sup\{f^n(g(\alpha)+1)\mid n\in\N\}</math>．
* <math>g(\alpha)=\sup\{g(\beta)\mid\beta<\alpha\}</math>，其中 <math>\alpha</math> 是[[序数#极限序数|极限序数]]．

从定义中不难看出，对任意序数 <math>\alpha</math>，<math>g(\alpha)</math> 总是 <math>f</math> 的不动点．

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


'''命题 1'''：<math>g(0)</math> 是 <math>f</math> 的最小不动点．

'''证明'''：反证．设 <math>\beta<g(0)</math> 是 <math>f</math> 的不动点．

根据 <math>g(0)</math> 的定义，存在 <math>n\in\N</math> 使得 <math>f^n(0)>\beta</math>，不妨设这样的 <math>n</math> 是最小的．

因为 <math>f^0(0)=0\le\beta</math>，所以 <math>n>0</math>．

那么有 <math>f^{n-1}(0)\le\beta=f(\beta)<f^n(0)</math>，这与 <math>f</math> 的单调不减性矛盾．

所以 <math>g(0)</math> 是 <math>f</math> 的最小不动点．


'''命题 2'''：<math>g(\alpha),g(\alpha+1)</math> 之间没有其他 <math>f</math> 的不动点．

'''证明'''：与命题 1 思路类似，使用反证法．

设 <math>g(\alpha)<\beta<g(\alpha+1)</math>，其中 <math>\beta</math> 是 <math>f</math> 的不动点．

因为 <math>g(\alpha)+1\le\beta</math>，所以 <math>f^n(g(\alpha)+1)\le f^n(\beta)=\beta</math>．

所以 <math>g(\alpha+1)=\sup\{f^n(g(\alpha)+1)\mid n\in\N\}\le\beta</math>，矛盾．

所以 <math>g(\alpha),g(\alpha+1)</math> 之间没有其他 <math>f</math> 的不动点．


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

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

==== 前置定义：正规函数 ====
在ZFC中，<math>\mathrm{Ord}</math>表示全体序数构成的真类，我们讨论的核心对象是正规函数（normal function），即满足以下两条性质的类函数<math>f:\mathrm{Ord}\to\mathrm{Ord}</math>：
# 严格递增性：对任意序数<math>\alpha < \beta</math>，有<math>f(\alpha) < f(\beta)</math>
# 连续性（保上确界）：对任意[[序数#极限序数|极限序数]]<math>\lambda</math>，有<math>f(\lambda) = \sup\{ f(\xi) \mid \xi < \lambda \}</math>

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

==== 不动点的形式化定义 ====
对于序数函数<math>f:\mathrm{Ord}\to\mathrm{Ord}</math>，序数<math>\alpha</math>称为<math>f</math>的不动点（fixed point, fp），当且仅当
<math>f(\alpha) = \alpha</math>

我们用<math>\operatorname{Fix}(f)</math>表示<math>f</math>的全体不动点构成的类，其形式化定义为
<math>\operatorname{Fix}(f) = \{ \alpha \in \mathrm{Ord} \mid f(\alpha) = \alpha \}</math>

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

1. 无界性：<math>\operatorname{Fix}(f)</math>是<math>\mathrm{Ord}</math>中的无界类，即对任意序数<math>\beta</math>，总存在序数<math>\alpha > \beta</math>，使得<math>\alpha \in \operatorname{Fix}(f)</math>。

2. 闭性：<math>\operatorname{Fix}(f)</math>是<math>\mathrm{Ord}</math>中的闭类，即对任意极限序数<math>\lambda</math>，若<math>\{ \alpha_\xi \mid \xi < \lambda \} \subseteq \operatorname{Fix}(f)</math>是递增序数序列，则
<math>\sup_{\xi < \lambda} \alpha_\xi \in \operatorname{Fix}(f)</math>
满足闭性与无界性的类称为闭无界类（club class），因此正规函数的不动点类是<math>\mathrm{Ord}</math>中的闭无界类。

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

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

1. ε-数：指数函数<math>f(\alpha) = \omega^\alpha</math>的不动点，即满足<math>\varepsilon = \omega^\varepsilon</math>的序数，其枚举函数记为<math>\varepsilon_\alpha</math>，最小的ε-数为
<math>\varepsilon_0 = \sup\{ 0, \omega, \omega^\omega, \omega^{\omega^\omega}, \dots \}</math>
<math>\varepsilon_0 = \sup\{ f^n(0) \mid n \in \mathbb{N} \}</math>

2. 阿列夫不动点：阿列夫基数枚举函数<math>f(\alpha) = \aleph_\alpha</math>的不动点，即满足<math>\kappa = \aleph_\kappa</math>的基数，最小的阿列夫不动点为
<math>\kappa_0 = \sup\{ \aleph_0, \aleph_{\aleph_0}, \aleph_{\aleph_{\aleph_0}}, \dots \}</math>
<math>\kappa_0 = \sup\{ f^n(0) \mid n \in \mathbb{N} \}</math>

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


[[分类:入门]]
[[分类:重要概念]]