上一篇日志的延续——塔斯基不动点定理的证明
2013-02-19 17:34阅读：
本文给出塔斯基不动点定理的一个证明。我们分如下几步进行：
1，定义：我们称 <A,≤> 是一个完备格
当且仅当 <A,≤> 是一个（非严格）偏序并且 A 的每个子集都有上确界。
事实上，对于任何偏序 <A,≤> ， A 的每个子集都有上确界
当且仅当 A 的每个子集都有下确界。
2，定义：设 <A,≤> 是偏序。函数 f:A→A 称为
<A,≤> 上的单调函数 当且仅当 对所有的 x、y ∈ A ，x≤y 蕴含 f(x)≤f(y)
。
3，引理：设 <A,≤> 是完备格， f:A→A
是 <A,≤> 上的单调函数。我们有：
（1）对所有的 a、b∈A ，若 a ≤ b ，则 < [ a , b ] , ≤
> 也是一个完备格。其中，[ a , b ] = { x∈A | a ≤ x ≤ b
} 。
（2）对所有的 a、b∈A ，若 a ≤ b 、a ≤ f(a) 、f(b) ≤ b ，则 f |
[ a , b ] 是 < [ a , b ] , ≤ >
上的单调函数。其中， f | [ a , b ] 表示函数 f 在 [ a , b ]
上的限制。
证明：显然成立。
4，引理：若 <A,≤> 是完备格， f:A→A
是 <A,≤> 上的单调函数，则 f 有一个最大的不动点和一
个最小的不动点。
这个引理是整个定理证明的关键，它的证明将在文章最后以“附注”的形式用两种方法证明。
5，塔斯基不动点定理：每个完备格 <A,≤> 上的单调函数 f
都有不动点（即使得 f(x)=x 的点 x ），并且 f 的全体不动点在 ≤
下也形成一个完备格。
证明：分如下几步：
5.1，由引理 4 ，我们知道函数 f 存在一个不动点。
5.2，设 f 的所有不动点的集合是 B ，我们证明 <B,≤> 是一个完备格。
按照定义 1 ，因为显然 <B,≤> 是偏序，我们只需证明 B 的每个子集 C 在 B
中有上确界。
5.3，我们取 a 为 C 在 A 中的上确界，取 b 为 A 的最大元（即 A 在 A
中的上确界）。
因为对每一个 x ∈C ，f(a) = f(sup C) ≥ f(x) = x，所以 f(a) 是 C
的上界。从而 f(a) ≥ sup C = a 。
而显然 f(b) ≤ b ，所以按照引理 3 ， f | [ a ,b ] 是完备格 <
[ a , b ] , ≤ > 上的单调函数。
按照引理 4 ，f | [ a , b ] 在 <
[ a , b ] , ≤ > 上有一个最小的不动点，这个不动点就是 f 的 ≥ a
的最小不动点，即 f 的 ≥ C 中每个元素的最小不动点，从而是 C 在 B
中的上确界。
证毕。
6，附注：这里我们给出引理 4 的两种证法：
6.1，第一种证法：
设 <A,≤> 是完备格， f:A→A 是 <A,≤>
上的单调函数。
我们令 D = { x ∈ A | x ≤ f(x) } ， E = { x ∈ A | x ≥ f(x)
} 。设 B 是 f 的所有不动点的集合。
取 d 为 D 的上确界，那么我们有：对每一个 x ∈ D ，f(d) = f(sup D) ≥ f(x) ≥ x 。所以
f(d) 是 D 的上界。从而 f(d) ≥ d ，即 d ∈ D 。D 有属于自身的上确界 d ，所以 d 是 D
中的最大元。
另一方面，因为 f(d) ≥ d ，利用 f 的单调性，有 f(f(d)) ≥ f(d) ，即 f(d) ∈
D 。而 d 是 D 的最大元，故 d ≥ f(d)。结合 f(d) ≥ d 我们有 f(d)=d ，即 d 是 f
的一个不动点，d ∈ B 。
由于 B ⊆ D，所以 D 的最大元 d 也是 B 的最大元。即 f 有最大不动点，这个最大不动点就是 D
的上确界。
同理可证 E 的下确界是 f 的最小不动点。证毕。
6.2，第二种证法：（本证法需要一些集合论中关于序数的知识）
设 a 为 A 的最小元（即 A 在 A 中的下确界）。
超穷递归定义一个序数宇宙 On 上的类函数 G ：
F(0) = a ，
F(β+1) = f(F(β)) ，
F(λ) = sup { F(δ) | δ < λ } ，对每个极限序数
λ 。
用归纳法容易证明 F 是非严格递增的。
如果 F 严格递增，那么 F 就是一个从序数宇宙 On 到集合 A
的单的（即一对一的）类函数，这意味着 On
也是集合（注意这个推理使用了替换公理）。与著名的康托定理（On
是真类）矛盾。
所以 F 一定不是严格递增的，即存在一个序数 η ，使得 F(η+1) =
F(η) 。即 f(F(η)) = F(η) ，即 F(η) 是 f
的一个不动点。
我们设 e = F(η) ，并证明 e 是 f 的最小不动点：
对 f 的每个不动点 x ，因为 a ≤ x ，用归纳法很容易证明对每个序数 β ，F(β) ≤ x 。所以
e = F(η) ≤ x 。
同理从 A 最大元出发超穷递归定义一个非严格递降的类函数，我们可以找到 f 的最大不动点。
证毕。
整个证明用下图表现很是贴切：
其中 A 、B、D、E
的意义如证明中所定义。左边的箭头表示那个从最小元出发的非严格递增的类函数，而右边的箭头表示从最大元出发的非严格递降的类函数。
