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,FA,RAi where A is the carrier set,FA is the set of operations on A, and RA 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(RA) ⊆RB 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κR1 whereκR1 =h−1(RB) ={s∈Aρ(R):h(s)∈RB}.
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,FA,RAiis a pairθ=hθ0, θ1iwhere
• θ0 is an equivalence relation onAthat is compatible with the oper- ations ofFA, and
• θ1 =S
R∈RθR1 where eachθ1R⊆Aρ(R)andRA ⊆θR1, i.e., the original relations ofA are contained in those of θ1, and for each R ∈ R, if a∈θ1R andb∈Aρ(R) and aθ0b componentwise, thenb∈θR1. 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,FS,RSi where S is a subuniverse of A, for each operation symbol f ∈ F the operation fS is the restriction of fA to Sρ(f), and for each relation symbolR∈Fthe relation RS is RA∩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 θ0b impliesε(a)θ0ε(b), and
• for eachR∈R,a∈θR1 impliesε(a)∈θR1.
The lattice of fully invariant congruences is denoted Ficon A.
The congruence generation theorems are straightforward to generalize.
Let C ⊆ A2 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 ∈ θ1R 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∪RA with respect to θ0, i.e., if R(a)∈D andaθ0b componentwise, thenb∈θR1.
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 ConK A. Moreover, ConK 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 Lv(V). Likewise, for a quasivarietyK, let QTh(K) denote the lattice of quasi- equational theories containing the theory ofK, so that QTh(K)∼=dLq(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 = FK(ω) be the countably generated K-free struc- ture. Then ConK F denotes the lattice of allK-congruences ofF.
• Define the isomorphism relation I and embedding relation E on ConK 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(ConK F, I)∼= Sp(ConK 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 Lv(V) ∼=d FiconF reflects equational logic, whereas the representation Lq(K) ∼= Sp(ConK 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 Lq(K)∼=dCon 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)∼=dCon Lc.
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=FK(ω) be theK-free algebra onω gener- ators, and let ConK F be the lattice ofK-congruences of F. For a set S of atomic formulae, recall that the K-congruence generated by S is
conK S=\
{ψ∈Con F:F/ψ∈K and S ⊆ψ}.
Then let T = TK denote the join semilattice of compact K-congruences in ConK F. Thus T = (ConK FK(ω))c consists of finite joins of the form W
jϕj, with each ϕj either conK(s, t) or conK R(s) for terms s, t, si ∈ F and a relation R.
Let X be a free generating set for FK(ω). 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ε(conK(s, t)) = conK(εs, εt)
ε(conb K R(s)) = conK 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 ConK F, conK α≤_
conK β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∈θR1. 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=SK=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,
Lq(K)∼=dConS
where S = hT,∨,0,bEi with T the semilattice of compact congruences of ConK F, E= EndF, and F=FK(ω).
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 Sn, where Sn = hTn,∨,0,bEi with Tn the semilattice of compact congruences of ConK F, E= EndF, and F=FK(n).
We shall prove Theorem 5, and afterwards discuss the modification re- quired for Theorem 6, which is essentially just replacing FK(ω) by FK(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 T2 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 (β, γ) ∈T2 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⊆T2 let κ(X) ={A∈K: (β, γ) ΞA for all (β, γ)∈X}.
Likewise, forY ⊆K, let
∆(Y) ={(β, γ)∈T2 : (β, γ) ΞA for allA∈Y}.
We must check that the following hold forX⊆T2 and Y ⊆K. (1) κ(X)∈Lq(K),
(2) ∆(Y)∈DonS,
(3) ∆κ(X) =X ifX ∈DonS, (4) κ∆(Y) =Y ifY ∈Lq(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
iAi then kerh = T
kerπih. So let Ai ∈ κ(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
Ai such thath=gf whereg:Q
Ai→Q Ai/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 conK α 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 :πif(αj)} ∈U. Taking the intersection, {i∈I :∀j πif(α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)⊆T2is 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
conK α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
conK αj and γ = conK ζ, 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 (µ, ν)∈T2−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 mapf0 :ω→Cextends to a homomorphismf :FK(ω)→C, and
(2)0 Every mapg0:n→Cextends to a homomorphismg:FC(ω)→C.
Quasivarieties satisfying conditions (1) and (2) are closed under arbitrary joins, and thus under containment they form a lattice which we will denote byLnq(K). This is a complete join subsemilattice ofLq(K); the correspond- ing dual lattice of theories is a complete meet subsemilattice QThn(K) of QTh(K). The proof of Theorem 5 gives us QTh(K) as the congruence lattice of a semilattice with operators obtained from FK(ω). In view of condition (2)0, the same construction withFK(ω) replaced throughout byFK(n) yields QThn(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 ConK F of principal congruences, say β = W
conK αj and γ = W
conK ζ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
conK αj
and γ = W
conK ζ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 ConK F, E= EndF, and F=FK(ω).
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 ⊆ T2, 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 FK(ω). 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 z0 such that η(z0) = η(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{xj :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
τ xj ≤τ(V
xj).
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 conSL(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 η(θ) = conSL(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 elementz0 ∈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
z0=s0 η(Z) s1 α s2 η(Z) s3 . . . sk=w.
Lettj =s0+· · ·+sj for 0≤j≤k. Thus we obtain z0 =t0 η(Z) t1 α t2 η(Z) t3 . . . tk with
t0≤t1≤t2 ≤t3 ≤ · · · ≤tk.
Put z0 = t1 and w0 =tk, so that with z0 ≤z0 ∈Z and w≤w0. Moreover, we may assume that kis minimal for such a sequence.
If k >2, then z0 =t1 α t2 η(Z) t3 α t4. By the definition ofη(Z), there exists u ∈ Z such that t2+u = t3+u. Joining with u yields the shorter sequence
z00=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∗ =t1 and w∗ =t2.
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 B3 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 latticeB3 with atomsx,y,z and the equa-interior operator withh(y) = 0 andh(t) =totherwise. Then (B3, h) fails the condi- tion (‡), thoughB3 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. Putz0=c∧z. Thenη(z0)p, for else sinceη(p)≤z0 we would have η(z0) =η(p) =η(z0∨p) = η(1) = 1, a contradiction. Now we apply (†). Surely τ(x) ≤ c and η(z0) ≤ z0 ≤ c. Moreover η(p) ≤ z0 ∧x ≤z∧x ≤ p whence η(z0∧x) = η(p), and thus τ(z0∧x) = p. But then η(η(z0)∨τ(x∧z0)) = η(η(z0)∨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 Subf 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 Subf 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∧zi))≤c.
As before, there is also a slightly simpler (and weaker) variation:
(I90) η(η(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, z1, . . . , zk, a1, . . . , ak of L we have x ∧zi ≤ ai 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
zi=
k
^
i=1
(ηx∨zi) = 1.
The property of Theorem 21 can fail when there are infinitely many zi’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
Ai =↓ui
for i ∈ ω, and let χ = τ(X), ζi = τ(Zi) and αi = τ(Ai). 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∈Izi = 1.
Proof. By Lemma 22, we haveτ(x∧zi) =afor everyi, and ηxa. Hence ηx∨V
τ(x∧zi) = 1. Then property (I90) gives the conclusion immediately.
0 1
v3 v2 v1
u1
u2 u3
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, ai andzi be coatoms of L withx∧zi ≤ai 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∧mj =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∧mj =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 Subf 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 Subf M is not representable as Con(S,+,0,F). HenceSubf 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 P1 consists of two descending chains{bi, i∈ω}, {ai, i∈ω}
with defining relations ai+1=ai∧bi+1,b0> a0.
Every equa-interior operator η on L would satisfy: η({ai}) = [ai, b0], η({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 Subf P1 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=d1∧d2.
(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)0are 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=FK(ω). The embedding relation is a continuous Brouwerian quasi-order on ConK F, and Lq(K) ∼= Sp(ConK(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 Lq(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 FQ(X) for some set X. For the corresponding map on Sp(ConFK(ω)), letX be the algebraic subset of allQ-congruences of ConFK(ω). Thenϕ=V
Xis the natural congruence withF/ϕ∼=FQ(ω), and the filter ↑ϕ is the algebraic subset associated with h(Q), that is, all h(Q)-congruences of ConFK(ω).
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) ∼= FiconFV(ω), 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 algebraFV(X) that they model.
IfX ={x0, x1, x2, . . .} and s,t are terms, then s·t=t(s, x1, x2, . . .).
