Definition 3[40]Let L be a lattice.An ele-ment x∈L is join-irreducible,if(i) x≠0(in case L has a zero)(ii)x=a∨b implies x=a or x=b for all a,b∈L.
Dually,a meet-irreducible element is defined as following.
Let L be a lattice.An element x∈ L is meet-ir-reducible,if(i) x≠0(in case L has a zero)(ii)x=a∧b implies x=a and x=b for all a,b∈L.
We denote the set of join-irreducible elements of L by J(L)and the set of meet-irreducible ele-ments by M(L).
Let P be an ordered set and Q⊆P,then Q is called join-dense in P if for every element a∈P,there is a subset A of Q such that a=∨PA.Corre-spondingly,Q is called meet-dense in P if for every element a∈P,there is a subset A of Q such that a=∧PA.
Definition 4[9]A formal context(G,M,I)con-sists of two sets G and M and a relation I between G and M.The elements of Gare called the objects and the elements of M are called the attributes of the context.
In order to express that an object g is in a rela-tion I with an attribute m,we write g Im or(g,m)∈I and read it as "the object g has the attri-bute m".
For an object g∈G,we write g∗instead of{g}∗for the object intent{m∈M|gIm}of the objectg.Correspondingly,m∗:={g∈G|gIm}is the attribute extent of the attribute m.
We write OC(L)for the object concept(g∗∗,g∗)and AC(L)for the attribute concept(m∗,m∗∗).
For X⊆G and A⊆M,a pair of operators,∗:P(G)→P(M)and∗:P(M)→P(G),are defined by
If X,X1,X2⊆G are sets of objects and A,A1,A2⊆Mare sets of attributes,the following con-clusions hold[9]:
Given a formal context(G,M,I),a formal con-cept is defined to be a pair(X,A)of an object sub-set X⊆G and an attribute subset A⊆M,where X*=A and A*=X.Xis called the extension and A is called the intension of the concept(X,A).We write the set of the extensions and the set of intensions of all the concepts as LG(G,M,I)and LM(G,M,I),re-spectively.
It is easy to know that both(X**,X*)and(A*,A**)are formal concepts.
where Ic=(G×M)-I.
If X,X1,X2⊆G are sets of objects and A,A1,A2⊆Mare sets of attributes,the following con-clusions hold[41]:
Given a formal context(G,M,I),a concept in-duced by its negative operators is called a N-con-cept.
Definition 6[31]Let(G,M,I)be a binary infor-mation table.A pair[X,(A,B)]of an object subset X⊆G and two attribute subsets A,B⊆Mis called an object-induced three-way concept,for short,an OE-concept,of(G,M,I),if and only if X∗=(A,B)and(A,B)∗=X.All OE-concept form a complete lattice,which is called the object-induced three-way con-cept lattice of(G,M,I)and written as OEL(G,M,I).
Definition 7[9]A context(G,M,I)is called clarified,if for any objectsg,h∈G,g∗=h*it always follows that g=hand,correspondingly,m∗=n*im-plies m=n for all m,n∈M.
Definition 8[37]Let(G,M,I)be a formal con-text.If a*∩b∗=φ and a*∪b∗=G with a∈M,b∈M,then a is called as the dual attribute to b and denot-ed by b̂.
Proposition 1[9]If(G,M,I)is a formal con-text,∀(X,A)∈L,
Meet-irreducible elements are attribute con-cepts,whereas attribute concepts are not necessarily meet-irreducible elements,dually,join-irreducible el-ements are object concepts,whereas object concepts are not necessarily join-irreducible elements[9].
Lemma 1[9]If T is an index set and,for ev-ery t∈T,Xt⊆G is a set of objects,then
Proposition 2[9]The concept lattice L(G,M,I)is a complete lattice in which infimum and supre-mum are given by:
Theorem 1[37]If(G,M,I)is a clarified attri-bute dual context,|M|must be even.Where|M|represents the cardinality of the set.
Definition 9[35]Let L be a lattice.L satisfies the ∨-simplification law if,for all a1,a2,a3∈L.a1∨a2=a1∨a3implies a2=a3.
Definition 10[9]A context(G,M,I)is regular,if∀x∈G,x*≠φ,x∗≠M,and ∀a∈M,a*≠φ,a∗≠G.
Lemma 2[42]Let(G,M,I)be a formal con-text.∀a∈M,∀g∈G,then
Definition 11[40]If L is a finite lattice.For each l∈L,we define its opposite element as:
Lemma 3[35]If L is an arbitrary finite lattice.For all l∈L,
Definition 12[40]A lattice L with 0 is said to be pseudocomplemented if,for each a∈L,there ex-ists an element a′∈L such that,for all b∈L,a∧b=0⇔b≤a′,that is,
Definition 13 A lattice L with 0 is said to be∧-pseudocomplemented if,for each l∈M(L),there exists an element,such that,for all a∈L,
Definition 14 A lattice L with 0 is said to be dual ∧-pseudocomplemented if,for each l∈M(L),there exists an element lop∈M(L),such that,for all l̂∈ M(L),
We can specify lopas
Definition 15 A lattice L with 0,M(L)is closed with respect to pseudocomplement,if the set has a dual∧-pseudocomplemented of M(L).
Definition 16[40]Let L be a lattice with 0 and 1.For a∈L,we say b∈L is a complement of a,if a∧b=0 and a∨b=1.
“I think it is gone,” he said. But it was not gone; it was one of those bits of the looking-glass—that magic mirror, of which we have spoken—the ugly glass which made everything great and good appear small and ugly, while all that was wicked and bad became more visible, and every little fault could be plainly seen. Poor little Kay had also received a small grain in his heart, which very quickly turned to a lump of ice. He felt no more pain, but the glass was there still. “Why do you cry?” said he at last; “it makes you look ugly. There is nothing the matter with me now. Oh, see!” he cried suddenly, “that rose is worm-eaten, and this one is quite crooked15. After all they are ugly roses, just like the box in which they stand,” and then he kicked the boxes with his foot, and pulled off the two roses.
Definition 17[35]A lattice L is said to be∧-complemented if for all l∈M(L),we have that lopis a complement of l,i.e.lop∧l=0 and lop∨l=1.
Definition 18[40]If L is an ordered set,given one element l∈L,the up-set and down-set of l are[l)={x∈L|l≤x}and(l]={x∈L|x≤l},respectively.
In this paper,lAdenotes(l]∩A(L)and lMd e-notes[l)∩M(L).
Theorem 2[37]If(G,M,I)is a clarified attri-bute dual context,then
where Ic=(G×M)-I.
Theorem 3[37]Let(G,M,I)be a clarified attri-bute dual context,then
Definition 19[40]Let P and Q be ordered sets.A map φ:P→Q is said to be
(1)order-preserving if x≤ y in P implies
(2)an order-embedding if x≤ y in P if and only if φ(x)≤φ(y)in Q;
(3)An order-isomorphism if it is an order-em-bedding which maps P onto Q;
3 Characterizing of Concept Lattices
Proposition 4 Let(G,M,I)be a clarified attri-bute dual context,we have the following properties:
Proof
(4)From(1),∀g∈G,(g**,g*)=(g,g*)obvious-ly holds.
Proposition 5 If(G,M,I)is a clarified attri-bute dual context,J(L)=OC(L).
Proof Since join-irreducible elements are ob-ject concepts,whereas object concepts are not neces-sarily join-irreducible elements[8],then
Now,let's prove that OC(L)⊆J(L).
And,according to Proposition 4,we then have{h∈G|g*⊂h*}=φ.Then,according to Lemma 2,
holds.Therefore,
From Proposition 4,we can see that J(L)={(g,g*)|g∈G}.
Proposition 6 If(G,M,I)is a clarified attribute dual context,we have A(L)={(g,g*)|g∈G}.
Proof Fixed,g0∈G,if(X,A)is a concept such that(φ,M)<(X,A)≤ (g0,g0∗)which implies
According to the Definition 2,atoms are join-irreducible elements.By Proposition 5 and Proposi-tion 6,we can easily come to the following Lemma:
Lemma 4 If(G,M,I)is a clarified attribute dual context,then J(L)=A(L).
Lemma 4 and Proposition 5 show that all atoms and join-irreducible elements of concept lattice are object concepts.
Proposition 7 If(G,M,I)is a clarified attri-bute dual context,then(L,≤)satisfies ∨-simplifica-tion law.
Proof Assume there are three concepts a1=(X1,A),a2=(X2,B),a3=(X3,C),and a1∨a2=a1∨a3,whereas a2≠a3.
From formula(2),we can know
From equation a1∨a2=a1∨a3,we have
From Lemma 4,we know
Therefore,the theorem holds.
Then dually,whether the attribute concepts(m*,m**)are meet-irreducible?To clarify the ques-tion,we illustrate it through Example 1.
Example 1[36]If(G,M,I)is a formal context,G={1,2,3,4},M={a,b,c,d},details of L are shown in Table 1 and Fig.1..
Table 1 Formal context(G，M，I)
Table 2 Formal context(G，M，I)
Fig.1 L(G,M,I)in Example 3.1
We can get the following meet-irreducible ele-ments of the concept lattice:
However,(1,acde)=(d*,d**)is not always meet-irreducible element.
Example 2 If(G,M,I)is a clarified attribute dual context,details of L are shown in Table 2 and Fig.2.
Fig.2 L(G,M,I)in Example 3.2
We can easily have
Example 2 shows that there are special cases in which the statement“the attribute concepts are meet-irreducible in clarified attribute dual context”is valid,then,under what circumstance this state-ment is always true?
Proposition 8 If K=(G,M,I)is a clarified attri-bute dual context,M(L)={(m*,m**)|m∈M}.
Proof Since meet-irreducible elements are at-tribute concepts,whereas attribute concepts are not necessarily meet-irreducible elements[8],then
i)if{X ∈LG(K)|m*⊂X}={G},∀m∈M.
Since K=(G,M,I)is a clarified attribute dual context and by Definition 10,we have(G,M,I)is regular,thus
ii)if
which means that{a∈M|m*⊂X}≠φ.By formula(1)and formula(3),we know
we have∃a∈M,m*=a*.
If(a*,a**)is not a meet-irreducible element,by Definition 7,we have m*=a*⇒m=a.∀X,Y∈LG(K),m*=X∩Y,thus
By the formula(1)and formula(3),then
By the formular(8)and(9),hence
It contradicts with m*=X∩Y.Then,
According to Lemma 2,we have
By the formular(7)and(10),therefore M(L)=AC(L)holds.
Now,we investigate the relationship between m and m̂.
Lemma 5 Let(G,M,I)be a clarified attribute dual context,then ∀m∈M,(m*,m**)and(m̂*,m̂**)are both complemented.
Proof Since m*∩m̂*=φ and m∗∪m̂∗=G,we then have
Proposition 9 Let K=(G,M,I)be a clarified attribute dual context.If the pseudocomplement of l∈M(L)exists,then
(1)lop={l̂∈ M(L)|l̂∧ l=0},
(2)M(L)is closed with respect to pseudocom-plement.
Proof (1)By Proposition 8,AC(L)=M(L),we consider
By Proposition 5 and Lemma 3,the equality lop=∨{x∈A(L)|x∉lA}holds.
By Lemma 4,we have
Since m*∩m̂*=φ and m∗∪m̂∗=G,by Lemma 5 and Definition 13,we have
(2)By the definition of ∧-pseudocomplement and Definition 15,this conclusion is obvious.
Proposition 10 Let K=(G,M,I)be a clarified attribute dual context,if(X,A)∈M(L),then the pseudocomplement of(X,A)is a ∧-complement.
Proof Since it follows from Proposition 9,Definition 16,Lemma 5 and Definition 17 holds.
Theorem 4 Let L be a complete lattice,if L satisfies the following properties:
(1)A(L)=J(L).
(2)L fits ∨-simplification law.
(3)M(L)is closed with respect to pseudocom-plement.
Then the complete lattice L is isomorphic to concept lattice B(K)in clarified attribute dual con-text.
Proof In the clarified attribute dual context
there is a mapping:
We will prove:
1)the mapping h is well defined,i.e.h(l)is a concept in the lattice B(K);
2)his an order-embedding;
3)his bijection.
lM={m∈M(L)|g≤m,∀g∈lA}.Due to the Defi-nition of lMand lA,transitivity of≤,hence
is obvious.
If m∈M(L),then we have g≤m,∀g∈lAand A(L)=J(L),we then have
1b)We prove that lA=(lM)∗holds.
lA={g∈J(L)|g≤m,∀m∈lM},i.e.any atomg satisfies g≤l if and only if g≤m,∀m∈lM.
If g≤m,∀m∈lM,by transitivity,then g≤∧lM=l.
2) ∀l1,l2∈L,if l1≤l2,by Definition 18,then l1A≤l2A,we have h(l1)≤h(l2).∀l1,l2∈L,if h(l1)≤h(l2),this means l1A≤l2A,then
Thus,his an order-embedding.
3)To prove that h is a bijection.
Since the lattice L fits ∨-simplification law,if for all l1,l2,l3∈L,l1∨l2=l1∨l3implies l2=l3,by Definition 18,which yields
We then have
That is clarified.
where l,lop∈M(L).
Since A(L)=J(L),we then have
If h(l1)=h(l2),and since A(L)=J(L)and by the formular(11),then
Therefore,his injective.
Conversely,h(l)≤ (X,Y),if m∈Y=X∗,m∈M(L),then x≤m,∀x∈X,therefore,l≤m,i.e.m∈lM.
Referring to Theorem 2,Theorem 3 and Theo-rem 4,we can get the following theorem.
Theorem 5 Let L be a complete lattice,if L satisfies the following properties:
(1)A(L)=J(L).
(2)L fits ∨ -simplification law.
(3)M(L)is closed with respect to pseudocom-plement.
Then,the complete lattice L,the negative con-cept lattice of B(K)and three-way concept lattice of B(K)are isomorphic to each other in clarified attri-bute dual context.
4 Conclusion
We study atoms,join-irreducible elements,meet-irreducible elements and dual complement ele-ments in clarified attribute dual context,and con-clude that the complete lattice with some certain properties will be isomorphic to the negative con-cept lattice and three-way concept.
In addition,Zhi et al.[39]proposed a complete lattice storage method based on the formal concept analysis theory,however,this method is not effec-tive for storing three-way concept lattices.In this paper,we construct an isomorphic bridge between complete lattice and three-way concept lattice,which can provide the theoretical support for the Zhi's method to store three-way concept lattices.
