CONGRUENCE LATTICES OF SEMILATTICES WITH OPERATORS, PART I

KIRA ADARICHEVA AND J. B. NATION

Abstract. We show that for every quasivarietyKof structures (where both functions and relations are allowed) there is a semilatticeSwith operators such that the lattice of quasi-equational theories ofK(the dual of the lattice of sub-quasivarieties ofK) is isomorphic to Con(S,+,0,F).

As a consequence, new restrictions on the natural quasi-interior operator on lattices of quasi-equational theories are found.

1. Motivation and terminology

Our objective is to provide, for the lattice of quasivarieties contained in a given quasivariety (Q-lattices in short), a description similar to the one that characterizes the lattice of subvarieties of a given variety as the dual of the lattice of fully invariant congruences on a countably generated free algebra.

Just as the result for varieties is more naturally expressed in terms of the lattice of equational theories, rather than the dual lattice of varieties, so it will be more natural to consider lattices of quasi-equational theories rather than lattices of quasivarieties.

The basic result is that the lattice of quasi-equational theories extend- ing a given quasi-equational theory is isomorphic to the congruence lattice of a semilattice with operators preserving join and 0. These lattices sup- port a natural quasi-interior operator, the properties of which lead to new restrictions on lattices of quasi-equational theories.

This is the first paper in a series of four. Part II shows that if S is a semilattice with both 0 and 1, andGis a group of operators on Ssuch that each operator inGfixes both 0 and 1, then there is a quasi-equational theory T such that Con(S,+,0,G) is isomorphic to the lattice of quasi-equational theories extendingT. The third part [30] shows that ifS is any semilattice with operators, then ConS is isomorphic to the lattice of implicational the- ories extending some given implicational theory, but in a language that may

Date: December 22, 2013.

2010Mathematics Subject Classification. 08C15, 08A30, 06A12.

Key words and phrases. quasivariety, quasi-equational theory, congruence lattice, semilattice.

The authors were supported in part by a grant from the U.S. Civilian Research &

Development Foundation. The first author was also supported in part by INTAS Grant N03-51-4110.

1

### arXiv:1106.2203v3 [math.RA] 28 Feb 2012

not include equality. The fourth paper [23], with T. Holmes, D. Kitsuwa and S. Tamagawa, concerns the structure of lattices of atomic theories in a language without equality.

The setting for varieties is traditionally algebras, i.e., sets with opera- tions, whereas work on quasivarieties normally allows structures, i.e., sets with operations and relations. Some adjustments are required for the more general setting. Let us review the universal algebra of structures, following Section 1.4 of Gorbunov [17]; see also Gorbunov and Tumanov [19, 20] and Gorbunov [15].

Thetype of a structure is determined by itssignature σ=hF,R, ρiwhere
Fis a set of function symbols,Ris a set of relation symbols, andρ:F∪R→ω
assigns arity. A structure is then A = hA,F^{A},R^{A}i where A is the carrier
set,F^{A} is the set of operations on A, and R^{A} is the set of relations onA.

For structures A and B of the same type, a map h : A → B is a ho-
momorphism if it preserves operations and h(R^{A}) ⊆R^{B} for each relation
symbolR. Anendomorphism ofA is a homomorphism ε:A→A.

The kernel kerh of a homomorphism h is a pair κ=hκ0, κ1iwhere

• κ_{0} is the equivalence relation onA induced by h, i.e., (x, y)∈κ_{0} iff
h(x) =h(y),

• κ_{1} =S

R∈Rκ^{R}_{1} whereκ^{R}_{1} =h^{−1}(R^{B}) ={s∈A^{ρ(R)}:h(s)∈R^{B}}.

Equality is treated differently because, in standard logic, equality is assumed to be a congruence relation. Indeed, the statements that≈is reflexive, sym- metric, transitive, and compatible with the functions ofFand the relations ofR, are universal Horn sentences. Thus in normal quasi-equational logic we are working in the quasivariety given by these laws. This is not necessary:

see Parts III and IV [30, 23].

Acongruence on a structureA=hA,F^{A},R^{A}iis a pairθ=hθ0, θ1iwhere

• θ0 is an equivalence relation onAthat is compatible with the oper-
ations ofF^{A}, and

• θ1 =S

R∈Rθ^{R}_{1} where eachθ_{1}^{R}⊆A^{ρ(R)}andR^{A} ⊆θ^{R}_{1}, i.e., the original
relations ofA are contained in those of θ_{1}, and for each R ∈ R, if
a∈θ_{1}^{R} andb∈A^{ρ(R)} and aθ0b componentwise, thenb∈θ^{R}_{1}.
Note that if h :A→ B is a homomorphism, then kerh is a congruence on
A. The collection of all congruences onAforms an algebraic lattice Con A
under set containment.

A subsetS ⊆Ais a subuniverse if it is closed under the operations ofA.

A substructure of A is S = hS,F^{S},R^{S}i where S is a subuniverse of A, for
each operation symbol f ∈ F the operation f^{S} is the restriction of f^{A} to
S^{ρ(f}^{)}, and for each relation symbolR∈Fthe relation R^{S} is R^{A}∩S^{ρ(R)}.

Given a congruenceθon a structureA, we can form a quotient structure
A/θby defining operations and relations on theθ_{0}-classes ofAin the natural
way. The isomorphism theorems carry over to this more general setting. In
particular, if h :A → B is a homomorphism, then h(A) is a substructure
of B, and h(B) is isomorphic toA/kerh.

A congruence is fully invariant if, for every endomorphismεofA,

• a θ_{0}b impliesε(a)θ_{0}ε(b), and

• for eachR∈R,a∈θ^{R}_{1} impliesε(a)∈θ^{R}_{1}.

The lattice of fully invariant congruences is denoted Ficon A.

The congruence generation theorems are straightforward to generalize.

Let C ⊆ A^{2} and let D be a set of formulae of the form R(a) with R ∈ R
and a ∈A^{ρ(R)}. The congruence generated by C∪D, denoted con(C∪D),
is the least congruence θ = hθ0, θ1i such that C ⊆ θ0 and a ∈ θ_{1}^{R} for
all R(a) ∈ D. The equivalence relation θ_{0} is given by the usual Mal’cev
construction applied to C, and θ1 is the closure ofD∪R^{A} with respect to
θ_{0}, i.e., if R(a)∈D andaθ_{0}b componentwise, thenb∈θ^{R}_{1}.

Avariety is a class closed under homomorphic images, substructures and
direct products. Varieties are determined by laws of the form s ≈ t and
R(s) where s,tand the components ofsare terms. That is, a variety is the
class of all similar structures satisfying a collection of atomic formulae. If
V is a variety of structures andFis the countably generated free structure
forV, then the lattice Lv(V) of subvarieties ofVis dually isomorphic to the
lattice of fully invariant congruences of F, i.e., Lv(V) ∼=^{d} FiconF. In the
case of varieties of algebras (with no relational symbols in the language),
this is equivalent to adding the endomorphisms of F to its operations and
taking the usual congruence lattice, so that Lv(V) ∼=^{d} Con (F,F∪End F).

For structures in general, this simplification does not work. (These standard results are based on Birkhoff [8].)

A quasivariety is a class of structures closed under substructures, direct products and ultraproducts (equivalently, substructures and reduced prod- ucts). Quasivarieties are determined by laws that are quasi-identities, i.e., Horn sentences

&1≤i≤nαi =⇒ β

where the α_{i} andβ are atomic formulae of the form s≈t and/orR(s).

If K is a quasivariety and A a structure, then a congruence θ on A is
said to be a K-congruence if A/θ ∈ K. Since the largest congruence is
a K-congruence, and K-congruences are closed under intersection, the set
of K-congruences on A forms a complete meet subsemilattice of ConA,
denoted Con_{K} A. Moreover, Con_{K} Ais itself an algebraic lattice.

Let us adopt some notation to reflect the standard duality between the-
ories and models. For a variety V, let ATh(V) denote the lattice of “equa-
tional” (really, atomic) theories extending the theory ofV, so that ATh(V)∼=^{d}
L_{v}(V). Likewise, for a quasivarietyK, let QTh(K) denote the lattice of quasi-
equational theories containing the theory ofK, so that QTh(K)∼=^{d}L_{q}(K).

Gorbunov and Tumanov described the latticeLq(K) of quasivarieties con- tained in a given quasivarietyKin terms of algebraic subsets. This descrip- tion requires some definitions.

• Given K, let F = F_{K}(ω) be the countably generated K-free struc-
ture. Then Con_{K} F denotes the lattice of allK-congruences ofF.

• Define the isomorphism relation I and embedding relation E on
Con_{K} Fby

ϕ I ψ if F/ψ∼=F/ϕ ϕ E ψ if F/ψ≤F/ϕ.

• For a binary relationRon a complete latticeL, let Sp(L, R) denote the lattice of all R-closed algebraic subsets of L. (Recall that S ⊆ L is algebraic if it is closed under arbitrary meets and nonempty directed joins. The set S is R-closed if s ∈ S and s R t implies t∈S.)

The characterization theorem of Gorbunov and Tumanov [20] then says that
Lq(K)∼= Sp(Con_{K} F, I)∼= Sp(Con_{K} F, E).

See Section 5.2 of Gorbunov [17]; also cf. Hoehnke [21].

By way of comparison, we might say that the description of the lattice
of subvarieties by L_{v}(V) ∼=^{d} FiconF reflects equational logic, whereas the
representation Lq(K) ∼= Sp(Con_{K} F, E) say reflects structural properties
(closure under S, P and direct limits). We would like to find an analogue of
the former for quasivarieties, ideally something of the form L_{q}(K)∼=^{d}Con S
for some semilatticeSwith operators, reflecting quasi-equational logic. This
is done below. Indeed, while our emphasis is on the structure ofQ-lattices,
Bob Quackenbush has used the same general ideas to provide a nice algebraic
proof of the completeness theorem for quasi-equational logic [33].

The lattice QTh(K) of theories of a quasivariety is algebraic and (com- pletely) meet semidistributive. Most of the other known properties of these lattices can be described in terms of the natural equa-interior operator, which is the dual of an equational closure operator on QTh(K). See Appen- dix II or Section 5.3 of Gorbunov [17].

A.M. Nurakunov [31], building on earlier work of R. McKenzie [28] and R. Newrly [29], has recently provided a nice algebraic description of the lattices ATh(V), where V is a variety of algebras, as congruence lattices of monoids with two additional unary operations satisfying certain properties.

See Appendix III.

Finally, let us note two (related) major differences between quasivarieties of structures versus algebras. Firstly, the greatest quasi-equational theory in QTh(K) need not be compact if the language of K has infinitely many relations. Secondly, many nice representation theorems for quasivarieties use one-element structures, whereas one-element algebras are trivial. Indeed, in light of Theorem 2 below, Theorem 5.2.8 of Gorbunov [17] (from Gorbunov and Tumanov [18]) can be stated as follows.

Theorem 1. The following are equivalent for an algebraic lattice L.

(1) L∼= Con(S,+,0)for some semilattice S.

(2) L∼= QTh(K) for some quasivariety K of one-element structures.

Congruence lattices of semilattices are coatomistic, i.e., every element is a meet of coatoms. Thus the Q-lattices for the special quasivarieties in the preceding theorem are correspondingly atomistic.

2. Congruence lattices of semilattices

Let Sp(L) denote the lattice of algebraic subsets of a complete lattice L.

IfLis an algebraic lattice, letLcdenote its semilattice of compact elements.

This is a join semilattice with zero. The following result of Fajtlowicz and Schmidt [11] directly generalizes the Freese-Nation theorem [13]. See also [12], [22], [34].

Theorem 2. If L is an algebraic lattice, then Sp(L)∼=^{d}Con L_{c}.

Proof. For an arbitrary join 0-semilattice S = hS,+,0i we set up a Galois correspondence between congruences ofS and algebraic subsets of the ideal latticeI(S) as follows.

Forθ∈Con S, let h(θ) be the set of allθ-closed ideals of S.

ForH ∈Sp(I(S)), let x ρ(H) y if{I ∈H:x∈I}={J ∈H:y∈J}.

It is straightforward to check thathandρare order-reversing, thath(θ)∈ Sp(I(S)) andρ(H)∈Con S.

To show that θ=ρh(θ), we note that ifx < y (w.l.o.g.) and (x, y) ∈/ θ, then {z ∈ S :x+z θ x} is a θ-closed ideal containing x and not y. Hence (x, y)∈/ ρh(θ).

To show that H =hρ(H), consider an ideal J /∈ H. For any x ∈ S, let ˆ

x=T

{I ∈H:x∈I}, noting that ˆx∈H. Then{ˆx:x∈J} is up-directed, whenceS

{ˆx:x∈J} ∈H. Therefore the union properly containsJ, so that there existx < y withx∈J and y∈xˆ−J, andJ is notρ(H)-closed. Thus

J /∈H impliesJ /∈hρ(H), as desired.

Compare this with the following result of Adaricheva, Gorbunov and Tu- manov ([5] Theorem 2.4, also [17] Theorem 4.4.12).

Theorem 3. Let Lbe a join semidistributive lattice that is finitely presented within the class SD∨. Then L ≤ Sp(A) for some algebraic and dually algebraic latticeA.

On the other hand, Example 4.4.15 of Gorbunov [17] gives a 4-generated join semidistributive lattice that is not embeddable into any lower continuous lattice satisfying SD∨.

Keith Kearnes points out that the classESof lattices that are embeddable into congruence lattices of semilattices is not first order. Indeed, every finite meet semidistributive lattice is inES, andESis closed under S and P. Now the quasivariety SD∧ is generated by its finite members (Tumanov [35], Theorem 4.1.7 in [17]), while ESis properly contained in SD∧. Hence ESis not a quasivariety, which means it must not be closed under ultraproducts.

This result has been generalized in Kearnes and Nation [25].

3. Connection with Quasivarieties

In this section, we will show that for each quasivarietyKof structures, the lattice of quasi-equational theories Qth(K) is isomorphic to the congruence lattice of a semilattice with operators.

Given a quasivarietyK, letF=F_{K}(ω) be theK-free algebra onω gener-
ators, and let Con_{K} F be the lattice ofK-congruences of F. For a set S of
atomic formulae, recall that the K-congruence generated by S is

con_{K} S=\

{ψ∈Con F:F/ψ∈K and S ⊆ψ}.

Then let T = T_{K} denote the join semilattice of compact K-congruences
in Con_{K} F. Thus T = (Con_{K} F_{K}(ω))c consists of finite joins of the form
W

jϕ_{j}, with each ϕ_{j} either con_{K}(s, t) or con_{K} R(s) for terms s, t, s_{i} ∈ F
and a relation R.

Let X be a free generating set for F_{K}(ω). Any map σ0 : X → F can
be extended to an endomorphism σ : F → F in the usual way. Since the
image σ(F) is a substructure of F, the kernel of an endomorphism σ is a
K-congruence. The endomorphisms of Fform a monoid EndF.

The endomorphisms of Fact naturally on T. Forε∈EndF, define
bε(con_{K}(s, t)) = con_{K}(εs, εt)

ε(conb _{K} R(s)) = con_{K} R(εs)
ε(b_

j

ϕ_{j}) =_

j

εϕb _{j}.

The next lemma is used to check the crucial technical details that bεis well- defined, and hence join-preserving.

Lemma 4. Let K be a quasivariety, F a K-free algebra, and ε ∈ End F.

Let α, β1, . . . , βm be atomic formulae. In Con_{K} F,
con_{K} α≤_

con_{K} βj implies ε(conb _{K} α)≤_

ε(conb _{K} βj).

Proof. For an atomic formulaα and a congruence θ, let us write α ∈ θ to
mean either (1)α iss≈tand (s, t)∈θ_{0}, or (2)α isR(s) ands∈θ^{R}_{1}. So for
the lemma, we are given that ifF/ψ ∈K and β1, . . . , βm ∈ψ, then α∈ψ.

We want to show that ifF/θ∈K and εβ1, . . . , εβm ∈θ, then εα∈θ.

Letθ∈ConF be a congruence such thatF/θ∈K, and let h:F→F/θ
be the natural map. Thenhε:F→F/θ, and since hε(F) is a substructure
of h(F), the image is in K. Now β_{1}, . . . , β_{m} ∈ kerhε, and so α ∈ kerhε.

Thusεα∈kerh=θ, as desired.

Now let ξ be a compact K-congruence. Suppose that ξ = W

iϕ_{i} and
ξ=W

jψj inT, with each ϕi andψj being a principalK-congruence. Then for each i we have ϕi ≤ W

jψj, whence bεϕi ≤ W

jbεψj by Lemma 4. Thus W

iεϕb i ≤ W

jεψb j. Symmetrically W

jεψb j ≤ W

iεϕb i, and so εξb = W

jbεψj = W

iεϕb i is well-defined.

It then follows from the definition of εbthat ifϕ =W

iϕi and ψ =W

jψj

inT, then

bε(ϕ∨ψ) =ε(b_

i

ϕ_{i} ∨ _

j

ψ_{j})

=_

i

εϕb i ∨ _

j

εψb j)

=εϕb ∨bεψ.

Thus bε preserves joins. Also note that for the zero congruence we have ε(0) = 0.b

LetEb={εb:ε∈End F}, and consider the algebra S=S_{K}=hT,∨,0,Ebi.

By the preceding remarks, the operations ofbEareoperators onS, i.e., (∨,0)- homomorphisms, soS is a join semilattice with operators. With this setup, we can now state our main result.

Theorem 5. For a quasivariety K,

L_{q}(K)∼=^{d}ConS

where S = hT,∨,0,bEi with T the semilattice of compact congruences of
Con_{K} F, E= EndF, and F=F_{K}(ω).

In Part II, we will use this technical variation.

Theorem 6. Let K be a quasivariety and letn≥1 be an integer. Then the lattice of all quasi-equational theories that

(1) contain the theory of K, and

(2) are determined relative to K by quasi-identities in at most n vari- ables,

is isomorphic to Con S_{n}, where S_{n} = hT_{n},∨,0,bEi with T_{n} the semilattice
of compact congruences of Con_{K} F, E= EndF, and F=F_{K}(n).

We shall prove Theorem 5, and afterwards discuss the modification re-
quired for Theorem 6, which is essentially just replacing F_{K}(ω) by F_{K}(n).

For the proof of Theorem 5, and for its application, it is natural to use two structures closely related to the congruence lattice instead. For an algebra A with a join semilattice reduct, let DonA be the lattice of all reflexive, transitive, compatible relationsR such that≥ ⊆R, i.e.,x≥y impliesx R y.

Let Eon A be the lattice of all reflexive, transitive, compatible relationsR such that

(1) R⊆≤, i.e., x R y implies x≤y, and (2) if x≤y≤z and x R z, then x R y.

Lemma 7. If A=hA,∨,0,Fiis a semilattice with operators, then ConA∼= DonA∼= EonA.

Proof. Letδ: Con A→DonA via δ(θ) =θ◦ ≥, so that x δ(θ)y iff x θ x∨y

and letγ : Don A→Con A via γ(R) = (R∩ ≤)◦(R∩ ≤)^{`}, so that
x γ(R)y iff x R x∨y &y R x∨y.

Now we check that, for θ∈ConA and R∈DonA, (1) δ(θ)∈DonA,

(2) γ(R)∈Con A,

(3) δ and γ are order-preserving, (4) γδ(θ) =θ,

(5) δγ(R) =R.

This is straightforward and only slightly tedious.

Similarly, letε: Don A→ Eon A via ε(R) = R∩ ≤, and δ^{0} : Eon A →
DonA via δ^{0}(S) = S◦ ≥, and check the analogous statements for this
pair, which is again routine. Note that for a congruence relation θ the
corresponding eon-relation is εδ(θ) =θ∩ ≤, while for S ∈ Eon A we have

the congruence γδ^{0}(S) =S◦S^{`}.

Now we define a Galois connection between T^{2} and structures A ∈ K.
(The collection of structures A ∈ K forms a proper class. However, every
quasivariety is determined by its finitely generated members. So we could
avoid any potential logical difficulties by restricting our attention to struc-
turesAdefined on some fixed infinite set large enough to contain an isomor-
phic copy of each finitely generated member of K.) For a pair (β, γ) ∈T^{2}
and A ∈ K, let (β, γ) ΞA if, whenever h : F → A is a homomorphism,
β ≤kerhimplies γ ≤kerh.

Then, following the usual rubric for a Galois connection, for X⊆T^{2} let
κ(X) ={A∈K: (β, γ) ΞA for all (β, γ)∈X}.

Likewise, forY ⊆K, let

∆(Y) ={(β, γ)∈T^{2} : (β, γ) ΞA for allA∈Y}.

We must check that the following hold forX⊆T^{2} and Y ⊆K.
(1) κ(X)∈Lq(K),

(2) ∆(Y)∈DonS,

(3) ∆κ(X) =X ifX ∈DonS,
(4) κ∆(Y) =Y ifY ∈L_{q}(K).

To prove (1), we show that κ(X) is closed under substructures, direct products and ultraproducts. Closure under substructures is immediate, and closure under direct products follows from the observation that if h :F → Q

iA_{i} then kerh = T

kerπ_{i}h. So let A_{i} ∈ κ(X) for i ∈ I, let U be an
ultrafilter on I, and let h : F→ Q

Ai/U be a homomorphism. Since F is free, we can findf :F→Q

A_{i} such thath=gf whereg:Q

A_{i}→Q
A_{i}/U
is the standard map. Let (β, γ) ∈ X with β = W

ϕj and γ = W

ψk, where
these are finite joins and each ϕand ψis of the form con_{K} α for an atomic
formulaα. Eachα in turn is of the form either s≈t orR(s).

Assumeβ ≤kerh. Thenh(αj) holds for eachj, so that for eachjwe have
{i∈I :π_{i}f(α_{j})} ∈U. Taking the intersection, {i∈I :∀j π_{i}f(α_{j})} ∈U. In
other words, {i∈ I :β ≤kerπif} ∈ U, and so the same thing holds for γ.

Now we reverse the steps to obtainγ ≤kerh, as desired. Thusκ(X) is also closed under ultraproducts, and it is a quasivariety.

To prove (2), letY ⊆K. It is straightforward that ∆(Y)⊆T^{2}is a relation
that is reflexive, transitive, and contains≥. Moreover, if (β, γ)∈∆(Y) and
β ∨τ ≤ kerh for an appropriate h, then γ ∨τ ≤ kerh, so ∆(Y) respects
joins.

Again let (β, γ) ∈ ∆(Y) and h : F → A with A ∈ Y. Let εb∈ bE and assume thatbεβ≤kerh. This is equivalent toβ≤kerhε, as both mean that hε(αj) holds for all j, where β = W

con_{K} αj. Hence γ ≤ kerhε, yielding
εγb ≤kerh. Thus ∆(Y) is compatible with the operations ofEb. We conclude
that ∆(Y)∈DonS.

Next consider (4). Given that Y is a quasivariety, we want to show that κ∆(Y) ⊆ Y. Let A ∈ κ∆(Y), and let &jαj =⇒ ζ be any quasi-identity holding in Y. Set β =W

con_{K} α_{j} and γ = con_{K} ζ, and let h :F → A be
a homomorphism. Then (β, γ) ∈ ∆(Y), whence as A ∈ κ∆(Y) we have
β ≤kerhimplies γ≤kerh. ThusAsatisfies the quasi-identity in question,
which shows thatκ∆(Y)⊆Y, as desired.

Part (3) requires the most care (we must show that relations in Don S correspond to theories of quasivarieties). Given X ∈ DonS, we want to prove that ∆κ(X)⊆X.

Let (µ, ν)∈T^{2}−X. Define a congruence θon Fas follows.

θ0 =µ
θ_{k+1} =θ_{k}∨_

{γ|(β, γ)∈X and β≤θ_{k}}
θ=_

k

θ_{k}.

LetC=F/θ. We want to show thatC∈κ(X) and thatν θ.

Claim a. If ψ is compact and ψ ≤ θ, then (µ, ψ) ∈ X. We prove by induction that if compactψ≤θk, then (µ, ψ)∈X. Fork= 0 this is trivial.

Assume the statement holds for k. Suppose we have a finite collection of (βi, γi) ∈ X with each βi ≤θk. Let ξ = W

βi, so that ξ is compact and
βi ≤ξ ≤θ_{k}. Then (ξ, βi)∈X, so by transitivity (ξ, γi)∈X for alli. Hence
(ξ,W

γ_{i})∈X. Now inductively (µ, ξ)∈X, and so (µ,W

γ_{i})∈X.

Claim b. If(β, γ)∈X andβ ≤θ, thenγ ≤θ. This holds by construction and compactness.

Claim c. F/θ∈κ(X). Suppose h:F→F/θ, (β, γ) ∈X and β ≤kerh.

Let f : F → F/θ be the standard map with kerf = θ. There exists an endmorphismεofFsuch thath=f ε. Then, using Claim b and an argument

above,

β ≤kerh= kerf ε =⇒ εβb ≤kerf =θ

=⇒ εγb ≤θ= kerf

=⇒ γ ≤kerf ε= kerh.

Claim d. (µ, ν) ∈/ ∆κ(X). This is because C ∈ κ(X) by Claim c and µ≤θ= kerf, while νθby Claim a.

This completes the proof of (3), and hence Theorem 5.

Only a slight modification is required for Theorem 6. Consider the col- lection of quasivarieties Csatisfying the conditions of the theorem:

(1) C⊆K, and

(2) Cis determined relative to K by quasi-identities in at most n vari- ables.

These properties mean that a structureCis in Cif and only if

(1)^{0} Every mapf_{0} :ω→Cextends to a homomorphismf :F_{K}(ω)→C,
and

(2)^{0} Every mapg_{0}:n→Cextends to a homomorphismg:F_{C}(ω)→C.

Quasivarieties satisfying conditions (1) and (2) are closed under arbitrary
joins, and thus under containment they form a lattice which we will denote
byL^{n}_{q}(K). This is a complete join subsemilattice ofLq(K); the correspond-
ing dual lattice of theories is a complete meet subsemilattice QTh^{n}(K) of
QTh(K). The proof of Theorem 5 gives us QTh(K) as the congruence lattice
of a semilattice with operators obtained from F_{K}(ω). In view of condition
(2)^{0}, the same construction withF_{K}(ω) replaced throughout byF_{K}(n) yields
QTh^{n}(K).

4. Interpretation

The foregoing analysis is rather structural and omits the motivation,
which we supply here. Let β and γ be elements of T, i.e., compact K-
congruences on the free structureF. Then these are finite joins in Con_{K} F
of principal congruences, say β = W

con_{K} αj and γ = W

con_{K} ζk, where
eachα andζ is an atomic formula of the forms≈torR(s). The basic idea
is that the congruence con(β, β∨γ), on the semilattice S of compact K-
congruences of F with the endomorphisms as operators, should correspond
to the conjunction over the indices k of the quasi-identities &jαj =⇒ ζk,
and that furthermore the quasi-equational consequences of combining impli-
cations (modulo the theory ofK) behaves like the join operation in ConS.

But β ≥ γ should mean thatβ =⇒ γ, so it is really Don S that we want.

On the other hand, all the nontrivial information is contained already in Eon S, and these three lattices are isomorphic.

LetH(β, γ) denote the set of all quasi-identities &_{j}α_{j} =⇒ ζ_{k} where the
atomic formulae αj and ζk come from join representations β = W

con_{K} αj

and γ = W

con_{K} ζk. Let ∆ and κ be the mappings from the Galois con-
nection in the proof of Theorem 5. The semantic versions of the structural
results of the preceding section then take the following form.

Lemma 8. Let Q be a quasivariety contained in K. The set of all pairs
(β, γ) such that Q satisfies each of the sentences in H(β, γ) is in Don S,
where S = hT,∨,0,bEi with T the semilattice of compact congruences of
Con_{K} F, E= EndF, and F=F_{K}(ω).

Lemma 9. Let Y be a collection of structures contained inK. The following are equivalent.

(1) (β, γ)∈∆(Y).

(2) EveryA∈Y satisfies all the implications inH(β, γ).

(3) The quasivarietySPU(Y) satisfies all the implications in H(β, γ).

Lemma 10. Let X ⊆ T^{2}, where T is as in Lemma 8. The following are
equivalent for a structureA.

(1) A∈κ(X).

(2) For every pair (β, γ) ∈ X, A satisfies all the quasi-identities of H(β, γ).

As always, it is good to understand both the semantic and logical view- point.

5. Congruence lattices of semilattices with operators Let us examine more closely lattices of the form Con(S,+,0,F). The following theorem summarizes some fundamental facts about their structure.

Theorem 11. Let (S,+,0,F) be a semilattice with operators.

(1) An ideal I of S is the 0-class of some congruence relation if and only if f(I)⊆I for everyf ∈F.

(2) If the ideal I isF-closed, then the least congruence with 0-class I is η(I), the semilattice congruence generated by I. It is characterized by

x η(I) y iff x+i=y+i for some i∈I.

(3) There is also a greatest congruence with 0-class I, which we will
denote byτ(I). To describe this, letF^{†}denote the monoid generated
by F, including the identity function. Then

x τ(I) y iff (∀h∈F^{†}) h(x)∈I ⇐⇒h(y)∈I.

The proof of each part of the theorem is straightforward. As a sample application, it follows that if S is a simple semigroup with one operator, then|S|= 2.

The maps η and τ from Theorem 11 induce operations on the entire congruence lattice Con(S,+,0,F). If θ is a congruence with 0-class I, de- fine η(θ) = η(I) and τ(θ) = τ(I). The map η is known as the natural

equa-interior operator on Con(S,+,0,F). This terminology will be justified below.

The natural equa-interior operator induces a partition of Con(S,+,0,F).

Theorem 12. Let S = hS,+,0,Fi be a semilattice with operators. The natural equa-interior operator partitions Con(S) into intervals [η(θ), τ(θ)]

consisting of all the congruences with the same0-class (which is anF-closed ideal).

The natural equa-interior operator on the congruence lattice of a semilat- tice with operators plays a role dual to that of the equaclosure operator for lattices of quasivarieties.

Adaricheva and Gorbunov [4], building on Dziobiak [9], described the
natural equational closure operator on Q-lattices. In the dual language of
theories, the restriction of quasi-equational theories to atomic formulae gives
rise to an equa-interior operator (defined below) on QTh(K). Finitely based
subvarieties of a quasi-variety K are given by quasi-identities that can be
written asx≈x =⇒ &_{k}β_{k} for some atomic formulaeβ_{k}. By Lemma 9, the
corresponding congruences are of the form con(0, θ) where θ is a compact
K-congruence on the free algebra F_{K}(ω). More generally, subvarieties of K
correspond to joins of these, i.e., to congruences of the form W

θ∈Icon(0, θ) for some ideal I of the semilattice of compact K-congruences. Thus we should expect the mapηto be the analogous interior operator on congruence lattices of semilattices with operators.

We now define an equa-interior operator abstractly to have those prop- erties that we know to hold for the natural equa-interior operator on the lattice of theories of a quasivariety. One of our main goals, in this section and the next two, is to extend this list of known properties using the repre- sentation of the lattice of theories as the congruence lattice of a semilattice with operators.

An equa-interior operator on an algebraic lattice L is a map η :L → L satisfying the following properties.

(I1) η(x)≤x

(I2) x≥y impliesη(x)≥η(y)
(I3) η^{2}(x) =η(x)

(I4) η(1) = 1

(I5) η(x) =u for all x∈X implies η(W

X) =u (I6) η(x)∨(y∧z) = (η(x)∨y)∧(η(x)∨z)

(I7) The image η(L) is the complete join subsemilattice of L generated byη(L)∩Lc.

(I8) There is a compact element w ∈ L such that η(w) = w and the interval [w,1] is isomorphic to the congruence lattice of a semilattice.

(Thus the interval [w,1] is coatomistic.)

Property (I5) means that the operationτ is implicitly defined byη,via τ(x) =_

{z∈L:η(z) =η(x)}.

Thusτ(x) is the largest elementz such thatη(z) =η(x). Likewise, proper-
ties (I1) and (I3) insure that η(x) is the least element z^{0} such that η(z^{0}) =
η(x). By (I2), if η(x)≤y ≤τ(x), then η(y) = η(x). Thus the kernel of η,
defined by x ≈ y iff η(x) = η(y), is an equivalence relation that partitions
L into disjoint intervals of the form [η(x), τ(x)]. We will refer to this as the
equa-partition of L.

Nowτ is not order-preserving in general. However, it does satisfy a weak order property that can be useful.

Lemma 13. Let L be an algebraic lattice, and assume that η satisfies con-
ditions (I1)–(I5). Define τ as above. Then for any subset{x_{j} :j∈J} ⊆L,

τ(^

j∈J

xj)≥ ^

j∈J

τ(xj).

Proof. We have

η(^

τ xj)≤^

ητ xj ≤^

xj ≤^ τ xj

and that’s all in one block of the equa-partition, whileV

xj ≤τ(V

xj), which is the top of the same block. Thus V

τ x_{j} ≤τ(V

x_{j}).

Property (I7) has some nice consequences.

Lemma 14. Let η be an equa-interior operator on an algebraic lattice L.

(1) The image η(L) is an algebraic lattice, and x is compact inη(L) iff x∈η(L) and x is compact in L.

(2) If X is up-directed, then η(W

X) =W η(X).

For any quasivarietyK, the natural equa-interior operator on the lattice of
theories of K satisfies the eight listed basic properties. Congruence lattices
of semilattices with operators come close. For an ideal I in a semilattice
with operators, let con_{SL}(I) denote the semilattice congruence generated by
collapsing all the elements ofI to 0.

Theorem 15. If S = hS,+,0,Fi is a semilattice with operators, then the
map η onCon S given by η(θ) = con_{SL}(0/θ) satisfies properties (I1)–(I7).

Proof. Property (I6) is the hard one to verify. Letα,β,γ ∈Con S and let ξ = η(α). Then x ξ y if and only if there exists z ∈S such that z α0 and x+z=y+z. (This is the semilattice congruence but it’s compatible with F.) We want to show that

(ξ∨β)∧(ξ∨γ)≤ξ∨(β∧γ).

Leta,b∈LHS. Then there exist elements such that a β c1ξ c2β c3. . . b a γ d1ξ d2γ d3. . . b.

Letz be the join of the elements witnessing the aboveξ-relations. Then a ξ a+z β c1+z=c2+z β c3+z=. . . b+z ξ b

so thata ξ a+z β b+z ξ b, and similarlya ξ a+z γ b+z ξ b. Thusa,b∈RHS,

as desired.

Property (I8), on the other hand, need not hold in the congruence lattice of a semilattice with operators. The elementwof (I8), called thepseudo-one, in lattices of quasi-equational theories corresponds to the identityx≈y. For an equa-interior operator on a latticeLwith 1 compact, we can takew= 1;

in particular, this applies when the semilattice has a top element, in which case we can take w= con(0,1). But in general, there may be no candidate for the pseudo-one.

Note that property (I8) implies that a lattice is dually atomic (orcoatomic).

Let x <1 in L. If x∨w <1 then it is below a coatom, while if x∨w= 1 then by the compactness of w there is a coatom above x that is not above w. In particular, the lattice of theories of a quasivariety is coatomic (Corol- lary 5.1.2 of Gorbunov [17]).

Consider the semilattice Ω= (ω,∨,0, p) withp(0) = 0 andp(x) =x−1 forx >0. Then ConΩ∼=ω+ 1, which has no pseudo-one (regardless of how η is defined). Thus ConΩ is not the dual of a Q-lattice. Likewise, ConΩ fails to be dually atomic.

In each of the next two sections we will discuss an additional property of the natural equa-interior operator on semilattices with operators. The point of this is that an algebraic lattice cannot be the dual of a Q-lattice unless it admits an equa-interior operator satisfying all these conditions. Indeed, we should really consider the representation problem in the context of pairs (L, η), rather than just the representation of a lattice with an unspecified equa-interior operator.

For the sake of clarity, let us agree that the term equa-interior operator refers to conditions (I1)–(I8) for the remainder of the paper, even though we are proposing that henceforth a ninth condition should be included in the definition.

6. A new property of natural equa-interior operators The next theorem gives a property of the natural equa-partition on con- gruence lattices of semilattices with operators that need not hold in all lattices with an equa-interior operator.

Theorem 16. Let S = hS,+,0,Fi be a semilattice with operators, and let η, τ denote the bounds of the natural equa-partition on ConS. If the congruences ζ, γ,χ satisfy η(ζ)≤η(γ) and τ(χ)≤τ(γ), then

η(η(ζ)∨τ(ζ∧χ))≤η(γ).

Proof. Assume thatζ,γ,χsatisfy the hypotheses, and let 0/ζ =Z, 0/γ=C and 0/χ=Xbe the corresponding ideals. SoZ⊆Candτ(X)⊆τ(C). For notation, let α=τ(Z∩X).

We want to show that 0/(η(Z)∨α)⊆C, so let w∈LHS. For anyz∈Z
we have (z, w)∈η(Z)∨α. Fix an elementz_{0} ∈Z. We claim that there exist
elements z^{∗} ∈Z and w^{∗} ∈S such thatz0≤z^{∗} ≤w^{∗},w≤w^{∗} and z^{∗}α w^{∗}.

There is a sequence

z_{0}=s_{0} η(Z) s_{1} α s_{2} η(Z) s_{3} . . . s_{k}=w.

Lettj =s0+· · ·+sj for 0≤j≤k. Thus we obtain
z_{0} =t_{0} η(Z) t_{1} α t_{2} η(Z) t_{3} . . . t_{k}
with

t_{0}≤t_{1}≤t_{2} ≤t_{3} ≤ · · · ≤t_{k}.

Put z^{0} = t1 and w^{0} =tk, so that with z0 ≤z^{0} ∈Z and w≤w^{0}. Moreover,
we may assume that kis minimal for such a sequence.

If k >2, then z^{0} =t_{1} α t_{2} η(Z) t_{3} α t_{4}. By the definition ofη(Z), there
exists u ∈ Z such that t2+u = t3+u. Joining with u yields the shorter
sequence

z^{00}=t1+u α t2+u=t3+u α t4+u . . .

contradicting the minimality of k. Thus k≤2, which yields the conclusion
of the claim with z^{∗} =t_{1} and w^{∗} =t_{2}.

Next, we claim that (z^{∗}, w^{∗}) ∈τ(X). This follows from the sequence of
implications:

f(z^{∗})∈X =⇒ f(z^{∗})∈X∩Z

=⇒ f(w^{∗})∈X∩Z

=⇒ f(w^{∗})∈X

=⇒ f(z^{∗})∈X

which hold for anyf ∈F, using theF-closure ofZ, (z^{∗}, w^{∗})∈τ(X∩Z) and
z^{∗} ≤w^{∗}.

Thus (z^{∗}, w^{∗}) ∈ τ(X) ⊆ τ(C). But z^{∗} ∈ Z ⊆ C = 0/τ(C), whence

w^{∗} ∈C andw∈C, as desired.

For an application of this condition, consider the lattice K in Figure 1.

It is straightforward to show that K has a unique equa-interior operator, with h(t) = 0 if t ≤ a and h(t) = t otherwise. Indeed, any equa-interior operator onKmust haveh(a)∨(x∧z) = (h(a)∨x)∧(h(a)∨z), from which it follows easily that h(a) = 0. But then we cannot have h(x) = 0, else h(1) = h(a∨x) = 0, a contradiction. Thus h(x) = x and symmetrically h(z) =z. This in turn yields thath(c) =c.

ButK is not the congruence lattice of a semilattice with operators. The only candidate for the equa-interior operator fails the condition of Theo- rem 16 with the substitution ζ 7→z, γ 7→c,χ7→x. ThereforeKis not the lattice of theories of a quasivariety. We could have also derived this latter fact by noting thatKis not dually biatomic: inKwe havea≥x∧z which is not refinable to a meet of coatoms.

a c

x z

Figure 1. K

1

Figure 1. K

On the other hand, K can be represented as a filterable sublattice of
Con(B3,+,0), whereB3 is the Boolean lattice on three atoms. (See Appen-
dix II for this terminology.) Indeed, if the atoms of B_{3} are p, q,r then we
can take

a7→[0] [p, q, r, p∨q, p∨r, q∨r,1]

c7→con(0, p∨q) x7→con(0, p) z7→con(0, q).

We will pursue the comparison of congruence lattices and lattices of algebraic sets in the appendices.

Taking a cue from this example, we continue investigating the conse- quences of the condition of Theorem 16. Recall that, whenever η satisfies (I1)–(I5), we have η(y) = η(x) iff η(x) ≤y ≤ τ(x). The condition can be written as follows, where we use the fact thatη(u)≤ciff η(u)≤η(c).

(†) τ(x)≤τ(c) &η(z)≤c =⇒ η(η(z)∨τ(x∧z))≤c

This holds for the natural equa-interior operator on congruence lattices of semilattices with operators, and we want to see how it applies to pairs (L, h) whereh is an arbitrary equa-interior operator onL.

There is a two-variable version of the condition, which is obtained by puttingc=η(z)∨τ(x).

(‡) η(η(z)∨τ(x∧z))≤η(z)∨τ(x) This appears to be slightly weaker than (†).

Consider the Boolean latticeB_{3} with atomsx,y,z and the equa-interior
operator withh(y) = 0 andh(t) =totherwise. Then (B3, h) fails the condi-
tion (‡), thoughB_{3} is a dual Q-lattice with another equa-interior operator
by Theorem 1.

There are two additional conditions on equa-interior operators that are known to hold in the duals ofQ-lattices: bicoatomicity and the four-coatom condition. (See Section 5.3 of Gorbunov [17].) Unfortunately, congruence lattices of semilattices with operators need not be coatomic (there is an example in the discussion of property (I8) in Section 5), but duals of Q- lattices are, so we will impose this as an extra condition. In that case, we will see that (†) implies both of these properties.

A lattice L is bicoatomic (or dually biatomic) if whenever p is a coatom ofL and p≥u∧v properly, then there exist coatomsc≥u andd≥v such thatp≥c∧d.

Theorem 17. Let L be a coatomic lattice and let h be an equa-interior operator on L. If (L, h) satisfies property(†), then L is bicoatomic.

Proof. Assume 1p≥u∧v properly in L. We want to find elementsc, z with 1c≥u, z≥v, andc∧z ≤p. (Then apply the argument a second time.)

Note that p≥η(p)∨(u∧v) = (η(p)∨u)∧(η(p)∨v). Putx =η(p)∨u and z=η(p)∨v. Let 1c≥τ(x) and noteτ(x)≥x≥u.

Supposec∧zp. Putz^{0}=c∧z. Thenη(z^{0})p, for else sinceη(p)≤z^{0}
we would have η(z^{0}) =η(p) =η(z^{0}∨p) = η(1) = 1, a contradiction. Now
we apply (†). Surely τ(x) ≤ c and η(z^{0}) ≤ z^{0} ≤ c. Moreover η(p) ≤
z^{0} ∧x ≤z∧x ≤ p whence η(z^{0}∧x) = η(p), and thus τ(z^{0}∧x) = p. But
then η(η(z^{0})∨τ(x∧z^{0})) = η(η(z^{0})∨p) = η(1) = 1, again a contradiction.

Thereforec∧z≤p, as desired.

The dual of the four-coatom condition played a significant role in the characterization of the atomistic, algebraic Q-lattices. This too is a conse- quence of property (†). For coatoms a, d we write a ∼ d to indicate that

| ↑(a∧d)|= 4, in which case the filter↑(a∧d) is exactly{1, a, d, a∧d}. A latticeLwith an equa-interior operatorηsatisfies thefour-coatom condition if, whenever a,b, c,dare coatoms of L such thata∼d,η(a)d,η(c)≤d and η(c) =η(a∧b), then η(c) =η(b∧d).

Theorem 18. The four-coatom condition holds in a lattice with an equa- interior operator η satisfying (†).

Proof. As η(c) ≤ b, d is given, we need that η(b∧d) ≤ c. Supposing not, substitute x = a∧d, z = η(b∧d), and the element d into (†). Note that τ(a∧d) 6= a has η(a) d. Thus τ(a∧d) ≤ d, and of course η(b∧d) ≤ d. But we also have η(c) ≤ a∧b ∧d ≤ a∧b and η(a∧b) = η(c), so η(η(b∧d)∨τ(a∧b∧d)) =η(η(b∧d)∨c) =η(1) = 1, a contradiction. Thus

η(b∧d)≤c, as desired.

7. Coatomistic congruence lattices and a stronger property One of the most intriguing hypotheses about lattices of quasivarieties is formulated for atomistic lattices. Dually, it can be expressed as follows:

Can every coatomistic lattice of quasi-equational theories be represented as Con(S,+,0), i.e., without operators?

This hypothesis is shown to be valid in the case when the lattice of quasi- equational theories is dually algebraic [3]. The problem provides a mo- tivation for investigating which coatomistic lattices can be represented as lattices of equational theories, or congruence lattices of semilattices, with or without operators.

Consider the class Mof lattices dual to Sub_{f} M, whereM is an infinite
semilattice with 0, and Subf Mis the lattice of finite subsemilattices ofM,
topped by the semilattice Mitself.

Evidently, lattices inM are coatomistic, and they are algebraic but not
dually algebraic. Besides, it is straightforward to show that they cannot be
presented as Con(S,+,0). Thus, it would be natural to ask whether such
lattices can be presented as Con(S,+,0,F), for a non-empty set of operators
on S. In many cases the answer is “no” simply because there might be no
equa-interior operator. For example, letM be a meet semilattice such that
the dual of Sub_{f} M admits an equa-interior operator. If ais an element of
M that can be expressed as a meet in infinitely many ways, then η(a) = 0
by Lemma 22 below. HenceM can contain at most one such element.

It turns out to be feasible to show that certain lattices fromM, thatdoad- mit an equa-interior operator, still cannot be represented as Con(S,+,0,F).

The crucial factor here is to understand the behavior of infinite meets of coatoms, or more generally infinite meets of elementsτ(x), in the congruence lattice of a semilattice with operators. The restriction given by Theorem 19 can be expressed as a ninth basic property of the natural equa-interior op- erator (as it implies (†)).

Aside: Coatoms arise naturally in another context, that does not make the lattice coatomistic. Suppose S =hS,+,0,Fi has the property that for each F-closed ideal I, everyf ∈F, and everyx∈S,

f(x)∈I =⇒ x∈I.

Then the congruence τ(I) partitions S into I and S −I, and hence is a coatom. In particular, this property holds whenever

• Fis empty, or

• Fis a group, or

• everyf ∈Fis increasing, i.e.,x≤f(x) for all x∈S.

In all these cases,τ(θ) is a coatom for everyθ∈ConS. We will be partic- ularly concerned with the case whenF is a group in Part II [7].

Theorem 19. Let S = hS,+,0,Fi be a semilattice with operators, I an
arbitrary index set, andχ,γ, andζ_{i} fori∈I congruences onS. The natural
equa-interior operator onConShas the following property: if η(χ)≤γ and
V

i∈Iτ(ζ_{i})≤τ(γ), then

η(η(χ)∨^

i∈I

τ(χ∧ζ_{i}))≤γ.

For the proof, it is useful to write down abstractly the two parts of the argument of the proof of Theorem 16.

Lemma 20. Let α, χ, ζ ∈Con(S,+,0,F) and let X be the 0-class of χ.

(1) If u ∈X and (u, v) ∈χ∨α, then there exist elements u^{∗}, v^{∗} with
u≤u^{∗} ∈X, v≤v^{∗}, u^{∗} ≤v^{∗}, and(u^{∗}, v^{∗})∈α.

(2) If u∈X, u≤v and (u, v)∈τ(χ∧ζ), then (u, v)∈τ(ζ).

Now, under the assumptions of the theorem, letu∈X and (u, v)∈η(χ)∨
Vτ(χ∧ζ_{i}), so thatvis in the 0-class of the LHS. Then by Lemma 20(1), there
exist u^{∗}, v^{∗} with u ≤u^{∗} ∈ X, v ≤ v^{∗}, u^{∗} ≤ v^{∗} and (u^{∗}, v^{∗}) ∈ V

τ(χ∧ζi).

Then (u^{∗}, v^{∗})∈τ(χ∧ζi) for everyi, whence by Lemma 20(2) (u^{∗}, v^{∗})∈τ(ζi)
for everyi, so that (u^{∗}, v^{∗})∈V

τ(ζ_{i}).

LetXandCdenote the 0-classes ofχandγ, respectively. By assumption,
we have u^{∗} ∈ X ⊆C, and (u^{∗}, v^{∗}) ∈V

τ(ζ_{i}) ≤ τ(γ), so v^{∗} ∈ C as well. A
fortiori,v∈C, as desired.

This proves Theorem 19. Thus we obtain the ninth fundamental prop- erty of the natural equa-interior operator on the congruence lattice of a semilattice with operators.

(I9) For any index set I, if η(x) ≤ c and V

τ(zi) ≤τ(c), then η(η(x)∨ V

i∈Iτ(x∧z_{i}))≤c.

As before, there is also a slightly simpler (and weaker) variation:

(I9^{0}) η(η(x)∨^

i∈I

τ(x∧zi))≤η(x)∨^ τ(zi).

Clearly, if|I|= 1 then property (I9) reduces to property (†). In fact, for I finite, (†) implies (I9). But for I infinite, property (I9) seems to carry a rather different sort of information, as we shall see below.

Consider the case when |I|= 2; the argument for the general finite case is similar. Assume that η(x) ≤ c and τ(y)∧τ(z) ≤ τ(c). Using (I6), (†), and the fact that η(u∧v) =η(η(u)∧η(v)), we calculate

η(η(x)∨(τ(x∧y)∧τ(x∧z))) =η((η(x)∨(τ(x∧y))∧(η(x)∨τ(x∧z))))

≤η((η(x)∨(τ(y))∧(η(x)∨τ(z))))

=η(η(x)∨(τ(y)∧τ(z)))

≤c as desired.

With property (I9) as a tool-in-hand, we turn to a thorough investiga- tion of the (dual) dependence relation for coatoms of Con(S,+,0,F); see Theorems 23 and 24 below. Throughout the remainder of this section, χ, ζ andα will denote distinct coatoms of the congruence lattice. Repeatedly, we use the basic property of equa-interior operators that ηx∨(y∧z) = (ηx∨y)∧(ηx∨z). Our goal is to generalize (to whatever extent possible) the following property of finite sets of coatoms.

Theorem 21. Let L be a lattice with an equa-interior operator. If for
coatoms x, z_{1}, . . . , z_{k}, a_{1}, . . . , a_{k} of L we have x ∧z_{i} ≤ a_{i} properly, then
ηx∨Vk

i=1zi= 1.

The proof uses the next lemma.

Lemma 22. Suppose x∧z ≤ a properly for coatoms in a lattice with an equa-interior operator. Then ηa≤x∧z, and thus

(1) τ(x∧z) =a, (2) ηxa, (3) ηxz.

Proof. If sayηax, thenηa∨x= 1, and using (I6) we would have ηa∨z= (ηa∨x)∧(ηa∨z)

=ηa∨(x∧z)≤a

whencez≤a, a contradiction. Soηa≤x, and symmetrically ηa≤z. Since ηa≤x∧z≤a=τ a, we have τ(x∧z) =a.

It follows that we cannot haveηx≤a, else ηa=η(x∧z)≤ηx≤a,

implying that ηx=ηa, and thusηa=η(x∨a) =η1 = 1 by (I5) and (I4), a contradiction. Therefore alsoηxz, elseηx≤x∧z≤a.

The theorem now follows immediately, because ηx∨

k

^

i=1

z_{i}=

k

^

i=1

(ηx∨z_{i}) = 1.

The property of Theorem 21 can fail when there are infinitely many z_{i}’s,
even in the congruence lattice of a semilattice. LetQbe the join semilattice
in Figure 2. Consider the ideals

X ={0, u1, u2, u3, . . .} Zi =↓vi

A_{i} =↓u_{i}

for i ∈ ω, and let χ = τ(X), ζ_{i} = τ(Z_{i}) and α_{i} = τ(A_{i}). Then an easy
calculation shows thatV

ζi = 0, and the infinite version of the property of the theorem fails.

Nonetheless, we shall show that a couple of infinite versions do hold.

Theorem 23. Let L be a lattice with an equa-interior operator satisfying property (I9). If for coatoms a, x and zi (i∈ I) of L we have x∧zi ≤a properly, then ηx∨V

i∈Iz_{i} = 1.

Proof. By Lemma 22, we haveτ(x∧zi) =afor everyi, and ηxa. Hence ηx∨V

τ(x∧z_{i}) = 1. Then property (I9^{0}) gives the conclusion immediately.

0 1

v_{3} v_{2} v_{1}

u1

u_{2}
u_{3}

1

Figure 2. Con(S,+,0) does not satisfy the infinite analogue of Theorem 21.

Theorem 24. Let L be a lattice with an equa-interior operator satisfying
property (I9). Let x, a_{i} andz_{i} be coatoms of L withx∧z_{i} ≤a_{i} properly for
alli∈I. If V

i∈Iaix, then V

i∈Izi x.

Proof. Again, by Lemma 22, we haveτ(x∧zi) =ai for every i. Now apply

(I9) directly withc=x.

Let us now use these results to show that certain coatomistic lattices are
not lattices of quasi-equational theories. Call an infinite (∧)-semilattice M
cute if it has an element aand different elements m, mj ∈M\{a}, j ∈ ω,
withm∧m_{j} =a.

Examples of cute semilattices are M∞: countably manymi covering the
least element a, or M2: a chain {mj, j ∈ ω} in addition to elements m, a,
satisfyingm∧m_{j} =afor allj. It was asked in [2] (p. 175), in connection with
the hypothesis about the atomistic Q-lattices mentioned above in the dual
form, whether Sub_{f} M∞is aQ-lattice. The following result, an immediate
application of Theorem 23, answers this question in the negative.

Theorem 25. If Mis a cute semilattice, then the dual of Sub_{f} M is not
representable as Con(S,+,0,F). HenceSub_{f} M is not a Q-lattice.

It would be desirable to extend Theorem 25 to all lattices from M. In
particular, we may ask about possibility to representL= (Subf P1)^{d}, where
the semilattice P_{1} consists of two descending chains{b_{i}, i∈ω}, {a_{i}, i∈ω}

with defining relations ai+1=ai∧bi+1,b0> a0.

Every equa-interior operator η on L would satisfy: η({a_{i}}) = [a_{i}, b_{0}],
η({bi})≥[bi, b0]. In particular,η(c) = 0, c∈L, impliesc= 0 (equivalently,

τ(0) = 0). This makesP1 drastically different from cute semilattices. Is the
dual of Sub_{f} P_{1} representable as Con(S,+,0,F)?

Another interesting case to consider would be Subf C where C is an infinite chain, so that every finite subset of C is a subsemilattice.

8. Appendix I: Complete sublattices of subalgebras In the first two appendices, we analyze conditions that were used in older descriptions of lattices of quasivarieties; see Gorbunov [17].

Note that Con(S,+,0,F) is a complete sublattice of Con(S,+,0), which is dually isomorphic to Sp(I(S)), which is the lattice of subalgebras of an infinitary algebra. (Joins of non-directed sets can be set to 1.) In this context we are considering complete sublattices of SubA where A is a semilattice, or a complete semilattice, or a complete algebra of algebraic subsets.

Let ε be a binary relation on a set S. A subset X ⊆ S is said to be ε-closed ifc∈X and c ε dimpliesd∈X.

Recall that a quasi-orderεon a semilatticeS=hS,∧,1iis distributive if it satisfies the following conditions.

(1) If c1 ∧c2ε d then there exist elements d1, d2 such that ciε di and
d=d_{1}∧d_{2}.

(2) If 1ε dthend= 1.

The effect of the next result is that for a semilattice S, any complete sublattice of Sub Scan be represented as the lattice of allρ-closed subsemi- lattices, for some distributive quasi-order ρ.

Theorem 26. Let S = hS,∧,1i be a semilattice with 1, and let ε be a distributive quasi-order on S. Then Sub (S, ε), the lattice of all ε-closed subsemilattices (with 1), is a complete sublattice of Sub S.

Conversely, letTbe a complete sublattice of SubS. Define a relationρon Sbyc ρ dif for allX∈Twe havec∈X =⇒ d∈X. Thenρis a distributive quasi-order, and T consists precisely of the ρ-closed subsemilattices of S.

Furthermore, ρ satisfies the following conditions.

(3) If c ρ d1, d2 thenc ρ d1∧d2. (4) For allc∈S,c ρ1.

The correspondence between complete sublattices of Sub S and distribu- tive quasi-orders satisfying (3) and (4) is a dual isomorphism.

The proof is relatively straightforward.

The description of all complete sublattices of SubS, the lattice of all complete subsemilattices of a complete semilattice S, is almost identical, except that complete meets appear in the conditions.

(1)^{0} IfV

ciε dthen there exist elementsdi such thatciε di andd=V
di.
(3)^{0} Ifc ε ci for alli, thenc ε V

ci.

Complete semilattices satisfying (1)^{0}are calledBrouwerianby Gorbunov [17].

The results can be summarized thusly.

Theorem 27. Let S = hS,∧,1i be a complete semilattice. Then there is
a dual isomorphism between complete sublattices of SubS and quasi-orders
satisfying conditions (1)^{0}, (2), (3)^{0} and (4).

For complete sublattices of Sp(A), the lattice of algebraic subsets of an algebraic lattice A, we must also deal with joins of nonempty up-directed subsets, and onceA fails the ACC matters get more complicated. A quasi- order εon Ais said to be continuous if it has the following property.

(5) If C is a directed set andW

C ε d, then there exists a directed setD such thatd=W

Dand for each d∈D there existsc∈C withc ε d.

This is a very slight weakening of Gorbunov’s definition [17]. As above, we have this result of Gorbunov.

Theorem 28. Letεbe a continuous Brouwerian quasi-order on a complete latticeA. ThenSp(A), the lattice ofε-closed algebraic subsets, is a complete sublattice of Sp(A).

Now for any algebraBwe can define the embedding relation E on Con B by θ E ψ if B/ψ ≤ B/θ. A fundamental result of Gorbunov characterizes Q-lattices in terms of the embedding relations (Corollaries 5.2.2 and 5.6.8 of [17]).

Theorem 29. Let K be a quasivariety and let F=F_{K}(ω). The embedding
relation is a continuous Brouwerian quasi-order on Con_{K} F, and Lq(K) ∼=
Sp(Con_{K}(F, E)).

For comparison, we note that the isomorphism relation need not be con- tinuous; see Gorbunov [17], Example 5.6.6.

We do not know (and doubt) that the relationρ corresponding to a com- plete sublattice of Sp(A) need always be continuous. However, our repre- sentation of Con(S,+,0,F) as dually isomorphic to a complete sublattice of Sp(I(S)) could be unraveled to give the ρ relation explicitly in that case.

Are these particular relations always continuous?

9. Appendix II: Filterability and equaclosure operators
The natural equational closure operator on L_{q}(K) is given by the map
h(Q) = H(Q)∩K for quasivarieties Q ⊆ K. That is, h(Q) consists of all
members of K that are in the variety generated by Q, or equivalently, that
are homomorphic images of F_{Q}(X) for some set X. For the corresponding
map on Sp(ConF_{K}(ω)), letX be the algebraic subset of allQ-congruences
of ConF_{K}(ω). Thenϕ=V

Xis the natural congruence withF/ϕ∼=F_{Q}(ω),
and the filter ↑ϕ is the algebraic subset associated with h(Q), that is, all
h(Q)-congruences of ConF_{K}(ω).

Abstractly, let ε be a distributive quasi-order on an algebraic lattice A.

Then it is not hard to see that the map h(X) =↑V

X on Sp(A, ε) will satisfy the duals of conditions (I1)–(I7) so long as↑V

Xisε-closed for every

X∈Sp(A, ε). A quasi-order that satisfies this crucial condition, c≥^

X &c ε d =⇒ d≥^ X

is said to befilterable. If the quasi-orderεis filterable, then the closure op- eratorh(X) =↑V

X on Sp(A, ε) is again called thenatural closure operator determined by ε. We can also speak of a complete sublattice of Sp(A) as being filterable if the quasi-order it inducesvia Theorem 26 is so.

Dually, a sublattice T ≤ Con(S,+,0) is filterable if, for each θ ∈ T, the semilattice congruence generated by the 0-class ofθis inT. As we have observed, this is the case whenT= Con(S,+,0,F) for some set of operators F. Thus we obtain a slightly different perspective on Theorem 15.

Theorem 30. For a semilattice S with operators,T= Con(S,+,0,F) is a filterable complete sublattice of Con(S,+,0). Thus T supports the natural interior operator h(θ) = con(0/θ), which satisfies conditions (I1)–(I7).

In fact, the natural interior operator on Con(S,+,0,F) also satisfies con- dition (I9). However, as we saw in Section 6, a filterable sublattice of Con(S,+,0) may fail condition (†), which is the finite index case of (I9), even with S finite. Thus being a congruence lattice of a semilattice with operators is a stronger property than just being a filterable sublattice of Con(S,+,0).

10. Appendix III: Lattices of equational theories

In this appendix, we summarize what is known about lattices of equational theories. Throughout the section,Vwill denote a variety of algebras, with no relation symbols in the signature. For this situation, atomic theories really are equational theories. The lattice of equational theories is, of course, dual to the lattice of subvarieties of V.

From the basic representation ATh(V) ∼= FiconF_{V}(ω), we see that the
lattice is algebraic. Its top element 1 has the basis x ≈ y, and thus 1 is
compact. On the other hand, J. Jeˇzek proved that any algebraic lattice
with countably many compact elements is isomorphic to an interval in some
lattice of equational theories [24].

R. McKenzie showed that every lattice of equational theories is isomorphic to the congruence lattice of a groupoid with left unit and right zero [28].

N. Newrly refined these ideas, showing that a lattice of equational theories is isomorphic to the congruence lattice of a monoid with a right zero and one additional unary operation [29]. A. Nurakunov added a second unary operation and proved a converse: a lattice is a lattice of equational theories if and only if it is the congruence lattice of a monoid with a right zero and two unary operations satisfying certain properties [31].

Nurakunov’s conditions are rather technical, but they just codify the prop-
erties of the natural operations on the free algebraF_{V}(X) that they model.

IfX ={x_{0}, x_{1}, x_{2}, . . .} and s,t are terms, then
s·t=t(s, x1, x2, . . .).