在数学中，序理论的克萊尼不動點定理（）指出给定任何完全格 L 和任何具有斯科特连续性的函数
:f: L \to L,
f的最小不动点fix(f)存在，如果我们用\bot来表示L内的最小元素，那么fix(f) = \bigsqcup_{i \geq 0}f^{i}(\bot)
证明
我们首先定义集合M = \{\bot, f(\bot), f^{2}(\bot), \ldots\}，为了方便表示，我们用m来表示集合M中最大的元素，即m = \bigsqcup M。我们想要证明m为函数f的最小不动点。
首先我们证明m为函数f的不动点。因为函数f是斯科特连续的，所以我们有f(m) = f(\sqcup M) = \sqcup(f(M) \cup \bot) = \bigsqcup M = m。
接下来我们证明m为函数f的最小不动点。假设函数f存在另外一个不动点x，因为\bot \sqsubseteq x, 且函数f为单调函数（由于斯科特连续性），所以f(\bot) \sqsubseteq f(x) = x。假设m = f^{k}(\bot), k \in \mathbb{N}， 根据数学归纳法，f^{k}(\bot) \sqsubseteq f^{k}(x) = x。 即m为函数f的最小不动点。
参见
*克纳斯特-塔斯基定理
- 其他不动点定理
评论 (0)