不求甚解學經濟-不動點定理（六）塔斯基不動點定理 Tarski's Fixed Point Theorem 及其他

介紹一些簡單的格點知識、超模概念以及塔斯基不動點定理。

格 Lattice

偏序集

給定一個集合 $X$，如果能夠在 $X$ 上定義一個序關係 $\geq$，使得 $\geq$ 在 $X$ 上滿足自反性、反對稱性和傳遞性，那麽 $(X,\geq)$ 便是一個偏序集。

【舉例】嚮量的序關係

$\forall i$

$x = y$ iff $x_{i} = y_{i}$;

$x\geq y$ iff $x_{i}\geq y_{i}$;

$x>y$ iff $x_{i}\geq y_{i}$且至少有一個不等式嚴格成立；

$x>>y$ iff $x_{i}>y_{i}$.

meet 與 join

給定偏序集 $(X,\geq)$ 上的一對元素 $x,y\in X$，定義元素 $x$ 和 $y$ 的 meet ($\wedge$) 和 join ($\vee$) 為

$$\begin{aligned} x \wedge y &:=\sup\left\{z\in X;x\geq z,y\geq z\right\}\\ x \vee y &:= \inf\left\{z\in X;z\geq x,z\geq y\right\} \end{aligned}$$

其中 $\sup$ 和 $\inf$ 是相對於偏序集 $(X,\geq)$ 上的序關係而言的，例如 $\geq$ 可以是歐式空間中的逐維大小關係、集合中的包含關係等等。

【舉例】

$x = (x_{1},...,x_{n})$;

$y = (y_{1},...,y_{n})$.

meet: $x\wedge y = z = (z_{1},...,z_{n})$

其中對於每個$i$，$z_{i}$都是從相應的第$i$項$x_{i}$與$y_{i}$之間選取較小的那個；即$\forall i$,$z_{i} = min\lbrace x_{i},y_{i} \rbrace$;

join: $x\vee y = z = (z_{1},...,z_{n})$

其中對於每個$i$，$z_{i}$都是從相應的第$i$項$x_{i}$與$y_{i}$之間選取較大的那個；即$\forall i$,$z_{i} = max\lbrace x_{i},y_{i} \rbrace$;

Def: Lattice

給定一個偏序集 $(X,\geq)$ 如果對於集合中的任意一對元素 $x$ 和 $y$，都滿足

$$\begin{aligned} x \wedge y &:=\sup\left\{z\in X;x\geq z,y\geq z\right\}\in X\\ x \vee y &:= \inf \left\{z\in X;z\geq x,z\geq y\right\}\in X \end{aligned}$$

則稱偏序集 $(X,\geq)$ 為一個 Lattice。

【舉例】給定一個集合$X\subset\mathbb R^{n}$，如果集合$X$中的任意一對元素 $x$ 和 $y$ 之meet和join都還在$X$之內，則稱$X$為一個Lattice。即$\forall x,y$，都有$x\wedge y\in X$ 并且 $x\vee y\in X$。

註意，此處我們不要求任意子集的 meet 和 join 都在集合之內 (那是完備格的要求)，而隻要求任意一對元素。

Def: Sublattice

給定一個格 $(X,\geq)$ 和一個子集 $S\subset X$，如果對於任何一對 $x,y\in S$，都滿足 $x\wedge y\in S$ 和 $x\vee y\in S$，則稱 $S$ 是 $X$ 在 $\geq$ 下的一個子格。

Fact: 子格

給定一個格 $(X,\geq)$ 和一個子集 $S\subset X$，$S$ 是 $X$ 在 $\geq$ 下的一個子格當且僅當 $S\geq S$。

Def: 最大（最小）元

給定一個 Lattice集合 $\subset\mathbb R^{n}$，如果 $\forall x\in X$ 都有 $x^{\ast}\geq x$（$x^{\ast}\leq x$），則稱元素 $x^{\ast}\in X$ 為格 $X$ 的最大（最小）元。

Th3

非空緊格必有最大及最小元。

證明

對於每個$i\in\lbrace 1,2,...,n \rbrace$，從各$x_{i}$中選擇使得第$i$個坐標取到最大值的那一個作為$z^{i}\in X$，即$z^{i}\in arg max_{x\in X}x_{i}$。
由於$X$為緊集，因此對於任何一個$i$，如上所述的最大元$z^{i}$都是可以找到的。令$y = z^{1}\vee z^{2}\vee ...\vee z^{n}$。而由於$X$是格，格內元素之join仍在格內，即$y\in X$。取$y = (z_{1}^{1},...,z_{n}^{n})$，即$y$的每個坐標都是那些能出現在該坐標的備選項中最大的，因此有$y\geq x$對於所有$x\in X$。

Def 強集序

給定格 $(X,\geq_{\text{for elements}})$ ，對於任何子集 $A,B\subset X$，定義強集序 $\geq_{\text{for sets}}$ 為

$$A\geq_{\text{for sets}} B\text{ iff } (\forall x\in A,y\in B)[y\geq_{\text{for elements}} x\Rightarrow (x\in B)\text{ and }(y\in A) ]$$

此處關於序關係的下標是爲了明確表明是應用於元素還是集合，但通過語境可以做出此種區分，因此後文將不再明確寫出。

對於來自於同一個格的兩個子集來説，一個子集“大”與另一個子集等價於任選一對元素，其中更“大”的元素來自更“大”的集合，更“小”的元素來自更“小”的集合。

但這并不意味著，從更“大”的集合中任選一個元素，從更“小”的集合中任選一個元素，前一個元素一定“大於”后一個元素。但確實意味著，更“大”的集合中的“最大元”一定“大於”更“小”集合中的“最大元”，并且更“大”集合中的“最小元”一定“大於”更“小”集合中的“最小元”，即：強集序只能保證極端元素的排序關係，更不能保證其中每個元素的排序關係，這也是爲什麽在超模博弈中，只有極端納什均衡具有單調比較靜態關係，但無法保證任意納什均衡具有單調比較靜態關係。

Def4: 超模性

給定一個格 $(X,\geq)$ 以及函數 $f:X\rightarrow\mathbb{R}$。如果對於所有的 $z,z^{\prime}\in X$ 都滿足

$$f(z)+f(z^{\prime})\leq f(z\vee z^{\prime})+f(z\wedge z^{\prime})$$

則稱函數 $f$ 具有超模性。

兩個小性質：超模任意正的常數倍仍是超模；兩個超模的和仍是超模。

如果 $X$ 不僅是個偏序集，而且是個綫序集 (任何兩個元素都可以比較大小，例如 $\mathbb{R}$)，那麽所有的函數都具有超模性 (前述不等式以等式成立)。因此可知，超模性具有 bites 僅當函數的定義域并非綫序時 (例如 $\mathbb{R}^{N}$)，否則超模性是平凡地成立的。

超模性是基數性質，未必在單調正變化下保持 (那是擬超模性的性質)。

Th5

任選取兩個格$x\subset\mathbb R^{n}$，$y\subset\mathbb R^{n}$，取定義在$X\times Y$上的一個超模$f:X\times Y\rightarrow\mathbb R$。如果對於任意的$y\in Y$，$h(y) = max_{x\in X}f(x,y)$都有良好定義，則$h$也是$X$上的超模。（類比Berge極大值定理）

證明

選取$y^{1},y^{2}\in Y$，以及$x^{1},x^{2}\in X$，使得$h(y^{i}) = f(x^{i},y^{i})$對於$i = 1,2$均成立。則有

$$h(y^{1})+h(y^{2}) = f(x^{1},y^{1})+f(x^{2},y^{2})$$

（根據我們對於$h(\cdot)$的設定）

$$\leq f(x^{1}\wedge x^{2},y^{1}\wedge y^{2})+f(x^{1}\vee x^{2},y^{1}\vee y^{2})$$

（根據我們對於$f(\cdot)$是超模的設定）

$$\leq h(y^{1}\wedge y^{2})+h(y^{1}\vee y^{2})$$

（再次根據我們對於$h(\cdot)$的設定）。$\square$

Def: 乘積格

給定偏序集們 $(X_{i},\geq_{i})_{i\in N^{\text{finite}}}$，定義偏序集 $X:=\Pi_{i\in N^{\text{finite}}}X_{i}$，以及對於 $x,y\in X$

$$x\geq y\text{ iff }x_{i}\geq_{i}y_{i},\forall i$$

則稱 $(X,\geq)$ 為乘積格。

Def: 增差

給定一個乘積格 $(X,\geq)$，函數 $f:X\rightarrow\mathbb{R}$ 滿足增差條件，當且僅當，任選維度 $i\neq j;i,j\in N$，給定 $(i,j;x_{ij};x_{i},x_{i}^{\prime};x_{j},x_{j}^{\prime})$，每當 $x_{i}^{\prime}\geq x_{i}$ 和 $x_{j}^{\prime}\geq x_{j}$ 都有

$$f(x_{i}^{\prime},x_{j}^{\prime};x_{-ij})-f(x_{i},x_{j}^{\prime};x_{-ij})\geq f(x_{i}^{\prime},x_{j};x_{-ij})-f(x_{i},x_{j};x_{-ij})$$

注意前式要對任意選取的一對 $i\neq j;i,j\in N$ 都成立。

【舉例】令$X\subset\mathbb R^{n}$為一個格，函數$f:X\rightarrow\mathbb R$。對於每個$z\in X$，每對不同的指標$i,j$以及相應的$z_{i}^{\ast}\geq z_{i}$，$z_{j}^{\ast}\geq z_{j}$，如果都有

$$f(z_{-ij},z_{i}^{\ast},z_{j}^{\ast})-f(z_{-ij},z_{i}^{\ast},z_{j})\geq f(z_{-ij},z_{i},z_{j}^{\ast})-f(z_{-ij},z_{i},z_{j})$$

則稱函數$f$對於$X$中的每對元素滿足增差性。

增差是基數性質，未必在單調正變換下保持。

Th7

$X\subset\mathbb R^{n}$而$f:X\rightarrow\mathbb R$。則函數$f$為超模當且僅當$f$在$X$上滿足增差性。

Def. 單交叉(一)

假設自變量集為 $X\subset\mathbb{R}$，參數集為 $T\subset\mathbb{R}$。一個函數 $f:X\cdot T\rightarrow\mathbb{R}$ 對於 $(x,t)$ 滿足單交叉性質，如果對於任何 $x^{\prime}> x$ 和 $t^{\prime}> t$ 都有

$$\begin{aligned} f(x^{\prime},t)\geq f(x,t)&\Rightarrow f(x^{\prime},t^{\prime}\geq f(x,t^{\prime}))\\ f(x^{\prime},t)> f(x,t)&\Rightarrow f(x^{\prime},t^{\prime}> f(x,t^{\prime})) \end{aligned}$$

Def. 單交叉(二)

假設自變量集 $X$ 是一個格，參數集 $T$ 是一個偏序集。一個函數 $f:X\cdot T\rightarrow\mathbb{R}$ 對於 $(x,t)$ 滿足單交叉性質，如果對於任何 $x^{\prime}> x$ 和 $t^{\prime}> t$ 都有

$$\begin{aligned} f(x^{\prime},t)\geq f(x,t)&\Rightarrow& f(x^{\prime},t^{\prime}\geq f(x,t^{\prime}))\\ f(x^{\prime},t)> f(x,t)&\Rightarrow& f(x^{\prime},t^{\prime}> f(x,t^{\prime})) \end{aligned}$$

單交叉是序數性質，可以在單調正變換下保持。

塔斯基不動點定理

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

Def. 完備格

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

註意，格的定義要求任意一對兒元素的 meet 和 join 仍在集合之內，而完備格的定義的相應要求施加於任何子集 (不僅任意一對，還得任意三個、任意四個……) 之上。

Def. 非減自映射

任給偏序集$(A,\leq)$。函數（自映射）$f:A\rightarrow A$ 稱為$(A,\leq)$上的非減自映射當且僅當對$A$中任意兩個元素$x,y\in A$ ，每當$x\leq y$便有$f(x)\leq f(y)$。

Lemma 1

任給完備格$(A,\leq)$。$f:A\rightarrow A$為$(A,\leq)$上的任一非減自映射，則：

（1）對所有的$a,b\in A​$ ，若$a\leq b​$，則$(\left[a,b\right],\leq)​$也是一個完備格。其中，$\left[a,b\right]=\lbrace x\in A\mid a\leq x\leq b \rbrace ​$。

（2）對所有的$a,b\in A$ ，若$a\leq b$、$a\leq f(a)$且$f(b)\leq b$，則$f\mid_{\left[a,b\right]}$是$(\left[a,b\right],\leq)$上的非減自映射。其中，$f\mid_{\left[a,b\right]}$錶示函數$f$在$\left[a,b\right]$上的限製。

Lemma 2

任給完備格$(A,\leq)$，$f:A\rightarrow A$為$(A,\leq)$上的任一非減自映射，則$f$有一個最大的不動點和一個最小的不動點。

註意，這裏確界的存在來自於完備格的定義，隻要是完備格那麼根據定義其確界都在集合之內。這跟我們採用的是 $\mathbb{R}$ 還是 $\mathbb{R}^{N}$ 作爲例子是無關的，完備格這個偏序集使用的序關係不必與實數集或歐式空間上的序關係相同。

證明

任給完備格$(A,\leq)$，$f:A\rightarrow A$為$(A,\leq)$上的任一非減自映射。

我們令， $E = \lbrace x\in A \mid x\geq f(x) \rbrace $。設$B$是$f$的所有不動點的集合。

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

另一方麵，因為$f(d) \geq d$，利用$f$的非減性，有$f(f(d))\geq f(d)$，再次滿足我們對集合$D$的設定，故而$f(d)\in D$。而$d$是$D$的最大元，故$d\geq f(d)$。結合我們上一步得到的$f(d) \geq d$有 $f(d)=d$ ，即$d$是$f$的一個不動點，$d \in B$。

由於$B=D\cap E$從而$B \subset D$，同時$d\in B$所以$D$的最大元$d$ 也是$B$的最大元。即$f$有最大不動點，這個最大不動點就是$D$的上確界。

同理可證$E$的下確界是$f$的最小不動點。$\square$

Th. 塔斯基不動點定理

完備格$(A,\leq)$上的任一非減自映射$f$都有不動點，並且$f$的全體不動點在$\leq$下組成一個完備格。

證明

Step 1. 由Lemma 2 ，我們知道函數 $f$ 在完備格 $(A,\leq)$ 上存在一個不動點。

Step 2. 設$f$的所有不動點的集合是 $B$，我們證明$(B,\leq)$是一個完備格。

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

Step 3. 任選一個集合$C\subset B$，取$a$為$C$在$A$中的上確界，取$b$為$A$的最大元（即$A$在$A$中的上確界），根據完備格的定義，我們知道它們在 $A$ 中存在，而我們需要證明它們也在 $C$ 中。

因為對每一個$x \in C$ ，$f(a) = f(\sup C) \geq f(x) = x$，所以 $f(a)$是 $C$ 的上界。從而 $f(a) \geq \sup C = a$ 。

而$b$為$A$的最大元，從而$f(b) \leq b$，所以按照Lemma 1(1)$\left( \left[ a , b \right] , \leq \right)$，而按照Lemma 1(2)，$f\mid _{\left[ a ,b\right]}$是完備格 $\left( \left[ a , b \right] , \leq \right)$上的非減自映射。

按照Lemma 2 ，$f \mid _{\left[ a , b \right]}$在 $\left( \left[ a , b \right] , \leq\right)$ 上有一個最小的不動點，即滿足“不小於$C$中任一元素”的最小不動點。從而這個不動點就是$C$在$B$中的上確界。$\square$

脫胎於：
[1] Vohra R V. Advanced mathematical economics[M]. Routledge, 2004.
[2] Corbae D, Stinchcombe M B, Zeman J. An introduction to mathematical analysis for economic theory and econometrics[M]. Princeton University Press, 2009.