Knaster–Tarski theorem
In the
- Let (L, ≤) be a complete lattice and let f : L → L be an order-preserving (monotonic) function w.r.t. ≤ . Then the set of fixed points of f in L forms a complete lattice under ≤ .
It was Tarski who stated the result in its most general form,[1] and so the theorem is often known as Tarski's fixed-point theorem. Some time earlier, Knaster and Tarski established the result for the special case where L is the lattice of subsets of a set, the power set lattice.[2]
The theorem has important applications in
A kind of converse of this theorem was proved by
Consequences: least and greatest fixed points
Since complete lattices cannot be
The
If f(lim xn) = lim f(xn) for all ascending
For example, in theoretical
The Knaster–Tarski theorem can be used to give a simple proof of the
Weaker versions of the theorem
Weaker versions of the Knaster–Tarski theorem can be formulated for ordered sets, but involve more complicated assumptions. For example:[citation needed]
- Let L be a least element (bottom) and let f : L → L be an monotonic function. Further, suppose there exists u in L such that f(u) ≤ u and that any chainin the subset has a supremum. Then f admits a least fixed point.
This can be applied to obtain various theorems on
- For the monotone map F : P(X ) → P(X ) on the familyof (closed) nonempty subsets of X, the following are equivalent: (o) F admits A in P(X ) s.t. , (i) F admits invariant set A in P(X ) i.e. , (ii) F admits maximal invariant set A, (iii) F admits the greatest invariant set A.
In particular, using the Knaster-Tarski principle one can develop the theory of global attractors for noncontractive discontinuous (multivalued) iterated function systems. For weakly contractive iterated function systems the Kantorovich theorem (known also as Tarski-Kantorovich fixpoint principle) suffices.
Other applications of fixed-point principles for ordered sets come from the theory of differential, integral and operator equations.
Proof
Let us restate the theorem.
For a complete lattice and a monotone function on L, the set of all fixpoints of f is also a complete lattice , with:
- as the greatest fixpoint of f
- as the least fixpoint of f.
Proof. We begin by showing that P has both a least element and a greatest element. Let D = {x | x ≤ f(x)} and x ∈ D (we know that at least 0L belongs to D). Then because f is monotone we have f(x) ≤ f(f(x)), that is f(x) ∈ D.
Now let (u exists because D ⊆ L and L is a complete lattice). Then for all x ∈ D it is true that x ≤ u and f(x) ≤ f(u), so x ≤ f(x) ≤ f(u). Therefore, f(u) is an upper bound of D, but u is the least upper bound, so u ≤ f(u), i.e. u ∈ D. Then f(u) ∈ D (because f(u) ≤ f(f(u))) and so f(u) ≤ u from which follows f(u) = u. Because every fixpoint is in D we have that u is the greatest fixpoint of f.
The function f is monotone on the dual (complete) lattice . As we have just proved, its greatest fixpoint exists. It is the least fixpoint of L, so P has least and greatest elements, that is more generally, every monotone function on a complete lattice has a least fixpoint and a greatest fixpoint.
For a, b in L we write [a, b] for the
It remains to be proven that P is a complete lattice. Let , W ⊆ P and . We show that f([w, 1L]) ⊆ [w, 1L]. Indeed, for every x ∈ W we have x = f(x) and since w is the least upper bound of W, x ≤ f(w). In particular w ≤ f(w). Then from y ∈ [w, 1L] follows that w ≤ f(w) ≤ f(y), giving f(y) ∈ [w, 1L] or simply f([w, 1L]) ⊆ [w, 1L]. This allows us to look at f as a function on the complete lattice [w, 1L]. Then it has a least fixpoint there, giving us the least upper bound of W. We've shown that an arbitrary subset of P has a supremum, that is, P is a complete lattice.
Computing a Tarski fixed-point
Chang, Lyuu and Ti
Deng, Qi and Ye
Input Lattice
|
Polynomial function | Value oracle |
---|---|---|
Componentwise | ||
Lexicographic |
The algorithms are based on binary search. On the other hand, determining whether a given fixed point is unique is computationally hard:
Input Lattice
|
Polynomial function | Value oracle |
---|---|---|
Componentwise | coNP-complete
|
|
Lexicographic | coNP-complete
|
For d=2, for componentwise lattice and a value-oracle, the complexity of is optimal.[9] But for d>2, there are faster algorithms:
- Fearnley, Palvolgyi and Savani[10] presented an algorithm using only queries. In particular, for d=3, only queries are needed.
- Chen and Li[11] presented an algorithm using only queries.
Application in game theory
Tarski's fixed-point theorem has applications to
Because the best-response functions are monotone, Tarski's fixed-point theorem can be used to prove the existence of a
Echenique[14] presents an algorithm for finding all PNE in a supermodular game. His algorithm first uses best-response sequences to find the smallest and largest PNE; then, he removes some strategies and repeats, until all PNE are found. His algorithm is exponential in the worst case, but runs fast in practice. Deng, Qi and Ye[8] show that a PNE can be computed efficiently by finding a Tarski fixed-point of an order-preserving mapping associated with the game.
See also
Notes
- .
- Ann. Soc. Polon. Math.6: 133–134. With A. Tarski.
- .
- .
- ^ Uhl, Roland. "Tarski's Fixed Point Theorem". MathWorld. Example 3.
- ISBN 9780521784511.
- ISSN 0304-3975.
- ^ a b c Dang, Chuangyin; Qi, Qi; Ye, Yinyu (2020-05-01). Computations and Complexities of Tarski's Fixed Points and Supermodular Games (Report). arXiv.org.
- S2CID 202538977.
- S2CID 222141645.
- S2CID 246823965.
- ISSN 0304-4068.
- ISSN 0363-0129.
- ISSN 0022-0531.
References
- Andrzej Granas and ISBN 978-0-387-00173-9.
- Forster, T. (2003-07-21). Logic, Induction and Sets. Cambridge University Press. ISBN 978-0-521-53361-4.
Further reading
- S. Hayashi (1985). "Self-similar sets as Tarski's fixed points". Publications of the Research Institute for Mathematical Sciences. 21 (5): 1059–1066. .
- J. Jachymski; L. Gajek; K. Pokarowski (2000). "The Tarski-Kantorovitch principle and the theory of iterated function systems". Bull. Austral. Math. Soc. 61 (2): 247–261. .
- E.A. Ok (2004). "Fixed set theory for closed correspondences with applications to self-similarity and games". Nonlinear Anal. 56 (3): 309–330. .
- B.S.W. Schröder (1999). "Algorithms for the fixed point property". Theoret. Comput. Sci. 217 (2): 301–358. .
- S. Heikkilä (1990). "On fixed points through a generalized iteration method with applications to differential and integral equations involving discontinuities". Nonlinear Anal. 14 (5): 413–426. .
- R. Uhl (2003). "Smallest and greatest fixed points of quasimonotone increasing mappings". S2CID 120679842.
External links
- J. B. Nation, Notes on lattice theory.
- An application to an elementary combinatorics problem: Given a book with 100 pages and 100 lemmas, prove that there is some lemma written on the same page as its index