不动点：修订间差异

←上一编辑

可视化wikitext

2025年8月25日 (一) 13:25的最新版本

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

例子

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

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

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

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

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

注意

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

不动点与基本列

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

如果 $X$ 是其第 $m$ 个不动点，则 $\sup {X + 1, f (X + 1), f (f (X + 1)), f (f (f (X + 1))), \dots}$ 是其第 $m + 1$ 个不动点．

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

相关结论及证明

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

单调不减：对任意两个序数 $α < β$ ，有 $f (α) \leq f (β)$ ．
对任意序数 $α$ ，有 $f (α) \geq α$ ．
连续性．对任意递增序数列 $α_{1}, α_{2}, \dots$ ，记 $α = \sup {α_{1}, α_{2}, \dots}$ ，则有 $f (α) = \sup {f (α_{1}), f (α_{2}), \dots}$ ．

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

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

$g (0) = \sup {0, f (0), f (f (0)), \dots} = \sup {f^{n} (0) ∣ n \in ℕ}$ ．
$g (α + 1) = \sup {f^{n} (g (α) + 1) ∣ n \in ℕ}$ ．
$g (α) = \sup {g (β) ∣ β < α}$ ，其中 $α$ 是极限序数．

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

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

命题 1： $g (0)$ 是 $f$ 的最小不动点．

证明：反证．设 $β < g (0)$ 是 $f$ 的不动点．

根据 $g (0)$ 的定义，存在 $n \in ℕ$ 使得 $f^{n} (0) > β$ ，不妨设这样的 $n$ 是最小的．

因为 $f^{0} (0) = 0 \leq β$ ，所以 $n > 0$ ．

那么有 $f^{n - 1} (0) \leq β = f (β) < f^{n} (0)$ ，这与 $f$ 的单调不减性矛盾．

所以 $g (0)$ 是 $f$ 的最小不动点．

命题 2： $g (α), g (α + 1)$ 之间没有其他 $f$ 的不动点．

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

设 $g (α) < β < g (α + 1)$ ，其中 $β$ 是 $f$ 的不动点．

因为 $g (α) + 1 \leq β$ ，所以 $f^{n} (g (α) + 1) \leq f^{n} (β) = β$ ．

所以 $g (α + 1) = \sup {f^{n} (g (α) + 1) ∣ n \in ℕ} \leq β$ ，矛盾．

所以 $g (α), g (α + 1)$ 之间没有其他 $f$ 的不动点．

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

@@ 第1行： / 第1行： @@
 在数学中，函数的不动点（fixed point, fp），指的是在函数定义域内的某一个值，经过函数映射后的值还是其本身．
-== 例子 ==
-在 [[Googology|googology]] 中，我们一般只关心 <math>\mathbb N \rightarrow \mathbb N</math> 的递增函数以及 <math>\rm{Ord \rightarrow Ord}</math> 的递增函数．由于前者一般无不动点（即使有也是平凡的，如 <math>f(x)=x</math>），因而只有后者的不动点是重要的．
+=== 例子 ===
+在 [[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>：
@@ 第11行： / 第12行： @@
 当 <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函数]]的强度就高度依赖于不动点．
+注意到这实际上提供了一种[[基本列]]选取的方法．实际上，著名的序数表示法 [[Veblen 函数]]的强度就高度依赖于不动点．
-== 相关结论及证明 ==
+=== 相关结论及证明 ===
 对于满足如下条件的序数函数 <math>f:\mathrm{Ord}\to\mathrm{Ord}</math>，其不动点呈现出许多良好的性质．
@@ 第44行： / 第43行： @@
 下面证明：<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(0)</math> 是 <math>f</math> 的最小不动点．
- 证明：与命题 1 思路类似，使用反证法．
- 设 <math>g(\alpha)<\beta<g(\alpha+1)</math>，其中 <math>\beta</math> 是 <math>f</math> 的不动点．
+'''证明'''：反证．设 <math>\beta<g(0)</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(0)</math> 的定义，存在 <math>n\in\N</math> 使得 <math>f^n(0)>\beta</math>，不妨设这样的 <math>n</math> 是最小的．
- 所以 <math>g(\alpha),g(\alpha+1)</math> 之间没有其他 <math>f</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函数]]的基本思路．
+实际上，由此定义出的序数函数 <math>g</math>，同样满足上述三条性质，因此可以继续讨论 <math>g</math> 的不动点．这就是 [[Veblen 函数]]的基本思路．
 [[分类:入门]]
+[[分类:重要概念]]