Friedrich Wehrung
email: wehrung@math.unicaen.fr

POSET REPRESENTATIONS OF DISTRIBUTIVE SEMILATTICES

Keywords: . 2000 Mathematics Subject Classification. Primary 06A06, 06A12. Secondary 06B10 Poset, distributive, semilattice, p-measure, diagram, relatively complete extension, interval extension, covering extension, normal interval diagram, standard interval scheme, strong amalgam, doubling extension

We prove that for every distributive ∨, 0 -semilattice S, there are a meet-semilattice P with zero and a map µ : P × P → S such that µ(x, z) ≤ µ(x, y) ∨ µ(y, z) and x ≤ y implies that µ(x, y) = 0, for all x, y, z ∈ P , together with the following conditions: (P1) µ(v, u) = 0 implies that u = v, for all u ≤ v in P . (P2) For all u ≤ v in P and all a, b ∈ S, if µ(v, u) ≤ a ∨ b, then there are a positive integer n and a decomposition u

The subset {µ(x, 0) | x ∈ P } generates the semilattice S. Furthermore, every finite, bounded subset of P has a join, and P is bounded in case S is bounded. Furthermore, the construction is functorial on latticeindexed diagrams of finite distributive ∨, 0, 1 -semilattices.

1. Introduction 1.1. Origin of the problem. The classical congruence lattice representation problem, usually denoted by CLP, asks whether every distributive ∨, 0 -semilattice is isomorphic to the semilattice Con c L of all compact (i.e., finitely generated) congruences of some lattice L. (It is well-known, see [START_REF] Funayama | On the distributivity of a lattice of lattice congruences[END_REF] or [START_REF] Grätzer | General Lattice Theory[END_REF]Theorem II.3.11], that Con c L is a distributive ∨, 0 -semilattice, for every lattice L.) This problem has finally been solved negatively by the author in [START_REF] Wehrung | A solution to Dilworth's Congruence Lattice Problem[END_REF]. This negative solution came out of a failed attempt to extend to semilattices the representation result of distributive semilattices by posets (i.e., partially ordered sets) stated in the Abstract. The purpose of the present paper is to give a proof of that result.

A first motivation for proving this result lies in its relation with congruence lattices of lattices, which we shall outline now. Definition 1.1. Let S be a ∨, 0 -semilattice and let P be a poset. A map µ : P × P → S is a S-valued p-measure on P , if µ(x, z) ≤ µ(x, y) ∨ µ(y, z) and x ≤ y implies µ(x, y) = 0, for all x, y, z ∈ P . The pair P, µ is a S-valued pmeasured poset.

The inequality µ(x, z) ≤ µ(x, y) ∨ µ(y, z) will be referred to as the triangular inequality. The letter 'p' in 'p-measure' stands for 'poset'. Notation 1.2. We shall always denote by P , Q, . . . , the underlying posets of pmeasured posets P , Q, . . . . For a p-measured poset P = P, µ , we shall often use the notation x y P = µ(x, y), for x, y ∈ P . Elements of the form x y P will be called Boolean values.

A fundamental class of p-measures is given as follows. For a lattice L, the map Θ + : L × L → Con c L defined by the rule Θ + (x, y) = least congruence of L that identifies x ∨ y and y, (1.1) for all x, y ∈ L, is obviously a Con c L-valued p-measure on L. Furthermore, it satisfies the following conditions: (i) Θ + (v, u) = 0 implies that u = v, for all u ≤ v in L.

(ii) For all u ≤ v in L and all a, b ∈ Con c L, if Θ + (v, u) ≤ a ∨ b, then there are a positive integer n and a decomposition u = x 0 ≤ x 1 ≤ • • • ≤ x n = v such that either Θ + (x i+1 , x i ) ≤ a or Θ + (x i+1 , x i ) ≤ b, for each i < n. (iii) The subset {Θ + (v, u) | u ≤ v in L} generates the semilattice Con c L. Item (ii) above follows from the usual description of congruences in lattices, see, for example, [4, Theorem I.3.9], while Items (i) and (iii) are trivial.

Hence, if a distributive ∨, 0 -semilattice S is isomorphic to Con c L for some lattice L, then there exists a S-valued p-measure µ : L × L → S satisfying (i)-(iii) above. Although we could prove in [START_REF] Wehrung | A solution to Dilworth's Congruence Lattice Problem[END_REF] that there may not exist such a lattice L, the main result of the present paper is that the conclusion about p-measures persists. Conditions (i) and (ii) are the same as the conditions denoted by (P1) and (P2), respectively, in the Abstract, while (P3) is a strengthening of (iii).

Furthermore, unlike earlier representation results such as Grätzer and Schmidt's representation theorem of algebraic lattices as congruence lattices of abstract algebras [START_REF] Grätzer | Characterizations of congruence lattices of abstract algebras[END_REF], our result characterizes distributive algebraic lattices, see Corollary 10.4 and Proposition 10.5.

1.2.

Lifting objects and diagrams with respect to functors. Most of the recent efforts at solving CLP have been aimed at lifting not only individual (distributive) semilattices, but also diagrams of semilattices, with respect to the congruence semilattice functor Con c . They are based on the following lemma, proved by Ju. L. Ershov as the main theorem in Section 3 of the Introduction of his 1977 monograph [START_REF] Ju | Theory of Numerations[END_REF] and P. Pudlák in his 1985 paper [START_REF] Pudlák | On congruence lattices of lattices[END_REF]Fact 4,p. 100].

Lemma 1.3. Every distributive ∨, 0 -semilattice S is the directed union of its finite distributive ∨, 0 -subsemilattices.

Because of this, lifting diagrams of distributive semilattices can be reduced to lifting diagrams of finite distributive semilattices.

The formal definition of a lifting runs as follows. For categories I, A, B and a functor Φ : A → B, a lifting of a functor B : I → B with respect to Φ is a functor A : I → A such that Φ • A is naturally equivalent to B. In particular, in case I is the one-object, one-morphism category, we identify the functors from I to any category C with the objects of C, so a lifting of an object B of B is an object A of A such that Φ(A) ∼ = B.

Our examples below will involve the following categories:

• The category DSLat (resp., DSLat emb ) of all distributive ∨, 0 -semilattices with ∨, 0 -homomorphisms (resp., ∨, 0 -embeddings). • The category DLat (resp., DLat emb ) of all distributive 0-lattices with 0-lattice homomorphisms (resp., 0-lattice embeddings).

• The category Lat of all lattices with lattice homomorphisms. Prominent results of lifting functors with respect to the functor Con c : Lat → DSLat are the following:

(1) E. T. Schmidt proved [START_REF] Schmidt | The ideal lattice of a distributive lattice with 0 is the congruence lattice of a lattice[END_REF] that every distributive 0-lattice is isomorphic to Con c L for some lattice L. (2) Schmidt's result got extended in 1985 by P. Pudlák [START_REF] Pudlák | On congruence lattices of lattices[END_REF], who proved that the inclusion functor DLat emb ֒→ DSLat has a lifting A : DLat emb → Lat with respect to the Con c functor. So Con c A(D) ∼ = D naturally in D, for every distributive 0-lattice D. Furthermore, in Pudlák's construction, A(D) is a finite atomistic lattice whenever D is finite. (3) Pudlák's result got further extended by P. Růžička [START_REF] Růžička | Liftings of distributive lattices by locally matricial algebras with respect to the Idc functor[END_REF], with a different, ring-theoretical construction that implies that A(D) can be taken locally finite, sectionally complemented, and modular, for every distributive 0lattice D. (4) On the negative side, Pudlák conjectured in 1985 the existence of a lifting of the inclusion functor DSLat emb ֒→ DSLat with respect to the Con c functor. This conjecture got disproved, before the final negative solution for CLP was obtained, by J. Tůma and F. Wehrung [START_REF] Tůma | Congruence lifting of diagrams of finite Boolean semilattices requires large congruence varieties[END_REF]. We shall often identify every poset K with the category whose objects are the elements of K and where there exists at most one morphism from x to y, for elements x, y ∈ K, and this occurs exactly in case x ≤ y. Denote by VPMeas the category whose objects are all triples P, µ, S , where P is a ∧, 0 -semilattice, S is a distributive ∨, 0 -semilattice, and µ : P × P → S is a p-measure satisfying the conditions (P1)-(P3) stated in the Abstract, and where the morphisms from P, µ, S to Q, ν, T are the pairs f, f , where f : P → Q is order-preserving, f : S → T is a ∨, 0 -homomorphism, and ν(f (x), f (y)) = f (µ(x, y)) for all x, y ∈ P . The main result of the present paper (Theorem 10.2) implies that every functor S : K → DSLat emb , where K is (the category associated to) a lattice, has a lifting with respect to the forgetful functor Π : VPMeas → DSLat. (By using the results of [START_REF] Wehrung | Distributive semilattices as retracts of ultraboolean ones; functorial inverses without adjunction[END_REF][START_REF] Wehrung | Lifting retracted diagrams with respect to projectable functors[END_REF], this can be extended to functors S : K → DSLat, still for a lattice K, but we shall not present more details about this here.) Hence, to every distributive ∨, 0 -semilattice S, this lifting associates, in a somewhat 'natural' fashion, an object of VPMeas of the form P, µ, S . We shall use ≤ (instead of ≤ P ), ≺, , ∼, or in case P is understood. We say that P is lower finite, if the principal ideal {x ∈ P | x ≤ a} is finite for all a ∈ Λ. Observe that in case P is a meet-semilattice, this implies that P has a least element.

For a category C and a poset P , a P -indexed diagram in C is a functor D : P → C (where P is identified with the associated category). This amounts to a family D x | x ∈ P of objects of C, together with a system of morphisms ϕ x,y : D x → D y , for x ≤ y in P , such that ϕ x,x = id Dx and ϕ x,z = ϕ y,z • ϕ x,y for all x ≤ y ≤ z in P , and then we write D = D x , ϕ x,y | x ≤ y in P . We shall also denote by D↾ ≤p (resp., D↾ <p ) the restriction of D to {x ∈ P | x ≤ p} (resp., {x ∈ P | x < p}), for all p ∈ P .

A join-semilattice S is distributive, if for all a, b, c ∈ S, if c ≤ a ∨ b, then there are x ≤ a and y ≤ b in S such that c = x ∨ y. Equivalently, the ideal lattice of S is a distributive lattice, see [START_REF] Grätzer | General Lattice Theory[END_REF]Section II.5].

We shall identify every natural number n with the set {0, 1, . . . , n -1}. We shall denote by P(X) the powerset of a set X.

Structure of the proof

2.1. First obstacle: there is no sequential proof. Many proofs of positive representation results use transfinite iterations of 'one-step constructions', each of them adding a small number of elements at a time. This is typically the case for Jónsson's proof of Whitman's Embedding Theorem (cf. [START_REF] Jónsson | On the representation of lattices[END_REF]). Other examples are the main construction of [START_REF] Wehrung | Forcing extensions of partial lattices[END_REF] (that proves, among other things, that every lattice L such that Con c L is a lattice admits a relatively complemented congruence-preserving extension), or the construction used in [START_REF] Růžička | Distributive congruence lattices of congruencepermutable algebras[END_REF] to prove that every distributive ∨, 0semilattice is the range of some 'V-distance' of type 2, or the construction used in [START_REF] Lampe | Congruence lattices of algebras of fixed similarity type[END_REF] to establish that every algebraic lattice with compact unit is isomorphic to the congruence lattice of some groupoid.

However, our result cannot be proved in such a way. The reason for this is contained in [START_REF] Wehrung | Non-extendability of semilattice-valued measures on partially ordered sets[END_REF], where we construct, at poset level, an example of a p-measure that cannot be extended to a p-measure satisfying (P2). This partly explains the complexity of our main construction: the posets and measures require a somehow 'explicit' construction, which in turn requires quite a large technical background.

2.2.

General principle of the proof. We need to lift a given ∨, 0 -semilattice S with respect to the functor Π introduced in Subsection 1.2. If this is done in case S has a largest element, the general result follows easily from restricting any p-measure µ : P × P → S ∪ {1} representing S ∪ {1} to a suitable lower subset of P (cf. proof of Corollary 10.4).

So suppose, from now on, that S is a ∨, 0, 1 -semilattice. By Lemma 1.3, S is the directed union of a family D = D i | i ∈ Λ of finite distributive ∨, 0, 1subsemilattices; furthermore, Λ can be taken the collection of all finite subsets of S, in particular Λ is a lower finite lattice. Our proof will construct a lifting, with respect to the functor Π, of D (viewed as a Λ-indexed diagram); the representation result for S will follow immediately (cf. proof of Corollary 10.4).

So now we start with a lower finite meet-semilattice Λ and a Λ-indexed diagram D = D i , ϕ i,j | i ≤ j in Λ of finite distributive lattices and ∨, 0, 1 -homomorphisms. (No stage of the proof will require the totality of these assumptions, nevertheless we shall assume them altogether in the present outline.) As Λ is lower finite, it is well-founded. Accordingly, our lifting will be constructed inductively: from a lifting (with respect to the Π functor) of D↾ <ℓ , we shall construct a lifting of D↾ ≤ℓ , for any ℓ ∈ Λ.

When trying to do this we stumble on a major problem. For such an extension of liftings to be possible, we need a number of somewhat complex assumptions on the lifting of D↾ <ℓ we are starting with. Fundamental examples, notably in [START_REF] Tůma | Simultaneous representations of semilattices by lattices with permutable congruences[END_REF][START_REF] Wehrung | Non-extendability of semilattice-valued measures on partially ordered sets[END_REF], show that these assumptions cannot be dispensed with.

2.3.

Structure of the lifting at poset level; interval extensions. A first, mild assumption is to suppose that our lifting of D↾ <ℓ consists, at poset level, of inclusion maps. Hence we start with a lifting of D↾ <ℓ of the form Q i | i < ℓ , where Q i is a D i -measured poset for all i < ℓ and Q j is an extension of Q i with respect to ϕ i,j for all i ≤ j < ℓ: the latter condition means that Q i is a sub-poset of Q j and x y

Q i = ϕ i,j ( x y Q j ) for all x, y ∈ Q i .
Trying to figure out what the poset Q ℓ should be, an obvious requirement is that it should contain the set-theoretical union

P ℓ = (Q i | i < ℓ).
As Q i should be a sub-poset of P ℓ for each i < ℓ, we should ensure that the reflexive, transitive binary relation on the set P ℓ generated by the union of all the partial orderings on the Q i s is a partial ordering (this amounts to verifying that it is antisymmetric).

Easy examples show that this is not the case as a rule.

Hence we need to put conditions on the inclusion maps Q i ֒→ Q j , for i ≤ j < ℓ. These embeddings will be required to be so-called interval extensions (cf. Definition 3.1). Furthermore, all the posets Q i will be finite lattices. As a consequence of the definition of an interval extension, it will turn out that Q i is a sublattice of Q j for all i ≤ j < ℓ (cf. Lemma 3.3).

2.4.

Normal interval diagrams and covering extensions. In order to endow the set-theoretical union P ℓ = (Q i | i < ℓ) with a suitable poset structure, we need to add, to the condition that Q j is an interval extension of Q i whenever i ≤ j < ℓ, an assumption of 'coherence' between the orderings of the Q i s. This condition, formulated in Definition 5.1, implies, in particular, that Q i ∩ Q j = Q i∧j for all i, j < ℓ (remember that Λ is a meet-semilattice). We shall say that Q i | i < ℓ is a normal interval diagram of posets. Once this is assumed, the partial ordering on P ℓ can be easily described from the individual orderings of the Q i s (cf. Lemma 5.2). We shall call P ℓ the strong amalgam of Q i | i < ℓ (cf. Lemmas 5.2 and 5.3). It will turn out that P ℓ is an interval extension of each Q i (cf. Lemma 5.4) and that it is a lattice (cf. Proposition 5.5).

Due to problems pertaining to Example 10.6 and originating in the main counterexample of [START_REF] Tůma | Simultaneous representations of semilattices by lattices with permutable congruences[END_REF], the p-measures on the Q i s need not have a common extension to a p-measure on P ℓ . This particular problem is, actually, the hardest technical problem that we need to solve, so we will postpone the required outline until Subsection 2.6.

For the moment, suppose that we have succeeded in finding a p-measure on P ℓ extending all p-measures on the Q i s. Even in case the latter p-measures all satisfy Conditions (P1)-(P3) stated in the Abstract, this may not be the case for --P ℓ . This is relatively easy to fix, by extending P ℓ to a larger poset Q ℓ with a natural extension - -Q ℓ of - -P ℓ . The general principle underlying the corresponding extension of p-measures is presented in Section 7. The poset Q ℓ will be obtained by inserting the ordinal sum of two suitable finite Boolean lattices in each prime interval of P ℓ (cf. Proof of Theorem 10.2). In particular, Q ℓ is an interval extension of P ℓ .

At this point, we stumble on the slightly annoying point that an interval extension of an interval extension may not be an interval extension (cf. Example 4.4). So nothing would guarantee a priori that Q ℓ is an interval extension of each Q i for i < ℓ, and the induction process would break down. Fortunately, Q ℓ is what we call in Definition 4.1 a covering extension of P ℓ , which, by Proposition 4.3, will be sufficient to ensure that Q ℓ is, indeed, an interval extension of each Q i . (It would be too much asking that Q ℓ be a covering extension of each Q i .) Therefore, the induction ball keeps rolling-at least at poset level.

2.5. The elements x • and x • . A fundamental tool in the inductive evaluation of the Boolean values x y P ℓ is introduced in Section 6. For each x ∈ P ℓ \ Q 0 , the properties of normal interval diagrams imply the existence of a least element of P ℓ , denoted by x • , such that x < x • and x • lies in a block Q i of smaller index than the one containing x (the latter condition is formulated ν(x • ) < ν(x) in Lemma 6.1the 'complexity' ν(x) of x is the least i < ℓ such that x ∈ Q i ). The element x • is defined dually, so x • is the largest element smaller than x such that ν(x • ) < ν(x). The inductive definition of x y P ℓ will make a heavy use of the elements x • and x • .

2.6. Finding the p-measure on P ℓ : doubling extensions. As mentioned earlier, the hardest technical problem of the whole paper is to ensure that the pmeasures on the Q i , for i < ℓ, have a common extension to some p-measure on P ℓ . Recall that Example 10.6 shows that this cannot be done without additional assumptions.

The idea that we implement here is to relate the Boolean value x y , for x, y ∈ P ℓ , to Boolean values involving less complicated elements, such as x • y , x y • , and so on. The first doubling condition (DB1) (cf. Section 8) says that every x ∈ P ℓ is 'closest' (with respect to Boolean values) either to x • or to x • . The second doubling condition (DB2) says that if x is closest to x • and in 'non-degenerate' cases, x y = x • y whenever both x and y (and thus also x • ) belong to the same Q i ; and, symmetrically, if x is closest to x • and in non-degenerate cases, y x = y x • . This is the basis for our definition of x y , for x, y ∈ P ℓ . In case x, y ∈ Q i for some i < ℓ, we put [[x y]] = ϕ i,ℓ ( x y Q i ) (cf. (8.4)). This is the easiest case where we can evaluate x y , for x, y ∈ P ℓ -namely by setting x y = [[x y]].

In the general case, the most natural guess is then to define x y as the meet, in D ℓ , of all joins of the form i<n [[z i z i+1 ]], where n is a positive integer, z 0 , z 1 , . . . , z n are elements of P ℓ , z 0 = x, and z n = y.

Most of the technical difficulties of the paper are contained in the proof that this guess is sound.

This proof makes a heavy use of the doubling conditions. Furthermore, as an unexpected side issue, it implies that it is sufficient to consider the case where n = 3 (cf. Corollary 9.7). The propagation of (DB1) to the level ℓ is taken care of by Lemma 8.5. The propagation of (DB2) is taken care of by Lemma 9.12.

This takes care of the construction of - -P ℓ . As mentioned earlier, the technical background for the extension of that p-measure to a suitable p-measure on Q ℓ is contained in Section 7. The construction of the poset Q ℓ itself is quite natural, and it is contained in the proof of Theorem 10.2.

Corollary 10.4 trivially implies the result stated in the Abstract. Further comments, in particular about the possible uses of our main result to tackle current open problems, are presented in Section 11.

Relatively complete and interval extensions of posets

Definition 3.1. A poset Q is a relatively complete extension of a poset P , in notation P ≤ rc Q, if for all x ∈ Q, there exists a largest element of P below x (denoted by x P ) and a least element of P above x (denoted by x P ). Then we define binary relations ≪ P and ≡ P on Q by x ≪ P y ⇐⇒ x P ≤ y P , x ≡ P y ⇐⇒ (x P = y P and x P = y P ), for all x, y ∈ Q. We say that Q is an interval extension of P , in notation P ≤ int Q, if P ≤ rc Q and for all x, y ∈ Q, x ≤ y implies that either x ≪ P y or x ≡ P y.

The proofs of the following two lemmas are easy exercises. Lemma 3.2. Let P , Q, and R be posets. If P ≤ rc Q and Q ≤ rc R, then P ≤ rc R. Lemma 3.3. Let Q be a relatively complete extension of a poset P and let X ⊆ P . Then P X exists iff Q X exists, and then the two values are equal. The dual statement also holds.

In particular, if P ≤ rc Q and Q is a lattice, then P is a sublattice of Q. Hence, from now on, when dealing with relatively complete extensions, we shall often omit to mention in which subset the meets and joins are evaluated. Lemma 3.4. Let Q be an interval extension of a poset P , let x ∈ P and y, z ∈ Q. If x, y ≤ z and x y, then y P ≤ z; and dually.

Proof. If y ≡ P z, then, as x ∈ P and x ≤ z, we get x ≤ z P = y P ≤ y, a contradiction; hence y ≡ P z. As y ≤ z and P ≤ int Q, we get y ≪ P z, and thus y P ≤ z. Lemma 3.5. Let Q be an interval extension of a poset P . Then Q is a lattice iff P is a lattice and the interval [x P , x P ] is a lattice for each x ∈ Q. Furthermore, if Q is a lattice, then for all incomparable x, y ∈ Q,

x ∨ y = x P ∨ y P , if x ≡ P y, x ∨ [u,v] y, if x P = y P = u and x P = y P = v, (3.1)
x

∧ y = x P ∧ y P , if x ≡ P y, x ∧ [u,v] y, if x P = y P = u and x P = y P = v. (3.2)
Proof. We prove the nontrivial direction. So suppose that P is a lattice and the interval [x P , x P ] is a lattice for each x ∈ Q. For incomparable x, y ∈ P , we prove that the join x ∨ y is defined in Q and given by (3.1). The proof for the meet is dual. So let z ∈ Q such that x, y ≤ z. If x ≪ P z, then x P ≤ z, hence, using Lemma 3.4 (with x P instead of x), we obtain y P ≤ z, and hence, using Lemma 3.3, x P ∨y P ≤ z. The conclusion is similar for y ≪ P z. As P ≤ int Q, the remaining case is where x ≡ P z ≡ P y. Putting u = x P = y P and v = x P = y P , the interval [u, v] is, by assumption, a lattice, so x ∨ [u,v] y ≤ z, and hence

x ∨ y = x ∨ [u,v] y ≤ z.
Lemma 3.6. Let Q be an interval extension of a poset P . Then x ∼ y implies that x P ∼ y and x P ∼ y, for all x, y ∈ Q.

Proof. We prove the result for x P . If x ≤ y, then x P ≤ y and we are done. Suppose that y ≤ x. If y ≪ P x, then y ≤ x P . Suppose that y ≪ P x. As y ≤ x and P ≤ int Q, we get x ≡ P y, and thus x P = y P ≤ y.

(ii) Q a,b ∩ P = ∅ for all a, b ∈ I. (iii) Q a,b ∩ Q c,d = ∅ for all distinct a, b , c, d ∈ I.
We say that the standard interval scheme above is based on P .

The proofs of the following two lemmas are straightforward exercises.

Lemma 3.8. Let P, Q a,b | a, b ∈ I be a standard interval scheme. Put Q = P ∪ (Q a,b | a, b ∈ I). Furthermore, for all x ∈ Q, put x P = x P = x if x ∈ P , while x P = a and x P = b if x ∈ Q a,b , for a, b ∈ I. Let x ≤ y hold, if either x P ≤ y P or there exists a, b ∈ I such that x, y ∈ Q a,b and x ≤ Q a,b y, for all x, y ∈ Q. Then ≤ is a partial ordering on Q and Q is an interval extension of P .
In the context of Lemma 3.8, we shall use the notation

Q = P + (Q a,b | a, b ∈ I). (3.3)
Conversely, the following lemma shows that any interval extension can be obtained by the

P + (Q a,b | a, b ∈ I) construction.
This construction is a special case of a construction presented in [START_REF] Grätzer | A new lattice construction[END_REF]. It follows from Lemmas 3.8 and 3.9 that any standard interval scheme based on P defines an interval extension of P , and every interval extension of P is defined via some standard interval scheme on P .

Covering extensions of posets

Definition 4.1. We say that a poset Q is a covering extension of a poset P , in notation P ≤ cov Q, if Q is an interval extension of P (cf. Definition 3.1) and the relation x P P x P holds for all x ∈ Q. Lemma 4.2. Let P , Q, and R be posets such that P ≤ int Q, Q ≤ int R, and there are no x ∈ P and y ∈ R such that y Q < x < y Q . Then P ≤ int R.

Proof. First, P ≤ rc R (cf. Lemma 3.2). Now let x ≤ y in R, and assume, towards a contradiction, that x ≪ P y and x ≡ P y.

If x ≡ Q y, then x ≡ P y, a contradiction. As x ≤ y and Q ≤ int R, we get x ≪ Q y, that is, x Q ≤ y Q . If x Q ≪ P y Q , then x ≪ P y, a contradiction. As x Q ≤ y Q and P ≤ int Q, we get x Q ≡ P y Q . As y Q ≤ y Q and P ≤ int Q, either y Q ≡ P y Q or y Q ≪ P y Q .
In the first case, we get, using the relation x Q ≡ P y Q , the equalities x P = (x Q ) P = (y Q ) P = (y Q ) P = y P . In the second case, we get, using again the relation x Q ≡ P y Q , the inequalities

x P = (x Q ) P = (y Q ) P ≤ y Q . But y Q ≤ (y Q ) P = x P ,
and so y Q ≤ x P ≤ y Q . Hence, by assumption, either x P = y Q or x P = y Q . If x P = y Q , then x P = y P , so x ≪ P y, a contradiction; hence only the subcase where x P = y Q remains, so y Q ∈ P , and so x P = y Q = y P .

So we have proved that in either case, the equality x P = y P holds. Dually, the equality x P = y P holds, and so x ≡ P y, a contradiction. Proposition 4.3. For arbitrary posets P , Q, and R, the following statements hold:

(i) If P ≤ int Q and Q ≤ cov R, then P ≤ int R. (ii) If P ≤ cov Q and Q ≤ cov R, then P ≤ cov R.
Proof. (i) follows immediately from Lemma 4.2. Now we prove (ii). So assume that

P ≤ cov Q and Q ≤ cov R, let x ∈ R, we prove that x P P x P . If {x Q , x Q } ⊆ P , then x P = x Q and x P = x Q , but Q ≤ cov R, thus x Q Q x Q ,
and thus, a fortiori,

x P P x P . So suppose, from now on, that {x Q , x Q } ⊆ P , say x Q / ∈ P . If (x Q ) P x, then, as x, (x Q ) P ≤ x Q , as P ≤ int R (proved in (i))
, and by Lemma 3.4, we get x P ≤ x Q , so x Q ∈ P , a contradiction. Hence (x Q ) P ≤ x, but (x Q ) P lies above x P and belongs to P , and so (x Q ) P = x P . As P ≤ cov Q, we get

x P = (x Q ) P P (x Q ) P = x P .
Example 4.4. The following example shows that interval extensions do not compose. We let K, L, and M the lattices diagrammed on Figure 4

.1. Then K ≤ int L and L ≤ int M , however K ≤ int M , as x ≤ y and x ≡ K y while x K y K . In this example, K ≤ cov L and L ≤ cov M . 0 0 0 1 1 1 a a a x y y K L M Figure 4.1.
Interval extensions do not compose.

Strong amalgams of normal diagrams of posets

In this section we shall deal with families of posets indexed by meet-semilattices.

Definition 5.1. A normal diagram of posets consists of a family Q = Q i | i ∈ Λ
of posets, indexed by a meet-semilattice Λ, such that the following conditions hold (we denote by ≤ i the partial ordering of Q i , for all i ∈ Λ):

(1

) Q i is a sub-poset of Q j for all i ≤ j in Λ. ( 2
) Q i ∩ Q j = Q i∧j (set-theoretically!) for all i, j ∈ Λ. (3) For all i, j, k ∈ Λ such that i, j ≤ k and all x, y ∈ Q i × Q j , if x ≤ k y, then there exists z ∈ Q i∧j such that x ≤ i z and z ≤ j y. Furthermore, we say that Q is a normal interval diagram of posets, if Q j is an interval extension of Q i for all i ≤ j in Λ. Let Q = Q i | i ∈ Λ be a normal diagram of posets and set P = (Q i | i ∈ Λ). For x, y ∈ P , let x ≤ y hold, if there are i, j ∈ Λ and z ∈ Q i∧j such that x ∈ Q i , y ∈ Q j ,
and x ≤ i z ≤ j y. As the following lemma shows, this definition is independent of the chosen pair i, j such that x ∈ Q i and y ∈ Q j . Lemma 5.2. For all x, y ∈ P and all i, j ∈ Λ such that x ∈ Q i and y ∈ Q j , x ≤ y iff there exists z ∈ Q i∧j such that x ≤ i z ≤ j y.

Proof. The given condition implies, by definition, that x ≤ y. Conversely, suppose that x ≤ y, and fix i ′ , j ′ ∈ Λ and

z ′ ∈ Q i ′ ∧j ′ such that x ∈ Q i ′ , y ∈ Q j ′ , and x ≤ i ′ z ′ ≤ j ′ y. As x ∈ Q i∧i ′ , z ′ ∈ Q i ′ ∧j ′ , and x ≤ i ′ z ′ , there exists t ∈ Q i∧i ′ ∧j ′ such that x ≤ i∧i ′ t ≤ i ′ ∧j ′ z ′ . As t ∈ Q i∧i ′ ∧j ′ , y ∈ Q j∧j ′ , and t ≤ j ′ y, there exists z ∈ Q i∧i ′ ∧j∧j ′ such that t ≤ i∧i ′ ∧j ′ z ≤ j∧j ′ y. In particular, z ∈ Q i∧j and x ≤ i z ≤ j y.
Lemma 5.3. The binary relation ≤ defined above is a partial ordering of P . Furthermore, Q i is a sub-poset of P for all i ∈ Λ.

Proof. Reflexivity is obvious. Now let x, y ∈ P such that x ≤ y and y ≤ x. Fix i, j ∈ Λ such that x ∈ Q i and y ∈ Q j . By Lemma 5.2, there are u, v ∈ Q i∧j such that x ≤ i u ≤ j y ≤ j v ≤ i x. Hence u ≤ i∧j v ≤ i∧j u, and so u = v, and therefore

x = u = y. Now let x ≤ y ≤ z in P , and fix i, j, k ∈ Λ such that x ∈ Q i , y ∈ Q j , and z ∈ Q k . By Lemma 5.2, there are u ∈ Q i∧j and v ∈ Q j∧k such that x ≤ i u ≤ j y and y ≤ j v ≤ k z. As u ≤ j v, there exists w ∈ Q i∧j∧k such that u ≤ i∧j w ≤ j∧k v.
Hence x ≤ i w ≤ k z, and so x ≤ z. Therefore, ≤ is a partial ordering on P .

Finally, let i ∈ Λ and let x, y

∈ Q i . If x ≤ i y, then x ≤ y trivially. Conversely, if x ≤ y, then, by Lemma 5.2, there exists z ∈ Q i such that x ≤ i z ≤ i y, whence x ≤ i y. Therefore, x ≤ y iff x ≤ i y.
Hence, from now on, we shall most of the time drop the index i in ≤ i , for i ∈ Λ. We shall call the poset P the strong amalgam of

Q i | i ∈ Λ . Lemma 5.4. Let Q = Q i | i ∈ Λ be a normal diagram of posets, with strong amalgam P = (Q i | i ∈ Λ).
Then the following statements hold:

(i) If i ≤ j implies that Q i ≤ rc Q j for all i, j ∈ Λ, then Q i ≤ rc P for all i ∈ Λ. (ii) If i ≤ j implies that Q i ≤ int Q j for all i, j ∈ Λ, then Q i ≤ int P for all i ∈ Λ.
Proof. (i). Let x ∈ P , say x ∈ Q j , for j ∈ Λ, and let i ∈ Λ. By Lemma 5.2, every element of Q i below x lies below x Qi∧j ; hence x Qi exists, and it is equal to x Qi∧j . Dually, x Qi exists, and it is equal to x Qi∧j . In particular, Q i ≤ rc P .

To ease notation, we shall from now on use the abbreviations x (i) = x Qi and x (i) = x Qi , for all x ∈ P and all i ∈ Λ. Similarly, we shall abbreviate x ≡ Qi y by x ≡ i y and x ≪ Qi y by x ≪ i y, for all x, y ∈ P and all i ∈ Λ. (ii). First, it follows from (i) above that Q i ≤ rc P . Now let x, y ∈ P such that x ≤ y, we prove that either x ≡ i y or x ≪ i y. Fix j, k ∈ Λ such that x ∈ Q j and y ∈ Q k . Suppose first that j = k. As Q i∧j ≤ int Q j , either x ≡ i∧j y or x ≪ i∧j y. As t (i) = t (i∧j) and t (i) = t (i∧j) for all t ∈ {x, y} (see proof of (i) above), this amounts to saying that either x ≡ i y or x ≪ i y, so we are done.

In the general case, there exists, by Lemma 5.2, z ∈ Q j∧k such that x ≤ j z ≤ k y. Applying the paragraph above to the pairs x, z and z, y , we obtain that either x ≡ i z or x ≪ i z, and either z ≡ i y or z ≪ i y. If x ≡ i z and z ≡ i y, then x ≡ i y. In all other three cases, x ≪ i y.

Proposition 5.5. Let Q = Q i | i ∈ Λ be a normal interval diagram of lattices.
Then the following statements hold:

(i) The strong amalgam

P = (Q i | i ∈ Λ) is a lattice. (ii) Q i is a sublattice of P for all i ∈ Λ. (iii) For all i, j ∈ Λ and all incomparable a ∈ Q i and b ∈ Q j , both a ∨ b and a ∧ b belong to Q i∧j .
Proof. We denote by ∨ k (resp., ∧ k ) the join (resp., meet) operation in Q k , for all k ∈ Λ. We first establish a claim.

Claim. Let i, j, k ∈ Λ with i, j ≤ k and let x, y ∈ Q i × Q j . If x y, then both x ∨ k y and x ∧ k y belong to Q i∧j .
Proof of Claim. If x ≡ i y, then, as x ∈ Q i , we obtain that x = y, which contradicts the assumption that x y; hence x ≡ i y.

As Q i ≤ int Q k , it follows from Lemma 3.5 that x∨ k y = x (i) ∨ k y (i)
, and thus, as

Q i is a sublattice of Q k , x∨ k y ∈ Q i . Similarly, x ∨ k y ∈ Q j , and hence x ∨ k y ∈ Q i∧j .
The proof for the meet is dual.

Claim.

Now we establish (iii). We give the proof for the meet; the proof for the join is dual. Suppose that a b, let i, j ∈ Λ such that a ∈ Q i and b ∈ Q j , and put

c = a (i∧j) ∧ i∧j b (i∧j) . Of course, c ≤ a, b. Now let x ∈ P such that x ≤ a, b, we prove that x ≤ c. Pick k ∈ Λ such that x ∈ Q k and set m = i∧j ∧k. By Lemma 5.2, there are a ′ ∈ Q i∧k and b ′ ∈ Q j∧k such that x ≤ a ′ ≤ a and x ≤ b ′ ≤ b. Suppose first that a ′ b ′ . It follows from the Claim above that a ′ ∧ k b ′ belongs to Q m , thus to Q i∧j . As x ≤ a ′ ∧ k b ′ ≤ a, b, we obtain that x ≤ a ′ ∧ k b ′ ≤ c.
Suppose now that a ′ ∼ b ′ , say a ′ ≤ b ′ . By Lemma 5.2, there exists a ′′ ∈ Q m such that a ′ ≤ a ′′ ≤ b ′ . If a ′′ ≤ a, then (as a ′′ ≤ b and a ′′ ∈ Q i∧j ) a ′′ ≤ c, and so x ≤ c. As a a ′′ (for a b), the only possibility left is a a ′′ . By the Claim above, a ∧ i a ′′ belongs to Q m , but this element lies below both a and b, thus, again, below c. As x ≤ a ′ ≤ a ∧ i a ′′ , we thus obtain that x ≤ c.

Hence c is the meet of {a, b} in P , and so P is a meet-semilattice. Dually, P is a join-semilattice; this establishes (i). In case a, b ∈ Q i , we take i = j, and thus c = a ∧ i b, and so we obtain that Q i is a meet-subsemilattice of P . Dually, Q i is a join-subsemilattice of P ; this establishes (ii).

Lower finite normal interval diagrams; the elements x

• and x • For a normal diagram Q = Q i | i ∈ Λ of posets, it follows from Definition 5.1(2) that for every element x of P = (Q i | i ∈ Λ), the set {i ∈ Λ | x ∈ Q i } is closed under finite meets.
In particular, in case Λ is lower finite (cf. Subsection 1.3; we shall say that the diagram Q is lower finite), there exists a least i ∈ Λ such that x ∈ Q i . We shall denote this element by ν(x), and we shall call the map ν : P → Λ the valuation associated with the normal diagram Q.

In this section, we shall fix a lower finite normal interval diagram

Q = Q i | i ∈ Λ of lattices, with strong amalgam P = (Q i | i ∈ Λ).
It follows from Proposition 5.5 that P is a lattice. Lemma 6.1. For all x ∈ P \Q 0 , there exist a largest x • < x such that ν(x • ) < ν(x) and a least x • > x such that ν(x • ) < ν(x). Furthermore, the following hold:

(i) ν(x • ) and ν(x • ) are comparable. (ii) Putting i = max{ν(x • ), ν(x • )}, both equalities x • = x (i) and x • = x (i)
hold. (iii) For all y ∈ P such that ν(x) ν(y), x ≤ y implies that x • ≤ y, and y ≤ x implies that y ≤ x • .

Proof.

Put Λ ′ = {i ∈ Λ | i < ν(x)} and X = {x (i) | i ∈ Λ ′ }. As x / ∈ Q 0 , the set X is nonempty. As X is finite (because Λ ′ is finite)
, it has a join in P , say x • . It follows easily from Proposition 5.5 that ν(x • ) < ν(x), whence x • is the largest element of X. The proof of the existence of x • is similar.

As

x • ≤ x • , there exists y ∈ Q ν(x•)∧ν(x • ) such that x • ≤ y ≤ x • . If
x ≤ y, then, as ν(y) < ν(x), we get y = x • , and thus ν(x • ) ≤ ν(x • ). Similarly, if y ≤ x, then y = x • , and thus ν(x • ) ≤ ν(x • ). Now suppose that x y. It follows from Proposition 5.5 that ν(x ∧ y), ν(x ∨ y) ≤ ν(y) < ν(x), thus, as x ∨ y ≤ x • and x • ≤ x ∧ y, we get x ∨ y = x • and x ∧ y = x • . By using the first equality, we get ν(x • ) = ν(x ∨ y) ≤ ν(y) ≤ ν(x • ), while by using the second one, we get ν(x • ) ≤ ν(x • ), and hence ν(x • ) = ν(x • ). This takes care of (i).

Now we deal with (ii). From ν(x (i) ), ν(

x (i) ) ≤ i < ν(x) it follows that x (i) ≤ x • and x • ≤ x (i) . As both x • and x • belong to Q i , we get x (i) = x • and x (i) = x • .
Let y ∈ P with ν(x) ν(y). If x ≤ y, then there exists z ∈ Q ν(x)∧ν(y) such that x ≤ z ≤ y, but ν(z) < ν(x), thus x • ≤ z, and so x • ≤ y. The proof for x • is dual. This takes care of (iii).

Extending a p-measure to an interval extension

Recall that we introduced p-measures and p-measured posets in Definition 1.1. We shall define the distance function on a p-measured poset P by x = y P = max{x, y} min{x, y} P , for all comparable x, y ∈ P.

Obviously, the distance function on P satisfies the triangular inequality x = z P ≤ x = y P ∨ y = z P , for all pairwise comparable x, y, z ∈ P . Furthermore, the equality holds for x ≥ y ≥ z.

For ∨, 0 -semilattices S and T and a ∨, 0 -homomorphism ϕ : S → T , a Svalued p-measured poset P , and a T -valued p-measured poset Q, we shall say that Q extends P with respect to ϕ, if P is a sub-poset of Q and

x y Q = ϕ ( x y P ) ,
for all x, y ∈ P.

We shall then say that the inclusion map from P into Q, together with ϕ, form a morphism from P to Q, and define diagrams of p-measured posets accordingly.

(Obviously, we could have defined morphisms more generally by involving an orderembedding from P into Q, but the present definition is sufficient, and more convenient, for our purposes.) Until Lemma 7.8, we fix a distributive lattice D with zero and a D-valued pmeasured poset P . We are given an interval extension Q of P in which each interval of Q of the form [x P , x P ], for x ∈ Q, is endowed with a p-measure --[xP ,x P ] . We assume compatibility between those p-measures, in the sense that x P = x P P = x P = x P [xP ,x P ] , for all x ∈ Q. We define a map --Q from Q × Q to D, by setting x y Q = x y [xP ,x P ] in case x ≡ P y, and x y Q = x P y P P ∧ x P y P P ∨ x = x P [xP ,x P ] ∧ x P y P P ∨ y P = y [yP ,y P ] ∧ x P y P P ∨ x = x P [xP ,x P ] ∨ y P = y [yP ,y P ] , (7.1) if x ≡ P y.

The proof of the following lemma is straightforward.

Lemma 7.1. The new map --extends the original one --P , and also all maps of the form --[xP ,x P ] , for x ∈ Q. Furthermore, for all x, y ∈ Q, the following statements hold: (i) x ∈ P implies that x y Q = x y P P ∧ x y P P ∨ y P = y [yP ,y P ] ; (ii) y ∈ P implies that x y Q = x P y P ∧ x P y P ∨ x = x P [xP ,x P ] . Lemma 7.2. x ≤ y implies that x y Q = 0, for all x, y ∈ Q.

Proof. If x ≡ P y, then x y Q = x y [xP ,x P ] = 0. If x ≡ P y, then, as P ≤ int Q, we get x P ≤ y P , thus x P y P P = 0, and so x y Q = 0.

Lemma 7.3. The inequality x z Q ≤ x y Q ∨ y z Q holds, for all x, y, z ∈ Q two of which belong to P .
Proof. Suppose first that x, y ∈ P . By applying Lemma 7.1 to x z Q and y z Q , we reduce the problem to the two inequalities x z P P ≤ x y P ∧ y z P P , x z P P ≤ x y P ∧ y z P P , which hold by assumption. The proof is dual for the case y, z ∈ P .

Suppose now that x, z ∈ P . By applying Lemma 7.1 to x y Q and y z Q , we reduce the problem to four inequalities, which we proceed to verify:

x z P ≤ x y P P ∨ y P z P ≤ x y P P ∨ y P z P .

x z P ≤ x y P P ∨ y P z P ≤ x y P P ∨ y P z P ∨ y = y P [yP ,y P ] .

x z P ≤ x y P P ∨ y P z P ≤ x y P P ∨ y P z P ∨ y P = y [yP ,y P ] .

x z P ≤ x y P P ∨ y P = y P P ∨ y P z P = x y P P ∨ y P = y [yP ,y P ] ∨ y = y P [yP ,y P ] ∨ y P z P . Hence x z P ≤ x y Q ∨ y z Q .

Lemma 7.4. The Boolean value x y Q lies below each of the semilattice elements x P y P P , x P y P P ∨ x = x P [xP ,x P ] , x P y P P ∨ y P = y [yP ,y P ] , and x P y P P ∨ x = x P [xP ,x P ] ∨ y P = y [yP ,y P ] , for all x, y ∈ Q.

Proof. This is obvious by the definition of x y Q in case x ≡ P y. If x ≡ P y, then, putting u = x P = y P and v = x P = y P , the four semilattice elements in the statement above are respectively equal to

v = u P , x = u [u,v] , v = y [u,v] , and x = u [u,v] ∨ v = y [u,v] . As v = u P = v = u [u,v] , we need to prove that x y [u,v] lies below both x = u [u,v] and v = y [u,v] , which is obvious (for example, x y [u,v] ≤ x u [u,v] ∨ u y [u,v] = x = u [u,v] ). Lemma 7.5. The inequalities x P y Q ≤ x y Q ≤ x P y Q and x y P Q ≤ x y Q ≤ x y P Q hold, for all x, y ∈ Q.
Proof. As the two sets of inequalities are dual, it suffices to prove that

x P y Q ≤ x y Q ≤ x P y Q .
As the conclusion is obvious in case x ≡ P y, it suffices to consider the case where x ≡ P y. As, by Lemma 7.1, the equality

x P y Q = x P y P P ∧ x P y P P ∨ y P = y [yP ,y P ]
holds, it follows from Lemma 7.4 that x y Q ≤ x P y Q . Moreover, again by Lemma 7.1, the equality x P y Q = x P y P P ∧ x P y P P ∨ y P = y [yP ,y P ] holds, and so x P y Q lies below each of the four meetands defining x y Q on the right hand side of (7.1), and hence

x P y Q ≤ x y Q . Lemma 7.6. The inequalities x y Q ≤ x P y Q ∨ x = x P [xP ,x P ] and x y Q ≤ x y P Q ∨ y P = y [yP ,y P ] hold, for all x, y ∈ Q.
Proof. By symmetry, it suffices to prove the first inequality. Using the expression of x P y Q given by Lemma 7.1(i), we reduce the problem to the following two inequalities,

x y Q ≤ x P y P P ∨ x = x P [xP ,x P ] , x y Q ≤ x P y P P ∨ x = x P [xP ,x P ] ∨ y P = y [yP ,y P ] ,
that follow immediately from Lemma 7.4.

Lemma 7.7. The inequalities x P y Q ≤ x P = x [xP ,x P ] ∨ x y Q and x y P Q ≤ y = y P [yP ,y P ] ∨ x y Q hold, for all x, y ∈ Q.

Proof. By symmetry, it suffices to prove the first inequality. Suppose first that x ≡ P y, put u = x P = y P and v = x P = y P . We need to prove that

v = y Q ≤ v = x Q ∨ x y [u,v] , which is obvious since v = y Q = v = y [u,v] and v = x Q = v = x [u,v] .
Now suppose that x ≡ P y. As in (7.1), x y Q is the meet of four meetands, so the first inequality reduces to four inequalities, which we proceed to prove:

x P y Q ≤ x P y P P (by Lemma 7.4)

≤ x P = x Q ∨ x y P Q (by Lemma 7.3) ≤ x P = x [xP ,
x P ] ∨ x P y P P (by Lemma 7.5).

(We have used the easy observation that x P = x Q = x P = x [xP ,x P ] .)

x P y Q ≤ x P y P P (by Lemma 7.5) ≤ x P = x P P ∨ x P y P P = x P = x [xP ,x P ] ∨ x P y P P ∨ x = x P [xP ,x P ] .

x P y Q ≤ x P y P P ∨ y P = y Q (by Lemma 7.3)

≤ x P = x [xP ,x P ] ∨ x P y P P ∨ y P = y [yP ,y P ] .
x P y Q ≤ x P y P P ∨ y P = y Q (by Lemma 7.3) ≤ x P = x P P ∨ x P y P P ∨ y P = y [yP ,y P ] = x P = x [xP ,x P ] ∨ x P y P P ∨ x = x P [xP ,x P ] ∨ y P = y [yP ,y P ] , which completes the proof of the inequality

x P y Q ≤ x P = x [xP ,x P ] ∨ x y Q .

The proof of the inequality x y

P Q ≤ y = y P [yP ,y P ] ∨ x y Q is dual. Lemma 7.8. The inequality x z Q ≤ x y Q ∨ y z Q holds, for all x, y, z ∈ Q.
Proof. This is obvious in case x ≡ P y ≡ P z, as --[xP ,x P ] is a p-measure. So suppose that either x ≡ P y or y ≡ P z, say x ≡ P y. Expressing the Boolean value x y Q as in (7.1), we reduce the problem to four inequalities, that we proceed to prove: This completes the proof.

x z Q ≤ x P z Q (by
So we have reached the following result.

Proposition 7.9. Let D be a distributive lattice with zero, let P be a D-valued p-measured poset, and let Q be an interval extension of P in which each interval of Q of the form [x P , x P ], for x ∈ Q, is endowed with a p-measure --[xP ,x P ] such that x P = x P P = x P = x P [xP ,x P ] for all x ∈ Q. Then there exists a common extension of all p-measures --P and --[xP ,x P ] , for x ∈ Q, to a p-measure on Q, given by (7.1) on pairs x, y such that x ≡ P y.

Doubling extensions; the conditions (DB1) and (DB2)

For a poset Λ and a Λ-indexed diagram S = S i , ϕ i,j | i ≤ j in Λ of ∨, 0semilattices and ∨, 0 -homomorphisms, we shall say that a Λ-indexed diagram

Q i | i ∈ Λ of p-measured posets is S-valued, if Q i is S i -valued and Q j extends Q i with respect to ϕ i,j for all i ≤ j in Λ.
We shall also use the convention of notation and terminology that consists of extending to p-measured posets the notions defined for posets, by restricting them to the underlying posets and stating that the poset extensions involved preserve the corresponding p-measures. For example, we say that a p-measured poset Q is an interval extension of a p-measured poset P , in notation P ≤ int Q, if Q extends P and the underlying posets (cf. Notation 1.2) satisfy P ≤ int Q. In particular, a normal interval diagram of p-measured lattices is a diagram of p-measured lattices whose underlying posets form a normal interval diagram. Definition 8.1. Let P and Q be p-measured posets such that P ≤ rc Q. We say that Q is a doubling extension of P , in notation P ≤ db Q, if x = x P ∼ x P = x for all x ∈ Q. Equivalently, either x P = x P = x = x P or x P = x P = x P = x , for all x ∈ Q.

The following lemma shows that under mild assumptions, doubling extensions are transitive. Lemma 8.2. Let P , Q, and R be p-measured posets. If P ≤ rc Q ≤ rc R, P ≤ int R, and P ≤ db Q ≤ db R, then P ≤ db R.

Proof. Let x ∈ R, we prove x = x P ∼ x P = x . As Q ≤ db R, we get x = x Q ∼ x Q = x . Hence, if {x Q , x Q } ⊆ P , then x P = x Q and x P = x Q , thus we are done. Suppose that {x Q , x Q } ⊆ P , say x Q / ∈ P . As P ≤ int R and x ∼ x Q , it follows from Lemma 3.6 that x ∼ (x Q ) P . If x ≤ (x Q ) P , then, as (x Q ) P ≤ x Q and (x Q ) P belongs to P , we get x Q = (x Q ) P ∈ P , a contradiction; hence (x Q ) P ≤ x. As x P ≤ (x Q ) P and (x Q ) P ∈ P , we get (x Q ) P = x P . As P ≤ db Q, we get x P = x Q ∼ x Q = x P . But this also holds trivially in case x Q ∈ P , so it holds in every case. So we have proved the following:

x P = x Q ∼ x Q = x P . (8.1)
The dual argument gives

x Q = x P ∼ x P = x Q . (8.2) If x P = x Q ≤ x Q =
x P , then we get x Q = x P = x P = x P , and thus x = x P = x P = x P , and we are done. Dually, the same conclusion follows from x Q = x P ≤ x P = x Q . By (8.1) and (8.2), it remains to consider the case where both inequalities

x Q = x P ≤ x P = x Q and x P = x Q ≤ x Q = x P hold, in which case x Q = x P = x P = x Q = x P = x P . (8.3) From Q ≤ db R it follows that x Q = x ∼ x = x Q . Suppose, for example, that x = x Q ≤ x Q = x . Hence x Q = x = x Q =
x Q , and we get

x P = x = x P = x Q ∨ x Q = x = x P = x Q ∨ x Q = x Q = x P = x Q = x P = x P (see (8.3)) ≥ x = x P .
From now on until the end of this section, we shall fix a finite lattice Λ with largest element ℓ, a Λ-indexed diagram D = D i , ϕ i,j | i ≤ j in Λ of distributive lattices with zero and ∨, 0 -homomorphisms, a D↾ <ℓ -valued normal interval diagram Q i | i < ℓ of p-measured lattices. In addition, we assume that the following statements hold:

(DB1) Q j is a doubling extension of Q i for all i ≤ j < ℓ. (DB2) For all i < ℓ and all x, y

∈ Q i with ν(x) ν(y), x = x • Q i = x • = x • Q i implies that x y Q i = x • y Q i and x • = x Q i = x • = x • Q i implies that y x Q i = y x • Q i .
As usual, we denote by

P = (Q i | i < ℓ) the strong amalgam of Q i | i < ℓ . Remark 8.3. It suffices to verify (DB2) in case x y. Indeed, let x, y ∈ Q i such that ν(x)
ν(y) and x = x • = x • = x • (to ease the notation, we drop the indices Q i ). If x ≤ y, then, by Lemma 6.1, x • ≤ y, thus x y = x • y = 0. If y ≤ x, then, again by Lemma 6.1, y ≤ x • , and so

x y = x = x • ∨ x • = y (because y ≤ x • ≤ x) = x • = x • ∨ x • = y (because x • = x • = x = x • ) = x • y .
The proof that x ∼ y and ν(x) ν(y) and

x • = x = x • = x • implies that y x = y x • is dual.
Notation 8.4. We add a largest element, denoted by 1, to D ℓ , and for all x, y ∈ P , we define an element [[x y]] of D ℓ ∪ {1} as follows:

[[x y]] = ϕ i,ℓ x y Q i , if ν(x) ∨ ν(y) ≤ i < ℓ, 1, otherwise. (8.4)
It is obvious that the value of [[x y]] defined in the first case is independent of the choice of i such that ν(x) ∨ ν(y) ≤ i < ℓ. We also put

[[x = y]] = [[max{x, y} min{x, y}]],
for all comparable x, y ∈ P.

Lemma 8.5. The elements [[x = x (i) ]] and [[x (i) = x]] are comparable, for all x ∈ P and all i < ℓ. Furthermore,

[[x • = x]] ∼ [[x = x • ]] for all x ∈ P \ Q 0 .
Proof. Let x ∈ P . As x ∈ Q j for some j < ℓ, we get x (i) = x (i∧j) and

x (i) = x (i∧j) (cf. Lemma 5.4(i)). As Q i∧j ≤ db Q j , we get x = x (i∧j) Q j ∼ x (i∧j) = x Q j , that is, x = x (i) Q j ∼ x (i) = x Q j ,
and thus, applying ϕ j,ℓ , we obtain the relation

[[x = x (i) ]] ∼ [[x (i) = x]].
It follows from Lemma 6.1 that ν(x • ) and ν(x • ) are comparable and that, if i denotes their maximum, then x • = x (i) and x • = x (i) . By applying the result of the previous paragraph, we obtain [[x

• = x]] ∼ [[x = x • ]].

Now we put

P ⊕ = {x ∈ P \ Q 0 | [[x = x • ]] = [[x • = x • ]]}, P ⊖ = {x ∈ P \ Q 0 | [[x • = x]] = [[x • = x • ]]}. If x belongs to Q i \ Q 0 , then x • , x • ∈ Q i . Hence, both [[x = x • ]] and [[x • = x]]
are evaluated by the formula giving the case ν(x) ∨ ν(y) < ℓ of (8.4). Therefore, it follows from Lemma 8.5 that P \ Q 0 = P ⊕ ∪ P ⊖ .

Strong amalgams of p-measured posets; from [[x y]] to x y

From now on until Lemma 9.12, we shall fix a finite lattice Λ with largest element ℓ, a Λ-indexed diagram D = D i , ϕ i,j | i ≤ j in Λ of finite distributive lattices and ∨, 0 -homomorphisms, a D↾ <ℓ -valued normal interval diagram Q i | i < ℓ of p-measured lattices. Furthermore, we assume that the conditions (DB1) and (DB2) introduced in Section 8 are satisfied.

We denote by P the strong amalgam of Q i | i < ℓ and by ρ(x) the height of ν(x) in Λ, for all x ∈ P . Lemma 9.1. For every positive integer n and all elements x 0 , x 1 , . . . ,

x n ∈ P , ν(x 0 ) ∨ ν(x n ) < ℓ implies that [[x 0 x n ]] ≤ i<n [[x i x i+1 ]].
Proof. We argue by induction on the pair n, n k=0 ρ(x k ) , ordered lexicographically. The conclusion is trivial for n = 1. Now suppose that n = 2. If either ν(x 0 ) ∨ ν(x 1 ) = ℓ or ν(x 1 ) ∨ ν(x 2 ) = ℓ, then the right hand side of the desired inequality is equal to 1 and we are done; so suppose that ν(x 0 ) ∨ ν(x 1 ), ν(x 1 ) ∨ ν(x 2 ) < ℓ. If ν(x 1 ) ≤ ν(x 0 ) ∨ ν(x 2 ), then, putting k = ν(x 0 ) ∨ ν(x 2 ) (which is smaller than ℓ), all the Boolean values under consideration are images under ϕ k,ℓ of the corresponding Boolean values in Q k , so the conclusion follows from the inequality

x 0 x 2 Q k ≤ x 0 x 1 Q k ∨ x 1 x 2 Q k (
we will often encounter this kind of reduction, and we will summarize it by "everything happens below level k"). Now suppose that ν(x 1 ) ν(x 0 ) ∨ ν(x 2 ). In particular, x 1 / ∈ Q 0 and ν(x 1 ) ν(x 0 ), ν(x 2 ). By Lemma 8.5, x 1 belongs to P ⊕ ∪ P ⊖ . If

x 1 ∈ P ⊕ , then, as ν(x 1 ) ∨ ν(x 2 ) < ℓ and by (DB2), [[x 1 x 2 ]] = [[(x 1 ) • x 2 ]], hence [[x 0 x 2 ]] ≤ [[x 0 (x 1 ) • ]] ∨ [[(x 1 ) • x 2 ]] (by the induction hypothesis) ≤ [[x 0 x 1 ]] ∨ [[x 1 x 2 ]] (because [[x 0 (x 1 ) • ]] ≤ [[x 0 x 1 ]])
so we are done. The proof is symmetric in case x 1 ∈ P ⊖ . This concludes the case where n = 2. Now assume that n ≥ 3. It ν(x i ) ∨ ν(x i+1 ) = ℓ for some i < n, then the right hand side of the desired inequality is equal to 1 and we are done; so suppose that ν(x i ) ∨ ν(x i+1 ) < ℓ for all i < n. Suppose that there are i, j such that 0

≤ i ≤ j ≤ n and 2 ≤ j -i < n such that ν(x i ) ∨ ν(x j ) < ℓ. It follows from the induction hypothesis that [[x i x j ]] ≤ i≤k<j [[x k x k+1 ]].
Hence, using again the induction hypothesis, we get

[[x 0 x n ]] ≤ k<i [[x k x k+1 ]] ∨ [[x i x j ]] ∨ j≤k<n [[x k x k+1 ]] ≤ k<n [[x k x k+1 ]] ,
so we are done again. Hence suppose that 0 ≤ i ≤ j ≤ n and 2 ≤ j -i < n implies that ν(x i ) ∨ ν(x j ) = ℓ, for all i, j. As ν(x 1 ) ∨ ν(x n ) = ℓ while ν(x 0 ) ∨ ν(x n ) < ℓ (we use here the assumption that n ≥ 3), we get ν(x 1 ) ν(x 0 ). As ν(x 2 )∨ν(x 3 ) < ℓ and ν(x 1 ) ∨ ν(x 3 ) = ℓ, we get ν(x 1 ) ν(x 2 ). Hence, if x 1 ∈ P ⊕ , then, as ν(x 1 ) ν(x 2 ) and by (DB2), [[x 1

x

2 ]] = [[(x 1 ) • x 2 ]],
and hence, by using the induction hypothesis and the obvious inequality

[[x 0 (x 1 ) • ]] ≤ [[x 0 x 1 ]] ("everything there happens below level ν(x 0 ) ∨ ν(x 1 )"), we get [[x 0 x n ]] ≤ [[x 0 (x 1 ) • ]] ∨ [[(x 1 ) • x 2 ]] ∨ 2≤i<n [[x i x i+1 ]] ≤ k<n [[x k x k+1 ]] ,
so we are done. If x 1 ∈ P ⊖ , then, as ν(x 1 ) ν(x 0 ) and by (DB2), [[x 0

x 1 ]] = [[x 0 (x 1 ) • ]]
, hence, by using the induction hypothesis and the obvious inequality

[[(x 1 ) • x 2 ]] ≤ [[x 1 x 2 ]], we get [[x 0 x n ]] ≤ [[x 0 (x 1 ) • ]] ∨ [[(x 1 ) • x 2 ]] ∨ 2≤i<n [[x i x i+1 ]] ≤ k<n [[x k x k+1 ]] ,
so we are done. As x 1 ∈ P ⊕ ∪ P ⊖ (cf. Lemma 8.5), this completes the induction step.

Notation 9.2. We put

P (z) = {t ∈ P | ν(t) < ν(z)}, P ⊕ (z) = P (z) ∩ P ⊕ , P ⊖ (z) = P (z) ∩ P ⊖ ,
for all z ∈ P . Furthermore, for all x, y ∈ P , we define

x y + = [[x t]] ∨ [[t y]] | t ∈ P (y) , (9.1)
x y -= [[x t]] ∨ [[t y]] | t ∈ P (x) , (9.2)
x y ± = [[x u]] ∨ [[u v]] ∨ [[v y]] | u, v ∈ P ⊖ (x) × P ⊕ (y) , (9.3)
x y = [[x y]] ∧ x y + ∧ x y -∧ x y ± . (9.4)
(All meets are evaluated in D ℓ , the empty meet being defined as equal to 1.) We observe that the meet on the right hand side of (9.1) may be taken over all t ∈ P (y) such that ν(x) ∨ ν(t) < ℓ: indeed, for all other t ∈ P (y), we get [[x t]] = 1. Similarly, the meet on the right hand side of (9.2) may be taken over all t ∈ P (x) such that ν(t) ∨ ν(y) < ℓ, and the meet on the right hand side of (9.3) may be taken over all u, v ∈ P ⊖ (x) × P ⊕ (y) such that ν(u) ∨ ν(v) < ℓ.

Lemma 9.3. x y ≤ [[x t]] ∨ [[t y]

] for all x, y, t ∈ P .

Proof. We argue by induction on ρ(x) + ρ(y) + ρ(t). If ν(x) ∨ ν(t) = ℓ or ν(t) ∨ ν(y) = ℓ then the right hand side of the desired inequality is equal to 1 so we are done. Suppose, from now on, that ν(x) ∨ ν(t), ν(t) ∨ ν(y) < ℓ. If ν(x) ∨ ν(y) < ℓ, then it follows from Lemma 9.1 (for

n = 2) that [[x y]] ≤ [[x t]] ∨ [[t y]], so we are done as x y ≤ [[x y]]. Now suppose that ν(x) ∨ ν(y) = ℓ. In particular, x, y / ∈ Q 0 . If t ∈ Q 0 , then t ∈ P (y), thus x y ≤ x y + ≤ [[x t]] ∨ [[t y]] .
So suppose that t / ∈ Q 0 . If ν(x) ≤ ν(t), then "everything happens below level ν(t) ∨ ν(y)" (which is smaller than ℓ), so we are done. The conclusion is similar in case ν(y) ≤ ν(t).

So suppose that ν(x), ν(y) ν(t). If ν(t) ≤ ν(y), then ν(t) < ν(y) (because ν(y) ν(t)), thus t ∈ P (y), and thus

x y ≤ x y + ≤ [[x t]] ∨ [[t y]] ,
so we are done. If t ∈ P ⊕ and ν(t) ν(y), then, by (DB2), [[t y]] = [[t • y]], and thus

x y ≤ [[x t • ]] ∨ [[t • y]]
(by the induction hypothesis)

≤ [[x t]] ∨ [[t y]] ,
so we are done again. This covers the case where t ∈ P ⊕ . The proof is symmetric for t ∈ P ⊖ .

Lemma 9.4. x y ≤ [[x u]] ∨ [[u v]] ∨ [[v y]] for all x, y, u, v ∈ P .
Proof. We argue by induction on ρ(x)+ρ(y)+ρ(u)+ρ(v). If either ν(x)∨ν(u) = ℓ or ν(u)∨ν(v) = ℓ or ν(v)∨ν(y) = ℓ, then the right hand side of the desired inequality is equal to 1 and we are done. So suppose that ν(x)∨ν(u), ν(u)∨ν(v), ν(v)∨ν(y) < ℓ.

If ν(x) ∨ ν(v) < ℓ, then, by Lemma 9.1, we get [[x v]] ≤ [[x u]] ∨ [[u v]],
and so

x y ≤ [[x v]] ∨ [[v y]] (by Lemma 9.3) ≤ [[x u]] ∨ [[u v]] ∨ [[v y]] .
The conclusion is similar for ν(u) ∨ ν(y) < ℓ. So suppose that ν(x) ∨ ν(v) = ν(u) ∨ ν(y) = ℓ. In particular, ν(x) ν(u), ν(y) ν(v), and ν(u) ν(v), so x, y, u, v / ∈ Q 0 . Suppose that u ∈ P ⊕ . As ν(u) ν(v) and by (DB2), we get

[[u v]] = [[u • v]], hence x y ≤ [[x u • ]] ∨ [[u • v]] ∨ [[v y]]
(by the induction hypothesis)

≤ [[x u]] ∨ [[u v]] ∨ [[v y]] (because [[x u • ]] ≤ [[x u]]).
Suppose that u ∈ P ⊖ and ν(u

) < ν(x). As ν(x) ν(u), we get ν(u) ν(x), thus [[x u]] = [[x u • ]],
and so

x y ≤ [[x u • ]] ∨ [[u • v]] ∨ [[v y]]
(by the induction hypothesis)

≤ [[x u]] ∨ [[u v]] ∨ [[v y]] (because [[u • v]] ≤ [[u v]]).
The case where either v ∈ P ⊖ or (v ∈ P ⊕ and ν(v) < ν(y) is symmetric. The only remaining case is where u ∈ P ⊖ (x) and v ∈ P ⊕ (y), in which case

x y ≤ x y ± ≤ [[x u]] ∨ [[u v]] ∨ [[v y]].
Consequently, we get the formula

x y = [[x u]] ∨ [[u v]] ∨ [[v y]] | u, v ∈ P ,
x z ≤ [[x u]] ∨ [[u v]] ∨ [[v y]] ∨ [[y z]], (9.6)
for all u, v ∈ P ⊖ (x)

× P ⊕ (y). From ν(v) < ν(y) it follows that [[v z]] ≤ [[v y]] ∨ [[y z]]
("everything there happens below level ν(y) ∨ ν(z)"), and hence

x z ≤ [[x u]] ∨ [[u v]] ∨ [[v z]]
(by Lemma 9.4)

≤ [[x u]] ∨ [[u v]] ∨ [[v y]] ∨ [[y z]],
which completes the proof of (9.6).

Lemma 9.6. x z ≤ x y ∨ y z for all x, y, z ∈ P .

Proof. For elements u, v ∈ P , we get, by three successive applications of Lemma 9.5, the inequalities

x u ≤ x y ∨ [[y u]] ; x v ≤ x u ∨ [[u v]] ; x z ≤ x v ∨ [[v z]] .
Hence, combining these inequalities, we obtain

x z ≤ x y ∨ [[y u]] ∨ [[u v]] ∨ [[v z]] .
Evaluating the meets of both sides over u, v ∈ P and using (the easy direction of) (9.5) yields the desired conclusion.

As a consequence, we obtain the following simple expression of x y .

Corollary 9.7. The Boolean value x y is equal to the meet in D ℓ of all elements of D ℓ of the form

[[x z 1 ]] ∨ [[z 1 z 2 ]] ∨ • • • ∨ [[z n-1 y]] , (9.7)
where n is a natural number and z 0 , z 1 , . . . , z n ∈ P such that z 0 = x, z n = y, and ν(z i ) ∨ ν(z i+1 ) < ℓ for all i < n. Furthermore, it is sufficient to restrict the meet to finite sequences z 0 , z 1 , z 2 , z 3 (so n = 3).

Proof. Denote temporarily by x y * the meet in D ℓ of all elements of D ℓ of the form (9.7). An immediate application of the easy direction of (9.5) yields the inequality x y * ≤ x y . Conversely, for every natural number n and all z 0 , z 1 , . . . , z n ∈ P such that z 0 = x, z n = y, and ν(z i ) ∨ ν(z i+1 ) < ℓ for all i < n,

x y ≤ i<n z i z i+1
(by Lemma 9.6)

≤ i<n [[z i z i+1 ]] (because z i z i+1 ≤ [[z i z i+1 ]]),
which concludes the proof of the first part. The bound n = 3 follows from the easy direction of (9.5).

As an immediate consequence of Lemma 9.1, we obtain that the equality x y = [[x y]] holds for all x, y ∈ P such that ν(x) ∨ ν(y) < ℓ. Hence we obtain the following lemma.

Lemma 9.8. The p-measure - -extends the p-measure - -Q i with respect to ϕ i,ℓ , for all i < ℓ. Definition 9.9. The strong amalgam P = (Q i | i < ℓ), endowed with the pmeasure - -constructed above, will be called the strong amalgam of the family Q i | i < ℓ with respect to D.

So we have reached the main goal of the present section. Proposition 9.10. Let Λ be a finite lattice with largest element ℓ, let D = D i , ϕ i,j | i ≤ j in Λ be a Λ-indexed diagram of finite distributive lattices and ∨, 0 -homomorphisms, and let Q i | i < ℓ be a D↾ <ℓ -valued normal interval diagram of p-measured lattices satisfying (DB1) and (DB2). Then the strong amalgam P of Q i | i < ℓ (see Definition 9.9) is a D ℓ -valued p-measured lattice, which extends Q i with respect to ϕ i,ℓ , for all i < ℓ. Lemma 9.11. Under the assumptions of Proposition 9.10, the p-measured poset P is a doubling extension of Q i for all i < ℓ.

Proof. An immediate consequence of Lemmas 8.5 and 9.8.

The goal of the following lemma is to propagate the assumption (DB2) through the induction process that will appear in the constructions of Theorems 10.1 and 10.2. Lemma 9.12. For all x, y ∈ P , the following statements hold:

(i) (ν(x) ν(y) and x ∈ P ⊕ ) implies that x y = x • y .

(ii) (ν(y) ν(x) and y ∈ P ⊖ ) implies that x y = x y • .

Proof. As (i) and (ii) are dual, it suffices to establish (i). We first claim that for all x ∈ P ⊕ and all y ∈ P , ν(x) ν(y

) implies that [[x • y]] ≤ [[x y]].
Indeed, the equality holds by assumption (DB2) in case ν(x) ∨ ν(y) < ℓ. If ν(x) ∨ ν(y) = ℓ, then [[x y]] = 1 and we are done again. Now let x ∈ P ⊕ and y ∈ P such that ν(x) ν(y), we must prove that x • y lies below [[x y]], x y + , x y -, and x y ± .

x • y ≤ [[x • y]]
(see (9.4))

≤ [[x y]] (as ν(x) ν(y) and by the claim above). Now let t ∈ P (y).

x • y ≤ [[x • t]] ∨ [[t y]] (by Lemma 9.3) ≤ [[x t]] ∨ [[t y]]
(as ν(x) ν(t) and by the claim above).

Evaluating the meets of both sides over t ∈ P ⊕ (y) yields x • y ≤ x y + . A similar (but not symmetric!) proof yields x • y ≤ x y -. Finally, let u ∈ P ⊖ (x) and v ∈ P ⊕ (y). Then

x • y ≤ [[x • u]] ∨ [[u v]] ∨ [[v y]] (by Lemma 9.4) ≤ [[x u]] ∨ [[u v]] ∨ [[v y]
] (as ν(x) ν(u) and by the claim above), hence, evaluating the meets of both sides over u, v ∈ P ⊖ (x) × P ⊕ (y), we get x • y ≤ x y ± , which completes the proof. 10. Constructing a p-measure on a covering, doubling extension of a strong amalgam of lattices Let Λ, D, and Q i | i < ℓ satisfy the assumptions of Proposition 9.10, with strong amalgam P (cf. Definition 9.9). By Proposition 9.10, - -P is a D ℓvalued p-measure on P , which extends each p-measured lattice Q i with respect to the corresponding ∨, 0 -homomorphism ϕ i,ℓ . Now we let Q be a covering extension of P . Furthermore, we assume that each closed interval [x P , x P ] of Q, for x ∈ Q, is endowed with a p-measure --[xP ,x P ] such that

x = x P [xP ,x P ] ∼ x P = x [xP ,x P ] ,
for all x ∈ Q, (10.1)

x P = x P [xP ,x P ] = x P = x P P , for all x ∈ Q. ( 10.2)
(Observe that the notation x P = x P P in (10.2) above does not involve the full definition of the strong amalgam given in Definition 9.9: indeed, from P ≤ cov Q it follows that x P P x P ; as P is the strong amalgam of Q i | i < ℓ , x P and x P belong to some Q i , and so we can just put x P = x P P = ϕ i,ℓ x P = x P Q i , which is independent of the chosen i.)

The goal of the present section is to extend --P to a p-measure on Q such that, setting Q ℓ = Q, the extended diagram Q i | i ≤ ℓ satisfies the assumptions of Proposition 9.10.

We need to verify several points. First, for all i < ℓ, as Q i ≤ int P and P ≤ cov Q, we obtain from Lemma 5.4 that Q i ≤ int Q. Item (3) of Definition 5.1 for the extended diagram Q i | i ≤ ℓ follows from the definition of the ordering of P ℓ (cf. Section 5). Further, the new valuation on the extended diagram Q i | i ≤ ℓ extends the original one (so we shall still denote it by ν), and ν(x) = ℓ for all x ∈ Q \ P . In addition, the elements x • and x • (cf. Lemma 6.1) remain the same for x ∈ P \ Q 0 , while x • = x P and x • = x P for all x ∈ Q \ P . Now we denote by - -Q the p-measure that we constructed in Section 7 (cf. Proposition 7.9), extending --P and all p-measures --[xP ,x P ] , for x ∈ Q-this is made possible by (10.2). It follows from the assumption (10.1) that x P = x Q ∼ x = x P Q for all x ∈ Q; that is, Q is a doubling extension of P . As Q i ≤ int Q and by Lemmas 9.11 and 8.2 (applied to the extensions Q i ≤ P ≤ Q), we obtain that Q is a doubling extension of Q i . This takes care of extending (DB1) to the larger diagram.

It remains to verify that

Q i | i ≤ ℓ satisfies (DB2). So let x, y ∈ Q such that ν(x) ν(y), we need to verify that x = x • Q = x • = x • Q implies that x y Q = x • y Q and x • = x Q = x • = x • Q implies that y x Q = y x • Q .
We prove for example the first statement. From ν(x) ν(y) it follows that y ∈ P . If x ∈ P then we are done by Lemma 9.12, so the remaining case is where x ∈ Q \ P . Observe that x • = x P and x • = x P . As y ∈ P , the Boolean value x y Q is given by Lemma 7.1(ii). Hence proving the inequality x • y Q ≤ x y Q reduces to proving that x P y Q (of course equal to x P y P ) lies below both x P y P and x P y P ∨

x = x P [xP ,x P ] .
The first inequality is a tautology, and the second one is proved as follows:

x P y P ≤ x P = x P P ∨ x P y P (because --P is a p-measure)

= x = x P Q ∨ x P y P (because x = x • Q = x • = x • Q ) = x = x P [xP ,x P ] ∨ x P y P .
As the inequality x y Q ≤ x • y Q always holds, we have proved the equality, and hence the extended diagram Then there exists a D ℓ -valued p-measure on Q extending all p-measures --[xP ,x P ] such that, defining Q ℓ as the corresponding p-measured poset, the extended diagram This result makes it possible to state and prove our main theorem. (i) For all i < j in Λ and all x < y in Q i , there exists z ∈ Q j such that x < z < y. (ii) y = x Q i ∈ J(D i ) ∪ {0}, for all i ∈ Λ and all x, y ∈ Q i such that x ≺ Qi y. (iii) For all i ∈ Λ and all p ∈ J(D i ), there exists x ∈ Q i such that 0 ≺ Qi x and x = 0 Q i = p.

Q i | i ≤ ℓ satisfies (DB2
Q i | i ≤ ℓ is a D-valued
Proof. We construct Q i by induction on the height of i in Λ. After possibly adding a new zero element to Λ, we may assume that D 0 = {0, 1}, so we take Q 0 = {0, 1}, with the p-measure defined by 1 = 0

Q 0 = 1. Put Λ n = {i ∈ Λ | height(i)
Every x ∈ (Q i | i ∈ Λ n ) can be written in the form x, ν(x) , (10.3)
where ν denotes the valuation associated with the diagram Q i | i ∈ Λ n . Let ℓ ∈ Λ n+1 \ Λ n and denote by P ℓ the strong amalgam of Q i | i < ℓ with respect to D given in Definition 9.9. It follows from Proposition 5.5 that P ℓ is a lattice and every Q i , for i < ℓ, is a sublattice of P ℓ . For all x ≺ y in P ℓ such that y = x P ℓ > 0, we put

1 x,y,ℓ = {p ∈ J(D ℓ ) | p ≤ y = x P ℓ }, B x,y,ℓ = P(1 x,y,ℓ ) (the powerset lattice of 1 x,y,ℓ ), Q x,y,ℓ = { X, ∅ | X ⊆ 1 x,y,ℓ } ∪ { 1 x,y,ℓ , Y | Y ⊆ 1 x,y,ℓ }.
Observe that the condition y = x P ℓ > 0 implies that the set 1 x,y,ℓ , that we shall often denote by 1, is nonempty. Also, Q x,y,ℓ is a sublattice of B x,y,ℓ × B x,y,ℓ . Hence Q x,y,ℓ is the ordinal sum of two copies of the Boolean lattice B x,y,ℓ , with the top of the lower copy of B x,y,ℓ (namely, X, ∅ where X = 1 x,y,ℓ ) identified with the bottom of the upper copy of B x,y,ℓ (namely, 1, Y where Y = ∅).

We endow Q x,y,ℓ with the p-measure --x,y,ℓ defined by

X 0 , ∅ X 1 , ∅ x,y,ℓ = (X 0 \ X 1 ) , 1, Y 0 1, Y 1 x,y,ℓ = (Y 0 \ Y 1 ) , X, ∅ 1, Y x,y,ℓ = 0 , 1, Y X, ∅ x,y,ℓ = ∁X ∪ Y ,
(where we put ∁X = 1 x,y,ℓ \ X), for all X, X 0 , X 1 , Y, Y 0 , Y 1 ⊆ 1 (it is easy to verify that this way we get, indeed, a p-measure on Q x,y,ℓ ). Further, we put

Q ′ x,y,ℓ = Q x,y,ℓ \ { ∅, ∅ , 1, 1 } ('truncated Q x,y,ℓ '), Q x,y,ℓ = { t, x, y , ℓ | t ∈ Q ′ x,y,ℓ }, where Q ′
x,y,ℓ is endowed with the restrictions of both the ordering and the p-measure of Q x,y,ℓ and Q x,y,ℓ is endowed with the ordering and p-measure for which the map t → t, x, y , ℓ is a measure-preserving isomorphism. So Q x,y,ℓ is the result of applying to Q x,y,ℓ the following two transformations:

-Remove the top and bottom elements of Q x,y,ℓ ; get Q ′ x,y,ℓ . -Replace t by t, x, y , ℓ , for all t ∈ Q ′

x,y,ℓ ; get Q x,y,ℓ . The latter step (from Q ′

x,y,ℓ to Q x,y,ℓ ) is put there in order to ensure the induction hypothesis (10.3) while making the Q x,y,ℓ s pairwise disjoint.

In case y = x P ℓ = 0, we pick an outside element t x,y,ℓ and we set Q x,y,ℓ = { t x,y,ℓ , ℓ }, the one-element poset. Furthermore, we endow Q x,y,ℓ = {x, y, t x,y,ℓ , ℓ } with the p-measure with constant value 0.

Observe that in any case, Q x,y,ℓ is nonempty.

Put Q ℓ = P ℓ + (Q x,y,ℓ | x ≺ y in P ℓ ) (cf. (3. 3
)). Then (10.3) is maintained at level ℓ, and Q ℓ is an interval extension of P ℓ (cf. Lemma 3.8). In fact, as Q x,y,ℓ is defined only for x ≺ y in P ℓ , the poset Q ℓ is a covering extension of P ℓ (cf. Definition 4.1). We shall still denote by --x,y,ℓ the p-measure on Q x,y,ℓ ∪{x, y} induced by the p-measure on Q x,y,ℓ defined above. As P ℓ is a lattice and [x, y] Q ℓ = Q x,y,ℓ ∪ {x, y} ∼ = Q x,y,ℓ is a lattice for all x ≺ y in P ℓ , it follows from Lemma 3.5 that Q ℓ is a lattice. Now we verify Conditions (10.1) and (10.2) with respect to --P ℓ and all p-measures - x,y,ℓ . Fix x ≺ y in P ℓ and let z ∈ Q x,y,ℓ ; so z P ℓ = x and z P ℓ = y. If y = x P ℓ = 0, then all members of both (10.1) and (10.2) are zero, thus trivializing the corresponding statements. Hence suppose that y = x P ℓ > 0. Condition (10.1) follows immediately from the inequalities

X, ∅ = ∅, ∅ x,y,ℓ = X ≤ y = x P ℓ = 1, 1 = X, ∅ x,y,ℓ , 1, 1 = 1, X x,y,ℓ = ∁X ≤ y = x P ℓ = 1, X = ∅, ∅ x,y,ℓ ,
for all X ⊆ 1 x,y,ℓ . Condition (10.2) follows from the equalities

1, 1 = ∅, ∅ x,y,ℓ = 1 x,y,ℓ = y = x P ℓ .
Hence, by Theorem 10.1, there is a p-measure on Q ℓ , extending all p-measures -x,y,ℓ , such that Q i | i ≤ ℓ is a D ≤ℓ -valued normal interval diagram of p-measured lattices satisfying (DB1) and (DB2). Now we verify Conditions (i)-(iii) of the statement of Theorem 10.2. Let i < ℓ and let x < y in Q i , we prove that x ≺ Q ℓ y. If x ≺ P ℓ y then this is trivial, so suppose that x ≺ P ℓ y. Pick any element z ∈ Q x,y,ℓ (we have seen that Q x,y,ℓ is always nonempty); then x < z < y in Q ℓ . Condition (i) follows.

In order to verify Condition (ii) at level Q ℓ , it suffices to prove that v = u x,y,ℓ belongs to J(D ℓ ) ∪ {0}, for all x ≺ y in P ℓ and all u ≺ v in Q x,y,ℓ . This is trivial in case y = x P ℓ = 0, in which case v = u x,y,ℓ = 0. So suppose that y = x P ℓ > 0. There are a proper subset X of 1 x,y,ℓ and an element p ∈ ∁X such that either (u = X, ∅ and v = X ∪ {p}, ∅ ) or (u = 1, X and v = 1, X ∪ {p} ). In both cases, v = u x,y,ℓ = p belongs to J(D ℓ ). Now we verify Condition (iii). Let p ∈ J(D ℓ ) and pick k ≺ ℓ in Λ. As p ≤ ϕ k,ℓ (1) = (ϕ k,ℓ (q) | q ∈ J(D k )) and p is join-irreducible, there exists q ∈ J(D k ) such that p ≤ ϕ k,ℓ (q). By the induction hypothesis (Condition (iii)), there exists x ∈ Q k such that 0 ≺ Q k x and x = 0 Q k = q. Suppose that there exists y ∈ P ℓ such that 0 < y < x, and let i < ℓ such that y ∈ Q i . As y ≤ x, there exists z ∈ Q i∧k such that y ≤ z ≤ x. As 0 < z ≤ x with z ∈ Q k and 0 ≺ Q k x, we get z = x, and so x ∈ Q i∧k . If i ∧ k < k, then, by Condition (i) on D (n) , we get 0 ≺ Q k x, a contradiction. Therefore, k = i ∧ k ≤ i, but k ≺ ℓ, and thus i = k. As y ∈ Q k , 0 < y < x, and 0 ≺ Q k x, we get again a contradiction. So we have proved that 0 ≺ P ℓ x. As p ≤ ϕ k,ℓ (q) = x = 0 P ℓ , we get p ∈ 1 0,x,ℓ . We consider the element t = {p}, ∅ , 0, x , ℓ of Q 0,x,ℓ (so 0 ≺ t < x in Q ℓ ). We compute t = 0 Q ℓ = {p}, ∅ = ∅, ∅ 0,x,ℓ = p , which completes the verification of Condition (iii) at level ℓ.

In order to verify that Q i | i ∈ Λ n+1 is as required, it remains to verify that Q i | i ∈ Λ n+1 satisfies Item (2) of Definition 5.1. So let i, j ∈ Λ n+1 , we need to verify that Q i ∩ Q j = Q i∧j . This holds by induction hypothesis for i, j ∈ Λ n . As it trivially holds for i = j, we assume that i = j. If height(i) = height(j) = n, then

Q i = P i ∪ (Q x,y,i | x ≺ y in P i ) , (10.4)
Q j = P j ∪ (Q x,y,j | x ≺ y in P j ) , (10.5)

The following easy result shows that distributivity cannot be removed from the assumptions of Corollary 10.4. In the general case, b = (c j | j < n) for a positive integer n and elements c 0 , . . . , c n-1 ∈ Σ. By the above paragraph, there are decompositions c j = c j,0 ∨c j,1 with c j,k ≤ a k for all j < n and k < 2. The elements b k = (c j,k | j < n), for k < 2, are as required.

The following example shows that the conditions (DB1) and (DB2) cannot be removed from the assumptions of Theorem 10. into B q . Set B = B p , ϕ p,q | p ⊆ q in P(3) , B * = B p , ϕ p,q | p ⊆ q in P(3) \ {3} .

Let Q p , for p ∈ Λ * , and P be the lattices diagrammed on Figure 10.1. We observe that Q p | p ∈ Λ * is a normal interval diagram of finite lattices. We endow Q ∅ P 0 0 1 1 with the unique p-measure - -∅ that satisfies 1 = 0 ∅ = 5, the largest element of B ∅ . For i < 3, we endow Q {i} with the unique p-measure --{i} that satisfies x i = 0 {i} = a i and 1 = x i {i} = b i . Finally, for {i, j, k} = 3, it is not hard to verify that there exists a unique p-measure --{i,j} on Q {i,j} such that x i x j {i,j} = c k,1 and x j x i {i,j} = c k,2 .

x 0 x i x i x j x 1 x 2 Q {i} 0 1 Q {i,j} 0
Suppose Relation with the V-distances of [START_REF] Růžička | Distributive congruence lattices of congruencepermutable algebras[END_REF]. The main result of the present paper, Theorem 10.2, is formally similar to [START_REF] Růžička | Distributive congruence lattices of congruencepermutable algebras[END_REF]Theorem 7.1], which states that every distributive ∨, 0 -semilattice is, functorially, the range of a V-distance of type 2 on some set. By definition, for a ∨, 0 -semilattice S, a S-valued distance on a set X is a map δ : X × X → S such that δ(x, x) = 0, δ(x, y) = δ(y, x), and δ(x, z) ≤ δ(x, y) ∨ δ(y, z), for all x, y, z ∈ X. Furthermore, δ satisfies the V-condition of type 2, if for all a, b ∈ S and all x, y ∈ X, if δ(x, y) = a ∨ b, then there are u, v ∈ X such that δ(x, u) ∨ δ(v, y) ≤ a and δ(u, v) ≤ b. (The 'V-condition' is named so after Hans Dobbertin's work in [START_REF] Dobbertin | Refinement monoids, Vaught monoids, and Boolean algebras[END_REF].) As every distance on a set X is obviously a p-measure on X viewed as a discrete poset, the problem of functorially lifting distributive ∨, 0 -semilattices by p-measures does not appear as difficult. The main problems encountered in the present work were (1) to get our posets connected (which is the case here as they are meet-semilattices), and (2) to get the subset { y = x | x ≤ y in P } join-generating the semilattice S under consideration. 11.2. Representation of distributive semilattices by majority algebras. To the author's knowledge, Corollary 10.4 is, so far, the only existing representation result that is specific to distributive ∨, 0 -semilattices. Unlike the Grätzer-Schmidt Theorem, it is not a lifting result of ∨, 0 -semilattices with respect to the Con c functor-the functor under consideration, namely Π (cf. Subsection 1.2), is more complicated to describe. One remaining hope after the negative result of [START_REF] Wehrung | A solution to Dilworth's Congruence Lattice Problem[END_REF] is whether every distributive ∨, 0 -semilattice is isomorphic to Con c A for some algebra A generating a congruence-distributive variety (cf. [START_REF] Wehrung | A solution to Dilworth's Congruence Lattice Problem[END_REF]Problem 2]). For instance, is every distributive ∨, 0 -semilattice isomorphic to Con c M , for some majority algebra M ? (A majority algebra is a nonempty set endowed with a ternary operation m that satisfies the identities m(x, x, y) = m(x, y, x) = m(y, x, x) = x.) Our hope is that the poset-theoretical methods used in the present paper could provide a stepping stone towards such a result. 11.3. Lifting finite diagrams of finite distributive ∨, 0 -semilattices. It is still an open problem whether every diagram D of finite ∨, 0 -semilattices and ∨, 0 -homomorphisms, indexed by a finite lattice, can be lifted, with respect to the Con c functor, by a diagram of (finite?) lattices (cf. [START_REF] Wehrung | A solution to Dilworth's Congruence Lattice Problem[END_REF]Problem 4]). Applying Theorem 10.2 to the diagram of ∨, 0, 1 -semilattices obtained by adding a largest element to each object in D and extending the transition maps accordingly, and then restricting the posets as at the end of the proof of Corollary 10.4, gives the weaker result that D can be lifted, with respect to the Π functor (cf. Subsection 1.2), by a diagram in VPMeas. The posets thus obtained may be thought of as 'skeletons' of the lattices that would appear in a (hypothetical) lifting of D with respect to Con c .

1. 3 .

 3 Basic notation and terminology. For elements a and b in a poset P , we shall use the abbreviations a ≺ P b ⇐⇒ (a < P b and there is no x such that a < P x < P b); a P b ⇐⇒ (either a ≺ P b or a = b); a ∼ P b ⇐⇒ (either a ≤ P b or b ≤ P a); a P b ⇐⇒ (a P b and b P a).

Definition 3 . 7 .

 37 A standard interval scheme is a family of the form P, Q a,b | a, b ∈ I , where the following conditions are satisfied: (i) P is a poset, I is a subset of { a, b ∈ P × P | a < b}, and Q a,b is a (possibly empty) poset, for all a, b ∈ I.

Lemma 3 . 9 .

 39 Let Q be an interval extension of a poset P . Put I = { a, b ∈ P × P | a < b}, and Q a,b = {x ∈ Q | x P = a and x P = b}, for all a, b ∈ P . Then P, Q a,b | a, b ∈ I is a standard interval scheme, and Q = P + (Q a,b | a, b ∈ I).

5 )

 5 for all x, y ∈ P. (9.Lemma 9.5. x z ≤ x y ∨ [[y z]] for all x, y, z ∈ P . Proof. If ν(y) ∨ ν(z) = ℓ then [[y z]] = 1 and the conclusion is trivial. Suppose that ν(y) ∨ ν(z) < ℓ. A direct use of Lemma 9.3 yields the inequality x z ≤ [[x y]] ∨ [[y z]], while a direct use of Lemma 9.4 together with the distributivity of D ℓ yields that x z ≤ x y + ∧ x y -∨ [[y z]]. It remains to establish the inequality x z ≤ x y ± ∨ [[y z]], which reduces, by the distributivity of D ℓ , to proving the inequality

  normal interval diagram of p-measured posets satisfying (DB1) and (DB2).

Theorem 10 . 2 .

 102 Let Λ be a lower finite meet-semilattice and let D = D i , ϕ i,j | i ≤ j in Λ be a Λ-indexed diagram of finite distributive lattices and ∨, 0, 1 -homomorphisms. Then there exists a D-valued normal interval diagram Q i | i ∈ Λ of finite p-measured lattices satisfying (DB1) and (DB2) together with the following additional conditions:

  ≤ n} and denote by D (n) the restriction of D to Λ n , for every natural number n. Suppose having constructed a D (n) -valued normal interval diagram Q i | i ∈ Λ n of finite p-measured lattices satisfying (DB1), (DB2), and Conditions (i)-(iii) of the statement of the theorem, we show how to extend it to a D (n+1) -valued normal interval diagram of finite p-measured lattices satisfying (DB1) and (DB2). In order to propagate Item (2) of Definition 5.1 through our induction, we shall add the following induction hypothesis:

Proposition 10 . 5 .

 105 Let S be a ∨, 0 -semilattice, let P be a poset, and let -- be a S-valued p-measure on P satisfying condition (ii) of Corollary 10.4 such that the subsetΣ = { y = x | x ≤ y in P } join-generates S. Then S is distributive. Proof. Let a 0 , a 1 , b ∈ S such that b ≤ a 0 ∨ a 1 , we find b i ≤ a i , for i < 2, such that b = b 0 ∨ b 1 .Suppose first that b ∈ Σ, so b = y = x , for some x ≤ y in P . By assumption, there are a positive integer m and a decompositionx = z 0 ≤ z 1 ≤ • • • ≤ z m = y such that for each i < m, there exists ε(i) ∈ {0, 1} with z i+1 = z i ≤ a ε(i) . Put b j = ( z i+1 = z i | i ∈ ε -1 {j}),for all j < 2. Then b j ≤ a j and b = y = x = b 0 ∨ b 1 .

1 .

 1 The construction is inspired by the one of the cube D c presented in [13, Section 3]. Example 10.6. Put Λ = P(3) (the three-dimensional cube) and Λ * = Λ \ {3}. There are a Λ-indexed diagram B = B p | p ∈ Λ of finite Boolean lattices and ∨, 0, 1 -embeddings, whose restriction to Λ * we denote by B * , and a B * -valued normal interval diagram Q p | p ∈ Λ * of finite p-measured lattices that cannot be extended to any B-valued normal diagram of p-measured posets.

1 QFigure 10 . 1 .

 1101 Figure 10.1. The posets Q ∅ , Q {i} , Q {i,j} , and P .

  that the B * -valued diagram Q p | p ∈ Λ * extends to some B-valued diagram Q p | p ∈ Λ . Evaluating the Boolean values in Q {0,1,2} , we obtain x 0 x 1 = x 0 x 1 {0,1} = c 2,1 , x 1 x 2 = x 1 x 2 {1,2} = c 0,1 , x 0 x 2 = x 0 x 2 {0,2} = c 1,1 ,hence, by the triangular inequality, c 1,1 ⊆ c 0,1 ∪ c 2,1 , a contradiction. 11. Concluding remarks 11.1.

  ). So we have reached the following theorem, which is the main technical result of the present paper. It refers to the conditions (DB1) and (DB2) introduced in Section 8.Theorem 10.1. Let Λ be a finite lattice with largest element ℓ, let D = D i , ϕ i,j | i ≤ j in Λ be a Λ-indexed diagram of finite distributive lattices and ∨, 0 -homomorphisms, and let Q i | i < ℓ be a D↾ <ℓ -valued normal interval diagram of p-measured lattices satisfying (DB1) and (DB2). Let Q be a covering extension of the strong amalgam P of Q i | i < ℓ . Furthermore, we assume that for all x ∈ Q, the closed interval [x P , x P ] of Q is endowed with a p-measure --[xP ,x P ] (depending only of the interval [x P , x P ]) such that x = x P [xP ,x P ] ∼ x P = x [xP ,x P ] andx P = x P [xP ,x P ] = x P = x P P .

and thus, as i j and as (10.3) is valid at all levels below either i or j,

If height(i) = n while height(j) < n, then Q i is still given by (10.4), and so

which completes the verification of Item (2) of Definition 5.1. This completes the proof of the induction step.

Remark 10.3. More can be said in case all transition homomorphisms ϕ i,j separate zero, that is, ϕ -1 i,j {0} = {0}, for all i ≤ j in Λ. Indeed, in such a case, in the proof of Theorem 10.2, for all x ≺ y in P ℓ , there exists i < ℓ such that x, y ∈ Q i , and so y = x P ℓ = ϕ i,ℓ ( y = x Q i ) is nonzero in case we have included in the induction hypothesis the assumption that v = u > 0 for all i < ℓ and all u < v in Q i . Hence, y = x P ℓ > 0 for all x < y in P ℓ . Therefore, we can strengthen the conclusion (ii) of Theorem 10.2 by stating that y = x is join-irreducible in D i , for all i ∈ Λ and all x ≺ y in Q i .

Corollary 10.4. For every distributive ∨, 0 -semilattice S, there are a ∧, 0 -semilattice P and a S-valued p-measure --on P satisfying the following additional conditions:

(i) y = x > 0 for all x < y in P .

(ii) For all x ≤ y in P and all a, b ∈ S, if y = x ≤ a ∨ b, there are a positive integer n and a decomposition

Furthermore, if S is bounded, then P can be taken a bounded lattice.

Proof. Suppose first that S is bounded. By Lemma 1.3, S is the directed union of its finite distributive ∨, 0, 1 -subsemilattices. Hence we can write S as a directed union S = (D i | i ∈ I), where Λ is the (lower finite) lattice of all finite subsets of S, all the D i are finite distributive 0, 1-subsemilattices of S, and the transition map from D i to D j is the inclusion map, for all i ≤ j in Λ (in particular, it separates zero). Let Q = Q i | i ∈ Λ be as in Theorem 10.2. We prove that the union of all the p-measures --

Condition (ii) above follows. As J(D i ) join-generates D i , for each i ∈ Λ, Condition (iii) above follows from Condition (iii) in Theorem 10.2.

In the general case, we apply the result above to S ∪ {1} (for some new unit element 1), and then, denoting by P the corresponding p-measured lattice, we set Q = {x ∈ P | x = 0 ∈ S}, which is a lower subset of P . The restriction of the p-measure of P to Q × Q is as required.