【筆記】不動點定理（六）塔斯基不動點定理 Tarskis Fixed Point Theorem

來自專欄 不求甚解學經濟

向量的序關係

iff ;

iff ;

iff 且至少有一個不等式嚴格成立；

iff .

meet與join

;

.

meet:

其中對於每個，都是從相應的第項與之間選取較小的那個；即,;

join:

其中對於每個，都是從相應的第項與之間選取較大的那個；即,;

Def.格（Lattice）

給定一個集合，如果集合中的任意元素和之meet和join都還在之內，則稱為一個Lattice。即，都有。

一個偏序集（即可以在其上定義一個滿足自反性、反對稱性和傳遞性的序關係的集合），如果其有上（以及下）確界，則此偏序集便成為一個格。

完備格的定義和非減自映射的性質是證明Lemma 2進而證明塔斯基不動點定理的關鍵。

Def.完備格

我們稱是一個完備格當且僅當是偏序集並且的每個子集都有上確界(當然也有下確界性質)。

Def.非減自映射

任給偏序集。函數（自映射） 稱為上的非減自映射當且僅當對中任意兩個元素 ，每當便有。

Lemma 1

任給完備格。為上的任一非減自映射，則：

（1）對所有的 ，若，則也是一個完備格。其中，。

（2）對所有的 ，若、且，則是上的非減自映射。其中，表示函數在上的限制。

Lemma 2

任給完備格，為上的任一非減自映射，則有一個最大的不動點和一個最小的不動點。

證明

任給完備格，為上的任一非減自映射。

我們令， 。設是的所有不動點的集合。

取為的上確界（因為是的子集，根據是完備格的定義，這個上確界是存在的），那麼我們有：對每一個 ， （因為是非減自映射，集合上確界的函數總是不小於集合中任何其他元素的函數）。所以也是的一個上界。從而，滿足我們對集合的設定(即)，即 。有屬於自身的上確界，所以是中的最大元。

另一方面，因為，利用的非減性，有，再次滿足我們對集合的設定，故而。而是的最大元，故。結合我們上一步得到的有 ，即是的一個不動點，。

由於從而，同時所以的最大元 也是的最大元。即有最大不動點，這個最大不動點就是的上確界。

同理可證的下確界是的最小不動點。

Th.塔斯基不動點定理

完備格上的任一非減自映射都有不動點，並且的全體不動點在下組成一個完備格。

證明

Step 1. 由Lemma 2 ，我們知道函數存在一個不動點。

Step 2. 設的所有不動點的集合是 ，我們證明是一個完備格。

按照完備格的定義，我們只需證明在下的偏序集的每個子集在中有上確界。

Step 3. 任選一個集合，取為在中的上確界，取為的最大元（即在中的上確界）。

因為對每一個 ，，所以 是 的上界。從而 。

而為的最大元，從而，所以按照Lemma 1(1)，而按照Lemma 1(2)，是完備格 上的非減自映射。

按照Lemma 2 ，在 上有一個最小的不動點，即滿足「不小於中任一元素」的最小不動點。從而這個不動點就是在中的上確界。

脫胎於：

Corbae D, Stinchcombe M B, Zeman J. An introduction to mathematical analysis for economic theory and econometrics[M]. Princeton University Press, 2009.