Editing Knaster–Tarski theorem

{{Short description|Theorem in order and lattice theory}}
In the [[mathematics|mathematical]] areas of [[order theory|order]] and [[lattice theory]], the '''Knaster–Tarski theorem''', named after [[Bronisław Knaster]] and [[Alfred Tarski]], states the following:

:''Let'' (''L'', ≤) ''be a [[complete lattice]] and let f : L → L be an [[Monotonic function#In order theory|order-preserving (monotonic) function]] w.r.t. ≤. Then the [[set (mathematics)|set]] of [[fixed point (mathematics)|fixed point]]s of f in L forms a complete lattice under ≤.''

It was Tarski who stated the result in its most general form,<ref>{{cite journal|author=Alfred Tarski|year=1955|title=A lattice-theoretical fixpoint theorem and its applications|url=https://www.projecteuclid.org/journals/pacific-journal-of-mathematics/volume-5/issue-2/A-lattice-theoretical-fixpoint-theorem-and-its-applications/pjm/1103044538.full|journal=Pacific Journal of Mathematics|volume=5|issue=2 |pages=285&ndash;309|doi=10.2140/pjm.1955.5.285 |doi-access=free}}</ref> 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 (order)|lattice]] of [[subset]]s of a set, the [[power set]] lattice.<ref>{{cite journal | author=B. Knaster | title=Un théorème sur les fonctions d'ensembles | journal=[[Ann. Soc. Polon. Math.]] | year=1928 | volume=6 | pages=133&ndash;134}} With A. Tarski.</ref>

The theorem has important applications in [[formal semantics of programming languages]] and [[abstract interpretation]], as well as in [[game theory]].

A kind of converse of this theorem was proved by [[Anne C. Morel|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.<ref>{{cite journal|author=Anne C. Davis|year=1955|title=A characterization of complete lattices|url=https://www.projecteuclid.org/journals/pacific-journal-of-mathematics/volume-5/issue-2/A-characterization-of-complete-lattices/pjm/1103044539.full|journal=Pacific Journal of Mathematics|volume=5|issue=2|pages=311&ndash;319|doi=10.2140/pjm.1955.5.311|doi-access=free|authorlink=Anne C. Morel}}</ref>

==Consequences: least and greatest fixed points==
Since complete lattices cannot be [[empty set|empty]] (they must contain a [[supremum]] and [[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 fixed point|''least'' fixed point]] (or [[greatest fixed point|''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'', or, equivalently, such that ''f''(''x'') ≤ ''x''; the [[duality (order theory)|dual]] holds for the [[greatest fixpoint]], the greatest element ''x'' such that ''f''(''x'') = ''x''.

If ''f''(lim ''x''<sub>''n''</sub>) = lim ''f''(''x''<sub>''n''</sub>) for all ascending [[sequence]]s ''x''<sub>''n''</sub>, then the least fixpoint of ''f'' is lim ''f''<sup>&thinsp;''n''</sup>(0) where 0 is the [[least element]] of ''L'', thus giving a more "constructive" version of the theorem. (See: [[Kleene fixed-point theorem]].) More generally, if ''f'' is monotonic, then the least fixpoint of ''f'' is the stationary limit of ''f''<sup>&thinsp;α</sup>(0), taking α over the [[ordinal number|ordinals]], where ''f''<sup>&thinsp;α</sup> is defined by [[transfinite induction]]: ''f''<sup>&thinsp;α+1</sup> = ''f'' (''f''<sup>&thinsp;α</sup>) and ''f''<sup>&thinsp;γ</sup> for a limit ordinal γ is the [[least upper bound]] of the ''f''<sup>&thinsp;β</sup> for all β ordinals less than γ.<ref>{{cite journal | last1=Cousot | first1=Patrick | last2=Cousot | first2=Radhia | title=Constructive versions of tarski's fixed point theorems | journal=Pacific Journal of Mathematics | year=1979 | volume=82 | pages=43&ndash;57 | doi=10.2140/pjm.1979.82.43| doi-access=free }}</ref> The dual theorem holds for the greatest fixpoint.

For example, in theoretical [[computer science]], least fixed points of [[Monotonic function#In order theory|monotonic function]]s are used to define [[program semantics]], see ''{{seclink|Least fixed point|Denotational semantics}}'' for an example. 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.

The Knaster–Tarski theorem can be used to give a simple proof of the [[Schröder–Bernstein theorem|Cantor–Bernstein–Schroeder theorem]]<ref>{{MathWorld|author=Uhl, Roland|title=Tarski's Fixed Point Theorem|urlname=TarskisFixedPointTheorem}} Example 3.</ref><ref>{{cite book|last1=Davey|first1=Brian A.|last2=Priestley|first2=Hilary A.|authorlink2=Hilary Priestley|title=Introduction to Lattices and Order|edition=2nd|pages=63, 4|publisher=[[Cambridge University Press]]|year=2002|isbn=9780521784511|title-link= Introduction to Lattices and Order}}</ref> and it is also used in establishing the [[Banach–Tarski paradox]].

==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|date=February 2024}}

:''Let L be a [[partially ordered set]] with a [[least element]] (bottom) and let f'' : ''L'' → ''L be an [[Monotonic function#In order theory|monotonic function]]. Further, suppose there exists u in L such that f''(''u'') ≤ ''u and that any [[Total order#Chains|chain]] in the subset <math>\{x \in L \mid x \leq f(x), x \leq u\}</math> has a supremum. Then f admits a [[least fixed point]].''

This can be applied to obtain various theorems on [[invariant set]]s, e.g. the Ok's theorem:

:''For the monotone map F'' : ''P''(''X''{{hairsp}}) → ''P''(''X''{{hairsp}}) ''on the [[powerset|family]] of (closed) nonempty subsets of X, the following are equivalent: (o) F admits A in P''(''X''{{hairsp}}) ''s.t. <math>A \subseteq F(A)</math>, (i) F admits invariant set A in P''(''X''{{hairsp}}) ''i.e. <math>A = F(A)</math>, (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 system]]s. 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 equation|differential]], [[integral equation|integral]] and [[operator equation|operator]] equations.

==Proof==
Let us restate the theorem.

For a complete lattice <math>\langle L, \le \rangle</math> and a monotone function <math>f\colon L \rightarrow L</math> on ''L'', the set of all fixpoints of ''f'' is also a complete lattice <math>\langle P, \le \rangle</math>, with:
* <math>\bigvee P = \bigvee \{ x \in L \mid x \le f(x) \}</math> as the greatest fixpoint of ''f''
* <math>\bigwedge P = \bigwedge \{ x \in L \mid x \ge f(x) \}</math> as the least fixpoint of ''f''.

''Proof.'' We begin by showing that ''P'' has both a least element and a greatest element. Let {{math|1=''D'' = {{mset|''x'' | ''x'' ≤ ''f''(''x'')}}}} and {{math|''x'' ∈ ''D''}} (we know that at least 0<sub>''L''</sub> belongs to ''D''). Then because ''f'' is monotone we have {{math|''f''(''x'') ≤ ''f''(''f''(''x''))}}, that is {{math|''f''(''x'') ∈ ''D''}}.

Now let <math>u = \bigvee D</math> (''u'' exists because {{math|''D'' ⊆ ''L''}} and ''L'' is a complete lattice). Then for all {{math|''x'' ∈ ''D''}} it is true that {{math|''x'' ≤ ''u''}} and {{math|''f''(''x'') ≤ ''f''(''u'')}}, so {{math|''x'' ≤ ''f''(''x'') ≤ ''f''(''u'')}}. Therefore, ''f''(''u'') is an upper bound of ''D'', but ''u'' is the least upper bound, so {{math|''u'' ≤ ''f''(''u'')}}, i.e. {{math|''u'' ∈ ''D''}}. Then {{math|''f''(''u'') ∈ ''D''}} (because {{math|''f''(''u'') ≤ ''f''(''f''(''u'')))}} and so {{math|''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 <math>\langle L^{op}, \ge \rangle</math>. 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 [[closed interval (order theory)|closed interval]] with bounds ''a'' and {{math|''b'': {{mset|''x'' ∈ ''L'' | ''a'' ≤ ''x'' ≤ ''b''}}}}. If ''a'' ≤ ''b'', then {{angbr|[''a'', ''b''], ≤}} is a complete lattice.

It remains to be proven that ''P'' is a complete lattice. Let <math>1_L = \bigvee L</math>, {{math|''W'' ⊆ ''P''}} and <math>w = \bigvee W</math>. We show that {{math|''f''([''w'', 1<sub>''L''</sub>]) ⊆ [''w'', 1<sub>''L''</sub>]}}. Indeed, for every {{math|''x'' ∈ ''W''}} we have ''x'' = ''f''(''x'') and since ''w'' is the least upper bound of ''W'', {{math|''x'' ≤ ''f''(''w'')}}. In particular {{math|''w'' ≤ ''f''(''w'')}}. Then from {{math|''y'' ∈ [''w'', 1<sub>''L''</sub>]}} follows that {{math|''w'' ≤ ''f''(''w'') ≤ ''f''(''y'')}}, giving {{math|''f''(''y'') ∈ [''w'', 1<sub>''L''</sub>]}} or simply {{math|''f''([''w'', 1<sub>''L''</sub>]) ⊆ [''w'', 1<sub>''L''</sub>]}}. This allows us to look at ''f'' as a function on the complete lattice [''w'', 1<sub>''L''</sub>]. 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<ref>{{Cite journal |last1=Chang |first1=Ching-Lueh |last2=Lyuu |first2=Yuh-Dauh |last3=Ti |first3=Yen-Wu |date=2008-07-23 |title=The complexity of Tarski's fixed point theorem |url=https://www.sciencedirect.com/science/article/pii/S0304397508003812 |journal=Theoretical Computer Science |volume=401 |issue=1 |pages=228–235 |doi=10.1016/j.tcs.2008.05.005 |issn=0304-3975}}</ref> present an algorithm for finding a Tarski fixed-point in a [[Total order|totally-ordered]] lattice, when the order-preserving function is given by a [[value oracle]]. Their algorithm requires <math>O(\log L)</math> queries, where ''L'' is the number of elements in the lattice. In contrast, for a general lattice (given as an oracle), they prove a lower bound of <math>\Omega(L)</math> queries.

Deng, Qi and Ye<ref name=":0" /> present several algorithms for finding a Tarski fixed-point. They consider two kinds of lattices: componentwise ordering and [[lexicographic ordering]]. They consider two kinds of input for the function ''f'': [[value oracle]], or a polynomial function. Their algorithms have the following runtime complexity (where ''d'' is the number of dimensions, and ''N<sub>i</sub>'' is the number of elements in dimension ''i''): 
{| class="wikitable"
!{{ diagonal split header|Lattice|Input }}
!Polynomial function
!Value oracle
|-
|Componentwise
|<math>O(\operatorname{poly}(\log L)\cdot \log N_1 \cdots \log N_d) </math>
|<math>O(\log N_1 \cdots \log N_d) \approx O(\log^d L)</math>
|-
|Lexicographic
|<math>O(\operatorname{poly}(\log L)\cdot \log L) </math>
|<math>O(\log L)</math>
|}
The algorithms are based on [[binary search]]. On the other hand, determining whether a given fixed point is ''unique'' is computationally hard:
{| class="wikitable"
!{{ diagonal split header|Lattice|Input }}
!Polynomial function
!Value oracle
|-
|Componentwise
|[[coNP-complete]]
|<math>\Theta(N_1+\cdots+N_d)</math>
|-
|Lexicographic
|[[coNP-complete]]
|<math>\Theta(L)</math>
|}
For ''d''=2, for componentwise lattice and a value-oracle, the complexity of <math>O(\log^2 L)</math> is optimal.<ref>{{Cite journal |last1=Etessami |first1=Kousha |last2=Papadimitriou |first2=Christos |last3=Rubinstein |first3=Aviad |last4=Yannakakis |first4=Mihalis |date=2020 |editor-last=Vidick |editor-first=Thomas |title=Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria |url=https://drops.dagstuhl.de/opus/volltexte/2020/11703 |journal=11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |series=Leibniz International Proceedings in Informatics (LIPIcs) |location=Dagstuhl, Germany |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |volume=151 |pages=18:1–18:19 |doi=10.4230/LIPIcs.ITCS.2020.18 |doi-access=free |isbn=978-3-95977-134-4|s2cid=202538977 }}</ref> But for ''d''>2, there are faster algorithms:

* Fearnley, Palvolgyi and Savani<ref>{{Cite journal |last1=Fearnley |first1=John |last2=Pálvölgyi |first2=Dömötör |last3=Savani |first3=Rahul |date=2022-10-11 |title=A Faster Algorithm for Finding Tarski Fixed Points |url=https://doi.org/10.1145/3524044 |journal=ACM Transactions on Algorithms |volume=18 |issue=3 |pages=23:1–23:23 |doi=10.1145/3524044 |arxiv=2010.02618 |s2cid=222141645 |issn=1549-6325}}</ref> presented an algorithm using only <math>O(\log^{2\lceil d/3 \rceil} L)</math> queries. In particular, for ''d''=3, only <math>O(\log^2 L)</math> queries are needed.
* Chen and Li<ref>{{Cite book |last1=Chen |first1=Xi |last2=Li |first2=Yuhao |title=Proceedings of the 23rd ACM Conference on Economics and Computation |chapter=Improved Upper Bounds for Finding Tarski Fixed Points |date=2022-07-13 |chapter-url=https://dl.acm.org/doi/10.1145/3490486.3538297 |series=EC '22 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=1108–1118 |doi=10.1145/3490486.3538297 |arxiv=2202.05913 |isbn=978-1-4503-9150-4|s2cid=246823965 }}</ref> presented an algorithm using only <math>O(\log^{\lceil (d+1)/2 \rceil} L)</math> queries.

== Application in game theory ==
Tarski's fixed-point theorem has applications to [[supermodular game]]s.<ref name=":0">{{cite arXiv | eprint=2005.09836 | last1=Dang | first1=Chuangyin | last2=Qi | first2=Qi | last3=Ye | first3=Yinyu | title=Computations and Complexities of Tarski's Fixed Points and Supermodular Games | date=2020 | class=cs.GT }}</ref> A ''supermodular game'' (also called a ''game of strategic complements''<ref>{{Cite journal |last=Vives |first=Xavier |date=1990-01-01 |title=Nash equilibrium with strategic complementarities |url=https://dx.doi.org/10.1016/0304-4068%2890%2990005-T |journal=Journal of Mathematical Economics |volume=19 |issue=3 |pages=305–321 |doi=10.1016/0304-4068(90)90005-T |issn=0304-4068}}</ref>) is a [[Game theory|game]] in which the [[utility function]] of each player has [[increasing differences]], so the [[best response]] of a player is a weakly-increasing function of other players' strategies. For example, consider a game of competition between two firms. Each firm has to decide how much money to spend on research. In general, if one firm spends more on research, the other firm's best response is to spend more on research too. Some common games can be modeled as supermodular games, for example [[Cournot competition]], [[Bertrand competition]] and [[Investment Game]]s.

Because the best-response functions are monotone, Tarski's fixed-point theorem can be used to prove the existence of a [[Pure strategy|pure-strategy]] [[Nash equilibrium]] (PNE) in a supermodular game. Moreover, Topkis<ref>{{Cite journal |last=Topkis |first=Donald M. |date=1979-11-01 |title=Equilibrium Points in Nonzero-Sum n -Person Submodular Games |url=http://epubs.siam.org/doi/10.1137/0317054 |journal=SIAM Journal on Control and Optimization |language=en |volume=17 |issue=6 |pages=773–787 |doi=10.1137/0317054 |issn=0363-0129}}</ref> showed that the set of PNE of a supermodular game is a complete lattice, so the game has a "smallest" PNE and a "largest" PNE.

Echenique<ref>{{Cite journal |last=Echenique |first=Federico |date=2007-07-01 |title=Finding all equilibria in games of strategic complements |url=https://www.sciencedirect.com/science/article/pii/S0022053106001086 |journal=Journal of Economic Theory |volume=135 |issue=1 |pages=514–532 |doi=10.1016/j.jet.2006.06.001 |issn=0022-0531}}</ref> 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<ref name=":0" /> 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==
* [[Modal μ-calculus]]

==Notes==
{{Reflist}}

==References==
*{{cite book | author=Andrzej Granas and [[James Dugundji]] | title=Fixed Point Theory | publisher=[[Springer Science+Business Media|Springer-Verlag]], New York | year=2003 | isbn=978-0-387-00173-9}}
*{{cite book|first=T.|last=Forster|title=Logic, Induction and Sets|isbn=978-0-521-53361-4|date=2003-07-21|publisher=Cambridge University Press }}

==Further reading==
*{{cite journal | author=S. Hayashi | title=Self-similar sets as Tarski's fixed points | journal=Publications of the Research Institute for Mathematical Sciences| year=1985 | volume=21 | pages=1059–1066 | doi=10.2977/prims/1195178796 | issue=5| doi-access=free }}
*{{cite journal |author1=J. Jachymski |author2=L. Gajek |author3=K. Pokarowski | title=The Tarski-Kantorovitch principle and the theory of iterated function systems | journal=Bull. Austral. Math. Soc. | year=2000 | volume=61 | pages=247&ndash;261 | doi=10.1017/S0004972700022243 | issue=2| doi-access=free }}
*{{cite journal | author=E.A. Ok | title=Fixed set theory for closed correspondences with applications to self-similarity and games | journal=Nonlinear Anal. | year=2004 | volume=56 | pages=309–330 | doi=10.1016/j.na.2003.08.001 | issue=3| citeseerx=10.1.1.561.4581 }}
*{{cite journal | author=B.S.W. Schröder | title=Algorithms for the fixed point property | journal=Theoret. Comput. Sci. | year=1999 | volume=217 | pages=301–358 | doi=10.1016/S0304-3975(98)00273-4 | issue=2| doi-access=free }}
*{{cite journal | author=S. Heikkilä | title=On fixed points through a generalized iteration method with applications to differential and integral equations involving discontinuities| journal=Nonlinear Anal. | year=1990 | volume=14 | pages=413–426 | doi=10.1016/0362-546X(90)90082-R | issue=5}}
*{{cite journal | author=R. Uhl | title=Smallest and greatest fixed points of quasimonotone increasing mappings | journal=[[Mathematische Nachrichten]] | year=2003 | volume=248–249 | pages=204–210 | doi=10.1002/mana.200310016| s2cid=120679842 }}

==External links==
* J. B. Nation, [http://people.math.sc.edu/mcnulty/alglatvar/lat.pdf ''Notes on lattice theory''].
*[https://math.stackexchange.com/a/3026040 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

{{DEFAULTSORT:Knaster-Tarski theorem}}
[[Category:Order theory]]
[[Category:Fixed points (mathematics)]]
[[Category:Fixed-point theorems]]
[[Category:Theorems in the foundations of mathematics]]
[[Category:Articles containing proofs]]