Distributive Lattice Visualization

Recently, I’ve been working with lattices as data types for certain dynamical systems on networks. I wrote this blog post to show some visualization tools I wrote to help me understand morphisms of lattices. A lattice $L$ is a partially order set with two binary operations called the meet $\wedge$ and join $\vee$ . The operations necessarily represent the greatest lower bound and least upper bound respectively. Moreover, we will want our lattices to be bounded, that is to say there is a greatest element $T \in L$ and smallest element $B \in L$ .

I needed to understand how lattices could pass information to one other i.e. to have an appropriate notion of morphism between them $f : L \to K$ . For my purposes, functions preserving the partial order are too weak, while functions preserving both the meet and join are too strong. A happy median turns out to be join preserving functions satisfying $f(a \vee b) = f(a) \vee f(b)$ and $f(B_L) = B_K$ for all $a,b \in L$ . A particularly nice property of such functions is that they admit adjoints $f^\bullet : K \to L$ that are meet preserving, i.e. $f^\bullet(a \wedge b) = f^\bullet(a) \wedge f^\bullet(b)$ and $f^\bullet(T_K) = T_L$ . To stress this duality, we write join preserving maps with a lower bullet $f = f_\bullet$ . Such a pair $(f_\bullet,f^\bullet)$ is known as a Galois connection and they arise in many different places across mathematics. Note this slightly different from the correspondences in Galois theory, in that setting the maps are order reversing, but the two notions are highly related.

Galois connections can be somewhat daunting to visualize, so I wrote some tools to help me understand them better and build some intuition. I will restrict myself to setting of distributive lattices since Galois connections between them are highly structured. A lattice is said to be distributive if joins distribute over meets and vice-versa. In other words the following formula

$x \wedge (y \vee z) = (x \vee y) \wedge (x \vee z)$

(and its dual) holds for all $x,y,z \in L$ . A theorem of Garret Birkhoff says that every distributive lattice is isomorphic to a ring of sets, hence we can realize every element of $L$ as a set in such a way that the partial order is given by set inclusion. Below is a script depicting a distributed lattice generated by the unions and intersections of the following sets:

$\{a\}, \ \{b\}, \ \{c,d\}, \ \{a,e\}, \ \{b,e\}, \ \{a,c,e\}.$

Clicking on a node highlights its upper and lower neighbors, while hovering your mouse over a node displays the associated set.

Before tackling morphisms of distributive lattice, we first consider the simpler case of power set lattices. It turns out that, given two sets $X$ and $Y$ , every Galois connection between their power sets $2^X$ and $2^Y$ bijectively corresponds to a binary relation $R \in 2^{X \times Y}$ . We can recover the connection via the following formula

where $A \subseteq X$ , $B \subseteq Y$ , and $R(x,-)$ is the set of all $y \in Y$ related to $x$ . Since every distributed lattice is a ring of sets, it can be embedded into a power set lattice. In particular, for a representation of distributive lattice $L$ , let $T_L$ be the set representing the top element of $L$ , then we can view $L$ as a sublattice of $2^{T_L}$ . Given another distributive lattice $K$ , we can obtain Galois connections between by inducing them from Galois connections between $2^{T_L}$ and $2^{T_K}$ . In summary, every Galois connection between $L$ and $K$ can be represented by a relation $R \in 2^{T_L \times T_K}$ .

As example, consider another lattice $K$ generated by the sets:

$\{v,w\}, \ \{x,y\}, \ \{x,y,z\}, \ \{v,z\}.$

We let $R$ be the following relation between the sets $T_L = \{a,b,c,d,e\}$ and $T_K = \{x,y,z,w,v\}$ :

Below we visualize both lattices side by side as well as the Galois connection induced by $R$ . The red dotted line indicates the left adjoint mapping $R_\bullet : L \to K$ , while green dotted lines represent the mapping $R_\bullet : K \to L$ . Hovering over a node displays its image as well as the set of elements mapping to it.

Some of the code for these examples is available in this Observable notebook or in this github repository.

Miguel Lopez

Math Apprentice

Distributive Lattice Visualization

Leave a Reply Cancel reply