Fixed point theorem by Tarski and Knaster

The fixed point theorem by Tarski and Knaster , named after Bronisław Knaster and Alfred Tarski , is a mathematical theorem from the field of association theory .

statement

Let be a complete lattice and a monotonous mapping and be the set of fixed points of in . ${\displaystyle {\mathcal {A}}:=\langle A,\leq \rangle }$ ${\displaystyle f\colon A\to A}$ ${\displaystyle \leq }$ ${\displaystyle P:=\{x\in A\mid f(x)=x\}}$ ${\displaystyle f}$ ${\displaystyle {\mathcal {A}}}$

Then is and is also a complete association. ${\displaystyle P\neq \emptyset }$ ${\displaystyle {\mathcal {P}}:=\langle P,{\leq }|_{P}\rangle }$

Proof idea

${\displaystyle \textstyle \bigcup _{\mathcal {A}}}$be the supremum operation of , and the infimum operation of . ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \textstyle \bigcap _{\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$

The following steps show that for any subsets of an infimum and a supremum in yields. ${\displaystyle {\mathcal {P}}}$ ${\displaystyle P}$ ${\displaystyle P}$

1. ${\displaystyle \textstyle \bigcup _{\mathcal {A}}\{x\in A\mid x\leq f(x)\}}$is the fixed point of , and indeed the largest in . So this is the supremum of . ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle P}$
2. Dual to step 1: is the fixed point of , namely the smallest in . ${\displaystyle \textstyle \bigcap _{\mathcal {A}}\{x\in A\mid f(x)\leq x\}}$ ${\displaystyle f}$ ${\displaystyle A}$
3. There should be a supremum for any subsets . The cases and are already shown in steps 1 and 2. The other cases are now considered. For this purpose, use is made of the fact that with is again a complete lattice, and is a monotonous function that has a smallest fixed point in after step 2 . This is the supremum of . In formulas . ${\displaystyle Y\subseteq P}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle Y=P}$ ${\displaystyle Y=\emptyset }$ ${\displaystyle \langle U,\leq \rangle }$ ${\displaystyle \textstyle U:=\{x\in A\mid \bigcup _{\mathcal {A}}Y\leq x\}}$ ${\displaystyle f|_{U}}$ ${\displaystyle U\to U}$ ${\displaystyle U}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle Y}$ ${\displaystyle \textstyle \bigcup _{\mathcal {P}}Y:=\bigcap _{\mathcal {A}}\{x\in A\mid \bigcup _{\mathcal {A}}Y\cup f(x)\ \leq \ x\}}$
4. Dual to step 3 it is shown that arbitrary subsets of have an -infimum. ${\displaystyle P}$ ${\displaystyle {\mathcal {P}}}$

Consequences

A consequence that is often used is that of the existence of the smallest and largest fixed points of functions that are monotonic with respect to the function. ${\displaystyle \subseteq }$

reversal

The fixed point theorem has a certain inversion in a sentence that Anne C. Davis put forward in 1955:

If every monotonous mapping in a lattice has a fixed point, then it is a complete lattice. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle f\colon {\mathcal {A}}\to {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$

literature

• Garrett Birkhoff : Lattice Theory . 3. Edition. American Mathematical Society , Providence, Rhode Island 1979.
• George Grätzer : General Lattice Theory . 2nd Edition. Birkhäuser Verlag , Basel, Boston, Berlin 1998, ISBN 3-7643-5239-6 ( MR1670580 ).
• LA Skornjakow: Elements of Association Theory (=  Scientific Pocket Books, Series Mathematics / Physics . Volume 130 ). Akademie Verlag , Berlin 1973, ISBN 3-7643-5239-6 .
• Alfred Tarski: A lattice-theoretical fixpoint theorem and its applications . In: Pacific Journal of Mathematics . 5: 2, 1955, pp. 285-309.

Individual evidence

1. ↑ George Graetzer: General Lattice Theory. 1998, p. 73
2. ^ LA Skornjakow: Elements of the association theory. 1973, p. 73
3. ^ Anne C. Davis: A characterization of complete lattices . In: Pacific Journal of Mathematics . tape 5 , 1955, pp. 311-319 ( MR0074377 ).