Tarski-Knaster theorem

The aim of this article is to prove



  1. (i)

    𝔄=(A,)  be a complete latticeMathworldPlanetmath,

  2. (ii)

    f be an increasing function on A to A,

  3. (iii)

    P the set of all fixpoints of f.

Then the set P is not empty and the system (P,) is a complete lattice; in particular we have




This article follows, with clarification, Tarski’s original 1955 article [6], which may not be available to some readers.

1 Definitions

The symbol denotes the empty setMathworldPlanetmath. The symbol is shorthand for ”for all”.

Definition 1.

A poset (partially ordered setMathworldPlanetmath) A=(A,) consists of a nonempty set A and a relationMathworldPlanetmath


that is reflexiveMathworldPlanetmathPlanetmath (aa aA), antisymmetric (a,bA, if ab and ba, then a=b). and transitiveMathworldPlanetmathPlanetmathPlanetmath  (a,b,cA, if ab and bc, then ac).

Definition 2.

If A=(A,) is a poset and B is a nonempty subset of A, then sup(B) is an element of A, if it exists, with these properties:

  1. 1.

    bB,bsup(B), (in shorthand, Bsup(B)).

  2. 2.

    If aA and Ba, then sup(B)a.

Similarly inf(B) is an element of A, if it exists, with these properties:

  1. (3)


  2. (4)

    If aA and aB, then ainf(B).

Theorem 2.

If sup(B) exists, then it is unique; if inf(B) exists, it is unique.

Definition 3.

Let A=(A,) be a poset. Then A is a latticeMathworldPlanetmath if a,bA, the set {a,b} has a sup and an inf. We write


As an exercise, prove the following:

Theorem 3.

Let A=(A,) be a lattice. Then

  1. 1.


  2. 2.


  3. 3.

    a(bc)(ab)(ac).  (ab)(ac)a(bc).

Definition 4.

A poset A=(A,) is a complete lattice if for each nonempty BA, both sup(B) and inf(B) exist.

In particular, this is the case when B={a,b}, so a complete lattice is a lattice.

2 The Tarski-Knaster Theorem

Statement of the theoremMathworldPlanetmath, as it is in [6]:



  1. (i)

    𝔄=(A,)  be a complete lattice,

  2. (ii)

    f be an increasing function on A to A,

  3. (iii)

    P the set of all fixpoints of f.

Then the set P is not empty and the system (P,) is a complete lattice; in particular we have




The symbols P and P are what I am calling sup(P) and inf(C). Now let me restate the theorem:

Theorem 5.

Let A=(A,) be a complete lattice. Let f be an increasing function on A to A, that is, whenever ab, then f(a)f(b). Let P be the set of all fixed pointsPlanetmathPlanetmath of f:



  1. 1.


  2. 2.

    The system 𝔓=(P, ) is a complete lattice.

  3. 3.

    Set B={bA|bf(b)}. Then B and sup(B)=sup(P)P.

  4. 4.

    Set C={cA|f(c)c}. Then Cand inf(C)=inf(P)P.

Lemma 1.

Let A=(A,) be a complete lattice and A0A. Let


(dAo means da0 a0A0.) Then both B and C are completePlanetmathPlanetmathPlanetmathPlanetmath lattices, with  inherited from that of A.

Proof (of Lemma).

We’ll do the case of D; that for E is similar (dual). First, D because inf(A)D. Suppose GD. Obviously


for any gG, so inf(G)D. As gA0 for all gG, we have sup(G)A0 by (2) in the definition of sup. So sup(G)D. As G was any nonempty subset of D, these statements say that D is a complete lattice. ∎

Proof (of Theorem).

B because inf(A)B. Hence b1=sup(B) exists. If bB, then bb1, which implies


because f is increasing., so


This is true bB. Hence


Therefore b1B. Because f is increasing, this implies


from which f(b1)B. Hence f(b1)sup(B)=b1. From


we have f(b1)=b1, that is, b1P. This settles (1): P, and incidentally proves sup(B)P.

From this, sup(B)sup(P). But obviously PB, so sup(P)sup(B). Therefore sup(P)=sup(B), completing the proof of (3). Statement (4) is proved similarly (or dually).

Next we prove (2). Let P0P. Set


By the Lemma, Q is a complete lattice. If qQ, then p0P0, we have qp0, hence


that is, f(q)Q. In other words,


By what we have already proved for A, applied to Q, we have sup(Q)Q, and sup(Q) is a fixed point of f. That is, sup(Q)P. But obviously sup(Q)=inf(P0), so inf(P0)P Similarly sup(P0)P, completing the proof of (2): P is a complete lattice. ∎

This theorem was proved by A. Tarski [6]. A special case of this theorem (for lattices of sets) appeared in a paper of B. Knaster [3]. Kind of converseMathworldPlanetmath of this theorem was proved by Anne C. Davis [1]: If every order-preserving function f:LL has a fixed point, then L is a complete lattice.


  • 1 Anne C. Davis, A characterizationMathworldPlanetmath of complete lattices., Pac. J. Math. 5 (1955), 311–319.
  • 2 Thomas Forster, Logic, inductionMathworldPlanetmath and sets, Cambridge University Press, Cambridge, 2003.
  • 3 B. Knaster, Un théorème sur les fonctions d’ensembles., Annales Soc. Polonaise 6 (1928), 133–134.
  • 4 M. Kolibiar, A. Legéň, T. Šalát, and Š. Znám, Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992 (Slovak).
  • 5 J. B. Nation: http://bigcheese.math.sc.edu/ mcnulty/alglatvar/Notes on lattice theory
  • 6 Alfred Tarski, A lattice-theoretical fixpoint theorem and its applications., Pac. J. Math. 5 (1955), 285–309.
  • 7 Wikipedia’s entry on http://en.wikipedia.org/wiki/Knaster-Tarski_theoremKnaster-Tarski theorem
Title Tarski-Knaster theorem
Canonical name TarskiKnasterTheorem
Date of creation 2013-03-22 15:30:19
Last modified on 2013-03-22 15:30:19
Owner kompik (10588)
Last modified by kompik (10588)
Numerical id 18
Author kompik (10588)
Entry type Theorem
Classification msc 06B99
Synonym Tarski theoremMathworldPlanetmath
Synonym Knaster-Tarski theorem
Related topic lattice
Related topic completelattice
Related topic fixedpoint
Related topic ProofOfSchroederBernsteinTheoremUsingTarskiKnasterTheorem
Related topic Lattice
Related topic CompleteLattice