克莱尼不动点定理

在数学中，序理论的 Kleene 不动点定理指出给定任何完全格 和任何具有斯科特连续性的函数

${\displaystyle f}$内的最小元素，那么${\displaystyle fix(f)=\underset{i\ge <!--\; \ge \; -->0}{⨆<!--\; ⨆\; -->}{f}^i(\mathrm{\perp <!--\; \perp \; -->})}$

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

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

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