EMBEDDING FINITE LATTICES INTO 5 FINITE BIATOMIC LATTICES 0 0 2 KIRAADARICHEVAANDFRIEDRICHWEHRUNG n a Abstract. For a class C of finite lattices, the question arises whether any J lattice in C can be embedded into some atomistic, biatomic lattice in C. We 2 provideanswerstothequestionaboveforCbeing,respectively, 2 — Theclassofallfinitelattices; — Theclassofallfinitelowerbounded lattices(solvedbythefirstauthor’s ] earlierwork). M — The class of all finite join-semidistributive lattices (this problem was, G untilnow,open). Wesolvethelatterproblembyfindingaquasi-identityvalidinallfinite,atom- h. istic, biatomic, join-semidistributivelattices but not inallfinite join-semidis- t tributivelattices. a m [ 1 1. Introduction v 4 A lattice L is biatomic, if it is atomic (i.e., every element of L\{0} lies above 6 someatomofL)andwheneverp,a,andbareelementsofLsuchthatpisanatom, 3 a and b are nonzero, and p ≤ a∨b, there are atoms x ≤ a and y ≤ b such that 1 p≤x∨y, see Definition 2.1. 0 5 Inourfirstresultofthispaper,Theorem2.3,weprovethatanyfinitelatticecan 0 be easily embedded atom-preservingly into a finite biatomic one. / Biatomicity arises naturally in geometric lattices such as lattices of subspaces h t of a vector space or, more generally, projective geometries. It was also noticed by a M.K.Bennett[4]thatingeometriclattices,biatomicityisequivalenttomodularity. m Biatomicity is probably even more common among convex geometries. The lat- : v tice theoreticalfacetofthese atfirstfinite andpurely combinatorialstructureswas i studied in P.H. Edelman [6] and P.H. Edelman and R. Jamison [7]. In [3], these X structures, now generalized to the infinite case, were considered as an antithesis of r a geometric lattices, in terms of the properties of the closure operators that define them. We mention the lattices of convex subsets of a given affine space and the lattice of subsemilattices of a givenmeet-semilattice as a few examples of biatomic convex geometries. Still,notallconvexgeometriesarebiatomic,thustodescribethebiatomicmem- bers within a given class of such structures would be of great interest. Date:February1,2008. 2000 Mathematics Subject Classification. Primary06B99, 05B25, 51E99. Secondary: 51E30, 51D20,05C20. Key words and phrases. Lattice, atomistic, biatomic, join-semidistributive, lower bounded, convexgeometry,congruence extensionproperty. ThesecondauthorwaspartiallysupportedbytheFundofMobilityoftheCharlesUniversity (Prague),byFRVSgrantno. 2125,andbyinstitutionalgrant CEZ:J13/98:113200007. 1 2 K.V.ADARICHEVAANDF.WEHRUNG Convex geometries are closely connected with the class of join-semidistributive lattices. A lattice L is called join-semidistributive, if x∨y =x∨z implies that x∨y =x∨(y∧z), for all x, y, z ∈L. It is proved in [3] that every finite join-semidistributive lattice can be embedded, inan atom-preservingway,into a finite, atomistic,join-semidistributive lattice, or, equivalently, into a finite atomistic convex geometry. This convex geometry is not generally biatomic. The other constructionin [3] embeds any finite join-semidistributive lattice into the lattice S (A) of algebraic subsets of some (generally infinite) algebraic and p dually algebraic lattice A. This is also a convex geometry with the additional properties that it is atomistic, biatomic, and join-semidistributive. This, together with [3, Theorem 1.4], implies that every join-semidistributive lattice L can be embedded into an atomistic, biatomic, join-semidistributive lattice L′, see also the proof of [3, Theorem 3.26]. It is asked in Problem 4 of [3] whether L′ can be taken to be finite whenever L is finite. In the present paper, we solve this problem in the negative, by showing a quasi-identity θ that is satisfied by all finite, atomistic, biatomic, join-semidis- tributive lattices but not by all finite atomistic join-semidistributive lattices, see Theorem 7.1. This result is inspired by a geometrical example of finite convex geometry that in general produces non-biatomic join-semidistributive lattices. In contrast with this, we prove that every finite atomistic join-semidistributive latticeLcanbeh∨,∧,0,1i-embedded,inanatom-preservingwayandwiththecon- gruence extension property, into a finite, atomistic, join-semidistributive lattice L′ ′ such that all biatomicity problems of L can be solved in L, see Theorem 6.1. We also study the case of finite lower bounded lattices, an important subclass of join-semidistributive lattices. The first author’s earlier work [1] provides an embedding of any finite lower bounded lattice into some finite biatomic convex geometry, which implies Corollary 4.2 (see also Theorem 6.1). Still, we do not know whether such an embedding can be done atom-preservingly. This contributes to the list of open problems that concludes the paper. 2. Biatomic lattices ForalatticeLwithzero(i.e.,leastelement),wedenotebyAtLthesetofatoms ofL. The followingdefinitionrecallsclassicalnotions,relatedto theircounterparts in [4]. Definition 2.1. A lattice L with zero is • atomic, if every element of L is above an atom of L; • atomistic, if every element of L is a join of atoms of L; • biatomic, ifLisatomicandforeveryatompofLandallnonzeroa,b∈L, if p≤a∨b, then there are atoms x≤a and y ≤b such that p≤x∨y. We observe that every finite lattice is atomic, and L is atomistic iff for all a, b ∈ L such that a (cid:2) b, there exists p ∈ AtL such that p ≤ a and p (cid:2) b. The following lemma is trivial. Lemma 2.2. Let L be an atomic lattice. Then L is biatomic iff for every atom p of L and all a, b ∈ L\{0} such that p (cid:2) a, p (cid:2) b, and p ≤ a∨b, there exists an atom q ≤a of L such that p≤q∨b. FINITE BIATOMIC LATTICES 3 Foralattice Lwithzeroandx∈L,letat(x)bethe statementthatxisanatom of L. We can prove right away the following easy embedding result. Theorem 2.3. Let L be a finite lattice. Then L has a h∨,∧,0,1,ati-embedding into some finite, atomistic, biatomic lattice M. Proof. Put A = L\({0}∪AtL). For each a ∈ A, let p and q be new distinct a a elements, and put M =L∪{p |a∈A}∪{q |a∈A}. a a We define a partial orderingon M, extending the partial orderingof L, by making all the elements of {p | a ∈ A}∪{q | a ∈ A} mutually incomparable, and by a a saying that x≤p iff x≤q iff x=0, a a p ≤x iff q ≤x iff a≤x, a a for all a ∈ A and x ∈ L. Then it is straightforward to verify that ≤ is a lattice ordering on M and that the inclusion map from L into M is a h∨,∧,0,1,ati- embedding. Since a=p ∨q for all a∈A, the lattice M is atomistic. a a ToprovethatM isbiatomic,itisconvenienttouseLemma2.2. Soletp∈AtM, let a, b ∈ M such that p (cid:2) a, p (cid:2) b, and p ≤ a∨b (in particular, a and b are incomparable,thus they arenonzero),wefind anatomq ofM suchthatq ≤a and p ≤ q∨b. If a is an atom of M then q = a works, so suppose from now on that a ∈ A. If b ∈ L, then p ≤ a∨b = p ∨b, thus q = p is as required. If b ∈/ L, say, a a b=pc for some c∈A such that c(cid:2)a, then p≤a∨pc =a∨c=pa∨pc, so q =pa is as required again. (cid:3) 3. Equivalence of definitions of embedding into finite biatomic join-semidistributive lattices We say that a partially ordered set is nœtherian, if it has no infinite strictly increasing chain. Equivalently, every nonempty subset has a maximal element. Of course, every finite partially ordered set is nœtherian. In this paragraph we will prove that if an atomistic lattice can be embedded into some nœtherian, join-semidistributive, biatomic lattice, then it also can be embedded into an atomistic such lattice. We will work toward the proof of this statement in Corollary 3.5. An immediate application of nœtherianity gives the following result. Lemma 3.1. Let L be a nœtherian lattice and let G be a subset of L. Then every join of elements of G is a finite join of elements of G. Werecallthefollowingelementarypropertyofjoin-semidistributivelatticesthat follows immediately from [8, Theorem 1.21]. Lemma 3.2. Let K be a join-semidistributive lattice with zero, let a ∈ K and let X and Y be finite sets of atoms of K. If a∨ X = a∨ Y, then a∨ X = a∨ (X ∩Y). W W W FWor asubsetS ofa join-semilattice L,wedenote the setofalljoins ofnonempty ∨ finite subsets of S by S . 4 K.V.ADARICHEVAANDF.WEHRUNG Proposition 3.3. Let L be a nœtherian, biatomic, (join-semidistributive) lattice and let a ∈ L. We put S = [0,a]∩AtL. Then T = ({0}∪S)∨ is a nœtherian, biatomic, (join-semidistributive), atomistic lattice. Proof. By definition, T is a h∨,0i-subsemilattice of L. Since L is nœtherian, it follows from Lemma 3.1 that T is a lattice in its own right, and it is nœtherian. It is obviously atomistic, with AtT =S. Let p∈S and let x, y ∈T \{0} such that p≤x∨y. Since L is biatomic, there are atoms u≤x andv ≤y of L such that p≤u∨v. Fromx, y ≤a, it follows that u, v ∈S. This shows that T is biatomic. Now weprovethatT is join-semidistributive providedL is. Letb,x, y ∈T such thatb∨x=b∨y. BythedefinitionofT,therearefinitesubsetsX andY ofS such that x= X and y = Y. It follows from Lemma 3.2 that b∨x=b∨ (X∩Y). Since (X ∩Y) ≤ x∧ y, we get b∨x = b∨(x∧ y), thus completing the proof T T W W W that T is join-semidistributive. (cid:3) W ForsubsetsP andQinalatticeL,wesaythatP separates the elements of Q,if forallx, y ∈Qwithx(cid:2)y,thereexists p∈P suchthatp≤xandp(cid:2)y. Observe, in particular, that L is atomistic iff AtL separates the elements of L. Corollary 3.4. Let L be a lattice. Then the following are equivalent: (i) There is a lattice embedding from L into some finite (resp., nœtherian), join-semidistributive, biatomic lattice M such that AtM separates the el- ements of L. (ii) There is a lattice embedding from L into some finite (resp., nœtherian), join-semidistributive, biatomic, atomistic lattice. Theresultsabove also hold for“0-latticeembedding” insteadof “latticeembedding”. Proof. We prove the nontrivial direction (i)⇒(ii), for “nœtherian”—the proof for “finite” is similar. Let M be a nœtherian, biatomic, join-semidistributive lattice containing L as a sublattice such that AtM separates the elements of L. We put S ={p∈AtM |p≤1 }, L andwe observethat S separatesthe elements of L. Now we put T =({0 }∪S)∨. M By Proposition 3.3, T is a nœtherian, atomistic, biatomic, join-semidistributive lattice, with AtT =S and 0 =0 . T M Now we shall investigate further the interaction of the lattices T, M, L. Define a map f: L→T by the rule f(x)= {p∈S |p≤x}, for all x∈L. T In view of Lemma 3.1, f is_well-defined. We observe that f(x)≤x, for all x∈L. Claim 1. The map f is a meet-embedding from L into T. If 0 = 0 , then M L f(0 )=0 . L T Proof of Claim. It is clear that f is order-preserving and that if 0 = 0 , then M L f(0L) = 0T. Let x, y ∈ L such that x (cid:2) y. Since S separates the elements of L, thereexistsp∈S suchthatp≤xandp(cid:2)y. Thusp≤f(x)(bythedefinitionoff) andp(cid:2)f(y)(becausef(y)≤y),whencef(x)(cid:2)f(y). Sof isanorder-embedding. Now let x, y ∈ L. We prove that f(x) ∧ f(y) ≤ f(x ∧ y). Let p ∈ S T L such that p ≤ f(x) ∧ f(y). Since f(x) ≤ x and f(y) ≤ y, this implies that T p ≤ x and p ≤ y. Thus, since L is a sublattice of M, the inequality p ≤ x∧ y L FINITE BIATOMIC LATTICES 5 holds, whence p ≤ f(x∧ y). Therefore, since f is order-preserving, f is a meet- L homomorphism. (cid:3) Claim 1. Claim 2. The map f is a join-homomorphism from L to T. Proof of Claim. Let x, y ∈L and let p∈S such that p≤f(x∨ y). Suppose that L p (cid:2) f(x)∨T f(y). In particular, x and y are nonzero in L, thus in M. By the definition of f, this means that p ≤ x∨ y = x∨ y. Hence, since M is biatomic L M and x and y are nonzero in M, there are atoms u ≤ x and v ≤ y of M such that p ≤ u∨ v. Observe that u, v ∈ S. Moreover, u ≤ f(x) and v ≤ f(y), whence M p≤u∨ v =u∨ v ≤f(x)∨ f(y), a contradiction. M T T Therefore, we have proved that f(x∨ y) ≤ f(x)∨ f(y). Since f is order- L T preserving, the converse inequality holds, which concludes the proof of the claim. (cid:3) Claim 2. The proof of Corollary 3.4 is completed. (cid:3) Corollary 3.5. Let L be an atomistic lattice. Then the following are equivalent: (i) L has a h∨,∧,0i-embedding into some finite (resp., nœtherian), join-sem- idistributive, biatomic lattice. (ii) L has a h∨,∧,0i-embedding into some finite (resp., nœtherian), join-sem- idistributive, biatomic, atomistic lattice. Proof. We prove the nontrivial direction (i)⇒(ii), for “nœtherian” (the proof for “finite” is similar). Let M be a nœtherian, join-semidistributive, biatomic lattice suchthatLisa0-sublatticeofM. ByCorollary3.4,itissufficienttoprovethatthe atomsofM separatethe elements ofL. So letx, y ∈Lsuchthat x(cid:2)y. Since L is atomistic,thereexistsp∈AtLsuchthatp≤xandp(cid:2)y. SinceM isatomic,there exists an atom q of M below p. Then q ≤ x. Furthermore, 0 ≤ q∧y ≤ p∧y = 0, and hence q∧y =0<q, that is, q (cid:2)y. This proves our assertion. (cid:3) 4. Embedding finite lower bounded lattices For lattices K and L, a lattice homomorphism f: K → L is lower bounded, if the preimage under f of any principal dual ideal of L is either empty or has a least element. A lattice L is lower bounded, if every homomorphism from a finitely generated lattice to L is lower bounded. We refer the reader to [2, 8] for more details. For a finite meet-semilattice P, we denote by Sub∧(P) the lattice of all sub- semilattices of P (∅ included). We state here the following result from the first author’s paper [1]. Theorem 4.1. A finite lattice L is lower bounded iff it can be embedded into Sub∧(P) for some finite meet-semilattice P. AsSub∧(P)islowerbounded,atomistic,andbiatomic,thisimpliesimmediately the following result. Corollary 4.2. Any finite lower bounded lattice can be embedded into some finite, atomistic, biatomic, lower bounded lattice. For a finite, atomistic, lower bounded lattice L, Theorem 4.1 says that there existsanembeddingfromLintoSub∧(P)forsomefinitemeet-semilatticeP. This embeddingcanbe chosentopreservethe zero,however,itmaynotpreserveatoms. 6 K.V.ADARICHEVAANDF.WEHRUNG The reasonfor this is that all lattices of the formSub∧(P) have the property that for all atoms x and y, there are at most three atoms below x∨y, while there are finite, atomistic, lower bounded lattices that fail this property. 5. One-atom extensions of finite atomistic lattices We start with the following definition. Definition 5.1. Let L be a finite atomistic lattice. An extension pair of L is a pair (a;M), where the following are satisfied: (i) a∈L\({0}∪AtL); (ii) M is a meet-subsemilattice of L that contains {0}∪[a,1]. For any a∈L, we put L =L\[a,1]. For an extension pair (a;M), we put a L(a;M)=(L ×{0})∪(M ×{1}), a endowed with the componentwise ordering. By definition, a closure operator of L is a map f: L → L such that f ◦f = f, f(x)≥x,andx≤yimpliesthatf(x)≤f(y),forallx,y ∈L. Fixanextensionpair (a;M) of a finite atomistic lattice L. Let f be the closure operatorof L associated with M, that is, f: L→L is given by the rule f(x)=least y ∈M such that x≤y, for all x∈L. We observe that L(a;M)is a meet-subsemilattice of L×2 (where 2={0,1})that contains both (0 ,0) and (1 ,1) as elements. Hence it is a lattice in its own right. L L For (x,ε) ∈ L×2, we denote by (x,ε) the least element of L(a;M) above (x,ε). This element can easily be calculated, by the rule (x,0) (if a(cid:2)x), (x,0)= ((x,1) (if a≤x), (x,1)=(f(x),1). We leave to the reader the straightforwardproof of the following lemma. Lemma 5.2. Let L be a finite atomistic lattice and let (a;M) be an extension pair of L. Then the lattice L(a;M) is finite atomistic, and the map j: L → L(a;M) defined by j(x) = (x,0) for all x ∈ L is a h∨,∧,0,1,ati-embedding from L into L(a;M). Furthermore, At(L(a;M))=(AtL×{0})∪{(0,1)}. Hence, L(a;M) is an atomistic extension of L by exactly one atom, here (0,1). In the sequel, the only properties of L′ =L(a;M)=L[p∗], where p∗ =(0,1) is the new atom, that will be used are the ones listed below: ′ ∗ ∗ L =L∪{p ∨x|x∈M}=L∪{p ∨x|x∈L}, (5.1) ∗ p ≤x⇔a≤x, (5.2) ∗ x≤p ∨y ⇔x≤f(y), (5.3) for all x, y ∈L. Furthermore, AtL′ =AtL∪{p∗}. From now on we shall use the more wieldy description of L(a;M) given by (5.1), (5.2), and (5.3). Remark 5.3. Itisnotdifficulttoverifythatconversely,everyh∨,0,1i-extensionofL by exactly one atom below 1 is, up to isomorphism above L, of the form L(a;M) for exactly one extension pair (a;M) of L. However,we shall not need this fact. FINITE BIATOMIC LATTICES 7 Our next resultdescribeswhen L(a;M)is join-semidistributive. For a subsetX of L, we denote by MaxX the set of all maximal elements of X. Lemma5.4. LetLbeafinite,atomistic,join-semidistributivelatticeandlet(a;M) be an extension pair of L with associated closure operator f. Then L(a;M) is join- semidistributive iff the following conditions are satisfied: (i) MaxL ⊆M; a (ii) f(x∨u) = f(x∨v) implies that u ≤ f(x), for all x ∈ L and all distinct atoms u and v of L. Proof. We put L′ = L(a;M). Suppose first that L′ is join-semidistributive. Let x ∈ MaxL . Suppose that x ∈/ M. Since L is atomistic, there exists an atom a u of L such that u ≤ f(x) while u (cid:2) x. From x < x∨u and the maximality of x in L = L\[a,1], it follows that a ≤ x∨u, whence x∨u ∈ M. So, since a x∨u≤f(x), we obtain that x∨u=f(x). Moreover,p∗ ≤a≤x∨u=f(x), thus ∗ ∗ ′ x∨u = f(x)∨p = x∨p , and so, by the join-semidistributivity of L, u ≤ x, a contradiction. Therefore, MaxL ⊆M. a Now let x∈L and u, v be distinct atoms of L such that f(x∨u)=f(x∨v). It followsfrom(5.3)thatx∨u∨p∗ =x∨v∨p∗,whence,bythejoin-semidistributivity of L′, u≤x∨p∗, and therefore, again by (5.3), u≤f(x). Conversely, suppose that both conditions (i) and (ii) are satisfied. To prove the join-semidistributivity of L′, if suffices to prove that x∨u = x∨v > x cannot happen, for all x ∈ L′ and all distinct atoms u and v of L′ (see [3, Lemma 1.2]). Since L is join-semidistributive, this holds if x, u, v ∈L. Now suppose that x ∈ L and v = p∗, so x∨p∗ = x∨u > x. Hence, by using (5.3),weobtainthatx∨u≤f(x)≤f(x)∨p∗ =x∨p∗ =x∨u,thusp∗ ≤f(x),that is, by (5.2), a ≤ f(x). Moreover, x∨u = f(x) > x, so x ∈ L . Hence there exists a y ∈ MaxL such that x ≤ y. By assumption, y ∈ M, and consequently f(x) ≤ y, a a contradiction since a≤f(x) and a(cid:2)y. Since x∨u = x∨v > x, the last case to consider is x = y∨p∗ for some y ∈ L (see (5.1)). It follows again from (5.3) that f(y∨u)=f(y∨v), and consequently, by assumption, u≤f(y), and so x∨u=x, a contradiction. (cid:3) 6. Partially biatomic extensions By definition, a “biatomicity problem” in a lattice L is a formal expression of theformp≤a∨b,wherep∈AtL,a,b∈L\{0},andtheinequalityp≤a∨bholds while p (cid:2) a, p (cid:2) b. A solution of the problem above in L consists of atoms x ≤ a andy ≤b ofL suchthat p≤x∨y. Recallthat a lattice embedding f: K ֒→L has the congruence extension property, if every congruence of K is the inverse image under f of some congruence of L. The present section will be mainly devoted to proving the following results. Theorem6.1. Everyfinite,atomistic, join-semidistributive (resp., lowerbounded) lattice L admits a h∨,∧,0,1,ati-embedding with the congruence extension property into some finite, atomistic, join-semidistributive (resp., lower bounded) lattice L′ such that all biatomicity problems in L can be solved in L′. Remark 6.2. It will turn out that the embedding from L into L′ in Theorem 6.1 preserves more than the congruences, it is in fact an embedding for the transitive closure ⊳ of the join-dependency relation D. This is equivalent to L′ being a 8 K.V.ADARICHEVAANDF.WEHRUNG congruence-preserving extension of L in the finite, lower bounded case, but not in general. Thecoreofthe difficultyunderlyingTheorem6.1consistsofsolvingveryspecial sorts of biatomicity problems. In Lemma 6.3 to Corollary6.6, we let L be a finite, atomistic,join-semidistributivelattice,andp,q,a∈Lsuchthatpandqaredistinct atoms,a∈L\({0}∪AtL),p≤a∨q,andp(cid:2)x∨q forallx<ainL. Furthermore, we let f: L→L be the map defined by the rule x (if q (cid:2)p∨x), f(x)= (6.1) (p∨x (if q ≤p∨x), for all x∈L. Lemma 6.3. The following assertions hold. (i) The map f is a closure operator of L. (ii) If we denote by M the range of f, then (a;M) is an extension pair of L. (iii) L(a;M) is join-semidistributive. (iv) Denote by p∗ the unique atom of L(a;M)\L. Then p<p∗∨q and p∗ <a. Hence,L(a;M)isajoin-semidistributiveextensionofLinwhichthebiatomicity problem p≤a∨q has a solution. Proof. The assertion (i) is straightforward. Furthermore, it is obvious that {0,1} is contained in M. Now let x ∈ [a,1], we prove that f(x) = x. This is obvious if q (cid:2) p∨x, so suppose that q ≤ p∨x. From p ≤ a ∨q, q ≤ p∨x, and the join-semidistributivityofL,itfollowsthatp≤x∨a=x, whencef(x)=x∨p=x. This completes the proof of (ii). Now let x ∈ MaxLa. We prove that f(x) = x. This is trivial if q (cid:2) p∨x, so suppose that q ≤ p∨x. If p (cid:2) x, then, by the maximality assumption on x, a ≤ p∨x. Thus, from p ≤ a∨q, p∧a = 0, and the join-semidistributivity of L, it follows that p ≤ x∨q. Thus, since q ≤ p∨x and by the join-semidistributivity of L, we obtain that p≤x, a contradiction. Therefore,p≤x, so f(x)=p∨x=x. This proves that MaxL ⊆M. a Let x ∈ L and u, v be distinct atoms of L such that f(x∨u) = f(x∨v). We prove that u≤f(x). If q (cid:2)p∨x∨u, then q (cid:2)p∨x∨v. Otherwise we would have p∨x∨u=f(x∨u)=f(x∨v)=x∨v, thusq ≤p∨x∨v =p∨x∨u,acontradiction. Thusx∨u=f(x∨u)=f(x∨v)=x∨v, whence, by the join-semidistributivity of L, u≤x≤f(x). Suppose now that q ≤p∨x∨u. By the previous paragraph,q ≤p∨x∨v, and thusp∨x∨u =f(x∨u)=f(x∨v)=p∨x∨v. Hence,bythejoin-semidistributivity of L, we have u≤p∨x, and so q ≤p∨x∨u=p∨x. Therefore,u≤p∨x=f(x). By Lemma 5.4, this completes the proof of assertion (iii). The assertion (iv) follows immediately from f(q)=p∨q >p. (cid:3) From Lemma 6.4 to Corollary 6.6, we let M and p∗ be as in the statement and proof of Lemma 6.3. For a finite lattice K, we let D denote the relation of join- K dependency on the set of join-irreducible elements of K. Observe that for atoms x and y of K, the relation D takes the following simple form: K xDK y iff x6=y and ∃u∈K such that x≤y∨u and x(cid:2)u. FINITE BIATOMIC LATTICES 9 Further,we denote by D the binaryrelationonJ(K)defined by xD y iff either K K xD y or x = y. Then we let ⊳ denote the transitive closure of D and E K K K K denote the reflexive, transitive closure of D . K Furthermore, since L is finite, atomistic, and join-semidistributive, it follows fromLemma 3.2that everyelement a of L hasa minimal decomposition,that is, a least(withrespecttocontainment)subsetX ofAtLsuchthata= X. Wedenote this set of atoms by ∂L(a) (“extreme boundary of a”), or ∂(a) if L is understood. W Note that ∂(a) is also the unique irredundant decomposition of a. Observe that ∂(a)consistsexactlyoftheelementswhicharejoin-primeintheinterval[0,a]. First it is convenient to prove the following lemma. Lemma 6.4. For any u∈∂(a), the following relations hold: (i) pD u; L (ii) p∗DL[p∗]u. Proof. Foranyu∈∂(a),weputaru= (∂(a)\{u}). Fromthefactthatu∈∂(a), itfollowsthataru<a,andsop(cid:2)(aru)∨q bythe minimality assumptionona. W However,p≤a∨q =(aru)∨u∨q while p6=u (because p(cid:2)a), whence pDLu. Furthermore, p∗ ≤a=(aru)∨u while, since aru<a, we have by (5.2) that p∗ (cid:2)aru, and consequently p∗DL[p∗]u. (cid:3) Lemma 6.5. For all x, y ∈AtL, the following assertions hold: (i) xDL[p∗]y implies that x⊳L y; (ii) xDL[p∗]p∗ implies that xDLp; (iii) p∗DL[p∗]x implies that there exists u∈∂(a) such that uDLx; (iv) x⊳L[p∗] y iff x⊳L y; (v) p∗ ⊳L[p∗] p∗ iff there exists u∈∂(a) such that u⊳L p. Proof. (i) By assumption, x 6= y and there exists u ∈ L[p∗] such that x ≤ y∨u and x (cid:2) u. Suppose that the relation x DL y does not hold. So u ∈/ L, and thereforethereexistsv ∈M suchthatu=v∨p∗, hence,by (5.3),x≤f(y∨v) and x (cid:2) v. Since the relation xDLy does not hold, we obtain that x (cid:2) y∨v. Hence f(y∨v)>y∨v, fromwhereweobtainf(y∨v)=p∨y∨v (soq ≤p∨y∨v). Then, since x≤p∨y∨v and x(cid:2)y∨v, we obtain that xD p. (6.2) L If q ≤ p ∨v, then, since v ∈ M, the equalities v = f(v) = p ∨v holds by the definition of f, whence p≤v, and so x≤p∨y∨v =y∨v, a contradiction. Hence q (cid:2)p∨v, but q ≤p∨y∨v, so we obtain the relation qD y. (6.3) L Finally, since p≤a∨q and p(cid:2)a, we obtain that pDLq, therefore, from (6.2) and (6.3), it follows that x⊳ y. L (ii) There exists u ∈ L[p∗] such that x ≤ p∗ ∨u and x (cid:2) u. Thus p∗ ∨u 6= u, so u ∈ L and x ≤ f(u). From the relation x (cid:2) u, it follows that f(u) = p∨u, so x≤p∨u while x(cid:2)u, and so xDLp. (iii) There exists v ∈ L[p∗] such that p∗ ≤ x∨v and p∗ (cid:2) v. Thus v ∈ L, and a≤x∨v whilea(cid:2)v. Fromthesecondrelation,itfollowsthatthereexistsu∈∂(a) such that u(cid:2)v. However, u≤a≤x∨v, and so uDLx. 10 K.V.ADARICHEVAANDF.WEHRUNG (iv) From the fact that the natural embedding from L into L[p∗] is atom- preserving, it follows that x ⊳L y implies that x ⊳L[p∗] y for all x, y ∈ AtL. Conversely, for any x, y ∈ AtL, the relation x ⊳L[p∗] y means that there are a positiveintegern andatomsz0 =x, z1,...,zn =y ofL[p∗]suchthatziDL[p∗]zi+1 foralli<n. We provebyinduction onn that this implies thatx⊳ y. Forn=1, L the conclusionfollows fromitem (i) above. Suppose that n≥2. If zn−1 6=p∗, then it follows from the induction hypothesis that x⊳L zn−1, while, by item (i) above, zn−1 ⊳L y, so x ⊳L y. Suppose now that zn−1 = p∗. Then zn−2 6= p∗. Thus, by the induction hypothesis, x EL zn−2 (the equality may hold, e.g, for n = 2). Furthermore,itfollowsfromitems(ii)and(iii)abovethatzn−2DLpanduDLy for some u∈∂(a). But from Lemma 6.4(i), it follows that pDLu, and so zn−2 ⊳L y. Therefore, x⊳ y. L (v) There exists z ∈ AtL such that p∗ ⊳L[p∗] z ⊳L[p∗] p∗. From (ii), (iii), and (iv), it follows that u E z, for some u ∈ ∂(a), and z E p, whence u E p, but L L L u6=p (because p(cid:2)a), and so u⊳L p. Conversely, let u ∈ ∂(a) such that u ⊳L p. Thus we also have u ⊳L[p∗] p. Since p ≤ p∗ ∨q by Lemma 6.3 (iv) and since p, p∗, and q are distinct atoms, the relation pDL[p∗] p∗ holds. From Lemma 6.4(ii), it follows that p∗ DL[p∗]u, so p∗DL[p∗]u⊳L[p∗] pDL[p∗]p∗, whence p∗ ⊳L[p∗] p∗. (cid:3) Corollary 6.6. (i) The canonical embedding from L into L[p∗] has the congruence extension property; in fact, it is an embedding for the ⊳ relation on atoms. (ii) If L is lower bounded, then L[p∗] is lower bounded. Proof. (i) By Theorem 2.30 and Lemma 2.36 in [8], it is sufficient to prove that x EL y iff x EL[p∗] y, for all atoms x and y of L, which follows immediately from the stronger statement Lemma 6.5(iv). (ii) It is well-known that a finite lattice K is lower bounded iff it has no D - K cycle,thatis, the relation⊳ is irreflexive, see [8, Corollary2.39]. Suppose that L K is lower bounded. It follows from Lemma 6.5(iv) that the relation x⊳L[p∗] x holds for no x ∈ AtL. Suppose that p∗ ⊳L[p∗] p∗. It follows from Lemma 6.5(v) that there exists u∈∂(a) such that u⊳ p. By Lemma 6.4(i), p⊳ u, whence L has a L L DL-cycle, a contradiction. Therefore, the relation x ⊳L[p∗] x holds for no atom x of L[p∗]. (cid:3) Proof of Theorem 6.1. We present the proof for “join-semidistributive”, the proof for “lower bounded” is similar. Since L is finite, it suffices to prove that every biatomicityproblemp≤a∨binLcanbesolvedinsomefinite,atomistic,join-sem- idistributive h∨,∧,0,1,ati-extension of L in which L has the congruence extension property. Wearguebyinductiononℓ (a)+ℓ (b),whereℓ (x)denotestheminimal L L L sizeofasubsetX ofAtLsuchthatx= X,forallx∈L. Ifℓ (a)=ℓ (b)=1then L L the biatomicity problem p≤a∨b is already solvedin L, by x=a and y =b. Now W suppose,forexample,thatb=c∨q,forsomec∈L\{0}andsomeatomqsuchthat ℓ (c)<ℓ (b). Let a≤a∨c be minimal such that p≤a∨q. By Lemma 6.3, there L L exists a finite join-semidistributiveh∨,∧,0,1,ati-extensionL of L,in whichL has 1 the congruence extension property, such that there exists an atom p′ ≤a with p≤ p′∨q. Sop′ ≤a∨cinL andℓ (a)+ℓ (c)≤ℓ (a)+ℓ (c)<ℓ (a)+ℓ (b). Thus, 1 L1 L1 L L L L arguing as above, we obtain a finite join-semidistributive h∨,∧,0,1,ati-extension L of L , in which L has the congruence extension property, with atoms x ≤ a 2 1 1