Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (195)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

Tarski-Knaster theorem

(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): be an increasing function on to
(iii): the set of all fixpoints of

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

$\displaystyle \cup P=\cup E_{x}[f(x)\geq x]\in P$

and

$\displaystyle \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 and a relation

$\displaystyle \leq:\ A\times A\longrightarrow\{$ False $\displaystyle ,\$ True $\displaystyle \}$

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 ). 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 is a nonempty subset of then $\sup(B)$ is an element of 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 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

$\displaystyle a\cup b=\sup(\{a,\ b\})$ and $\displaystyle \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): be an increasing function on to
(iii): the set of all fixpoints of

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

$\displaystyle \cup P=\cup E_{x}[f(x)\geq x]\in P$

and

$\displaystyle \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 be an increasing function on to that is, whenever $a\leq b,$ then $f(a)\leq f(b).$ Let be the set of all fixed points of

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

Then

$P\neq\emptyset$ .
The system $\mathfrak{P}=(P,$ $\leq)$ is a complete lattice.
Set $B=\{\ b\in A\ \vert\ b\leq f(b)\ \}$ . Then $B\neq\emptyset$ and $\sup(B)=\sup(P)\in P.$
Set $C=\{\ c\in A\ \vert\ 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

$\displaystyle D=\{d\in A\ \vert\ d\leq A_{0}\},\qquad E=\{e\in A\ \vert\ A_{0}\leq e\}.$

( $d\leq A_{o}$ means $d\leq a_{0}$ $\forall a_{0}\in A_{0}.$ ) Then both and are complete lattices, with $\leq$ inherited from that of

Proof. [Proof (of Lemma)]We'll do the case of

that for

is similar (dual). First, $D\neq\emptyset$ because $\inf(A)\in D.$ Suppose $\emptyset\neq G\subseteq D.$ Obviously

$\displaystyle \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

was any nonempty subset of

these statements say that

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

$\displaystyle f(b)\leq f(b_{1}).$

because

is increasing., so

$\displaystyle b\leq f(b)\leq f(b_{1}).$

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

$\displaystyle b_{1}=\sup(B)\leq f(b_{1}).$

Therefore $b_{1}\in B.$ Because

is increasing, this implies

$\displaystyle 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

$\displaystyle 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

$\displaystyle Q=\{\ q\in A\ \vert\ q\leq P_{0}\ \}.$

By the Lemma,

is a complete lattice. If $q\in Q,$ then $\forall\ p_{0}\in P_{0},$ we have $q\leq p_{0},$ hence

$\displaystyle f(q)\leq f(p_{0})=p_{0}\ ,$

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

$\displaystyle f:\ Q\longrightarrow Q.$

By what we have already proved for

applied to

we have $\sup(Q)\in Q,$ and $\sup(Q)$ is a fixed point of

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):

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 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éň, 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

Anyone with an account can edit this entry. Please help improve it!

"Tarski-Knaster theorem" is owned by kompik. [ full author list (6) ]

(view preamble)

Other names:

Tarski theorem, Knaster-Tarski theorem

Attachments:: proof of Schroeder-Bernstein theorem using Tarski-Knaster theorem (Proof) by kompik

Log in to rate this entry.
(view current ratings)

Cross-references: order-preserving function, converse, implies, similar, proof, complete, fixed points, lattice, properties, subset, transitive, antisymmetric, Reflexive, relation, poset, empty set, function, increasing, complete lattice
There is 1 reference to this entry.

This is version 15 of Tarski-Knaster theorem, born on 2005-09-10, modified 2007-12-06.
Object id is 7366, canonical name is TarskiKnasterTheorem.
Accessed 5570 times total.

Classification:

AMS MSC:

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

Pending Errata and Addenda

None.

Discussion

forum policy

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 pahio 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 mps on 2006-11-23 11:37:40

Interact