不动点定理

基本定义

偏序集

定义（偏序集） 设 为一个集合， 为 上的二元关系。若满足：

• 自反性

• 反对称性

• 传递性

则称 为一个偏序集 (partially ordered set, poset)。

上界与上确界

定义（上界） 设 ，。如果 ，则称 为 的上界。

定义（上确界） 若 是 的上界，且对任意上界 有 ，则称 为 的上确界 (least upper bound, or supremum)，记作 。

类似地，可以定义下界与下确界。 的下确界用 表示。

完备格

定义（格） 偏序集 称为格，若任意 都存在上确界 和下确界 。

定义（完备格） 偏序集 称为完备格，若对任意子集 都存在 和 。 特别地，

分别称为最小元与最大元。

单调函数

定义（单调函数） 对于偏序集 ，函数 称为单调的，若

不动点

定义（不动点） 若 ，则称 为 的不动点。 记

Knaster–Tarski 不动点定理

定理（Knaster–Tarski 不动点定理） 设 为完备格， 为单调函数。则 的所有不动点 关于 也构成一个完备格，而且满足：

• 存在最小不动点:
• 存在最大不动点:

特别地，上述定理蕴含了 至少存在一个不动点，因为完备格至少包含一个元素。

证明

先证明 有最大元素。设 。完备格 的最小元素 满足 ，因此 ，因此 非空。

对任意 ，根据 的定义，我们有 。因为 是单调的，我们有 ，即 。

取 （因为 是完备格 的子集，所以 存在）。 对于任意 ，我们有 和 ，因此 。因此， 是 的一个上界，但 是 的最小上界，所以 ，即 。因为 ，所以 ，因此 ，从而得到 。因为每个不动点都在 中，所以 是 的最大不动点。

函数 在对偶（完备）格 上也是单调的。 因此，将上述证明应用在对偶格上，我们就能得到 的最小不动点存在。

综上所述， 有最小元素和最大元素，即每个完备格上的单调函数都有最小不动点和最大不动点。

我们知道：对于完备格 和任意 ，以 和 为界的闭区间 关于 也是一个完备格。

接下来需要证明 是一个完备格。对于任意 ，我们需要证明 中存在 的上确界。

设 ，。注意此处 是 在 中的上确界，而未必是我们要找的在 中的上确界，因为 可能不在 中（即 可能不是 的不动点）。我们接下来将会在 上寻找最小不动点 ，那么 就是 在 中的上确界。

我们证明 。 对于任意 ，我们有 。 因为 是 的上界，所以 ，由 的单调性得 ，所以 。

这说明 是 的一个上界。因为 是 的最小上界，所以 。

因此，对于任意 ，根据 和 的单调性，有 ，结合 ，我们得到 ，因此 。这说明了 。

于是我们可以将 看作是完备格 上的一个函数，因此它在该区间上存在一个最小不动点 ， 这个 就是我们要找的 在 中的上确界。

有向集与 DCPO

有向集

定义（有向集） ，若 且 使 ，则称 为有向集。

DCPO

定义（DCPO） 偏序集 称为 DCPO (directed complete partial order)，若对任意有向集 ， 存在于 。

链

定义（链） 称为链，若 。

Scott 连续函数

定义（Scott 连续函数）

设 为偏序集，如果函数 将有向集映射为有向集且保持上确界，则称 是 Scott 连续的：

• 对任意有向集 ， 是有向集；
• 对任意有向集 ，，其中 。

注意每个 DCPO 之间的 Scott 连续函数都是单调函数。Scott 连续性等价于由 Scott 拓扑引入的拓扑连续性。

Kleene 不动点定理

定理（Kleene 不动点定理） 设 为具有最小元 的 DCPO， 为 Scott 连续函数。定义序列：

则 构成递增链，并且

满足 ，即这个序列的上确界就是 的最小不动点。

证明

我们有以下的定向 -链：

的 Scott 连续性蕴含了 的单调性，因此 是一个递增链，因此 是一个有向集。

因为 是 DCPO， 中存在 的上确界 。接下来我们需要证明 是 的最小不动点。

一，证明 是一个不动点，即 。因为 是 Scott 连续的，所以 ，即 。又因为 ，而 不影响上确界的计算，所以 。因此 ，所以 是 的一个不动点。

二，证明 是最小不动点。我们接下来证明 的任意不动点都是 的上界。如果这个结论成立，那么 作为 的上确界（最小上界），就必然小于 的任意不动点，从而证明 是最小不动点。

使用数学归纳法证明。设 是 的一个不动点，我们证明对于任意 ，。

• 奠基步骤 显然成立：，因为 是 的最小元素。
• 归纳假设：假设 。归纳步骤：根据归纳假设和 的单调性，我们有 。又因为 是 的不动点，所以 ，因此 。