クリーネの不動点定理のソースを表示

{{otheruses|順序理論や束論における不動点定理|計算可能性理論における不動点定理|クリーネの再帰定理}}

[[数学]]の[[順序集合|順序理論]]や[[束 (束論)|束論]]における'''クリーネの不動点定理'''（クリーネのふどうてんていり、{{En|Kleene fixed-point theorem}}）とは、[[スティーヴン・コール・クリーネ]]によって導入された以下の定理である。

:[[最大と最小#全順序に関する最大元・最小元|最小元]]を持つ [[完備半順序|ω-完備半順序]] <math>(L, \sqsubseteq)</math> 上の[[スコット連続]][[関数 (数学)|関数]] <math>f: L \to L</math> は[[最小不動点]]を持ち、それは <math>f</math> のクリーネ鎖の[[順序集合#上界、最大、極大、上限、上方集合|上限]]に一致する。

ここで、<math>f</math> の'''クリーネ鎖'''とは、<math>L</math> の最小元 <math>\bot</math> に <math>f</math> を[[反復合成写像|繰り返し]]適用することで得られる以下の[[全順序#鎖|鎖]]のことである。

:<math>\bot \sqsubseteq f(\bot) \sqsubseteq f(f(\bot)) \sqsubseteq \cdots \sqsubseteq f^n(\bot) \sqsubseteq \cdots</math>

最小不動点を <math>\textrm{lfp}</math> と書くことにすると、本定理は次式で表すことができる。

:<math>\textrm{lfp}(f) = \sup \left(\left\{f^n(\bot) \mid n\in\mathbb{N}\right\}\right)</math>

本定理はしばしば[[アルフレト・タルスキ]]によるものと誤解されるが、本定理は不動点の具体的な構成方法を与えているという点で{{仮リンク|タルスキの不動点定理|en|Knaster–Tarski theorem}}（こちらは[[完備束]]上の[[単調写像|単調関数]]に関する定理である）とは異なるものである。

== 証明<ref>{{Cite book|url=https://doi.org/10.1017/CBO9781139166386|title=Mathematical Theory of Domains by V. Stoltenberg-Hansen|last=Stoltenberg-Hansen |first=V.| last2=Lindstrom |first2=I.|last3=Griffor|first3=E. R.|publisher=Cambridge University Press |year=1994 |isbn=0521383447|location=|pages=24|language=en|doi=10.1017/cbo9781139166386|quote=|via=}}</ref> ==

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

:<math>\bot \sqsubseteq f(\bot) \sqsubseteq f(f(\bot)) \sqsubseteq \cdots \sqsubseteq f^n(\bot) \sqsubseteq \cdots</math>

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

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

:<math>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})</math>

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

== 関連項目 ==
* {{仮リンク|タルスキの不動点定理|en|Knaster–Tarski theorem}}
* その他の[[不動点定理]]

== 参考文献 ==
{{Reflist}}

{{デフォルトソート:くりいねのふとうてんていり}}
[[Category:順序構造]]
[[Category:順序集合論]]
[[Category:不動点定理]]
[[Category:数学に関する記事]]