Identifying Non-Sublattice Equivalence Classes Induced by an Attribute Reduction in FCA

Abstract

The detection of redundant or irrelevant variables (attributes) in datasets becomes essential in different frameworks, such as in Formal Concept Analysis (FCA). However, removing such variables can have some impact on the concept lattice, which is closely related to the algebraic structure of the obtained quotient set and their classes. This paper studies the algebraic structure of the induced equivalence classes and characterizes those classes that are convex sublattices of the original concept lattice. Particular attention is given to the reductions removing FCA’s unnecessary attributes. The obtained results will be useful to other complementary reduction techniques, such as the recently introduced procedure based on local congruences.

1. Introduction

Redundant data hinder the efficient acquisition of information from datasets. Obviously, the elimination of redundant data should not modify the information contained in a dataset. The most common redundant data consist of repeated entries, which can be removed without cost, or dependent variables, which can be derived from the independent variables, whose detection is an appealing research topic in many areas dealing with data analysis, such as Formal Concept Analysis (FCA). This mathematical theory was original developed in the 1980s by R. Wille and B. Ganter [1], and it has intensively been studied from a theoretical and applied point of view [2,3,4,5,6,7,8,9,10,11,12]. Two important features of FCA, in which the notion of Galois connection is fundamental [13,14,15,16], is that the information contained in a relational dataset can be described in a hierarchic manner by means of a complete lattice [17] and that dependencies between attributes can be determined [18,19,20,21], which is fundamental to applications. In both features, the removal of redundant data has a great impact.

The detection of (ir)relevant attributes or objects of a given formal context in FCA has been studied from different points of view, for example: in order to obtain a concept lattice isomorphic to the original one [22,23,24,25,26], to efficiently reduce the size of the concept lattice [8,27,28,29,30,31,32], to extensional stability [33], to consider contexts with positive and negative attributes [34], to apply the rough set philosophy [35,36,37], etc. Notice that the different mechanisms focused on attribute reduction can dually be adapted to object reduction.

In [36], it was demonstrated that attribute reductions of formal contexts induce equivalence relations whose equivalence classes have the structure of join-semilattices. In addition, in [38], local congruences were introduced as equivalence relations defined on lattices whose equivalence classes are sublattices of the original lattice. Therefore, local congruences were intended to complement the attribute reductions of formal contexts in order to ensure that the equivalence classes ${\left[C\right]}_D$ are sublattices of the original concept lattice. Due to a join-semilattice with the least element being a lattice, if the infimum $C_m={\bigwedge }_{C_i\in {\left[C\right]}_D}{C}_i$ belongs to the equivalence class, we can assert that the class already is a sublattice. Obviously, in these cases, the use of local congruences, as a complementary mechanism to the attribute reduction, turns out to be unnecessary since they do not provide any modification in the classes, and so, it modifies neither the attributes nor the objects generating the concepts of these classes. Therefore, it is very interesting to characterize the required conditions in which these cases hold, which was precisely the main issue addressed in [39].

In this paper, we continue with the research line initiated in [39], improving the results introduced in that work. Specifically, in this paper, we show an enhanced version of Proposition 4 and Corollary 1 in [39], which characterize the infimum of the elements belonging to a non-singleton classes. In addition, due to the attribute reductions usually carried out in FCA tending to discard the set of unnecessary attributes from the formal context, we also analyze the characterization of the infimum of the induced equivalence classes when the considered attribute reduction does not contain unnecessary attributes. The fact of considering attribute reductions that do not contain unnecessary attributes allows us also to prove some interesting results. For example, we establish a sufficient condition to ensure an equivalence between meet-irreducible concepts in the reduced context and in the original one. Furthermore, under this consideration, we also prove that when the original concept lattice is isomorphic to a distributive lattice, the induced equivalence classes by the reduction are always sublattices. Finally, all the results presented in this work are accompanied by illustrative examples whose objective is to clarify all the introduced ideas.

The paper is structured as follows: Section 2 reviews some preliminary notions related to formal concept analysis and attribute reduction. In Section 3, the contributions of this paper are presented, the study on the equivalence classes induced by an attribute reduction.This section is divided into two parts: first, we study sufficient conditions to characterize the infimum of equivalence classes, and second, we carry out an analysis of the characterization when the considered subset of attributes in the reduction does not contain unnecessary attributes. Finally, Section 4 presents some conclusions and provides some prospects for future work.

2. Preliminaries

First of all, we recall some basic notions about formal concept analysis and attribute reduction. A context in FCA is a triple $(A,B,R)$ where A is a set of attributes, B is a set of objects, and $R\subseteq A\times B$ is a relation, such that $(a,x)\in R$, if the object $x\in B$ possesses the attribute $a\in A$, and $(a,x)\notin R$, otherwise. The derivation operators are the mappings ${}^{\uparrow }:2^B\to 2^A$ and ${}^{\downarrow }:2^A\to 2^B$ defined for each $X\subseteq B$ and $Y\subseteq A$ as:

$$\begin{array}{ccc}\hfill X^{\uparrow }& =& \{a\in A\mid \mathrm{for}\mathrm{all}x\in X,(a,x)\in R\}\hfill \end{array}$$

(1)

$$\begin{array}{ccc}\hfill Y^{\downarrow }& =& \{x\in B\mid \mathrm{for}\mathrm{all}a\in Y,(a,x)\in R\}\hfill \end{array}$$

(2)

A concept in $(A,B,R)$ is a pair $C=(X,Y)$, where $X\subseteq B$, $Y\subseteq A$, and satisfies that $X^{\uparrow }=Y$ and $Y^{\downarrow }=X$. The subset X is called the extent of the concept, and the subset Y is called the intent; they are denoted by $\mathfrak{E}\left(C\right)$ and $\mathfrak{I}\left(C\right)$, respectively. Furthermore, a concept generated by an attribute $a\in A$, that is $(a^{\downarrow },a^{\downarrow \uparrow })$, is called an attribute concept.

In addition, the set of concepts is denoted by $\mathcal{C}(A,B,R)$ and is a complete lattice with the inclusion order on the left argument, that is for each $(X_1,Y_1),(X_2,Y_2)\in \mathcal{C}(A,B,R)$, we have $(X_1,Y_2)\le (X_2,Y_2)$ if $X_1\subseteq X_2$. $\left(\mathcal{C}\right(A,B,R),\le )$ is called the concept lattice of the context $(A,B,R)$. The meet ∧ and join ∨ operators are defined by:

$$(X_1,Y_1)\wedge (X_2,Y_2)=(X_1\wedge X_2,{(Y_1\vee Y_2)}^{\downarrow \uparrow })$$

$$(X_1,Y_1)\vee (X_2,Y_2)=({(X_1\vee X_2)}^{\uparrow \downarrow },Y_1\wedge Y_2)$$

for all $(X_1,Y_1),(X_2,Y_2)\in \mathcal{C}(A,B,R)$.

Considering a subset of attributes $Y\subseteq A$ and the restriction relation $R_{|Y\times B}=R\cap (Y\times B)$, the triple $(Y,B,R_{|Y\times B})$ is also a formal context. There are two relevant notions regarding subsets of attributes in FCA that we recall below.

Definition 1.

Given a context $(A,B,R)$, if there exists a subset of attribute $Y\subseteq A$ such that $\mathcal{C}(A,B,R)\cong \mathcal{C}(Y,B,R_{|Y\times B})$, then Y is called a consistent set of $(A,B,R)$. Moreover, if $\mathcal{C}(Y\backslash \left\{y\right\},B,R_{|Y\backslash \{y\}\times B})\ncong \mathcal{C}(A,B,R)$, for all $y\in Y$, then Y is called a reduct of $(A,B,R)$.

Then, we can recall the definition of the three types of attributes considering the notation in [40] to denote the subsets of attributes.

Definition 2.

Given an index set Λ, a formal context $(A,B,R)$, and the set $\{Y_i\mid Y_{i}isareduct,i\in \mathsf{\Lambda }\}$ of all reducts of $(A,B,R)$, the set of attributes A can be divided into the following three parts:

• Absolutely necessary attributes $C_f={\bigcap }_{i\in \mathsf{\Lambda }}{Y}_i$.
• Relatively necessary attributes $K_f=\left({\bigcup }_{i\in \mathsf{\Lambda }}{Y}_i\right)\backslash \left({\bigcap }_{i\in \mathsf{\Lambda }}{Y}_i\right)$.
• Absolutely unnecessary attributes $I_f=A\backslash \left({\bigcup }_{i\in \mathsf{\Lambda }}{Y}_i\right)$.

The set of attributes of the context is closely related to the meet-irreducible concepts, whose notion is recalled in the following definition.

Definition 3.

Given a lattice $(L,⪯)$, such that ∧ is the meet operator, and an element $x\in L$ verifying:

• If L has a top element ⊤, then $x\ne \top$;
• If $x=y\wedge z$, then $x=y$ or $x=z$, for all $y,z\in L$;

x is called a meet-irreducible (∧-irreducible) element of L.

In particular, in this paper, we use the notion of the unnecessary attribute and, specifically, the following characterization introduced in [26].

Theorem 1.

Given a formal context $(A,B,R)$ and the set of ∧-irreducible elements of $\mathcal{C}(A,B,R)$, denoted by $M_F(A,B,R)$, the following equivalences are obtained:

• $a\in I_f$ if and only if $(a^{\downarrow },a^{\downarrow \uparrow })\notin M_F(A,B,R)$.
• $a\in K_f$ if and only if $(a^{\downarrow },a^{\downarrow \uparrow })\in M_F(A,B,R)$ and there exists $a_1\in A$, $a_1\ne a$, such that $(a_1^{\downarrow },a_1^{\downarrow \uparrow })=(a^{\downarrow },a^{\downarrow \uparrow })$.
• $a\in C_f$ if and only if $(a^{\downarrow },a^{\downarrow \uparrow })\in M_F(A,B,R)$ and $(a_1^{\downarrow },a_1^{\downarrow \uparrow })\ne (a^{\downarrow },a^{\downarrow \uparrow })$, for all $a_1\in A$, $a_1\ne a$.

With respect to attribute reductions in FCA, we recall the main results related to the induced equivalence relation on the set of concepts of the original concept lattice when we reduce the set of attributes of a formal context. For more detailed information, we refer the reader to [36,39]. The following proposition was proven in [36] for the classical setting of FCA.

Proposition 1

([36]). Given a context $(A,B,R)$ and a subset $D\subseteq A$, the set ${\rho }_D=\{((X_1,Y_1),(X_2,Y_2))\mid (X_1,Y_1),(X_2,Y_2)\in \mathcal{C}(A,B,R),X_1^{{\uparrow }_D\downarrow }=X_2^{{\uparrow }_D\downarrow }\}$ is an equivalence relation, where ${}^{{\uparrow }_D}$ denotes the concept-forming operator given in Expression (2), restricted to the subset of attributes $D\subseteq A$.

Moreover, the authors also proved that each equivalence class of the induced equivalence relation has a structure of join-semilattice, and they also determined the maximum element.

Proposition 2

([36]). Given a context $(A,B,R)$, a subset $D\subseteq A$, and a class ${\left[(X,Y)\right]}_D$ of the quotient set $\mathcal{C}(A,B,R)/{\rho }_D$, the class ${\left[(X,Y)\right]}_D$ is a join-semilattice with maximum element $(X^{{\uparrow }_D\downarrow },X^{{\uparrow }_D\downarrow \uparrow })$.

In addition, an ordering relation on the set of equivalence classes given by the relation ${\rho }_D$ was defined in [41].

Proposition 3

([41]). On the quotient set $\mathcal{C}(A,B,R)/{\rho }_D$ associated with a context $(A,B,R)$, the relation ${⊑}_D$, defined as ${\left[(X_1,Y_1)\right]}_D{⊑}_D{\left[(X_2,Y_2)\right]}_D$ if ${X_1}^{{\uparrow }_D\downarrow }\subseteq {X_2}^{{\uparrow }_D\downarrow }$, for all ${\left[(X_1,Y_1)\right]}_D,{\left[(X_2,Y_2)\right]}_D\in \mathcal{C}(A,B,R)/{\rho }_D$, is an ordering relation.

The quotient set $\mathcal{C}(A,B,R)/{\rho }_D$ with the ordering relation ${⊑}_D$ is closely related to the reduced concept lattice as shown in the following result presented in [41].

Theorem 2

([41]). Given a context $(A,B,R)$ and a subset of attributes $D\subseteq A$, we have that the quotient set given by ${\rho }_D$ and the reduced concept lattice by D are isomorphic, that is:

$$(\mathcal{C}(A,B,R)/{\rho }_D,{⊑}_D)\cong (\mathcal{C}(D,B,R_{|D\times B}),{\le }_D)$$

where ${\le }_D$ is the ordering in the original concept lattice restricted to the reduced one.

Next, the notation of the infimum of an equivalence class is given to simplify the expressions in which it is involved.

Definition 4.

Given a context $(A,B,R)$, a subset of attributes $D\subseteq A$, and an equivalence class ${\left[C\right]}_D$, with $C\in \mathcal{C}(A,B,R)$, of the induced equivalence relation, the infimum of the subset of concepts ${\left[C\right]}_D$ is denoted by $C_m$, that is $C_m={\bigwedge }_{C_i\in {\left[C\right]}_D}{C}_i$.

The following result was presented in [39], and it establishes preliminary consequences whenever a class, of the equivalence relation induced by an attribute reduction, contains its infimum.

Proposition 4

([39]). Let $(A,B,R)$ be a context, $D\subseteq A$ a subset of attributes, and ${\left[C\right]}_D$ an equivalence class of the induced equivalence relation, with $C\in \mathcal{C}(A,B,R)$, which is not a convex sublattice, then we have that one of the following statements is satisfied:

• There exists at least one attribute $a\in D$ such that $C_m=(a^{\downarrow },a^{\downarrow \uparrow })$.
• There exists a concept $C^{*}\in M_F(A,B,R)$ in a meet-irreducible decomposition $\{C_j\in M_F(A,B,R)\mid j\in J\}$ of $C_m$, such that $C_{i_0}\nleqq C^{*}$ for a concept $C_{i_0}\in {\left[C\right]}_D$.

We continue, in the following sections, this study exploring characterizations of the infimum of equivalence classes. Lastly, distributive lattices play an important role at the end of the paper. We recall their definition below.

Definition 5.

A lattice $(L,⪯)$ is called distributive if, for all $x,y,z,\in L$,

$$x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z).$$

Distributive lattices offer interesting properties such as the uniqueness of meet and join-irreducible decompositions and the following result.

Proposition 5

([17]). Given a distributive lattice $(L,⪯)$ and a meet-irreducible element p, if ${\wedge }_{i\in I}{x}_i⪯p$, then there exists $i_0\in I$, such that $x_{i_0}⪯p$.

3. Characterizing the Infimum of Classes

In this section, we continue with the study on the equivalence classes induced by a reduction of attributes presented in [39], improving the results introduced in it. From this point forward, a formal context $(A,B,R)$ is fixed, and the maximum element of an equivalence class ${\left[C\right]}_D$, with $D\subseteq A$ and $C=(X,Y)\in \mathcal{C}(A,B,R)$, is denoted by $C_M=(X_M,Y_M)$. Notice that Proposition 2 characterizes $C_M$ as $(X^{{\uparrow }_D\downarrow },X^{{\uparrow }_D\downarrow \uparrow })$, and therefore, $X_M=X^{{\uparrow }_D\downarrow }$ is also the extent of a concept of the reduced concept lattice $\mathcal{C}(D,B,R_{|D\times B})$.

First of all, different technical results are introduced. Given a context $(A,B,R)$ and any two concepts of its corresponding concept lattice $C_1=(X_1,Y_1),C_2=(X_2,Y_2)\in \mathcal{C}(A,B,R)$, it is known that if $C_1<C_2$, then there exists $a_0\in Y_1$, such that $a_0\notin Y_2$. This attribute is completely determined when attribute concepts are considered.

Proposition 6.

Given a context $(A,B,R)$, $C_1\in \mathcal{C}(A,B,R)$, $D\subseteq A$, $a\in D$, and a concept $C_2=(a^{\downarrow },a^{\downarrow \uparrow })$, we have that:

$$C_1\nleqq C_2 if and only if a\notin \mathfrak{I}\left(C_1\right)$$

Proof. 

If $a\in \mathfrak{I}\left(C_1\right)$, then by the properties of the concept-forming operators, we obtain that $a^{\downarrow \uparrow }\subseteq \mathfrak{I}{\left(C_1\right)}^{\downarrow \uparrow }=\mathfrak{I}\left(C_1\right)$, which leads us to a contradiction with the hypothesis $C_1\nleqq C_2$. Thus, $a\notin \mathfrak{I}\left(C_1\right)$.

By reduction ad absurdum, we assume that $C_1\le C_2$, then $\mathfrak{I}\left(C_2\right)\subseteq \mathfrak{I}\left(C_1\right)$, which implies that:

$$a\in a^{\downarrow \uparrow }=\mathfrak{I}\left(C_2\right)\subseteq \mathfrak{I}\left(C_1\right)$$

Hence, we obtain a contradiction with the hypothesis $a\notin \mathfrak{I}\left(C_1\right)$. □

In a similar way, the following proposition arises for equivalence classes induced by an attribute reduction.

Proposition 7.

Given a context $(A,B,R)$, $C_1,C_2\in \mathcal{C}(A,B,R)$ with $C_1\le C_2$, and $D\subseteq A$, we have that $C_1\notin {\left[C_2\right]}_D$ if and only if there exists $a\in D$, such that $a\in \mathfrak{I}\left(C_1\right)$ and $a\notin \mathfrak{I}\left(C_2\right)$.

Proof. 

We consider a context $(A,B,R)$ and a subset of attribute $D\subseteq A$. Let us assume any two concepts $C_1,C_2\in \mathcal{C}(A,B,R)$ such that $C_1\le C_2$. On the one hand, if $C_1\notin {\left[C_2\right]}_D$, then we obtain straightforwardly that $C_1<C_2$, and hence, there exists $a\in D$, such that $a\in \mathfrak{I}\left(C_1\right)$ and $a\notin \mathfrak{I}\left(C_2\right)$. On the other hand, if there exists an attribute $a\in D$ such that $a\in \mathfrak{I}\left(C_1\right)$ and $a\notin \mathfrak{I}\left(C_2\right)$, then $C_1\notin {\left[C_2\right]}_D$ by the definition of ${\rho }_D$ in Proposition 1. □

In Proposition 7, we chose the concept $C_2$ to represent the equivalence class ${\left[C_2\right]}_D$, but this class univocally determines a concept in the reduced concept lattice $\mathcal{C}(D,B,R_{|D\times B})$ by Theorem 2. In order to differentiate between classes and associated concepts in the reduced concept lattice, we denote the latter with a line over the concept, that is $\overline{C_2}$.

3.1. Characterizing the Infimum of Classes

The following property determines a sufficient condition to ensure that the equivalence class of the infimum element is generated by an attribute concept.

Theorem 3.

Let $(A,B,R)$ be a context, a finite subset of attributes $D\subseteq A$, and $C\in \mathcal{C}(A,B,R)$ such that $C_j\in {\left[C\right]}_D$, for all concepts $C_j$ in any meet-irreducible decomposition $\{C_j\in M_F(A,B,R)\mid j\in J\}$ of $C_m$. If $C_m$ is not in ${\left[C\right]}_D$, then there exists an attribute $a\in D$ such that ${\left[C_m\right]}_D={\left[(a^{\downarrow },a^{\downarrow \uparrow })\right]}_D$.

Proof. 

Since $C_m$ is not in ${\left[C\right]}_D$, by Proposition 7, there exists $a_1\in D$, such that $a_1\in \mathfrak{I}\left(C_m\right)$ and $a_1\notin \mathfrak{I}\left(C\right)$.

If $C_m=(a_1^{\downarrow },a_1^{\downarrow \uparrow })$, we are finished. Otherwise, there exists $C_1=(a_1^{\downarrow },a_1^{\downarrow \uparrow })$, such that $C_m<C_1$. If $C_1\in {\left[C\right]}_D$, then $a_1^{{\downarrow \uparrow }_D}=\mathfrak{I}{\left(C\right)}^{{\downarrow \uparrow }_D}$, and we obtain that:

$$a_1\in a_1^{{\downarrow \uparrow }_D}=\mathfrak{I}{\left(C\right)}^{{\downarrow \uparrow }_D}\subseteq \mathfrak{I}{\left(C\right)}^{\downarrow \uparrow }=\mathfrak{I}\left(C\right)$$

which leads us to a contradiction. Therefore, we have that $C_1\notin {\left[C\right]}_D$. Hence, in particular, $C_1$ cannot be meet-irreducible, since by hypothesis, in this case, $C_1$ should be in ${\left[C\right]}_D$. Therefore, we consider a meet-irreducible decomposition $\{C_j^1\in M_F(A,B,R)\mid j\in J_1\}$ of $C_1$. Due to $C_m\le C_1$, the meet-irreducible concepts $C_j^1$ are in a meet-irreducible decomposition of $C_m$, which implies by hypothesis that $C_j^1\in {\left[C\right]}_D$ for all $j\in J_1$. Therefore,

$${\left[C_1\right]}_D{⊏}_D{\left[C_j\right]}_D={\left[C\right]}_D$$

for all $j\in J_1$, where ${⊏}_D$ is the ordering defined in Proposition 3. As a consequence, if ${\left[C_m\right]}_D={\left[C_1\right]}_D$, then we are finished. Otherwise, we have that ${\left[C_m\right]}_D{⊏}_D{\left[C_1\right]}_D{⊏}_D{\left[C\right]}_D$. Thus, there exists $a_2\in D\backslash \left\{a_1\right\}$, such that $a_2\in \mathfrak{I}\left(C_m\right)$ and $a_2\notin \mathfrak{I}\left(C\right)$. This process can be repeated, and due to D being finite, it must finish in an attribute $a\in D$ such that ${\left[C_m\right]}_D={\left[(a^{\downarrow },a^{\downarrow \uparrow })\right]}_D$. □

Note that Theorem 3 arises from the restriction of the hypotheses of Proposition 4. The following example is useful to illustrate the previous result. This example also inspects Corollary 1 presented in [39], and as a consequence, it also argues that Theorem 3 must be considered instead of this corollary.

Example 1.

We consider a context composed of the set of attributes $A=\{a_1,a_2,a_3,a_4\}$ and the set of objects $B=\{b_1,b_2,b_3\}$, related by $R:A\times B\to \{0,1\}$, defined on

Table 1. Relation of the context of Example 1.

R	${\mathit{b}}_1$	${\mathit{b}}_2$	${\mathit{b}}_3$
$a_1$	1	1	0
$a_2$	1	0	1
$a_3$	0	1	1
$a_4$	0	0	1

, which has the concepts listed on

Table 2. List of extents and intents of every concept of the context of Example 1.

${\mathit{C}}_{\mathit{i}}$	Extent			Intent
	${\mathit{b}}_{\mathbf{1}}$	${\mathit{b}}_{\mathbf{2}}$	${\mathit{b}}_{\mathbf{3}}$	${\mathbf{a}}_{\mathbf{1}}$	${\mathbf{a}}_{\mathbf{2}}$	${\mathbf{a}}_{\mathbf{3}}$	${\mathbf{a}}_{\mathbf{4}}$
0	0	0	0	1	1	1	1
1	1	0	0	1	1	0	0
2	0	1	0	1	0	1	0
3	0	0	1	0	1	1	1
4	1	1	0	1	0	0	0
5	1	0	1	0	1	0	0
6	0	1	1	0	0	1	0
7	1	1	1	0	0	0	0

. The associated concept lattice is given on the left side of Figure 1.

From this context, we obtain the attribute concepts listed below, together with the induced equivalence classes obtained by removing attributes $a_2$ and $a_3$, that is considering only the subset of attributes $D=\{a_1,a_4\}$.

$$\begin{array}{cccccccc}{C}_3=(a_4^{\downarrow },a_4^{\downarrow \uparrow })\hfill & & & & & \hfill {\left[C_0\right]}_D& \hfill =& \left\{C_0\right\}\hfill \\ C_4=(a_1^{\downarrow },a_1^{\downarrow \uparrow })\hfill & \hfill {\left[C_1\right]}_D& \hfill =& \hfill {\left[C_2\right]}_D& \hfill =& \hfill {\left[C_4\right]}_D& \hfill =& \{C_1,C_2,C_4\}\hfill \\ C_5=(a_2^{\downarrow },a_2^{\downarrow \uparrow })\hfill & & & & & \hfill {\left[C_3\right]}_D& \hfill =& \left\{C_3\right\}\hfill \\ C_6=(a_3^{\downarrow },a_3^{\downarrow \uparrow })\hfill & \hfill {\left[C_5\right]}_D& \hfill =& \hfill {\left[C_6\right]}_D& \hfill =& \hfill {\left[C_7\right]}_D& \hfill =& \{C_5,C_6,C_7\}\hfill \end{array}$$

The partition induced by such a reduction is shown on the right side of Figure 1. Notice that two of the obtained equivalence classes are not convex sublattices of the original concept lattice. The first one contains the concepts $C_1$, $C_2$, $C_4$, and the other one contains the concepts $C_5$, $C_6$, $C_7$. However, the reasons for which these classes are not convex sublattices are well differentiated.

On the one hand, if we consider the equivalence class ${\left[C_7\right]}_D$, we have that the infimum of the concepts of this class is the concept $C_3$. Notice that the meet-irreducible decomposition of $C_3$ is $C_3=C_5\wedge C_6$, and both concepts $C_5$ and $C_6$ belong to ${\left[C_7\right]}_D$; this means that we are under the conditions given in Theorem 3. Since $C_3\notin {\left[C_7\right]}_D$, we have that ${\left[C_3\right]}_D={\left[(a^{\downarrow },a^{\downarrow \uparrow })\right]}_D$, with $a\in D$. Specifically, in this case, we have that the concept $C_3$ is just generated by the attribute $a_4\in D$. Notice that $C_m$ is not always an attribute concept. For example, if we consider $D^{\prime }=\left\{a_4\right\}$, then we obtain two classes: ${\left[C_7\right]}_{D^{\prime }}=\{C_7,C_6,C_5,C_4,C_2,C_1\}$ and ${\left[C_3\right]}_{D^{\prime }}=\{C_3,C_0\}$, where $C_0=C_4\wedge C_5\wedge C_6$ and satisfying that $C_4,C_5,C_6$ belong to ${\left[C_7\right]}_{D^{\prime }}$. Therefore, the hypotheses of Theorem 3 hold; indeed, ${\left[C_0\right]}_{D^{\prime }}={\left[(a_4^{\downarrow },a_4^{\downarrow \uparrow })\right]}_{D^{\prime }}$; however, $C_0$ is not an attribute concept.

On the other hand, if we consider the equivalence class ${\left[C_4\right]}_D$, we have that the infimum of the equivalence class ${\left[C_4\right]}_D$ is the concept $C_0$. In this case, the decomposition of $C_0$ is $C_0=C_4\wedge C_5\wedge C_6$, we observe that there are two meet-irreducible concepts, $C_5$ and $C_6$, such that $C_5,C_6\notin {\left[C_4\right]}_D$. Therefore, we cannot apply Theorem 3 since the hypothesis are not satisfied. Moreover, since the concept lattice $\mathcal{C}(A,B,R)$ is distributive, the condition that the meet-irreducible concepts of the decomposition are in the class is a required hypothesis in [39], Corollary 1. In addition, this corollary must also be corrected in its conclusion, since ${\left[C_m\right]}_D={\left[(a^{\downarrow },a^{\downarrow \uparrow })\right]}_D$ can only be ensured. Thus, Theorem 3 presents an improved version of Corollary 1 given in [39].

Next, we present one of the main results of this paper, which characterizes the infimum of the elements of non-singleton classes.

Theorem 4.

Given a context $(A,B,R)$, a subset of attributes $D\subseteq A$, and a concept $C\in \mathcal{C}(A,B,R)$ such that its equivalence class ${\left[C\right]}_D$ of the induced equivalence relation is not a singleton, we have that $C_m\notin {\left[C\right]}_D$ if and only if one of the following statements is satisfied:

• There exists at least one attribute $a\in D$ such that $C_m=(a^{\downarrow },a^{\downarrow \uparrow })$.
• There exists a concept $C^{*}\in \mathcal{C}(A,B,R)$, such that $C^{*}=(a^{*\downarrow },a^{*\downarrow \uparrow })$ with $a^{*}\in D$, $C^{*}\notin {\left[C\right]}_D$, and $C_M\nleqq C^{*}$. Moreover, $\overline{C^{*}}$ is in a meet-irreducible decomposition $\{\overline{C_j}\in M_F(D,B,R_{|D\times B})\mid j\in J\}$ of $\overline{C_m}$. Recall that the concept of the reduced concept lattices is denoted with an overline.

Proof. 

Let us assume that we reduce the context $(A,B,R)$ by a subset of attributes $D\subseteq A$. Given a concept $C\in \mathcal{C}(A,B,R)$, we consider the induced equivalence class ${\left[C\right]}_D$, which is not a singleton. The concept $C_m={\bigwedge }_{C_i\in {\left[C\right]}_D}{C}_i$ does not necessarily belong to the class ${\left[C\right]}_D$ since ${\left[C\right]}_D$ is a join-semilattice by Theorem 2.

Therefore, if $C_m\notin {\left[C\right]}_D$, then we can distinguish two cases:

• If there exists $a_0\in D$ such that $C_m=(a_0^{\downarrow },a_0^{\downarrow \uparrow })$, the first statement holds.
• Otherwise, $C_m$ is not generated by any attribute of D. On the one hand, since $C_m\notin {\left[C\right]}_D$, we have that $\overline{C_m}<\overline{C}$ and $\overline{C}=\overline{C_i}$ for all $C_i\in {\left[C\right]}_D$; applying Proposition 7 to the reduced context, we can assert that there exists at least one attribute $a^{*}\in D$ such that $a^{*}\in \mathfrak{I}\left(C_m\right)$ and $a^{*}\notin \mathfrak{I}\left(C_i\right)$ for all $C_i\in {\left[C\right]}_D$. On the other hand, there exists an attribute concept $C^{*}\in \mathcal{C}(A,B,R)$ such that $C^{*}=(a^{*\downarrow },a^{*\downarrow \uparrow })$, which implies that $C_m\le C^{*}$. Moreover, $C^{*}\notin {\left[C\right]}_D$, because $a^{*}\notin \mathfrak{I}\left(C_i\right)$ for all $C_i\in {\left[C\right]}_D$. If $C^{*}\in M_F(A,B,R)$, then the concept $C^{*}$ is the required concept, and the second statement holds.
  If $C^{*}\notin M_F(A,B,R)$, we consider a meet-decomposition of $C^{*}$ in the reduced concept lattice $\mathcal{C}(D,B,R_{|D\times B})$, that is $\overline{C^{*}}={\bigwedge }_{j\in J}\overline{C_j}$, where $\overline{C_j}\in M_F(D,B,R_{|D\times B})$ for all $j\in J$. Since $C^{*}=(a^{*\downarrow },a^{*\downarrow \uparrow })$ and $a^{*}\notin \mathfrak{I}\left(C_M\right)$, then by Proposition 6, we have that $\overline{C_M}\nleqq \overline{C^{*}}$. If $\overline{C_M}\le \overline{C_j}$, for all $j\in J$, then, by the infimum property, we obtain that $\overline{C_M}\le {\bigwedge }_{\overline{C_j}\in J}\overline{C_j}=\overline{C^{*}}$, which leads us to a contradiction. Therefore, there exists $j_0\in J$, such that $\overline{C_{j_0}}$ is in a meet-decomposition in the reduced context of $\overline{C^{*}}$, with $\overline{C_M}\nleqq \overline{C_{j_0}}$. This last property implies that $C_{j_0}\notin {\left[C_M\right]}_D$ (since, otherwise, $\overline{C_M}=\overline{C_{j_0}}$) and $C_M\nleqq C_{j_0}$. Moreover, since $\overline{C_{j_0}}$ is a meet-irreducible concept of the reduced context, then there exists $a^{\prime }\in D$, such that $\overline{C_{j_0}}=(a^{\prime \downarrow },a^{{\prime \downarrow \uparrow }_D})$.
  Thus, $C_{j_0}$ is the required concept in the second statement.

Now, we assume that one of the statements is satisfied, and we again consider two cases:

• There exists $a_0\in D$ such that $C_m=(a_0^{\downarrow },a_0^{\downarrow \uparrow })$, then since ${\left[C\right]}_D$ is not a singleton, we have that $C_m={\bigwedge }_{C_i\in {\left[C\right]}_D}{C}_i<C$, and so, $a_0\in \mathfrak{I}\left(C_m\right)$ and $a_0\notin \mathfrak{I}\left(C\right)$. Therefore, by Proposition 7, we obtain that $C_m\notin {\left[C\right]}_D$.
• There exists a concept $C^{*}\in \mathcal{C}(A,B,R)$, such that $C^{*}=(a^{*\downarrow },a^{*\downarrow \uparrow })$ with $a^{*}\in D$, $C_M\nleqq C^{*}$, and $\overline{C^{*}}$ is in a meet-irreducible decomposition $\{\overline{C_j}\in M_F(D,B,R_{|D\times B})\mid j\in J\}$ of $\overline{C_m}$. Hence, by Proposition 6, we have that $a^{*}\in \mathfrak{I}\left(C^{*}\right)$ and $a^{*}\notin \mathfrak{I}\left(C_M\right)$. Due to $\overline{C^{*}}$ being in a meet-irreducible decomposition of $\overline{C_m}$, in particular, we have that $C_m\le C^{*}$, which implies that $a^{*}\in \mathfrak{I}\left(C^{*}\right)\subseteq \mathfrak{I}\left(C_m\right)$. Thus, since $a^{*}\in \mathfrak{I}\left(C_m\right)$ and $a^{*}\notin \mathfrak{I}\left(C_M\right)$, by Proposition 7, we obtain that $C_m\notin {\left[C_M\right]}_D={\left[C\right]}_D$.

□

Notice that, given $C^{*}=(a^{*\downarrow },a^{*\downarrow \uparrow })$ with $a^{*}\in D$, if $C\nleqq C^{*}$, then $a^{*}$ cannot belong to $\mathfrak{I}\left(C\right)$, and so, $C^{*}\notin {\left[C\right]}_D$. Hence, the hypothesis $C^{*}\notin {\left[C\right]}_D$ is not considered in the implication to prove $C_m\notin {\left[C\right]}_D$. Moreover, from the hypothesis that $\overline{C^{*}}$ is in a meet-irreducible decomposition $\{\overline{C_j}\in M_F(D,B,R_{|D\times B})\mid j\in J\}$ of $\overline{C_m}$, only $C_m\le C^{*}$ is used. These hypotheses are included in the characterization in order to collect as much as possible the consequences of $C_m\notin {\left[C\right]}_D$. The following corollary presents the reduced version.

Corollary 1.

Given a context $(A,B,R)$, a subset of attributes $D\subseteq A$, and a concept $C\in \mathcal{C}(A,B,R)$ such that its equivalence class ${\left[C\right]}_D$ of the induced equivalence relation is not a singleton, then $C_m\notin {\left[C\right]}_D$ if and only if one of the following statements is satisfied:

• There exists at least one attribute $a\in D$ such that $C_m=(a^{\downarrow },a^{\downarrow \uparrow })$.
• There exists a concept $C^{*}\in \mathcal{C}(A,B,R)$, such that $C^{*}=(a^{*\downarrow },a^{*\downarrow \uparrow })$ with $a^{*}\in D$, $C_m\le C^{*}$, and $C_M\nleqq C^{*}$.

Notice that the previous corollary improves Proposition 4, since the concept $C^{*}$ must be generated by an attribute of the reduced attribute subset D, and it does not need to be a meet-irreducible concept in order to obtain the equivalence. An application of Theorem 4 is illustrated in the following example.

Example 2.

We consider a context $(A,B,R)$ whose Hasse diagram of its concept lattice $\mathcal{C}(A,B,R)$ is on the left side of Figure 2. Labels in the concept lattice indicate the mappings γ and μ of the fundamental theorem, that is the node labeled as a represents the concept $(a^{\downarrow },a^{\downarrow \uparrow })$ for $a\in A$, and similarly, the node labeled as b represents the concept $(b^{\uparrow },b^{\uparrow \downarrow })$ for $b\in B$.

Now, if we consider a subset of attributes $D=\{a_1,a_4,a_5\}$, we obtain an induced partition, which is illustrated in the middle of Figure 2. We choose the class ${\left[C_4\right]}_D=\{C_2,C_3,C_4\}$, which is not a singleton, and therefore, we are under the conditions of Theorem 4. Thus, $C_m=C_0\notin {\left[C_4\right]}_D$ if and only if one of the statements of Theorem 4 is satisfied. In this case, we have that $C_m\notin {\left[C_4\right]}_D$, and the second statement holds, as we show next.

We have that the concept $C_5\in \mathcal{C}(A,B,R)$ is the attribute concept generated by $a_5$, $C_5=(a_5^{\downarrow },a_5^{\downarrow \uparrow })$, where $a_5\in D$, and it satisfies that $C_5\notin {\left[C_4\right]}_D$ and $C_M=C_4\nleqq C_5$. Moreover, the meet-irreducible decomposition of $\overline{C_m}$ in the reduced concept lattice, shown on the right side of Figure 2, is the set $\{\overline{C_4},\overline{C_5}\}$. Since $\overline{C_5}$ is in the meet-irreducible decomposition of $\overline{C_m}$, we can conclude that the second statement is satisfied.

3.2. Attribute Reduction without Unnecessary Attributes

Attribute reduction in FCA usually removes unnecessary attributes. Hence, this section analyzes the characterization when the set D does not contain unnecessary attributes. This study is interesting, for example, for any attribute reduction strategy merging FCA and other frameworks, such as rough set theory [35,42,43]. The first result shows that Statement 1 in Proposition 4 only arises when the context contains unnecessary attributes.

Proposition 8.

Given a context $(A,B,R)$, a subset of attributes $D\subseteq A$, and a concept $C\in \mathcal{C}(A,B,R)$, if the equivalence class ${\left[C\right]}_D$ of the induced equivalence relation is not a singleton and there exists $a\in D$ such that $C_m=(a^{\downarrow },a^{\downarrow \uparrow })$, then $a\in I_f$.

Proof. 

Since ${\left[C\right]}_D$ is not a singleton, $C_m={\bigwedge }_{C_i\in {\left[C\right]}_D}{C}_i$ and $C_m=(a^{\downarrow },a^{\downarrow \uparrow })$ with $a\in D$, we have that $C_m$ is not a ∧-irreducible concept. Therefore, $a\in A$ generates a non-irreducible concept, and by Theorem 1, we obtain that $a\in I_f$. □

As a consequence of this result, Statement 1 in Theorem 4 and Statement 1in Corollary 1 cannot be satisfied when D does not contain any unnecessary attribute of A. Hence, according to this consideration, Theorem 4 can be written as follows.

Corollary 2.

Given a context $(A,B,R)$, a subset of attributes $D\subseteq A$, such that $D\subseteq A\backslash I_f$, and a concept $C\in \mathcal{C}(A,B,R)$, where ${\left[C\right]}_D$ is not a singleton, then, $C_m\notin {\left[C\right]}_D$ if and only if there exists $C^{*}\in \mathcal{C}(A,B,R)$, such that $C^{*}=(a^{*\downarrow },a^{*\downarrow \uparrow })$ with $a^{*}\in D$, $C^{*}\notin {\left[C\right]}_D$, $C_M\nleqq C^{*}$, and $\overline{C^{*}}$ is in a meet-irreducible decomposition $\{\overline{C_j}\in M_F(D,B,R_{|D\times B})\mid j\in J\}$ of $\overline{C_m}$.

In general, a meet-irreducible $\overline{C^{*}}$ in the reduced concept lattice does not have an associated meet-irreducible concept in the original concept lattice as the following example shows.

Example 3.

Let us consider the concept lattice on the left side of Figure 3, which is associated with a context $\mathcal{C}(A,B,R)$. If we select the subset of attributes $D=\{a_1,a_2,a_6\}$, then we obtain the induced partition illustrated in the middle of Figure 3. As we can see in the figure, there is a class, ${\left[C_4\right]}_D=\{C_1,C_2,C_4\}$, such that the concept $C_m=C_0\notin {\left[C_4\right]}_D$. Therefore, by Theorem 4, there exists a concept satisfying the second statement of this theorem (the first statement is not satisfied since $C_0$ is not generated by any attribute).

Moreover, we have that the meet-irreducible decomposition of $\overline{C_m}$ is the set $\{\overline{C_3},\overline{C_4},\overline{C_5}\}$, as we can see in the reduced concept lattice induced by the attribute reduction depicted on the right side of Figure 3. In this case, the concept $\overline{C_3}$, which satisfies the conditions of the second statement of Theorem 4, is a meet-irreducible concept in the reduced concept lattice $\mathcal{C}(D,B,R_{|D\times B})$; however, the concept $C_3=(a_1^{\downarrow },a_1^{\downarrow \uparrow })$ is not a meet-irreducible concept in $\mathcal{C}(A,B,R)$.

The following result shows that removing unnecessary attributes provides a sufficient condition to ensure the equivalence between meet-irreducible concepts in the reduced context and in the original one.

Proposition 9.

Given a context $(A,B,R)$, a subset of attributes $D\subseteq A\backslash I_f$, and a concept $C\in \mathcal{C}(A,B,R)$, such that $C=(a^{\downarrow },a^{\downarrow \uparrow })$, with $a\in D$, the following equivalence holds:

$$C\in M_F(A,B,R) if and only if \overline{C}\in M_F(D,B,R_{|D\times B})$$

Proof. 

On the one hand, if we assume the concept C is a meet-irreducible concept in the original concept lattice, $C\in M_F(A,B,R)$, then taking into account that $a\in D$, the set of extents of the reduced concept lattice is included in the set of extents of the original, and if $C_1\le C_2$, then $\overline{C_1}\le \overline{C_2}$ holds too; we have that $\overline{C}=(a^{\downarrow },a^{{\downarrow \uparrow }_D})$ is also a meet-irreducible concept in the reduced concept lattice, $\overline{C}\in M_F(D,B,R_{|D\times B})$.

On the other hand, if we assume that $\overline{C}\in M_F(D,B,R_{|D\times B})$, then there exists $a\in D$ such that $\overline{C}=(a^{\downarrow },a^{{\downarrow \uparrow }_D})$. Furthermore, since $a\notin I_f$, we have that $C=(a^{\downarrow },a^{\downarrow \uparrow })\in M_F(A,B,R)$ by Theorem 1. □

Notice that $a_1$ in Example 3 is an unnecessary attribute, which is the reason why $C_3$ is not a meet-irreducible element of the original concept lattice. Hence, as a consequence of the previous results, Theorem 4 can be rewritten as follows.

Theorem 5.

Given a context $(A,B,R)$, a subset of attributes $D\subseteq A\backslash I_f$, an equivalence class ${\left[C\right]}_D$ with $C\in \mathcal{C}(A,B,R)$, of the induced equivalence relation, and the concept $C_m$, then $C_m\notin {\left[C\right]}_D$ if and only if there exists a concept $C^{*}\in M_F(A,B,R)$ in a meet-irreducible decomposition $\{C_j\in M_F(A,B,R)\mid j\in J\}$ of $C_m$, such that $C^{*}=(a^{*\downarrow },a^{*\downarrow \uparrow })$ with $a^{*}\in D$ and $C_M\nleqq C^{*}$.

Proof. 

The proof straightforwardly holds from Corollary 2 and Proposition 9. □

Therefore, if the subset $D\subseteq A$ contains no unnecessary attribute, which is the case of the reducts in FCA [1,26], the characterization is mainly based on the concepts of the original concept lattice instead of Theorem 4. This fact simplifies the detection of lattices whose equivalence classes of an attribute reduction are not convex sublattices of the original concept lattice. Moreover, this result also improves Proposition 4, showing that $D\subseteq A\backslash I_f$ must be included in the hypothesis of this proposition in order to obtain the equivalence.

Thus, the previous results and examples have a relevant interest for the application of local congruences, since they characterize the cases when the classes are not sublattices [36,39] and, so, what classes are affected when a local congruence is applied after an attribute reduction mechanism. In particular, we can determine the kind of lattices for which, after applying any attribute reduction, we obtain equivalence classes that are convex sublattices, that is for any class of any attribute reduction, the concept $C_m$ belongs to the class. Based on these results, different particular cases are analyzed next.

Example 4.

The simplest non-linear concept lattice satisfying that “$C_m\in {\left[C\right]}_D$, for every class ${\left[C\right]}_D$ and attribute reduction $D\subseteq A$” is the one associated with the lattice ${\mathcal{D}}_1$, which is also denoted as $M_2$ [44] (left side of Figure 4) and without unnecessary attributes. If ${\left[C\right]}_D$ is a singleton, then clearly, $C_m\in {\left[C\right]}_D$. Otherwise, the only case in which ${\left[C\right]}_D$ does not contain $C_m$ is when D implies that ${\left[C\right]}_D=\{C_M,C_1,C_2\}$. In this case, all meet-irreducible concepts in the decomposition of $C_m$ belong to the class ${\left[C\right]}_D$, and by Theorem 3, we obtain that there exists $a\in D$, such that ${\left[C_m\right]}_D={\left[(a^{\downarrow },a^{\downarrow \uparrow })\right]}_D$, which implies in this particular case that $C_m=(a^{\downarrow },a^{\downarrow \uparrow })$. Thus, by Proposition 8, we have that $a\in I_f$, which contradicts the hypothesis.

The concatenation of this lattice (right side of Figure 4) also satisfies this statement as the following result shows.

Proposition 10.

Given a context $(A,B,R)$, whose concept lattice is isomorphic to $D_n$, with $n\in \mathbb{N}$, $D\subseteq A\backslash I_f$, and a class ${\left[C\right]}_D$, we have that $C_m\in {\left[C\right]}_D$.

Proof. 

Let us consider a context $(A,B,R)$ whose associated concept lattice is isomorphic to $D_n$, with $n\in \mathbb{N}$. In addition, let us consider a subset of attributes $D\subseteq A$, a concept $C\in \mathcal{C}(A,B,R)$, and the equivalence class ${\left[C\right]}_D$ of the induced equivalence relation.

If ${\left[C\right]}_D$ is a singleton, then clearly, $C_m\in {\left[C\right]}_D$. Hence, we assume that ${\left[C\right]}_D$ is not a singleton. Since, by Proposition 8, $C_m$ cannot be a meet-irreducible concept, we have that all meet-irreducible concepts in the decomposition of $C_m$ belong to the class ${\left[C\right]}_D$, because of the shape of this lattice. Therefore, by Theorem 3, we have that ${\left[C_m\right]}_D={\left[(a^{\downarrow },a^{\downarrow \uparrow })\right]}_D$, with $a\in D$ and $a\notin \mathfrak{I}\left(C\right)$. If $C_m=(a^{\downarrow },a^{\downarrow \uparrow })$, then by Proposition 8, we obtain that $a\in I_f$, which leads us to a contradiction. Otherwise, there exists a concept $C^{*}$ such that $C_m<C^{*}=(a^{\downarrow },a^{\downarrow \uparrow })$ and $C^{*}\notin {\left[C\right]}_D$. As a consequence, by the shape of $D_n$, $C^{*}$ must be a meet-irreducible concept in the meet-irreducible decomposition of $C_m$. Thus, we obtain a contradiction with the fact that all meet-irreducible concepts in the decomposition of $C_m$ belong to the class ${\left[C\right]}_D$. □

The following example shows that the basic non-distributive lattices $M_3$ and $N_5$ do not satisfy the previous property.

Example 5.

We consider a context $(A,B,R)$, where the Hasse diagram of its concept lattice $\mathcal{C}(A,B,R)$ is depicted on the left side of Figure 5, which is isomorphic to $M_3$, and it has no unnecessary attribute. If we carry out any attribute reduction on this particular context, we cannot ensure that every induced equivalence class obtained by the reduction is a convex sublattice. For instance, we consider the subset of attributes $D_{M_3}=\left\{a_3\right\}$, and therefore, the induced partition obtained by this attribute reduction is the Venn diagram depicted on the right side of Figure 5.

We can notice that the infimum concept $C_0$ of the class ${\left[C_4\right]}_D=\{C_1,C_2,C_4\}$ does not belong to the class since there is a concept $C_3$ such that $C_3=(a_3^{\downarrow },a_3^{\downarrow \uparrow })$, with $a_3\in D$, $C_m\le C_3$ and $C_M\nleqq C_3$, that is Statement 2 of Corollary 1 is satisfied.

A similar case arises when a context $(A,B,R)$, with concept lattice $\mathcal{C}(A,B,R)$ isomorphic to $N_5$ (left side of Figure 6) and without unnecessary attributes, is considered.

If we consider the singleton $D_{N_5}=\left\{a_1\right\}$, we obtain the partition shown on the right side of Figure 6. In this case, Statement 2 of Corollary 1 also holds, because there is a concept $C_1$, such that $C_1=(a_1^{\downarrow },a_1^{\downarrow \uparrow })$ with $a_1\in D$, $C_m\le C_1$, and $C_M\nleqq C_1$. Thus, $C_m=C_0\notin {\left[C_4\right]}_D=\{C_2,C_3,C_4\}$.

Finally, we prove that, in general, every distributive lattice satisfies the property.

Theorem 6.

Given a context $(A,B,R)$, whose concept lattice is isomorphic to a distributive lattice, $D\subseteq A\backslash I_f$, and a class ${\left[C\right]}_D$, we have that $C_m\in {\left[C\right]}_D$.

Proof. 

We proceed by reduction ad absurdum. Hence, we assume that $C_m\notin {\left[C\right]}_D$, and we get a contradiction.

From $C_m\notin {\left[C\right]}_D$, by Proposition 7, we have that there exists $a\in D$, such that $a\in \mathfrak{I}\left(C_m\right)$ and $a\notin \mathfrak{I}\left(C\right)$. Since $a\notin I_f$, by Proposition 8, there exists a concept $C^{*}$ such that $C_m\le C^{*}=(a^{\downarrow },a^{\downarrow \uparrow })$ and $C^{*}\notin {\left[C\right]}_D$, which must be meet-irreducible, because otherwise, $a\in I_f$.

Moreover, by the definition of $C_m$, we have that:

$$C_m=\underset{C_i\in {\left[C\right]}_D}{\bigwedge }{C}_i=\underset{j\in J}{\bigwedge }{C}_j$$

where $\{C_j\in M_F(A,B,R)\mid j\in J\}$ is the unique meet-irreducible decomposition of $C_m$. The uniqueness arises because the concept lattice is distributive. Hence, in particular, the concept $C^{*}$ belongs to this decomposition. Therefore, by Proposition 5, there exists $C_i\in {\left[C\right]}_D$, such that $C_i\le C^{*}$, which implies that:

$$a\in \mathfrak{I}{\left(C^{*}\right)}^{{\downarrow \uparrow }_D}\subseteq \mathfrak{I}{\left(C_i\right)}^{{\downarrow \uparrow }_D}=\mathfrak{I}{\left(C\right)}^{{\downarrow \uparrow }_D}$$

which contradicts that $a\notin \mathfrak{I}\left(C\right)$. □

This result and the previous example are very interesting since they characterize the concept lattices providing convex sublattices for every attribute reduction. In addition, when the concept lattice is not distributive, we highlighted that many possibilities exist such that an attribute reduction provides equivalent classes, which are not sublattices of the original one. Moreover, Theorem 6 holds when the attribute reduction does not contain unnecessary attributes, as in FCA. If the reduction is given by another mechanism, such as based on the rough set theory philosophy [35,42,43], we can obtain classes that are not sublattices, as Example 3 shows. These facts also reinforce the necessity of studying mechanisms to lightly modify the equivalence relation given by the reduction in order to ensure that the classes are convex sublattices, as the new notion of local congruence [38,45] does.

4. Conclusions and Future Work

In this paper, we improve the results presented in [39], giving a characterization of the infimum of the elements belonging to a non-singleton class induced by an attribute reduction. Furthermore, we also found the characterization of these infimum elements when the considered attribute reduction does not contain unnecessary attributes, which is of special interest in FCA since attribute reductions usually discard this kind of attribute. We also introduced other interesting results in this framework. For example, we proved that the equivalence classes, induced by an attribute reduction on a distributive concept lattice, always have the structure of a convex sublattice. All the theoretical development carried out in this paper has a direct impact on the theory of local congruences [38].

In the future, we will study sufficient conditions on a (fuzzy) context in order to ensure that its concept lattice is distributive. This is an interesting problem, which has already attracted the attention of other researchers [46]. Moreover, the introduced results will be applied to real cases, such as the ones obtained from the COST Action DigForASP, which is focused on the application of artificial intelligence and automatic reasoning tools to digital forensics.