In this paper, we generalize the classical duplication of intervals in lattices. Namely, we deal with partial duplication instead of complete convex subsets. We characterize those subsets that guarantee the result to still be a lattice. Moreover, we show that semi-distributive and extremal lattices can be encompassed by such construction where classical duplication fails.
The aim of this paper is to give a characterization of several classes of lattices
obtained by doubling suborder (not necessary convex) in lattices. This
construction generalizes the one that uses convex duplication introduced by Day [
In the opposite of constructing a lattice, decomposing a lattice using
properties of duplication to small lattices has been also considered in the
literature. Markowsky [
In this paper we give a necessary and su cient condition for duplications that maintain the lattice structure. We also give other properties that guarantee some combinatorial properties of lattices such as ^-semidistributivity and extremality. As a by-product of our results and existing ones, we obtain characterizations of some classes of lattices. element j in X is called join-irreducible in L if x = z _ t implies x = z or x = t. The set of all join-irreducible elements is denoted by J (L). The set M (L) of all meet-irreducible elements is de ned dually. The height h(L) of a lattice L is the length of the longest chain from ? to > (the least and greatest elements of L). Given an element x in X, the set " (x; L) is the subset of X containing every element y such that x 6 y. Set # (x; L) is de ned dually.
Given two elements x and y in any lattice L, we use relations ., % and .%
de ned in [
A lattice is said meet-semidistributive, if for all x; y; z 2 L; x ^ y = x ^ z implies x ^ y = x ^ (y _ z). It is said semidistributive if it is meet-semidistributive and join-semidistributive. We may use .%L to denote the set of pairs (j; m) in L such that j .% m. The subscript may be omitted when the context is clear. 2
We study the possibilities of copying a part of a lattice so that it remains in certain classes of well-known lattices.
The general framework is the following. Let L be a lattice on some set X with partial order 6. Let C be any subset of X that will be copied. We call C0 the copy of C (meaning there is a bijection ' from C to C0). The convex closure of C in L is the set H(C) = fy : 9x; z 2 C with x 6 y 6 zg. We may now consider the partial order (X [ C0; 4) where the relation 4 is de ned as follows for any pair (x; y) of elements of X [ C0: x 4 y if 8x 2 X; y 2 X and x 6 y > ><>x 2 X H(C); y 2 C0 and x 6 ' 1(y) >x 2 C0; y 2 X and ' 1(x) 6 y > >:x 2 C0; y 2 C0 and ' 1(x) 6 ' 1(y): Note that if x is in H(C), y is in C and x 6 y, we do not have x 4 '(y). It is routine to check that 4 de nes a partial order on X [ C0. We shall denote this partial order L[C]. If C is the empty set, then this process does not alter L (L[;] = L). We shall distinguish two speci c subsets of C, namely the minimal elements L = fl1; l2; : : : ; lng and the maximal elements U = fu1; u2; : : : ; umg. Figure 1 depicts an example of a copy with two minimal and two maximal elements in C.
In order to guarantee that the resulting partial order remains a lattice, we need to enforce two properties about C. The rst one says that if the join of two H(C) 5 2 8 11 4 7 1 copied elements is in the convex closure of C, then it must be copied. The second says that if an element x in H(C) covers an element which is not in H(C), then x must be copied.
8(x; y) 2 C2; x _ y 2 H(C) ) x _ y 2 C; 8x 2 H(C); 8y 2 X
H(C); x covers y ) x 2 C: (P1) (P2) Remark 1. When U and L are singletons, Property (P1) says that (C; 6) is a join-sublattice of L.
We shall rst prove that properties (P1) and (P2) are necessary and su cient conditions for the resulting partial order to be a lattice.
Proposition 1. Given a lattice L = (X; 6) and a subset C of X, L[C] is a lattice if and only if (P1) and (P2) are satis ed.
Proof. We rst show that (P1) and (P2) are necessary. Suppose that L[C] is a lattice. We shall prove both properties separately.
{ (P1). Let x and y be two elements of C such that their join z in L is in H(C). There is some element u in U such that z 6 u. By hypothesis, L[C] is a lattice, so there is a join of '(x) and '(y) in L[C] let us call it t0. By the de nition of 4, we have '(x) 4 '(u) and '(y) 4 '(u). This ensures that t0 is between '(x) and '(u). But those elements can only be in C0 and there must be an element t in C such that t0 = '(t). This element t is then larger than both x and y so that z 6 t and by de nition of 4, z 4 t. But we also have '(x) 4 z and '(y) 4 z so that t 4 z. Finally, t = z and thus the join of x and y is in C. { (P2). Let x be an element of H(C) and y be an element of X H(C) which is covered by x in L. Since x is in H(C), there are elements l and u in L and U such that l 6 x 6 u. In turn, '(l) 4 x. We also know that y 4 x, thus the join of '(l) and y in L[C] is less than or equal to x. For a contradiction, suppose that x is not in C. Then x covers y in L[C] so that the join of y and '(l) in L[C] must be exactly x. Now y 4 '(u) and '(l) 4 '(u) so the join of y and '(l) must be below '(u). This is a contradiction since x 64 '(u).
Let us now prove that (P1) and (P2) are su cient conditions for L[C] to be a lattice. For this, it su ces to prove that any pair of elements have a least upper bound. From the de nition of 4, one may check that for any x in X [ C0 we have " (x; L[C]) = 8>" (x; L) if x 2 H(C) <
" (x; L) [ '(" (x; L)) if x 2 X > :" (' 1(x); L) [ '(" (' 1(x); L)) if x 2 C0; H(C) where '(A) denotes all elements that can be written as '(a) for some a in A. In all three cases, there exists an element a in X such that " (x; L[C]) is exactly " (a; L) or " (a; L) [ '(" (a; L)).
Now, notice that for any two subsets of X, A and B, the intersection of A and '(B) is always empty. From this and the distributivity of set operations, we may derive that for any pair (x; y) of elements in X [ C0, there are two elements a and b in X such that " (x; L[C])\ " (y; L[C]) = 8 >" (a; L)\ " (b; L) <
or >:(" (a; L)\ " (b; L)) [ '(" (a; L)\ " (b; L)):
In the rst case, " (a; L)\ " (b; L) is a subset of X and since L is a lattice, we know there is a least element. For the second case, let c be the join of a and b in L. We distinguish three subcases.
{ If c is in C, then '(c) is de nitely less than any element of both " (a; L)\ " (b; L) and '(" (a; L)\ " (b; L)). Therefore, '(c) is the least upper bound of a and b. { If c is not in H(C), then c is a least element of " (a; L)\ " (b; L). Consider any element x of '(" (a; L)\ " (b; L)). Then there ' 1(x) is an element of C which is greater than a and b. Therefore it is also bigger than c. By the de nition of 4, x is greater than c in L[C]. Element c is then the least upper bound of a and b. { If c is in H(C) C, then a and b cannot be both elements of C by (P1).
Property (P2) basically tells us that for any chain from an element out of H(C) to some element in H(C), there is an element of C. As a consequence, there is a0 (respectively b0) in C such that a 6 a0 6 c (respectively b 6 b0 6 c). But then the join of a0 and b0 must be c and since c is not in C, this leads to a contradiction of (P1) so that this third subcase can never occur. Thus any pair of elements in L[C] has a least upper bound. Since there is also a bottom element in L[C], we conclude that L[C] is a lattice. tu
As a useful side result, we get that (P1) and (P2) imply that the copy of any join-irreducible element in L is a join-irreducible element of L[C]. Proposition 2. Given a lattice L, and a subset C satisfying, (P1) and (P2), then for any element j in J (L) \ C, its copy '(j) is a join-irreducible element of L[C].
Proof. Let j be such an element and j its unique predecessor in L. For a contradiction, suppose that '(j) is not a join-irreducible element in L[C]. This implies that j is in H(C) but has not been copied. Consider two di erent elements a and b covered by '(j). In particular, '(j) is the join of a and b in L[C]. Furthermore, a and b are less than j in L[C]. Whether they are in C0 or in X, this means they are also less than j . But j is not comparable to '(j) the join of a and b, which is a contradiction since Proposition 1 ensures that L[C] is a lattice. tu
We may rst notice that the copying process creates only m new and pairwise distinct meet-irreducible elements.
Remark 2. Given a lattice L and a subset C satisfying (P1) and (P2),
M (L[C]) = M (L) [ f'(u1); '(u2); : : : ; '(um)g:
Join-irreducible elements can be of four types. Any join-irreducible element of L which is not copied remains a join-irreducible element in L[C]. By Proposition 2, any join-irreducible element of L which is copied has its image as a join-irreducible element of L[C]. In addition, any element l in L becomes a join-irreducible element in L[C]. And nally, some elements of C0 might be joinirreducible in L[C] even though their pre-image by ' is not join-irreducible in L. This paragraph is summed up in the following remark.
Remark 3. Given a lattice L and a subset C satisfying (P1) and (P2), J (L[C]) = (J (L)
C) [ '(J (L) \ C) [ fl1; l2; : : : ; lng [ R; where R denotes the join-irreducible elements of C0 which are not the copy of a join-irreducible element. 3
In this paper we want to keep control on the number of join-irreducible elements in order to guarantee that the lattice L[C] satis es several combinatorial properties. To this end, we would like the sizes of J (L[C]) and J (L) to di er by only one. Remark 3 ensures that jJ (L[C])j jJ (L)j = jRj + n. Since n is at least 1, we need to enforce that R is empty and L is a singleton. Having R as an empty set means that any join-irreducible element of L[C] in C0 is the image of a former join-irreducible of L in C. We thus states the additional property, : Remark 4. Given a lattice L and a subset C satisfying (P0), (P1) and (P2),
In addition we shall consider three properties that will allow us to circumscribe the type of lattice that we want to obtain.
jJ (L[C])j = jJ (L)j + 1:
L = f?g
(P0) (?) (U ) (.) 8x 2 C; 8y 2 X; '(x) . y in L[C] ) x . y in L:
Each of these properties allows us to control some combinatorial parameter of L[C]. Namely, (?) controls the height of the lattice, (U ) controls the number of its meet-irreducible elements and (.) controls the number of pairs related through relation .%. These are formalized in the following theorem. Theorem 1. Given L a lattice and C a subset satisfying (P0), (P1) and (P2), we have the following implications: (i) if (?), then h(L[C]) = h(L) + 1; (ii) if (U ), then jM (L[C])j = jM (L)j + 1; (iii) if (.), then j .%L[C] j = j .%L j + jU j:
Proof. Fact (i) is trivial and (ii) is obtained by considering Remark 2. Let us focus on (iii). By Property (P0), we know that L is a singleton. Let l denote its single element.
Claim 1.1. For any u in U , l .% '(u).
The only predecessor of l in L[C] is '(l) and for any u in U , the only successor of '(u) in L[C] is u itself. Furthermore l 4 u, '(l) 4 '(u) and l 64 '(u). This concludes the proof of Claim 1.1.
Claim 1.2. Reciprocally, for any meet-irreducible element m of L[C], if l .% m, then there is u in U such that m = '(u).
A stronger statement is that when l . m, then there is u in U such that m = '(u).
We prove the stronger statement for a later use. Let m be an element of M (L[C]) '(U ), thus m is in X. We shall prove that l . m cannot occur in L[C]. For a contradiction, suppose that l . m in L[C]. This means that '(l) 4 m and by the de nition of 4, we get that l 6 m in L and in turn that '(l) 4 m which is a contradiction. This concludes the proof of Claim 1.2. Claim 1.3. Similarily, for any join-irreducible element j of L[C] and any u in U , if j .% '(u), then j = l.
Once again, a stronger statement is obtained when .% is replaced by ..
We also prove the stronger statement. Let u be some element of U and suppose for a contradiction that '(u) is in relation . with some join-irreducible element j distinct from l. Then j 64 '(u) and j 4 u. Thus j cannot be in C0 (it would be less than both u and '(u) or not less than both of them). Therefore, j is a join-irreducible element of L with a single predecessor j . In L[C], j has also a single predecessor j which is not in C0. Since we assumed that j 4 '(u), it cannot be in H(C) (they would be non-comparable). Since j has not been copied, Property (P2) guarantees that j is not in H(C) either. But by the de nition of 4, j must be either less than both u and '(u) or not less than both of them. This is a contradiction. This concludes the proof of Claim 1.3.
Let j be an element of J (L) C then j is a join-irreducible element of L[C] and its only predecessor in L[C] is the same as in L, say j . Let m be a meetirreducible from L. It remains a meet-irreducible element in L[C]. But its only successor in L[C] can be the same as in L, say m or its copy '(m ). In any case, the comparability of j and m is the same in both L and L[C]. Same stands for j and m. Now if the only successor of m is the same in L and L[C], j .% m in L if and only if j .% m in L[C]. In the case where the only successor of m in L[C] is '(m ), if j 4 '(m ), we also have j 6 m . Reciprocally, if j 6 m , we only need to prove that j is not in H(C) to conclude that j 4 '(m ). Suppose that j is in H(C). Since m is in C, there is an element u in U such that m 4 '(m ) 6 '(u). This implies that m is not in H(C) (otherwise it would not be comparable with '(m )) so that j 66 m. If j .% m in L, it means that j 6 m thus j is not in H(C) either. In the end, since j has not been copied, Property (P2) allows us to say that j is not in H(C). So j .% m in L if and only if j .% m in L[C], ending the proof of Claim 1.4.
Claim 1.5. For any j in J (L) \ C and m in M (L), j .% m in L if and only if '(j) .% m in L[C].
We still have to study the case when the join-irreducible element is a copy of a former join-irreducible element. Let j be in J (L) \ C and m be a meetirreducible element of L. We want to prove that '(j) .% m in L[C] if and only if j .% m in L. In this case, we know that the only predecessor of '(j) is some element between '(l) and '(j). This element can then be written '(x) for some x in C between l and j. Thus, x 6 j . By the de nition of 4, '(j) 64 m if and only if j 66 m. Clearly, if j 6 m, we have that '(x) 4 m. Conversely, if '(x) 4 m, and '(j) 64 m it means that '(j) . m. By Property (.), we have that j . m, thus j 6 m. Let m be the only successor of m in L. In L[C] the only successor of m is either m or '(m ). In the latter case, if j 6 m , '(j) 4 '(m ) and reciprocally. In the former case, we also have that '(j) 4 m if and only if j 6 m . Therefore '(j) .% m in L[C] if and only if j .% m in L. This concludes the proof of Claim 1.5
%.L[C]=f(l; '(u)) : u 2 U g [ f(j; m) 2 J (L) [ f('(j); m) 2 C0
M (L) : j .% m in L and j 2= Cg
M (L) : j 2 J (L) \ C and j .% m in Lg: In terms of cardinality, we get that j .%L[C] j = j .%L j + jU j. tu
We may notice that Property (.) is actually only needed for Claim 1.5. Indeed, if this property is not satis ed, we may have new relations between the image of a join-irreducible element and some old meet-irreducible element (see Figure 2).
The proof of the third implication of Theorem 1 can be adapted to prove a fourth implication. We prove separately for an easier reading.
Theorem 2. Given L a lattice and C a subset satisfying (P0), (P1) and (P2), we have
(.) ) j .L[C] j = j .L j + jU j Proof. We use the same ideas as in the proof of Theorem 1.
Claim 2.6. For any u in U , l . '(u) where L = flg.
Let j be an element of J (L) C then j is a join-irreducible element of L[C] and its only predecessor in L[C] is the same as in L, say j . Let m be a meetirreducible from L. It remains a meet-irreducible element in L[C]. But its only successor in L[C] can be the same as in L, say m or its copy '(m ). In any case, the comparability of j and m is the same in both L and L[C]. Same stands for j and m since j is not copied. Then j . m in L if and only if j . m in L[C], ending the proof of Claim 2.7.
Claim 2.8. For any j in J (L) \ C and m in M (L), j . m in L if and only if '(j) . m in L[C].
By Property (.), we have for any j in J (L) \ C and m in M (L), '(j) . m in L[C] imply j . m in L.
For the converse, let j be in J (L) \ C and m be a meet-irreducible element of L such that j . m in L. We want to prove that '(j) . m in L[C]. First, by de nition of 4, '(j) is incomparable to m. If j 2= H(C) then j = '(j) by de nition of 4, and then '(j) . m in L[C]. Now suppose that j 2 H(C). In this case, we know that the only predecessor '(j) of '(j) is some element between '(l) and '(j). This element can then be written '(x) = '(j) for some x in C between l and j. Then x 6 j and thus '(x) 4 m. So '(j) . m in L[C].
Summarising the previous results (and the strong versions of Claims 1.2 and 1.3), we obtain that .L[C]=f(l; '(u)) : u 2 U g [ f(j; m) 2 J (L) [ f('(j); m) 2 C0
M (L) : j . m in L and j 2= Cg
M (L) : j 2 J (L) \ C and j . m in Lg: In terms of cardinality, we get that j .L[C] j = j .L j + jU j. tu 3 4
L C = {0, 2} 2 1 0 3 4 2 1 0 L[C] ϕ(2) ϕ(0)
Lattices characterizations given in the following theorem can be found in
several papers (see for example [
Theorem 3. Let L be a nite lattice. Then L is
{ meet-semidistributive if and only if j .% j = jJ (L)j [18].
{ semidistributive if and only if j .% j = jJ (L)j = jM (L)j [18].
{ meet-extremal if and only if h(L) = jM (L)j [
{ distributive if and only if j . j = jJ (L)j = jM (L)j [17].
Remark 5. Notice that a lattice that is semidistributive and extremal does not imply that is distributive (see Figure 3). In fact it is not graded. This explain the property (.).
As a corollary of Theorems 1 2 and 3, we obtain a wider range of possibilities to build speci c types of lattices by preserving some combinatorial characterizations.
Corollary 1. Given a lattice L and a subset C verifying (P0), (P1) and (P2) the following implications are true: 1. L is distributive, (.), (?) and (U ) imply that L[C] is distributive. 2. L is semidistributive, (.), and (U ) imply that L[C] is semidistributive 3. L is meet-semidistributive and (.) imply that L[C] is meet-semidistributive 4. L is extremal, (?) and (U ) imply that L[C] is extremal 5. L is meet-extremal and (?) imply that L[C] is meet-extremal
One challenging problem is the characterization of contexts where their concepts lattices satisfy the considered properties. For doubling convex sets, there are nice FCA characterization and algorithms that recognize bound, lower (upper) bounded, semidistributive and convex lattices [5{7, 1{4, 8].
Acknowledgment The authors are very grateful to the referee for their constructive comments. This work has been funded by the french national research agency (ANR Graphen, 2015-2018). 14. Viaud, J., Bertet, K., Demko, C., Missaoui, R.: Subdirect decomposition of contexts into subdirectly irreducible factors. In: Proceedings of the International Workshop on Formal Concept Analysis and Applications, FCA&A 2015, co-located with 13th International Conference on Formal Concept Analysis (ICFCA 2015), Nerja, Malaga, Spain, June 23-26, 2015. (2015) 49{64 15. Wille, R.: Subdirect product construction of concept lattices. Discrete Mathematics 63(2) (1987) 305 { 313 16. Birkho , G.: Lattice Theory. 3rd edn. Volume 25 of Coll. Publ. XXV. American
Mathematical Society, Providence (1967) 17. Monjardet, B.: The presence of lattice theory in discrete problems of mathematical social sciences. why. Mathematical Social Sciences 46(2) (2003) 103 { 144 Mathematical Theories of Allocation of Discrete Resources: Equilibria, Matchings, Mechanisms. 18. Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations.
Springer-Verlag Berlin (1999)