# Relational Lattices via Duality

Luigi Santocanale

► To cite this version:

Luigi Santocanale. Relational Lattices via Duality. 13th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2016, Eindhoven, Netherlands. pp.195-215, 10.1007/978-3-319-40370-0_12. hal-01446027

HAL Id: hal-01446027

https://inria.hal.science/hal-01446027

Submitted on 25 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Relational lattices via duality

Luigi Santocanale

LIF, CNRS UMR 7279, Aix-Marseille Université

**Abstract.** The *natural join* and the *inner union* combine in different ways tables of a relational database. Tropashko [18] observed that these two operations are the meet and join in a class of lattices—called the *relational lattices*—and proposed lattice theory as an alternative algebraic approach to databases. Aiming at query optimization, Litak et al. [12] initiated the study of the equational theory of these lattices. We carry on with this project, making use of the duality theory developed in [16]. The contributions of this paper are as follows. Let $A$ be a set of column's names and $D$ be a set of cell values; we characterize the dual space of the relational lattice $R(D, A)$ by means of a generalized ultra-metric space, whose elements are the functions from $A$ to $D$, with the $P(A)$-valued distance being the Hamming one but lifted to subsets of $A$. We use the dual space to present an equational axiomatization of these lattices that reflects the combinatorial properties of these generalized ultrametric spaces: symmetry and pairwise completeness. Finally, we argue that these equations correspond to combinatorial properties of the dual spaces of lattices, in a technical sense analogous of correspondence theory in modal logic. In particular, this leads to an exact characterization of the finite lattices satisfying these equations.

## 1 Introduction

Tropashko [18] has recently observed that the *natural join* and the *inner union*, two fundamental operations of the relational algebra initiated by Codd [2]—the algebra by which we construct queries—can be considered as the meet and join operations in a class of lattices, known by now as the class of *relational lattices*. Elements of the relational lattice $R(D, A)$ are the relations whose variables are listed by a subset of a total set $A$ of attributes, and whose tuples' entries are taken from a set $D$. Roughly speaking, we can consider a relation as a table of a database, its variables as the columns' names, its tuples being the rows.

Let us illustrate these operations with examples. The natural join takes two tables and constructs a new one whose columns are indexed by the union of the headers, and whose rows are the glueings of the rows along identical values in common columns. As we emphasize in this paper the lattice theoretic aspects of the natural join operation, we shall depart from the standard practice of denoting it by the symbol $▷$ and use instead the meet symbol $\wedge$.

<table><thead><tr><td>Author</td><td>Area</td></tr></thead><tbody><tr><td>Santocanale</td><td>Logic</td></tr><tr><td>Santocanale</td><td>CS</td></tr></tbody></table>

<figure><img src="image_2.png" /></figure>

<table><thead><tr><td>Area</td><td>Reviewer</td></tr></thead><tbody><tr><td>CS</td><td>Turing</td></tr><tr><td>Logic</td><td>Gödel</td></tr></tbody></table>

<figure><img src="image_3.png" /></figure>

<table><thead><tr><td>Author</td><td>Area</td><td>Reviewer</td></tr></thead><tbody><tr><td>Santocanale</td><td>Logic</td><td>Gödel</td></tr><tr><td>Santocanale</td><td>CS</td><td>Turing</td></tr></tbody></table>
The inner union restricts two tables to the common columns and lists all the possible rows. The following example suggests how to construct, using this operation, a table of users given two (or more) tables of people having different roles.

<table><thead><tr><th colspan="2">Authors</th></tr></thead><tbody><tr><td>Name</td><td>Surname</td><td>Conf</td></tr><tr><td>Luigi</td><td>Santocanale</td><td>CMCS</td></tr></tbody></table>

V

<table><thead><tr><th colspan="2">Reviewers</th></tr></thead><tbody><tr><td>Name</td><td>Surname</td><td>Area</td></tr><tr><td>Alan</td><td>Turing</td><td>CS</td></tr><tr><td>Kurt</td><td>Gödel</td><td>Logic</td></tr></tbody></table>

=

<table><thead><tr><th colspan="2">Users</th></tr></thead><tbody><tr><td>Name</td><td>Surname</td></tr><tr><td>Luigi</td><td>Santocanale</td></tr><tr><td>Alan</td><td>Turing</td></tr><tr><td>Kurt</td><td>Gödel</td></tr></tbody></table>

Considering the lattice signature as a subsignature of the relational algebra, Litak, Mikulás and Hidders [12] proposed to study the equational theory of the relational lattices. The capability to recognize when two queries are equivalent—that is, a solution to the word problem of such a theory—is of course an important step towards query optimization.

Spight and Tropashko [17] exhibited equational principles in a signature strictly larger than the one of lattice theory. A main contribution of Litak et al. [12]—a work to which we are indebted in many respects—was to show that the quasiequational theory of relational lattices with the header constant is undecidable. The authors also proposed a base of equations for the theory in the signature extended with the header constant, and exhibited two non-trivial pure lattice equations holding on relational lattices. It was argued there that the lattice $R(D, A)$ arises via a closure operator on the powerset $P(A \sqcup D^A)$ and, at the same time, as the Grothendieck construction for the functor $P(D^{(-)})$, from $P(A)^{op}$ to $SL_\vee$ (the category of complete lattices and join-preserving mappings), sending $X \subseteq A$ to $D^X$ and then $D^X$ covariantly to $P(D^X)$.

The focus of this paper is on the pure lattice signature. We tackle the study of the equational theory of relational lattices in a coalgebraic fashion, that is, by using the duality theory developed in [16] for finite lattices and here partially extended to infinite lattices. Let us recall some key ideas from the theory, which in turn relies on Nation's representation Theorem [14, §2]. For a complete lattice $L$, a join-cover of $x \in L$ is a subset $Y \subseteq L$ such that $x \leq \bigvee Y$. A lattice is pluperfect if it is a complete spatial lattice and every join-cover of a completely join-irreducible element refines to a minimal one—see Section 2 for a complete definition. Every finite lattice is pluperfect; moreover, relational lattices are pluperfect, even when they are infinite. This property, i.e. pluperfectness, allows to define the dual structure of a lattice $L$, named the OD-graph in [14]. This is the triple $\langle \mathcal{J}(L), \leq, \prec_m \rangle$ with $\mathcal{J}(L)$ the set of completely join-irreducible elements, $\leq$ the restriction of the order to $\mathcal{J}(L)$, and the relation $j \prec_m C$ holds when $j \in \mathcal{J}(L)$, $C \subseteq \mathcal{J}(L)$, and $C$ is a minimal join-cover of $j$. The original lattice $L$ can be recovered up to isomorphism from its OD-graph as the lattice of closed downsets of $\mathcal{J}(L)$—where a downset $X \subseteq \mathcal{J}(L)$ is closed if $j \prec_m C \subseteq X$ implies $j \in X$.

We characterize the OD-graph of the lattice $R(D, A)$ as follows. Firstly recall from [12] that we can identify completely join-irreducible elements of $R(D, A)$ with elements of the disjoint sum $A \sqcup D^A$. The order on completely
join-irreducible elements is trivial, i.e. it is the equality. All the elements of $A$ are join-prime, whence the only minimal join-cover of some $a \in A$ is the singleton $\{a\}$. The minimal join-covers of elements in $D^A$ are described via an ultrametric distance valued in the join-semilattice $P(A)$; this is, morally, the Hamming distance, $\delta(f,g) = \{x \in A \mid f(x) \neq g(x)\}$. Whenever $f,g \in D^A$ we have $f \prec_m \delta(f,g) \cup \{g\}$ and these are all the minimal join-covers of $f$.

As in correspondence theory for modal logic, the combinatorial structure of the dual spaces is an important source for discovering axioms/equations that uniformly hold in a class of models. For relational lattices, most of these combinatorial properties stem from the structure of the ultrametric space $(D^A, \delta)$. When we firstly attempted to show that equations (RL1) and (RL2) from [12] hold in relational lattices using duality, we realized that the properties necessary to enforce these equations were the following:

P1. Every non-trivial minimal join-cover contains at most one join-irreducible element which is not join-prime.

Moreover, the generalized ultrametric space $(D^A, \delta)$ is

P2. *symmetric*, i.e. $\delta(f,g) = \delta(g,f)$, for each $f,g \in D^A$,

P3. *pairwise complete*: if $\delta(f,g) \subseteq X \cup Y$, then $\delta(f,h) \subseteq X$ and $\delta(h,g) \subseteq Y$ for some $h \in D^A$.

Various notions of completeness for generalized ultrametric spaces are discussed in [1]. At first we called pairwise completeness the Beck-Chevalley-Malcev property of $(D^A, \delta)$. Indeed, it is equivalent to saying that the functor $P(D^{(-)}) : P(A)^{op} \to SL_{\vee}$ mentioned above sends a pullback square (i.e., a square of inclusions with objects $X \cap Y$, $X$, $Y$, $Z$) to a square satisfying the Beck-Chevalley condition. As the property implies that a collection of congruences of join-semilattices commute, it is also a sort of Malcev condition.

We show with Theorem 4 that property P1 of an OD-graph is definable by an equation that we name (Unjp). We investigate the deductive strength of this equation and show in particular that (RL2) is derivable from (Unjp), but not the converse.

In presence of P1, symmetry and pairwise completeness can also be understood as properties of an OD-graph. Symmetry is the following property: if $k_0 \prec_m C \cup \{k_1\}$ with $k_1$ not join-prime, then $k_1 \prec_m C \cup \{k_0\}$. Pairwise completeness can be read as follows: if $k_0 \prec_m C_0 \cup C_1 \cup \{k_2\}$ with $k_2$ not join-prime and $C_0, C_1, \{k_2\}$ pairwise disjoint, then $k_0 \prec_m C_0 \cup \{k_1\}$ and $k_1 \prec_m C_1 \cup \{k_2\}$ for some completely join-irreducible element $k_1$.

We exhibit in Section 6 three equations valid on relational lattices and characterize, via a set of properties of their OD-graphs, the pluperfect lattices satisfying (Unjp) and these equations. We propose these four equations as an axiomatization of the theory of relational lattices that we call [[AxRel]]. The main result of this paper, Theorem 7, sounds as follows. If we restrict to *finite* lattices that are *atomistic*—that is, lattices in which any element is the join of the atoms below it, so the order on join-irreducible elements in the dual space is trivial—then a
lattice satisfies [[AxRel]] if and only if its OD-graph is symmetric and pairwise
complete, in the sense just explained.

We can build lattices similar to the relational lattices from $P(A)$-valued ultrametric spaces. It is tempting to look for further equations so to represent the OD-graph of finite atomistic lattices satisfying these equations as $P(A)$-valued ultrametric space. Unfortunately this is not possible, since a key property of the OD-graph of lattices of ultrametric spaces—the ones ensuring that the distance function is well defined—is not definable by lattice equations. Yet Theorem 7 also exhibits a deep connection between the OD-graph of finite atomistic lattices satisfying [[AxRel]] and the frames of the commutator logic $[S5]^A$, see [10]. Considering the complexity of the theory of combination of modal logics, Theorem 7 can be used to foresee and shape future researches. For example, we shall discuss in Section 7 how to derive undecidability results from the correspondent ones in multidimensional modal logic. In particular, a refinement of the main result of Litak et al. [12, Corollary 4.8] can be derived.

The paper is structured as follows. We introduce in Section 2 the notation as
well as the least lattice theoretic tools that shall allow the reader to go through
the paper. In Section 3 we describe the relational lattices, present some known
results in the literature, and give a personal twist to these results. In particular,
we shall introduce semidirect products of lattices, ultrametric spaces as a tool for
studying relational lattices, emphasize the role of the Beck-Chevalley property
in the theory. In Section 4 we characterize the OD-graphs of relational lattices.
In Section 5 we present our results on the equation (Unjp). In Section 6, we
describe our results relating equations valid on relational lattices to symmetry
and pairwise completeness. In the last Section we discuss the results presented
as well as ongoing researches, by the author and by other researchers, trace a
road-map for future work.

## 2 Some elementary lattice theory

A *lattice* is a poset *L* such that every finite non-empty subset *X* ⊆ *L* admits a smallest upper bound $\bigvee X$ and a greatest lower bound $\bigwedge X$. We assume a minimal knowledge of lattice theory—otherwise, we invite the reader to consult a standard monograph on the subject, such as [3] or [5]. The technical tools that we use may be found in the monograph [4], that we also invite to explore. A lattice can also be understood as a structure $\mathfrak{A}$ for the functional signature $(\vee, \wedge)$, such that the interpretations of these two binary function symbols both give $\mathfrak{A}$ the structure of an idempotent commutative semigroup, the two semigroup structures being tied up by the absorption laws $x \wedge (y \vee x) = x$ and $x \vee (y \wedge x) = x$. Once a lattice is presented as such structure, the order is recovered by stating that $x \le y$ holds if and only if $x \wedge y = x$.

A lattice *L* is *complete* if any subset *X* ⊆ *L* admits a smallest upper bound $\bigvee X$. It can be shown that this condition implies that any subset *X* ⊆ *L* admits a greatest lower bound $\bigwedge X$. A complete lattice is *bounded*, since $\bot := \bigvee \emptyset$ and $\top := \bigwedge \emptyset$ are respectively the least and greatest elements of the lattice.
A closure operator on a complete lattice L is an order-preserving function $j : L \to L$ such that $x \le j(x)$ and $j^2(x) = j(x)$, for each $x \in L$. We shall use Clop(L) to denote the poset of closure operators on L, under the pointwise ordering. It can be shown that Clop(L) is itself a complete lattice. If $j \in Clop(L)$, then the set $L/j$ of fixed points of $j$ is itself a complete lattice, with $\bigwedge_{L/j} X = \bigwedge_L X$ and $\bigvee_{L/j} X = j(\bigvee_L X)$. For the correspondence between closure operators and congruences in the category of complete join-semilattices, see [9].

Let L be a complete lattice. An element $j \in L$ is said to be completely join-irreducible if $j = \bigvee X$ implies $j \in X$, for each $X \subseteq L$; the set of completely join-irreducible element of L is denoted here $\mathcal{J}(L)$. A complete lattice is spatial if every element is the join of the completely join-irreducible elements below it. An element $j \in \mathcal{J}(L)$ is said to be join-prime if $j \le \bigvee X$ implies $j \le x$ for some $x \in X$, for each finite subset $X$ of $L$. We say that $j \in \mathcal{J}(L)$ is non-join-prime if it is not join-prime. An atom of a lattice L is an element of L such that $\perp$ is the only element strictly below it. A spatial lattice is atomistic if every element of $\mathcal{J}(L)$ is an atom.

For $j \in \mathcal{J}(L)$, a join-cover of $j$ is a subset $X \subseteq L$ such that $j \le \bigvee X$. For $X, Y \subseteq L$, we say that $X$ refines $Y$, and write $X \ll Y$, if for all $x \in X$ there exists $y \in Y$ such that $x \le y$. A join-cover $X$ of $j$ is said to be minimal if $j \le \bigvee Y$ and $Y \ll X$ implies $X \subseteq Y$; we write $j \triangleleft_m X$ if $X$ is a minimal join-cover of $j$. In a spatial lattice, if $j \triangleleft_m X$, then $X \subseteq \mathcal{J}(L)$. If $j \triangleleft_m X$, then we say that $X$ is a non-trivial minimal join-cover of $j$ if $X \ne \{j\}$. It is common to use the word perfect for a lattice which is both spatial and dually spatial. We need here something different:

**Definition 1.** A complete lattice is pluperfect if it is spatial and for each $j \in \mathcal{J}(L)$ and $X \subseteq L$, if $j \le \bigvee X$, then $Y \ll X$ for some $Y$ such that $j \triangleleft_m Y$. The OD-graph of a pluperfect lattice L is the structure $\langle \mathcal{J}(L), \le, \triangleleft_m \rangle$.

That is, in a pluperfect lattice every cover refines to a minimal one. Notice that every finite lattice is pluperfect. If L is a pluperfect lattice, then we say that $X \subseteq \mathcal{J}(L)$ is closed if it is a downset and $j \triangleleft_m C \subseteq X$ implies $j \in X$. As from standard theory, the mapping $X \mapsto \bigcap \{Y \subseteq \mathcal{J}(L) \mid X \subseteq Y, Y \text{ is closed}\}$ defines a closure operator whose fixed points are exactly the closed subsets of $\mathcal{J}(L)$. The interest of considering pluperfect lattices stems from the following representation Theorem.

**Theorem 1 (Nation [14]).** Let L be a pluperfect lattice and let $\mathcal{L}(\mathcal{J}(L), \le, \triangleleft_m)$ be the lattice of closed subsets of $\mathcal{J}(L)$. The mapping $l \mapsto \{j \in \mathcal{J}(L) \mid j \le l\}$ is a lattice isomorphism from L to $\mathcal{L}(\mathcal{J}(L), \le, \triangleleft_m)$.

It was shown in [16] how to extend this representation theorem to a duality between the category of finite lattices and the category of OD-graphs. The following Lemma shall be repeatedly used in the proofs of our statements.

**Lemma 1.** Let L be a pluperfect lattice, let $j \triangleleft_m C$ and $k \in C$. If $j \le \bigvee D$ with $D \ll \{\bigvee(C \setminus \{k\}), k\}$, then $k \in D$. In particular, if $k' < k$, then $\{\bigvee C \setminus \{k\}, k'\}$ is not a cover of j.
### 3 The relational lattices $R(D, A)$

In this Section we define relational lattices, recall some known facts, and develop then some tools to be used later, semidirect products of lattices, generalized ultrametric spaces, a precise connection to the theory of combination of modal logics (as well as multidimensional modal logic and relational algebras).

Let $A$ be a collection of attributes (or column names) and let $D$ be a set of cell values. A relation (or, more informally, a table) on $A$ and $D$ is a pair $(X, T)$ where $X \subseteq A$ and $T \subseteq D^X$; $X$ is the header of the table while $T$ is the collection of rows. Elements of the relational lattice $R(D, A)$ are relations on $A$ and $D$.

Before we define the natural join, the inner union operations, and the order on $R(D, A)$, let us recall a few key operations. If $X \subseteq Y \subseteq A$ and $f \in D^Y$, then we shall use $f|_X \in D^X$ for the restriction of $f$ to $X$; if $T \subseteq D^Y$, then $T \nvdash_X$ shall denote projection to $X$, that is, the direct image of $T$ along restriction, $T \nvdash_X := \{f|_X | f \in T\}$; if $T \subseteq D^X$, then $i_Y(T)$ shall denote cylindrification to $Y$, that is, the inverse image of restriction, $i_Y(T) := \{f \in D^Y | f|_X \in T\}$. Recall that $i_Y$ is right adjoint to $\nvdash_X$. With this in mind, the natural join and the inner union of tables are respectively described by the following formulas:

$$ (X_1, T_1) \wedge (X_2, T_2) := (X_1 \cup X_2, T) $$
$$ \text{where } T = \{f \mid f|_{X_1} \in T_i, i = 1, 2\} = i_{X_1 \cup X_2}(T_1) \cap i_{X_1 \cup X_2}(T_2), $$
$$ (X_1, T_1) \vee (X_2, T_2) := (X_1 \cap X_2, T) $$
$$ \text{where } T = \{f \mid \exists i \in \{1, 2\}, \exists g \in T_i \text{ s.t. } g|_{X_1 \cap X_2} = f\} $$
$$ = T_1 \Vdash_{X_1 \cap X_2} T_2 \Vdash_{X_1 \cap X_2}. $$

The order is then given by

$$ (X_1, T_1) \leq (X_2, T_2) \quad \text{iff} \quad X_2 \subseteq X_1 \text{ and } T_1 \Vdash_X T_2. $$

It was observed in [12] that $R(D, A)$ arises—as a category with at most one arrow between two objects—via the Grothendieck construction for the functor sending $X \subseteq A$ contravariantly to $D^X$ and then $D^X$ covariantly to $P(D^X)$. Let us record the following important property:

**Lemma 2.** *The image of a pullback square by the functor $P(D^{(-)}) : P(A)^{op} \to SL_{\vee}$ satisfies the Beck-Chevalley property.*

The above statement means that if we apply the functor to inclusions of the form $X_1 \cap X_2 \subseteq X_i \subseteq X_3$, $i = 1, 2$, then the two possible diagonals in the diagram on the right, $\Vdash_{X_2} \circ i_{X_3}$ and $i_{X_2} \circ \Vdash_{X_1 \cap X_2}$, are equal. The Beck-

Chevalley property is a consequence of the glueing property of functions: if $f \in D^{X_2}, g \in D^{X_1}$ and $f|_{X_1 \cap X_2} = g|_{X_1 \cap X_2}$, then there exists $h \in D^{X_3}$ such that $h|_{X_2} = f$ and $h|_{X_1} = g$.

<figure><img src="image_4.png" /></figure>
We can recast the previous category-theoretic observations in an algebraic framework. An *action* of a complete lattice $L$ over a complete lattice $M$ is a monotonic mapping $\langle \rangle : L \to \mathbf{Clop}(M)$, thus sending $X \in L$ to a closure operator $\langle X \rangle$ on $M$. Given such an action, if we define $j(X, T) := (X, \langle X \rangle T)$, then $j(X, T)$ is a closure operator on the product $L \times M$. In particular, the set of $j$-fixed points, $L \times_j M := \{(X, T) \in L \times M \mid \langle X \rangle T = T\}$, is itself a complete lattice, where the meet coincides with the one from $L \times M$, while the join is given by the formula $(X_1, T_1) \vee_{L \times_j M} (X_2, T_2) := (X_1 \vee X_2, \langle X_1 \vee X_2 \rangle (T_1 \vee T_2))$. We call $L \times_j M$ the *semidirect product* of $L$ and $M$ via $j$. The naming is chosen here after the semidirect product of groups, which is a similar instance of the Grothendieck construction. Given such an action, the correspondence $X \mapsto M/\langle X \rangle$ gives rise to a covariant functor from $L$ to the category $\mathbf{SL}_V$, so that it makes sense to ask when the Beck-Chevalley property holds, as in Lemma 2. This happens—and then we say that an action $\langle \rangle$ satisfies the Beck-Chevalley property—exactly when

$$ \langle X_1 \vee X_2 \rangle T = \langle X_1 \rangle \langle X_2 \rangle T, \quad \text{for each } X_1, X_2 \in L \text{ and } T \in M. \quad (1) $$

Notice that the identity $\langle X_1 \rangle \langle X_2 \rangle T = \langle X_2 \rangle \langle X_1 \rangle T$ is a consequence of (1). As these closure operators correspond to congruences of complete join-semilattices, we also think of the Beck-Chevalley property as a form of Malcev property, stating that a collection of congruences (thought as binary relations) pairwise commute (w.r.t composition of relations).

**Relational lattices from ultrametric spaces.** Let us come back to the lattice $\mathbf{R}(D, A)$. Define on the set $D^A$ the following $P(A)$-valued ultrametric distance:

$$ \delta(f, g) := \{x \in A \mid f(x) \neq g(x)\}. $$

Thus $\delta(f, f) \subseteq \emptyset$ and $\delta(f, g) \subseteq \delta(f, h) \cup \delta(h, g)$ for any $f, g, h \in D^A$, making $(D^A, \delta)$ into a generalized metric space in the sense of [11].<fnref n="1" /> With respect to the latter work—where axioms for the distance are those of a category enriched over $(P(A))^{op}, \emptyset, \cup$—for $f, g \in D^A$ we also have that $\delta(f, g) = \emptyset$ implies $f = g$ and symmetry, $\delta(f, g) = \delta(g, f)$. We can define then an action of $P(A)$ on $P(D^A)$:

$$ \langle X \rangle T = \{f \in D^A \mid \exists g \in T \text{ s.t. } \delta(f, g) \subseteq X\}. \quad (2) $$

We can now restate (and refine) Lemma 2.1 from [12]—which constructs the lattice $\mathbf{R}(D, A)$ via a closure operator on $P(A + D^A)$—as follows:

**Theorem 2.** The correspondence sending $(X, T)$ to $(A \setminus X, i_A(T))$ is an isomorphism bewteen the relational lattice $\mathbf{R}(D, A)$ and $P(A) \times_j P(D^A)$.

<footnote n="1">¹ This is a lifting of the Hamming distance to subsets. Yet, in view of [15] and of their work on generalized ultrametric spaces, such a distance might reasonably tributed to Priess-Crampe and Ribenboim.</footnote>
The action defined in (2) satisfies the identity (1). As a matter of fact, (1) is equivalent to *pairwise completeness* of ($D^A$, $\delta$) as an ultrametric space, see [1], namely the following property:

$$ \begin{array}{l} \text{if } \delta(f,g) \subseteq X_1 \cup X_2, \\ \text{then there exists } h \text{ such that } \delta(f,h) \subseteq X_1 \text{ and } \delta(h,g) \subseteq X_2. \end{array} \qquad (3) $$

It is easily verified that (3) is yet another spelling of the glueing property of functions.

Observe that, given any generalized ultrametric space ($F$, $\delta$) whose distance takes values in $P(A)$, equation (2)—with $D^A$ replaced by $F$—defines an action of $P(A)$ on $P(F)$. The lattice $P(A) \times_j P(F)$ shall have similar properties to those of the lattices $R(D, A)$ and will be useful when studying the variety generated by the relational lattices. As an example, we construct *typed relational lattices*, i.e. lattices of relations where each column has a fixed type. To this goal, fix a surjective mapping $\pi: D \to A$. For each $a \in A$, we think of the set $D_a = \pi^{-1}(a)$ as the type of the attribute $a$. Let $S(\pi)$ be the set of sections of $\pi$, that is, $s \in S(\pi)$ if and only if $s(a) \in D_a$, for each $a \in A$. Notice that $(S(\pi), \delta)$ is a pairwise complete sub-metric space of $(D^A, \delta)$. The lattice $R(\pi) := P(A) \times_j P(S(\pi))$ is the typed relational lattice. It can be shown that relational lattices and typed relational lattices generate the same variety.

*Relational lattices from multidimensional modal logics.* In order to illustrate and stress the value of identity (1), i.e. of the Beck-Chevalley-Malcev property, we derive next a useful formula for computing the join of two tables under the $P(A) \times_j P(D^A)$ representation.

$$ \begin{align*} (X_1, T_1) \vee (X_2, T_2) &= (X_1 \cup X_2, \langle X_1 \cup X_2 \rangle (T_1 \cup T_2)) \\ &= (X_1 \cup X_2, \langle X_1 \cup X_2 \rangle T_1 \cup \langle X_1 \cup X_2 \rangle T_2) \end{align*} $$

since the modal operators $\langle X \rangle$ are normal, in the usual sense of modal logic,

$$ \begin{align*} &= (X_1 \cup X_2, \langle X_2 \rangle \langle X_1 \rangle T_1 \cup \langle X_1 \rangle \langle X_2 \rangle T_2) \quad \text{by (1)} \\ &= (X_1 \cup X_2, \langle X_2 \rangle T_1 \cup \langle X_1 \rangle T_2) \end{align*} $$

since $\langle X_1 \rangle T_1 = T_1$ and $\langle X_2 \rangle T_2 = T_2$.

Theorem 2 suggests that a possible way to study the equational theory of the lattices $R(D, A)$ is to interpret the lattice operations in a two sorted modal logic, where the modal operators are indexed by the first sort and act on the second. It is easily recognized that each modal operator satisfies the S5 axioms, while equation (1) implies that, when $A$ is finite, each modal operator $\langle X \rangle$ is determined by the modal operators of the form $\langle a \rangle$ with $a$ an atom below $X$. That is, the kind of modal logic we need to interpret the lattice theory is the commutator logic $[S5]^n = [S5, \dots, S5]$, with $n = \text{card } A$, see [10, Definition 18].

$n$-times
## 4 Minimal join-covers in $R(D, A)$

The lattices $R(D, A)$ are pluperfect, even when $A$ or $D$ is an infinite set. The completely join-irreducible elements were characterized in [12] together with the meet-irreducible elements and the canonical context (see [3, Chapter 3] for the definition of canonical context). If we stick to the representation given in Theorem 2, the completely join-irreducible elements are of the form $\hat{a} = (\{a\}, \emptyset)$ and $\hat{f} = (\emptyset, \{f\})$. We can think of $\hat{a}$ as an empty named column, while $\hat{f}$ is an everywhere defined row. They are all atoms, so that, in particular, we shall not be concerned with the restriction of the order to $\mathcal{J}(R(D, A))$ (since this order coincides with the equality). In order to characterize the OD-graph of the lattice $R(D, A)$, we only need to characterize the minimal join-covers. Taking into account that if an element $j \in \mathcal{J}(L)$ is join-prime, then it has just one minimal join-cover, the singleton $\{j\}$, the following Theorem achieves this goal.

**Theorem 3.** The lattices $R(D, A)$ are atomistic pluperfect lattices. As a matter of fact, every element $\hat{a}$, $a \in A$, is join-prime; for $f \in D^A$, the minimal join-covers of $\hat{f}$ are of the form

$$ \hat{f} \leq \bigvee_{a \in \delta(f,g)} \hat{a} \vee \hat{g}, \quad \text{for } g \in D^A. $$

The proof of this statement is almost straightforward, given the characterization of $R(D, A)$ as the semidirect product $P(A) \times_j P(D^A)$ and the definition of the closure operators given with equation (2). For this reason, we skip it.

In particular, every minimal join-cover contains at most one non-join-prime element. In view of Theorem 1, we obtain a more precise description of the closure operator described in [12, Lemma 2.1] that gives rise to relational lattices.

**Corollary 1.** The relational lattice $R(D, A)$ is isomorphic to the lattice of closed subsets of $A \sqcup D^A$, where a subset $X$ is closed if $\delta(f, g) \cup \{g\} \subseteq X$ implies $f \in X$.

In order to ease the reading, we shall use in the rest of this paper the same notation for a completely join-irreducible element of $R(D, A)$ and an element of $A \sqcup D^A$. This is consistent with the above Corollary, as under the isomorphism we have $\hat{a} = \{a\}$ and $\hat{f} = \{f\}$. Thus $a$ shall stand for $\hat{a}$, and $f$ for $\hat{f}$.

In a spatial lattice $L$ (thus in a relational lattice), an inequation $s \leq t$ holds if and only if $j \leq s$ implies $j \leq t$, for each $j \in \mathcal{J}(L)$—thus we shall often consider inequations of the form $j \leq s$ with $j \in \mathcal{J}(L)$. When $L = R(D, A)$, the characterization of minimal join-cover leads to the following principle that we shall repeatedly use:

$$ f \leq x_1 \vee \dots \vee x_n \quad \text{iff} \quad \delta(f,g) \cup \{g\} \ll \{x_1, \dots, x_n\}, \quad \text{for some } g \in D^A. \quad (4) $$

## 5 Uniqueness of non-join-prime elements

For an inclusion we mean a pair $(s, t)$ of terms (in the signature of lattice theory) such that the equation $t \vee s = s$ (i.e. the inequality $t \leq s$) is derivable from the
usual axioms of lattices. Thus, the equality $s = t$ reduces to the inequality $s \le t$. We write $s \le t$ for a lattice inclusion and say it holds in a lattice if the identity $s = t$ holds in that lattice. Next, let us set

$$ \mathbf{d}_{\ell}(\mathbf{u}) := u_0 \wedge (u_1 \vee u_2), \quad \mathbf{d}_{\rho}(\mathbf{u}) := (u_0 \wedge u_1) \vee (u_0 \wedge u_2), $$

so $\mathbf{d}_{\ell}(\mathbf{u}) \le \mathbf{d}_{\rho}(\mathbf{u})$ is (an inclusion equivalent to) the usual distributive law. Consider the following inclusion:

$$ \begin{aligned} & x \wedge (\mathbf{d}_{\ell}(\mathbf{y}) \vee \mathbf{d}_{\ell}(\mathbf{z}) \vee w) \qquad (\text{Unjp}) \\ & \le (x \wedge (\mathbf{d}_{\rho}(\mathbf{y}) \vee \mathbf{d}_{\ell}(\mathbf{z}) \vee w)) \vee (x \wedge (\mathbf{d}_{\ell}(\mathbf{y}) \vee \mathbf{d}_{\rho}(\mathbf{z}) \vee w)). \end{aligned} $$

**Theorem 4.** The inclusion (Unjp) holds on relational lattices. As a matter of fact, (Unjp) holds in a pluperfect lattice if and only if every minimal join-cover contains at most one non-join-prime element.

*Proof.* Let us prove the first statement. To this goal, it will be enough to argue that any join-irreducible element below the left-hand side of the inclusion is below its right-hand side. Let $k$ be such a join-irreducible element. It is not difficult to see that if $k$ is join-prime, then $k$ is also below the right-hand side of the inclusion. Suppose then that $k$ is non-join-prime, whence $k = f$ for some $f \in D^A$. From $f \le \mathbf{d}_{\ell}(\mathbf{y}) \vee \mathbf{d}_{\ell}(\mathbf{z}) \vee w$ and (4), it follows that there exists $g \in D^A$ such that $\delta(f,g) \cup \{g\} \ll \{\mathbf{d}_{\ell}(\mathbf{y}), \mathbf{d}_{\ell}(\mathbf{z}), w\}$. In particular, $\{g\} \ll \{\mathbf{d}_{\ell}(\mathbf{y}), w\}$ or $\{g\} \ll \{\mathbf{d}_{\ell}(\mathbf{z}), w\}$. We firstly suppose that the last case holds. If $a \in \delta(f,g)$ and $a \le \mathbf{d}_{\ell}(\mathbf{y}) = y_0 \wedge (y_1 \vee y_2)$, then $a \le (y_0 \wedge y_1) \vee (y_0 \wedge y_2) = \mathbf{d}_{\rho}(\mathbf{y})$, since $a$ is join-prime. It follows that $\delta(f,g) \cup \{g\} \ll \{\mathbf{d}_{\rho}(\mathbf{y}), \mathbf{d}_{\ell}(\mathbf{z}), w\}$, whence $f \le x \wedge (\mathbf{d}_{\ell}(\mathbf{y}) \vee \mathbf{d}_{\ell}(\mathbf{z}) \vee w)$. If $\{g\} \ll \{\mathbf{d}_{\ell}(\mathbf{y}), w\}$, then we conclude similarly that $f \le x \wedge (\mathbf{d}_{\ell}(\mathbf{y}) \vee \mathbf{d}_{\rho}(\mathbf{z}) \vee w)$. Whence $k$ is below the right-hand side of this inclusion, and the inclusion holds since $k$ was arbitrary.

We leave the reader to generalize the argument above so to prove that if a pluperfect lattice is such that every minimal join-cover has at most one non-join-prime element, then (Unjp) holds. For the converse we argue as follows.

Let $L$ be a pluperfect lattice, let $k_x \in \mathcal{J}(L)$, $C_x \subseteq \mathcal{J}(L)$ with $k_x \subsetneq C_x$, and suppose that $k_y, k_z \in C_x$ are distinct and non-join-prime. For $u \in \{y, z\}$, since $k_u$ is non-join-prime, there is a non-trivial minimal join-cover $k_u \subsetneq C_u$; as every non-trivial minimal join-cover has at least two elements, let $C_{u,1}, C_{u,2}$ be a partition of $C_u$ such that $C_{u,i} \neq \emptyset$ for each $i = 1, 2$.

We construct a valuation which fails (Unjp). Let $x := k_x$, $y_0 := k_y$, $z_0 := k_z$, $w := \bigvee(C_x \setminus \{k_y, k_z\})$ and, for $u \in \{y, z\}$ and $i = 1, 2$, let $u_i := \bigvee C_{u,i}$. The left-hand side of the (Unjp) evaluates to $k_x$. Assume, by the way of contradiction, that (Unjp) holds, so $k_x$ is below the right-hand side of the inclusion. Since the only minimal join-cover $D$ of $k_x$ such that $D \ll \{k_x\}$ is $\{k_x\}$, either $k_x \le \mathbf{d}_{\rho}(\mathbf{y}) \vee \mathbf{d}_{\ell}(\mathbf{z}) \vee w$ or $k_x \le \mathbf{d}_{\ell}(\mathbf{y}) \vee \mathbf{d}_{\rho}(\mathbf{z}) \vee w$; let us assume that the first case holds. We have then $k_x \le \mathbf{d}_{\rho}(\mathbf{y}) \vee k_z \vee \bigvee(C_x \setminus \{k_y, k_z\}) = \mathbf{d}_{\rho}(\mathbf{y}) \vee \bigvee(C_x \setminus \{k_y\})$. Considering that $\mathbf{d}_{\rho}(\mathbf{y}) \le k_y$, Lemma 1 implies that $k_y = \mathbf{d}_{\rho}(\mathbf{y}) = (y_0 \wedge y_1) \vee (y_0 \wedge y_2)$. Since $k_y$ is join-irreducible $k_y = y_0 \wedge y_i$ for some $i \in \{1, 2\}$. Yet this is not possible, as such relation implies that $C_{y,i}$ is a join-cover of $k_y$; considering that $C_{y,i}$ is
a proper subset of the minimal join-cover $C_y$, this contradicts the minimality of $C_y$. If $k_x \le d_\ell(y) \lor d_\rho(z) \lor w$, then we get to a similar contradiction. Whence, $k_x$ is not below the right-hand side of (Unjp), which therefore fails. $\square$

It is worth noticing that the statement “every minimal join-cover contains exactly one non-join-prime element” is not definable by equations: for $A = D = \{0, 1\}$, there is a sublattice of $R(D, A)$ which fails this property.

While Theorem 4 gives a semantic characterization of (Unjp), we might also wish to measure its power at the syntactic level. Theorem 5 and Corollary 2 illustrate the deductive strength of (Unjp), by pinpointing an infinite set of its consequences.

**Theorem 5.** If $s_\ell = s_\rho$ and $t_\ell = t_\rho$ are equations valid on distributive lattices, then the equation

$$ (x \land (s_\ell \lor t_\ell \lor w)) \lor (x \land (s_\rho \lor t_\rho \lor w)) \\ = (x \land (s_\rho \lor t_\ell \lor w)) \lor (x \land (s_\ell \lor t_\rho \lor w)) $$

is derivable from (Unjp) and general lattice axioms.

*Proof.* For a lattice term $s$, let $dnf(s)$ be its disjunctive normal form. Recall that we can obtain $dnf(s)$ from $s$ by means of a sequence $s = s_0, \dots, s_n = dnf(s)$ where, for each $i = 0, \dots, n-1$, $s_{i+1}$ is obtained from $s_i$ by one application of the distributive law at the toplevel of the term, and by general lattice axioms. Thus, for two lattice terms $s^1, s^2$, let $s_i^1, i = 0, \dots, n$, and $s_j^2, j = 0, \dots, m$ be the sequences leading to the respective normal forms.

For $i = 0, \dots, n$ and $j = 0, \dots, m$, let now $t_{i,j} = x \land (s_i^1 \lor s_j^2 \lor w)$. Using (Unjp) and general lattice axioms, we can compute as follows:

$$ t_{0,0} = t_{1,0} \lor t_{0,1} = t_{2,0} \lor t_{1,1} \lor t_{0,2} = \dots \\ = \bigvee_{j=0,\dots,m} t_{n,j} \lor \bigvee_{i=0,\dots,n} t_{i,m} \stackrel{?}{=} t_{n,0} \lor t_{0,m}, $$

where only the last equality needs to be justified. Notice that the relation $s_{i+1}^k \le s_i^k$ holds in every lattice. Whence we have $s_{i'}^k \le s_i^k$ when $i < i'$, and both $t_{n,j} \le t_{n,0}$ and $t_{i,m} \le t_{i,0}$. It follows that the indexed join at the last line evaluates to $t_{n,0} \lor t_{0,m}$. We have derived, up to now, the identity

$$ x \land (s^1 \lor s^2 \lor w) = (x \land (dnf(s^1) \lor s^2 \lor w)) \lor (x \land (s^1 \lor dnf(s^2) \lor w)) $$

for every pair of lattice terms $s^1$ and $s^2$.

Let us call co-clause a conjunction of variables. By using lattice axioms only, we can suppose that, within $dnf(t)$, there are no repeated literals in co-clauses and that no co-clause subsumes another. Under this assumption, we have that an identity $s_\ell = s_\rho$ holds in all distributive lattices if and only if $dnf(s_\ell)$ is equal to $dnf(s_\rho)$. Whence, to derive the statement of the Theorem, we can compute as follows:

$$ (x \land (s_\ell \lor t_\rho \lor w)) \lor (x \land (s_\rho \lor t_\ell \lor w)) $$
$$
\begin{align*}
&= (x \wedge (\mathbf{dnf}(s_\ell) \vee t_\rho \vee w)) \vee (x \wedge (s_\ell \vee \mathbf{dnf}(t_\rho) \vee w)) \\
&\phantom{= (x \wedge (\mathbf{dnf}(s_\ell) \vee t_\rho \vee w))} \vee (x \wedge (\mathbf{dnf}(s_\rho) \vee t_\ell \vee w)) \vee (x \wedge (s_\rho \vee \mathbf{dnf}(t_\ell) \vee w)) \\
&= (x \wedge (\mathbf{dnf}(s_\rho) \vee t_\rho) \vee w) \vee (x \wedge (s_\ell \vee \mathbf{dnf}(t_\ell) \vee w)) \\
&\phantom{= (x \wedge (\mathbf{dnf}(s_\rho) \vee t_\rho) \vee w) \vee} \vee (x \wedge (\mathbf{dnf}(s_\ell) \vee t_\ell \vee w)) \vee (x \wedge (s_\rho \vee \mathbf{dnf}(t_\rho) \vee w)) \\
&= (x \wedge (\mathbf{dnf}(s_\ell) \vee t_\ell \vee w)) \vee (x \wedge (s_\ell \vee \mathbf{dnf}(t_\ell) \vee w)) \\
&\phantom{= (x \wedge (\mathbf{dnf}(s_\ell) \vee t_\ell \vee w)) \vee} \vee (x \wedge (\mathbf{dnf}(s_\rho) \vee t_\rho \vee w)) \vee (x \wedge (s_\rho \vee \mathbf{dnf}(t_\rho) \vee w)) \\
&\multicolumn{2}{c}{\text{—where we have permuted the order of the four joinands}} \\
&= (x \wedge (s_\ell \vee t_\ell \vee w)) \vee (x \wedge (s_\rho \vee t_\rho \vee w)). \quad \square
\end{align*}
$$

In [12] two equations were shown to hold on relational lattices. One of them
is (RL2) that we describe next. Set

$$
\mathbf{d}_{\ell}^{o}(\boldsymbol{u}) := (u_0 \vee u_1) \wedge (u_0 \vee u_2), \quad \mathbf{d}_{\rho}^{o}(\boldsymbol{u}) := u_0 \vee (u_1 \wedge u_2),
$$

the equation is

$$
x \wedge (d_{\ell}^{o}(\mathbf{y}) \vee d_{\ell}^{o}(\mathbf{z})) \leq (x \wedge (d_{\rho}^{o}(\mathbf{y}) \vee d_{\ell}^{o}(\mathbf{z}))) \vee (x \wedge (d_{\ell}^{o}(\mathbf{y}) \vee d_{\rho}^{o}(\mathbf{z}))) \quad (\text{RL2})
$$

**Corollary 2.** If $s_\ell = s_\rho$ and $t_\ell = t_\rho$ are equations valid on distributive lattices, then the inequation

$$
(x \wedge (s_{\ell} \vee t_{\ell} \vee w)) \leq (x \wedge (s_{\rho} \vee t_{\ell} \vee w)) \vee (x \wedge (s_{\ell} \vee t_{\rho} \vee w)) \quad (5)
$$

is derivable from (Unjp). In particular (RL2) is derivable from (Unjp).

The Corollary follows from the Theorem and from the fact that $x \leq x \vee y$. In order to derive (RL2) from (5) (if we do not include the bottom constant $\perp$ as part of the signature of lattice theory), we instantiate $s_\ell := d_\ell^o(\mathbf{y})$, $s_\rho := d_\rho^o(\mathbf{y})$, $t_\ell := d_\ell^o(\mathbf{z})$, $t_\rho := d_\rho^o(\mathbf{z})$, and $w := d_\rho^o(\mathbf{z})$.

It can be shown that (Unjp) is not derivable from (RL2)—mainly due to
the role of the variable *w* in the (Unjp). The construction of a lattice *L* satis-
fying (RL2) but failing (Unjp) proceeds via the construction of its OD-graph
⟨*J*(*L*), ≤, ⊲<sub>*m*</sub>⟩. Due to the consistent number of variables in the two equations,
an automated tool such as Mace4 [13] could not help finding a countermodel.
Similarly, automated tools such as Prover9 and Waldmeister [13,6] were of no
help to show that (RL2) is a consequence of (Unjp).

Natural questions—e.g. decidability—may be raised concerning the equa-
tional theory of (Unjp). Since we can give an easy semantic proof that an equa-
tion of the form (5) holds on finite lattices (or pluperfect) satisfying (Unjp), a
reasonable conjecture is that this theory has some sort of finite model property.
Yet, proving this might not be immediate, since the variety of lattices satisfying
(Unjp) is not locally finite (i.e., not every finitely generated lattice satisfying
(Unjp) is finite). The construction used in [16, Proposition 7.5] may be used
to argue that the lattice freely generated in this variety by three generators is
infinite.
# 6 Symmetry and pairwise completeness

Due to its syntactic shape (Unjp) falls in a class of inclusions described in [16, Section 8] that admit a correspondent property in the OD-graph. Here, the meaning of the word correspondent is analogous to its use in modal logic, where some formulas might be uniformly valid in a frame if and only if the frame satisfies a correspondent first order property. Thus Theorem 4 is not completely unexpected. A more surprising result comes from considering the three equations below, that fall outside the syntactic fragment described in [16]; a strengthening of Lemma 1 (Lemma 4 to follow) allows to characterize the OD-graphs of pluperfect lattices satisfying (Unjp) and these equations, see Theorem 8.

$$x \wedge (y \vee z) \le \qquad (\text{SymPC})$$

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

$$x \wedge ((y \wedge z) \vee (y \wedge x) \vee (z \wedge x)) \le (x \wedge y) \vee (x \wedge z) \qquad (\text{VarRL1})$$

$$x \wedge ((x \wedge y) \vee \mathbf{d}_{\ell}(\mathbf{z})) \le (x \wedge ((x \wedge y) \vee \mathbf{d}_{\rho}(\mathbf{z}))) \vee (x \wedge \mathbf{d}_{\ell}(\mathbf{z})) \qquad (\text{RMod})$$

Let us first illustrate the way in which these equations hold in relational lattices. In particular, the proof shall illustrate the crucial role played by symmetry and pairwise completeness—i.e., condition (3)—of the ultrametric space ($D^A, \delta$).

**Theorem 6.** *The inclusions (SymPC), (VarRL1), (RMod) hold in relational lattices.*

*Proof.* (SymPC). Let $k$ be a join-irreducible element below $x \wedge (y \vee z)$. If $k$ is join-prime, then $k$ is also below $(x \wedge y) \vee (x \wedge z)$, whence it is below the right-hand side of this inclusion. Therefore, let $k$ be non-join-prime, so $k = f$ for some $f \in D^A$; by (4), let $g \in D^A$ be such that $\delta(f, g) \cup \{g\} \ll \{y, z\}$. Let us suppose first that $g \le z$. Since $\delta(f, g) \ll \{y, z\}$, using pairwise completeness we can find $h$ such that $\delta(f, h) \ll \{y\}$ and $\delta(h, g) \ll \{z\}$. It follows that $h \le \bigvee \delta(h, g) \vee g \le z$; moreover, since $f \le x$, $\delta(h, f) = \delta(f, h)$, and $\delta(f, h) \ll \{y\}$, then $h \le \delta(h, f) \vee f \le x \vee y$. Consequently, we have $h \le z \wedge (x \vee y)$ and, considering that $\delta(f, h) \ll \{y\}$, we have $f \le x \wedge (y \vee (z \wedge (x \vee y)))$. If $g \le y$, then we similarly deduce that $f \le x \wedge (z \vee (y \wedge (x \vee z)))$. In both cases, $f$ is below the right-hand side of this inclusion.

(VarRL1). Let $k$ be below the left-hand side of this inclusion. If $k$ is join-prime, then it is below the right-hand side of this inclusion as well. Otherwise $k = f$ is non-join-prime and $\delta(f, g) \cup \{g\} \ll \{y \wedge z, y \wedge x, z \wedge x\}$ for some $g \in D^A$.

Since $g \le r$ for some $r \in \{y \wedge z, y \wedge x, z \wedge x\}$, we consider three cases; by pairwise completeness we can also assume that $g$ is the only element of $\delta(f, g) \cup \{g\}$ below $r$—since if $\delta(f, g') \ll \{y \wedge z, y \wedge x, z \wedge x\} \setminus \{r\}$ and $\delta(g', g) \ll \{r\}$, then $g' \le r$. Also, the last two cases, $g \le y \wedge x$ and $g \le z \wedge x$, are symmetric in $y$ and $z$, so that we consider among them the second-to-last only.

Suppose firstly that $g \le y \wedge z$. Then, from $\delta(g, f) = \delta(f, g) \ll \{x \wedge y, x \wedge z\} \ll \{x\}$ and $f \le x$, we deduce $g \le x$; whence $g \le x \wedge y$ and $f \le (x \wedge z) \vee (x \wedge y)$.
Suppose next that $g \le x \wedge y$. By pairwise completeness, let $h$ be such that $\delta(f, h) \ll \{x \wedge z\}$ and $\delta(h, g) \ll \{y \wedge z\}$. We deduce then $h \le y$ from $\delta(h, g) \ll \{y\}$ and $g \le y$, and $h \le x$, from $\delta(h, f) = \delta(f, h) \ll \{x\}$ and $f \le x$. Thus $h \le x \wedge y$ and $f \le (x \wedge z) \vee (x \wedge y)$.

(RMod). Let $k$ be a join-irreducible below the left-hand side of this inclusion. If $k$ is join-prime, then $k$ is below $x \wedge ((x \wedge y) \vee d_\rho(z))$. Otherwise $k = f$ and, for some $g \in D^A$, $\delta(f, g) \cup \{g\} \ll \{x \wedge y, d_\ell(z)\}$. If $g \le x \wedge y$, then all the elements that are not below $x \wedge y$ are below $d_\ell(z)$ and join-prime, whence they are below $d_\rho(z)$. It follows that $f \le x \wedge ((x \wedge y) \vee d_\rho(z))$. Otherwise $g \le d_\ell(z)$ and, by pairwise completeness, we can also assume that $g$ is the only element below $d_\ell(z)$, so $\delta(f, g) \ll \{x \wedge y\}$. It follows then that $\delta(g, f) \cup \{f\} = \delta(f, g) \cup \{f\} \ll \{x\}$, $g \le x$, whence $g \le x \wedge d_\ell(z)$. Consequently, $f \le (x \wedge y) \vee (x \wedge d_\ell(z)) \le (x \wedge ((x \wedge y) \vee d_\rho(z))) \vee (x \wedge d_\ell(z))$. $\square$

In [12] a second inclusion was shown to hold on relational lattices:

$$x \wedge ((y \wedge (z \vee x)) \vee (z \wedge (y \vee x))) \le (x \wedge y) \vee (x \wedge z) \quad (\text{RL1})$$

The same kind of tools used in the proof of Theorem 6 can be used to argue that this inclusion holds on relational lattices. The reader will have noticed the similarity of (VarRL1) with (RL1). As a matter of fact, (VarRL1) was suggested when trying to derive (RL1) from (Unjp) and the other equations as in the following Proposition.

**Proposition 1.** (RL1) is a consequence of (Unjp), (RMod) and (VarRL1).

*Proof.* Using (Unjp) and considering that $y \wedge z \le z \wedge (y \vee x)$, we have:

$$\begin{aligned} & x \wedge ((y \wedge (z \vee x)) \vee (z \wedge (y \vee x))) \\ & = (x \wedge ((y \wedge x) \vee (z \wedge (y \vee x)))) \vee (x \wedge ((y \wedge (z \vee x)) \vee (z \wedge x))). \end{aligned}$$

Using now (RMod) and considering that $x \wedge z \le y \vee x$, we compute as follows:

$$\begin{aligned} & x \wedge ((y \wedge x) \vee (z \wedge (y \vee x))) \\ & = (x \wedge ((y \wedge x) \vee (z \wedge y) \vee (z \wedge x))) \vee (x \wedge z \wedge (y \vee x)) \\ & = (x \wedge ((y \wedge x) \vee (z \wedge y) \vee (z \wedge x))) \vee (x \wedge z) \\ & = x \wedge ((y \wedge z) \vee (y \wedge x) \vee (z \wedge x)). \end{aligned}$$

Considering the symmetric role of $y$ and $z$, we obtain:

$$\begin{aligned} & x \wedge ((y \wedge (z \vee x)) \vee (z \wedge (y \vee x))) = x \wedge ((y \wedge z) \vee (y \wedge x) \vee (z \wedge x)) \\ & = (x \wedge y) \vee (x \wedge z), \quad \text{by (VarRL1).} \quad \square \end{aligned}$$

We present now what we consider our strongest result in the study of the equational theory of relational lattices. To this end, let us denote by [[AxRel]] the (set composed of the) four equations (Unjp), (VarRL1), (RMod) and (SymPC). Also, given that we restrict to lattices satisfying (Unjp), and considering the characterization given with Theorem 4, it is convenient to introduce the notation $k_0 \triangleleft_m^C k_1$ for the statement $k_0, k_1 \in J(L)$, $k_1$ is non-join-prime, $k_1 \notin C$, and $k_0 \triangleleft_m C \cup \{k_1\}$.
**Theorem 7.** Let L be a finite atomistic lattice. Then $L \models [[AxRel]]$ if and only if every nontrivial minimal join-cover contains exactly one non-join-prime element and, moreover, the following properties hold in the OD-graph:

* If $k_0 \prec_m^C k_1$, then $k_1 \prec_m^C k_0$. (6)

* If $k_0 \prec_m^{C_0 \sqcup C_1} k_2$, then $k_0 \prec_m^{C_0} k_1$ and $k_1 \prec_m^{C_1} k_2$, for some $k_1 \in \mathcal{J}(L)$.

Given Theorem 7, it becomes tempting to look for a representation Theorem. Given a pluperfect atomistic lattice satisfying the above four equations, we would like to define an ultrametric space on the set of non-join-prime elements with distance valued on the powerset of the join-prime ones, and then argue that the lattice constructed via the standard action, defined in (2), is isomorphic to the given lattice. Unfortunately, this idea does not work, since if we try to set $\delta(k_0, k_1) = C$ whenever $k_0 \prec_m^C k_1$, this might be ill defined since the implication "$k_0 \prec_m^C k_1$ and $k_0 \prec_m^D k_1$ implies $C = D$" might fail. Moreover, there is no equation nor quasiequation enforcing this, as an immediate consequence of the next Proposition.

**Proposition 2.** There is an atomistic sublattice of $R(\{0,1\}, \{0,1\})$ which does not arise from an ultrametric space.

Theorem 7 is a consequence of a more general Theorem, to be stated next, characterizing the OD-graphs of pluperfect lattices in the variety axiomatized by [[AxRel]]. While the conditions stated next may appear quite complex, they are the ones to retain if we aim at studying further the theories of relational lattices by duality—e.g., a sublattice of a relational lattice need not be atomistic.

**Theorem 8.** A pluperfect lattice belongs to the variety axiomatized by [[AxRel]] if and only if every minimal join-cover contains at most one non-join-prime element and, moreover, the following properties hold in its OD-graph:

* If $k_0 \prec_m^C C$, then there exists at most one $c \in C$ with $c \le k_0$. ($\pi$-VarRL1)

* If $k_0 \prec_m^C k_1$, then no element of C is below $k_0$. ($\pi$-RMod)

* if $k \prec_m^{C_0 \sqcup C_1} C_1$ with $C_0, C_1$ non-empty, then for some $k' \in \mathcal{J}(L)$, either $k \prec_m^{C_0 \sqcup C_1} \{k'\} \sqcup C_1$, $k' \prec_m^{C_0}$, and $k' \le \bigvee C_1 \lor k$, or $k \prec_m^{C_0 \sqcup \{k'\}} \{k'\}$, $k' \prec_m^{C_1}$, and $k' \le \bigvee C_0 \lor k$. ($\pi$-StrongSymPC)

Let us notice that the conditions

* If $k_0 \prec_m^{C_0 \sqcup C_1} k_2$ then, for some $k_1 \in \mathcal{J}(L)$, $k_0 \prec_m^{C_0} k_1$, $k_1 \prec_m^{C_1} k_2$, and $k_1 \le \bigvee C_0 \lor k_0$. ($\pi$-SymPC)

* If $k_0 \prec_m^C k_1$, then $k_1 \le \bigvee C \lor k_0$ ($\pi$-Sym)

follow from the above properties. On atomistic pluperfect lattices the last condition is equivalent to (6).
**Lemma 3.** If L is a pluperfect lattice with L $|=$ (Unjp) and whose OD-graph satisfies $(\pi$-StrongSymPC) and $(\pi$-RMod), then $(\pi$-SymPC) holds as well.

*Proof.* Let $k_1 \triangleleft_C_0 \sqcup C_1 \sqcup \{k_2\}$ with $k_2 \in \mathcal{J}(L)$ and non-join-prime, and use $(\pi$-StrongSymPC) to find $k_1$ such that either (i) $k_0 \triangleleft_C \{k_1\} \sqcup C_1 \sqcup \{k_2\}$ and $k_1 \le k_0 \lor \bigvee C_1 \lor k_2$, or (ii) $k_0 \triangleleft_C C_0 \sqcup \{k_1\}$ and $k_1 \le k_0 \lor \bigvee C_0$. Let us argue, by contradiction, that (i) cannot arise. By (Unjp), $k_1$ is join-prime, whence the relation $k_1 \le k_0 \lor \bigvee C_1$ yields $k_1 \le k_0$. This, however, contradicts $(\pi$-RMod). $\square$

We close this section by proving Theorem 8. To this end, we need a generalization of Lemma 1. As the refinement relation is an extension to subsets of the order relation, the relation $\triangleleft_m$, defined next, can be considered as an extension to subsets of the minimal join-covering relation.

**Definition 2.** Let L be a pluperfect lattice and let X, Y $\subseteq \mathcal{J}(L)$ be antichains. Put $X \triangleleft_m Y$ if $X \ll \{\bigvee Y\}$ and $y \in C_{x_y}$ for some $x_y \in X$, for each $y \in Y$ and whenever $\{C_x | x \in X\}$ is a family of coverings of the form $x \triangleleft_m C_x \ll Y$.

**Lemma 4.** Let L be a pluperfect lattice and let $j \triangleleft_C C_0 \sqcup C_1$. Suppose that $\bigvee X \le \bigvee C_0$ and $j \le \bigvee X \lor \bigvee C_1$. Then there exists a minimal join-cover of the form $j \triangleleft_m D_0 \sqcup C_1$ with $D_0 \ll X$ and $D_0 \triangleleft_m C_0$.

While the proof that a pluperfect lattice whose OD-graphs satisfies those properties essentially mimics the proof of Theorem 6, we prove instead the converse direction through a series of Lemmas.

**Lemma 5.** If (VarRL1) holds on a pluperfect lattice, then its OD-graph satisfies $(\pi$-VarRL1).

*Proof.* Suppose $C = \{k_1\} \sqcup \{k_2\} \sqcup D$ with $k_0 \triangleleft_C C$ and $k_1, k_2 \le k_0$. Let $x := k_0$, $y := k_1 \lor \bigvee D$, $z := k_2 \lor \bigvee D$. Then $k_1 \le x \land y$, $k_2 \le x \land z$ and $\bigvee D \le y \land z$, whence the left-hand side of (VarRL1) evaluates to $k_0$, which is therefore below the right-hand side of this inclusion. It follows that either $k_0 \le y$, or $k_0 \le z$, in both cases contradicting the fact that C is a minimal join-cover. $\square$

The inclusion

$$x \land (y \lor \mathbf{d}_{\ell}(z)) \le (x \land (y \lor \mathbf{d}_{\rho}(z))) \lor (x \land (y \lor (\mathbf{d}_{\ell}(z) \land (y \lor x))), \quad (\text{Sym})$$

is derivable from (Unjp), (SymPC) and (RMod). It can also be shown that (RMod) is a consequence of (Sym).

**Lemma 6.** If (Sym) holds in a pluperfect lattice, then its OD-graph satisfies $(\pi$-Sym).

*Proof.* Suppose that the inclusion holds and let $k_0 \triangleleft_m^C k_1$. Since $k_1$ is non-join-prime, there exists a minimal join-cover $k_1 \triangleleft_m D$ which we can partition into two non empty subsets $D_1$ and $D_2$. Let now $x := k_0$, $y := \bigvee C$, $z_0 := k_1$, $z_1 = \bigvee D_1$, $z_2 = \bigvee D_2$. Then, the left-hand side of the inclusion evaluates to $k_0,$
which therefore is below the right-hand side. Considering that $x$ is $k_0$ and that the unique minimal join-cover of $k_0$ whose elements are all below $k_0$ is $\{k_0\}$, it follows that either $k_0 \le y \lor d_\rho(z)$ or $k_0 \le y \lor (d_\ell(z) \land (y \lor x))$.

Argue that $d_\rho(z) < d_\ell(z)$, since $k_1$ is join-irreducible, whence by Lemma 1, $\{y, d_\rho(z)\}$ is not a cover of $k_0$, excluding the first case. Therefore $\{y, d_\ell(z)\} \land (y \lor x)$ is a cover of $k_0$, whence, by Lemma 1, $k_1 = d_\ell(z) \land (y \lor x)$, showing that $k_1 \le y \lor x = \bigvee C \lor k_0$ and proving the statement. □

**Lemma 7.** If $L$ is a pluperfect lattice such that $L \models [[AxRel]]$, then $(\pi$-RMod) holds in its OD-graph.

*Proof.* Let $k_0 \subset_C^C k_1$ and put $C = C_0 \sqcup C_1$ with $C_0 \ll \{k_0\}$ and $c \not\le k_0$ for each element $c \in C_1$. As (Sym) whence $(\pi$-Sym) hold, we have $k_1 \le \bigvee C_1 \lor \bigvee C_0 \lor k_0$.

We consider next equation (RMod). Put $x := k_0$, $y := \bigvee C_0$, $z_0 := \bigvee C_1 \lor k_1$, $z_1 := \bigvee C_1 \lor \bigvee C_0$, $z_2 := k_0$. From $k_1 \le \bigvee C_1 \lor \bigvee C_0 \lor k_0$, we get $z_0 \land (z_1 \lor z_2) = z_0$. Whence, the left-hand side of (RMod) evaluates to $k_0$ so $k_0$ is below the right-hand side of (RMod). Considering that $\{k_0\}$ is the unique minimal join-cover of $k_0$ whose elements are all below $k_0$, it follows that either $k_0 \le z_0 \land (z_1 \lor z_2)$ or $k_0 \le y \lor (z_0 \land z_1) \lor (z_0 \land z_2)$.

As $k_0 \not\le \bigvee C_1 \lor k_1 = z_0$, it follows that $k_0 \le y \lor (z_0 \land z_1) \lor (z_0 \land z_2)$. We can use then Lemma 4 to deduce that $k_0$ has a minimal join-cover of the form $k_0 \subset_C^C C_0 \sqcup D$, with $D \ll \{z_0 \land z_1, z_0 \land z_2\} \ll \{z_1, z_2\}$. If all the elements of $D$ are below $z_1 = \bigvee C_0 \lor \bigvee C_1$, then

$$k_0 \le \bigvee C_0 \lor \bigvee D \le \bigvee C_0 \lor \bigvee C_1,$$

contradicting the minimality of $k_0 \subset_C^C C_0 \sqcup C_1 \sqcup \{k_1\}$. Therefore, at least one element of $D$ is below $z_2 = k_0$. If $C_0 \ne \emptyset$, then in the minimal join-cover $C_0 \sqcup D$ there are at least two elements that are below $k_0$. This however contradicts $(\pi$-VarRL1), whence (VarRL1). We have, therefore, $C_0 = \emptyset$. □

**Lemma 8.** If $L$ is a pluperfect lattice with $L \models [[AxRel]]$, then $(\pi$-StrongSymPC) holds in its OD-graph.

*Proof.* By Lemmas 5 and 7, $(\pi$-RMod) and $(\pi$-VarRL1) hold in the OD-graph.

Let $x := k_0$, $y := \bigvee C_0$, $z := \bigvee C_1$. Then the left-hand side of (SymPC) evaluates to $k_0$ which is therefore below the right-hand side. Thus, by Lemma 4, there is a minimal join-cover of the form $k_0 \subset_C^C D_0 \sqcup D_1$ with either (i) $D_0 \subset_C^C C_0$, $D_0 \ll \{y \land (x \lor z)\}$, and $D_1 = C_1$, or (ii) $D_0 = C_0$, $D_1 \subset_C^C C_1$, and $D_1 \ll \{z \land (x \lor y)\}$.

W.l.o.g. we can suppose that (i) holds. From $D_0 \ll \{y \land (x \lor z)\} \ll \{x \lor z\} = \{k_0 \lor \bigvee C_1\}$, we can argue as follows. We notice first that if an element of $D_0$ is join-prime, then it is either below $k_0$ or below some $c \in C_1$; since $D_0 \sqcup C_1$ is an antichain, this element is below $k_0$. Therefore, if all the elements of $D_0$ are join-prime, then, by $(\pi$-VarRL1), $D_0 = \{k'\}$. Otherwise, there exists a non-join-prime element $k'$ in $D_0$ and, by (Unjp), this is the only non-join-prime in $D_0$. Write $D_0 = \{k'\} \sqcup E$, then every element of $E$ is join-prime and, as seen before,
we need to have $E \ll \{k_0\}$. Then $(\pi$-RMod) enforces $E_0 = \emptyset$ and $D_0 = \{k'\}$. In both cases, the relation $\{k'\} = D_0 \ll_{\mathfrak{m}} C_0$ yields $k' \prec_{\mathfrak{m}} C_0$. $\square$

Finally, in order to understand the structure of finite lattices in the variety of axiomatized by [[AxRel]], let $\mathcal{J}_p(L)$ denote the set of join-prime elements of $L$ and consider the following property:

* If $k_0 \prec_m C$ and $C \subseteq \mathcal{J}_p(L)$, then $c_0 \le k_0$ for some $c_0 \in C$ $(\pi$-JP)

The next Lemma ensures the existence of a non-join-prime element in a cover in finite atomistic lattices, as stated in Theorem 7.

**Lemma 9.** If a finite lattice $L$ satisfies [[AxRel]], then $(\pi$-JP) holds in its OD-graph. In particular, if $L$ is atomistic, then $k_0 \prec_m C$ implies that $k_1 \in C$ for some non-join-prime $k_1$.

It can be shown that the finiteness assumption in Lemma 9 is necessary.

# 7 Conclusions and further directions

**Some undecidable problems.** Our main result, Theorem 7, characterizes the OD-graphs of finite atomistic lattices satisfying [[AxRel]] as structures similar to frames for the commutator logic $[S5]^{n}$, the multimodal logic with $n$ distinct pairwise commuting S5 modal operators, see [10]. We exemplify next how to take advantage of such similarity and of the existing theory on combination of modal logics, to deduce undecidability results. As this is not the main goal of the paper, we delay a full exposition of these ideas to an upcoming set of notes.

An $[S5]^{n}$ frame is a structure $\mathfrak{F} = (F, R_1, \dots, R_n)$ where each $R_i$ is an equivalence relation on $F$ and, moreover, the confluence property holds: if $i \neq j$, $xR_iy$ and $xR_jz$, then $yR_jw$ and $zR_iw$ for some $w \in F$. A particular class of $[S5]^{n}$ frames are the universal S5$^n$-products, those of the form $\mathfrak{A} = (F, R_1, \dots, R_n)$ with $F = X_1 \times \dots \times X_n$ and $(x_1, \dots, x_n)R_i(y_1, \dots, y_n)$ if and only if $x_j = y_j$ for each $j \neq i$.

For a frame $\mathfrak{F} = (W, R_1, \dots, R_n)$ and $X \subseteq \{1, \dots, n\}$, let us say that $Y \subseteq W$ is $X$-closed if $w_0 \in Y$, whenever there is a path $w_0 R_{i_0} w_1 \dots w_{k-1} R_{i_k} w_k$ with $\{i_0, \dots, i_k\} \subseteq X$ and $w_k \in Y$. Then $X$-closed subsets are closed under intersections, so subsets of $\{1, \dots, n\}$ give rise to closure operators $\langle X \rangle$ and to an action as defined in Section 3. Let $\mathcal{L}(\mathfrak{F}) = P(\{1, \dots, n\}) \times_j P(W)$ and notice that $\mathcal{L}(\mathfrak{F})$ is atomistic. A frame $\mathfrak{F}$ is initial if there is $f_0 \in F$ such every other $f \in F$ is reachable from $f_0$; it is full if, for each $i = 1, \dots, n$, $R_i$ is not included in the identity. If $\mathfrak{F}$ is initial and full, then $\mathcal{L}(\mathfrak{F})$ is subdirectly irreducible. A $p$-morphism is defined as usual in modal logic. The key observation leading to undecidability is the following statement.

**Theorem 9.** There is a surjective $p$-morphism from a universal S5$^n$-product frame $\mathfrak{A}$ to a full initial frame $\mathfrak{F}$ if and only if $\mathcal{L}(\mathfrak{F})$ embeds in a relational lattice.
*Proof (Sketch).* The construction $\mathcal{L}$ is extended to a contravariant functor, so if $\psi : \mathfrak{U} \to \mathfrak{F}$ is a $p$-morphim, then we have an embedding $\mathcal{L}(\psi)$ of $\mathcal{L}(\mathfrak{F})$ into $\mathcal{L}(\mathfrak{U})$. We can assume that all the components $X_1, \dots, X_n$ of $\mathfrak{U}$ are equal, so $X_i = X$ for each $i = 1, \dots, n$; if this is the case, then $\mathcal{L}(\mathfrak{U})$ is isomorphic to the relational lattice $\mathbb{R}\{\{1, \dots, n\}, X\}$.

The converse direction is subtler. Let $\chi : \mathcal{L}(\mathfrak{F}) \to \mathbb{R}(A, D)$ be a lattice embedding; since $\mathcal{L}(\mathfrak{F})$ is subdirectly-irreducible, we can suppose that $\chi$ preserves bounds; its left adjoint $\mu : \mathbb{R}(A, D) \to \mathcal{L}(\mathfrak{F})$ is then surjective. Since both $\mathcal{L}(\mathfrak{F})$ and $\mathbb{R}(D, A)$ are generated (under possibly infinite joins) by their atoms, each atom $x \in \mathcal{L}(\mathfrak{F})$ has a preimage $y \in \mathbb{R}(D, A)$ which is an atom. Consider now $S_0 = \{f \in D^A \mid \mu(f)$ is a non-join-prime atom$\}$ and make it into a $\mathcal{P}(\{1, \dots, n\})$-valued ultrametric space by letting $\delta_{S_0}(f,g) = \mu(\delta(f,g)) \subseteq \{1, \dots, n\}$—we use here the fact that $\mu$ sends join-prime elements to join-prime elements. $S_0$ is shown to be a pairwise complete ultrametric space over $\{1, \dots, n\}$. We prove that pairwise complete ultrametric spaces over a finite set $B$ are in bijection with universal $S_5^n$-product frames, with $n = \text{card } B$. Then the restriction of $\mu$ to $S_0$ is a surjective $p$-morphism from $S_0$ to (a frame isomorphic to) $\mathfrak{F}$. $\square$

In view of the following statement, which relies on [8] and can be inferred from [7]: "for $n \ge 3$, it is undecidable whether, given a finite full initial frame $\mathfrak{F}$, there is a surjective $p$-morphism from a universal $S_5^n$-product $\mathfrak{U}$ to $\mathfrak{F}$", we deduce the following undecidability results, which partially answer Problem 4.10 in [12].

**Corollary 3.** It is undecidable whether a finite subdirectly irreducible atomistic lattice embeds into a relational lattice. Consequently, the quasiequational theory of relational lattices in the pure lattice signature is also undecidable.

**Comparison with Litak et al. [12].** We have presented our first contribution to the study of the equational theory of relational lattices. In [12] two equations in the larger signature with the header constant are presented as a base for the equational theory of relational lattices. As mentioned there, the four equations of [[AxRel]] are derivable from these two equations. Therefore, we can also think of the present work as a contribution towards assessing or disproving completeness of these two axiomatizations. Yet, we wish to mention here and emphasize some of our original motivations. Lattice theoretic equations are quite difficult to grasp, in particular if considered on the purely syntactic side, as done for example in [12]. Duality theory attaches a meaning to equations via the combinatorial properties of the dual spaces. This process is nowadays customary in modal and intuitionistic logic and gives rise to a well defined area of research, correspondence theory. Our aim was to attach meaning to the equations of relational lattices. The answer we provide is, at the present state of research, via the relevant combinatorial properties, symmetry and pairwise completeness. From this perspective, the results presented in Section 6 undoubtedly need further understanding. In particular it is worth trying to modularize them, so as to discover equations exactly corresponding to symmetry or, respectively, to pairwise completeness; alternatively, argue that these equations do not exist. Finally, the
present work opens new directions and challenges for the duality theory devel-
oped in [16]—of which, we hope we have illustrated the fruitfulness—including
a better understanding of how to generalize it to the infinite case, new mecha-
nisms by which to devise correspondence results, natural conjectures concerning
equations having correspondents in finite lattices.

References

1. Ackerman, N.: Completeness in generalized ultrametric spaces. p-Adic Numbers Ultrametric Anal. Appl. 5(2), 89–105 (2013)

2. Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13(6), 377–387 (Jun 1970)

3. Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge Uni-
versity Press, New York (2002)

4. Freese, R., Ježek, J., Nation, J.: Free lattices. Providence, RI: American Mathe-
matical Society (1995)

5. Grätzer, G.: General Lattice Theory. Basel (1998), new appendices by the author with B. A. Davey, R. Freese, B. Ganter, M. Greferath, P. Jipsen, H. A. Priestley, H. Rose, E. T. Schmidt, S. E. Schmidt, F. Wehrung and R. Wille

6. Hillenbrand, T., Löchner, B.: Waldmeister (1996–2008),
http://www.waldmeister.org/

7. Hirsch, R., Hodkinson, I., Kurucz, A.: On modal logics between K × K × K and S5 × S5 × S5. The Journal of Symbolic Logic 67, 221–234 (3 2002)

8. Hirsch, R., Hodkinson, I.: Representability is not decidable for finite relation alge-
bras. Trans. Amer. Math. Soc. 353, 1403–1425 (2001)

9. Joyal, A., Tierney, M.: An extension of the Galois theory of Grothendieck. Mem. Amer. Math. Soc. 51(309) (1984)

10. Kurucz, A.: Combining modal logics. In: Patrick Blackburn, J.V.B., Wolter, F. (eds.) Handbook of Modal Logic, Studies in Logic and Practical Reasoning, vol. 3, pp. 869–924. Elsevier (2007)

11. Lawvere, F.W.: Metric spaces, generalized logic and closed categories. Rendiconti del Seminario Matematico e Fisico di Milano (XLIII), 135–166 (1973)

12. Litak, T., Mikulás, S., Hidders, J.: Relational lattices: From databases to universal algebra. JLAMP (2015), to appear, doi:10.1016/j.jlamp.2015.11.008

13. McCune, W.: Prover9 and Mace4 (2005–2010),
http://www.cs.unm.edu/~{}mccune/prover9/

14. Nation, J.B.: An approach to lattice varieties of finite height. Algebra Universalis 27(4), 521–543 (1990)

15. Priess-Crampe, S., Ribemboim, P.: Equivalence relations and spherically complete ultrametric spaces. C. R. Acad. Sci. Paris 320(1), 1187–1192 (1995)

16. Santocanale, L.: A duality for finite lattices (Sep 2009), preprint, available from
http://hal.archives-ouvertes.fr/hal-00432113

17. Spight, M., Tropashko, V.: Relational lattice axioms (2008), preprint available at
http://arxiv.org/abs/0807.3795

18. Tropashko, V.: Relational algebra as non-distributive lattice (2006), preprint, avail-
able at http://arxiv.org/abs/cs/0501053