Projections of pattern structures don't always lead to pattern structures, however residual projections and o-projections do. As a unifying approach, we introduce the notion of pattern morphisms between pattern structures and provide a general sufficient condition for a homomorphic image of a pattern structure being again a pattern structure. In particular, we receive a better understanding of the theory of o-projections.
Pattern structures within the framework of formal concept analysis have been
introduced in [
The goal of our paper is to establish an adequate concept of pattern morphism
between pattern structures, which also gives a better understanding of the concept of
oprojections as recently introduced and investigated in [
We also derive that a pattern morphism from a pattern structure to a pattern setup (introduced in this paper), which is surjective on the sets of objects, yields again a pattern structure.
Our main result states that a pattern morphism always induces an adjunction between the corresponding concept lattices. In case the underlying map between the sets of objects is surjective, the induced residuated map between the concept lattices turns out to be surjective too.
The fundamental order theoretic concepts of our paper are nicely presented in the book
on Residuation Theory by T.S. Blythe and M.F. Janowitz (cf. [
Definition 1 (Adjunction). Let P p P, ⁄q and L p L, ⁄q be posets; furthermore let f : P L and g : L P be maps. (1) The pair p f , gq is an adjunction w.r.t. pP, Lq if f x ⁄ y is equivalent to x ⁄ gy for all x P P and y P L. In this case, we will refer to pP, L, f , gq as a poset adjunction. (2) f is residuated from P to L if the preimage of a principal ideal in L under f is always a principal ideal in P, that is, for every y P L there exists x P P s.t.
f 1tt P L | t ⁄ yu t s P P | s ⁄ xu. (3) g is residual from L to P if the preimage of a principal filter in P under g is always a principal filter in L, that is, for every x P P there exists y P L s.t.
g 1ts P P | x ⁄ su t t P L | y ⁄ tu. (4) The dual of L is given by Lop p L, ¥q with ¥: tp x, tq P L L | t ⁄ xu. The pair p f , gq is a Galois connection w.r.t. pP, Lq if p f , gq is an adjunction w.r.t. pP, Lopq.
The following well-known facts are straightforward (cf. [
Proposition 1. Let P p P, ⁄q and L p L, ⁄q be posets. (1) A map f : P L is residuated from P to L iff there exists a map g : L P s.t. p f , gq is an adjunction w.r.t. pP, Lq. (2) A map g : L P is residual from L to P iff there exists a map f : P L s.t. p f , gq is an adjunction w.r.t. pP, Lq. (3) If p f , gq and ph, kq are adjunctions w.r.t. pP, Lq with f h or g k then f h and g k. (4) If f is a residuated map from P to L, then there exists a unique residual map f from L to P s.t. p f , f q is an adjunction w.r.t. pP, Lq. In this case, f is called the residual map of f . (5) If g is a residual map from L to P, then there exists a unique residuated map g from P to L s.t. pg , gq is an adjunction w.r.t. pP, Lq. In this case, g is called the residuated map of g.
Definition 2. Let P p P, ⁄q be a poset and T
(1) The restriction of P onto T is given by P|T : p T, ⁄ XpT T qq, which clearly is a poset too. (2) The canonical embedding of P|T into P is given by the map T P, t t. (3) T is a kernel system in P if the canonical embedding τ of P|T into P is residuated.
In this case, the residual map ϕ of τ will also be called the residual map of T in P. The composition κ : τ ϕ is referred to as the kernel operator associated with T in P. (4) Dually, T is a closure system in P if the cannonical embedding τ of P|T into P is residual. In this case, the residuated map ψ of τ will also be called the residuated map of T in P. The composition γ : τ ψ is referred to as the closure operator associated with T in P. (5) A map κ : P P is a kernel operator on P if s ⁄ x is equivalent to s ⁄ κx for all s P κP and x P P.
Remark: In this case, κP forms a kernel system in P, the kernel operator of which is κ. (6) Dually, a map γ : P P is a closure operator on P if x ⁄ t is equivalent to γx ⁄ t for all x P P and t P γP.
Remark: In this case, ϕP forms a closure system in P, the closure operator of which is γ.
The following known facts will be needed for the sequel (cf. [
Proposition 2. Let P p P, ⁄q and L p L, ⁄q be posets. (1) If f is a residuated map from P to L then f preserves all existing suprema in P, that is, if s P P is the supremum (least upper bound) of X P in P then f s is the supremum of f X in L.
In case P and L are complete lattices, the reverse holds too: If a map f from P to L preserves all suprema, that is, f psupP X q supL f X f or all X
P, then f is residuated. (2) If g is a residual map from L to P, then g preserves all existing infima in L, that is, if t P L is the infimum (greatest lower bound) of Y L in L then gt is the infimum of gY in P.
In case P and L are complete lattices, the reverse holds too: If a map g from L to P preserves all infima, that is, f pinfP Y q infL gY f or all Y
L, then g is residual. (3) For an adjunction p f , gq w.r.t. pP, Lq the following hold: (a1) f is an isotone map from P to L. (a2) f g f f (a3) f P is a kernel system in L with f g as associated kernel operator on L. In particular, L P, y f gy is a residual map from L to L| f P. (b1) g is an isotone map from L to P. (b2) g f g g (b3) gL is a closure system in P with g f as associated closure operator on P. In particular, P gL, x g f x is a residuated map from P to P|gL. 3
Definition 3. Let P : p P, S, σ , σ q and Q : p Q, T, τ, τ q be poset adjunctions. Then a pair pα, β q forms a morphism from P to Q if pP, Q, α, α q and pS, T, β , β q are poset adjunctions satisfying τ α β σ
τ σ
β , that is, the following diagrams are commuNext we illustrate the involved poset adjunctions: α α β β σ
P S α β τ
τ
Q T τ σ Definition 4 (Concept Poset). For a poset adjunction P p P, S, σ , σ q let BP : tp p, sq P P
S | σ p s ^ σ s pu denote the set of pformalq concepts in P . Then the concept poset of P is given by BP : p P
Sq | BP , that is, pp0, s0q ⁄ p p1, s1q holds iff p0 ⁄ p1 iff s0 ⁄ s1, for all pp0, s0q, pp1, s1q P BP . If pp, sq is a formal concept in P then p is referred to as extent in P and s as intent in P . Theorem 1. Let pα, β q be a morphism from a poset adjunction P p P, S, σ , σ q to a poset adjunction Q p Q, T, τ, τ q. Then is a poset adjunction for and
pBP , BQ , Φ ,Ψ q Φ : BP
BQ , pp, sq p τ β s, β sq Ψ : BQ
BP , pq, tq p α q, σ α qq.
In addition, if α is surjective then so is Φ .
Remark: In particular we want to point out that α q is an extent in P for every extent q in Q and similarly, β s is an intent in Q for every intent s in P . Proof. Let p p, sq P BP and pq, tq P BQ ; then σ p τ t q. This implies β s β σ p τ α p, thus s and σ s p and τ q t and (since τ τ β s τ τ τ α p τ α p β sq. Similarly, Ψ pq, tq P BQ .
Assume now that Φ p p, sq ⁄ pq, tq holds, which implies β s ⁄ t. It follows that Φ p p, sq p τ β s, β sq P BP τ α p β σ p
β s ⁄ t p ⁄ α τ t α q, and hence that is, p p, sq ⁄ Ψ pq, tq.
Conversely, assume that p p, sq ⁄ Ψ pq, tq holds, which implies p ⁄ α q. It follows that p ⁄ α q α τ t σ β t, and hence β s β σ p ⁄ t, that is, Φ p p, sq ⁄ pq, tq.
Assume now that α is surjective; then α α idQ . Let pq, tq P BP , that is, τ q τ t q. Then for p : α q and s : σ p we have p p, sq P BP since t and σ s σ σ α q σ σ α τ t σ σ σ β t σ β t α τ t α q
Our claim is now that Φ p p, sq p q, tq holds, that is, β s α p α α q q implies t. The latter is true, since β s β σ p τ α p τ q
Discussion for clarification: The question was raised whether, in the previous theorem, the residuated map Φ from BP to BQ allows some modification, since the map P
S
Q
T, p p, sq p α p, β sq is obviously residuated from P S to Q T. However, in general the latter map does not restrict to a map from BP to BQ . Indeed, our construction of the map Φ is of the form p p, sq p α 1 p, β sq. As a warning, we want to point out that, in general, there is no residuated map from BP to BQ of the form p p, sq p α p, β 1sq. The simple reason for this is that β s is an intent in Q for every intent s in P , while there may exist an extent p in P such that α p is not an extent in Q . 4
Definition 5. A triple G p G, D, δ q is a pattern setup if G is a set, D p D, q is a poset, and δ : G D is a map. In case every subset of δ G : t δ g | g P Gu has an infimum in D, we will refer to G as pattern structure. Then the set
CG : t infD δ X | X forms a closure system in D.
If G p G, D, δ q and H p H, E, εq each is a pattern setup, then a pair p f , ϕq forms a pattern morphism from G to H if f : G H is a map and ϕ is a residual map from D to E satisfying ϕ δ ε f , that is, the following diagram is commutative: δ
G D f ϕ
H E ε In the sequel we show how our previous considerations apply to pattern structures. Applications (1) Let G be a pattern structure and H be a pattern setup. If p f , ϕq is a pattern morphism from G to H with f being surjective, then H is also a pattern structure. (2) Let G p G, D, δ q and H p H, E, εq be pattern structures. Also let p f , ϕq be a pattern morphism from G to H .
To apply the previous theorem we give the following construction: f gives rise to an adjunction pα, α q between the power set lattices 2G : p 2G, q and 2H : p 2H , q via and Further let ϕ denote the residuated map of ϕ w.r.t. pE, Dq, that is, pE, D, ϕ , ϕq is a poset adjunction. Then, obviously, pDop, Eop, ϕ, ϕ q is a poset adjunction too. For pattern structures the following operators are essential:
α : 2G α : 2H 2H , X 2G,Y f X f 1Y. : 2G : D : 2H : E
D, X E, Z infD δ X infE εZ 2G, d t g P G | d 2H , e t h P H | e δ gu εhu It now follows that pα, ϕq forms a morphism from the poset adjunction to the poset adjunction
P p 2G, Dop, , q
Q p 2H , Eop, , q. 2G D α ϕ 2H E Replacing Dop by D and Eop by E we receive the following commutative diagrams: In combination we receive the following diagram of Galois connections and adjunctions between them: 2G Dop 2H
E 2G In particular, p f X q ϕpX q holds for all X G.
Here we give an illustration of the constructed adjunctions: For the following we recollect that the concept lattice of G is given by BG : BP — similarly, BH : BQ .
Now we are prepared to give an application of Theorem 1 to concept lattices of pattern structures: pBG , BH , Φ ,Ψ q is an adjunction for and Ψ : BH
BG , pZ, eq p f 1Z, p f 1Zq q.
In case f is surjective, Φ is surjective too.
Remark: This application implies a generalization of Proposition 1 in [
Remark: In [
Remark: In [
In particular, X ϕ pX ) holds for all X G.
Remark: This application gives a better understanding to properly generalize the
concept of projections as discussed in [