克纳斯特-塔斯基定理

在数学领域序理论和格理论中，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.