# Which complete lattices arise as images of the Galois connections induced by binary relations?

Any binary relation $R\subseteq X\times Y$ gives rise to a Galois connection between the powersets of $X$ and $Y$ in a well known way (on MO you can see it e. g. in this answer; in fact, such Galois connections are in one-to-one correspondence with binary relations).

It follows that any $R$ defines closure operators on subsets of both $X$ and $Y$, with anti-isomorphic complete lattices of closed sets.

Does any complete lattice occur in this way? If not, which ones do occur? Which lattices can occur for given fixed cardinalities of $X$ and $Y$? Can one characterize those relations which give rise to "nice" (modular, distributive, Heyting, Boolean, ...) lattices?

I am aware that this is most probably very well studied, so this is a reference request more than anything else; still I would be glad to have an explained answer without any references too :D

Yes. Any complete lattice arises from a Galois connection. For instance, if $(X,\leq)$ is a poset, then the complete lattice associated with the Galois connection induced by the relation $\leq$ is the Dedekind-MacNeille completion of $X$. In particular, if $X$ is a complete lattice, then $X$ is the complete latticed obtained from the Galois connection that we get from the relation $\leq$.

In fact, there are, in general, many ways to obtain a complete lattice from a binary relation, and the ways to obtain a certain complete lattice from binary relations can be completely described.

Suppose $A$ is a subset of a complete lattice $L$. Then $A$ is said to be join-dense if $L=\{\bigvee R|R\subseteq A\}$, and $A$ is said to be meet-dense if $L=\{\bigwedge R|R\subseteq A\}$.

$\textbf{Theorem}$ Suppose that $L$ is a complete lattice and $A,B$ are sets. Furthermore, suppose that $f:A\rightarrow L,g:B\rightarrow > L$ are functions such that $f[A]$ is join-dense and $g[B]$ is meet-dense. Let $R$ be the binary relation on $A\times B$ such that $aRb$ if and only if $f(a)\leq g(b)$. Then $L$ is isomorphic to the complete lattice obtained from the Galois connection induced by $R$.

The above result is the best possible in the sense that the only binary relations $R\subseteq A\times B$ that give you the complete lattice $L$ are induced by functions $f:A\rightarrow L,g:B\rightarrow L$ with $f[A]$ join-dense and $g[B]$ meet-dense. In fact, we obtain a duality between the class of all binary relations and the class of all triples $(L,f,g)$ where $L$ is a complete lattice, $f:A\rightarrow L,g:B\rightarrow L$, $f[A]$ is join dense, and $g[B]$ is meet-dense.

One should probably look at any reference on formal concept analysis for more information on the correspondence between binary relations and complete lattices. The book Introduction to Lattices and Order by Davey and Priestley has a chapter on formal concept analysis.

• I like this very much, thank you! One question - in the last statement (about duality between relations and triples), could not one further restrict $f$ and $g$ in such a way as to obtain some sort of "canonical representation" of a given $L$ by a relation? E. g. by taking $f$ and $g$ inclusions? Of course one almost never has smallest join- or meet-dense subsets, but maybe there are some canonical choices... – მამუკა ჯიბლაძე Apr 19 '14 at 17:40
• For finite lattices, the collection of all join (meet)-irreducible sets is the smallest join (meet)-dense subset, so that will be a canonical choice. More generally, if a complete lattice has no infinite chains, then the join(meet)-irreducible sets forms the smallest join(meet)-dense subset. However, I can only think of canonical choices of join-dense subsets for certain specialized classes of complete lattices. I therefore cannot think of a canonical join-dense subset in general. – Joseph Van Name Apr 19 '14 at 17:52
• @JosephVanName Right. And yes, you've been right, I checked Davey&Priestley (second edition), it is Theorem 3.9 there. – მამუკა ჯიბლაძე Apr 20 '14 at 5:56