5.2 Knaster-Tarski fixed-point theorem

Fixed points and monotone functions are key concepts in lattice theory. They help us understand how functions behave on ordered structures, with fixed points representing stable states and monotone functions preserving order.

The Knaster-Tarski theorem is a powerful result for complete lattices. It guarantees that monotone functions on complete lattices always have fixed points, forming a complete lattice themselves. This theorem has wide-ranging applications in mathematics and computer science.

Fixed Points and Monotone Functions

Properties and Definitions

Top images from around the web for Properties and Definitions

• 

  Fixed Point Theorem for Non-self Mapping in Cone Metric Space View original

  Is this image relevant?

• 

  Generalization of Common Fixed Point Theorems for Two Mappings View original

  Is this image relevant?

• 

  Fixed Point Theorem for Non-self Mapping in Cone Metric Space View original

  Is this image relevant?

• 

  Generalization of Common Fixed Point Theorems for Two Mappings View original

  Is this image relevant?

1 of 2

Top images from around the web for Properties and Definitions

• 

  Fixed Point Theorem for Non-self Mapping in Cone Metric Space View original

  Is this image relevant?

• 

  Generalization of Common Fixed Point Theorems for Two Mappings View original

  Is this image relevant?

• 

  Fixed Point Theorem for Non-self Mapping in Cone Metric Space View original

  Is this image relevant?

• 

  Generalization of Common Fixed Point Theorems for Two Mappings View original

  Is this image relevant?

1 of 2

• Fixed point a point $x$ in the domain of a function $f$ such that $f(x) = x$
• Monotone function a function between partially ordered sets that preserves the given order
  • If $f: P \to Q$ is a function between two partially ordered sets $(P, \leq_P)$ and $(Q, \leq_Q)$, then $f$ is monotone if for all $a, b \in P$, $a \leq_P b$ implies $f(a) \leq_Q f(b)$
• Least fixed point the smallest element of the set of fixed points of a function, if it exists
  • For a function $f: P \to P$ on a partially ordered set $(P, \leq)$, an element $x \in P$ is the least fixed point of $f$ if $x$ is a fixed point of $f$ and for every fixed point $y$ of $f$, $x \leq y$
• Greatest fixed point the largest element of the set of fixed points of a function, if it exists
  • For a function $f: P \to P$ on a partially ordered set $(P, \leq)$, an element $x \in P$ is the greatest fixed point of $f$ if $x$ is a fixed point of $f$ and for every fixed point $y$ of $f$, $y \leq x$

Examples

• Consider the function $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^2$
  • The fixed points of $f$ are the solutions to the equation $x = x^2$, which are $x = 0$ and $x = 1$
  • $f$ is not monotone on $\mathbb{R}$ because, for example, $-1 \leq 0$ but $f(-1) = 1 \not\leq 0 = f(0)$
• Let $f: \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$ be defined by $f(X) = \{0\} \cup \{n+1 \mid n \in X\}$ for $X \subseteq \mathbb{N}$
  • $f$ is monotone with respect to set inclusion $\subseteq$ because if $A \subseteq B$, then $f(A) \subseteq f(B)$
  • The least fixed point of $f$ is $\mathbb{N}$, and the greatest fixed point is also $\mathbb{N}$

Knaster-Tarski Theorem

Statement and Significance

• Knaster-Tarski theorem states that if $(L, \leq)$ is a complete lattice and $f: L \to L$ is monotone, then the set of fixed points of $f$ is also a complete lattice
  • This theorem guarantees the existence of least and greatest fixed points for monotone functions on complete lattices
  • It has important applications in order theory, logic, and computer science
• Complete partial order a partially ordered set $(P, \leq)$ in which every directed subset $D \subseteq P$ has a least upper bound (supremum) in $P$
  • Complete lattices are a special case of complete partial orders

Proof Outline

• Constructive proof a proof that not only shows the existence of a mathematical object but also provides a method for finding or constructing it
  • The proof of the Knaster-Tarski theorem is constructive and proceeds as follows:
    1. Define the set $S = \{x \in L \mid x \leq f(x)\}$
    2. Show that $S$ is non-empty and closed under arbitrary infima (greatest lower bounds)
    3. Let $a = \inf S$ and show that $a$ is a fixed point of $f$
    4. Prove that $a$ is the least fixed point of $f$
    5. By duality, the set of fixed points also has a greatest element

Examples and Applications

• In the lattice of subsets of a set $X$ ordered by inclusion $(\mathcal{P}(X), \subseteq)$, the Knaster-Tarski theorem can be used to show the existence of least and greatest fixed points for monotone functions $f: \mathcal{P}(X) \to \mathcal{P}(X)$
  • This has applications in the theory of inductive definitions and recursive constructions
• The Knaster-Tarski theorem is used in the semantics of programming languages to define the meaning of recursive definitions and to prove the existence of least and greatest solutions to recursive equations
  • For example, in domain theory, the theorem is used to construct the denotational semantics of programming languages with recursive types and functions