mathematics

Knaster–Tarski theorem

Knaster–Tarski theorem is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Knaster–Tarski theorem rather than just read about it. In short: In the mathematical areas of 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 order-preserving (monotonic) function with respect to ≤. Then the set of fixed points of f in L forms a complete lattice under ≤.

Key takeaways

Knaster–Tarski theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Knaster–Tarski theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Knaster–Tarski theorem from memory before moving on to harder problems.

Reference excerpt

In the mathematical areas of 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 order-preserving (monotonic) function with respect to ≤. Then the set of fixed points of f in L forms a complete lattice under ≤. It was Tarski who stated the result in its most general form, 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 of subsets of a set, the power set lattice. The theorem has important applications in formal semantics of programming languages and abstract interpretation, as well as in game theory. It is the logical bedrock for defining the meaning of recursive or repetitive processes in computer science and for proving the existence of equilibrium states in fields like game theory. It essentially proves that when a system follows simple, non-decreasing rules, a stable, self-consistent outcome is always guaranteed to exist. A kind of converse of this theorem was proved by 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.

Consequences: least and greatest fixed points Since complete lattices cannot be 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 and a 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 dual holds for the greatest fixpoint, the greatest element x such that f(x) = x. If f(lim xn) = lim f(xn) for all ascending sequences xn, then the least fixpoint of f is lim f n(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 α(0), taking α over the ordinals, where f α is defined by transfinite induction: f α+1 = f (f α) and f γ for a limit ordinal γ is the least upper bound of the f β for all β ordinals less than γ. The dual theorem holds for the greatest fixpoint. For example, in theoretical computer science, least fixed points of monotonic functions are used to define program semantics, see 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 Cantor–Bernstein–Schroeder theorem 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:

Let L be a partially ordered set with a least element (bottom) and let f : L → L be an monotonic function. Further, suppose there exists u in L such that f(u) ≤ u and that any chain in the subset { x ∈ L ∣ x ≤ f ( x ) , x ≤ u } {\displaystyle \{x\in L\mid x\leq f(x),x\leq u\}} has a supremum. Then f admits a least fixed point. This can be applied to obtain various theorems on invariant sets, e.g. Ok's theorem:

For the monotone map F : P(X ) → P(X ) on the family of (closed) nonempty subsets of X, the following are equivalent: (o) F admits A in P(X ) such that A ⊆ F ( A ) {\displaystyle A\subseteq F(A)} , (i) F admits invariant set A in P(X ) i.e. A = F ( A ) {\displaystyle A=F(A)} , (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 systems. 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, integral and operator equations.

Proof Let us restate the theorem. For a complete lattice ⟨ L , ≤ ⟩ {\displaystyle \langle L,\leq \rangle } and a monotone function f : L → L {\displaystyle f\colon L\rightarrow L} on L, the set of all fixpoints of f is also a complete lattice ⟨ P , ≤ ⟩ {\displaystyle \langle P,\leq \rangle } , with:

⋁ P = ⋁ { x ∈ L ∣ x ≤ f ( x ) } {\displaystyle \bigvee P=\bigvee \{x\in L\mid x\leq f(x)\}} as the greatest fixpoint of f

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Knaster–Tarski theorem

Start with the simplest possible case. Write down what Knaster–Tarski theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Knaster–Tarski theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Knaster–Tarski theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Knaster–Tarski theorem

In research: Knaster–Tarski theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Knaster–Tarski theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Knaster–Tarski theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Fixed-point theorems, Fixed points (mathematics), Order theory, so understanding it makes those chapters shorter.
In everyday life: Look for Knaster–Tarski theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Knaster–Tarski theorem” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Knaster–Tarski theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Knaster–Tarski theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Knaster–Tarski theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Knaster–Tarski theorem in simple terms?

In the mathematical areas of 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 order-preserving (monotonic) function with respect to ≤. Then the set of fixed points of…

Why does Knaster–Tarski theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Knaster–Tarski theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Knaster–Tarski theorem.