On Convergence of Sequences in Complete Lattices
- PDF / 211,885 Bytes
- 5 Pages / 439.642 x 666.49 pts Page_size
- 94 Downloads / 184 Views
On Convergence of Sequences in Complete Lattices Wojciech Olszewski1 Received: 4 February 2020 / Accepted: 8 August 2020 / © Springer Nature B.V. 2020
Abstract We generalize the famous Tarski result by showing that: if X is a complete lattice, and f : X → X is an order-preserving mapping, then for all points x ∈ X, the limit superior and the limit inferior of the (possibly transfinite) sequence of iterations x, f (x), f 2 (x)..., f β (x),... are fixed points of f . These limits are the sharp fixed-point bounds between which sufficiently large transfinite iterations are located. Keywords Tarski fixed-point theorem
1 Introduction The celebrated Tarski [9] fixed-point theorem1 says that an increasing (or order-preserving) mapping f on a complete lattice has a fixed point. Moreover, the set of fixed points is also a complete lattice. The lowest fixed point is the “limit” of the sequence of iterations of the lowest element of the lattice, and the highest fixed point is the “limit” of the sequence of iterations of the highest element of the lattice. In the general case, these sequences have to be transfinite, but in applications, it often suffices to study sequences indexed by natural numbers. The Tarski theorem has numerous applications in studying simple discrete dynamic processes. In economics, it has also been used to prove equilibrium existence in supermodular games (see Topkis [10] and Vives [11]), to prove the existence of stable matchings
1 This result is also known as the Knaster-Tarski theorem. See Knaster and Tarski [6]. In economics, authors typically refer to it as the Tarski theorem.
The author is grateful to the editor and referees for their important suggestions regarding exposition, and to Efe Ok for pointing out some economic papers which use Tarski’s theorem. Wojciech Olszewski
[email protected] 1
Department of Economics, Northwestern University, Evanston, IL 60208, USA
Order
(see Adachi[1] and Fleiner [3]), and to solve certain types of discontinuous generalized variational inequalities (see Nishimura and Ok [8] and Li and Ok [7]2 ). However, the theorem is not fully satisfying for the following reason. It says nothing about the sequences of iterations of x, when x is neither the lowest nor the highest element of a lattice. Such sequences often appear in the analysis of dynamic processes, e.g., the best-response dynamics in games. For an arbitrary x, a result similar to that for the lowest or the highest x is not possible. It is easy to give examples of diverging sequences of iterations. However, we will show in this note that the properly defined limit superior and limit inferior of the sequences of iterations are fixed points of f for all x. These limits are the sharp fixed-point bounds between which all sufficiently large iterations are located. When the two limits coincide, the sequence of iterations converges to a fixed point. Our result generalizes the Tarski theorem to all x. As the Tarski theorem itself, our result has to allow for transfinite sequences, but in applications, it of
Data Loading...