Some reasons to teach lattice theory to undergraduates

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 (X,\leq) where X is a set and \leq is a reflexive, transitive, and antisymmetric binary relation on X. A directed acyclic graph, where x \leq y if and only if there is a directed path from x to y, is a prime example of a poset.

If (X,\leq) is a poset and if \geq is defined as x \geq y if and only if y \leq x, then (X,\geq) 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 (X,\leq_X), (Y,\leq_Y), a function F : X \to Y is said to be monotone if a \leq_X b implies F(a) \leq_Y F(b). If F is monotone as a function from (X,\leq_X) to (Y,\leq_Y), then it is also monotone as a function from (X,\geq_X) to (Y,\geq_Y): this simple observation often allows to make proofs in only one direction.

Let (X,\leq) be a poset and let U \subseteq X. An upper bound for U is an element m \in X such that x \leq m for every x \in U. A subset U of X may have a least upper bound, that is, an upper bound m_U such that, if x is any upper bound for U, then m_u \leq x: in this case, such least upper bound is usually indicated as \bigvee U. Dually, a lower bound for U is an \ell \in X such that \ell \leq x for every x \in U, and a greatest lower bound is an element \ell_U = \bigwedge U such that, if x is a lower bound for U, then x \leq \ell_U.

A partially ordered set (X,\leq) such that every subset U of X have both a greatest lower bound \bigwedge U and a least upper bound \bigvee U, is called a complete lattice.

It follows from the definition that a complete lattice (X,\leq) is nonempty. In fact, it must contain at least an element \top = \bigvee X and an element \bot = \bigwedge X, 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 (X,\leq) is a complete lattice, and a,b \in X with a \leq b then the interval [a,b] = \{x \in X \mid a \leq x \leq b\} is a complete lattice: if U \subseteq [a,b], then a \leq x \leq b for every x \in U, thus a \leq \bigwedge U \leq \bigvee U \leq b 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 \mathbb{N} is not a complete lattice. To see this, let X be a recursively enumerable subset of \mathbb{N} which is not recursive: then for a suitable total recursive function f : \mathbb{N} \to \mathbb{N} we have X = f(\mathbb{N}) = \bigvee \left\{\{f(m) \mid 0 \leq m \leq n\} \mid n \geq 0\right\}.

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 (X,\leq) be a complete lattice with top element \top and bottom element \bot; let F : X \to X be a monotone function, and let \mathrm{Fix}(F) = \{x \in X \mid F(x) = x\}. Then:

  1. (\mathrm{Fix}(F), \leq) is a complete lattice.
  2. The smallest fixed point x_m of F satisfies
    x_m = \bigwedge \{x \in X \mid F(x) \leq x\} \,,
    and the largest fixed point x_M of F satisfies
    x_M = \bigvee \{x \in X \mid x \leq F(x)\} \,.
  3. If X is finite, then the sequence defined by x_0 = \bot and x_{n+1} = F(x_n) for n \geq 0 converges to x_m in finitely many iterations, and the sequence defined by x_0 = \top and x_{n+1} = F(x_n) for n \geq 0 converges to x_M in finitely many iterations.

Observe that (\mathrm{Fix}(F), \leq) is not, in general, a full sublattice of (X,\leq): the least upper bound of U in \mathrm{Fix}(F) may not coincide with the least upper bound of U in X. To understand why, let X = \mathbb{N} \sqcup \{a,b\} where the natural ordering of \mathbb{N} is extended by putting a < b and x < a for every x \in \mathbb{N}. Let F : X \to X be defined by F(a) = b and F(x) = x if x \neq a: then the greatest upper bound of \mathbb{N} \subseteq \mathrm{Fix}(F) is a in X, but b in \mathrm{Fix}(F).

Proof. We first prove point 2. Call \mathrm{Fix}^+(F) = \{x \in X \mid x \leq F(x)\} the set of post-fixed points, and x^+_M its least upper bound. Then for every x \in \mathrm{Fix}^+(F) we have x \leq x^+_M, thus also x \leq F(x) \leq F(x^+_M), i.e., F(x^+_M) is an upper bound for \mathrm{Fix}^+(F): then x^+_M \leq F(x^+_M), so that the greatest lower bound of the set of post-fixed point is itself a post-fixed point! But if x^+_M is post-fixed, then F(x^+_M) is post-fixed as well as F is monotone: as x^+_M is by construction the least upper bound of the set of the post-fixed points, F(x^+_M) \leq x^+_M. By antisymmetry of the order relation, F(x^+_M) = x^+_M, i.e., x^+_M 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, F 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 U \subseteq \mathrm{Fix}(F) and let \overline{x} = \bigvee U \in X. By monotonicity of F, for every z \in [\overline{x},\top] and x \in U we have x = F(x) \leq F(z), so that \overline{x} \leq F(z) too: as clearly F(z) \leq \top for z \in [\overline{x},\top], F is also a monotone function from [\overline{x}, \top] to itself. As the latter is a complete lattice, F has a least fixed point y in it: if z \in \mathrm{Fix}(F) satisfies x \leq z for every x \in U, then it also satisfies z \in [\overline{x},\top], thus also y \leq z. Hence, this y is the least upper bound of U in \mathrm{Fix}(F), although it might happen that \overline{x} < y. Dually, U has a greatest lower bound in \mathrm{Fix}(F), which might be strictly greater than the greatest lower bound of U in X.

Finally, suppose X is finite. Then the sequence \{x_n\}_{n \geq 0} where x_0 = \top and x_{n+1} = F(x_n) also has finitely many elements, so there exist n \geq 0 and k > 0 such that x_{n+k} = x_n. But x_{n+k} \leq x_{n+k-1} \leq \ldots \leq x_{n+1} \leq x_n by construction, so x_{n+1} = F(x_n) = x_n and x_n \in \mathrm{Fix}(F). If x \in \mathrm{Fix}(F) too, then x = F^{(n)}(x) \leq F^{(n)}(\top) = x_n: then x_n is a fixed point and is greater than every fixed point, so ti must be the greatest fixed point x_M. Dually, if x_0 = \bot and x_{n+1} = F(x_n), then x_n = x_m, the least fixed point, for some n \geq 0. \Box

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 \mathrm{Proc} of processes is a binary relation \mathcal{R} \subseteq \mathrm{Proc} \times \mathrm{Proc} such that, for every (P,Q) \in \mathcal{R}:

  1. if P \stackrel{a}{\rightarrow} P' then there exists Q' \in \mathrm{Proc} such that (P',Q') \in \mathcal{R} and Q \stackrel{a}{\rightarrow} Q'; and
  2. if Q \stackrel{a}{\rightarrow} Q' then there exists P' \in \mathrm{Proc} such that (P',Q') \in \mathcal{R} and P \stackrel{a}{\rightarrow} P'.

Two processes are bisimilar if there is a bisimulation that contains them. As any union of bisimulations is a bisimulation, whatever \mathrm{Proc} is, there exists a largest bisimulation on \mathrm{Proc}, called bisimilarity, and usually indicated by \sim.

If \mathrm{Proc} is finite, then bisimilarity can be constructed via the Knaster-Tarski fixed point theorem. In fact, consider the powerset 2^{\mathrm{Proc} \times \mathrm{Proc}} as a complete lattice according to inclusion, and define a function F : 2^{\mathrm{Proc} \times \mathrm{Proc}} \to 2^{\mathrm{Proc} \times \mathrm{Proc}} by saying that (P,Q) \in F(\mathcal{R}) if and only if conditions 1 and 2 of bisimulation are satisfied for (P,Q). Then not only F is monotone, but bisimulations are precisely those \mathcal{R} \subseteq \mathrm{Proc} \times \mathrm{Proc} such that \mathcal{R} \subseteq F(\mathcal{R}): hence, bisimilarity, which is the least upper bound of the family of bisimulations, is precisely the greatest fixed point of F!

Coming back to the Schröder-Bernstein theorem: let f : X \to Y and g : Y \to X be injective functions. Then

F(U) = X \setminus g \left( Y \setminus f(U) \right)

is a monotone function on the complete lattice (2^X, \subseteq). Surely f : U \to f(U) is a bijection. By the Knaster-Tarski theorem, there exists U \subseteq X such that U = X \setminus g(Y \setminus f(U)): but for such U we have g(Y \setminus f(U)) = X \setminus U, so that g: Y \setminus f(U) \to X \setminus U is a bijection too! Define then a bijection h = h_U : X \to Y as follows:

  1. if x \in U, let h(x) = f(x);
  2. otherwise, let h(x) be the unique y \in Y such that g(y) = x.

Observe that the standard proof is obtained by explicitly constructing a fixed point for F.

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 (X,\leq) be a lattice. Suppose that every monotone function F : X \to X has a fixed point. Then (X,\leq) 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.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s