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.