標籤：

關係離散數學

遞歸函數（八）：偏序結構

04-28

回顧

上一篇我們介紹了不動點運算元和Y組合子，以及Y組合子的具體表現形式，

這一篇我們根據不動點運算元的性質來證明fact函數就是g函數的不動點。

隨後，我們回歸到了數學中，討論集合上的一種偏序結構，

這為下文完全偏序集，以及完全偏序集上連續函數的不動點定理做好準備。

不動點運算元的性質

上文我們介紹了不動點運算元fix，

它可以用來求取任意函數的不動點。

fix :: (a -> a) -> afix f = let x = f x in x

並且我們說以下函數的不動點為fact = fix g，

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

但是上文中，我們只是對它們的計算結果進行比對，

並沒有對它進行證明。

考慮到fix的性質，fix g = g (fix g)，

（因為fix g是g的不動點，令h = fix g，上式為h = g h

我們可以使用數學歸納法，證明對於任意的自然數 $n$ ，fact n = fix g n。

我們先證初始條件，

fix g 1 = g (fix g) 1 = case 1 of 1 -> 1 _ -> ...= 1= fact 1

然後再證遞推條件，假設fact k = fix g k，

我們要推出fact (k+1) = fix g (k+1)，其中， $k > 0$ 。

fix g (k+1)= g (fix g) (k+1)= case (k+1) of 1 -> 1 _ -> (k+1) * (fix g) k= (k+1) * (fix g) k= (k+1) * fact k= fact (k+1)

因此，對於任意的自然數 $n$ ，fact n = fix g n。

即，fact = fix g。

不動點運算元的有限展開

根據上一節fact = fix g的證明，我們看到，

每一步遞推，我們都使用了不動點運算元fix的性質fix g = g (fix g)，

但是對於一個具有有限存儲空間的機器來說，遞推的步驟不可能是無限的。

為了界定最多使用多少次遞推，我們定義， $fix^{[n+1]} g = g (fix^{[n]} g)$ ，

並且認為 $fix^{[0]} g$ 對於任意的 $n$ 無定義，

$fix^{[1]} g 1 = 1$ ，而 $fix^{[1]} g n$ 在 $n > 1$ 時沒有定義，

$fix^{[2]} g 1 = 1$ ， $fix^{[2]} g 2 = 2$ ，而 $fix^{[2]} g n$ 在 $n > 2$ 時沒有定義。

因此， $fix^{[n]} g$ 是一個部分函數，且，

$fix^{[n+1]} g$ 所表示的函數，總是比 $fix^{[n]} g$ 的計算能力更強一些，離fact更近一些。

當 $n ightarrow infty$ 時， $fix^{[infty ]} g$ 就是階乘函數fact。

即， $lbrace fix^{[n]} g| ngeqslant 0 brace$ 的最小上界，就是g的不動點。

那麼，什麼樣的g才能保證這個集合具有最小上界呢？

序理論指出，完全偏序集上的序保持自映射具有最小不動點。

為此，我們需要先認識什麼是偏序集，什麼是連續函數。

使用完全偏序集上的連續函數解釋程序中函數的方式，稱為域論模型。

偏序集與哈斯圖

在第三篇中，我們討論過偏序關係，

一個偏序集 $(D,leqslant )$ 是一個集合 $D$ ，並且在這個集合上定義了一個偏序關係 $leqslant$ 。

設 $A$ 為實數集的一個非空子集，我們定義 $A$ 上的偏序關係為 $leqslant$ ，

$xleqslant y$ 當且僅當 $x$ 是小或等於 $y$ 的實數，則 $(A,leqslant )$ 是一個偏序集。

偏序集反映了集合上的一種偏序結構，它比我們想像中的更為常見，

例如，一個集合 $A$ ，對於任意兩個元素 $x,yin A$ ，我們定義 $xleqslant y$ 當且僅當 $x=y$ ，

那麼 $(A,leqslant )$ 是一個偏序集。

因此，如果某個集合構成了一個偏序集，這完全取決於我們怎樣定義偏序關係。

設 $(D,leqslant )$ 是一個偏序集，

對於任意的 $x,yin D$ ，如果總是有 $xleqslant y$ 或者 $yleqslant x$ 成立，

則稱 $x$ 和 $y$ 是可比的。

$xleqslant y$ ，且 $x eq y$ ，則記為 $x<y$ 。

如果 $x$ 和 $y$ 是可比的，且 $x<y$ ，如果不存在 $zin D$ ，使得 $x<z<y$ ，

則稱 $y$ 覆蓋 $x$ 。

根據可比性和覆蓋性，我們就可以將偏序關係用無向圖表示出來了，

其中，頂點表示元素，邊表示覆蓋關係，並且省去圖中每個頂點處的環，

$y$ 覆蓋 $x$ 就將代表 $y$ 的頂點放在代表 $x$ 的頂點之上，並在 $x$ 和 $y$ 之間連線，

如果 $x<y$ ，但是 $y$ 不覆蓋 $x$ ，就省掉 $x$ 與 $y$ 之間的連線。

這樣用來表示有限偏序集的無向圖，稱為哈斯圖。

例如，易證整除關係是整數集上的一種偏序關係，

我們可以畫出偏序集 $lbrace 1,2,3,4,5,6,9,10,15 brace$ 對應的哈斯圖，如下，

全序集與擬序集

設 $(D,leqslant )$ 是一個偏序集，如果對於任意 $x,yin D$ ， $x$ 和 $y$ 都可比，

則稱 $leqslant$ 為 $D$ 上的全序關係，此時稱 $(D,leqslant )$ 為全序集。

可見，實數集以及實數集上的小於等於關係 $leqslant$ ，構成了一個全序集。

哈斯圖為從下至上的「一條線」，是全序集的充要條件。

設 $R$ 是非空集合 $A$ 上的，反自反的和傳遞的二元關係，

則稱 $R$ 為 $A$ 上的擬序關係，常將擬序關係記為 $<$ ，並稱 $(A,<)$ 為擬序集。

擬序關係自然具有反對稱性。

（其中，反自反關係，指的是不存在 $xin A$ ，使得 $x<x$ 。

擬序關係與偏序關係的哈斯圖在畫法上完全相同，

只是擬序關係的哈斯圖的各頂點都沒有環。

設 $(A,<)$ 是一個擬序集，如果對於任意的 $x,yin A$ ，

$x<y$ ， $x=y$ ， $y<x$ 三式有且僅有一式成立，則稱 $<$ 具有三歧性，

這樣的擬序關係 $<$ ，稱為擬全序關係，這樣的擬序集 $(A,<)$ ，稱為擬全序集。

擬全序集的哈斯圖也是「一條線」。

最小元與上確界

對於偏序集 $(D,leqslant )$ ，以及它的一個子集 $Ssubseteq D$ ，

如果存在 $yin S$ ，且對於任意的 $xin S$ ，有 $yleqslant x$ ，則稱 $y$ 為 $S$ 的最小元。

（相似的我們可以定義最大元

如果存在 $yin S$ ，對於任意的 $xin S$ ，

如果 $xleqslant y$ 那麼就有 $x=y$ ，則稱 $y$ 為 $S$ 的極小元。

（相似的我們可以定義極大元

如果 $S$ 是有窮集，則 $S$ 的極小元一定存在，並且可能有多個，

但是最小元卻不一定存在。

上文中，我們畫出了偏序集 $A=lbrace 1,2,3,4,5,6,9,10,15 brace$ 對應的哈斯圖，

我們取 $B_1=lbrace 1,2,3 brace$ ， $B_2=lbrace 3,5,15 brace$ ， $B_3=A$ ，

則 $1$ 是 $B_1$ 的最小元，也是極小元， $2,3$ 是 $B_1$ 的極大元，但 $B_1$ 沒有最大元。

$3,5$ 是 $B_2$ 的極小元，但 $B_2$ 沒有最小元， $15$ 是 $B_2$ 的最大元，也是極大元。

$1$ 是 $B_3$ 的最小元，也是極小元， $4,6,9,10,15$ 是 $B_3$ 的極大元，但是 $B_3$ 沒有最大元。

對於偏序集 $(D,leqslant )$ ，以及它的一個子集 $Ssubseteq D$ ，

如果存在 $yin D$ ，（注意，不一定是 $yin S$

使得對於任意的 $xin S$ ， $xleqslant y$ ，則稱 $y$ 為 $S$ 的上界，

如果 $S$ 的所有上界存在最小元，則稱它為 $S$ 最小上界，或上確界。

（相似的可以定義下確界

$S$ 的上界和下界不一定存在，即使存在，上確界和下確界也不一定存在。

設 $(A,<)$ 是一個擬全序集，如果對於 $A$ 中的任何非空子集 $S$ 都有最小元，

則稱 $<$ 是一個良序關係， $(A,<)$ 是一個良序集。

例如，自然數集以及自然數集上的小於關係，構成了一個良序集 $(N,<)$ ，

但是，整數集以及整數集上的小於關係，並不構成良序集，而僅僅是一個擬全序集。

總結

本文從一個證明出發，我們了解了不動點運算元的工作原理，

然後引出了一些數學概念，序關係在不動點運算元理論中佔有很重要的地位，

所以，這裡給出了詳細的介紹，下文我們開始討論最小不動點定理。

參考

序理論

域論模型

偏序關係

離散數學教程

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

推薦閱讀：

※不能證明也無法否定的「連續統假說」——集合的勢（三）
※麻花辮（Braid）

TAG:離散數學 | 關係 |