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

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

=== 例子 ===
在 [[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 函数]]的基本思路．

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