克納斯特-塔斯基定理

在數學領域序理論和格理論中，Knaster–Tarski 定理，得名於 Bronisław Knaster 和阿爾弗雷德·塔斯基，它聲稱:

設 L 是完全格並設 f : L → L 是次序保持函數。則 f 在 L 中的不動點的集合也是完全格。

這個定理的一種逆命題由 Anne C. Davis 證明了: 如果所有次序保持函數 f : L → L 有不動點，則 L 是完全格。

推論

因為完全格不能是空的，這個定義特別保證 f 的至少一個不動點的存在，甚至一個「最小」(或「最大」)不動點的存在。在很多實際情況中，這是這個定理最重要的蘊涵。

f 的最小不動點是最小元素 x 使得 f(x) = x，或者等價的說，使得 f(x) ≤ x；最大不動點的對偶命題成立，它是最大的元素 x 使得 f(x) = x。

如果對於 L 的元素的遞升序列的所有 x_n 有 f(lim x_n)=lim f(x_n)，則 f 的最小不動點是 lim fⁿ(0)，這裡的 0 是 L 的最小元素，因此給出了這個定理的更有「建設性」的一個版本。更一般的說，如果 f 是單調函數，則 f 的最小不動點是 f^α(0) 的固定極限，選取 α 於序數上，這裡的 f^α 使用超限歸納法定義: f^α+1 = f ( f^α) 而 f^γ 對於極限序數 γ 是 f^β 對於所有小於 γ 的序數 β 的最小上界。最大不動點的對偶定理成立。

例如，在理論計算機科學中，單調函數的最小不動點被用來定義程序語義。使用這個定理的一個更專門的版本，這裡的 L 被堅定為是特定集合的所有子集在集合包含次序下格。這反映了在很多應用中只使用這種格的事實。人們經常查找有是函數 f 的不動點的這種性質的最小集合。抽象釋義充分利用了 Knaster–Tarski 定理並公式給出了最小和最大不動點。

Knaster–Tarski 定理可以用於康托爾-伯恩斯坦-施洛德定理的一個簡單證明。

這個定理(對於集合的格)的一個特殊情況出現在 Bronislaw Knaster 的論文中:

在和到一個集合的在集合包含下遞增的所有子集的家族的所有函數都有至少一個不動點。

引用

• Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics. 1955, 5:2: 285–309. 
• Andrzej Granas and James Dugundji. Fixed Point Theory. Springer-Verlag, New York. 2003. ISBN 0-387-00173-5. 
• M. Kolibiar, A. Legéň, T. Šalát and Š. Znám. Algebra a príbuzné disciplíny. Alfa, Bratislava (in Slovak). 1992. ISBN 80-05-00721-3. 
• Anne C. Davis. A characterization of complete lattices. Pacific J. Math. 1955, 5: 311–319. 
• B. Knaster. Un théorème sur les fonctions d'ensembles. Ann. Soc. Polon. Math. 1928, 6: 133–134. 
• T. Forster, Logic, Induction and Sets, ISBN 0521533619

外部連結

• J. B. Nation, Notes on lattice theory.