Knaster–Tarski theorem
Teorema de Knaster-Tarski
- Date
- 1928/1955 · confidence low
- Place
- Berkeley, California, United States
- Credited to
- Bronisław Knaster and Alfred Tarski
- Field
- Knowledge & symbols
What was discovered
The Knaster–Tarski theorem, in lattice theory, states that if (L, ≤) is a complete lattice and f: L → L is an order-preserving function, then the set of fixed points of f in L also forms a complete lattice. Bronisław Knaster and Alfred Tarski proved a special case in 1928, and Tarski generalized it in 1955.
What it led to
- Standard tool for proving the existence of fixed points in theoretical computer science
- Basis of the denotational semantics of recursion in programming languages
- Use in game theory and economics (existence of equilibria)