First-year students in mathematics and computer science are often troubled with the Schröder-Bernstein theorem, which proves that the natural ordering between cardinal numbers is in fact a partial order, but has a lengthy and convoluted proof. A more accurate study of order structures (often neglected by basic course) would, however, allow to see this fact as an almost immediate consequence of a much simpler, and very powerful, theorem due to Bronislaw Knaster and Alfred Tarski.
Recall that a partially ordered set (shortened as poset) is a pair where is a set and is a reflexive, transitive, and antisymmetric binary relation on . A directed acyclic graph, where if and only if there is a directed path from to , is a prime example of a poset.
If is a poset and if is defined as if and only if , then is a poset too: just think of the original poset, turned upside down—or, equivalently, to the order graph with all the edges reversed.
Given two posets , , a function is said to be monotone if implies . If is monotone as a function from to , then it is also monotone as a function from to : this simple observation often allows to make proofs in only one direction.
Let be a poset and let . An upper bound for is an element such that for every . A subset of may have a least upper bound, that is, an upper bound such that, if is any upper bound for , then : in this case, such least upper bound is usually indicated as . Dually, a lower bound for is an such that for every , and a greatest lower bound is an element such that, if is a lower bound for , then .
A partially ordered set such that every subset of have both a greatest lower bound and a least upper bound , is called a complete lattice.
It follows from the definition that a complete lattice is nonempty. In fact, it must contain at least an element and an element , although these two may coincide.
Power sets, ordered by inclusion, are complete lattices: the greatest lower bound of a family of subsets is the intersection of the subsets, and the least upper bound is the union. The real line is not a complete lattice: hovewer, any closed and bounded interval of the real line is a complete lattice. Moreover, if is a complete lattice, and with then the interval is a complete lattice: if , then for every , thus too.
Finite boolean algebras are complete lattices. Infinite boolean algebra are only guaranteed to have finite meets and joins: indeed, the boolean algebra of the recursive subsets of is not a complete lattice. To see this, let be a recursively enumerable subset of which is not recursive: then for a suitable total recursive function we have .
The following statement was proved by Knaster in 1928 for power sets, then by Tarski in 1955 for arbitrary complete lattices.
Knaster-Tarski fixed point theorem. Let be a complete lattice with top element and bottom element ; let be a monotone function, and let . Then:
- is a complete lattice.
- The smallest fixed point of satisfies
and the largest fixed point of satisfies
- If is finite, then the sequence defined by and for converges to in finitely many iterations, and the sequence defined by and for converges to in finitely many iterations.
Observe that is not, in general, a full sublattice of : the least upper bound of in may not coincide with the least upper bound of in . To understand why, let where the natural ordering of is extended by putting and for every . Let be defined by and if : then the greatest upper bound of is in , but in .
Proof. We first prove point 2. Call the set of post-fixed points, and its least upper bound. Then for every we have , thus also , i.e., is an upper bound for : then , so that the greatest lower bound of the set of post-fixed point is itself a post-fixed point! But if is post-fixed, then is post-fixed as well as is monotone: as is by construction the least upper bound of the set of the post-fixed points, . By antisymmetry of the order relation, , i.e., is actually a fixed point: but if the least upper bound of the overfixed points is a fixed point, then it cannot help but be the greatest fixed point as well! Dually, has a least fixed point, which is the greatest lower bound of the set of pre-fixed points.
We now use point 2 to prove point 1. Let and let . By monotonicity of , for every and we have , so that too: as clearly for , is also a monotone function from to itself. As the latter is a complete lattice, has a least fixed point in it: if satisfies for every , then it also satisfies , thus also . Hence, this is the least upper bound of in , although it might happen that . Dually, has a greatest lower bound in , which might be strictly greater than the greatest lower bound of in .
Finally, suppose is finite. Then the sequence where and also has finitely many elements, so there exist and such that . But by construction, so and . If too, then : then is a fixed point and is greater than every fixed point, so ti must be the greatest fixed point . Dually, if and , then , the least fixed point, for some .
The Knaster-Tarski theorem can be used to define specific constructions as least or greatest fixed points of monotone functions over complete lattices: if the latter are finite, then it also provides an algorithm for their construction. An example of this is bisimilarity. Recall that a bisimulation on a family of processes is a binary relation such that, for every :
- if then there exists such that and ; and
- if then there exists such that and .
Two processes are bisimilar if there is a bisimulation that contains them. As any union of bisimulations is a bisimulation, whatever is, there exists a largest bisimulation on , called bisimilarity, and usually indicated by .
If is finite, then bisimilarity can be constructed via the Knaster-Tarski fixed point theorem. In fact, consider the powerset as a complete lattice according to inclusion, and define a function by saying that if and only if conditions 1 and 2 of bisimulation are satisfied for . Then not only is monotone, but bisimulations are precisely those such that : hence, bisimilarity, which is the least upper bound of the family of bisimulations, is precisely the greatest fixed point of !
Coming back to the Schröder-Bernstein theorem: let and be injective functions. Then
is a monotone function on the complete lattice . Surely is a bijection. By the Knaster-Tarski theorem, there exists such that : but for such we have , so that is a bijection too! Define then a bijection as follows:
- if , let ;
- otherwise, let be the unique such that .
Observe that the standard proof is obtained by explicitly constructing a fixed point for .
We conclude with a very interesting converse to the Knaster-Tarski theorem, proved by Anne Davis in 1955, in an article that appeared on the same issue as Tarski’s—actually, immediately after it! Recall that a lattice is a poset where every finite subset has a least upper bound and a greatest lower bound.
Davis’ characterization of complete lattices. Let be a lattice. Suppose that every monotone function has a fixed point. Then is a complete lattice.
An interesting exercise, is to construct a proof of Davis’ theorem by showing that meets and joins of arbitrary sets can be seen as fixed points of suitable monotone functions.