克莱尼不动点定理

在数学中，序理论的克萊尼不動點定理（Template:Lang-en）指出给定任何完全格 L 和任何具有斯科特连续性的函数

$f:L\to L,$

$f$的最小不动点$fix(f)$存在，如果我们用$\mathrm{\perp }$来表示L内的最小元素，那么$fix(f)=\underset{i\ge 0}{⨆}{f}^i(\mathrm{\perp })$

证明

我们首先定义集合$M=\{\mathrm{\perp },f(\mathrm{\perp }),f^2(\mathrm{\perp }),\dots \}$，为了方便表示，我们用$m$来表示集合$M$中最大的元素，即$m=⨆M$。我们想要证明$m$为函数$f$的最小不动点。

首先我们证明$m$为函数$f$的不动点。因为函数$f$是斯科特连续的，所以我们有$f(m)=f(\bigsqcup M)=\bigsqcup (f(M)\cup \mathrm{\perp })=⨆M=m$。

接下来我们证明$m$为函数$f$的最小不动点。假设函数$f$存在另外一个不动点$x$，因为$\mathrm{\perp }⊑x$, 且函数$f$为单调函数（由于斯科特连续性），所以$f(\mathrm{\perp })⊑f(x)=x$。假设$m=f^k(\mathrm{\perp }),k\in \mathbb{N}$， 根据数学归纳法，$f^k(\mathrm{\perp })⊑f^k(x)=x$。 即$m$为函数$f$的最小不动点。

参见

• 克纳斯特-塔斯基定理
• 其他不动点定理