This is a place holder for potential sponsor logos.

Tarski-Knaster theorem

The aim of this article is to prove

Theorem 1 (LATTICE-THEORETICAL FIXPOINT THEOREM) Let

(i): $\mathfrak{A}=(A,\ \leq)$ be a complete lattice,
(ii): $f$ be an increasing function on $A$ to $A,$
(iii): $P$ the set of all fixpoints of $f.$

Then the set $P$ is not empty and the system $(P,\ \leq)$ is a complete lattice; in particular we have$$ \cup P=\cup E_{x}[f(x)\geq x]\in P$$ and$$ \cap P=\cap E_{x}[f(x)\leq x]\in P.$$

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

Definitions

The symbol $\emptyset$ denotes the empty set. The symbol $\forall$ is shorthand for "for all".

Definition 1 A poset (partially ordered set) $\mathfrak{A}=(A,\ \leq)$ consists of a nonempty set $A$ and a relation$$ \leq:\ A\times A\longrightarrow\{\text{False},\ \text{True}\}$$ that is reflexive ($a\leq a$ $\forall a\in A$ ), antisymmetric ($\forall \ a,\ b\in A,$ if $a\leq b$ and $b\leq a,$ then $a=b$ ). and transitive ($\forall\ a,\ b,\ c\in A,$ if $a\leq b$ and $b\leq c,$ then $a\leq c$ ).

Definition 2 If $\mathfrak{A}=(A,\ \leq)$ 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:

$\forall\ b\in B,~b\leq\sup(B)$ , (in shorthand, $B\leq\sup(B)$ ).
If $a\in A$ and $B\leq a,$ then $\sup(B)\leq a.$

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

(3): $\inf(B)\leq B,$
(4): If $a\in A$ and $a\leq B,$ then $a\leq\inf(B).$

Theorem 2 If $\sup(B)$ exists, then it is unique; if $\inf(B)$ exists, it is unique.

Definition 3 Let $\mathfrak{A}=(A,\ \leq)$ be a poset. Then $\mathfrak{A}$ is a lattice if $\forall\ a,\ b\in A,$ the set $\{a,\ b\}$ has a $\sup$ and an $\inf.$ We write$$ a\cup b=\sup(\{a,\ b\})\quad\text{and}\quad a\cap b=\inf(\{a,\ b\}).$$

As an exercise, prove the following:

Theorem 3 Let $\mathfrak{A}=(A,\ \leq)$ be a lattice. Then

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

Definition 4 A poset $\mathfrak{A}=(A,\ \leq)$ is a complete lattice if for each nonempty $B\subseteq A,$ both $\sup(B)$ and $\inf(B)$ exist.

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

The Tarski-Knaster Theorem

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

Theorem 4 (LATTICE-THEORETICAL FIXPOINT THEOREM) Let

(i): $\mathfrak{A}=(A,\ \leq)$ be a complete lattice,
(ii): $f$ be an increasing function on $A$ to $A,$
(iii): $P$ the set of all fixpoints of $f.$

Then the set $P$ is not empty and the system $(P,\ \leq)$ is a complete lattice; in particular we have$$ \cup P=\cup E_{x}[f(x)\geq x]\in P$$ and$$ \cap P=\cap E_{x}[f(x)\leq 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 $\mathfrak{A}=(A,\ \leq)$ be a complete lattice. Let $f$ be an increasing function on $A$ to $A,$ that is, whenever $a\leq b,$ then $f(a)\leq f(b).$ Let $P$ be the set of all fixed points of $f:$ $$ P=\{\ a\in A\ |\ f(a)=a\ \}.$$ Then

$P\neq\emptyset$ .
The system $\mathfrak{P}=(P,$ $\leq)$ is a complete lattice.
Set $B=\{\ b\in A\ |\ b\leq f(b)\ \}$ . Then $B\neq\emptyset$ and $\sup(B)=\sup(P)\in P.$
Set $C=\{\ c\in A\ |\ f(c)\leq c\ \}$ . Then $C\neq\emptyset\ $ and $\inf(C)=\inf(P)\in P.$

Lemma 1 Let $\mathfrak{A}=(A,\ \leq)$ be a complete lattice and $\emptyset\neq A_{0}\subseteq A.$ Let$$ D=\{d\in A\ |\ d\leq A_{0}\},\qquad E=\{e\in A\ |\ A_{0}\leq e\}.$$ ($d\leq A_{o}$ means $d\leq a_{0}$ $\forall a_{0}\in A_{0}.$ ) Then both $B$ and $C$ are complete lattices, with $\leq$ inherited from that of $A.$

Proof. [Proof (of Lemma)]We'll do the case of $D;$ that for $E$ is similar (dual). First, $D\neq\emptyset$ because $\inf(A)\in D.$ Suppose $\emptyset\neq G\subseteq D.$ Obviously$$ \inf(G)\leq g\leq A_{0}$$ for any $g\in G,$ so $\inf(G)\in D.$ As $g\leq A_{0}$ for all $g\in G,$ we have $\sup(G)\leq 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. $\qedsymbol$

Proof. [Proof (of Theorem)]$B\neq\emptyset$ because $\inf(A)\in B.$ Hence $b_{1} =\sup(B)$ exists. If $b\in B,$ then $b\leq b_{1},$ which implies$$ f(b)\leq f(b_{1}).$$ because $f$ is increasing., so$$ b\leq f(b)\leq f(b_{1}).$$ This is true $\forall$ $b\in B.$ Hence$$ b_{1}=\sup(B)\leq f(b_{1}).$$ Therefore $b_{1}\in B.$ Because $f$ is increasing, this implies$$ f(b_{1})\leq f(f(b_{1})),$$ from which $f(b_{1})\in B.$ Hence $f(b_{1})\leq\sup(B)=b_{1}.$ From$$ b_{1}\leq f(b_{1})\leq b_{1}$$ we have $f(b_{1})=b_{1},$ that is, $b_{1}\in P.$ This settles (1): $P\neq \emptyset,$ and incidentally proves $\sup(B)\in P.\smallskip$

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

Next we prove (2). Let $\emptyset\neq P_{0}\subseteq P.$ Set$$ Q=\{\ q\in A\ |\ q\leq P_{0}\ \}.$$ By the Lemma, $Q$ is a complete lattice. If $q\in Q,$ then $\forall\ p_{0}\in P_{0},$ we have $q\leq p_{0},$ hence$$ f(q)\leq f(p_{0})=p_{0}\ ,$$ that is, $f(q)\in Q.$ In other words,$$ f:\ Q\longrightarrow 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. $\qedsymbol$

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\colon L\to L$ has a fixed point, then $L$ is a complete lattice.

Bibliography

1: Anne C. Davis, A characterization of complete lattices., Pac. J. Math. 5 (1955), 311-319.
2: Thomas Forster, Logic, induction 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én, T. Šalát, and Š. Znám, Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992 (Slovak).
5: J. B. Nation: 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 Knaster-Tarski theorem

Tarski-Knaster theorem is owned by kompik, matte, Thomas Foregger, Chi Woo, yark, Roger Lipsett, .

How to Cite This Entry

kompik, matte, Thomas Foregger, Chi Woo, yark, Roger Lipsett, . "Tarski-Knaster theorem" (version 15). PlanetMath.org. Freely available at http://planetmath.org/TarskiKnasterTheorem.html.

Classification

AMS MSC:

06B99 (Order, lattices, ordered algebraic structures :: Lattices :: Miscellaneous)

Pending Errata and Addenda

None.

Interact

Discussion

Correction? by slotik on 2006-11-20 18:05:05

Maybe I don't understand the proof correctly. But it seems to me that the first paragraph is about proving that at least one fixpoint exists, not about proving that $L$ is nonempty.

Also, I'm not quite sure if this holds: f(inf F) = inf f(F)
Counterexample: take a lattice

L = {a, b, c, d, e}

with

a < b, b < c, b < d, c < e, d < e

and a mapping f (I believe it's order-preserving)

f(a) = a
f(b) = a
f(c) = c
f(d) = d
f(e) = e

Then we have f(inf {c, d}) = f(b) = a and inf{f(c), f(d)} = inf{c, d} = a.

Is there a mistake in the proof or in my counterexample? Nevertheless, I still believe the theorem holds :o)

[ reply | up ]

Re: Correction? by kompik on 2006-11-21 15:29:19

Correction by slayerchange on 2006-09-24 07:00:22

This proof is not right. First of all there are some mistakes . Please change M and A, I mean delete all M's and let tem be A.

Second, f(x) should not be in the set M , so we cannot say
f(x)<=f(x_0)

[ reply | up ]

Re: Correction by slayerchange on 2006-09-24 07:02:54
- Re: Correction by kompik on 2006-09-24 12:15:13

Reference in a foreign language by kompik on 2005-09-10 10:56:48

I wasn't sure about including the reference in Slovak language. It was the book where I've learned about this topic and I somehow felt, that this book should be credited. But for English-speaking readers this reference is useless. What would you say?

[ reply | up ]

Re: Reference in a foreign language by J. Pahikkala on 2005-09-11 12:57:45

Another form of this theorem by kompik on 2005-09-10 10:56:07

I knew this theorem in the following form: If $L$ is a complete lattice and $f:L\to L$ is an order-preserving map, then there exists at least one fixed point of $f$. I found the formulation included here (set of fixed point is a complete lattice) on wikipedia, I don't have any textbook reference to it.

[ reply | up ]

Re: Another form of this theorem by kompik on 2006-11-23 03:43:40
- Re: Another form of this theorem by Michael Slone on 2006-11-23 11:37:40

Username:
Password:

Register
I've forgotten my login details

Login

Tarski-Knaster theorem

Definitions

The Tarski-Knaster Theorem

Bibliography

How to Cite This Entry

Classification

Tags

Pending Errata and Addenda

Interact

Discussion