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 is a partially order set with two binary operations called the meet and join . 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 and smallest element .
I needed to understand how lattices could pass information to one other i.e. to have an appropriate notion of morphism between them . 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 and for all . A particularly nice property of such functions is that they admit adjoints that are meet preserving, i.e. and . To stress this duality, we write join preserving maps with a lower bullet . Such a pair 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
(and its dual) holds for all . A theorem of Garret Birkhoff says that every distributive lattice is isomorphic to a ring of sets, hence we can realize every element of 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:
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 and , every Galois connection between their power sets and bijectively corresponds to a binary relation . We can recover the connection via the following formula
where , , and is the set of all related to . 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 , let be the set representing the top element of , then we can view as a sublattice of . Given another distributive lattice , we can obtain Galois connections between by inducing them from Galois connections between and . In summary, every Galois connection between and can be represented by a relation .
As example, consider another lattice generated by the sets:
We let be the following relation between the sets and :
Below we visualize both lattices side by side as well as the Galois connection induced by . The red dotted line indicates the left adjoint mapping , while green dotted lines represent the mapping . Hovering over a node displays its image as well as the set of elements mapping to it.