Cardinality, Knaster's Fixed Point Theorem

Knaster's Fixed Point Theorem

Let f be a weakly increasing function from a complete lattice S into itself. That is, x ≤ y implies f(x) ≤ f(y). There is a fixed point x with f(x) = x.

The intuition is that f maps all of S to a bounded subset inside S, and applying f twice yields a smaller subset, and so on, until we zoom in on a point, whence f(x) = x.

Suppose there is no fixed point, and let x0 be the minimum point in the lattice. Let x1 = f(x0), and let xn+1 = f(xn). Similarly, y0 starts at the top, and yn+1 = f(yn).

Since x0 is at the bottom, x0 ≤ x1, whence x1 ≤ x2, and x2 ≤ x3, and so on. Similarly yn ≥ yn+1.

Since all points lie between x0 and y0, the image of the entire set S, under f, lies between x1 and y1. By induction the image of everything between xn and yn lies between xn+1 and yn+1. This builds a descending chain Cn of bounded posets of S, each smaller than the previous.

Let u be the least upper bound of the sequence x0 x1 x2 etc, the cap on a linearly ordered set. Note that u cannot equal any xn, else it is not an upper bound for xn+1, which lies above xn. Thus u is a new point.

Everything above u is above each xn. Conversely, if a point is above each xn it is an upper bound for our sequence, and u is the least upper bound, hence it lies above u.

Let v be the greatest lower bound for y1 y2 y3 etc. The points between u and v are the points above each xn and below each yn, or the intersection of the descending chain Cn. Call this set D, the set bounded by u and v.

Clearly u and v are in C0. Apply f, and u and v are in C1. Continue this process, and u and v are in each Cn, and in D. In other words, D is not empty.

Set u0 = u, v0 = v, and D0 = D, and go on to build un, vn, and Dn as above. Then let the least upper bound and greatest lower bound bracket another subset, and continue by transfinite induction through the ordinals. Since S is a set, the resulting chain of subsets cannot continue forever. We have reached a contradiction, hence there must be some x such that f(x) = x.