# 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.