Axiomatic characterizations of adjoint generalized (dual) concept systems

Abstract

There are mainly two classes of approaches in the studies of Formal Concept Analysis (FCA), i.e. the constructive and axiomatic approaches. In axiomatic approach, operators are interpreted by using operations in mathematical systems instead of operations in a formal context. Seeking for minimal axioms to characterize the concept generation operators is an important issue in the research of the axiomatic approach. In this paper, axiomatic characterizations of set-theoretic operators are investigated. We construct an adjoint generalized (dual) concept systems in which the pair of classical concept generation operators are represented by one set-theoretic operator, and the other operator can be obtained from the former. Compared with the previous methods, the proposed generalized (dual) concept systems have fewer axioms and is easy to verify. Some properties of adjoint generalized (dual) concept systems are examined.

Keywords

Concept lattice galois connection generalized concept system set-theoretic operator

1 Introduction

The theory of formal concept analysis (FCA), originally proposed by Wille [4, 43] in 1982, is a model for the study of formal concepts and conceptual hierarchies. In the last two decades, it has been studied from various perspectives, such as its mathematical foundations [1 , 41], the generalizations of formal concepts [17 , 53], relationship with other theories [2 , 52], knowledge reduction and rule acquisition [12 , 47]. Currently, FCA has been successfully applied to information retrieval, knowledge discovery, data mining, machine learning, software engineering and other disciplines [3 , 26].

FCA is formulated on the basis of a formal context represented by a binary relation between a pair of sets. The formal concept is constructed from a formal context by using a pair of set-theoretic operators, and all the formal concepts combined with a partial order form a concept lattice (CL). In the above process, formal contexts and binary relations are primitive notions, which is referred to the constructive approach. From this perspective, the pair of set-theoretic operators that generate all concepts are defined on a formal context. In the constructive approach, the physical meaning of set-theoretic operators is associated with the binary relations R. Most of the research on FCA is carried out along this line.

In contrast, the axiomatic approach focuses on the algebraic properties of set-theoretic operators. The axiomatic approach regards the pair of set-theoretic operators as primitive notions, in which a set of axioms is used to characterize the pair of set-theoretic operators that are the same as the ones produced by using the constructive approach. In axiomatic approach, operators are interpreted by using operations in mathematical systems instead of operations in a specific formal context.

The axiomatic approach of FCA was proposed from the viewpoint of algebra, and the idea was inspired by rough set theory (RS) [28]. Many authors explored and developed the axiomatic approach in the study of RS theory [40 , 58]. In recent years, the axiomatic approach of fuzzy RS has been a research hotspot [18 , 44– 46]. Zhang et al. [54] first proposed the axiomatic approach in the study of FCA, in which set-theoretic operators are primitive notions. In their approach, a set of axioms is used to characterize the pair of set-theoretic operators and the formal context can be obtained from the pair of set-theoretic operators.

Recently, there has been an increasing interest in the axiomatic approach of CL, and several axiomatic methods related to FCA have been proposed [5 , 30]. Among which, Ma and Zhang [21] presented axiomatic characterizations of dual concept lattices. An important contribution of the authors is that they characterized a pair of dual concept lattices by using different sets of axioms. Rodrĺłguez-Lorenzo et al. [31] proposed a complete axiomatic system for conditional attribute implications in triadic concept analysis. In another interesting work, Li et al. applied the axiomatic approach of concept systems to concept learning and cognitive computing on the basis of isotone Galois connection [7 , 57].

Along the line of Ma and Zhang’s study on the axiomatic approach of CL [21], this paper focuses on axiomatic characterizations of generalized (dual) concept systems. In the paper, we propose an adjoint generalized (dual) concept system with two axioms, that is, we use fewer axioms to construct a generalized (dual) concept system. The rest of this paper is organized as follows. We review some basic notions of formal concepts and concept lattices in Section 2. In Section 3, we construct a kind of adjoint generalized concept system and discuss its properties. Section 4 proposes an adjoint generalized dual concept system and discuss its properties. Section 5 concludes the paper and outlines the future work.

2 Preliminaries

In this section we briefly recall some relevant notions needed for our purposes (please refer to [4, 21] for further details).

A formal context is a triplet $K = (U, A, I)$ , where U is a non-empty finite set of objects, A is a non-empty finite set of attributes and I is a relation between U and A. Where, (x, a) ∈ I means that object x has attribute a or the attribute a is possessed by object x. For any X ⊆ U, B ⊆ A, the pair of set-theoretic operators ^* and ^★ are defined by $X^{*} = {a | a \in A, \forall x \in X, (x, a) \in R},$ (1) $B^{★} = {x | x \in U, \forall a \in B, (x, a) \in R} .$ (2)

Let (U, A, I) be a formal context, the operators ^∗ and ^★ satisfy the followings properties (see [4]): for all X₁, X₂, X ⊆ U and B₁, B₂, B ⊆ A, $\begin{matrix} (i) & X_{1} \subseteq X_{2} \Rightarrow X_{2}^{*} \subseteq X_{1}^{*}, \\ B_{1} \subseteq B_{2} \Rightarrow B_{2}^{★} \subseteq B_{1}^{★}; \\ (ii) & X \subseteq X^{* ★}, B \subseteq B^{★ *}; \\ (iii) & X^{*} = X^{* ★ *}, B^{★} = B^{★ * ★}; \\ (iv) & (X_{1} \cup X_{2})^{*} = X_{1}^{*} \cap X_{2}^{*}, \\ (B_{1} \cup B_{2})^{★} = B_{1}^{★} \cap B_{2}^{★}, \\ (v) & X \subseteq B^{★} \Leftrightarrow B \subseteq X^{*} . \end{matrix}$

A pair (X, B) of two sets X ⊆ U and B ⊆ A is called a formal concept if X = B^★ and B = X^∗. Where, X and B are called the extent and the intent of the concept. The set of all concepts of (U, A, I) is denoted by $L (U, A, I)$ , that is, $L (U, A, I) = {(X, B) | X^{*} = B, B^{★} = X} .$ Under partial order ≤ defined by $(X_{1}, B_{1}) \leq (X_{2}, B_{2}) iff X_{1} \subseteq X_{2} (iff B_{1} \supseteq B_{2})$ for $(X_{1}, B_{1}), (X_{2}, B_{2}) \in L (U, A, I)$ , $L (U, A, I)$ forms a CL with meet and join given by: $\begin{matrix} (X_{1}, B_{1}) \lor (X_{2}, B_{2}) & = & ((X_{1} \cup X_{2})^{* ★}, B_{1} \cap B_{2}) \\ (X_{1}, B_{1}) \land (X_{2}, B_{2}) & = & (X_{1} \cap X_{2}, (B_{1} \cup B_{2})^{★ *}) . \end{matrix}$

For any X ⊆ U and B ⊆ A, the other pair of set-theoretic operators ^△ and ^▽ are defined as $X^{△} = {a \in A | \exists x \in X^{\sim}, (x, a) \notin I},$ (3) $B^{▽} = {x \in U | \exists a \in B^{\sim}, (x, a) \notin I},$ (4) where, ^∼ denotes the complement of a set.

Let (U, A, I) be a formal context, the operators ^△ and ^▽ satisfy the followings properties (see [21, 51]): for all X₁, X₂, X ⊆ U, B₁, B₂, B ⊆ A, $\begin{matrix} (i) & X_{1} \subseteq X_{2} \Rightarrow X_{2}^{△} \subseteq X_{1}^{△}, \\ B_{1} \subseteq B_{2} \Rightarrow B_{2}^{▽} \subseteq B_{1}^{▽}; \\ (ii) & X^{△ ▽} \subseteq X, B^{▽ △} \subseteq B; \\ (iii) & X^{△} = X^{△ ▽ △}, B^{▽} = B^{▽ △ ▽}; \\ (iv) & (X_{1} \cap X_{2})^{△} = X_{1}^{△} \cup X_{2}^{△}, \\ (B_{1} \cap B_{2})^{▽} = B_{1}^{▽} \cup B_{2}^{▽}, \\ (v) & B^{▽} \subseteq X \Leftrightarrow X^{△} \subseteq B . \end{matrix}$

A pair (X, B) of two sets X ⊆ U and B ⊆ A is called a dual formal concept if X = B^▽ and B = X^△. X and B act as the extent and the intent of the dual concept, respectively. We denote the set of all dual concepts of (U, A, I) by $L_{d} (U, A, I)$ . The partial order ≤ is given by $(X_{1}, B_{1}) \leq (X_{2}, B_{2}) iff X_{1} \subseteq X_{2} (iff B_{1} \supseteq B_{2})$ for $(X_{1}, B_{1}), (X_{2}, B_{2}) \in L_{d} (U, A, I)$ .

$L_{d} (U, A, I)$ forms a CL with meet and join defined by: $\begin{matrix} (X_{1}, B_{1}) \lor (X_{2}, B_{2}) & = & (X_{1} \cup X_{2}, (B_{1} \cap B_{2})^{▽ △}) \\ (X_{1}, B_{1}) \land (X_{2}, B_{2}) & = & ((X_{1} \cap X_{2})^{△ ▽}, B_{1} \cup B_{2}) . \end{matrix}$

3 Axiomatic characterizations of adjoint generalized concept systems

In this section, we first propose an adjoint generalized concept system (AGCS), then discuss its axiomatic characterizations and properties. Where, the term “adjoint" means that the pair of operators generating generalized concept system is adjoint.

Definition 1. Let $L : P (U) \to P (A)$ and $H : P (A) \to P (U)$ be a pair of set-theoretic operators between power sets $P (U)$ and $P (A)$ . The sextuple $(P (U), P (A), \cup, \cap, L, H)$ is called an AGCS, if the operators L and H satisfy the following axioms: for all $X, Y \in P (U)$ , $B \in P (A)$ ,

(AL) L (X ∪ Y) = L (X) ∩ L (Y),

(AH) $H (B) = ⋃ {X \in P (U) | L (X) \supseteq B} .$

From the above definition, we know that $(P (U), P (A)$ , ∪, ∩) is a set algebra and adjoint generalized concept system $(P (U), P (A), \cup, \cap, L, H)$ is an algebra system.

The pair of set-theoretic operators in an AGCS satisfy the following fundamental properties.

Proposition 1. Let $(P (U), P (A), \cup, \cap, L, H)$ be an AGCS. Then the following conclusions hold for all $X_{1}, X_{2} \in P (U)$ , $B_{1}, B_{2} \in P (A)$ ,

(1) X₁ ⊆ X₂ ⇒ L (X₂) ⊆ L (X₁);

(2) B₁ ⊆ B₂ ⇒ H (B₂) ⊆ H (B₁);

(3) L (X₁) ∪ L (X₂) ⊆ L (X₁ ∩ X₂);

(4) H (B₁) ∪ H (B₂) ⊆ H (B₁ ∩ B₂).

Proof. It can be easily derived from axioms (AL) and (AH). □

Now we review some well known facts between Galois connection and complete lattice.

Definition 2. [4] Let φ : P → Q and φ : Q → P be mappings between ordered sets (P, ≤) and (Q, ≤). A pair (φ, φ) of mappings is called a Galois connection between the ordered sets if

(i) p₁ ≤ p₂ ⇒ φ (p₁) ≥ φ (p₂),

(ii) q₁ ≤ q₂ ⇒ φ (q₁) ≥ φ (q₂),

(iii) p ≤ φφ (p) and q ≤ φφ (q).

The two mapings then are called dually adjoint to each other.

Note that above conditions (i), (ii) and (iii) are equivalent to the following one: $p \leq φ (q) \Leftrightarrow φ (p) \geq q .$ (5)

Theorem 1. The pair (L, H) of set-theoretic operators defined in Definition 1 forms a Galois connection between $P (U)$ and $P (A)$ .

Proof. Assume that $X_{1}, X_{2} \in P (U)$ , and X₁ ⊆ X₂. According to (AL), we have $L (X_{2}) = L (X_{1} \cup X_{2}) = L (X_{1}) \cap L (X_{2}) \subseteq L (X_{1}),$ (6) which implies Definition 2 (i). Similarly, we can prove Definition 2 (ii).

For any $B \in P (A)$ , we have $\begin{matrix} L (H (B)) & = & L (⋃ {X \in P (U) | L (X) \supseteq B}) \\ = & ⋂ {L (X) | L (X) \supseteq B} \\ \supseteq & B . \end{matrix}$ (7)

By the similar proof we have H (L (X)) ⊇ X.

From above assertions, we conclude that Definition 2 (iii) holds. Hence, (L, H) is a Galois connection between $P (U)$ and $P (A)$ . □

In the following, for the sake of simplicity, we denote H (L (X)) and L (H (B)) as H ∘ L (X) and L ∘ H (B) respectively.

Proposition 2. Let $(P (U), P (A), \cup, \cap, L, H)$ be an AGCS, $X \in P (U)$ and $B \in P (A)$ . Then L ∘ H ∘ L (X) = L (X), H ∘ L ∘ H (B) = H (B).

Proof. By Equation (7), we have L ∘ H (B) ⊇ B. It follows from Proposition 1 (2) that $H \circ (L \circ H (B)) \subseteq H (B) .$ On the other hand, from Equation (8) it is easy to show that $H \circ L (H (B)) \supseteq H (B) .$ Therefore, H ∘ L ∘ H (B) = H (B). By the similar proof we obtain L ∘ H ∘ L (X) = L (X). □

Proposition 3. Let φ : P → Q, φ₁ : Q → P and φ₂ : Q → P be mappings between ordered sets (P, ≤) and (Q, ≤). If pairs (φ, φ₁) and (φ, φ₂) are Galois connections between the ordered sets, then φ₁ = φ₂.

Proof. For any p ∈ P, q ∈ Q, by Equation (5) we have $p \leq φ_{1} (q) \Leftrightarrow φ (p) \geq q, φ (p) \geq q \Leftrightarrow p \leq φ_{2} (q) .$ Hence $p \leq φ_{1} (q) \Leftrightarrow p \leq φ_{2} (q) .$ (8) Suppose φ₁ ≠ φ₂. Then there exists q₁ ∈ Q such that φ₁ (q₁) > φ₂ (q₁) or φ₁ (q₁) < φ₂ (q₁). We denote φ₁ (q₁) = p₁. If φ₁ (q₁) > φ₂ (q₁), then we have φ₁ (q₁) = p₁ > φ₂ (q₁), which contradicts Equation (9). By the similar proof, we obtain that φ₁ (q₁) < φ₂ (q₁) contradicts Equation (9). Therefore, φ₁ = φ₂. □

By Proposition 3, it can be easily seen that a mapping’s dually adjoint is unique. That is, if a mapping is given, then its dually adjoint is also determined.

Recall that Ma and Zhang’s definition of generalized concept system (GCS) is defined as follows [21].

Definition 3. [21] Let $L : P (U) \to P (A)$ and $H : P (A) \to P (U)$ be a pair of set-theoretic operators between power sets $P (U)$ and $P (A)$ . The sextuple $(P (U), P (A), \cup, \cap, L, H)$ is called a GCS, if the operators L and H satisfy the following axioms: for all $X, Y \in P (U)$ , $B, C \in P (A)$ ,

(L) L (X ∪ Y) = L (X) ∩ L (Y),

(H) H (B ∪ C) = H (B) ∩ H (C),

(LH) X ⊆ H (L (X)) and B ⊆ L (H (B)).

Note that operators L and H in Definition 3 are defined independently, however, operator H in Definition 1 are defined by operator L. On the other hand, axiom (LH) in Definition 3 is difficult to verify. Comparing with a GCS, an AGCS has fewer axioms and is easy to verify.

Theorem 2. Let $L : P (U) \to P (A)$ and $H : P (A) \to P (U)$ be a pair of set-theoretic operators between power sets $P (U)$ and $P (A)$ . Then the sextuple $(P (U), P (A), \cup, \cap, L, H)$ is an AGCS iff $(P (U), P (A), \cup, \cap, L, H)$ is a GCS.

Proof. (⇒) It is evident that (L) holds. Here, we are to prove (H). For any $B, C \in P (A)$ , we have $\begin{matrix} H (B \cup C) & = & ⋃ {X \in P (U) | L (X) \supseteq (B \cup C)} \\ = & ⋃ {X \in P (U) | (L (X) \supseteq B) \land (L (X) \supseteq C)} \\ = & (⋃ {X \in P (U) | (L (X) \supseteq B)}) ⋂ \\ (⋃ {X \in P (U) | (L (X) \supseteq C)}) \\ = & H (B) \cap H (C), \end{matrix}$ from which (H) follows. (LH) follows immediately from Equations (7) and (8). Hence, $(P (U), P (A)$ , ∪, ∩ , L, H) is a GCS.

(⇐) By Definition 2 and using (L),(H) and (LH), we can easily conclude that the pair (L, H) of operators forms a Galois connection between $P (U)$ and $P (A)$ . We define the mapping $H_{1} : P (A) \to P (U)$ by $H_{1} (B) = ⋃ {X \in P (U) | L (X) \supseteq B}, B \in P (A) .$ From Theorem 2, it is easy to check that the pair (L, H₁) of operators also forms a Galois connection. By Proposition 3, we conclude that H = H₁. Combining the fact and (L), we immediately conclude that $(P (U), P (A), \cup, \cap, L, H)$ is an AGCS. □

Remark. The above theorem shows that an AGCS is equivalent to a GCS. The proposed AGCS deleted two of three axiomatic characterizations but added another condition. That is to say, the new axiomatic system is constructed by two axiomatic characterizations. An AGCS can be regarded as a specific explanation and implementation of a GCS in the viewpoint of the adjoint operators.

Theorem 3. Let $L : P (U) \to P (A)$ and $H : P (A) \to P (U)$ be two set-theoretic operators. Then there exists a 0-1 binary relation I ⊆ U × A such that (U, A, I) is a formal context, and the operators defined by Equations (1) and (2) satisfy L (X) = X^∗ and H (B) = B^★ ( $\forall X \in P (U), B \in P (A)$ ) iff the operators L and H satisfy axioms (AL) and (AH).

Proof. (⇒) Easy, it is omitted.

(⇐) Putting I = {(x, a) | a ∈ L ({x})} (x ∈ U, a ∈ A), then we obtain a formal context (U, A, I). For any $X \in P (U)$ , by Equation (1) we have $\begin{matrix} X^{*} & = & ⋂_{x \in X} x^{*} \\ = & ⋂_{x \in X} {a \in A | (x, a) \in I} \\ = & ⋂_{x \in X} {a \in A | a \in L ({x})} \\ = & ⋂_{x \in X} L ({x}) \\ = & L (X) . \end{matrix}$

For any $B \in P (A)$ , using Equation (2) and the proof of Theorem 1 we have $\begin{matrix} B^{★} & = & ⋂_{b \in B} b^{★} \\ = & ⋂_{b \in B} {x \in U | (x, b) \in I} \\ = & ⋂_{b \in B} {x \in U | b \in L ({x})} \\ = & ⋂_{b \in B} {⋃ {X \in P (U) | b \in L (X)}} \\ = & ⋂_{b \in B} {⋃ {X \in P (U) | L (X) \supseteq {b}}} \\ = & ⋂_{b \in B} H ({b}) \\ = & H (B), \end{matrix}$ we have completed the proof of the theorem. □

By Theorem 3, we can obtain a formal context from an AGCS, and vice versa.

Example 1. For U = {x₁, x₂, x₃, x₄, x₅}, A = {a, b, c, d}, X ⊆ U and B ⊆ A, define the operators $L : P (U) \to P (A)$ and $H : P (A) \to P (U)$ as follows: $\begin{matrix} L (\emptyset) = A, L ({x_{1}}) = {a, c, d}, \\ L ({x_{2}}) = {b, c}, L ({x_{3}}) = {a, d}, \\ L ({x_{4}}) = {b, c}, L ({x_{5}}) = {a, b}, \\ L (X) = ⋂_{x \in X} L ({x}), L (U) = \emptyset, \\ H (B) = ⋃ {X \in P (U) | L (X) \supseteq B} . \end{matrix}$

Table 1

The formal context (U, A, I)

I	a	b	c	d
x ₁	1	0	1	1
x ₂	0	1	1	0
x ₃	1	0	0	1
x ₄	0	1	1	0
x ₅	1	1	0	0

It can be checked that $(P (U), P (A), \cup, \cap, L, H)$ is an AGCS. For x ∈ U and a ∈ A, we define I = {(x, a) |x ∈ L ({a})}. Then (U, A, I) is a formal context and is showed in Table 1. Figure 1 depicts the Hasse diagram of lattice $B (P (U), P (A), \cup, \cap, L, H)$ .

Fig.1

$B (P (U), P (A), \cup, \cap, L, H)$ .

From Example 1, we can obtain a concept lattice from an AGCS. Therefore, the knowledge hidden in the an AGCS can be mined and presented.

4 Axiomatic characterizations of adjoint generalized dual concept systems

In this section, we first propose an adjoint generalized dual concept system (AGDCS), then present its axiomatic characterizations and properties.

Definition 4. Let $L_{d} : P (U) \to P (A)$ and $H_{d} : P (A) \to P (U)$ be a pair of set-theoretic operators between power sets $P (U)$ and $P (A)$ . The sextuple $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ is called an AGDCS, if the operators L_d and H_d satisfy the following axioms: for all $X, Y \in P (U)$ , $B \in P (A)$ ,

(AL_d) L_d (X ∩ Y) = L_d (X) ∪ L_d (Y),

(AH_d) $H_{d} (B) = ⋂ {X \in P (U) | L_{d} (X) \subseteq B}$ .

From Definition 4, we know that $(P (U), P (A), \cup, \cap)$ is a set algebra and adjoint generalized dual concept system $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ is an algebra system.

The pair of set-theoretic operators in an AGDCS satisfy the following fundamental properties.

Proposition 4. Let $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ be an AGDCS. Then the following conclusions hold for all $X_{1}, X_{2} \in P (U)$ , $B_{1}, B_{2} \in P (A)$ ,

(1) X₁ ⊆ X₂ ⇒ L_d (X₂) ⊆ L_d (X₁);

(2) B₁ ⊆ B₂ ⇒ H_d (B₂) ⊆ H_d (B₁);

(3) L_d (X₁) ∩ L_d (X₂) ⊆ L_d (X₁ ∪ X₂);

(4) H_d (B₁) ∩ H_d (B₂) ⊆ H_d (B₁ ∩ B₂).

Proof. It can be easily derived from axioms (AL_d) and (AH_d).

Definition 5. Let φ : P → Q and φ : Q → P be mappings between ordered sets (P, ≤) and (Q, ≤). A pair (φ, φ) of mappings is called a dual Galois connection between the ordered sets if

(i) p₁ ≤ p₂ ⇒ φ (p₁) ≥ φ (p₂),

(ii) q₁ ≤ q₂ ⇒ φ (q₁) ≥ φ (q₂),

(iii) p ≥ φφ (p) and q ≥ φφ (q).

Proposition 5. Let φ : P → Q and φ : Q → P be mappings between ordered sets (P, ≤) and (Q, ≤). A pair (φ, φ) of mappings is a dual Galois connection iff $p \geq φ (q) \Leftrightarrow φ (p) \leq q .$ (9)

Proof. (⇒) Suppose p ≥ φ (q). From Definition 5 (i), we have φ (p) ≤ φφ (q), and by Definition 5 (iii) we have φ (p) ≤ q. Thus, p ≥ φ (q) ⇒ φ (p) ≤ q. Conversely, from φ (p) ≤ q we can obtain p ≥ φ (q) symmetrically.

(⇐) Since φ (p) ≤ φ (p) and φ (q) ≤ φ (q), by Equation (10) they follow that p ≥ φφ (p) and q ≥ φφ (q). Thus, we have proved Definition 5 (iii). Suppose p₁ ≤ p₂ and q₁ ≤ q₂. By employing Definition 5 (iii), we have p₂ ≥ φφ (p₁), by Equation (10) it follows that φ (p₁) ≥ φ (p₂). By the similar proof, we obtain φ (q₁) ≥ φ (q₂). □

Proposition 5 states that conditions (i), (ii) and (iii) in Definition 5 are equivalent to Equation (10).

Theorem 4. The pair (L_d, H_d) of set-theoretic operators defined in Definition 4 forms a dual Galois connection between $P (U)$ and $P (A)$ .

Proof. Assume that $X_{1}, X_{2} \in P (U)$ , and X₁ ⊆ X₂. According to Definition 4, we have $L_{d} (X_{1}) = L_{d} (X_{1} \cap X_{2}) = L_{d} (X_{1}) \cup L_{2} (X_{2}) \supseteq L_{d} (X_{2}),$ which implies Definition 5 (i). By the similar proof, we obtain Definition 5 (ii).

For any $B \in P (A)$ , we have $\begin{matrix} L_{d} (H_{d} (B)) & = & L_{d} (⋂ {X \in P (U) | L_{d} (X) \subseteq B}) \\ = & ⋃ {L_{d} (X) | L_{d} (X) \subseteq B} \\ \subseteq & B . \end{matrix}$ (10) On the other hand, for any $X \in P (U)$ , it follows that $H_{d} (L_{d} (X)) = ⋂ {Y \in P (U) | L_{d} (Y) \subseteq L_{d} (X)} \subseteq X .$ (11) From Equations (11) and (12), we conclude that Definition 5 (iii) holds. Therefore, (L_d, H_d) is a dual Galois connection between $P (U)$ and $P (A)$ . □

Proposition 6. Let $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ be an AGCS, $X \in P (U)$ and $B \in P (A)$ . Then L_d ∘ H_d ∘ L_d (X) = L_d (X), H_d ∘ L_d ∘ H_d (B) = H_d (B).

Proof. It is similar to the proof of Proposition 2. □

Proposition 7. Let φ_d : P → Q, φ_1d : Q → P and φ_2d : Q → P be mappings between ordered sets (P, ≤) and (Q, ≤). If pairs (φ_d, φ_1d) and (φ_d, φ_2d) are dual Galois connections between the ordered sets, then φ_1d = φ_2d.

Proof. It is similar to the proof of Proposition 3. □

By Proposition 7, it can be easily seen that a mapping’s dually adjoint is uniquely determined.

Recall that the definition of generalized dual concept system is defined as follows [21].

Definition 6. Let $L_{d} : P (U) \to P (A)$ and $H_{d} : P (A) \to P (U)$ be a pair of set-theoretic operators between power sets $P (U)$ and $P (A)$ . The sextuple $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ is called a GDCS, if the operators L_d and H_d satisfy the following axioms: for all $X, Y \in P (U)$ , $B, C \in P (A)$ ,

(L_d) L_d (X ∩ Y) = L_d (X) ∪ L_d (Y),

(H_d) H_d (B ∩ C) = H_d (B) ∪ H_d (C),

(L_dH_d) X ⊇ H_d (L_d (X)) and B ⊇ L_d (H_d (B)).

Theorem 5. Let $L : P (U) \to P (A)$ and $H : P (A) \to P (U)$ be a pair of set-theoretic operators between power sets $P (U)$ and $P (A)$ . Then the sextuple $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ is an AGDCS iff $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ is a GDCS.

Proof. (⇒) It is evident that (L_d) holds. Here, we are to prove (H_d). For any $B, C \in P (A)$ , we have $\begin{matrix} H_{d} (B \cap C) & = & ⋂ {X \in P (U) | L_{d} (X) \subseteq (B \cap C)} \\ = & ⋂ {X \in P (U) | (L_{d} (X) \subseteq B) \land (L_{d} (X) \subseteq C)} \\ = & (⋂ {X \in P (U) | (L_{d} (X) \subseteq B)}) ⋃ \\ (⋂ {X \in P (U) | (L_{d} (X) \subseteq C)}) \\ = & H_{d} (B) \cup H_{d} (C), \end{matrix}$ from which (H_d) follows. (L_dH_d) follows immediately from Equations (11) and (12). Therefore, $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ is a GDCS.

(⇐) By Definition 5 and using (L_d),(H_d) and (L_dH_d), we can easily conclude that the pair (L_d, H_d) of operators forms a dual Galois connection between $P (U)$ and $P (A)$ . Define the mapping $H_{1 d} : P (A) \to P (U)$ by $H_{1 d} (B) = ⋃ {X \in P (U) | L_{1 d} (X) \supseteq B}, B \in P (A) .$ From Theorem 4, it is easy to check that the pair of operators (L_d, H_1d) also forms a dual Galois connection. By Proposition 7, we conclude that H_d = H_1d. Using above assertion and (AL), we immediately conclude that $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ is an AGDCS. □

Remark. The above theorem shows that an AGDCS is equivalent to a GDCS. An AGDCS can be regarded as a specific explanation and implementation of a GDCS in the viewpoint of the adjoint operators.

Theorem 6. Let $L_{d} : P (U) \to P (A)$ and $H_{d} : P (A) \to P (U)$ be two set-theoretic operators. Then there exists a 0-1 binary relation I ⊆ U × A such that (U, A, I) is a formal context, and the operators defined by Equations (3) and (4) satisfy L_d (X) = X^△ and H_d (B) = B^▽ ( $\forall X \in P (U), B \in P (A)$ ) iff the operators L_d and H_d satisfy axioms (AL_d) and (AH_d).

Proof. (⇒) It follows immediately.

(⇐) Putting I = {(x, a) | a ∉ L_d ({x} ^∼)} (x ∈ U, a ∈ A). We are going to prove that $a \notin L_{d} ({x}^{\sim}) \Leftrightarrow x \notin H_{d} ({a}^{\sim}) .$ For any x ∈ U and a ∈ A, we obtain from Equations (3), (4) and the proof of Theorem 4 that $\begin{matrix} a \notin L_{d} ({x}^{\sim}) & \Leftrightarrow & a \in (L_{d} ({x}^{\sim}))^{\sim} \\ \Leftrightarrow & {a}^{\sim} \supseteq L_{d} ({x}^{\sim}) \\ \Rightarrow & H_{d} ({a}^{\sim}) \subseteq H_{d} L_{d} ({x}^{\sim}) \\ \Rightarrow & H_{d} ({a}^{\sim}) \subseteq {x}^{\sim} \\ \Leftrightarrow & \sim H_{d} ({a}^{\sim}) \supseteq {x} \\ \Leftrightarrow & x \notin H_{d} ({a}^{\sim}) . \end{matrix}$

Similarly, we can verify that $a \notin H_{d} ({x}^{\sim}) \Rightarrow x \notin L_{d} ({a}^{\sim}) .$ Thus, we have $a \notin L_{d} ({x}^{\sim}) \Leftrightarrow x \notin H_{d} ({a}^{\sim}),$ from which we conclude that $I = {(x, a) | a \notin L_{d} ({x}^{\sim})} = {(x, a) | x \notin H_{d} ({a}^{\sim})} .$

For any $B \in P (A)$ , using Equation (4) and the proof of Theorem 4 we have $\begin{matrix} B^{▽} & = & {x \in U | \exists a \in B^{\sim}, (x, a) \notin I} \\ = & {x \in U | \exists a \in B^{\sim}, x \in H_{d} ({a}^{\sim})} \\ = & ⋃_{a \in B^{\sim}} H_{d} ({a}^{\sim}) \\ = & ⋃_{a \in B^{\sim}} H_{d} (A - {a}) \\ = & H_{d} (⋂_{a \in B^{\sim}} (A - {a})) \\ = & H_{d} (B) . \end{matrix}$

The proof that X^△ = L_d (X) is similar. □

From Theorem 6, we can obtain a formal context from an AGDCS, and vice versa.

Example 2. Let U = {x₁, x₂, x₃, x₄, x₅} and A = {a, b, c, d}. The operators $L_{d} : P (U) \to P (A)$ and $H_{d} : P (A) \to P (U)$ are defined as follows: for all X_i ⊆ U, B ⊆ A, $\begin{matrix} L_{d} (U) = \emptyset, L_{d} (\emptyset) = A, \\ L_{d} ({x_{1}, x_{2}, x_{3}, x_{4}}) = {b}, \\ L_{d} ({x_{1}, x_{2}, x_{3}, x_{5}}) = {a, c, d}, \\ L_{d} ({x_{1}, x_{2}, x_{4}, x_{5}}) = {b, e}, \\ L_{d} ({x_{1}, x_{3}, x_{4}, x_{5}}) = {a, c, d}, \\ L_{d} ({x_{2}, x_{3}, x_{4}, x_{5}}) = {b}, \\ L_{d} (⋂_{i \in I} X_{i}) = ⋃_{i \in I} L_{d} (X_{i}), \\ H_{d} (B) = ⋂ {X \in P (U) | L_{d} (X) \subseteq B} . \end{matrix}$ It is easy to verify that $(P (U), P (A), \cup, \cap, L_{d}, H_{d})$ is an AGDCS. For x ∈ U and a ∈ A, we define I = {(x, a) | a ∉ L_d ({x} ^∼)}. Then (U, A, I) is a formal context (represented by Table 2, L_d (X) = X^△ and H_d (B) = B^▽.

Table 2

Formal context (U, A, I)

I	a	b	c	d	e
x ₁	1	0	1	1	1
x ₂	0	1	0	0	1
x ₃	1	0	1	1	0
x ₄	0	1	0	0	1
x ₅	1	0	1	1	1

Corollary 1. Let $L : P (U) \to P (A)$ and $H : P (A) \to P (U)$ be a pair of set-theoretic operators between power sets $P (U)$ and $P (A)$ . The sextuple $(P (U), P (A), \cup, \cap, L, H)$ is an AGCS if and only if for all $X, Y \in P (U)$ , $B \in P (A)$ :

(1) (L (X ∩ Y) ^∼) ^∼ = (L (X^∼)) ^∼ ∪ (L (Y^∼)) ^∼,

(2) $H (B) = ⋃ {X \in P (U) | L (X) \supseteq B}$ .

Proof. (⇒) By (AL), we have $\begin{matrix} (L (X \cap Y)^{\sim})^{\sim} & = & (L (X^{\sim} \cup Y^{\sim}))^{\sim} \\ = & (L (X^{\sim}) \cap L (Y^{\sim}))^{\sim} \\ = & (L (X^{\sim}))^{\sim} \cup (L (Y^{\sim}))^{\sim} . \end{matrix}$

(⇐) For any $X, Y \in P (U)$ , by the assumption we have $\begin{matrix} (L (X \cup Y))^{\sim} & = & (L (X^{\sim} \cap Y^{\sim})^{\sim})^{\sim} \\ = & (L (X^{\sim \sim}))^{\sim} \cup (L (Y^{\sim \sim}))^{\sim} \\ = & (L (X))^{\sim} \cup (L (Y))^{\sim} \\ = & (L (X) \cap L (Y))^{\sim}, \end{matrix}$ which implies that L (X ∪ Y) = L (X) ∩ L (Y). It follows from Definition 1 that $(P (U), P (A), \cup$ , ∩, L, H) is an AGCS. □

Corollary 2. Let $L : P (U) \to P (A)$ and $H : P (A) \to P (U)$ be a pair of set-theoretic operators between power sets $P (U)$ and $P (A)$ . The sextuple $(P (U), P (A), \cup, \cap,^{\sim} L^{\sim},^{\sim} H^{\sim})$ is an AGDCS if and only if for all $X, Y \in P (U)$ , $B \in P (A)$ :

(1) L (X ∪ Y) = L (X) ∩ L (Y),

(2) $^{\sim} H^{\sim} (B) = ⋂ {X \in P (U) | (L (X^{\sim}))^{\sim} \subseteq B}$ . Where, ^∼ L^∼ (X) = (L (X^∼)) ^∼, ^∼ H^∼ (B) = (H (B^∼)) ^∼.

Proof. (⇒) For any $X, Y \in P (U)$ , by (AL_d) we have $\begin{matrix} L (X^{\sim} \cup Y^{\sim}) & = & ((L (X \cap Y)^{\sim})^{\sim})^{\sim} \\ = & ((L (X^{\sim}))^{\sim} \cup (L (Y^{\sim}))^{\sim} \\ = & (L (X^{\sim}))^{\sim \sim} \cap (L (Y^{\sim}))^{\sim \sim} \\ = & L (X^{\sim}) \cap L (Y^{\sim}), \end{matrix}$ which implies that L (X ∪ Y) = L (X) ∩ L (Y).

(⇐) For any $X, Y \in P (U)$ , by the assumption we have $\begin{matrix} (L (X \cap Y)^{\sim})^{\sim} & = & (L (X^{\sim} \cup Y^{\sim}))^{\sim} \\ = & (L (X^{\sim}) \cap L (Y^{\sim}))^{\sim} \\ = & (L (X)^{\sim})^{\sim} \cup (L (Y)^{\sim})^{\sim} . \end{matrix}$ It follows from Definition 4 that $(P (U), P (A), \cup, \cap,^{\sim} L^{\sim},^{\sim} H^{\sim})$ is an AGDCS. □

Corollaries 1 and 2 show the relationship between an AGCS and an AGDCS.

5 Conclusion

There are mainly two approaches in the study of concept lattices, i.e., the constructive and axiomatic approaches. Many researchers investigated the constructive approach in the development of FCA. Comparing with the constructive approach, less effort has been made to the axiomatic approach in the study of FCA. Axiomatic characterizations of set-theoretic operators are important in the study of concept lattice. The axiomatic approach focuses on the algebraic properties of set-theoretic operators without being restricted to any explicitly formal contexts. In the paper, axiomatic characterizations of set-theoretic operators are investigated. In this approach, a set of properties is used to characterize the pair of set-theoretic operators that are the same as the ones produced by using the constructive approach. We construct an adjoint generalized (dual) concept systems by using a pair of adjoint operators, and the pair of concept generation operators can be represented by one set-theoretic operator. Compared with the previous methods, the proposed adjoint generalized (dual) concept systems have fewer axioms and is easy to verify. The research results may improve our understanding of CL’s algebraic properties. Note that the axiomatic approach of generalized (dual) concept systems discussed in this paper are based on antitone Galois connection. The axiomatic approach of generalized (dual) concept systems generated from isotone Galois connection is a problem worthy of further research. Knowledge reduction and rules acquisition in adjoint generalized (dual) concept systems should be further studied also.

Footnotes

Acknowledgement

This work was supported by the grants from the National Natural Science Foundation of China (Nos. 61673396, 61573321, 61572082), Shandong Provincial Natural Science Foundation (No. ZR2015FM022), the Fundamental Research Funds for the Central Universities under Grant (No. 16CX02008A, 18CX02133A) and National Social Science Foundation of China (No.14XXW004).

References

Butka

and Pócs

, Generalization of one-sided concept lattices, Computing and Informatics 32 (2013), 355–370.

Chen

J.k.

, Li

J.J.

, Lin

Y.J.

, Lin

G.P.

and Ma

Z.M.

, Relations of reduction between covering generalized rough sets and concept lattices, Information Sciences 304 (2015), 16–27.

Formica

, Semantic Web search based on rough sets and Fuzzy Formal Concept Analysis, Knowledge-Based Systems 26 (2012), 40–47.

Ganter

and Wille

, Formal Concept Analysis, Mathematic Foundations, Springer, Berlin, 1999.

Gong

F.M.

, Shao

M.W.

and Qiu

G.F.

, Concept granular computing systems and their approximation operators, International Journal of Machine Learning and Cybernetics 8(2) (2017), 627–640.

Hashem

, Ahmed

C.F.

, Samiullah

, et al., Assessing semantic annotation activities with formal concept analysis, Expert Systems with Applications 41 (2014), 2914–2938.

Huang

C.C.

, Li

J.H.

, Mei

C.L.

and Wu

W.Z.

, Three-way concept learning based on cognitive operators: An information fusion viewpoint, International Journal of Approximation Reasoning 83 (2017), 218–242.

Kang

X.P.

, Li

D.Y.

, Wang

S.G.

and Qu

K.S.

, Formal concept analysis based on fuzzy granularity base for different granulations, Fuzzy Sets and Systems 203 (2012), 33–48.

Kaytoue

, Kuznetsov

S.O.

, Napoli

and Duplessis

, Mining gene expression data with pattern structures in formal concept analysis, Information Sciences 181 (2011), 1989–2001.

10.

Kumar

C.A.

and Srinivas

, Concept lattice reduction using fuzzy K-means clustering, Expert Systems with Applications 37 (2010), 2696–2704.

11.

Kumar

C.A.

, Fuzzy clustering-based formal concept analysis for association rules mining, Applied Artificial Intelligence 26(3) (2012), 274–301.

12.

J.H.

, Mei

C.L.

, Kumar

C.A.

and Zhang

, On rule acquisition in decision formal contexts, International Journal of Machine Learning and Cybernetics 4(6) (2013), 721–731.

13.

J.H.

, Mei

C.L.

, Xu

W.H.

and Qian

Y.H.

, Concept learning via granular computing: A cognitive viewpoint, Information Sciences 298 (2015), 447–467.

14.

J.H.

, Ren

, Mei

C.L.

, Qian

Y.H.

and Yang

X.B.

, A comparative study of multigranulation rough sets and concept lattices via rule acquisition, Knowledge-Based Systems 91 (2016), 152–164.

15.

J.H.

, Kumar

C.A.

, Mei

C.L.

and Wang

X.Z.

, Comparison of reduction in formal decision contexts, International Journal of Approximate Reasoning 80 (2017), 100–122.

16.

K.W.

, Shao

M.W.

and Wu

W.Z.

, A data reduction method in formal fuzzy contexts, International Journal of Machine Learning and Cybernetics 8(4) (2017), 1145–1155.

17.

M.Z.

and Wang

G.Y.

, Approximate concept construction with three-way decisions and attribute reduction in incomplete contexts, Knowledge-Based Systems 91 (2016), 165–178.

18.

Liu

G.L.

, Axiomatic systems for rough sets and fuzzy rough sets, International Journal of Approximate Reasoning 48 (2008), 857–867.

19.

Liu

G.L.

, Using one axiom to characterize rough set and fuzzy rough set approximations, Information Sciences 223 (2013), 285–296.

20.

J.M.

, Zhang

W.X.

, Leung

and Song

X.X.

, Granular computing and dual Galois connection, Information Sciences 177(23) (2007), 5365–537.

21.

J.M.

and Zhang

W.X.

, Axiomatic characterizations of dual concept lattices, International Journal of Approximate Reasoning 54 (2013), 690–697.

22.

J.M.

, Cai

M.J.

and Zou

C.J.

, Concept acquisition approach of object-oriented concept lattices, International Journal of Machine Learning and Cybernetics 8(1) (2017), 3–20.

23.

Medina

and Ojeda-Aciego

, Multi-adjoint t-concept lattices, Information Sciences 180 (2010), 712–725.

24.

Medina

and Ojeda-Aciego

, Dual multi-adjoint concept lattices, Information Sciences 225 (2013), 47–54.

25.

J.S.

and Zhang

W.X.

, An axiomatic characterization of a fuzzy generalization of rough sets, Information Sciences 160 (2004), 235–249.

26.

Niu

J.J.

, Huang

C.C.

, Li

J.H.

and Fan

, Parallel computing techniques for concept-cognitive learning based on granular computing, International Journal of Machine Learning and Cybernetics 9(11) (2018), 1785–1805.

27.

Morsi

N.N.

and Yakout

M.M.

, Axiomatics for fuzzy rough sets, Fuzzy Sets and Systems 100 (1998), 327–342.

28.

Pawlak

, Rough sets, International Journal of Computer and Information Science 11 (1982), 341–356.

29.

J.J.

, Qian

and Wei

, The connections between three-way and classical concept lattices, Knowledge-Based Systems 91 (2016), 143–151.

30.

Qiu

G.F.

, Ma

J.M.

, Yang

H.Z.

and Zhang

W.X.

, A mathematical model for concept granular computing systems, Science China (Information Sciences) 53(7) (2010), 1397–1408.

31.

Rodriguez-Lorenzo

, Cordero

, Enciso

, Missaoui

and Mora

, An axiomatic system for conditional attribute implications in triadic concept analysis, International Journal of Intelligent Systems 32(8) (2017), 760–777.

32.

Shao

M.W.

, Liu

and Zhang

W.X.

, Set approximations in fuzzy formal concept analysis, Fuzzy Set and Systems 158 (2007), 2627–2640.

33.

Shao

M.W.

, Leung

, Wang

X.Z.

and Wu

W.Z.

, Granular Reducts of Formal Fuzzy Contexts, Knowledge-Based Systems 114(15) (2016), 156–166.

34.

Shao

M.W.

and Li

K.W.

, Attribute reduction in generalized onesided formal contexts, Information Sciences 378 (2017), 317–327.

35.

Shao

M.W.

, Guo

and Wang

C.Z.

, Connections between twouniverse rough sets and formal concepts, International Journal of Machine Learning and Cybernetics 9(11) (2018), 1869–1877.

36.

Shivhare

and Aswani Kumar

Ch.

, Three-way conceptual approach for cognitive memory functionalities, International Journal of Machine Learning and Cybernetics 8(1) (2017), 21–34.

37.

Singh

P.K.

and Kumar

C.A.

, Bipolar fuzzy graph representation of concept lattice, Information Sciences 288 (2014), 437–448.

38.

She

Y.H.

and Wang

G.J.

, An axiomatic approach of fuzzy rough sets based on residuated lattices, Computers & Mathematics with Applications 58(1) (2009), 189–201.

39.

Tan

A.H.

, li

J.J.

and Lin

G.P.

, Connections between covering-based rough sets and concept lattices, International Journal of Approximate Reasoning 56 (2015), 43–58.

40.

Thiele

, On axiomatic characterisation of crisp approximation operators, Information Sciences 129 (2000), 221–226.

41.

Wang

L.D.

and Liu

X.D.

, Concept analysis via rough set and AFS algebra, Information Sciences 178 (2008), 4125–4137.

42.

Wei

and Qi

J.J.

, Relation between concept lattice reduction and rough set reduction, Knowledge-Based Systems 23 (2010), 934–938.

43.

Wille

, Restructuring lattice theory: An approach based on hierarchies of concepts, in: I. Rival (Ed.), Ordered Sets, Reidel, Dordrecht-Boston, 1982, pp. 445–470.

44.

W.Z.

, Mi

J.S.

and Zhang

W.X.

, Generalized fuzzy rough sets, Information Sciences 151 (2003), 263–282.

45.

W.Z.

and Zhang

W.X.

, Constructive and axiomatic approaches of fuzzy approximation operators, Information Sciences 159 (2004), 233–254.

46.

W.Z.

, Li

T.J.

and Gu

S.M.

, Using one axiom to characterize fuzzy rough approximation operators determined by a fuzzy implication operator, Fundamenta Informaticae 142 (2015), 87–104.

47.

W.Z.

, Leung

and Mi

J.S.

, Granular computing and knowledge reduction in formal contexts, IEEE Transactions Knowledge and Data Engineering 21(10) (2009), 1461–1474.

48.

Yang

X.P.

and Li

T.J.

, The minimization of axiom sets characterizing generalized approximation operators, Information Sciences 176 (2006), 887–899.

49.

Yang

X.P.

, Minimization of axiom sets on fuzzy approximation operators, Information Sciences 177 (2007), 3840–3854.

50.

Yao

Y.Y.

, Two views of the theory of rough sets in finite universes, International Journal of Approximate Reasoning 15 (1996), 291–317.

51.

Yao

Y.Y.

, Constructive and algebraic methods of the theory of rough sets, Journal of Information Sciences 109 (1998), 21–47.

52.

Yao

Y.Y.

, A comparative study of formal concept analysis and rough set theory in data analysis, 4th International Conference on Rough Sets and Current Trends in Computing, LNCS, vol. 3066, Springer, Beilin, 2004, pp. 59–68.

53.

Yao

Y.Y.

, Interval sets and three-way concept analysis in incomplete contexts, International Journal of Machine Learning and Cybernetics 8(1) (2017), 3–20.

54.

Zhang

W.X.

, Yang

H.Z.

, Ma

J.M.

and Qiu

G.F.

, Concept granular computing based on lattice theoretic setting, Studies in Computational Intelligence 182 (2009), 67–94.

55.

Zhang

Y.L.

, Li

J.J.

and Wu

W.Z.

, On axiomatic characterizations of three pairs of covering based approximation operators, Information Sciences 180 (2010), 274–287.

56.

Zhang

Y.L.

and Luo

M.K.

, On minimization of axiom sets characterizing covering-based approximation operators, Information Sciences 181 (2011), 3032–3042.

57.

Zhao

Y.X.

, Li

J.H.

, Liu

W.Q.

and Xu

W.H.

, Cognitive concept learning from incomplete information, International Journal of Machine Learning and Cybernetics 8(1) (2017), 3–20.

58.

Zhu

and Wang

F.Y.

, Reduction and axiomization of covering generalized rough sets, Information Sciences 152 (2003), 217–230.