The Sca olding of a Formal Context

Abstract

The sca olding of a complete lattice L of nite length was introduced by Rudolf Wille in 1976 as a relative subsemilattice of L that can be constructed using subdirect decomposition. The lattice is uniquely de ned by its sca olding and can be reconstructed from it. Using bonds, we demonstrate how the sca olding can be constructed from a given formal context and thereby extend the notion of the sca olding to doubly founded lattices. Further, we explain the creation of a suitable graphical representation of the sca olding from the context.

Keywords

• sca olding
• subcontext
• bond
• subirreducible

Introduction

The notion of the sca olding was introduced by Rudolf Wille in [ 5 ]. There, the sca olding of a complete lattice L of nite length is constructed as a supremumdense subset of L. The subset together with a partial supremum operation allows the reconstruction of the lattice L. In fact, any complete lattice of nite length is uniquely determined by its sca olding up to isomorphism. The construction of the sca olding is closely related to subdirect decomposition. If a lattice is decomposable into small factors, its sca olding will contain signi cantly fewer elements than the lattice itself. Like lattices, their sca oldings can also be visualized by diagrams. The sca olding diagrams are an extension of the usual line diagrams. Although they require more interpretation e ort, they can increase readibility a lot, especially when the sca olding is much smaller than its lattice. An impressive example is given in [ 5 ], pp. 64-67, with a lattice of 99 elements that has a sca olding consisting of only 15 elements. In this paper we explain the construction of the sca olding and its diagram from a given formal context without constructing the corresponding concept lattice rst. Further, we extend the de nition of the sca olding to doubly founded complete lattices. In the next section we will recall the sca olding as it was constructed in [ 5 ]. Other de nitions or properties of contexts and lattices will be recalled when used.

The Sca olding of a complete lattice of nite length

A relative sup-subsemilattice of a complete lattice L is a subset S L together with a partial operation supS such that supS A = s () sup A = s holds for A S and s 2 S. The partial operation supS induces an order S on S by x S y : () supS fx; yg = y that is consistent with the order on L. The sca olding of a complete lattice L is constructed as a relative sup-subsemilattice of L using a speci c set of separating complete homomorphisms t : L ! Lt (t 2 T where T is a suitable index set) and their residual maps t : Lt ! L : x 7! inf t 1x. Here, separating means that for any two elements x; y 2 L there is an element t 2 T with t(x) 6= t(y). Theorem 1 summarizes two important results of [ 5 ]: Theorem 1. For an arbitrary index set T , complete lattices L and Lt (t 2 T ) and separating complete homomorphisms t : L ! Lt

S( t j t 2 T ) := f t tx j x 2 L; t 2 T g n f0g is a supremum-dense subset of L and L is isomorphic to the complete lattice of complete ideals of the relative sup-subsemilattice S( t j t 2 T ).

The latter part of the theorem points out a method to reconstruct L from S( t j t 2 T ) as an isomorphic copy of the complete lattice of ideals of the sca olding. An ideal of a relative sup-subsemilattice S is a subset I S that is closed against the partial supremum-operation supS and that with each element x 2 I also contains all elements of S that are smaller than x w.r.t. S . Note that a similar approach is taken in [ 2 ], where with the core of a nite lattice L a minimal subset of L is constructed such that its lattice of lters is isomorphic to L.

For the next step of the construction we need to distinguish between the two properties of being subdirectly irreducible as a lattice and as a complete lattice. A (complete) lattice L is called (completely) subdirectly irreducible, if there is no set of (complete) lattices Lt (t 2 T ), such that L is a (complete) subdirect product of the Lt while none of the Lt is isomorphic to L. A lattice that is complete and subdirectly irreducible is also completely subdirectly irreducible. In the case of nite length, the two properties are the same. Note that when it is clear that only complete lattices are discussed (as in [ 4 ] or [ 5 ]), usually subdirectly irreducible stands for completely subdirectly irreducible.

To get a one-to-one relationship between lattices and their sca oldings, one xes the choice of the Lt and t in the construction of Theorem 1. Considered are all completely subdirectly irreducible factors Lt of the lattice L and all surjective complete homomorphisms t : L ! Lt. For lattices of nite length (thus the Lt are also subdirectly irreducible) these t are separating (cf. [ 5 ] or [ 1 ], p. 193) and therefore one can de ne the sca olding of L as S(L) := S( t j t 2 T ). An element x 2 L is called subirreducible if it is an element of S(L), i. e., if a complete homomorphism from L onto a subdirectly irreducible factor of L exists with x = x.

An example of the sca olding of a lattice is shown in Figure 1 (the last diagram). The subirreducible elements of the lattice are colored in gray. The diagram above to the right of the lattice is that of its sca olding as it is described in [ 5 ]. Construction and interpretation of such diagrams are explained in Sect. 4.

In the following, K always denotes a context (G; M; I), and Kx a context (Gx; Mx; Ix). By g we denote the object concept of an object g and by m the attribute concept of an attribute m. T will always be an index set. In the next section we present a construction of the sca olding from a formal context. 3

The Sca olding of a Formal Context

For our construction we employ the theory of bonds and therefore shortly recall some results about them (for details see [ 4 ], Sect. 7.2). A bond from Ks to Kt is a relation Rst Gs Mt; such that gRst is an intent of Kt for every object g 2 Gs and mRst is an extent of Ks for every attribute m 2 Mt. For bonds Rrs from Kr to Ks and Rst from Ks to Kt the bond product, de ned by Rrs

Rst := f(g; m) 2 Gr

Mt j gRrsIs mRst g ; is itself a bond from Kr to Kt. The signi cance of the bond notion stems from the fact that bonds from Ks to Kt correspond one-to-one to the sup-morphisms from B(Ks) to B(Kt) and the bonds from Kt to Ks correspond one-to-one to the inf-morphisms from B(Ks) to B(Kt). For example, a bond R from Ks to Kt yields a sup-morphism from B(Ks) to B(Kt) via (A; B) 7! (ARIt ; AR) :

(A; B) 7! (BS ; AR) Each complete homomorphism from B(Ks) to B(Kt) is thus de ned via by a pair (R; S) of bonds (R from Ks to Kt, S from Kt to Ks) where ARIt = BS holds for every (A; B) 2 B(Ks) (equiv. BSIt = AR). In this paper, such pairs shall be called hom-bonds. We also introduce the notion of being separating for hom-bonds: A set of hom-bonds (Rt; St) from K to Kt (t 2 T ) is called separating, if for any two extents A 6= C of K an index t 2 T exists such that ARt 6= CRt . The following proposition presents some useful rules for bond arithmetics. Proposition 1. Let Rrs, Rst and Rrt be bonds from Kr to Ks, Ks to Kt and Kr to Kt resp. and A Gr; B Mt. The following hold: 1. AIrIrRrs = ARrs and BItItRst = BRst , 2. ARrs Rst = ARrsIsRst and BRrs Rst = BRstIsRrs , 3. AR S AIs and A(R S)IsR = AR for hom-bonds (R; S) from Kr to Ks. Proof. 1 simply follows from the bond properties and 2 follows from Proposition 83 in [ 4 ]. 3: According to 2 we have AR S = ARIsS = BSS B = AIs and A(R S)IsR = (ARIsS )IsR = (BSS )SIs = BSIs = ARIsIs = AR using the hom-bond property twice. a b c d e f g

We are now ready to begin our construction.

Theorem 2. For separating hom-bonds (Rt; St) between K and Kt (t 2 T )

S(Rt; St)t2T := f(ARt StI ; ARt St ) j (A; B) 2 B(K); t 2 T g n f(M I ; M )g is a supremum-dense subset of B(K): Proof. For (A; B) 2 B(K) we show (A; B) = supf(ARt StI ; ARt St ) j t 2 T g by proving A = (Tt2T ARt St )I : For an arbitrary index u 2 T holds ( \ ARt St )IRu = ( \ ARt StII )IRu = ( [ ARt StI )IIRu = ( [ ARt StI )Ru t2T t2T t2T t2T by Proposition 1.1. From Proposition 1.3 we get:

ARt StI

AII = A =) [ ARt StI t2T

A =) ( [ ARt StI )Ru

ARu t2T ARu SuI

ARu SuIRu = ARu : and \ ARt St t2T

ARu Su ) ( \ ARt St )I

t2T ) ( \ ARt St )IRu

t2T tThheuresfowree hAave=( T(Tt2T ARt St )IRu = (St2T ARt StI )Ru = ARu for all u 2 T and t2T ARt St )I , since the bonds are separating. The smallest concept (M I ; M ) of K can be removed from the set, since it is the supremum of the empty set.

To continue our construction we require the concept lattices to be doubly founded. A complete lattice L is called doubly founded, if for any two elements x; y 2 L there always are elements s; t 2 L with s being minimal w.r.t. s y and s x and t being maximal w.r.t. t x and t y (cf. [ 4 ], De nition 26). Note that every nite lattice is a doubly founded complete lattice. Further, every doubly founded complete lattice is isomorphic to the concept lattice of a reduced context. It is also possible to de ne doubly founded contexts. In fact, the context of a doubly founded lattice is always doubly founded. The de nition can be found in [ 4 ], but the details are not important in this work. In the following we will also make use of the arrow relations in a context K (cf. [ 4 ], De nition 25), i.e. { g . m () g ^ m = supf(A; B) 2 B(K) j (A; B) < gg 6= g { g % m () g _ m = inff(A; B) 2 B(K) j (A; B) > mg 6= m { g %. m () g . m and g % m where g is an object and m is an attribute of K. In a reduced context of a doubly founded lattice for every object g exists at least one attribute m with g %. m. The analogue holds for every attribute. A subcontext of (H; N; J ) of a reduced context (G; M; I) is called arrow-closed, if for g 2 G and m 2 M it always holds that { from g 2 H and g % m follows m 2 N and { from m 2 N and g . m follows g 2 H.

For an object g 2 G there always exists a smallest arrow-closed subcontext hgiK = (Gg; Mg; Ig) containing g, called the 1-generated subcontext of g in (G; M; I) (cf. [ 4 ], Sect. 4.1). An example of those subcontexts is given in Figure 1, where the three small contexts are 1-generated subcontexts of the larger one. A subcontext (H; N; J ) of a context (G; M; I) is called compatible, if for each concept (A; B) of (G; M; I) the pair (A \ H; B \ N ) is a concept of (H; N; J ). In the reduced context K of a doubly founded concept lattice the compatible subcontexts are exactly the arrow-closed subcontexts. For proof see [ 4 ], Propositions 15 and 36. Moreover, in this case, the 1-generated subcontexts yield the subdirectly irreducible factors of B(K) (cf. [ 4 ], Propositions 61 and 62). Finally, subcontexts Kt of K (t 2 T ) are said to cover K, if S t2T Mt = M .

The sca olding of a reduced context to2fTaGdto=ubGly afnoudnSded concept lattice is now de ned using the construction of Theorem 2 by xing speci c subcontexts and bonds.

Proposition 2. If K is a reduced context of a doubly founded concept lattice and hgiK = (Gg; Mg; Ig), then (Rg; Sg) with Rg := I\(G Mg) and Sg := I\(Gg M ) (g 2 G) are separating hom-bonds.

Proof. From [ 4 ], Theorem 18 follows that, because B(K) is doubly founded, it has a subdirect decomposition into subdirectly irreducible factors. By [ 4 ], Proposition 61 such a decomposition corresponds to a family of arrow-closed subcontexts covering K and by [ 4 ], Proposition 62 those subcontexts are 1-generated and thus form a subset of the hgiK (g 2 G). The bond properties of Rg and Sg (g 2 G) and the hom-bond condition follow easily from the fact that the subcontexts hgiK are arrow-closed and thus compatible (cf. [ 4 ], Proposition 36). Left to prove is that (Rg; Sg) (g 2 G) are also separating. Suppose for two extents A; C of K holds ARg = CRg for all g 2 G. By the de nintion of the bonds this means AI \ Mg = CI \ Mg for all g 2 G and since the subcontexts hgiK (g 2 G) cover K, we have AI = CI and thus A = AII = CII = C: De nition 1. If B(K) is the doubly founded concept lattice of a reduced context K and (Rg; Sg) are as above, then the relative sup-semilattice

S(Rg; Sg)g2G = f(ARg SgI ; ARg Sg ) j (A; B) 2 B(K); g 2 Gg n f(M I ; M )g is called the sca olding of K and will be denoted by S(K).

By the above proposition the sca olding is well-de ned. If one constructed the sca olding according to the de nition above, one would need B(K) rst. This is an obvious drawback considering that one of the goals of the sca olding idea is to have a small representation of the lattice from which the lattice can be reconstructed. We therefore simplify the construction such that one only needs to construct smaller lattices { namely the concept lattices of the 1-generated subcontexts. We then also reduce the set of subcontexts needed for the construction in Proposition 4. But rst we have to prove that our de nition is consistent with the construction in [ 5 ] described in the previous section.

Theorem 3. For a reduced context K of a lattice of nite length the sca olding of the context S(K) is equal to the sca olding of the lattice S(B(K)): Proof. By (A; B) 7! (AS ; AR) hom-bonds (R; S) from K to a context L de ne a complete homomorphism B(K) ! B(L). From this it is easy to see that separating hom-bonds de ne separating complete homomorphisms and vice versa.

Claim: S( t j t 2 T ) = S(Rt; St)t2T if t : B(K) ! B(Kt) are the complete homomorphisms de ned by (Rt; St) (t 2 T ).

As t is residual to t, Corollary 112 in [ 4 ] states that the bond from Kt to K de ning the sup-morphism t is in fact St. Since is a sup-morphism too (de ned by the bond Rt), we can use the dual of [ 4 ], Proposition 113 (stating that the composition of sup-morphisms corresponds to the product of their bonds) and obtain t t(A; B) = (ARt StI ; ARt St ).

In order to construct the sca olding, surjective complete homomorphisms onto subdirectly irreducible lattices are used. Considering isomorphism, it is obvious that one can narrow these choices down to the projections onto subdirectly irreducible factors of B(K). The subdirectly irreducible factors of a lattice of nite length (in fact of all doubly founded lattices) correspond to the 1-generated subcontexts Kg (g 2 G) (cf. [ 4 ], Propositions 61 and 62) and the associated projections are given by B(K) ! B(Kg) : (A; B) 7! (A \ Gg; B \ Mg) (cf. [ 4 ], Proposition 34). It is easy to see that the hom-bonds to these complete homomorphisms are (Rg; Sg) as de ned above. Thus S(K) and S(B(K)) meet the requirements of the claim and are therefore equal.

Analogously to [ 5 ] it is also possible to de ne the sca olding by subirreducible elements. We restate this in the next corollary, which presents a rst simpli cation of the sca olding construction: it allows to compute S(K) without computing B(K) rst.

Corollary 1. In a reduced context K of a doubly founded concept lattice a concept (A; B) with B 6= M is subirreducible, i there is a 1-generated subcontext (H; N; J ) such that (A; B) = ((A\H)II ; (A\H)I ). The sca olding S(K) consists of all subirreducible elements of B(K); i.e.

S(K) = [ f(CII ; CI ) j (C; CIg ) 2 B(hgiK); CIg 6= Mgg :

g2G Proof. Similarly to the proof above follows that a concept (A; B) is subirreducible i K has a 1-generated subcontext (H; N; J ) such that the equation (A; B) = (AR SI ; AR S ) holds with R = I \ (G N ) and S = I \ (H N ). The claimed equivalence follows (using Proposition 34 from [ 4 ] and Proposition 1.2) from:

AR S = ARJS = (AI \ N )JS = (BI \ H)S = (A \ H)I : Considering that the composed operator R S is idempotent (Proposition 1.3), it follows immediately from De nition 1 that S(K) is the set of all subirreducible elements. Since the map (A; B) 7! (A\Gg; (A\Gg)Ig ) de ned by the hom-bonds (Rg; Sg) is surjective onto B(hgiK) (again [ 4 ], Proposition 34), we obtain S(K) [ f(M I ; M )g = [ f(CII ; CI ) j (C; CIg ) 2 B(hgiK)g :

Left to prove for the claimed equation is

(CII ; CI ) = (M I ; M ) () CIg = Mg for (C; CIg ) 2 B(hgiK): For (CII ; CI ) = (M I ; M ) we obtain CIg = Mg. Conversely, for CIg = Mg the concept (CII ; CI ) is the smallest concept of B(K) such that its intent contains Mg. (M I ; M ) is the smallest concept of B(K) and it is Mg M . Hence we have (CII ; CI ) = (M I ; M ).

As promised above, we will now show that one can construct the sca olding with any set of 1-generated subcontexts that is covering K.

Theorem 4. For a reduced context K of a doubly founded concept lattice with 1-generated subcontexts Kt (t 2 T ) covering K and Rt := I \ (G Mt) and St := I \ (Gt M ) (t 2 T ) holds

S(K) = S(Rt; St)t2T = [ f(CII ; CI ) j (C; CIt ) 2 B(Kt); CIt 6= Mtg : t2T Proof. The second equality follows like in the proof above. From De nition 1 follows S(Rt; St)t2T S(K). For the proof of the converse inclusion let (A; B) be an element of S(K). Hence B 6= M and therefore by Corollary 1 (A; B) equals ((A \ Gg)II ; (A \ Gg)I ) for some object g 2 G. Since K is covered by the subcontexts Kt (t 2 T ), an index s 2 T exists with g 2 Gs. As Ks is arrow-closed, hgiK is a subcontext of Ks (esp. Gg Gs G) and we have:

A = (A \ Gg)II (A \ Gs)II

AII = A which (using Proposition 1) yields

A = (A \ Gs)II = (AI \ Ms)IsII = ARsIsII = ARsIsSsI = ARs SsI and therefore (A; B) 2 S(Rt; St)t2T following the de nition in Theorem 2.

The above theorem implies for nite contexts that, if a 1-generated subcontext Ks of K is strictly contained in a 1-generated subcontext Kt of K; then Ks does not have to be used for the construction. Note that in an in nite context an in nite chain without maximal element of 1-generated subcontexts could exist, where each subcontext contains its predecessor. However, it is unclear whether such a situation can occur in a doubly founded context.

In Theorem 4 the sca olding is composed as a union of sets. This motivates the interpretation of these sets as the components of the sca olding (similar to [ 3 ]). However, these components depend on the choice of the subcontexts. Also, in general neither the components nor the corresponding subcontexts need to be disjoint. It has been noted in [ 5 ], Sect. 6, that this disjointness can be achieved in the modular case.

Figure 1 shows an example for the sca olding construction. In the given context, three 1-generated subcontexts are chosen. For each subcontext its concept lattice is constructed, with the smallest element removed. In the lattice diagram, the nine gray colored elements are those, that belong to the sca olding.

The better a context can be decomposed into 1-generated subcontexts, the smaller will its sca olding be. Power set lattices can be regarded as the extreme case for this. A context for a power set lattice of a set S of size n is L = (S; S; I) with (g; m) 2 I () g 6= m for g; m 2 S. In this context we have g %. m () g = m and thus hgiL = (fgg; fgg; ;) for all g 2 S. While the concept lattice grows exponentially with the size of the set n (i. e., has 2n concepts) the cardinality of the sca olding grows only linearly (i. e., the sca olding consists of n disjoint components, each containing only one element { the object concept g where g is the object generating the subcontext).

To construct the sca olding of a formal context one has to nd a set of 1generated covering subcontexts and then compute the concept lattices to those subcontexts. It is clear that if a context is 1-generated itself, one will have to construct the whole concept lattice of that context and the sca olding will contain all elements of the lattice but its smallest. Thus in this (worst) case the complexity of the construction is equal to the complexity of constructing the concept lattice from its context. However, if the the context can be decomposed into many small 1-generated subcontexts (like in the example of the power set lattice), only the lattices of the small contexts have to be computed. Then the time for computing the sca olding will be signi cantly shorter than the time for computing the whole lattice. 4

The diagram of a sca olding

Wille describes a graphical representation of the sca olding (cf. [ 5 ]) based on the usual line diagrams of lattices. In this section we will adapt that visualization scheme for our context based sca olding. Let K be a reduced context of a doubly founded complete lattice and Kt (t 2 T ) be 1-generated subcontexts covering K. For (C1; C1It ); (C2; C2It ) 2 B(Kt) we have (C1II ; C1I ) (C2II ; C2I ) () (C1; C1It ) (C2; C2It ) ; because C1 C2 implies C1II C2II and C2I C1I implies C2It C1It . Therefore within one component we can calculate the supremum of elements (AIxI ; AIx) (x 2 X where X is an index set) with (Ax; AIxt ) 2 B(Kt) via supf(AIxI ; AIx) j x 2 Xg = (CII ; CI ) , where (C; CIt ) = suptf(Ax; AIxt ) j x 2 Xg (here, supt is the supremum operation in B(Kt)). Next, we take a look at the relations between elements of di erent components. Let (A; B) 2 B(Ks) and

CIts

( ) A

CII and thus: (C; D) 2 B(Kt) be concepts of two of the chosen subcontexts. We have (AII ; AI ) (CII ; CI ) ()

AII

CII () A

CII : This order relation can be described using the relations Ist := I \ (Gs Mt) and Its := I \ (Gt Ms). Ist and Its are bond products (Ist = Ss Rt and Its = St Rs, with (Rs; Ss) and (Rt; St) de ned as before). Therefore, they are bonds themselves { Ist from Ks to Kt and Its from Kt to Ks. From A Gs and B Ms follows () A

CII \Gs () (A; B)

(CII \Gs; CI \Ms) () B (AII ; AI ) (CII ; CI ) ()

CIts

B: Since we can determine the order in the sca olding from the elements of the lattices of the subcontexts and the bonds between them, we will use these elements to construct a diagram. However, elements of the sca olding can belong to more than one component. When drawing the sca olding we will have to identify such two elements and therefore factor the set D of all the concepts of the lattices B(Kt) (t 2 T ) by the equivalence relation

:= f((A; B); (C; D)) 2 D2 j (AII ; AI ) = (CII ; CI )g : By the rule ( ) concepts (A; B) 2 B(Ks) and (C; D) 2 B(Kt) are equivalent i CIts AIs and AIst CIt . Note, that the two inclusions together imply CIts = AIs and AIst = CIt . The order on D= given by [(A; B)] [(C; D)] : ()

CIts

B is well-de ned and consistent with the order of the corresponding sca olding elements. Particularly, (A; B) = (CItsIs ; CIts ) is the largest concept of B(Ks) whose equivalence class is smaller than the one of (C; CIt ): We are now ready to draw a diagram of the sca olding in four steps: 1. We draw the line diagrams for B(Kt) (t 2 T ) omitting each lattice's smallest element. Objects and attributes are annotated as usual. 2. We calculate the relations between the elements of di erent components using the bonds Ist (s; t 2 T ). If two elements are equivalent according to D, we enclose them with a circle. The order relation will be visualized by dashed lines. If CIts = B for (A; B) 2 B(Ks) and (C; D) 2 B(Kt), then (A; B) is the largest concept of B(Ks) with an equivalence class smaller than that of (C; D). In the diagram we move (A; B) below (C; D) and connect them by a dashed line. The structure of the line diagram of B(Ks) n f(MsIs ; Ms)g must hereby be retained. 3. We erase any dashed line between two elements, if there already exists another path of upward lines. This deletion realizes the transitive reduction that is also conducted drawing regular line diagrams.

The resulting diagram with dashed and regular lines is the line diagram of the ordered set S(K): All objects below some node form the extent and all attributes above the node form the intent of that node's concept. Other than in the line diagram of a lattice the suprema and in ma can not simply be read from the lines. Only within a component the regular lines indicate suprema. Fig. 1 shows the diagram of the sca olding of a given context (below the three small contexts). 5

Conclusion

In this paper, we have translated the notion of the sca olding into the language of Formal Concept Analysis and we have extended the class of lattices for that it is de ned. We have presented a construction of the sca olding from a given reduced context (of a doubly founded lattice) without constructing the concept lattice rst. Further, we have described a method to draw and interpret the corresponding diagrams.

References

1. Birkho , G.: Lattice theory . In: Colloquium Publications , vol. 25 . Amer. Math. Soc. , 3 . edn. ( 1967 )

2. Duquenne , V. : The core of nite lattices . Discrete Math . 87 ( 2-3 ), 133 { 147 ( 1991 )

3. Ganter , B. , Poguntke , W. , Wille , R.: Finite sublattices of four-generated modular lattices . Algebra Univ . 12 , 160 { 171 ( 1981 )

4. Ganter , B. , Wille , R.: Formal Concept Analysis: Mathematical Foundations . Springer-Verlag, Berlin/Heidelberg ( 1999 )

5. Wille , R.: Subdirekte Produkte vollstandiger Verbande . J. reine angew. Math. 283/284 , 53{ 70 ( 1976 )