主题
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.net.cn/TarskisFixedPointTheorem.html

主题分类