Théorème de Knaster-Tarski

Knaster–Tarski theorem In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following: Laisser (L,≤) be a complete lattice and let f : L → L be an monotonic function (w.r.t. ≤). Then the set of fixed points of f in L also 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 formal semantics of programming languages and abstract interpretation.

A kind of converse of this theorem was proved by Anne C. Davis: If every order preserving function f : L → L on a lattice L has a fixed point, then L is a complete lattice.[3] Contenu 1 Conséquences: least and greatest fixed points 2 Weaker versions of the theorem 3 Preuve 4 Voir également 5 Remarques 6 Références 7 Lectures complémentaires 8 External links Consequences: least and greatest fixed points Since complete lattices cannot be empty (they must contain a supremum/infimum of the empty set), the theorem in particular guarantees the existence of at least one fixed point of f, and even the existence of a least (or greatest) fixed point. In many practical cases, this is the most important implication of the theorem.

The least fixpoint of f is the least element x such that f(X) =x, ou, de manière équivalente, such that f(X) ≤ x; the dual holds for the greatest fixpoint, the greatest element x such that f(X) =x.

Si f(lim xn)=lim f(xn) for all ascending sequences xn, then the least fixpoint of f is lim fn(0) où 0 is the least element of L, thus giving a more "constructive" version of the theorem. (Voir: Kleene fixed-point theorem.) Plus généralement, if f is monotonic, then the least fixpoint of f is the stationary limit of fα(0), taking α over the ordinals, where fα is defined by transfinite induction: fα+1 = f ( fα) and fγ for a limit ordinal γ is the least upper bound of the fβ for all β ordinals less than γ. The dual theorem holds for the greatest fixpoint.

Par exemple, in theoretical computer science, least fixed points of monotonic functions are used to define program semantics. Often a more specialized version of the theorem is used, where L is assumed to be the lattice of all subsets of a certain set ordered by subset inclusion. This reflects the fact that in many applications only such lattices are considered. One then usually is looking for the smallest set that has the property of being a fixed point of the function f. Abstract interpretation makes ample use of the Knaster–Tarski theorem and the formulas giving the least and greatest fixpoints.

Knaster–Tarski theorem can be used for a simple proof of the Cantor–Bernstein–Schroeder theorem.[4][5] Weaker versions of the theorem Weaker versions of the Knaster–Tarski theorem can be formulated for ordered sets, but involve more complicated assumptions. Par exemple: Let L be a partially ordered set with the smallest element (bottom) and let f : L → L be an monotonic function. Plus loin, suppose there exists u in L such that f(tu) ≤ u and that any chain in the subset {style d'affichage {xin Lmid xleq f(X),xleq u}} has supremum. Then f admits a least fixed point.

This can be applied to obtain various theorems on invariant sets, par exemple. the Ok's theorem: For the monotone map F : P(X) → P(X) on the family of (fermé) nonempty subsets of X the following are equivalent: (o) F admits A in P(X) s.t. {displaystyle Asubseteq F(UN)} , (je) F admits invariant set A in P(X) c'est à dire. {displaystyle A=F(UN)} , (ii) F admits maximal invariant set A, (iii) F admits the greatest invariant set A.

En particulier, 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 Kantorovitch fixpoint theorem (known also as Tarski-Kantorovitch fixpoint principle) suffices.

Other applications of fixed-point principles for ordered sets come from the theory of differential, integral and operator equations.

Proof Let's restate the theorem.

For a complete lattice {displaystyle langle L,leq rangle } and a monotone function {displaystyle fcolon Lrightarrow L} on L, the set of all fixpoints of f is also a complete lattice {displaystyle langle P,leq rangle } , avec: {displaystyle bigvee P=bigvee {xin Lmid xleq f(X)}} as the greatest fixpoint of f {displaystyle bigwedge P=bigwedge {xin Lmid xgeq f(X)}} as the least fixpoint of f.

Preuve. 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.

Maintenant, laisse {displaystyle u=bigvee D} (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(tu), so x ≤ f(X) ≤ f(tu). Par conséquent, F(tu) is an upper bound of D, but u is the least upper bound, so u ≤ f(tu), c'est à dire. u ∈ D. Alors f(tu) ∈ D (because f(tu) ≤ f(F(tu))) and so f(tu) ≤ u from which follows f(tu) = 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 (Achevée) lattice {displaystyle langle L^{op},geq rangle } . 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.

If a ∈ L and b ∈ L, we'll write [un, b] for the closed interval with bounds a and b: { x ∈ L | a ≤ x ≤ b }. If a ≤ b, alors {displaystyle langle } [un, b], {displaystyle leq rangle } is a complete lattice.

It remains to be proven that P is a complete lattice. Laisser {displaystyle 1_{L}=bigvee L} , W ⊆ P and {displaystyle w=bigvee W} . We′ll show that f([w, 1L]) ⊆ [w, 1L]. En effet, 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, C'est, P is a complete lattice.

See also Modal μ-calculus Notes ^ Alfred Tarski (1955). "A lattice-theoretical fixpoint theorem and its applications". Pacific Journal of Mathematics. 5:2: 285–309. ^ B. Knaster (1928). "Un théorème sur les fonctions d'ensembles". Anne. Soc. Polon. Math. 6: 133–134. With A. Tarski. ^ Anne C. Davis (1955). "A characterization of complete lattices". Pacific Journal of Mathematics. 5 (2): 311–319. est ce que je:10.2140/pjm.1955.5.311. ^ Example 3 en R. Uhl, "Tarski's Fixed Point Theorem", from MathWorld--a Wolfram Web Resource, created by Eric W. Weisstein. ^ Davey, Brian A.; Priestley, Hilary A. (2002). Introduction aux treillis et à l'ordre (2sd éd.). la presse de l'Universite de Cambridge. pp. 63, 4. ISBN 9780521784511. References Andrzej Granas and James Dugundji (2003). Fixed Point Theory. Springer Verlag, New York. ISBN 978-0-387-00173-9. Forster, J. (2003-07-21). Logique, Induction and Sets. 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. est ce que je:10.2977/prims/1195178796. J. Jachymski; L. Gajek; K. Pokarowski (2000). "The Tarski-Kantorovitch principle and the theory of iterated function systems". Taureau. Austral. Math. Soc. 61 (2): 247–261. est ce que je:10.1017/S0004972700022243. E.A. Ok (2004). "Fixed set theory for closed correspondences with applications to self-similarity and games". Nonlinear Anal. 56 (3): 309–330. CiteSeerX 10.1.1.561.4581. est ce que je:10.1016/j.na.2003.08.001. B.S.W. Schröder (1999). "Algorithms for the fixed point property". Theoret. Comput. SCI. 217 (2): 301–358. est ce que je:10.1016/S0304-3975(98)00273-4. 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. est ce que je:10.1016/0362-546X(90)90082-R. R. Uhl (2003). "Smallest and greatest fixed points of quasimonotone increasing mappings". Actualités mathématiques. 248–249: 204–210. est ce que je:10.1002/mana.200310016. 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 Categories: Order theoryFixed points (mathématiques)Fixed-point theoremsTheorems in the foundations of mathematics