標籤：

遞歸函數（九）：最小不動點定理

04-02

回顧

上文我們討論了集合上的偏序結構，之所以談論它們是因為，

完全偏序集上的連續函數具有最小不動點，這稱之為最小不動點定理，

除了集合論的一些知識之外，我們還要討論到底什麼是連續函數，以及什麼是完全偏序集。

有向子集與完全偏序

偏序集 $(D,leqslant )$ 的非空子集 $Ssubseteq D$ 叫做有向子集（directed subset），

當且僅當，對於 $S$ 中的任意元素 $a,bin S$ ，

存在 $S$ 中的一個元素 $c$ ，有 $aleqslant c$ 且 $bleqslant c$ 。

如果一個偏序集 $(D,leqslant )$ 的每個有向子集 $Ssubseteq D$ 都有上確界（記為 $igvee S$ ），

就稱它是一個有向完全偏序集，

此外，如果它還有最小元，就稱它是一個完全偏序集。

注意，完全偏序集並不是每一個子集都有上確界，

而是它的每一個有向子集都有上確界。

連續函數

假設 $(D,leqslant )$ 與 $(E,leqslant )$ 是完全偏序集， $f:D ightarrow E$ 是集合上定義的一個函數，

如果 $Ssubseteq D$ ，則 $f(S)$ 為 $E$ 的子集，其中 $f(S)=lbrace f(d)| din S brace$ 。

對於任意的 $d,din D$ ，如果 $dleqslant d$ 就有 $f(d)leqslant f(d)$ ，我們就說 $f$ 是單調的。

可以看出，如果 $f$ 是單調的，且 $S$ 是 $D$ 的有向子集，那麼 $f(S)$ 也是 $E$ 的有向子集。

如果 $f$ 是單調的，且對於任意有向子集 $Ssubseteq D$ ，有 $f(igvee S)=igvee f(S)$ ，

就稱 $f$ 是連續的。

連續函數集上的偏序結構

完全偏序集 $(D,leqslant )$ 到 $(E,leqslant )$ 的連續函數，也可以定義出一個偏序結構，

我們稱 $fleqslant g$ ，當且僅當對於每一個 $din D$ ，我們有 $f(d)leqslant g(d)$ 。

這樣我們就得到了一個元素為連續函數的偏序集， $(D ightarrow E,leqslant )$ 。

可以證明， $(D ightarrow E,leqslant )$ 也是一個完全偏序集。（證略

最小不動點定理

如果 $(D,leqslant )$ 是一個完全偏序集，且 $f:D ightarrow D$ 是連續的，

則 $f$ 有最小不動點， $fix_D f=igvee lbrace f^n(perp )| ngeqslant 0 brace$ 。

因為 $perp$ 是 $D$ 中的最小元，且 $f(perp )in D$ ，所以， $perp leqslant f(perp )$ ，

因為 $f$ 是連續的，所以 $f$ 也一定是單調的，所以， $f(perp )leqslant f^2(perp )$ ，

繼而， $f^n(perp )leqslant f^{n+1}(perp )$ ，對於任意的 $ngeqslant 0$ 都成立。

$lbrace f^n(perp )| ngeqslant 0 brace$ 構成了一個全序集，

所以，它是完全偏序集 $(D ightarrow E,leqslant)$ 的一個有向子集，必有上確界。

設 $a$ 是上確界， $a=igvee lbrace f^n(perp )| ngeqslant 0 brace$ ，則 $a$ 是 $f$ 的不動點。

因為由 $f$ 的連續性， $f(a)=f(igvee lbrace f^n(perp )| ngeqslant 0 brace )=igvee lbrace f^{(n+1)}(perp )| ngeqslant 0 brace$ ，

而 $lbrace f^n(perp ) brace$ 與 $lbrace f^{(n+1)}(perp ) brace$ 有同樣的上確界，所以 $f(a)=a$ ，即 $a$ 是 $f$ 的不動點。

其次， $a$ 是 $f$ 的最小不動點，

假設 $b=f(b)$ 是 $f$ 的任意不動點，因為 $perp leqslant b$ ，所以 $f(perp )leqslant f(b)$ ，

類似的，對於任意的 $ngeqslant 0$ ， $f^n(perp )leqslant f^n(b)$ 。

而 $b$ 是 $f$ 的不動點，所以 $f^n(b)=b$ ，因此 $b$ 是集合 $lbrace f^n(perp )| ngeqslant 0 brace$ 的上界。

由於集合的最小上界是 $a$ ，所以有 $aleqslant b$ 。

後繼函數的不動點

succ :: Int -> Intsucc n = n+1

在第七篇中，我們說fix可以得到任意函數的不動點，

那麼這個succ函數呢？它有沒有不動點？fix succ是什麼？

現在我們有了最小不動點定理，

就得驗證succ所指稱的數學函數，是不是一個完全偏序集上的連續函數，

如果是的話，它就有不動點。

在第四篇為了表示計算的不可終止性，我們對自然數集進行了擴充， $Ncup lbrace perp brace$ ，

然後用這個集合作為程序中Int類型的值的解釋。

然而， $Ncup lbrace perp brace$ 不是一個完全偏序集，原因是它沒有上界，

如果我們額外加入一個比其他的自然都大的元素 $+infty$ ，

則我們就得到了一個完全偏序集， $Ncup lbrace perp bracecup lbrace +infty brace$ 。

然後，我們看succ連續嗎？

首先，它是單調的，如果我們再定義 $succ(+infty )=+infty$ ，

就有 $succ(igvee N)=igvee succ(N)$ ，因此，succ是一個連續函數。

根據最小不動點定理，succ的最小不動點是， $fix succ=igvee lbrace succ^n(perp )| ngeqslant 0 brace$ 。

由於 $succ(perp )=perp$ ，即對於非終止的輸入succ的計算也不會終止，所以 $succ^n(perp )=perp$ ，

因此， $fix succ=igvee lbrace succ^n(perp )| ngeqslant 0 brace =perp$ ，

即，succ的最小不動點是 $perp$ ，fix succ的計算不會終止。

求解階乘函數

上一篇中，我們證明了階乘函數fact是以下函數的不動點，fact = fix g，

g :: (Int -> Int) -> Int -> Intg f n = case n of 1 -> 1 _ -> n * f (n-1)

現在我們來看一下，如何運用最小不動點定理來得到這個答案。

為了避免篇幅過長，關於g函數的連續性證明暫略，

我們直接使用公式， $fix g=igvee lbrace g^n(perp )| ngeqslant 0 brace$ ，

即，g函數的最小不動點，就是集合 $D=lbrace g^n(perp )| ngeqslant 0 brace$ 的上確界。

我們先來看一下這個集合 $D$ 中有哪些元素，

其中， $g(perp )in D$ ，我們將 $perp$ 傳入 $g$ 中，看看會得到什麼，

f1 = n -> case n of 1 -> 1 _ -> ...

這個函數能計算f1 1，但是不能計算f1 2，恰好是fact函數有限展開的一階項。

我們再來看 $g^2(perp )in D$ ，它等於 $g(f1)$ ，

f2 = n -> case n of 1 -> 1 _ -> n * f1 (n-1)

這個函數能計算f2 1以及f2 2，但是不能計算f2 3，

恰好是fact函數展開的二階項。

由此，我們看出了規律， $g^n(perp )in D$ 就是fact函數有限展開的第 $n$ 階項。

上一篇中，我們已經證明了，當 $n ightarrow infty$ 時，它就是fact函數，

考慮到 $f1,f2,cdots$ 這些函數的序關係，因此，我們有 $fact=igvee lbrace g^n(perp )| ngeqslant 0 brace$ 。

即，fact函數就是g函數的最小不動點。

總結

到此為止，我想這個系列的文章已經討論完了，

本系列文章一直圍繞著遞歸函數和不動點進行分析，

在內容上可以分為兩個部分，前半部分主要與可計算性理論有關，

後半部分與不動點定理有關，希望對大家有所幫助。

參考

有向集合

完全偏序

Kleene fixed-point theorem

Foundations for Programming Languages

推薦閱讀：

TAG:連續函數 |