Kleeneの不動点定理

同義語：Kleene fixed-point theoremクリーネの不動点定理

概要

前提知識: 半順序集合, 単調写像, Knaster–Tarskiの定理

Kleeneの不動点定理（Kleene fixed-point theorem）は、最小元 $\bot$ をもち増加列がいつも上限をもつ半順序集合の上で、増加列の上限を保つ単調写像 $f$ が最小の不動点をもち、それが
$$ \bot\le f(\bot)\le f(f(\bot))\le\cdots $$
の上限として得られることを述べる定理である。Knaster–Tarskiの定理は完備束の上の任意の単調写像について最小不動点の存在を示すが、それは前不動点全体の下限という「上からの」記述である。Kleene の不動点定理は、写像に連続性を課す代わりに、最小不動点を「下から」可算回の反復で組み立てる。
この形は、再帰的な定義の意味づけに向いている。階乗の定義 $g(0)=1$、$g(n)=ng(n-1)$ や、文法の規則 $S\to aSb\mid\varepsilon$ は、「何も定まっていない状態」から規則を 1 回ずつ当てていくと、答えが少しずつ定まっていく。その極限が定義の表すものであり、それが規則の最小の解であることを定理は保証する。この記事では主定理を証明し、関係の反射推移閉包・文脈自由言語・部分関数への応用、不動点帰納法、連続性のない単調写像での超限反復を扱う。
計算可能性理論には Kleene の再帰定理（プログラムが自分自身の番号を使えることを述べる定理。計算可能性理論の記事に言明がある）があり、不動点の定理とも呼ばれるが、この記事の定理とは別のものである。

定義

$\mathbb N=\{0,1,2,\dots\}$ とする。半順序集合の部分集合 $S$ の上限（最小の上界）を $\bigsqcup S$ と書く。

ω完備半順序集合とω連続写像

$(D,\le)$ を半順序集合とする。

$D$ の元の列 $(x_n)_{n\in\mathbb N}$ が $x_0\le x_1\le x_2\le\cdots$ を満たすとき、ω鎖（ω-chain）という。その上限を $\bigsqcup_nx_n$ と書く。
$D$ のすべての ω鎖が上限をもつとき、$D$ は ω完備（ω-complete）であるという。ω完備で最小元 $\bot$ をもつ半順序集合を、点付き ω完備半順序集合という。
ω完備な $D,E$ の間の写像 $f\colon D\to E$ が ω連続であるとは、$f$ が単調写像であり、任意の ω鎖 $(x_n)$ について $f\bigl(\bigsqcup_nx_n\bigr)=\bigsqcup_nf(x_n)$ となることをいう。

$f$ が単調なら $(f(x_n))$ も ω鎖なので、右辺の上限は存在する。単調性から $f(x_m)\le f\bigl(\bigsqcup_nx_n\bigr)$ がすべての $m$ で成り立つので、$\bigsqcup_nf(x_n)\le f\bigl(\bigsqcup_nx_n\bigr)$ はいつも成り立ち、ω連続性の要点は逆向きの不等号にある。不動点・前不動点（$f(x)\le x$）・最小不動点 $\operatorname{lfp}(f)$ の用語は Knaster–Tarskiの定理の定義「単調写像と不動点」に従う。$f^0(x)=x$、$f^{n+1}(x)=f(f^n(x))$ と書く。
ω完備性の典型的な与えられ方は次のとおりである。

完備束は、すべての部分集合が上限をもつので点付き ω完備である。
有向集合をなす部分集合がすべて上限をもつ半順序集合を有向完備（dcpo）といい、有向集合をなす部分集合の上限を保つ単調写像を Scott 連続という（AJ94 Definition 2.1.13, 2.1.17, p. 15）。ω鎖の値の集合は鎖なので有向集合であり、有向完備なら ω完備、Scott 連続なら ω連続である。
有限な半順序集合では ω鎖はいつか一定になるので、ω完備である。より一般に、どの ω鎖もいつか一定になる（昇鎖条件を満たす）半順序集合は ω完備である。

直感

$\bot$ は「まだ何も分かっていない」状態であり、$f$ は「今の知識から一段だけ多くを導く」操作である。$\bot\le f(\bot)$ は自明で、単調性から $f^n(\bot)\le f^{n+1}(\bot)$ が続くので、反復は知識を増やす方向にしか進まない。ω完備性は「増えていく知識の極限」が存在することを、ω連続性は「極限で新しく導けることは、すでに有限の段階で導けている」ことを保証する。このとき極限はもう増えず、不動点になる。
Banach の不動点定理（Banachの不動点定理）との類似もある。Banach の定理は距離の縮小を使って任意の点からの反復の極限を不動点とし、Kleene の定理は順序の連続性を使って最小元からの反復の上限を不動点とする。

主定理

Kleeneの不動点定理

$D$ を点付き ω完備半順序集合、$f\colon D\to D$ を ω連続写像とする。このとき
$$ x^{*}:=\bigsqcup_{n\in\mathbb N}f^n(\bot) $$
は $f$ の不動点であり、$f$ のすべての前不動点 $p$（$f(p)\le p$）について $x^{*}\le p$ である。とくに $x^{*}$ は $f$ の最小不動点であり、最小の前不動点でもある。

反復は ω鎖である。 $n$ についての帰納法で $f^n(\bot)\le f^{n+1}(\bot)$ を示す。$n=0$ では $\bot$ が最小元なので $\bot\le f(\bot)$ である。$f^n(\bot)\le f^{n+1}(\bot)$ なら、$f$ の単調性から $f^{n+1}(\bot)\le f^{n+2}(\bot)$ である。$D$ は ω完備なので上限 $x^{*}$ が存在する。
$x^{*}$ は不動点である。 ω連続性から
$$ f(x^{*})=\bigsqcup_nf\bigl(f^n(\bot)\bigr)=\bigsqcup_nf^{n+1}(\bot) $$
である。列 $(f^{n+1}(\bot))_n$ の上界と列 $(f^n(\bot))_n$ の上界は同じものである。実際、後者の上界は前者の上界であり、前者の上界 $u$ は $f^0(\bot)=\bot\le u$ も満たすので後者の上界である。上界の集合が同じなので上限も等しく、$f(x^{*})=x^{*}$ である。
最小性。 $f(p)\le p$ とする。$n$ についての帰納法で $f^n(\bot)\le p$ を示す。$n=0$ では $\bot\le p$ である。$f^n(\bot)\le p$ なら、単調性から $f^{n+1}(\bot)\le f(p)\le p$ である。よって $p$ は反復の上界であり、$x^{*}\le p$ である。不動点はとくに前不動点なので、$x^{*}$ は最小不動点である。$x^{*}$ 自身も前不動点なので、最小の前不動点である。$\square$

AJ94 Theorem 2.1.19（p. 16）は、点付き有向完備半順序集合と Scott 連続写像についてこの定理を述べている。上の定義の後の注意により、それはこの定理の特別な場合である。
$D$ が完備束で $f$ が ω連続なら、Knaster–Tarskiの定理の最小不動点 $\bigwedge\{x\mid f(x)\le x\}$ は、最小の前不動点として $x^{*}$ と一致する。つまり二つの定理は同じ元を、前不動点の下限と、反復の上限という別々の形で与える。

有限回の反復で止まる場合

$D$ を最小元 $\bot$ をもつ半順序集合で、どの ω鎖もいつか一定になるものとする。このとき $D$ 上の任意の単調写像 $f$ は ω連続であり、ある $N$ で $f^{N+1}(\bot)=f^N(\bot)$ となって、$f^N(\bot)$ が $f$ の最小不動点である。$D$ が有限なら $N$ は $D$ の元の個数より小さくとれる。

ω鎖 $(x_n)$ が $n\ge M$ で $x_n=x_M$ なら $\bigsqcup_nx_n=x_M$ であり、$(f(x_n))$ も $n\ge M$ で $f(x_M)$ に等しいので $\bigsqcup_nf(x_n)=f(x_M)=f\bigl(\bigsqcup_nx_n\bigr)$ である。よって $f$ は ω連続で、thm-kleene-main が使える。反復 $(f^n(\bot))$ は ω鎖なので、ある $N$ で $f^N(\bot)=f^{N+1}(\bot)$ となり、以後は一定なので $x^{*}=f^N(\bot)$ である。$D$ が $k$ 個の元からなるとき、$f^0(\bot)< f^1(\bot)<\cdots$ と真に増え続けられるのは $k$ 個の元までなので、$N\le k-1$ にとれる。$\square$

これは Knaster–Tarskiの定理の節「有限反復で求められる範囲」で示されている有限の完備束の場合を含む。

例

次の 3 つの例では、写像が鎖の和集合（上限）と交換することを確かめれば ω連続性が分かり、反復を計算すると最小不動点が求まる。

関係の反射推移閉包

集合 $X$ 上の関係 $R\subset X\times X$ をとる。完備束 $\mathcal P(X\times X)$ 上に
$$ \Phi(S):=\Delta_X\cup\{(x,z)\mid (x,y)\in R,\ (y,z)\in S\text{ となる } y\text{ がある}\} $$
を定める（$\Delta_X$ は対角集合）。$\Phi$ は空でない族の和集合と交換するので ω連続である。$n$ についての帰納法により、$\Phi^n(\emptyset)$ は「$x=y_0,y_1,\dots,y_k=z$ で各 $(y_{i-1},y_i)\in R$ となる長さ $k< n$ の列がある」組 $(x,z)$ の全体である。よって最小不動点 $\bigcup_n\Phi^n(\emptyset)$ は、$R$ の辺をたどって有限回で行ける組の全体、すなわち $R$ の反射推移閉包である。有向グラフの到達可能性はこの特別な場合である。

文法の最小の解

$\Sigma=\{a,b\}$ とし、文字列全体 $\Sigma^{*}$ の冪集合上に $\Phi(L):=\{\varepsilon\}\cup\{awb\mid w\in L\}$ を定める（$\varepsilon$ は空語）。$\Phi$ は和集合と交換するので ω連続であり、帰納法により $\Phi^n(\emptyset)=\{a^kb^k\mid 0\le k< n\}$ である。最小不動点は $\{a^kb^k\mid k\ge0\}$ で、これは規則 $S\to aSb\mid\varepsilon$ の生成する文脈自由言語である。不動点 $L$ はどれも $L=\{\varepsilon\}\cup aLb$ を満たすので、長さについての帰納法で $L$ の元は $a^kb^k$ の形とわかり、この例では不動点はただ 1 つである。

部分関数と再帰的定義

$\mathbb N$ から $\mathbb N$ への部分写像（部分関数）の全体 $D$ に、拡大の順序 $g\le h$（$h$ が $g$ の拡大。部分写像の定義「合成と拡大」の 2。グラフ $\Gamma_g\subset\Gamma_h$ と同値）を入れる。どこでも定義されない部分関数 $\bot$ が最小元である。ω鎖 $g_0\le g_1\le\cdots$ のグラフの和集合 $\Gamma=\bigcup_n\Gamma_{g_n}$ は、同じ $m$ に対する 2 つの組 $(m,u),(m,v)$ がある 1 つの $\Gamma_{g_n}$ に入るので $u=v$ となり、部分関数のグラフである。これが上限なので、$D$ は点付き ω完備である。

階乗。 $\Phi(g)$ を、$\Phi(g)(0)=1$、$m\ge1$ で $m-1\in\operatorname{dom}g$ なら $\Phi(g)(m)=m\,g(m-1)$、それ以外では定義しない部分関数とする。$\Gamma_{\Phi(g)}=\{(0,1)\}\cup\{(m+1,(m+1)u)\mid(m,u)\in\Gamma_g\}$ はグラフの和集合と交換するので、$\Phi$ は ω連続である。$\Phi^n(\bot)$ は $\{0,\dots,n-1\}$ の上で $m!$ を返し、それ以外では定義されない。最小不動点は階乗 $m\mapsto m!$ で、すべての $m$ で定義される。
止まらない定義。 $\Psi(g)(m)$ を「$m+1\in\operatorname{dom}g$ なら $g(m+1)$、そうでなければ定義しない」とする（定義式 $h(m)=h(m+1)$ にあたる）。$\Psi$ も ω連続で、$\Psi(\bot)=\bot$ なので最小不動点は $\bot$ である。不動点はほかに定数関数がある（不動点 $g$ では $m\in\operatorname{dom}g$ と $m+1\in\operatorname{dom}g$ が同値なので、定義域は $\emptyset$ か $\mathbb N$ であり、後者なら $g(m)=g(m+1)$ から $g$ は定数である）。最小不動点 $\bot$ は、この定義を手続きとして実行すると計算が終わらないことに対応する。

不動点帰納法

最小不動点が性質をもつことは、反復の各段階を調べて示せる。

不動点帰納法

$D$ を点付き ω完備半順序集合、$f\colon D\to D$ を ω連続写像とし、部分集合 $S\subset D$ が次を満たすとする。

$\bot\in S$。
項がすべて $S$ に属する ω鎖の上限は $S$ に属する。
$f(S)\subset S$。
このとき $\operatorname{lfp}(f)\in S$ である。

1 と 3 から、帰納法ですべての $n$ について $f^n(\bot)\in S$ である。$(f^n(\bot))$ は ω鎖（thm-kleene-main の証明）なので、2 によりその上限 $\operatorname{lfp}(f)$ は $S$ に属する。$\square$

この形の原理は AJ94 Lemma 2.1.20（p. 17）にある。たとえば ex-kleene-partial-functions の階乗の $\Phi$ について、$S:=\{g\mid\operatorname{dom}g\text{ のすべての }m\text{ で }g(m)\ge1\}$ は 1–3 を満たす（2 はグラフの和集合をとっても値が変わらないことによる）ので、最小不動点の値はすべて $1$ 以上である。条件 2 は外せない。有限の定義域をもつ部分関数の全体 $S'$ は $\bot$ を含み $\Phi(S')\subset S'$ だが、最小不動点の階乗の定義域は無限で、$S'$ に属さない。

単調写像と超限反復

ω連続性がないと、可算回の反復では不動点に届かないことがある（Knaster–Tarskiの定理の節「有限反復で求められる範囲」の $\mathcal P(\mathbb N\cup\{\infty\})$ の例）。それでも、鎖の上限が十分にあれば、反復を順序数の長さまで続けて最小不動点に到達できる。

単調写像の最小不動点

（$\mathsf{ZF}$）$D$ を最小元 $\bot$ をもつ半順序集合で、空でない鎖がすべて上限をもつものとし、$f\colon D\to D$ を単調写像とする。このとき $f$ は最小不動点をもち、それは最小の前不動点でもある。

要点：超限再帰で $x_0=\bot$、$x_{\alpha+1}=f(x_\alpha)$、極限順序数 $\lambda$ では $x_\lambda=\bigsqcup_{\beta<\lambda}x_\beta$ と反復を続けると、この列は増加し、どの前不動点よりも下にある。Hartogs数の長さまで真に増え続けることはできないので、どこかで止まる。

詳しい証明を開く

超限再帰の系「三段階形式の超限再帰」により、$x_0=\bot$、$x_{\alpha+1}=f(x_\alpha)$、$0$ でない極限順序数 $\lambda$ では「$\{x_\beta\mid\beta<\lambda\}$ が鎖ならその上限、そうでなければ $\bot$」を $x_\lambda$ とする列を定める。

(A) すべての順序数 $\alpha$ について、「$\beta\le\alpha$ なら $x_\beta\le x_\alpha$」と「$x_\alpha\le x_{\alpha+1}$」を、$\alpha$ についての超限帰納法で示す。$\alpha=0$ では $\bot\le f(\bot)$ である。$\alpha=\gamma+1$ のとき、$\beta\le\gamma$ なら帰納法の仮定から $x_\beta\le x_\gamma\le x_{\gamma+1}$ であり、$x_\gamma\le x_{\gamma+1}$ に $f$ を施して $x_{\gamma+1}\le x_{\gamma+2}$ である。$\alpha=\lambda$ が極限のとき、帰納法の仮定から $\{x_\beta\mid\beta<\lambda\}$ は空でない鎖なので、$x_\lambda$ はその上限であり、$\beta<\lambda$ なら $x_\beta\le x_\lambda$ である。さらに $\beta<\lambda$ について $x_\beta\le x_{\beta+1}=f(x_\beta)\le f(x_\lambda)$ なので、$f(x_\lambda)$ は上界であり、$x_\lambda\le f(x_\lambda)=x_{\lambda+1}$ である。

(B) $f(p)\le p$ なら、すべての $\alpha$ で $x_\alpha\le p$ である。$x_0=\bot\le p$、$x_\alpha\le p$ なら $x_{\alpha+1}=f(x_\alpha)\le f(p)\le p$、極限では上限が上界 $p$ 以下になるからである。

(C) $\kappa$ を $D$ の Hartogs 数（$D$ への単射が存在しない最小の順序数）とする。すべての $\alpha<\kappa$ で $x_\alpha\ne x_{\alpha+1}$ だったとする。$\beta<\alpha<\kappa$ なら (A) から $x_\beta< x_{\beta+1}\le x_\alpha$ なので $x_\beta\ne x_\alpha$ であり、$\alpha\mapsto x_\alpha$ は $\kappa$ から $D$ への単射になって矛盾する。よってある $\alpha<\kappa$ で $f(x_\alpha)=x_\alpha$ である。(B) により $x_\alpha$ はすべての前不動点、とくにすべての不動点以下なので、最小不動点であり、最小の前不動点でもある。$\square$

有向完備で最小元をもつ半順序集合は、鎖が有向集合なのでこの命題の仮定を満たす。AJ94 Proposition 2.1.16（p. 15）は、最小元をもつ半順序集合について、有向完備であることと、すべての単調写像が最小不動点をもつことが同値であると述べている。この逆向きは、この記事では証明しない。
ω完備性だけでは単調写像に不動点があるとは限らない。選択公理のもとで、可算順序数の全体 $\omega_1$ は、可算個の可算順序数の上限が可算順序数なので点付き ω完備であり、$\alpha\mapsto\alpha+1$ は単調だが不動点をもたない。この写像は ω連続でなく（$\bigsqcup_n n=\omega$ だが $\omega+1\ne\bigsqcup_n(n+1)=\omega$）、$\omega_1$ 自身は上限をもたない鎖である。

反例の表

thm-kleene-main の仮定を 1 つずつ外した例と、prop-kleene-induction の条件 2 を外した例である。

外す条件	反例	成り立たなくなること
ω完備性	$\mathbb N$ の通常の大小と $f(n)=n+1$（単調で、上限をもつ ω鎖の上限を保つ）	不動点の存在
最小元の存在	比較不能な 2 元 $\{a,b\}$ と、$a,b$ を入れ替える写像	不動点の存在
ω連続性	$\mathcal P(\mathbb N\cup\{\infty\})$ 上の、自然数がすべて揃うと $\infty$ を加える写像	$\bigsqcup_nf^n(\bot)$ が不動点であること
ω鎖の上限で閉じる（不動点帰納法）	有限の定義域の部分関数の全体と階乗の $\Phi$	$\operatorname{lfp}(f)\in S$

1 行目：$\mathbb N$ で上限をもつ ω鎖はいつか一定になるものだけで、$f$ はその上限を保つが、ω鎖 $0,1,2,\dots$ は上限をもたない。不動点 $n=n+1$ はない。2 行目：ω鎖は定数列だけなので $\{a,b\}$ は ω完備で、入れ替えは ω連続だが、不動点はない。3 行目：写像は $\varphi(S)=\{0\}\cup\{n+1\mid n\in S\cap\mathbb N\}\cup\{\infty\mid\mathbb N\subset S\}$ で、反復の上限は $\mathbb N$ だが $\varphi(\mathbb N)=\mathbb N\cup\{\infty\}$ である（Knaster–Tarskiの定理の同じ節）。最小不動点 $\mathbb N\cup\{\infty\}$ は存在するが、可算回の反復では届かない。4 行目は前の節で確かめた。

補足

最小不動点をとる操作の連続性。 点付き有向完備半順序集合 $D$ の上の Scott 連続写像の全体に点ごとの順序を入れると、$f\mapsto\operatorname{lfp}(f)$ はまた Scott 連続になる（AJ94 Theorem 2.1.19 の 2、p. 16）。この記事では証明しない。プログラムの意味論では、これが再帰的な定義を組み合わせてよい根拠になる。
文献。 単調写像の最小不動点の存在と、その形式言語の理論・再帰理論・プログラムの意味論での使われ方については、AJ94 §1.1（p. 6）が文献を挙げている。