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:

$(\mathrm{Fix}(F), \leq)$ is a complete lattice.
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)\} \,.$
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}$ :

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
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:

if $x \in U$ , let $h(x) = f(x)$ ;
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

Theory Lunch

Institute of Cybernetics, Tallinn

Some reasons to teach lattice theory to undergraduates

Leave a Reply Cancel reply

Follow “Theory Lunch”

Share this:

Like this:

Leave a Reply Cancel reply

Follow “Theory Lunch”