クリーネの不動点定理（とベルマンフォード法）

言語処理系で講義でクリーネの不動点定理をやった時にベルマンフォードの証明にも使えるなぁと思ったので紹介します。

クリーネの不動点定理

$(D,\le)$ を完備半順序集合とし、 $f$ をその上のスコット連続写像とする。このとき、 $f$ は最小不動点を持つ。

ここで、完備半順序集合とは最小元 $\bot$ を持ち、任意の有向部分集合 $X$ について $X$ の上限 $\sqcup X$ が存在する半順序集合とします。

$X$ が有向集合であるとは任意の $a,b \in X$ についてある元 $c \in X$ が存在して $a \le c \land b \le c$ が成り立つこととします。

$f$ が $D$ 上のスコット連続写像であるとは、 $D$ の任意の有向部分集合 $X$ について $f(\sqcup X) = \sqcup \{ f(x) \mid x \in X \}$ が成り立つこととします。

何言ってんだコイツと思った人もブラウザバックを早まらないでください。

あとで有限半順序の場合を紹介しますが、有限の場合は簡単で、ベルマンフォードの証明に応用するのはそこだけで十分なので、意味がわからないひとは少しスクロールしてみてください。

とりあえず一般の完備半順序集合についてクリーネの不動点定理を証明しましょう。

証明

まず、 $f$ がスコット連続なら $f$ は単調です。

なぜなら $X = \{ a, b \}, a \le b$ とすると、 $X$ は有向集合で、 $\sqcup X = b$ となり、スコット連続性を考えると $f(\sqcup X) = f(b) = \sqcup \{ f(a), f(b) \}$ となるので、 $f(a) \le f(b)$ が導かれるからです。

$A = \{ f^{n}(\bot) \mid n \in \mathbb{N} \}$ とします。( $\mathbb{N}$ は $0$ を含むものとします)

このとき、最小性より $\bot \le f(\bot)$ が成り立ち、単調性より $\bot \le f(\bot) \le f^{2}(\bot) \le ...$ となります。

よって、 $A$ は有向集合で、完備性より上限 $\sqcup A$ が存在します。これが目的の最小不動点となることを示します。

まず不動点性ですが、スコット連続性より

$f(\sqcup A) = \sqcup \{ f(f^{n}(\bot)) \mid n \in \mathbb{N} \} = \sqcup \{ f^{n}(\bot) \mid 1 \le n \in \mathbb{N} \} = \sqcup A$ より不動点です。

また、任意の不動点 $x$ について、 $\bot \le x$ と単調性より任意の $n \in \mathbb{N}$ について $f^{n}(\bot) \le f^{n}(x) = x$ となり、 $\sqcup A \le x$ が成立します。

以上より示せました。

有限半順序の場合

おまたせしました。

有限の場合、クリーネの不動点定理は

$(D,\le)$ を最小元 $\bot$ を持つ有限半順序集合とし、 $f$ をその上の広義単調増加写像とする。このとき、 $f$ は最小不動点を持つ。

となります。

$f$ が広義単調増加写像であるとは、任意の $a, b \in D$ に対して $a \le b \Rightarrow f(a) \le f(b)$ が成り立つことです。

それでは証明しましょう（一般の場合を読んだ人は繰り返しになるので読む必要は無いかもしれません）

有限半順序の場合の証明

$D$ の要素数を $|D|$ と表します。

任意に $x \in D$ を一つ取ります。

$\bot, f(\bot), ..., f^{|D|}(\bot)$ を考えると、最小性より $\bot \le f(\bot)$ が成り立ち、単調性より $\bot \le f(\bot) \le ..\ \le f^{|D|}(\bot)$ が成り立ちます。

そして、鳩の巣原理から $0 \le i$ < $j \le |D|$ で $f^{i}(\bot) = f^{j}(\bot)$ となるものが存在し、 $f^{i}(\bot) \le f^{i+1}(\bot) \le ...\le f^{j}(\bot) = f^{i}(\bot)$ の間が全て等号で成り立つので、 $f^{i}(\bot) = \bot'$ が不動点になります。