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

Question

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

Answer 1

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.