克莱尼不动点定理

此條目没有列出任何参考或来源。 (2010年1月1日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

在数学中，序理论的克萊尼不動點定理（英語：Kleene fixed-point theorem）指出给定任何完全格 L 和任何具有斯科特连续性的函数

${\displaystyle f:L\to L,}$

${\displaystyle f}$的最小不动点${\displaystyle fix(f)}$存在，如果我们用${\displaystyle \bot }$来表示L内的最小元素，那么${\displaystyle fix(f)=\bigsqcup _{i\geq 0}f^{i}(\bot )}$

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

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

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

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

这是一篇关于数学的小作品。您可以通过编辑或修订扩充其内容。 查 论 编