クリーネの不動点定理

はじめに、${\displaystyle L}$ における ${\displaystyle f}$ のクリーネ鎖の存在性を示す。 ${\displaystyle \bot }$ の最小性より ${\displaystyle \bot \sqsubseteq f(\bot )}$ が成り立つので、この両辺に単調関数 ${\displaystyle f}$ （スコット連続関数はすなわち単調である）を繰り返し適用することで以下の通りクリーネ鎖 ${\displaystyle \mathbb {M} }$ が得られる。

${\displaystyle \bot \sqsubseteq f(\bot )\sqsubseteq f(f(\bot ))\sqsubseteq \cdots \sqsubseteq f^{n}(\bot )\sqsubseteq \cdots }$

これは ω-完備半順序上の ω-鎖であるから、上限 ${\displaystyle \sup(\mathbb {M} )}$ を持つ。

続いて、${\displaystyle \sup(\mathbb {M} )}$ が ${\displaystyle f}$ の不動点であることを示す。 これは ${\displaystyle f}$ のスコット連続性より次式の通り示される。（この式の最後の等号は ${\displaystyle \bot \sqsubseteq f(\bot )}$ より成り立つ）

${\displaystyle f(\sup(\mathbb {M} ))=f(\sup(\{\bot ,f(\bot ),f(f(\bot )),\ldots \}))=\sup(\{f(\bot ),f(f(\bot )),f(f(f(\bot ))),\ldots \})=\sup(\mathbb {M} )}$

最後に、${\displaystyle \sup(\mathbb {M} )}$ が ${\displaystyle f}$ の最小不動点であることを示す。 ${\displaystyle f}$ の任意の不動点 ${\displaystyle k}$ を取ると、${\displaystyle \bot }$ の最小性より ${\displaystyle \bot \sqsubseteq k}$ が成り立つ。 この両辺に単調関数 ${\displaystyle f}$ を繰り返し適用すると ${\displaystyle f^{n}(\bot )\sqsubseteq f^{n}(k)}$ (${\displaystyle n\in \mathbb {N} }$) が得られるが、${\displaystyle k}$ は ${\displaystyle f}$ の不動点であるからすなわち ${\displaystyle f^{n}(\bot )\sqsubseteq k}$ が成り立つ。 よって ${\displaystyle \mathbb {M} }$ は ${\displaystyle k}$ 以下の元からなる鎖であり、${\displaystyle \sup(\mathbb {M} )}$ はその上限であるから、${\displaystyle \sup(\mathbb {M} )}$ もまた ${\displaystyle k}$ 以下である。 斯くして ${\displaystyle \mathbb {M} }$ が ${\displaystyle f}$ の最小不動点であることが示された。

• タルスキの不動点定理（英語版）
• その他の不動点定理