# Override and restricted union for partial functions

Tim Stokes

###### Abstract

The override operation $\sqcup$ is a natural one in computer science, and has
connections with other areas of mathematics such as hyperplane arrangements.
For arbitrary functions $f$ and $g$, $f\sqcup g$ is the function with domain
$\operatorname{dom}(f)\cup\operatorname{dom}(g)$ that agrees with $f$ on
$\operatorname{dom}(f)$ and with $g$ on
$\operatorname{dom}(g)\backslash\operatorname{dom}(f)$. Jackson and the author
have shown that there is no finite axiomatisation of algebras of functions of
signature $(\sqcup)$. But adding operations (such as update) to this minimal
signature can lead to finite axiomatisations. For the functional signature
$(\sqcup,\backslash)$ where $\backslash$ is set-theoretic difference, Cirulis
has given a finite equational axiomatisation as subtraction o-semilattices.
Define $f\curlyvee g=(f\sqcup g)\cap(g\sqcup f)$ for all functions $f$ and
$g$; this is the largest domain restriction of the binary relation $f\cup g$
that gives a partial function. Now $f\cap g=f\backslash(f\backslash g)$ and
$f\sqcup g=f\curlyvee(f\curlyvee g)$ for all functions $f,g$, so the
signatures $(\curlyvee)$ and $(\sqcup,\cap)$ are both intermediate between
$(\sqcup)$ and $(\sqcup,\backslash)$ in expressive power. We show that each is
finitely axiomatised, with the former giving a proper quasivariety and the
latter the variety of associative distributive o-semilattices in the sense of
Cirulis.

Keywords: Function, override, intersection, axiomatisation.

2020 Mathematics Subject Classification: 08A02, 06F99, 20M20.

##  1 Introduction

Let $X$ and $Y$ be sets, and let $\operatorname{\sf Par}(X,Y)$ denote the set
of all partial functions from $X$ to $Y$; these are the functions with domain
in $X$ and range in $Y$.

In the theory of function algebras, one seeks to axiomatise algebras of
(partial) functions under one or more operations or relations. The elements of
such an algebra are members of $\operatorname{\sf Par}(X,Y)$ for some fixed
$X,Y$, and the operations are from some given signature. If composition is in
the signature, it is normally assumed that $X=Y$.

Recall the following familiar purely set-theoretic operations on
$\operatorname{\sf Par}(X,Y)$:

  * •

intersection $\cap$, defined as the usual set-theoretic intersection of (the
graphs of) $f$ and $g$;

  * •

difference $\backslash$, defined to be the usual set-theoretic difference of
$f$ and $g$:

$f\backslash g=\\{(x,y)\mid(x,y)\in f,(x,y)\not\in g\\}.$

For function algebras, the signature of intersection gives nothing but
semilattices, and difference gives so-called subtraction algebras (which have
appeared in different forms in the literature, for example implication
algebras [1, 2] and implicative BCK-algebras [7]).

We are here mainly interested in two functional analogs of the set operation
of union, which, unlike intersection and difference, do not have purely set-
theoretic definitions. To define them, if $f,g\in\operatorname{\sf Par}(X,Y)$,
denote by $g-f$ the restriction of $g$ to the complement of the domain of $f$
(a notation used in [3]). Then we may define, for all functions
$f,g\in\operatorname{\sf Par}(X,Y)$,

  * •

override $\sqcup$, given by

$f\sqcup g=f\cup(g-f);$

  * •

restricted union $\curlyvee$, given by

$f\curlyvee g=(f-g)\cup(f\cap g)\cup(g-f).$

Each of $f\sqcup g$ and $f\curlyvee g$ is a disjoint union of its constituent
parts and hence gives a function when applied to two functions. Indeed, it is
easy to see that $f\curlyvee g$ is the domain restriction of the binary
relation $f\cup g$ to where it is single-valued (that is, a function).
Notably, $\sqcup$ is associative but not commutative, and $\curlyvee$ is the
opposite. Both are idempotent.

The override operation has received considerable attention in theoretical
computer science and mathematics, especially when taken in combination with
other operations such as $\cap$ and others; see [3], [5], [9] and [10], as
well as the earlier works [11] and [12]. (The symbol $\sqcup$ was used in [9]
and [10], but other notations are often used.) It is shown in [9] that
override has a close connection to the if-then-else construct. As discussed in
[4], the operation is also of interest in the setting of so-called flat
records, which are modelled as (partial) functions on a finite domain, and it
also arises as the (opposite of the) overriding operator $\oplus$ in Z [18].
Finally, there are interesting connections with hyperplane arrangements [13].
Restricted union was defined and briefly discussed in Section 3.3 of [9],
where it was noted to be equivalent in expressive power to override in the
presence of intersection, but as far as the author knows, it has not been
considered since.

In some previous work, such as [3] and [5], a different operation which is
often called intersection but is based on the idea of domain restriction (and
studied at least since the time of [17]) was either part of the signature
considered or derivable within it; we do not consider this operation here. The
original motivation for the current work came from interest in functional
signatures having actual intersection together with some functional
approximant of union such as $\sqcup$ or $\curlyvee$.

There are straightforward connections between some of the signatures just
discussed. For example, $\cap$ can be expressed in terms of $\backslash$, as
noted in the abstract. But the two notions of union are also linked: $f\sqcup
g=f\curlyvee(f\curlyvee g)$ (see Proposition 3.8 to follow), and $f\curlyvee
g=(f\sqcup g)\cap(g\sqcup f)$ (see Proposition 3.7), so $\curlyvee$ contains
some information about intersection as well as $\sqcup$. It follows that
$\\{\cap,\curlyvee\\}$ is equivalent in expressive power to
$\\{\cap,\sqcup\\}$, and that an axiomatisation of the functional algebras of
one signature easily gives an axiomatisation of functional algebras of the
other.

Note also that $\curlyvee$ is strictly more expressive than $\sqcup$: any
collection $S$ of more than one partial function in $\operatorname{\sf
Par}(X,Y)$, all members of which are defined everywhere on $X$, will be such
that $(S,\sqcup)$ is a left zero semigroup, but $s\curlyvee t$ will not be in
$S$ unless $s=t$. Moreover, $\curlyvee$ alone is strictly less expressive than
$\cap$ plus $\curlyvee$ (equivalently, $\cap$ plus $\sqcup$), as a simple
example shows. Let $X=\\{1,2,3,0\\}$ with $S=\\{f,g,h,\emptyset\\}$ with

$f=\\{(1,0),(2,0)\\},g=\\{(2,0),(3,0)\\},h=\\{(1,0),(2,0),(3,0)\\}.$

Then $S$ is closed under $\curlyvee$, since $h=f\curlyvee g$, with all other
cases of $\curlyvee$ trivial since for any other pair of elements, one is a
subset of the other. But of course $S$ is not closed under intersection since
$f\cap g\not\in S$. So functional algebras and semigroups closed under
$\curlyvee$ are more general than those closed under both $\curlyvee$ and
$\cap$.

The signature $(\sqcup)$ is considered in [10], where the functional algebras
are shown to have no finite axiomatisation, and an infinite quasiequational
axiomatisation is given. By contrast, in Section 5 of [4], Cirulis axiomatises
functional algebras of signature $(\sqcup,\backslash)$, as the finitely based
variety of subtraction o-semilattices (see Theorem 5.6 there). The two
signatures we consider here lie between these two known cases in terms of
expressive power.

In [4], the author gives a structural description of the functional algebras
having the signature $(\sqcup,\cap)$, but does not axiomatise them. We do this
here, showing them to be nothing but the variety of associative distributive
o-semilattices defined in [4]. It is straightforward to then enrich the
signature to include difference and recover the finite equational
axiomatisability result due to Cirulis in [4], albeit with a different (though
necessarily equivalent) equational axiomatisation to the one given in Theorem
5.6 there. But we also finitely axiomatise the signature $(\curlyvee)$, giving
a proper quasivariety. This covers off every signature consisting of some or
all of the four functional operations $(\sqcup,\curlyvee,\cap,\backslash)$.

A partial operation of domain-disjoint union of sets and partial functions is
considered in [8], motivated by separation logic. It was shown there that no
finite axiomatisation for either set-based or functional algebras exists
(though again, an axiomatisation was given). This is consistent with the
situation for the signature $(\sqcup)$ (noting that $\sqcup$ agrees with
domain-disjoint union when the latter is defined). But it is perhaps
surprising that the signature $(\curlyvee)$ admits a finite axiomatisation,
since, like $\sqcup$, it agrees with the partial operation of union when the
latter exists; it seems that the intersection-related information present in
the definition of $\curlyvee$ is enough to allow this.

In what follows, if $\Sigma$ is a particular signature comprising some of the
operations $\sqcup,\curlyvee,\cap,\backslash$ considered above, we say an
equational or quasiequational law in the signature $\Sigma$ is functionally
sound if it is satisfied by $\operatorname{\sf Par}(X,Y)$ for any non-empty
set $X$; it follows that the law is satisfied by any subalgebra (under the
relevant signature) of $\operatorname{\sf Par}(X,Y)$. We say an algebra of
signature $\Sigma$ is functional if it is isomorphic to one whose elements are
partial functions, and the operations have their standard functional
interpretations as described above.

In the section to follow, we begin by considering properties of override
alone, noting that it is a left regular band operation and recording some
basic properties of such bands that will be useful in what follows. In Section
3, we consider the associative distributive o-semilattices considered in [4],
where their defining laws are observed to be functionally sound. We call these
ado-semilattices, and reformulate their axioms somewhat for later use. We
define $\curlyvee$-algebras in terms of some laws satisfied by $\curlyvee$
defined in an ado-semilattice via $a\curlyvee b=(a\sqcup b)\cap(b\sqcup a)$;
it follows that every functional algebra of signature $(\curlyvee)$ is a
$\curlyvee$-algebra.

Then in Section 4, we present our completeness proofs. Most of the work is in
showing that the class of $\curlyvee$-algebras axiomatises the functional
algebras of signature $(\curlyvee)$, which is also shown to be a proper
quasivariety. We then build on this to prove that the finitely based variety
of ado-semilattices axiomatises the functional algebras of signature
$(\sqcup,\cap)$. We conclude in Section 5 by obtaining as a corollary a
different finite equational axiomatisation for the functional signature
$(\sqcup,\backslash)$.

Throughout, we write functions on the right of their arguments, so “$xf$”,
rather than “$f(x)$”.

##  2 Left regular bands

The operation of $\sqcup$ alone is rather badly behaved in terms of
axiomatisation of functional algebras: by Corollary 4.1 of [10], the class of
functional algebras of signature $(\sqcup)$ has no finite axiomatisation in
first order logic. Indeed it is shown there to consist of precisely those
algebras that arise from hyperplane arrangements, and is the proper
quasivariety generated by the three-element band $\\{1,e,f\\}$ in which $1$ is
an identity element appended to the left zero semigroup on $\\{e,f\\}$. It was
also shown in [10] that the addition to the signature of the operation of
update as defined there and in earlier work including [3] and [5] leads to a
finite equational axiomatisation, answering a question posed in that earlier
work. It was shown in [3] that adding the operation minus to override
(yielding a signature that subsumes update) gives a finite axiomatisation, at
least for the equational theory generated by the functional algebras. The more
general finite axiomatisability of the functional algebras follows from the
work of [5], itself reliant on the work of [11] on skew Boolean algebras. We
shall see very similar behavior for the cases considered here, in which the
signature of $\sqcup$ is enriched in various natural ways that give finite
axiomatisations.

We next note note some quite elementary properties satisfied by the override
operation that will be useful in what follows.

Recall that $(S,\sqcup)$ is a left regular band if for all $a,b,c\in S$,

  1. 1.

$a\sqcup(b\sqcup c)=(a\sqcup b)\sqcup c$;

  2. 2.

$a\sqcup a=a$;

  3. 3.

$a\sqcup b=(a\sqcup b)\sqcup a$.

The fact that the left regular band properties are all satisfied by override
for partial functions has been noted by several authors; see [3] and [4]. Note
that in the first of these, the operation of override is denoted $\rhd$,
whilst in the latter, it is denoted $\lhd$ but defined opposite to the way
most other authors (including the current one) define it.

On the left regular band $S$, define

  * •

$a\leq b$ if $a\sqcup b=b$.

  * •

$a\lesssim b$ if $b\sqcup a=b$;

For the case of partial functions, $\leq$ is the partial order of set-
theoretic inclusion of the sets of ordered pairs representing them, and
$\lesssim$ is the domain inclusion quasiorder: $f\lesssim g$ if and only if
$\operatorname{dom}(f)\subseteq\operatorname{dom}(g)$. Note also that
$\operatorname{dom}(f\sqcup
g)=\operatorname{dom}(f)\cup\operatorname{dom}(g)$.

Most of the facts noted in the following are well-known, but good sources are
[16] and [14].

###### Lemma 2.1

Let $S$ be a left regular band.

  1. 1.

The relation $\leq$ is a partial order on $S$, and for all $a,b,c\in S$, if
$b\leq c$ then $a\sqcup b\leq a\sqcup c$.

  2. 2.

The relation $\lesssim$ is a quasiorder and for all $a,b,c,d\in S$, if
$a\lesssim b,c\lesssim d$ then $a\sqcup c\lesssim b\sqcup d$.

  3. 3.

For all $a,b\in S$, $a\sqcup b\sim b\sqcup a$.

  4. 4.

For all $a,b\in S$, $a\leq b$ implies $a\lesssim b$.

  5. 5.

If $d\lesssim a_{1}\sqcup i_{1},a_{2}\sqcup i_{2},\ldots,a_{n}\sqcup i_{n}$ in
$S$, then letting $i=i_{1}\sqcup i_{2}\sqcup\ldots\sqcup i_{n}$, we have that
$d\lesssim a_{j}\sqcup i$ for $j=1,2,\ldots,n$.

Proof. (1) That $\leq$ is a partial order was noted in Section 2 of [16], and
the second part is Lemma 2.1 in [14].

(2) That $\lesssim$ is a quasiorder is again noted in Section 2 of [16].
further, if $a\lesssim b$ and $c\lesssim d$ then $b\sqcup a=b$ and $d\sqcup
c=d$, so

$(b\sqcup d)\sqcup(a\sqcup c)=b\sqcup d\sqcup b\sqcup a\sqcup d\sqcup
c=b\sqcup d\sqcup b\sqcup d=b\sqcup d,$

and so $a\sqcup c\lesssim b\sqcup d$.

(3) above follows from (2) and (3) of Proposition 2.1 in [16], and (4) here
follows from (1) and (3) of that result.

(5) Assume that $d\lesssim a_{1}\sqcup i_{1},a_{2}\sqcup
i_{2},\ldots,a_{n}\sqcup i_{n}$. Then $a_{j}\sqcup i_{j}\sqcup d=a_{j}\sqcup
i_{j}$, $j=1,2,\ldots,n$. Hence for any $j\in\\{1,2,\ldots,n\\}$,

$\displaystyle a_{j}\sqcup i\sqcup d$ $\displaystyle=a_{j}\sqcup i_{1}\sqcup
i_{2}\sqcup\cdots\sqcup i_{n}\sqcup d$ $\displaystyle=a_{j}\sqcup i_{1}\sqcup
i_{2}\sqcup\cdots\sqcup i_{n}\sqcup a_{j}\sqcup i_{j}\sqcup d$
$\displaystyle=a_{j}\sqcup i_{1}\sqcup i_{2}\sqcup\cdots\sqcup i_{n}\sqcup
a_{j}\sqcup i_{j}$ $\displaystyle=a_{j}\sqcup i_{1}\sqcup
i_{2}\sqcup\cdots\sqcup i_{n}$ $\displaystyle=a_{j}\sqcup i,$

so $d\lesssim a_{j}\sqcup i$. $\Box$

We remark that defining $a\leq b$ if and only if $ab=b$ for all $a,b$ in a
band $S$ gives a partial order if and only if $S$ is left regular. Moreover,
distinct left regular bands structures on the same set can induce the same
partial order, so the poset structure does not determine the left regular band
operation. (This contrasts with the case of the override operation in
overriding nearlattices, considered in the next section.) The following
example to show this is well-known.

###### Example 2.2

Two non-isomorphic left regular band structures on the same set giving the
same partial order.

Let $S=\\{b,t,e,f\\}$. Consider the four element Boolean algebra structure on
$S$, with bottom $b$, top $t$, $e\wedge f=b$, $e\vee f=t$; then $(S,\vee)$ is
a semilattice and hence a left regular band. Now define $\sqcup$ on $S$ by
adjoining zero $t$ and identity $b$ to the left zero semigroup defined on
$\\{e,f\\}$. The partial order obtained from $(S,\vee)$ equals that obtained
from $(S,\sqcup)$ but obviously these are non-isomorphic bands.

###### Definition 2.3

Suppose $S$ is a left regular band. Let $I\subseteq S$ be non-empty. We say
$I$ is a $\lesssim$-ideal if it is a down-set under $\lesssim$, additionally
satisfying the requirement that if $i,j\in I$ then $i\sqcup j\in I$. For $a\in
S$, we say the $\lesssim$-ideal is relatively maximal (with respect to not
containing $a$) if $a\not\in I$ and there is no larger $\lesssim$-ideal of $S$
that does not contain $a$.

Every maximal $\lesssim$-ideal (defined as expected) is relatively maximal,
although the converse may fail.

###### Lemma 2.4

Let $S$ be a left regular band with $I$ a $\lesssim$-ideal of $S$. Suppose $I$
is relatively maximal with respect to not containing $d\in S$, and $a\not\in
I$. Then there exists $i\in I$ such that $d\lesssim a\sqcup i$.

Proof. Let $G=\\{w\in S\mid w\lesssim a\sqcup i,i\in I\\}$. Then $G$ is a
$\lesssim$-ideal since it is obviously down-closed with respect to $\lesssim$,
and moreover if $w_{1}\lesssim a\sqcup i_{1}$ and $w_{2}\lesssim a\sqcup
i_{2}$ for some $i_{1},i_{2}\in I$, then

$\displaystyle a\sqcup i_{2}\sqcup i_{1}\sqcup(w_{1}\sqcup w_{2})$
$\displaystyle=a\sqcup i_{2}\sqcup a\sqcup i_{1}\sqcup(w_{1}\sqcup w_{2})$
$\displaystyle=a\sqcup i_{2}\sqcup(a\sqcup i_{1}\sqcup w_{1})\sqcup w_{2}$
$\displaystyle=a\sqcup i_{2}\sqcup(a\sqcup i_{1})\sqcup w_{2}$
$\displaystyle=a\sqcup i_{2}\sqcup a\sqcup i_{1}\sqcup a\sqcup i_{2}\sqcup
w_{2}$ $\displaystyle=a\sqcup i_{2}\sqcup a\sqcup i_{1}\sqcup a\sqcup i_{2}$
$\displaystyle=a\sqcup i_{2}\sqcup a\sqcup i_{1}$ $\displaystyle=a\sqcup
i_{2}\sqcup i_{1}$

and so because $i_{2}\sqcup i_{1}\in I$, we have $w_{1}\sqcup w_{2}\in G$. Now
$a\sqcup i\sqcup i=a\sqcup i$, so $i\lesssim a\sqcup i$ for all $i\in I$, and
so $I\subseteq G$, and also since $a\lesssim a\sqcup i\sqcup a=a\sqcup i$ for
each $i\in I$, we have $a\lesssim a\sqcup i$ and so $a\in G$. So by relative
maximality of $I$ with respect to not containing non-zero $d\in S$, we have
that $d\in G$, and so $d\lesssim a\sqcup i$ for some $i\in I$. $\Box$

##  3 Ado-semilattices and $\curlyvee$-algebras

###  3.1 Ado-semilattices

In [4], an overriding nearlattice is defined to be a nearlattice (meaning a
(meet)-semilattice $(S,\wedge)$ in which any two elements with an upper bound
have a least upper bound) such that, for all $a,b\in S$, the following exists:

$a\lhd b=sup\\{x\in S:(x\leq a\mbox{ and }x,b\mbox{ share an upper bound), or
}x\leq b\\}.$

If $a,b$ have an upper bound, then their least upper bound is $a\lhd b$. Note
that $a\lhd b$ in an overriding nearlattice is wholly determined by its
structure as a semilattice. It is observed in [4] that every functional
algebra of signature $(\sqcup,\cap)$ is an overriding nearlattice in which
$a\wedge b=a\cap b$ and $a\lhd b=b\sqcup a$.

In [4], the author went on to axiomatise those algebras $(S,\cap,\lhd)$ that
arise from overriding nearlattices as above, as semilattices with overriding,
abbreviated to o-semilattices. Using our notation, with $a\sqcup b=b\lhd a$,
o-semilattices may be defined as algebras $(L,\cap,\sqcup)$ such that
$(L,\cap)$ is a semilattice, and such that, defining $\leq$ via $x\leq
y\Leftrightarrow x=x\cap y$ as usual, we have for all $x,y,z\in L$:

  1. 1.

$x\leq x\sqcup y$;

  2. 2.

$(x\cap y)\sqcup(y\cap z)\leq y$;

  3. 3.

$x\sqcup y\leq x\sqcup(y\cap(x\sqcup y))$;

  4. 4.

$x\cap z\leq(x\cap y)\sqcup z$.

In what follows, we use this notation and these laws when we refer to
o-semilattices.

Functional algebras of signature $(\sqcup,\cap)$ were amongst the main
motivating examples of overriding nearlattices (and hence of o-semilattices)
given in [4]. The author described their structure: they are precisely the
subdirect products of flat o-semilattices; see Theorem 5.2 there. (A poset
$(P,\leq)$ is flat if there is a smallest element $0\in P$ and all other
elements are maximal; these are easily seen to be o-semilattices.) He did not
axiomatise them, but did give a finite equational axiomatisation of the
functional algebras of signature $(\lhd,\backslash)$, as the class of
overriding nearlattices with associative $\lhd$ in which the principal ideal
(with respect to the meet-semilattice order $\leq$) generated by each element
is a Boolean algebra. He gave an equational axiomatisation in the language of
$(\lhd,\backslash)$ as so-called subtraction o-semilattices; we return to
these in Section 5.

An overriding nearlattice (hence an o-semilattice) is said to be distributive
if the principal ideal generated by each element is a distributive lattice; so
“Boolean” implies “distributive”. In terms of the signature $(\sqcup,\cap)$,
this distributivity condition can be stated equationally as

$(a\cap d)\sqcup((b\cap d)\cap(c\cap d))=((a\cap d)\sqcup(b\cap d))\cap((a\cap
d)\sqcup(c\cap d)).$

(Of course there is a dual form in terms of $\lhd$, which is the form given in
[4].) Every functional o-semilattice is distributive (since for partial
functions contained in a given one, $\sqcup$ is the same as union). But it is
also associative, meaning that $(x\sqcup y)\sqcup z=x\sqcup(y\sqcup z)$.

###### Definition 3.1

An ado-semilattice is a distributive o-semilattice in which $\sqcup$ is
associative.

If an o-semilattice is a lattice, (so that $\sqcup$ is simply join), then the
distributivity condition is simply lattice distributivity, which is also
sufficient for functional representability since every distributive lattice
can be represented as subsets of a set with intersection and union as the meet
and join. So amongst o-semilattices which are lattices, distributivity is
necessary and sufficient for functional representability. We shortly show that
this is true for general associative o-semilattices.

Next, we note some laws satisfied by ado-semilattices, some of which we have
seen but some of which are new; since the ado-semilattice laws are
functionally sound, so must these derived laws be.

###### Lemma 3.2

Every ado-semilattice $(S,\sqcup,\cap)$ is such that $(S,\sqcup)$ is a left
regular band, satisfying extended distributivity given by $a\sqcup(b\cap
c)=(a\sqcup b)\cap(a\sqcup c)$.

Proof. Most of the laws follow from properties listed in Lemma 2.2 of [4]; in
particular, the left regular band laws are associativity together with
properties (xiv) and (xvi), and $a\cap b=b\cap a\leq a$ follows from (xii).

Next we prove extended distributivity. First note that the third law $x\sqcup
y\leq x\sqcup(y\cap(x\sqcup y))$ given above for o-semilattices can be
strengthened to an equation since the reverse inclusion holds by (1) in Lemma
2.1. Hence, for all $a,b,c$,

$\displaystyle a\sqcup(b\cap c)$ $\displaystyle=a\sqcup((b\cap
c)\cap(a\sqcup(b\cap c))$ $\displaystyle\leq a\sqcup((b\cap
c)\cap(a\sqcup(b\cap c)\sqcup c)$ $\displaystyle=a\sqcup((b\cap c)\cap(a\sqcup
c))$ $\displaystyle\leq a\sqcup(b\cap c),$

so all are equal, and so in particular,

$\displaystyle a\sqcup(b\cap c)$ $\displaystyle=a\sqcup((b\cap c)\cap(a\sqcup
c))$ $\displaystyle=(a\cap(a\sqcup c))\sqcup((b\cap(a\sqcup
c))\cap(c\cap(a\sqcup c)))$ $\displaystyle=((a\cap(a\sqcup
c))\sqcup(b\cap(a\sqcup c))\cap(a\cap(a\sqcup c))\sqcup(c\cap(a\sqcup c)))$
(by o-semilattice distributivity) $\displaystyle=(a\sqcup(b\cap(a\sqcup
c)))\cap(a\sqcup(c\cap(a\sqcup c)))$ $\displaystyle=(a\sqcup(b\cap(a\sqcup
c)))\cap(a\sqcup c)$ (by the strengthened o-semilattice law (3))
$\displaystyle=a\sqcup(b\cap(a\sqcup c))\mbox{ since $a\sqcup(b\cap(a\sqcup
c))\leq a\sqcup(a\sqcup c)=a\sqcup c$}$ (upon using (1) of Lemma 2.1)
$\displaystyle=a\sqcup((a\sqcup c)\cap b).$

But then applying this result again to $a\sqcup(b\cap(a\sqcup c))$ gives that

$a\sqcup(b\cap c)=a\sqcup((a\sqcup b)\cap(a\sqcup c))=(a\sqcup b)\cap(a\sqcup
c),$

since $a\leq a\sqcup b,a\sqcup c$, so $a\leq(a\sqcup b)\cap(a\sqcup c)$.
$\Box$

The extended distributivity law can be used to replace the distributivity law
for ado-semilattices since the former clearly implies the latter. We can then
give an alternative axiomatisation for the class of ado-semilattices in which
the partial order determined by $\sqcup$ is primary.

###### Corollary 3.3

The class of ado-semilattices may be defined by the following:

  1. 1.

$\sqcup$ is a left regular band operation;

  2. 2.

$\cap$ is semilattice meet with respect to the partial order determined by
$\sqcup$;

  3. 3.

$a\sqcup(b\cap c)=(a\sqcup b)\cap(a\sqcup c)$;

  4. 4.

$a\cap c\leq(a\cap b)\sqcup c$.

Proof. We have seen in Lemma 3.2 that the above laws follow from those for
ado-semilattices. Conversely, these laws imply those for ado-semilattices
(expressed in terms of $\sqcup$): the first two laws of o-semilattices follow
easily, and the third follows from the third extended distributivity law
above, as does ado-semilattice distributivity, and associativity of $\sqcup$
is immediate. $\Box$

We next establish some further facts about ado-semilattices.

###### Lemma 3.4

Suppose $(S,\sqcup,\cap)$ is an ado-semilattice. Then for all $a,b,c\in S$,

  1. 1.

$a\sqcup b=b\sqcup a$ if and only if $a,b$ have an upper bound;

  2. 2.

$a\cap((a\cap b)\sqcup c)=a\cap((a\cap c)\sqcup b)$.

Proof. Now if $a\sqcup b=b\sqcup a$ then $a,b\leq a\sqcup b$. Conversely if
$a,b\leq c$ then $a\sqcup b=b\sqcup a$ because $a\sqcup b$ is the join of
$a,b$ in the principal ideal determined by $c$.this establishes (1). For (2),
using extended distributivity we obtain

$(a\cap b)\sqcup(a\cap c)=((a\cap b)\sqcup a)\cap((a\cap b)\sqcup
c)=a\cap((a\cap b)\sqcup c),$

and similarly $(a\cap c)\sqcup(a\cap b)=a\cap((a\cap c)\sqcup b)$. But $a\cap
b,a\cap c\leq a$ so $(a\cap b)\sqcup(a\cap c)=(a\cap c)\sqcup(a\cap b)$ by the
first part of the proof. The result now follows. $\Box$

###### Lemma 3.5

Suppose $(S,\sqcup,\cap)$ is an ado-semilattice. If $a,b\in S$ have an upper
bound and $d\lesssim a,d\lesssim b$, then $d\lesssim a\cap b$.

Proof. Assume $a,b\in S$ have an upper bound and $d\lesssim a,d\lesssim b$. We
prove the following facts in turn.

  1. 1.

$b\leq(b\cap(d\sqcup b))\sqcup a$;

  2. 2.

$b\sqcup a=(b\cap(d\sqcup b))\sqcup a$;

  3. 3.

$b\leq(a\cap b)\sqcup d\sqcup b$;

  4. 4.

$d\lesssim a\cap b$.

Since $d\lesssim a,d\lesssim b$, we obtain $a\sqcup d=a,b\sqcup d=b$. For (1),
we have that $b\sqcup a=a\sqcup b$ by (1) in Lemma 3.4, and so from (3) in
Corollary 3.3,

$b\leq a\sqcup b=(a\sqcup b)\cap(a\sqcup b)=(a\sqcup b)\cap(a\sqcup d\sqcup
b)=a\sqcup(b\cap(d\sqcup b))=(b\cap(d\sqcup b))\sqcup a,$

again using (1) in Lemma 3.4 (since $a,b\cap(d\sqcup b)$ have an upper bound,
namely any upper bound of $a,b$). For (2), first note that

$\displaystyle(b\sqcup a)\cap((b\cap(d\sqcup b))\sqcup a)$
$\displaystyle=(b\sqcup a)\cap((b\cap(d\sqcup b))\sqcup a\sqcup b)\mbox{ (by
(1))}$ $\displaystyle=(b\sqcup a)\cap((b\cap(d\sqcup b))\sqcup b\sqcup a)$
$\displaystyle=(b\sqcup a)\cap(b\sqcup a)$ (since $b\cap(d\sqcup b)\leq b$)
$\displaystyle=b\sqcup a,$

so $b\sqcup a\leq((b\cap(d\sqcup b))\sqcup a$. Hence

$\displaystyle(b\cap(d\sqcup b))\sqcup a)$ $\displaystyle=(b\sqcup
a)\sqcup((b\cap(d\sqcup b))\sqcup a))$ $\displaystyle=b\sqcup
a\sqcup(b\cap(d\sqcup b))$ $\displaystyle=b\sqcup a\sqcup
b\sqcup(b\cap(d\sqcup b))$ $\displaystyle=b\sqcup a\sqcup b$ (since
$b\cap(d\sqcup b)\lesssim b$ by (4) in Lemma 2.1) $\displaystyle=b\sqcup a.$

For (3),

$\displaystyle b\cap((a\cap b)\sqcup d\sqcup b)$
$\displaystyle=b\cap((b\cap(d\cap b))\sqcup a)$ (by (2) in Lemma 3.4)
$\displaystyle=b\cap(b\sqcup a)\mbox{ (by (2))}$ $\displaystyle=b,$

so $b\leq(a\cap b)\sqcup d\sqcup b$. Finally, for (4):

$\displaystyle(a\cap b)\sqcup d\sqcup b$ $\displaystyle=b\sqcup(a\cap b)\sqcup
d\sqcup b\mbox{ (by (3))}$ $\displaystyle=b\sqcup d\sqcup b$
$\displaystyle=b\sqcup d$ $\displaystyle=b,$

so $b\geq(a\cap b)\sqcup d$. Similarly, $a\geq(b\cap a)\sqcup d=(a\cap
b)\sqcup d$. So

$(a\cap b)\sqcup d\leq a\cap b\leq(a\cap b)\sqcup d,$

so $a\cap b=(a\cap b)\sqcup d$, and so $d\lesssim a\cap b$. $\Box$

We may now infer two quasiequations for ado-semilattices.

###### Lemma 3.6

In an ado-semilattice, the following two quasiequations hold:

  1. 1.

$d\lesssim a\cap b,d\lesssim b\cap c\Rightarrow d\lesssim a\cap c$;

  2. 2.

$d\lesssim a,d\lesssim b,d\lesssim a\curlyvee b\Rightarrow d\lesssim a\cap b$.

Proof. Suppose $d\lesssim a\cap b,d\lesssim b\cap c$. Then by Lemma 3.5, we
have that

$d\lesssim(a\cap b)\cap(b\cap c)=a\cap b\cap c\leq a\cap c,$

and so $d\lesssim a\cap c$.

Now suppose $d\lesssim a,d\lesssim b,d\lesssim a\curlyvee b$. But
$a,a\curlyvee b\leq a\sqcup b$, so $d\lesssim a\cap(a\curlyvee b)$ by Lemma
3.5. Similarly, $d\lesssim b\cap(a\curlyvee b)$. Using Lemma 3.5 again, we
obtain $d\lesssim a\cap b\cap(a\curlyvee b)\leq a\cap b$, so $d\lesssim a\cap
b$ by (4) in Lemma 2.1. $\Box$

###  3.2 $\curlyvee$-algebras

On any ado-semilattice $S$, we define the operation $\vee$ as follows: $a\vee
b=(a\sqcup b)\cap(b\sqcup a)$ for all $a,b\in S$.

###### Proposition 3.7

In a functional ado-semilattice, $a\vee b=a\curlyvee b$.

Proof. First, note that $a\curlyvee b\subseteq a\sqcup b,b\sqcup a$, so
$a\curlyvee b\subseteq(a\sqcup b)\cap(b\sqcup a)$. Conversely, suppose
$(x,y)\in(a\sqcup b)\cap(b\sqcup a)$, so $(x,y)\in a\sqcup b$ and $(x,y)\in
b\sqcup a$. If $(x,y)\in a,b$, then $(x,y)\in a\cap b\subseteq a\curlyvee b$.
So assume $(x,y)\not\in a$. Then because $(x,y)\in a\sqcup b$, $(x,y)\in b$
and $x\not\in\operatorname{dom}(a)$, so $(x,y)\in a\curlyvee b$. Similarly if
$(x,y)\not\in b$, $(x,y)\in a\curlyvee b$. So $(a\sqcup b)\cap(b\sqcup
a)\subseteq a\curlyvee b$. $\Box$

So from now on, we use the notation $\curlyvee$ rather than $\vee$ for this
derived operation on an ado-semilattice. A number of laws involving
$\curlyvee$ only may be derived.

###### Proposition 3.8

Let $S$ be an ado-semilattice. Then for all $a,b,c\in S$:

  1. 1.

$a\sqcup b=a\curlyvee(a\curlyvee b)$;

  2. 2.

$\curlyvee$ is commutative and idempotent;

  3. 3.

$(a\curlyvee b)\sqcup(a\sqcup b)=(a\sqcup b)$;

  4. 4.

$a\sqcup(b\curlyvee c)=(a\sqcup b)\curlyvee(a\sqcup c)$;

  5. 5.

$d\lesssim a,d\lesssim b,d\lesssim c,d\lesssim a\curlyvee b$ and $d\lesssim
b\curlyvee c$ imply that $d\lesssim a\curlyvee c$.

Proof. Now $a,a\curlyvee b\leq a\sqcup b$, so by (1) in Lemma 3.4,
$a\sqcup(a\curlyvee b)=(a\curlyvee b)\sqcup a$, and so $a\curlyvee(a\curlyvee
b)=a\sqcup(a\curlyvee b)=a\sqcup((a\sqcup b)\cap(b\sqcup a))=(a\sqcup a\sqcup
b)\cap(a\sqcup b\sqcup a)=(a\sqcup b)\cap(a\sqcup b)=a\sqcup b$ as required.
Clearly $\curlyvee$ is commutative and idempotent. Further,

$\displaystyle(a\sqcup b)\curlyvee(a\sqcup c)$ $\displaystyle=((a\sqcup
b)\sqcup(a\sqcup c))\cap((a\sqcup c)\sqcup(a\sqcup b))$
$\displaystyle=(a\sqcup(b\sqcup c))\cap(a\sqcup(c\sqcup b))$
$\displaystyle=a\sqcup((b\sqcup c)\cap(c\sqcup b))$
$\displaystyle=a\sqcup(b\curlyvee c),$

establishing the final equational law.

Finally, if $d\lesssim a,d\lesssim b,d\lesssim c,d\lesssim a\curlyvee b$ and
$d\lesssim b\curlyvee c$, then using (2) in Lemma 3.6 twice, we obtain that
$d\lesssim a\cap b$ and $d\lesssim b\cap c$, and so using (1) in Lemma 3.6,
$d\lesssim a\cap c$, and so $d\lesssim a\curlyvee c$. So $(S,\curlyvee,\cap)$
is a $\curlyvee$-algebra. $\Box$

The properties just listed turn out to be critical ones.

###### Definition 3.9

Let $S$ be an algebra with binary operation $\curlyvee$ such that:

  1. 1.

if we set $a\sqcup b=a\curlyvee(a\curlyvee b)$ for all $a,b\in S$,
$(S,\sqcup)$ is a left regular band, and

  2. 2.

$(S,\curlyvee)$ satisfies the properties listed in Proposition 3.8.

Then we say $S$ is a $\curlyvee$-algebra.

The final law for $\curlyvee$-algebras (in Proposition 3.8) can be expressed
as an algebraic quasiequation, so the class of $\curlyvee$-algebras is a
quasivariety.

###### Corollary 3.10

Every ado-semilattice is a $\curlyvee$-algebra when we define $a\curlyvee
b=(a\sqcup b)\cap(b\sqcup a)$. Hence every functional algebra of signature
$(\curlyvee)$ is a $\curlyvee$-algebra.

Proof. If $S$ is an ado-semilattice and we define $\curlyvee$ as indicated,
then we know that $a\curlyvee(a\curlyvee b)$ gives $a\sqcup b$ which is a left
regular band operation. The other $\curlyvee$-algebra properties follow from
Proposition 3.8.

Since the $\curlyvee$-algebra laws are derivable from the ado-semilattice laws
which are functionally sound, and for functional ado-semilattices, $a\curlyvee
b=(a\sqcup b)\cap(b\sqcup a)$, it follows that every functional algebra of
signature $(\curlyvee)$ is a $\curlyvee$-algebra. $\Box$

The quasiequation in the definition of $\curlyvee$-algebras cannot be replaced
by equations.

###### Theorem 3.11

The class of $\curlyvee$-algebras is a proper quasivariety.

Proof. Let $X=\\{a,b\\}$ and consider
$S=\\{0,1,i,1_{a},1_{b},p_{a},1\\}\subseteq\operatorname{\sf Par}(X,X)$, where
$0=\emptyset,1=\\{(a,a),(b,b)\\},i=\\{(b,a)\\},1_{a}=\\{(a,a)\\},1_{b}=\\{(b,b)\\}$
and $p_{a}=\\{(a,a),(b,a)\\}$. Then $S$ is a $\curlyvee$-subalgebra of
$\operatorname{\sf Par}(X,X)$ in which the tables for $\curlyvee$ and the
derived operation $\sqcup$ are easily seen to be as follows.

$\begin{array}[]{c|cccccc}\curlyvee&0&i&1_{b}&1_{a}&p_{a}&1\\\ \hline\cr
0&0&i&1_{b}&1_{a}&p_{a}&1\\\ i&i&i&0&p_{a}&1_{a}&1_{a}\\\
1_{b}&1_{b}&0&1_{b}&1&1_{a}&1\\\ 1_{a}&1_{a}&p_{a}&1&1_{a}&p_{a}&1\\\
p_{a}&p_{a}&p_{a}&1_{a}&p_{a}&p_{a}&1_{a}\\\
1&1&1_{a}&1&1&1_{a}&1\end{array}\hskip
42.67912pt\begin{array}[]{c|cccccc}\sqcup&0&i&1_{b}&1_{a}&p_{a}&1\\\ \hline\cr
0&0&i&1_{b}&1_{a}&p_{a}&1\\\ i&i&i&i&p_{a}&p_{a}&p_{a}\\\
1_{b}&1_{b}&1_{b}&1_{b}&1&1&1\\\ 1_{a}&1_{a}&p_{a}&1&1_{a}&p_{a}&1\\\
p_{a}&p_{a}&p_{a}&p_{a}&p_{a}&p_{a}&p_{a}\\\ 1&1&1&1&1&1&1\end{array}$

It is easy to see that the equivalence relation $\theta$ in which the
$\theta$-classes are $\\{0\\}$, $\\{i\\}$, $\\{1_{b}\\}$, and
$\\{1_{a},p_{a},1\\}$ is a congruence on $S$. Denoting the non-singleton
$\theta$-class by $1$ and the others by their only elements, the tables for
$S/\theta$ are evidently as follows.

$\begin{array}[]{c|cccc}\curlyvee&0&i&1_{b}&1\\\ \hline\cr 0&0&i&1_{b}&1\\\
i&i&i&0&1\\\ 1_{b}&1_{b}&0&1_{b}&1\\\ 1&1&1&1&1\end{array}\hskip
56.9055pt\begin{array}[]{c|cccc}\sqcup&0&i&1_{b}&1\\\ \hline\cr
0&0&i&1_{b}&1\\\ i&i&i&i&1\\\ 1_{b}&1_{b}&1_{b}&1_{b}&1\\\
1&1&1&1&1\end{array}$

It is easy to see that $1_{b}\lesssim 1_{b},1_{b}\lesssim 1,1_{b}\lesssim
i,1_{b}\lesssim 1_{b}\curlyvee 1,1_{b}\lesssim 1\curlyvee i$, and yet
$1_{b}\lesssim 1_{b}\curlyvee i$ fails since $(1_{b}\curlyvee i)\sqcup
1_{b}=1_{b}=1_{b}\neq 0=1_{b}\curlyvee i$.

So the quasiequational law for $\curlyvee$-algebras does not hold and so the
class of $\curlyvee$-algebras is not closed under taking homomorphic images.
$\Box$

We do not pretend that the axioms used to define $\curlyvee$-algebras are
irredundant. Indeed it can be shown using Prover9 that associativity of
$\sqcup$, idempotence of $\curlyvee$, and the third law in Proposition 3.8 are
indeed all redundant. It can also be shown that the left regular band partial
order may be expressed directly in terms of $\curlyvee$, via $a\leq b$ if and
only if $a\curlyvee b=b$. However, none of this affects either finite
axiomatisabilty or the proper quasiequational nature of these axioms, so we do
not give detailed proofs.

Given the above comments, along with the obvious fact that the defining axioms
for $\curlyvee$-algebras could easily be expressed entirely in terms of
$\curlyvee$ (using the first law in Proposition 3.8), one might hold out hope
of obtaining a general theory of “generalised $\curlyvee$-algebras” that can
be viewed as part of the general theory of partially ordered sets, as was done
with o-semilattices in [4]. There, it was shown that a poset is an
o-semilattice in at most one way. However, in Example 2.2, a poset $(S,\leq)$
that is even a Boolean distributive lattice arises from two non-isomorphic
left regular band structures on $S$, $(S,\vee)$ and $(S,\sqcup)$. For each,
one may wish to define $a\curlyvee_{1}b=(a\vee b)\wedge(b\vee a)$ and
$a\curlyvee_{2}b=(a\sqcup b)\wedge(b\sqcup a)$, but then $e\curlyvee_{1}f=t$
whereas $e\curlyvee_{2}f=b$.

In this last example, $(S,\curlyvee_{1})$ is a $\curlyvee$-algebra, but
$(S,\curlyvee_{2})$ is not. However, even if we consider only
$\curlyvee$-algebras, a similar issue arises.

###### Example 3.12

Two non-isomorphic $\curlyvee$-algebra structures on a set $S$ giving the same
partial order on $S$.

Let $S=\\{a,b,c,d,0,f\\}$. We define two $\curlyvee$-algebra structures on
$S$, having “multiplication” tables for $\curlyvee$ and hence $\sqcup$ given
below. In the first (yielding $\curlyvee_{1},\sqcup_{1}$), let $X=\\{x,y\\}$
and in $\operatorname{\sf Par}(X,X)$, let $a=\\{(x,x)\\}$, $b=\\{(x,y)\\}$,
$c=\\{(x,x),(y,y)\\}$, $d=\\{(x,y),(y,y)\\}$, $0=\emptyset$ (the empty
function), and $f=\\{(y,y)\\}$. It is straightforward to check that $S$ is
then closed under $\curlyvee$ and yields the multiplication table for
$\curlyvee_{1}$ given below, and similarly for $\sqcup_{1}$. Likewise, one can
easily check that the following definitions of the members of $S$ in
$\operatorname{\sf Par}(X,X)$ where $X=\\{x,y,z\\}$ yield the tables below for
$\curlyvee_{2}$ and $\sqcup_{2}$: $a=\\{(x,x),(y,y)\\}$,
$b=\\{(y,z),(z,z)\\}$, $c=\\{(x,x),(y,y),(z,z)\\}$,
$d=\\{(x,x),(y,z),(z,z)\\}$, $0=\emptyset$, and $f=\\{(x,x),(z,z)\\}$.

$\begin{array}[]{c|cccccc}\curlyvee_{1}&a&b&c&d&0&f\\\ \hline\cr
a&a&0&c&f&a&c\\\ b&0&b&f&d&b&d\\\ c&c&f&c&f&c&c\\\ d&f&d&f&d&d&d\\\
0&a&b&c&d&0&f\\\ f&c&d&c&d&f&f\end{array}\hskip
56.9055pt\begin{array}[]{c|cccccc}\sqcup_{1}&a&b&c&d&0&f\\\ \hline\cr
a&a&a&c&c&a&c\\\ b&b&b&d&d&b&d\\\ c&c&c&c&c&c&c\\\ d&d&d&d&d&d&d\\\
0&a&b&c&d&0&f\\\ f&c&d&c&d&f&f\end{array}$

and

$\begin{array}[]{c|cccccc}\curlyvee_{2}&a&b&c&d&0&f\\\ \hline\cr
a&a&f&c&f&a&c\\\ b&f&b&f&d&b&d\\\ c&c&f&c&f&c&c\\\ d&f&d&f&d&d&d\\\
0&a&b&c&d&0&f\\\ f&c&d&c&d&f&f\end{array}\hskip
56.9055pt\begin{array}[]{c|cccccc}\sqcup_{2}&a&b&c&d&0&f\\\ \hline\cr
a&a&c&c&c&a&c\\\ b&d&b&d&d&b&d\\\ c&c&c&c&c&c&c\\\ d&d&d&d&d&d&d\\\
0&a&b&c&d&0&f\\\ f&c&d&c&d&f&f\end{array}$

The only differences here are that $a\curlyvee_{1}b=b\curlyvee_{1}a=0$, and
$a\sqcup_{1}b=a$ and $b\sqcup_{1}a=b$, whereas
$a\curlyvee_{2}b=b\curlyvee_{2}a=f$, and $a\sqcup_{2}b=c$ and
$b\sqcup_{2}a=d$. In both cases, we see that $a\leq c,b\leq d,0\leq s$ for all
$s\in S$, and $f\leq c,d$, and it follows that in both, $(S,\leq)$ is a meet-
semilattice with the following table:

$\begin{array}[]{c|cccccc}\wedge&a&b&c&d&0&f\\\ \hline\cr a&a&0&a&0&0&0\\\
b&0&b&0&b&0&0\\\ c&a&0&c&f&0&f\\\ d&0&b&f&d&0&f\\\ 0&0&0&0&0&0&0\\\
f&0&0&f&f&0&f\end{array}$

For the first representation of $S$, $\wedge$ as above is intersection, as is
easily seen, so $(S,\curlyvee_{1},\wedge)$ is an ado-semilattice and indeed
the unique ado-semilattice defined on the semilattice $(S,\wedge)$. Hence
$(S,\curlyvee_{2},\wedge)$ cannot be an ado-semilattice, and indeed one sees
that $a\wedge d=0$ does not correctly calculate intersection of $a,d$ in the
second representation.

So one cannot view the study of $\curlyvee$-algebras as simply part of the
study of partially ordered sets, the way one can so view the study of
lattices, Heyting algebras, o-semilattices and so on, since the operation
$\curlyvee$ can admit no partial order-theoretic description.

##  4 The completeness results

Our main task in the remainder is to prove the converse of the second
statement in Corollary 3.10. From this, the functional completeness of the
ado-semilattice axioms will also follow.

###  4.1 Completeness for $\curlyvee$-algebras

In [4], the notion of a flat o-semilattice was critical, and the same applies
here. It is easy to see that a flat poset can be turned into a
$\curlyvee$-algebra.

###### Definition 4.1

A flat $\curlyvee$-algebra $S$ is one in which there is $0\in S$ such that
$a\curlyvee b=0$ if $a,b\in S$ are unequal and $a,b\neq 0$, with $a\curlyvee
a=a$ and $a\curlyvee 0=0\curlyvee a=a$ for all $a\in S$.

Given a flat poset, it can easily be turned into a flat $\curlyvee$-algebra by
setting $a\curlyvee b=0$ if $a,b\neq 0$, with $a\curlyvee 0=a$ for all $a$,
and every flat $\curlyvee$-algebra arises in this way.

The following is the relevant variant of Lemma 5.1 in [4].

###### Proposition 4.2

Every flat $\curlyvee$-algebra is simple, hence subdirectly irreducible.

Proof. Suppose $S$ is a flat $\curlyvee$-algebra, with $\psi:S\rightarrow T$ a
non-injective homomorphism into another $\curlyvee$-algebra $T$. So there are
unequal $a,b\in S$ for which $a\psi=b\psi$, and we can assume without loss of
generality that $a\neq 0$. If $b=0$ then $a\curlyvee b=a$ so $a\psi=0\psi$,
whereas if $b\neq 0$, then $a\psi=a\psi\curlyvee a\psi=a\psi\curlyvee
b\psi=(a\curlyvee b)\psi=0\psi$. So in all cases, $a\psi=0\psi$. Then for any
non-zero $c\in S$, $c\psi=(c\curlyvee 0)\psi=c\psi\curlyvee
0\psi=c\psi\curlyvee a\psi=(c\curlyvee a)\psi=0\psi$. Hence $\psi$ is a
constant. This shows $S$ is simple. $\Box$

###### Proposition 4.3

Every flat $\curlyvee$-algebra is functional, and a direct product of
functional algebras of signature $(\curlyvee)$ is functional.

Proof. Let $S$ be a flat $\curlyvee$-algebra with bottom element $0$, and let
$X=\\{0\\}$ and $Y=S$. For each $a\in S$, define $\psi_{a}\in\operatorname{\sf
Par}(X,Y)$ by setting $\psi_{0}=\emptyset$ and $\psi_{a}=\\{(0,a)\\}$. It is
straightforward to check that the map $a\mapsto\psi_{a}$ is a
$\curlyvee$-embedding.

Consider a family $S_{i},i\in{\mathcal{I}}$ of functional $\curlyvee$-algebras
$S_{i}$. View $S_{i}$ as embedded in $\operatorname{\sf Par}(X_{i},Y_{i})$
where it is assumed that the $X_{i}$ are all disjoint from one-another, and
similarly for the $Y_{i}$, let $X=\bigcup_{i}X_{i}$ and $Y=\bigcup_{i}Y_{i}$,
and then note that $\curlyvee$ on the direct product corresponds to
$\curlyvee$ on the corresponding elements of $\operatorname{\sf Par}(X,Y)$.
$\Box$

Hence any subalgebra of a direct product is also functional, and in
particular, any subdirect product of flat algebras is functional. We shall
show that the converse is true: every functional $\curlyvee$-algebra is a
subdirect product of flat algebras. This will follow immediately from our
proof that every $\curlyvee$-algebra is a subdirect product of flat algebras.

First, we note that the quasiequation in the definition of
$\curlyvee$-algebras may be usefully strengthened.

###### Lemma 4.4

If $S$ is a $\curlyvee$-algebra, then the following law holds: $d\lesssim
a\sqcup i,d\lesssim b\sqcup i,d\lesssim c\sqcup i,d\lesssim(a\curlyvee
b)\sqcup i,d\lesssim(b\curlyvee c)\sqcup i$ imply that $d\lesssim(a\curlyvee
c)\sqcup i$.

Proof. Suppose $d\lesssim a\sqcup i,b\sqcup i,c\sqcup i,(a\curlyvee b)\sqcup
i,(b\curlyvee c)\sqcup i$. Then $d\lesssim i\sqcup a,i\sqcup b,i\sqcup
c,i\sqcup(a\curlyvee b)=(i\sqcup a)\curlyvee(i\sqcup b),i\sqcup(b\curlyvee
c)=(i\sqcup b)\curlyvee(i\sqcup c)$, and we may infer from the simplified
quasiequation that $d\lesssim(i\sqcup a)\curlyvee(i\sqcup
c)=i\sqcup(a\curlyvee c)\lesssim(a\curlyvee c)\sqcup i$. So the general
quasiequation holds. $\Box$

###### Proposition 4.5

A subset $I$ of a $\curlyvee$-algebra is a $\lesssim$-ideal if and only if it
is a down-set under $\lesssim$ such that $i\curlyvee j\in I$ whenever $i,j\in
I$.

Proof. This follows because $i\curlyvee j\leq i\sqcup j$ and so $i\curlyvee
j\lesssim i\sqcup j$, and also $i\sqcup j=i\curlyvee(i\curlyvee j)$. $\Box$
Now let $I$ be a relatively maximal $\lesssim$-ideal of the
$\curlyvee$-semigroup $S$. Let

$E_{I}=\\{(a,b)\in S\times S\mid a\not\in I,b\not\in I,a\curlyvee b\not\in
I\\},\mbox{ and }\epsilon_{I}=E_{I}\cup(I\times I).$

###### Lemma 4.6

Let $S$ be a $\curlyvee$-algebra, with $I$ a relatively maximal
$\lesssim$-ideal of $S$. Then $\epsilon_{I}$ is a congruence on $S$ and
$S_{I}=S/\epsilon_{I}$ is a flat $\curlyvee$-algebra. Moreover $S$ is a
subdirect product of the $S_{I}$ as $I$ ranges over all relatively maximal
$\lesssim$-ideals of $S$.

Proof. Suppose $I$ is relatively maximal with respect to not containing $d\in
S$. Clearly, $\epsilon_{I}$ is reflexive and symmetric. For transitivity,
suppose $(a,b)\in\epsilon_{I}$ and $(b,c)\in\epsilon_{I}$. If $a,b\in I$ and
$b,c\in I$ then of course $a,c\in I$. The only other case to check is whether
none of $a,b,c,a\curlyvee b,b\curlyvee c$ being in $I$ implies also
$a\curlyvee c\not\in I$.

Suppose for a contradiction that $a\not\in I,b\not\in I,c\not\in I,a\curlyvee
b\not\in I,b\curlyvee c\not\in I$, yet $a\curlyvee c\in I$. Then by Lemma 2.4,
there are $i_{1},i_{2},\ldots,i_{5}$ such that $d\lesssim a\sqcup i_{1}$,
$d\lesssim b\sqcup i_{2}$, $d\lesssim c\sqcup i_{3}$, $d\lesssim(a\curlyvee
b)\sqcup i_{4}$ and $d\lesssim(b\curlyvee c)\sqcup i_{5}$. So by (5) in Lemma
2.1, $d\lesssim a\sqcup i$, $d\lesssim b\sqcup i$, $d\lesssim c\sqcup i$,
$d\lesssim(a\curlyvee b)\sqcup i$ and $d\lesssim(b\curlyvee c)\sqcup i$, where
$i=i_{1}\sqcup\ldots\sqcup i_{5}\in I$. So by Lemma 4.4, we have that
$d\lesssim(a\curlyvee c)\sqcup i\in I$, so $d\in I$, a contradiction. So
$a\curlyvee c\not\in I$, as required. Hence $\epsilon_{I}$ is an equivalence
relation.

Let $\overline{a}$ denote the $\epsilon_{I}$-class of $S_{I}$ containing $a\in
S$. On $S_{I}$, define the flat $\curlyvee$-algebra structure obtained by
making $I$ the bottom element with all other $\epsilon_{I}$-classes maximal.
Define $\theta_{I}:S\rightarrow S_{I}$ by setting

$a\theta_{I}=\begin{cases}\overline{a}&\mbox{ if }a\not\in I\\\ I&\mbox{ if
}a\in I.\end{cases}$

We shall show that $\theta_{I}$ is a (clearly surjective) homomorphism; since
its kernel is $\epsilon_{I}$, it will follow that $S_{I}\cong S/\epsilon_{I}$.
We perform a case analysis. Now by Proposition 4.5, for $a,b\in S$, $a,b\in I$
imply $a\curlyvee b\in I$, and if $a,a\curlyvee b\in I$ then $b\in I$ (since
$b\leq b\sqcup a\lesssim a\sqcup b=a\curlyvee(a\curlyvee b)\in I$).

Suppose $a\curlyvee b\in I$ but $a\not\in I,b\not\in I$. Then

$\displaystyle a\theta_{I}\curlyvee b\theta_{I}$
$\displaystyle=\overline{a}\curlyvee\overline{b}$ $\displaystyle=I\mbox{ since
$a\curlyvee b\in I$ so $\overline{a}\neq\overline{b}$}$
$\displaystyle=(a\curlyvee b)\theta_{I}\mbox{ since $a\curlyvee b\in I$.}$

Suppose $a\curlyvee b\in I$ and $a\in I,b\in I$. Then $a\theta_{I}\curlyvee
b\theta_{I}=I\curlyvee I=I=(a\curlyvee b)\theta_{I}$.

Suppose $a\curlyvee b\not\in I$, $a\not\in I,b\not\in I$. Then
$\overline{a}=\overline{b}$, and $a\curlyvee(a\curlyvee b)=a\sqcup b\geq
a\curlyvee b\not\in I$, so $a\curlyvee(a\curlyvee b)\not\in I$, and so
$\overline{a}=\overline{a\curlyvee b}$. Hence $a\theta_{I}\curlyvee
b\theta_{I}=\overline{a}\curlyvee\overline{b}=\overline{a}=\overline{a\curlyvee
b}=(a\curlyvee b)\theta_{I}$.

Suppose $a\curlyvee b\not\in I,a\not\in I,b\in I$. Then as in the previous
case, $\overline{a}=\overline{a\curlyvee b}$, and so $a\theta_{I}\curlyvee
b\theta_{I}=\overline{a}\curlyvee I=\overline{a}=\overline{a\curlyvee
b}=(a\curlyvee b)\theta_{I}$. The case $a\curlyvee b\not\in I,a\in I,b\not\in
I$ is very similar by symmetry.

This covers all cases, so $\theta_{I}$ is a surjective homomorphism, and
because $ker(\theta_{I})=\epsilon_{I}$, the latter must be a congruence on
$S$. It now suffices to show that $S$ is a subdirect product of the $S_{I}$,
for which it suffices to show that $\epsilon=\bigcap_{I}\epsilon_{I}$ is the
diagonal relation.

Let $a,b\in S$ be distinct, and without loss of generality assume $a\leq b$,
so $a\lesssim b$. We shall find a relatively maximal $\lesssim$-ideal $I$ such
that $a\theta_{I}\neq b\theta_{I}$, so that $(a,b)\not\in\epsilon_{I}$ and so
$(a,b)\not\in\epsilon$.

We consider two cases. First suppose that $b\not\lesssim a$. Then let
$I_{0}=\\{s\in S\mid s\lesssim a\\}$, a $\lesssim$-ideal since it is obviously
down-closed under $\lesssim$, and if $i,j\in I_{0}$ then $a\sqcup i=a=a\sqcup
j$ so $a\sqcup(i\sqcup j)=(a\sqcup i)\sqcup j=a\sqcup j=a$, and so $i\sqcup
j\lesssim a$ also. Moreover $a\in I_{0}$ but $b\not\in I_{0}$. Extend $I_{0}$
to a $\lesssim$-ideal $I$ of $S$ that is maximal with respect to not
containing $b$ using Zorn’s Lemma; then of course $a\in I$ still. Then
$a\theta_{I}=I$ whereas $b\theta_{I}=\overline{b}\neq I$, so
$(a,b)\not\in\epsilon_{I}$.

Secondly, suppose $b\lesssim a$, and recall that $a\lesssim b$. Suppose for a
contradiction that $b\lesssim a\curlyvee b$ also. So $b\sqcup a=b$, $a\sqcup
b=a$ and $(a\curlyvee b)\sqcup b=a\curlyvee b$. Hence

  1. 1.

$b\curlyvee(b\curlyvee a)=b$,

  2. 2.

$a\curlyvee(a\curlyvee b)=a$,

  3. 3.

$(a\curlyvee b)\curlyvee((a\curlyvee b)\curlyvee b)=a\curlyvee b$.

Recalling that $s\curlyvee t=t\curlyvee s$ for all $s,t$, using (1) in (3)
gives $(a\curlyvee b)\curlyvee b=a\curlyvee b$, and (1) then gives
$b=a\curlyvee b$, and then (2) gives $a\curlyvee b=a$, and so $a=b$, a
contradiction. So $b\not\lesssim a\curlyvee b$. Now let $I_{0}=\\{s\in S\mid
s\lesssim a\curlyvee b\\}$, again a $\lesssim$-ideal of $S$, and $b\not\in
I_{0}$ as just shown. Again extend to a $\lesssim$-ideal of $S$ that is
maximal with respect to not containing $b$ using Zorn’s Lemma, noting that
$a\curlyvee b\in I$. If $a\in I$ then $a\theta_{I}=I$, whereas
$b\theta_{I}=\overline{b}\neq I$ (as before). If $a\not\in I$, so that
$b\not\in I$ and so $a\theta_{I}=\overline{a}$ and $b\theta_{I}=\overline{b}$
are both defined, because $a\curlyvee b\in I$, we have $a\theta_{I}\neq
b\theta_{I}$. So $(a,b)\not\in\epsilon_{I}$ in either case. $\Box$

From the above lemma, as well as Proposition 4.3 and the discussion after it,
we obtain the following.

###### Theorem 4.7

The class of functional algebras of signature $(\curlyvee)$ equals the class
of $\curlyvee$-algebras, which consists of subdirect products of flat
$\curlyvee$-algebras.

This shows that the class of functional algebras of signature $(\curlyvee)$ is
a finitely based quasivariety (and not a variety by Theorem 3.11). It also
follows that knowledge of $\sqcup$ is enough to determine $\curlyvee$ in a
$\curlyvee$-algebra, since from it one can recover $\leq$, hence meets where
they exist, and then $a\curlyvee b=(a\sqcup b)\wedge(b\sqcup a)$ (a meet which
will always exist in a $\curlyvee$-algebra since it is functional).

###  4.2 Completeness for ado-semilattices

The notion of flatness for ado-semilattices is precisely that for
o-semilattices as discussed in [4]; from the poset perspective they are just
flat posets. As noted in [4], all flat o-semilattices are functional, and
hence are ado-semilattices, and indeed they are exactly o-semilattices that
satisfy $0\cap a=a$ and $a\cap b=0$ for $a\neq b$; it follows that $a\sqcup
b=a$ if $a\neq 0$, with $0\sqcup a=a$ for all $a$.

Since every ado-semilattice is a $\curlyvee$-algebra by Corollary 3.10, we
obtain the following consequence of Proposition 4.2.

###### Corollary 4.8

Every flat ado-semilattice is simple, hence subdirectly irreducible.

###### Lemma 4.9

Let $S$ be an ado-semilattice, with $I$ a relatively maximal $\lesssim$-ideal
of $S$. Then the $\curlyvee$-algebra congruence $\epsilon_{I}$ is an ado-
semilattice congruence on $S$ and $S/\epsilon_{I}$ is a flat ado-semilattice.
Moreover $S$ is a subdirect product of the $S/\epsilon_{I}$ as $I$ ranges over
all relatively maximal $\lesssim$-ideals of $S$.

Proof. Since each $S_{I}$ as in the proof of Lemma 4.6 is made into a flat
poset with $I$ as the bottom element, it has flat ado-semilattice structure as
well. To show what is claimed, it suffices to show that each
$\curlyvee$-algebra homomorphism $\theta_{I}$ respects $\cap$ as well.

Let $a,b\in S$. First, suppose $a\cap b\not\in I$. Then $a\curlyvee b\not\in
I$ since $a\cap b\leq a\curlyvee b$, and also $a,b\not\in I$ since $a\cap
b\leq a,b$, so $\overline{a}=\overline{b}$. Moreover $(a\cap b)\curlyvee
a=((a\cap b)\sqcup a)\cap(a\sqcup(a\cap b))=a\cap a=a\not\in I$ since $a\cap
b\leq a$. Alternatively, suppose $a\cap b\in I$; then $(a\cap b)\theta_{I}=I$.
Now if $a\in I$ or $b\in I$, $a\theta_{I}\cap b\theta_{I}=I$. If $a\not\in I$
and $b\not\in I$, then $a\neq b$ as otherwise $a\cap b\not\in I$, a
contradiction, so $a\theta_{I}\cap
b\theta_{I}=\overline{a}\cap\overline{b}=I$. So in either case, we have
$(a\cap b)\theta_{I}=a\theta_{I}\cap b\theta_{I}$, as required. $\Box$

Again, we immediately obtain the following.

###### Theorem 4.10

The class of functional algebras of signature $(\sqcup,\cap)$ is finitely
axiomatised as the variety of ado-semilattices.

##  5 Difference

Recall that the operation of difference can be used to express intersection.
The functional signature $(\sqcup,\backslash)$ is axiomatised in [4] as the
variety of associative subtraction o-semilattices: these are associative
o-semilattices which satisfy several further laws involving difference only
which ensure they are Boolean nearlattices (see Proposition 6.1 there). An
alternative axiomatisation building on ado-semilattices follows from the next
definition and result.

###### Definition 5.1

An algebra $(S,\sqcup,\backslash)$ such that $(S,\sqcup,\cap)$ is an ado-
semilattice and the following three laws are satisfied is said to be an od-
algebra (override-difference algebra):

  1. 1.

$(a\backslash b)\cap b=0$ (meaning that $(a\backslash b)\cap b$ is constant);

  2. 2.

$(a\backslash b)\sqcup(a\cap b)=a$.

(Here we define $a\cap b=a\backslash(a\backslash b)$.)

It is fairly clear that the od-algebra laws are all functionally sound and
that we may interpret $0$ as the empty function.

###### Proposition 5.2

The functional algebras of signature $(S,\sqcup,\backslash)$ are axiomatised
by the od-algebra laws.

Proof. Soundness was noted earlier. Conversely, suppose
$(S,\sqcup,\backslash)$ satisfies the above conditions. Then we know that its
$(S,\sqcup,\cap)$-reduct is functional from Theorem 4.10. Moreover, using the
three laws involving difference, we have that for $a\in S$, $a\backslash a\leq
a$, so $a\backslash a=(a\backslash a)\cap a=0$, and so $0\sqcup a=(a\backslash
a)\sqcup a=a$, so $0\leq a$ for all $a\in S$, and so $0\in I$ for every
$\lesssim$-ideal $I$ of $S$. So each $\theta_{I}$ maps $0$ to $I$ in $S_{I}$.
View $S_{I}$ as partial functions; then the bottom element $I$ can be taken to
be the empty function. Hence in the resulting functional representation of $S$
determined by $\theta$ (or indeed any in which all other operations and $0$
are correctly represented), the three laws for $\backslash$ above force
$a\backslash b$ to be (1) disjoint with $b$, (2) contained in $a$, and (3)
such that when its (necessarily disjoint) union with $a\cap b$ is taken, the
result is all of $a$. This forces $a\backslash b$ to be the set-theoretic
difference of $a,b$. (In the language of Section 3.1 of [10], $\backslash$ is
abstractly definable in terms of $\sqcup,\cap,0$.) $\Box$

So the variety of od-algebras axiomatises the functional algebras of signature
$(\sqcup,\backslash)$, and is therefore equal to the variety of associative
subtractive o-semilattices as in [4].

## Acknowledgements

I would like to acknowledge the considerable time-saving assistance of the
Prover9/Mace4 software [15], which helped with finding both proofs and
examples.

## References

  * [1] Abbot, J.C.: Semi-Boolean algebra. Mat. Vesn. 4(19), 177–198 (1967)
  * [2] Abbot, J.C.: Implicational algebras. Bull. Math. Soc. Sci. Math. Répub. Social. Roum. 11(59), 1–23 (1967)
  * [3] Berendsen, J., Jansen, D.N., Schmaltz, J., Vaandrager, F.W.: The axiomatization of override and update, J. Appl. Logic 8, 141–150 (2010)
  * [4] Cirulis, J.: Nearlattices with an overriding operation, Order 28, 33–51 (2011)
  * [5] Cvetko-Vah, K., Leech, J., Spinks, M.: Skew lattices and binary operations on functions, J. Appl. Logic 11, 253–265 (2013)
  * [6] Garvac’kiĭ, V.S.: $\cap$-semigroups of transformations. Theory of Semigroups and its Applications, No. 2, pp.2–13, Izdat. Saratov. Uni., Saratov (1971) (Russian)
  * [7] Guzmán, F.: The poset structure of positive implicative BCK-algebras. Algebra Univers. 32, 398–406 (1994)
  * [8] Hirsch, R., McLean, B.: Disjoint-union partial algebras, Logical Methods in Comp. Sci. 13(2:10) (2017)
  * [9] Jackson, M., Stokes, T.: Modal restriction semigroups: towards an algebra of functions, Int. J. Algebra Comput. 21, 1053–1095 (2011)
  * [10] Jackson, M., Stokes, T.: Override and update, J. Pure Appl. Algebra 225, 106532 (2021)
  * [11] Leech, J.: Skew Boolean algebras, Algebra Univers. 27, 497–506 (1990)
  * [12] Leech, J.: Normal skew lattices, Semigroup Forum 44, 1–8 (1992)
  * [13] Margolis, S., Saliola, F., Steinberg, B.: Semigroups embeddable in hyperplane face monoids, Semigroup Forum 89, 236–248 (2014)
  * [14] Margolis, S., Saliola, F., Steinberg, B.: Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry, to appear in Memoirs of the Americal Mathematical Society. https://arxiv.org/abs/1508.05446v2
  * [15] McCune, W.: Prover9 and Mace4, version LADR-Dec-2007, (http://www.cs.unm.edu/ mccune/prover9/).
  * [16] Saliola, F.: The quiver of the semigroup algebra of a left regular band, Int. J. Algebra Comput. 17, 1593–1610 (2007)
  * [17] Schein, B.M.: Restrictively multiplicative algebras of transformations, Izv. Vysš. Učebn. Zaved., Mat. 1970 (4(95)), 91–102 (1970) (Russian)
  * [18] Spivey, J.M.: The Z Notation: A Reference Manual, Prentice Hall, Englewood Cliffs, 1989.

Tim Stokes
Department of Mathematics
University of Waikato
Hamilton 3216
New Zealand.
email<EMAIL_ADDRESS>