クリーネの不動点定理

順序と格子理論の数学の分野において、アメリカの数学者スティーブン・コール・クリーネにちなんで名付けられたクリーネの不動点定理は、次のことを述べています。

クリーネ不動点定理。が最小元を持つ有向完全半順序（dcpo）であり、 がスコット連続（したがって単調）関数であるとします。すると、は最小不動点を持ち、これはの上昇クリーネ連鎖の上限です。${\displaystyle (L,\sqsubseteq )}$${\displaystyle f:L\to L}$${\displaystyle f}$${\displaystyle f.}$

fの上昇クリーネ連鎖は連鎖である

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

Lの最小元⊥に対してf を反復する ことで得られる。式で表すと、定理は次のように述べている。

${\displaystyle {\textrm {lfp}}(f)=\sup \left(\left\{f^{n}(\bot )\mid n\in \mathbb {N} \right\}\right)}$

ここで、 は最小の固定点を表します。 ${\displaystyle {\textrm {lfp}}}$

タルスキの不動点定理は、ある種からf を 反復することで不動点がどのように計算されるかを考慮していないが（また、完全格子上の単調関数に関係する）、この結果は加法関数に対して証明したアルフレッド・タルスキに起因するとされることが多い。^{[1]さらに、クリーネの不動点定理は、超限反復を使用して}単調関数に拡張することができる。^[2]

出典: ^[3]

まず、 の上昇クリーネ連鎖がに存在することを示す必要があります。それを示すために、次のことを証明します。 ${\displaystyle f}$${\displaystyle L}$

補題。が最小元を持つdcpoであり、スコット連続である場合、${\displaystyle L}$${\displaystyle f:L\to L}$${\displaystyle f^{n}(\bot )\sqsubseteq f^{n+1}(\bot ),n\in \mathbb {N} _{0}}$

証明。帰納法を使います。

• n = 0 と仮定します。すると は最小の要素になります。${\displaystyle f^{0}(\bot )=\bot \sqsubseteq f^{1}(\bot ),}$${\displaystyle \bot }$
• n > 0 と仮定します。次に、 を示さなければなりません。整理すると、 が得られます。帰納的仮定により、 が成り立つことがわかります。また、f は単調であるため (スコット連続関数の性質)、結果も成り立ちます。${\displaystyle f^{n}(\bot )\sqsubseteq f^{n+1}(\bot )}$${\displaystyle f(f^{n-1}(\bot ))\sqsubseteq f(f^{n}(\bot ))}$${\displaystyle f^{n-1}(\bot )\sqsubseteq f^{n}(\bot )}$

補題の系として、次の有向ω連鎖が得られます。

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

dcpo の定義から、 には上限があり、それを と呼ぶことがわかります。残っているのは、 が最小の不動点であることを示すことです。 ${\displaystyle \mathbb {M} }$${\displaystyle m.}$${\displaystyle m}$

まず、が不動点、つまり であることを示します。 はスコット連続なので、、つまり です。また、 およびは上限の決定に影響を与えないため、が成り立ちます。したがって となり、の不動点が作成されます。 ${\displaystyle m}$${\displaystyle f(m)=m}$${\displaystyle f}$${\displaystyle f(\sup(\mathbb {M} ))=\sup(f(\mathbb {M} ))}$${\displaystyle f(m)=\sup(f(\mathbb {M} ))}$${\displaystyle \mathbb {M} =f(\mathbb {M} )\cup \{\bot \}}$${\displaystyle \bot }$${\displaystyle \sup(f(\mathbb {M} ))=\sup(\mathbb {M} )}$${\displaystyle f(m)=m}$${\displaystyle m}$${\displaystyle f}$

が実際に最小の不動点であることを証明するには、 の任意の要素が の任意の不動点よりも小さいことを示す必要があります(なぜなら、上限 の特性により、集合のすべての要素が の要素よりも小さい場合、 も の同じ要素よりも小さいためです)。これは、帰納法によって行われます。 はの不動点であると仮定します。次に、 に対して帰納法によって証明します。帰納法の基底は明らかに成り立ちます。は の最小の要素であるためです。帰納法の仮説として、 と仮定できます。次に、帰納法のステップを実行します。帰納法の仮説と(再び、 のスコット連続性によって示唆される) の単調性から、次の結論を得ることができます。ここで、が の不動点であると仮定することにより、 であることがわかり、そこから次の結果が得られます。${\displaystyle m}$${\displaystyle \mathbb {M} }$${\displaystyle f}$${\displaystyle D\subseteq L}$${\displaystyle L}$${\displaystyle \sup(D)}$${\displaystyle L}$${\displaystyle k}$${\displaystyle f}$${\displaystyle i}$${\displaystyle \forall i\in \mathbb {N} :f^{i}(\bot )\sqsubseteq k}$${\displaystyle (i=0)}$${\displaystyle f^{0}(\bot )=\bot \sqsubseteq k,}$${\displaystyle \bot }$${\displaystyle L}$${\displaystyle f^{i}(\bot )\sqsubseteq k}$${\displaystyle f}$${\displaystyle f}$${\displaystyle f^{i}(\bot )\sqsubseteq k~\implies ~f^{i+1}(\bot )\sqsubseteq f(k).}$${\displaystyle k}$${\displaystyle f,}$${\displaystyle f(k)=k,}$${\displaystyle f^{i+1}(\bot )\sqsubseteq k.}$

• その他の不動点定理