不动点：修订间差异

←上一编辑

可视化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），指的是在函数定义域内的某一个值，经过函数映射后的值还是其本身。
+在数学中，函数的不动点（fixed point, fp），指的是在函数定义域内的某一个值，经过函数映射后的值还是其本身．
-== 例子 ==
-在[[Googology|googology]]中，我们一般只关心<math>\mathbb N \rightarrow \mathbb N</math>的连续递增函数以及<math>\rm{Ord \rightarrow Ord}</math>的连续递增函数。由于前者一般无不动点(即使有也是平凡的，如<math>\rm{f(x)=x}</math>)，因而只有后者的不动点是重要的。
-如<math>\rm{f(x)=1+x}</math>
+=== 例子 ===
+在 [[googology]] 中，我们一般只关心 <math>\mathbb N \rightarrow \mathbb N</math> 的递增函数以及 <math>\rm{Ord \rightarrow Ord}</math> 的递增函数．由于前者一般无不动点（即使有也是平凡的，如 <math>f(x)=x</math>），因而只有后者的不动点是重要的．
-注意到当<math>\rm{x=\omega}</math>时，<math>\rm{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)=1+x</math>：
-又如<math>f(x)=\omega \times 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>\rm{x=\omega^{\omega}}</math>时，<math>\rm{f(\omega^{\omega})=\omega^{\omega}}</math>，因此<math>\omega^{\omega}</math>是<math>f(x)=\omega \times 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> 的不动点．
-# 并非所有的Ord→Ord的连续递增函数都存在不动点。如f(x)=x+1,就不存在不动点。
+=== 注意 ===
-# 在googology中，我们一般把f(α)的不动点写作α→f(α)不动点。
+# 并非所有的 <math>\rm{Ord \rightarrow Ord}</math> 的递增函数都存在不动点．如 <math>f(x)=x+1</math>，就不存在不动点．
-# 一个序数函数可以不只存在一个不动点。如<math>\omega^{\omega}\times m</math>是<math>f(x)=\omega \times x</math>的第m个不动点。
+# <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>的连续递增函数f(x)<math>f(x)</math>且满足f(x)≥x<math>\rm{f(x)\geq x}</math>，存在这样一个定理：
+<math>\rm{Ord \rightarrow Ord}</math> 的连续递增函数 <math>f(x)</math> 且满足 <math>f(x)\ge x</math>，存在这样一个定理：
-如果X是其第m个不动点，则<math>\rm{sup \{ X+1.f(X+1),f(f(X+1)),f(f(f(X+1))),\cdots \}}</math>是其第m+1个不动点
+如果 <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 函数]]的基本思路．
-注意到这实际上提供了一种[[基本列]]选取的方法。实际上，著名的序数表示法[[veblen函数]]的强度就高度依赖于不动点.
 [[分类:入门]]
+[[分类:重要概念]]