Tarski-Knaster theorem

The aim of this article is to prove

Theorem 1 (LATTICE-THEORETICAL FIXPOINT THEOREM).

Let

1. $𝔄=(A,\le )$  be a complete lattice,

2. $f$ be an increasing function on $A$ to $A,$

3. $P$ the set of all fixpoints of $f.$

Then the set $P$ is not empty and the system $\mathrm{(}P\mathrm{,}\mathrm{\le }\mathrm{)}$ is a complete lattice; in particular we have

$$\cup P=\cup E_x[f(x)\ge x]\in P$$

and

$$\cap P=\cap E_x[f(x)\le x]\in P.$$

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

1 Definitions

The symbol $\mathrm{\varnothing }$ denotes the empty set. The symbol $\forall$ is shorthand for ”for all”.

Definition 1.

A poset (partially ordered set) $\mathrm{A}\mathrm{=}\mathrm{(}A\mathrm{,}\mathrm{\le }\mathrm{)}$ consists of a nonempty set $A$ and a relation

$$\le :A\times A⟶\{\text{𝐹𝑎𝑙𝑠𝑒},\text{𝑇𝑟𝑢𝑒}\}$$

that is reflexive ($a\mathrm{\le }a$ $\mathrm{\forall }a\mathrm{\in }A$), antisymmetric ($\mathrm{\forall }a\mathrm{,}b\mathrm{\in }A\mathrm{,}$ if $a\mathrm{\le }b$ and $b\mathrm{\le }a\mathrm{,}$ then $a\mathrm{=}b$). and transitive  ($\mathrm{\forall }a\mathrm{,}b\mathrm{,}c\mathrm{\in }A\mathrm{,}$ if $a\mathrm{\le }b$ and $b\mathrm{\le }c\mathrm{,}$ then $a\mathrm{\le }c$).

Definition 2.

If $\mathrm{A}\mathrm{=}\mathrm{(}A\mathrm{,}\mathrm{\le }\mathrm{)}$ is a poset and $B$ is a nonempty subset of $A\mathrm{,}$ then $\sup \mathit{}\mathrm{(}B\mathrm{)}$ is an element of $A\mathrm{,}$ if it exists, with these properties:

1. $\forall b\in B,b\le sup(B)$, (in shorthand, $B\le sup(B)$).

2. If $a\in A$ and $B\le a,$ then $sup(B)\le a.$

Similarly $\inf \mathit{}\mathrm{(}B\mathrm{)}$ is an element of $A\mathrm{,}$ if it exists, with these properties:

1. $inf(B)\le B,$

2. If $a\in A$ and $a\le B,$ then $a\le inf(B).$

Theorem 2.

If $\sup \mathit{}\mathrm{(}B\mathrm{)}$ exists, then it is unique; if $\inf \mathit{}\mathrm{(}B\mathrm{)}$ exists, it is unique.

Definition 3.

Let $\mathrm{A}\mathrm{=}\mathrm{(}A\mathrm{,}\mathrm{\le }\mathrm{)}$ be a poset. Then $\mathrm{A}$ is a lattice if $\mathrm{\forall }a\mathrm{,}b\mathrm{\in }A\mathrm{,}$ the set $\mathrm{\{}a\mathrm{,}b\mathrm{\}}$ has a $\sup$ and an $\inf \mathrm{.}$ We write

$$a\cup b=sup(\{a,b\})\mathit{\hspace{1em}}\text{𝑎𝑛𝑑}\mathit{\hspace{1em}}a\cap b=inf(\{a,b\}).$$

As an exercise, prove the following:

Theorem 3.

Let $\mathrm{A}\mathrm{=}\mathrm{(}A\mathrm{,}\mathrm{\le }\mathrm{)}$ be a lattice. Then

1. $a\cup b=b\cup a,a\cap b=b\cap a$

2. $(a\cup b)\cup c=a\cup (b\cup c),(a\cap b)\cap c=a\cap (b\cap c)$

3. $a\cup (b\cap c)\le (a\cup b)\cap (a\cup c).\mathit{\hspace{1em}\hspace{1em}}(a\cap b)\cup (a\cap c)\le a\cap (b\cup c).$

Definition 4.

A poset $\mathrm{A}\mathrm{=}\mathrm{(}A\mathrm{,}\mathrm{\le }\mathrm{)}$ is a complete lattice if for each nonempty $B\mathrm{\subseteq }A\mathrm{,}$ both $\sup \mathit{}\mathrm{(}B\mathrm{)}$ and $\inf \mathit{}\mathrm{(}B\mathrm{)}$ 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 theorem, as it is in [6]:

Theorem 4 (LATTICE-THEORETICAL FIXPOINT THEOREM).

Let

1. $𝔄=(A,\le )$  be a complete lattice,

2. $f$ be an increasing function on $A$ to $A,$

3. $P$ the set of all fixpoints of $f.$

Then the set $P$ is not empty and the system $\mathrm{(}P\mathrm{,}\mathrm{\le }\mathrm{)}$ is a complete lattice; in particular we have

$$\cup P=\cup E_x[f(x)\ge x]\in P$$

and

$$\cap P=\cap E_x[f(x)\le x]\in P.$$

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

Theorem 5.

Let $\mathrm{A}\mathrm{=}\mathrm{(}A\mathrm{,}\mathrm{\le }\mathrm{)}$ be a complete lattice. Let $f$ be an increasing function on $A$ to $A\mathrm{,}$ that is, whenever $a\mathrm{\le }b\mathrm{,}$ then $f\mathit{}\mathrm{(}a\mathrm{)}\mathrm{\le }f\mathit{}\mathrm{(}b\mathrm{)}\mathrm{.}$ Let $P$ be the set of all fixed points of $f\mathrm{:}$

$$P=\{a\in A|f(a)=a\}.$$

Then

1. $P\ne \mathrm{\varnothing }$.

2. The system $𝔓=(P,$ $\le )$ is a complete lattice.

3. Set $B=\{b\in A|b\le f(b)\}$. Then $B\ne \mathrm{\varnothing }$ and $sup(B)=sup(P)\in P.$

4. Set $C=\{c\in A|f(c)\le c\}$. Then $C\ne \mathrm{\varnothing }$and $inf(C)=inf(P)\in P.$

Lemma 1.

Let $\mathrm{A}\mathrm{=}\mathrm{(}A\mathrm{,}\mathrm{\le }\mathrm{)}$ be a complete lattice and $\mathrm{\varnothing }\mathrm{\ne }{A}_{\mathrm{0}}\mathrm{\subseteq }A\mathrm{.}$ Let

$$D=\{d\in A|d\le A_0\},E=\{e\in A|A_0\le e\}.$$

($d\mathrm{\le }{A}_o$ means $d\mathrm{\le }{a}_{\mathrm{0}}$ $\mathrm{\forall }{a}_{\mathrm{0}}\mathrm{\in }{A}_{\mathrm{0}}\mathrm{.}$) Then both $B$ and $C$ are complete lattices, with $\mathrm{\le }$  inherited from that of $A\mathrm{.}$

Proof (of Lemma).

We’ll do the case of $D;$ that for $E$ is similar (dual). First, $D\ne \mathrm{\varnothing }$ because $inf(A)\in D.$ Suppose $\mathrm{\varnothing }\ne G\subseteq D.$ Obviously

$$inf(G)\le g\le A_0$$

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

Proof (of Theorem).

$B\ne \mathrm{\varnothing }$ because $inf(A)\in B.$ Hence $b_1=sup(B)$ exists. If $b\in B,$ then $b\le b_1,$ which implies

$$f(b)\le f(b_1).$$

because $f$ is increasing., so

$$b\le f(b)\le f(b_1).$$

This is true $\forall$ $b\in B.$ Hence

$$b_1=sup(B)\le f(b_1).$$

Therefore $b_1\in B.$ Because $f$ is increasing, this implies

$$f(b_1)\le f(f(b_1)),$$

from which $f(b_1)\in B.$ Hence $f(b_1)\le sup(B)=b_1.$ From

$$b_1\le f(b_1)\le b_1$$

we have $f(b_1)=b_1,$ that is, $b_1\in P.$ This settles (1): $P\ne \mathrm{\varnothing },$ and incidentally proves $sup(B)\in P.$

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

Next we prove (2). Let $\mathrm{\varnothing }\ne P_0\subseteq P.$ Set

$$Q=\{q\in A|q\le P_0\}.$$

By the Lemma, $Q$ is a complete lattice. If $q\in Q,$ then $\forall p_0\in P_0,$ we have $q\le p_0,$ hence

$$f(q)\le f(p_0)=p_0,$$

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

$$f:Q⟶Q.$$

By what we have already proved for $A,$ applied to $Q,$ we have $sup(Q)\in Q,$ and $sup(Q)$ is a fixed point of $f.$ That is, $sup(Q)\in P.$ But obviously $sup(Q)=inf(P_0),$ so $inf(P_0)\in P$ Similarly $sup(P_0)\in 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 converse of this theorem was proved by Anne C. Davis [1]: If every order-preserving function $f:L\to L$ has a fixed point, then $L$ is a complete lattice.

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 theorem
Synonym	Knaster-Tarski theorem
Related topic	lattice
Related topic	completelattice
Related topic	fixedpoint
Related topic	ProofOfSchroederBernsteinTheoremUsingTarskiKnasterTheorem
Related topic	Lattice
Related topic	CompleteLattice