The notion of a double Boolean algebra was proposed by Wille in 2000. In 2006, Kwuida redefined this algebraic structure by adding two new axioms, retaining the same name for it. Notions of primary ideals and filters were introduced for this enhanced structure and the prime ideal theorem was proved. In this work, we show that the two axioms considered by Kwuida are derivable in Wille's double Boolean algebra. As a consequence, the prime ideal theorem holds for Wille's double Boolean algebra itself. We also discuss representation theorems for the class of double Boolean algebras, including, in particular, the result for representation of the class of regular double Boolean algebras given recently by Breckner and Sa˘ca˘rea.
Formal concept analysis [
Algebraic studies of dBas led to the natural question whether the important
prime ideal theorem of Boolean algebras also holds for dBas. The question was
addressed by Kwuida. In [
Prosenjit Howlader and Mohua Banerjee
definition of Wille’s dBas (Section 3), and observe the consequence that the
prime ideal theorem proved in [
Preliminaries required for the work are given in the next section. Section 5 concludes the paper. 2
Definition 1. [
For any A ⊆ G, B ⊆ M the following sets are defined: A0 := {m ∈ M : ∀g ∈ G(g ∈ A=⇒gRm)}, B0 := {g ∈ G : ∀m ∈ M (m ∈ M =⇒gRm)}. (A, B) is a concept of K provided A0 = B and B0 = A.
There is a partial order relation ≤ on the set of all concepts defined as follows: for concepts (A1, B1), (A2, B2), (A1, B1) ≤ (A2, B2) if and only if A1 ⊆ A2 (equivalently B2 ⊆ B1).
Notation 1 The set of all concepts of a context K is denoted by B(K). For a concept (A, B) of K, A := ext((A, B)) is its extent and B := int((A, B)) is its intent.
The partial ordered set (B(K), ≤) forms a complete lattice [
Definition 2. Let K := (G, M, R) be a context and A ⊆ G, B ⊆ M . The pair (A, B) is called a semiconcept of K if and only if A0 = B or B0 = A. (A, B) is called a protoconcept of K if and only if A00 = B0.
Notation 2 The set of all semiconcepts of K is denoted by H(K), while that of all protoconcepts is denoted by P(K). Clearly, H(K) ⊆ P(K).
There is a partial order relation ≤ (we use the same notation as before) on the set P(K) of protoconcepts also, defined as follows: (A, B) ≤ (C, D) if and only if A ⊆ C and D ⊆ B, for all (A, B), (C, D) ∈ P(K). The following operations are defined on P(K). For (A1, B1) and (A2, B2) in P(K), (A1, B1) u (A2, B2) := (A1 ∩ A2, (A1 ∩ A2)0 ) (A1, B1) t (A2, B2) := ((B1 ∩ B2)0 , B1 ∩ B2) ¬(A, B) := (G \ A, (G \ A)0 ) y(A, B) := ((M \ B)0 , M \ B) > := (G, φ) ⊥ := (φ, M ).
Remarks on Prime Ideal and Representation Theorems 85
P(K) forms an abstract algebra of type (2, 2, 1, 1, 0, 0) with respect to the above operations. This algebra is called the protoconcept algebra of the context K, and is denoted by P(K) := (P(K), t, u, ¬, y, >, ⊥). The set H(K) of semiconcepts is closed under the above operations and so it forms a subalgebra of the protoconcept algebra, called the semiconcept algebra of K. It is denoted by H(K).
Observation 1 The partial order ≤ on P(K) is characterized by the operations u, t: for all x, y ∈ P(K),
x ≤ y if and only if x u y = x u x and x t y = y t y.
On abstraction of properties of the protoconcept algebra P(K), the double
Boolean algebra (dBa) [
Definition 3. [
Definition 4. A dBa D is called pure if for all x ∈ D, either x u x = x or x t x = x.
In the following, let D := (D, t, u, ¬, y, >, ⊥) be a dBa.
On abstraction of the partial order ≤ in the protoconcept algebra P(K), a relation v is defined on D as follows. For any x, y ∈ D,
x v y if and only if x u y = x u x and x t y = y t y.
v is shown to be a quasi-order on D [
Proposition 1. [
Proposition 2. [
In [
The name ‘double Boolean algebra’ was retained for the new class of algebras by Kwuida. In this section, we prove a sequence of results and conclude in Corollary 1 that the two axioms (a)-(b) above are derivable from Definition 3. In the following, let D := (D, t, u, ¬, y, >, ⊥) denote Wille’s dBa. Proposition 3. For any x, y ∈ D, the following hold. 1. ¬x u ¬x = ¬x and yxtyx =yx, that is
¬x = (¬x)u ∈ Du and yx = (yx)t ∈ Dt. 2. x v y if and only if ¬y v ¬x and yy vyx. 3. ¬¬x = x u x and yyx = x t x. 4. x ∨ y ∈ Du, x ∧ y ∈ Dt. 5. ¬(x ∨ y) = ¬x u ¬y and ¬(x u y) = ¬x ∨ ¬y. 6. y(x ∧ y) =yxtyy and y(x t y) =yx∧yy.
Proof. 1. Let x ∈ D. Axiom (1a) gives x u x ∈ Du. Axiom (4a) and Proposition 1(i) give ¬x = ¬(x u x) ∈ Du. The other part is proved dually. 2. Let x, y ∈ D then x v y if and only if xu vu yu and xt vt yt, by (iii) of Proposition 1. xu vu yu and xt vt yt if and only if ¬yu vu ¬xu and yyt vtyxt, by (i) and (ii) of Proposition 1. ¬yu vu ¬xu and yyt vtyxt if and only if ¬y vu ¬x and yy vtyx, by axioms (4a) and (4b). Finally, ¬y vu ¬x and
Remarks on Prime Ideal and Representation Theorems 87 yy vtyx if and only if ¬y v ¬x and yy vyx, by Proposition 1 and part (1) of this proposition. 3. Proof follows from axioms (4a) and (8a). 4. By part (1) of this proposition, ¬x ∈ Du and yx ∈ Dt. Using the definitions of ∧ and ∨ and closure with respect to the operations in Du and Dt, we get the result. 5. ¬(x ∨ y) = ¬(¬(¬x u ¬y)) = ¬x u ¬y, by axiom (8a).
Now ¬(x u y) = ¬((x u x) u (y u y))(by axioms (1a) − (3a)) = ¬(¬¬x u ¬¬y) (3 of Proposition 3) = ¬x ∨ ¬y (by definition of ∨). 6. Proof is dual to the proof of 5.
Proposition 4. For any x, y ∈ D, we have the following.
1. x u ¬(x t y) = ⊥ 6. xty(x u y) = > 2. ¬(x t y) = ¬(x t y) u ¬x 7. y(x u y) =y(x u y)tyx 3. x u y = x u ¬(x u ¬y) 8. x t y = xty(xtyy) 4. x t (y u ¬x) = x t (y u y) 9. x u (ytyx) = x u (y t y) 5 (x u y) t (x u ¬y) = (x u x) t (x u x) 10 (x t y) u (xtyy) = (x t x) u (x t x) Proof. We give the proofs for 1, 2, 3, 4, 5. The properties of commutativity and associativity are used without mention in the proofs. Let x, y ∈ D. Proof of 1: ⊥ = x u ⊥ (by Proposition 2) = x u ((x t y) u ¬(x t y)) (by axiom (9a)) = (x u (x t y)) u ¬(x t y) = (x u x) u ¬(x t y) (by axiom (5a)) = x u ¬(x t y) (by axiom (1a)).
Proof of 2: ¬(x t y) u ¬x = ¬(x t y) u ¬(x u x) (by axiom (4a)) = ¬(x t y) u ¬((x t y) u x) (by axioms (5a)) = ¬(x t y) u ¬(x t y) (as ¬(x t y) v ¬((x t y) u x)) = ¬(x t y) (by (1) of Proposition 3).
Proof of 3: x u ¬(x u ¬y) = x u (¬x ∨ ¬¬y) (by 5 of Proposition 3) = x u (¬x ∨ (y u y)) (by axioms (8a) and (4a)) = (x u ¬x) ∨ (x u (y u y)) (by axiom (6a)) = ⊥ ∨ (x u y) (by axioms (9a) and (1a)) = x u y (as x u y ∈ Du).
Prosenjit Howlader and Mohua Banerjee Proof of 4: To prove 4, first we show that y u > = y u (x t (y u ¬x)). Now y u > = y u > u > (by axiom (1a)) = y u ¬⊥ (by axiom (10a)) = y u ¬((y u ¬x) u ¬(x t (y u ¬x))) (by 1 of this proposition) = y u ¬(y u (¬x u ¬(x t (y u ¬x)))) = y u ¬(y u ¬(x t (y u ¬x))) (by 2 of this proposition) = y u (x t (y u ¬x)) (by 3 of this proposition). (*) Now x t (y u y) = x t (y u y) t (y u y) (by axioms (1b) ) = x t ((y u y) t ((y u y) u ¬x)) (by axiom (5b)) = x t ((y u y) t (y u ¬x)) (by (1a)) = x t ((y u >) t (y u ¬x)) (by Proposition 2) = x t (y u (x t (y u ¬x)) t (y u ¬x) (by (*)) = (x t (y u ¬x)) t (y u (x t (y u ¬x))) = (x t (y u ¬x)) t (x t (y u ¬x))(by axiom(5b)) = (x t (y u ¬x)) (by axiom (1b)).
Proof of 5: (xuy)t(xu¬y) = (xuy)t(xu¬(xu¬¬y)) (by 3 of this proposition) = (x u y) t (x u ¬(x u y u y)) (by axioms (4a) and (8a)) = (x u y) t (x u ¬(x u y)) (by axiom (1a)) = (x u y) t (x u x) (by 4 of this proposition) = ((x u x) u y) t (x u x) (by axiom (1a)) = (x u x) t (x u x) (by axiom (5b)).
The proofs of 6, 7, 8, 9, 10 are dual to those of 1, 2, 3, 4, 5 respectively.
We now conclude that the new structure defined by Kwuida is, in fact, equivalent to Wille’s dBa:
(a) (x t y) u (xtyy) v x t x. (b) x u x v (x u y) t (x u ¬y).
Proof. Follows from 5 and 10 of Theorem 2, and Proposition 2(4).
Kwuida generalized the notion of prime filter (ideal) of Boolean algebras to
that of ‘primary filter’ (‘primary ideal’) for dBas defined in [
A filter F (ideal I) is proper if and only if F 6= D (I 6= D). A proper filter F (ideal I) is called primary if and only if x ∈ F or ¬x ∈ F (x ∈ I or yx ∈ I), for all x ∈ D.
The set of primary filters is denoted by Fpr(D); the set of all primary ideals is denoted by Ipr(D).
Remarks on Prime Ideal and Representation Theorems 89 Theorem 3 (Prime ideal theorem for dBas). Let D be a dBa, F a filter in D and I an ideal in D such that F ∩ I = ∅. There exists a primary filter G and a primary ideal J of D such that F ⊆ G, I ⊆ J and G ∩ J = ∅. 4
The dBa is obtained by abstraction of certain properties of the protoconcept
algebra and the pure dBa is obtained from the semiconcept algebra. Now two
fundamental questions raised are as follows:
Q1: Is every dBa (pure dBa) D isomorphic to the protoconcept (semiconcept)
algebra of some context?
Q2: Can every dBa (pure dBa) D be embedded into the protoconcept
(semiconcept) algebra of some context?
The answer of Q2 is yes. Some notations and definitions [
Notation 4 – Fp(D) := {F ⊆ D|F is a filter of D and F ∩ Du is a prime filter in Du}. – Ip(D) := {I ⊆ D|I is an ideal of D and I ∩ Dt is a prime ideal in Dt}. – For any x ∈ D, Fx := {F ∈ Fp(D) | x ∈ F } and Ix := {I ∈ Ip(D) | x ∈ I}. Definition 6. Let D and M be two dBas. A map h : M → D is called a homomorphism if h preserves the operations in the algebras. h is called quasi-injective, when x v y if and only if h(x) v h(y), for all x, y ∈ M . A quasi-injective and surjective homomorphism is called a quasi-isomorphism and a bijective homomorphism is called an isomorphism.
In [
Theorem 4. [
Balbiani subsequently showed the following for a pure dBa.
Theorem 5. [
For addressing Q1, we need some definitions.
Definition 7. [
Prosenjit Howlader and Mohua Banerjee
In [
Regular dBas In the following, let K := (G, M, R) be a context. Let us first note that the dBa P(K) formed by the protoconcepts of K is regular. Topologies are now introduced into the picture. Recall that for a topological space (X, τ ), a subset A of X is said to be clopen if it is both closed and open in (X, τ ). Definition 8. Let τ be a topology on G and ρ a topology on M . Then KDB := ((G, τ ), (M, ρ), R) is called a context on topological spaces.
A clopen protoconcept (A, B) of KDB is a protoconcept of K such that A and
B are clopen in the topological spaces (G, τ ), (M, ρ) respectively.
Notation 5 The set of all clopen protoconcepts of KDB is denoted by Pco(KDB).
Definition 9. [
In [
Proposition 5. For a DB-topological context KDB, the set Pco(KDB) of all clopen protoconcepts of KDB forms a subalgebra of the regular dBa P(K).
For a regular dBa D and the context K(D) := (Fp(D), Ip(D), Δ) mentioned earlier, define a topology τ on Fp(D) with a subbasis for the closed sets given by {Fx : x ∈ D}, and a topology ρ on Ip(D) with a subbasis for the closed sets given by {Ix : x ∈ D}. So one obtains the context on topological spaces KDB(D) := ((Fp(D), τ ), (Ip(D), ρ), Δ).
Proposition 6. KDB(D) := ((Fp(D), τ ), (Ip(D), ρ), Δ) is a DB-topological context. Theorem 6. Let D be a regular dBa. The map
i : D → Pco(KDB(D)) such that i(a) := (Fa, Ia) for any a ∈ D, is an isomorphism.
From Theorem 4 it follows that the map i is a quasi-injective homomorphism. In particular when D is regular, i becomes an embedding. Theorem 6 claims that i is moreover surjective onto Pco(KDB(D)). In Example 1 below, we show that this need not be the case.
A counterexample to Theorem 6: To establish that the map i defined in Theorem 6 is surjective, it is shown that the extent of any clopen protoconcept is of the form Fa for some a ∈ D. The intent would also be of the form Ib for some b ∈ D. An observation is that any pair (Fa, Ib) is a protoconcept (Fa00 = Ib0 ), if and only if Fata = Fbtb (equivalently, Iaua = Ibub). Now if we choose a 6= b such that Fata = Fbtb then (Fa, Ib) is a clopen protoconcept of KDB(D), but there is no guarantee that there exists a c ∈ D such that i(c) = (Fa, Ib). This is what we verify in Example 1 below. Before doing so, we observe that primary filters (ideals) of a dBa D introduced by Kwuida are exactly the extensions of prime filters (ideals) of the Boolean algebra Dt(Du): Proposition 7. For a double Boolean algebra D, 1. Fpr(D)=Fp(D). 2. Ipr(D)=Ip(D).
Proof. The proof of 2 is dual to the proof of 1. We prove 1. Let F ∈ Fp(D). F ∩ Du is then a prime filter in Du. Let x ∈ D and x ∈/ F . Then x u x ∈/ F (otherwise x ∈ F ) and hence x u x ∈/ F ∩ Du. As F ∩ Du is a prime filter in Du, using axiom (4a), ¬x = ¬(x u x) ∈ F ∩ Du, giving ¬x ∈ F . Hence F ∈ Fpr(D). For the converse, let us assume that F ∈ Fpr(D). Let x ∈ Du(⊆ D). Then x ∈ F or ¬x ∈ F , as F is a primary filter in D. Therefore we have x ∈ F ∩ Du or ¬x ∈ F ∩ Du, and hence F ∩ Du is a prime filter in Du. So F ∈ Fp(D). Corollary 2. For a double Boolean algebra D, there is one-one and onto correspondence between the set of primary filters (ideals) of D and the set of prime filters (ideals) of Du(Dt).
Proof. Let F be a primary filter of D. Then by Proposition 7, F ∩ Du is a prime filter of Du. If F0 is a prime filter in Du, it can be shown that F = {y : x v y for some x ∈ F0} is a filter in D such that F ∩ Du = F0. So by Proposition 7, F is a primary filter in D. The case for ideals is done dually.
Lemma 1. [
Prosenjit Howlader and Mohua Banerjee
Example 1. For a regular dBa D, the map i defined in Theorem 6 may not
be surjective. This is established by the following example of a regular dBa
D [
The special case for Boolean algebras: We know that the class of Boolean algebras is a subclass of that of regular dBas. For this subclass however, the isomorphism result (Theorem 6) holds, as we note in Theorem 7 below.
Note that in the case of a Boolean algebra B, the topological spaces (Fp(B), τ ) and (Ip(B), ρ) are homeomorphic Stone spaces. Moreover, we have Lemma 2. For all a ∈ B, (Fa, Ia) is a clopen concept of the DB-topological context KDB(B) := ((Fp(B), τ ), (Ip(B), ρ), Δ).
Proof. Since B is a Boolean algebra, for all a ∈ B we have that Fa is clopen in (Fp(B), τ ) and Ia is clopen in (Ip(B), ρ). Now from Lemma 1 it follows that Fa0 = Iaut = Ia, as aut = a. Similarly, we can show that Ia0 = Fa. So (Fa, Ia) is a clopen concept of the DB-topological context KDB(B).
Theorem 7. Let B := (B, t, u,c , >, ⊥) be a Boolean algebra. Then B is isomorphic to Pco(KDB(B)).
Proof. One shows that the map i : B → Pco(KDB(B)) defined by i(a) := (Fa, Ia) for any a ∈ B, is a Boolean algebra isomorphism.
Let (X, Y ) ∈ Pco(KDB(B)). Then X is clopen in (Fp(B), τ ) and Y is clopen in (Ip(B), ρ). Since B is a Boolean algebra, every clopen set in (Fp(B), τ ) is of the form Fa for some a ∈ B and every clopen set in (Ip(B), ρ) is of the form Ib for some b ∈ B. So X = Fa0 for some a0 ∈ B and Y = Ib0 for some b0 ∈ B. Since (X, Y ) is a protoconcept, Fa000 = Ib00 and so Fa0 = Fb0 . Now, if possible, let us suppose that a0 6= b0. This would imply that either a0 6≤ b0 or b0 6≤ a0. Let a0 6≤ b0. By the prime ideal theorem of Boolean algebras, there exists a prime filter F such that a0 ∈ F and b0 ∈/ F – which is not possible, as Fa0 = Fb0 . In case b0 6≤ a0, one can similarly show that Fa0 6= Fb0 . So a0 = b0. Therefore by Lemma 2, it follows that Pco(KDB(B)) is a collection of clopen concepts of KDB(B) and since Pco(KDB(B)) is closed under t, u, (Pco(KDB(B)), t, u) forms a lattice. Now for all clopen protoconcepts (Fa, Ib) ∈ Pco(KDB(B)), ¬(Fa, Ia) = (Fp(B) \ Fa, (Fp(B) \ Fa)0) = (Fac , Iac ) = ((Ip(B) \
Remarks on Prime Ideal and Representation Theorems 93 Ia)0, Ip(B) \ Ia) =y(Fa, Ia) and since > := (Fp(B), ∅), ⊥ := (∅, Ip(B)) belongs to Pco(KDB(B)) then Pco(KDB(B)) = (Pco(KDB(B)), t, u, ¬, >, ⊥) forms a bounded complemented lattice. Considering the structures as dBas, Theorem 4 gives that the map i is a dBa homomorphism. Injectivity and surjectivity of the map i follow from the above proof also. Hence i becomes a Boolean algebra isomorphism. 5
In this work, we show that the new class of algebras defined in [
From Theorem 4 and the work of Breckner and S˘ac˘area it follows that every dBa D is quasi-isomorphic to some subalgebra of Pco(KDB(D)). Moreover, a regular dBa D is isomorphic to some subalgebra of Pco(KDB(D)). Characterization of this subalgebra remains an open question.