在數學中,序理論的 Kleene 不動點定理指出給定任何完全格 L 和任何具有斯科特連續性的函數
f {\displaystyle f} 的最小不動點 f i x ( f ) {\displaystyle fix(f)} 存在,如果我們用 ⊥ {\displaystyle \bot } 來表示L內的最小元素,那麼 f i x ( f ) = ⨆ i ≥ 0 f i ( ⊥ ) {\displaystyle fix(f)=\bigsqcup _{i\geq 0}f^{i}(\bot )}
我們首先定義集合 M = { ⊥ , f ( ⊥ ) , f 2 ( ⊥ ) , … } {\displaystyle M=\{\bot ,f(\bot ),f^{2}(\bot ),\ldots \}} ,為了方便表示,我們用 m {\displaystyle m} 來表示集合 M {\displaystyle M} 中最大的元素,即 m = ⨆ M {\displaystyle m=\bigsqcup M} 。我們想要證明 m {\displaystyle m} 為函數 f {\displaystyle f} 的最小不動點。
首先我們證明 m {\displaystyle m} 為函數 f {\displaystyle f} 的不動點。因為函數 f {\displaystyle f} 是斯科特連續的,所以我們有 f ( m ) = f ( ⊔ M ) = ⊔ ( f ( M ) ∪ ⊥ ) = ⨆ M = m {\displaystyle f(m)=f(\sqcup M)=\sqcup (f(M)\cup \bot )=\bigsqcup M=m} 。
接下來我們證明 m {\displaystyle m} 為函數 f {\displaystyle f} 的最小不動點。假設函數 f {\displaystyle f} 存在另外一個不動點 x {\displaystyle x} ,因為 ⊥ ⊑ x {\displaystyle \bot \sqsubseteq x} , 且函數 f {\displaystyle f} 為單調函數(由於斯科特連續性),所以 f ( ⊥ ) ⊑ f ( x ) = x {\displaystyle f(\bot )\sqsubseteq f(x)=x} 。假設 m = f k ( ⊥ ) , k ∈ N {\displaystyle m=f^{k}(\bot ),k\in \mathbb {N} } , 根據數學歸納法, f k ( ⊥ ) ⊑ f k ( x ) = x {\displaystyle f^{k}(\bot )\sqsubseteq f^{k}(x)=x} 。 即 m {\displaystyle m} 為函數 f {\displaystyle f} 的最小不動點。