主題
Search

塔斯基不動點定理


(L,<=) 為任意 完全格。假設 f:L->L 是單調遞增(或保序)的,即,對於所有 x,y in Lx<=y 意味著 f(x)<=f(y)。那麼 f 的所有 不動點 的集合關於 <= 是一個 完全格 (Tarski 1955)

因此,f 有一個最大 不動點 u^_ 和一個最小 不動點 u__。此外,對於所有 x in Lx<=f(x) 意味著 x<=u^_,而 f(x)<=x 意味著 u__<=x

考慮三個例子

1. 設 a,b in R 滿足 a<=b,其中 <= 是實數的通常順序。由於閉區間 [a,b] 是一個 完全格,每個單調遞增對映 f:[a,b]->[a,b] 都有一個最大 不動點 和一個最小 不動點。注意,這裡的 f 不需要是連續的。

2. 對於 x,y in R^n,宣告 x<=y 表示 x_1<=y_1...x_n<=y_n (逐分量序)。設 a,b in R^n 滿足 a<=b。那麼集合

[a,b]={x in R^n:a<=x<=b}
(1)
=[a_1,b_1]×...×[a_n,b_n]
(2)

是一個 完全格(關於逐分量序)。因此,每個單調遞增對映 f:[a,b]->[a,b] 都有一個最大 不動點 和一個最小 不動點

3. 設 g:A->Bh:B->A單射。那麼存在一個 雙射 i:A->B (施羅德-伯恩斯坦定理),它可以如下構造。冪集 A 由集合包含關係排序,(P(A), subset= ),是一個 完全格。由於對映 f:P(A)->P(A)

 f(S)=A\h(B\g(S))    (S subset= A)
(3)

是單調遞增的,它有一個 不動點 C subset= A。作為 A\C=h(B\g(C)),一個 雙射 i:A->B 可以透過設定以下方式定義

 i(x)=g(x) if x in C,    i(x)=h^(-1)(x) if x in A\C.
(4)

參見

完全格, 對映不動點, 偏序集, 施羅德-伯恩斯坦定理

此條目由 Roland Uhl 貢獻

使用 探索

參考文獻

Tarski, A. "A Lattice-Theoretical Fixpoint Theorem and Its Applications." Pacific J. Math. 5, 285-309, 1955.

在 上被引用

塔斯基不動點定理

引用為

Uhl, Roland. "塔斯基不動點定理." 來自 Web 資源,由 Eric W. Weisstein 建立. https://mathworld.tw/TarskisFixedPointTheorem.html

主題分類