Introduction

The notion of the scaffolding was introduced by Rudolf Wille in [5]. There, the scaffolding of a complete lattice L of finite 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 finite length is uniquely determined by its scaffolding up to isomorphism. The construction of the scaffolding is closely related to subdirect decomposition. If a lattice is decomposable into small factors, its scaffolding will contain significantly fewer elements than the lattice itself. Like lattices, their scaffoldings can also be visualized by diagrams. The scaffolding diagrams are an extension of the usual line diagrams. Although they require more interpretation effort, they can increase readibility a lot, especially when the scaffolding 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 scaffolding consisting of only 15 elements. In this paper we explain the construction of the scaffolding and its diagram from a given formal context without constructing the corresponding concept lattice first. Further, we extend the definition of the scaffolding to doubly founded complete lattices. In the next section we will recall the scaffolding as it was constructed in [5]. Other definitions or properties of contexts and lattices will be recalled when used.

The Scaffolding of a complete lattice of finite length

A relative sup-subsemilattice of a complete lattice L is a subset S ⊆ L together with a partial operation sup S such that sup S A = s ⇐⇒ sup A = s holds for A ⊆ S and s ∈ S. The partial operation sup S induces an order ≤ S on S by x ≤ S y : ⇐⇒ sup S {x, y} = y that is consistent with the order on L. The scaffolding of a complete lattice L is constructed as a relative sup-subsemilattice of L using a specific set of separating complete homomorphisms α t : L → L t (t ∈ T where T is a suitable index set) and their residual maps α t :

L t → L : x → inf α −1 t x.

Here, separating means that for any two elements x, y ∈ L there is an element t ∈ T with α t (x) = α t (y). Theorem 1 summarizes two important results of [5]:

Theorem 1. For an arbitrary index set T , complete lattices L and L t (t ∈ T ) and separating complete homomorphisms

α t : L → L t S(α t | t ∈ T ) := {α t α t x | x ∈ L, t ∈ T } \ {0}

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 | t ∈ T ).

The latter part of the theorem points out a method to reconstruct L from S(α t | t ∈ T ) as an isomorphic copy of the complete lattice of ideals of the scaffolding. An ideal of a relative sup-subsemilattice S is a subset I ⊆ S that is closed against the partial supremum-operation sup S and that with each element x ∈ 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 finite lattice L a minimal subset of L is constructed such that its lattice of filters 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 L t (t ∈ T ), such that L is a (complete) subdirect product of the L t while none of the L t is isomorphic to L. A lattice that is complete and subdirectly irreducible is also completely subdirectly irreducible. In the case of finite 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 scaffoldings, one fixes the choice of the L t and α t in the construction of Theorem 1. Considered are all completely subdirectly irreducible factors L t of the lattice L and all surjective complete homomorphisms α t : L → L t . For lattices of finite length (thus the L t are also subdirectly irreducible) these α t are separating (cf. [5] or [1], p. 193) and therefore one can define the scaffolding of L as S(L) := S(α t | t ∈ T ). An element x ∈ 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 scaffolding 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 scaffolding 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 K x a context (G x , M x , I x ). 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 scaffolding from a formal context.

The Scaffolding 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 K s to K t is a relation R st ⊆ G s × M t , such that g Rst is an intent of K t for every object g ∈ G s and m Rst is an extent of K s for every attribute m ∈ M t . For bonds R rs from K r to K s and R st from K s to K t the bond product, defined by

R rs • R st := {(g, m) ∈ G r × M t | g RrsIs ⊆ m Rst } ,

is itself a bond from K r to K t . The significance of the bond notion stems from the fact that bonds from K s to K t correspond one-to-one to the sup-morphisms from B(K s ) to B(K t ) and the bonds from

K t to K s correspond one-to-one to the inf-morphisms from B(K s ) to B(K t ). For example, a bond R from K s to K t yields a sup-morphism from B(K s ) to B(K t ) via (A, B) → (A RIt , A R ) . Each complete homomorphism from B(K s ) to B(K t ) is thus defined via (A, B) → (B S , A R )

by a pair (R, S) of bonds (R from K s to K t , S from K t to K s ) where A RIt = B S holds for every (A, B) ∈ B(K s ) (equiv. B SIt = A R ). 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 (R t , S t ) from

K to K t (t ∈ T ) is called separating, if for any two extents A = C of K an index t ∈ T exists such that A Rt = C Rt .

The following proposition presents some useful rules for bond arithmetics.

Proposition 1. Let R rs , R st and R rt be bonds from K r to K s , K s to K t and K r to K t resp. and A ⊆ G r , B ⊆ M t . The following hold:

1. A IrIrRrs = A Rrs and B ItItRst = B Rst , 2. A Rrs•Rst = A RrsIsRst and B Rrs•Rst = B RstIsRrs , 3. A R•S ⊇ A Is and A (R•S)IsR = A R for hom-bonds (R, S) from K r to K s .

Proof. 1 simply follows from the bond properties and 2 follows from Proposition 83 in [4]. 3: According to 2 we have We are now ready to begin our construction.

A R•S = A RIsS = B SS ⊇ B = A Is and A (R•S)IsR = (A RIsS ) IsR = (B SS ) SIs = B SIs = A RIsIs = A R using the hom-bond property twice. a b c d e f g 1 × × × × × × 2 × × × × × 3 × × 4 × × × × 5 × × × × × × 6 × × × × × 7 × × × a b c 1 × × 2 × 3 × b c d 1 × × 3 × 4 × e f g 5 × × 6 × 7 ×1

Theorem 2. For separating hom-bonds (R t , S t ) between K and K t (t ∈ T )

S(R t , S t ) t∈T := {(A Rt•StI , A Rt•St ) | (A, B) ∈ B(K), t ∈ T } \ {(M I , M )} is a supremum-dense subset of B(K). Proof. For (A, B) ∈ B(K) we show (A, B) = sup{(A Rt•StI , A Rt•St ) | t ∈ T } by proving A = ( t∈T A Rt•St ) I . For an arbitrary index u ∈ T holds ( t∈T A Rt•St ) IRu = ( t∈T A Rt•StII ) IRu = ( t∈T A Rt•StI ) IIRu = ( t∈T A Rt•StI ) Ru

by Proposition 1.1. From Proposition 1.3 we get:

A Rt•StI ⊆ A II = A =⇒ t∈T A Rt•StI ⊆ A =⇒ ( t∈T A Rt•StI ) Ru ⊇ A Ru and t∈T A Rt•St ⊆ A Ru•Su ⇒ ( t∈T A Rt•St ) I ⊇ A Ru•SuI ⇒ ( t∈T A Rt•St ) IRu ⊆ A Ru•SuIRu = A Ru .

Thus we have (t∈T A Rt•St ) IRu = ( t∈T A Rt•StI ) Ru = A Ru for all u ∈ T and therefore A = ( t∈T A Rt•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 ∈ L there always are elements s, t ∈ 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], Definition 26). Note that every finite 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 define doubly founded contexts. In fact, the context of a doubly founded lattice is always doubly founded. The definition 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], Definition 25), i.e.

-g m ⇐⇒ γg ∧ µm = sup{(A, B) ∈ B(K) | (A, B) < γg} = γg -g m ⇐⇒ γg ∨ µm = inf{(A, B) ∈ B(K) | (A, B) > µm} = µ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 ∈ G and m ∈ M it always holds that from g ∈ H and g m follows m ∈ N and from m ∈ N and g m follows g ∈ H.

For an object g ∈ G there always exists a smallest arrow-closed subcontext g K = (G g , M g , I g ) 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

K t of K (t ∈ T ) are said to cover K, if t∈T G t = G and t∈T M t = M .

The scaffolding of a reduced context of a doubly founded concept lattice is now defined using the construction of Theorem 2 by fixing specific subcontexts and bonds. Proposition 2. If K is a reduced context of a doubly founded concept lattice and g K = (G g , M g , I g ), then (R g , S g ) with R g := I∩(G×M g ) and S g := I∩(G g ×M ) (g ∈ 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 g K (g ∈ G). The bond properties of R g and S g (g ∈ G) and the hom-bond condition follow easily from the fact that the subcontexts g K are arrow-closed and thus compatible (cf. [4], Proposition 36). Left to prove is that (R g , S g ) (g ∈ G) are also separating. Suppose for two extents A, C of K holds A Rg = C Rg for all g ∈ G. By the definintion of the bonds this means A I ∩ M g = C I ∩ M g for all g ∈ G and since the subcontexts g K (g ∈ G) cover K, we have A I = C I and thus A = A II = C II = C. Definition 1. If B(K) is the doubly founded concept lattice of a reduced context K and (R g , S g ) are as above, then the relative sup-semilattice

S(R g , S g ) g∈G = {(A Rg•SgI , A Rg•Sg ) | (A, B) ∈ B(K), g ∈ G} \ {(M I , M )}

is called the scaffolding of K and will be denoted by S(K).

By the above proposition the scaffolding is well-defined. If one constructed the scaffolding according to the definition above, one would need B(K) first. This is an obvious drawback considering that one of the goals of the scaffolding 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 first we have to prove that our definition is consistent with the construction in [5] described in the previous section.

Theorem 3. For a reduced context K of a lattice of finite length the scaffolding of the context S(K) is equal to the scaffolding of the lattice S(B(K)).

Proof. By (A, B) → (A S , A R ) hom-bonds (R, S) from K to a context L define a complete homomorphism B(K) → B(L). From this it is easy to see that separating hom-bonds define separating complete homomorphisms and vice versa.

Claim:

S(α t | t ∈ T ) = S(R t , S t ) t∈T if α t : B(K) → B(K t ) are the complete homomorphisms defined by (R t , S t ) (t ∈ T ).

As α t is residual to α t , Corollary 112 in [4] states that the bond from K t to K defining the sup-morphism α t is in fact S t . Since α is a sup-morphism too (defined by the bond R t ), 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) = (A Rt•StI , A Rt•St ).

In order to construct the scaffolding, 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 finite length (in fact of all doubly founded lattices) correspond to the 1-generated subcontexts K g (g ∈ G) (cf. [4], Propositions 61 and 62) and the associated projections are given by B [4], Proposition 34). It is easy to see that the hom-bonds to these complete homomorphisms are (R g , S g ) as defined above. Thus S(K) and S(B(K)) meet the requirements of the claim and are therefore equal.

(K) → B(K g ) : (A, B) → (A ∩ G g , B ∩ M g ) (cf.

Analogously to [5] it is also possible to define the scaffolding by subirreducible elements. We restate this in the next corollary, which presents a first simplification of the scaffolding construction: it allows to compute S(K) without computing B(K) first.

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

S(K)= g∈G {(C II , C I ) | (C, C Ig ) ∈ B( g K ), C Ig = M g } .

Proof. Similarly to the proof above follows that a concept (A, B) is subirreducible iff K has a 1-generated subcontext (H, N, J) such that the equation

(A, B) = (A R•SI , A R•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:

A R•S = A RJS = (A I ∩ N ) JS = (B I ∩ H) S = (A ∩ H) I .

Considering that the composed operator R • S is idempotent (Proposition 1.3), it follows immediately from Definition 1 that S(K) is the set of all subirreducible elements. Since the map (A, B) → (A∩G g , (A∩G g ) Ig ) defined by the hom-bonds (R g , S g ) is surjective onto B( g K ) (again [4], Proposition 34), we obtain

S(K) ∪ {(M I , M )} = g∈G {(C II , C I ) | (C, C Ig ) ∈ B( g K )} .

Left to prove for the claimed equation is

(C II , C I ) = (M I , M ) ⇐⇒ C Ig = M g for (C, C Ig ) ∈ B( g K ).

For (C II , C I ) = (M I , M ) we obtain

C Ig = M g . Conversely, for C Ig = M g the concept (C II , C I ) is the smallest concept of B(K) such that its intent contains M g . (M I , M ) is the smallest concept of B(K) and it is M g ⊆ M . Hence we have (C II , C I ) = (M I , M ).

As promised above, we will now show that one can construct the scaffolding 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 K t (t ∈ T ) covering K and R t := I ∩ (G × M t ) and

S t := I ∩ (G t × M ) (t ∈ T ) holds S(K) = S(R t , S t ) t∈T = t∈T {(C II , C I ) | (C, C It ) ∈ B(K t ), C It = M t } .

Proof. The second equality follows like in the proof above. From Definition 1 follows S(R t , S t ) t∈T ⊆ S(K). For the proof of the converse inclusion let (A, B) be an element of S(K). Hence B = M and therefore by Corollary 1 (A, B) equals ((A ∩ G g ) II , (A ∩ G g ) I ) for some object g ∈ G. Since K is covered by the subcontexts K t (t ∈ T ), an index s ∈ T exists with g ∈ G s . As K s is arrow-closed, g K is a subcontext of K s (esp. G g ⊆ G s ⊆ G) and we have:

A = (A ∩ G g ) II ⊆ (A ∩ G s ) II ⊆ A II = A which (using Proposition 1) yields A = (A ∩ G s ) II = (A I ∩ M s ) IsII = A RsIsII = A RsIsSsI = A Rs•SsI

and therefore (A, B) ∈ S(R t , S t ) t∈T following the definition in Theorem 2.

The above theorem implies for finite contexts that, if a 1-generated subcontext K s of K is strictly contained in a 1-generated subcontext K t of K, then K s does not have to be used for the construction. Note that in an infinite context an infinite 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 scaffolding is composed as a union of sets. This motivates the interpretation of these sets as the components of the scaffolding (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 scaffolding 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 scaffolding.

The better a context can be decomposed into 1-generated subcontexts, the smaller will its scaffolding 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) ∈ I ⇐⇒ g = m for g, m ∈ S. In this context we have g m ⇐⇒ g = m and thus g L = ({g}, {g}, ∅) for all g ∈ S. While the concept lattice grows exponentially with the size of the set n (i. e., has 2 n concepts) the cardinality of the scaffolding grows only linearly (i. e., the scaffolding 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 scaffolding of a formal context one has to find 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 scaffolding 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 scaffolding will be significantly shorter than the time for computing the whole lattice.

The diagram of a scaffolding

Wille describes a graphical representation of the scaffolding (cf. [5]) based on the usual line diagrams of lattices. In this section we will adapt that visualization scheme for our context based scaffolding. Let K be a reduced context of a doubly founded complete lattice and K t (t ∈ T ) be 1-generated subcontexts covering K. (here, sup t is the supremum operation in B(K t )). Next, we take a look at the relations between elements of different components. Let (A, B) ∈ B(K s ) and 4. Since the contexts K t are not necessarily disjoint, annotations of the same object/attribute can occur more than once. Since the context is reduced, all object concepts are supremum-irreducible and thus contained in the (supremum-dense) scaffolding. Hence, there is one smallest element for each g ∈ G in the diagram annotated with g. We erase all other object annotations. The same consideration does not apply for attributes. We determine the maximal elements annotated with m in the diagram and delete m on all others.

For (C 1 , C It 1 ), (C 2 , C It 2 ) ∈ B(K t ) we have (C II 1 , C I 1 ) ≤ (C II 2 , C I 2 ) ⇐⇒ (C 1 , C It 1 ) ≤ (C 2 , C It 2 ) , because C 1 ⊆ C 2 implies C II 1 ⊆ C II

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 infima can not simply be read from the lines. Only within a component the regular lines indicate suprema. Fig. 1 shows the diagram of the scaffolding of a given context (below the three small contexts).

Conclusion

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