# Reduction of Neighborhood-Based Generalized Rough Sets

Authors: Zhaohao Wang; Lan Shu; Xiuyong Ding
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

Rough set theory is a powerful tool for dealing with uncertainty, granularity, and incompleteness of knowledge in information systems. This paper discusses five types of existing neighborhood-based generalized rough sets. The concepts of minimal neighborhood description and maximal neighborhood description of an element are defined, and by means of the two concepts, the properties and structures of the third and the fourth types of neighborhood-based rough sets are deeply explored. Furthermore, we systematically study the covering reduction of the third and the fourth types of
neighborhood-based rough sets in terms of the two concepts. Finally, two open problems proposed by Yun et al. (2011) are solved.


---

## Body

## 1. Introduction

Rough set theory was first proposed by Pawlak [1] for dealing with vagueness and granularity in information systems. It has been successfully applied to process control, economics, medical diagnosis, biochemistry, environmental science, biology, chemistry, psychology, conflict analysis, and other fields [2–10]. The further investigation into rough set theory and its extension will find new applications and new theories [11].The classical rough set theory is based on equivalence relation. However, equivalence relation imposes restrictions and limitations on many applications [12–15]. Zakowski then established the covering-based rough set theory by exploiting coverings of a universe [16]. The covering generalized rough sets are an improvement of traditional rough set model to deal with more complex practical problems which the traditional one cannot handle. For covering models, two important theoretical issues must be explored. The first one is to present reasonable definitions of set approximations, and the second one is to develop reasonable algorithms for attribute reduct. The concept of attribute reduct can be viewed as the strongest and the most important result in rough set theory to distinguish itself from other theories. However, the current processes covering generalized rough sets mainly focus on constructing approximation operations [16–24]. Little attention has been paid to attribute reduction of covering generalized rough sets [14, 19, 25]. In this paper, five types of special covering generalized rough sets, that is, neighborhood-based generalized rough sets [24, 26, 27] are elaborated, and the covering reduction is also examined and discussed in detail.Zhu and Wang investigated the covering reduction of the first type of generalized rough sets [14]. Yang and Li constructed a unified reduction theory for the first, the second, and the fifth types of generalized rough sets [25]. This paper establishes the reduction theory for the third and the fourth types of neighborhood-based generalized rough sets in terms of the new concepts defined by us. This newly proposed theory can reduce redundant elements in a covering and then find the minimal coverings that induce the same neighborhood-based lower and upper approximation.The remainder of this paper is organized as follows. In Section2, we review the relevant concepts and properties of generalized rough sets. Section 3 defines the concepts of minimal neighborhood description and maximal neighborhood description related to an element, and the new characterizations of the third and the fourth types of neighborhood-based rough sets are given by means of the two concepts. In Section 4, we study the reduction issues of the third and the fourth types of neighborhood-based rough sets. In Section 5, two open problems proposed by Yun et al. in [28] are solved. This paper concludes in Section 6.


## 2. Preliminaries

In this section, we will briefly review basic concepts and results of the generalized rough sets. LetU be a nonempty set and X⊆U. In this paper, we denote by ~X the complement of X.Definition 2.1 ([17] Covering).
LetU be a universe of discourse and 𝒞 a family of subsets of U. If no subsets in 𝒞 is empty, and ∪𝒞=U,𝒞 is called a covering of U.It is clear that a partition ofU is a covering of U, so the concept of a covering is an extension of the concept of a partition. In the following discussion, unless stated to the contrary, the coverings are considered to be finite, that is, coverings consist of a finite number of sets in them.Definition 2.2 ([17] Covering approximation space).
LetU be a nonempty set and 𝒞 a covering of U. The pair (U,𝒞) is called a covering approximation space.Definition 2.3 ([17], Neighborhood).
Let𝒞 be a covering of U and x∈U.N𝒞(x)=∩{K∈𝒞∣x∈K} is called the neighborhood of x. Generally, we omit the subscript 𝒞 when there is no confusion.By the above Definition, it is easy to see that for allu∈N(x), N(u)⊆N(x) and for all x∈U, x∈N(x).In this paper, we consider five pairs of dual approximation operators defined by means of neighborhoods.Definition 2.4 ([24] Neighborhood-based approximation operations).
Let(U,𝒞) be a covering approximation space. The five types of neighborhood-based approximation operations are defined as follows: for any X⊆U,(1)
𝒞1̲(X)=∪{K∈𝒞∣K⊆X}, 𝒞1¯(X)=~𝒞1̲(~X)=~(∪{K∈𝒞∣K⊆~X}),(2)
𝒞2̲(X)={x∈U∣N(x)⊆X}, 𝒞2¯(X)={x∈U∣N(x)∩X≠∅},(3)
𝒞3̲(X)={x∈U∣∃u(u∈N(x)∧N(u)⊆X)},𝒞3¯(X)={x∈U∣ for all u(u∈N(x)→N(u)∩X≠∅)},(4)
𝒞4̲(X)={x∈U∣for all u(x∈N(u)→N(u)⊆X)}, 𝒞4¯(X)=∪{N(x)∣x∈U∧N(x)∩X≠∅},(5)
𝒞5̲(X)={x∈U∣ for all u(x∈N(u)→u∈X)}, 𝒞5¯(X)=∪{N(x)∣x∈X},
𝒞1̲, 𝒞2̲, 𝒞3̲, 𝒞4̲, and 𝒞5̲ are called the first, the second, the third, the fourth, and the fifth neighborhood-based lower approximation operations with respect to 𝒞, respectively. 𝒞1¯, 𝒞2¯, 𝒞3¯, 𝒞4¯, and 𝒞5¯ are called the first, the second, the third, the fourth, and the fifth neighborhood-based upper approximation operations with respect to 𝒞, respectively.This paper is concerned with the list of five definitions of approximations (Definition2.4). In fact, the above definition can be extended. For definitions of dual approximations and many other approximations look at [29].Note 1.
In [24], 𝒞1¯(X) is denoted by ∩{~K∣K∈𝒞,K∩X=∅}, that is, 𝒞1¯(X)=∩{~K∣K∈𝒞,K∩X=∅}. This is not accurate. For example, let U={x1,x2,x3}, C1={x1,x2}, C2={x3}, and 𝒞={C1,C2}. Clearly, 𝒞 is a covering of U and N(x1)={x1,x2}=N(x2) and N(x3)={x3}. Taking X={x1,x3}, since C1∩X≠∅ and C2∩X≠∅, it follows that ∩{~K∣K∈𝒞,K∩X=∅}=∅. However, it is easy to see that ~𝒞1̲(~X)=U. Hence, 𝒞1¯(X)≠~𝒞1̲(~X). This contradicts the fact that 𝒞1¯ and 𝒞1̲ are dual with each other. In above definition, we denote 𝒞1¯(X) by ~(∪{K∈𝒞∣K⊆~X}).


## 3. Minimal Neighborhood Description and Maximal Neighborhood Description

In this section, we define the concepts of minimal neighborhood description and maximal neighborhood description of an element. And we show that the two notions play essential roles in the studies of neighborhood-based rough sets.Now we give the definitions of minimal neighborhood description and maximal neighborhood description related to an element.Definition 3.1 (Minimal neighborhood description).
Let(U,𝒞) be a covering approximation space and x∈U. The family of sets
(3.1)NmidC(x)={N(u)∣u∈N(x)∧(forally∈U∧N(y)⊆N(u)⟹N(y)=N(u))}
is called the minimal neighborhood description of the element x. When there is no confusion, we omit the subscript 𝒞.By above definition, it is easy to see that every element inNmid(x) is a minimal neighborhood contained in N(x).Definition 3.2 (Maximal neighborhood description).
Let(U,𝒞) be a covering approximation space and x∈U. The family of sets
(3.2)NmadC(x)={N(u)∣x∈N(u)∧(forally∈U∧N(u)⊆N(y)⟹N(u)=N(y))}
is called the maximal neighborhood description of the element x. When there is no confusion, we omit the subscript 𝒞.By above definition, it is easy to see that every element inNmad(x) is a maximal neighborhood containing x.In order to describe an object, we need only the essential characteristics related to this object, not all the characteristics for this object. That are the purposes of the minimal neighborhood description and the maximal neighborhood description concepts.For better understanding of Definitions3.1 and 3.2, we illustrate them by the following example.Example 3.3.
LetU={x1,x2,x3,x4}, C1={x1}, C2={x2}, C3={x1,x2,x3}, C4={x1,x2,x4}, and 𝒞={C1,C2,C3,C4}. Clearly, 𝒞 is a covering of U. It is easy to check that N(x1)={x1}, N(x2)={x2}, N(x3)={x1,x2,x3}, and N(x4)={x1,x2,x4}. By Definitions 3.1 and 3.2, we can get that Nmid(x1)={N(x1)}, Nmid(x2)={N(x2)}, Nmid(x3)={N(x1),N(x2)}=Nmid(x4) and Nmad(x1)={N(x3),N(x4)}=Nmad(x2), Nmad(x3)={N(x3)}, and Nmad(x4)={N(x4)}.Remark 3.4.
Based on the above analysis, we know that every element inNmid𝒞(x) is a neighborhood of covering approximation space (U,𝒞). Hence, for convenience, in this paper, we may use for all N𝒞(u)∈Nmid𝒞(x) to express any element belonging to Nmid𝒞(x). Similarly, we may use for all N𝒞(u)∈Nmad𝒞(x) to express any element belonging to Nmad𝒞(x).


### 3.1. The Third Type of Neighborhood-Based Rough Sets and the Minimal Neighborhood Description

In the following, we will employ the concept of minimal neighborhood description to characterize the third type of neighborhood-based rough sets. Firstly, we introduce a lemma.Lemma 3.5.
Let(U,𝒞) be a covering approximation space and  x∈U. Then  for allu∈N(x), there exists  N(z)∈Nmid(x) such that  N(z)⊆N(u).Proof.
Since𝒞 is a finite covering of U, it follows from Definition 2.3 that the set {N(u)∣u∈U} has only finite elements. We will use this fact to prove the lemma.
Letu∈N(x). Then N(u)⊆N(x). Assume that for all N(z)∈Nmid(x), N(z)⊈N(u). Then N(u)∉Nmid(x), hence by Definition 3.1, ∃u1∈U, N(u1)⊂N(u). By N(u1)⊂N(u) and the assumption, we have N(u1)∉Nmid(x). Clearly u1∈N(x), so again by Definition 3.1, ∃u2∈U, N(u2)⊂N(u1). Hence N(u2)⊆N(u). By the assumption, N(u2)∉Nmid(x). Clearly, u2∈N(x), so again by Definition 3.1, ∃u3∈U, N(u3)⊂N(u2)⋯. Continue in this way, we have an infinite sequence N(u),N(u1),N(u2),…,N(um),… in (U,𝒞) such that N(u)⊃N(u1)⊃N(u2)⊃⋯⊃N(um)⊃⋯. But it is impossible since the set {N(u)∣u∈U} has only finite elements. This completes the proof.Remark 3.6.
Since for allx∈U, x∈N(x), it follows from Lemma 3.5 that there exists N(z)∈Nmid(x) such that N(z)⊆N(x). This implies that for all x∈U, Nmid(x)≠∅.Theorem 3.7.
Let(U,𝒞) be a covering approximation space. Then for  X⊆U,  𝒞3̲(X)={x∈U∣∃N(u)∈Nmid(x),N(u)⊆X},  𝒞3¯(X)={x∈U∣for allN(u)∈Nmid(x),N(u)∩X≠∅}.Proof.
LetX⊆U. We first show that 𝒞3̲(X)={x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. For all x∈𝒞3̲(X), by the part (3) of Definition 2.4, we have that ∃u∈N(x), N(u)⊆X. By Lemma 3.5, there exists N(z)∈Nmid(x) such that N(z)⊆N(u). This implies that  N(z)⊆X. It follows that x∈{x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. Thus 𝒞3̲(X)⊆{x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. On the other hand, by Definitions 3.1 and 2.4, it is obvious that 𝒞3̲(X)⊇{x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. Hence 𝒞3̲(X)={x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}.
We have proved that𝒞3̲(X)={x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. By Definition 2.4, we know that 𝒞3̲ and 𝒞3¯ are dual with each other. Thus 𝒞3¯(X)=~𝒞3̲(~X)=~{x∈U∣∃N(u)∈Nmid(x),N(u)⊆~X}=~{x∈U∣∃N(u)∈Nmid(x),N(u)∩X=∅}={x∈U∣ for all N(u)∈Nmid(x),N(u)∩X≠∅}, that is, 𝒞3¯(X)={x∈U∣ for all N(u)∈Nmid(x),N(u)∩X≠∅}.The above theorem establishes the relationship between the third type of neighborhood-based rough sets and the notion of minimal neighborhood description. In order to study further the third type of neighborhood-based rough sets, we will explore the properties of minimal neighborhood description.Proposition 3.8.
Let(U,𝒞) be a covering approximation space and  x∈U. Then  for all N(u)∈Nmid(x),  N(u)⊆N(x).Proof.
For allN(u)∈Nmid(x), by Definition 3.1, it is clear that u∈N(x). Thus by Definition 2.3, we conclude that N(u)⊆N(x).Proposition 3.9.
Let(U,𝒞) be a covering approximation space,  x∈U and  N(u)∈Nmid(x). Then  for all z∈N(u),  N(u)=N(z).Proof.
Letz∈N(u). Then by Definition 2.3, we have that N(z)⊆N(u). By N(u)∈Nmid(x) and Definition 3.1, it is clear that N(u)=N(z).The above proposition shows that every element inNmid(x) is a minimal one.Proposition 3.10.
Let(U,𝒞) be a covering approximation space,  x∈U and  N(u)∈Nmid(x). If  u∈N(z) for  z∈U, then  N(u)∈Nmid(z).Proof.
Letz∈U and u∈N(z). Suppose that N(u)∉Nmid(z). Then by Definition 3.1, we have that there exists y∈U such that N(y)⊂N(u). Thus y∈N(u). By N(u)∈Nmid(x) and Proposition 3.9, this implies that N(y)=N(u), which contradicts the fact that N(y)⊂N(u). Hence N(u)∈Nmid(z).Proposition 3.11.
Let(U,𝒞) be a covering approximation space and  x∈U. Then  for all N(u)∈Nmid(x),  Nmid(u)={N(u)}.Proof.
LetN(u)∈Nmid(x). Clearly, u∈N(u), it follows from Proposition 3.10 that N(u)∈Nmid(u) and so {N(u)}⊆Nmid(u). On the other hand, for all N(z)∈Nmid(u), by Proposition 3.8, we conclude that N(z)⊆N(u) and so z∈N(u). It follows from Proposition 3.9 that N(z)=N(u) and thus N(z)∈{N(u)}. Hence Nmid(u)⊆{N(u)}. In summary, Nmid(u)={N(u)}.In the following, we will use the above properties to study the third type of neighborhood-based generalized rough sets.The following example shows that two distinct coverings can generate the same neighborhood-based lower and upper approximation (the third type of neighborhood-based rough sets).Example 3.12 (Two different coverings generate the same the third type of neighborhood-based rough sets).
LetU={x,y,z}, C1={x}, C2={x,y}, C3={x,z}, C4={x,y,z}, ℬ={C1,C4}, and 𝒞={C1,C2,C3,C4}. Clearly, ℬ and 𝒞 are two different coverings of U. Then by Definition 2.3, we can get that Nℬ(x)={x}, Nℬ(y)={x,y,z}=Nℬ(z) and N𝒞(x)={x}, N𝒞(y)={x,y}, N𝒞(z)={x,z}. By Definition 3.1, it is easy to check that Nmidℬ(x)=Nmidℬ(y)=Nmidℬ(z)={Nℬ(x)}={{x}} and Nmid𝒞(x)=Nmid𝒞(y)=Nmid𝒞(z)={N𝒞(x)}={{x}}. Hence Nmidℬ(x)=Nmid𝒞(x), Nmidℬ(y)=Nmid𝒞(y), and Nmidℬ(z)=Nmid𝒞(z). Thus by Theorem 3.7, it is easy to see that for all X⊆U, ℬ3̲(X)=𝒞3̲(X), and ℬ3¯(X)=𝒞3¯(X).Now we present the conditions under which two coverings generate the same the third type of neighborhood-based rough sets.Theorem 3.13.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then for all  X⊆U,  ℬ3̲(X)=𝒞3̲(X) and  ℬ3¯(X)=𝒞3¯(X) if and only if  for all x∈U,  Nmidℬ(x)=Nmid𝒞(x).In order to prove the theorem, we first introduce a lemma.Lemma 3.14.
Let(U,𝒞) be a covering approximation space. Then  for ally∈U,
(3.3)C3¯({y})={x∈U∣Nmid(x)={N(y)}}.Proof.
By Theorem3.7, we have that 𝒞3¯({y})={x∈U∣for allN(u)∈Nmid(x),N(u)∩{y}≠∅}={x∈U∣for allN(u)∈Nmid(x),y∈N(u)}. By Proposition 3.9, we conclude that {x∈U∣for allN(u)∈Nmid(x),y∈N(u)}={x∈U∣for allN(u)∈Nmid(x), and N(y)=N(u)}={x∈U∣Nmid(x)={N(y)}}. Thus 𝒞3¯({y})={x∈U∣Nmid(x)={N(y)}}.Now we prove our theorem.Proof.
The sufficiency follows directly from Theorem3.7.
Conversely, letx∈U. For all Nℬ(u)∈Nmidℬ(x).(i)
We first show thatN𝒞(u)∈Nmid𝒞(u). By Proposition 3.11, we have that Nmidℬ(u)={Nℬ(u)}. Thus by Lemma 3.14, u∈ℬ3¯({u}). Applying the condition for allX⊆U, ℬ3¯(X)=𝒞3¯(X), we can have that ℬ3¯({u})=𝒞3¯({u}). Thus u∈𝒞3¯({u}). It follows from Lemma 3.14 that Nmid𝒞(u)={N𝒞(u)}. Therefore, N𝒞(u)∈Nmid𝒞(u).(ii)
We will show thatNℬ(u)=N𝒞(u). For all v∈Nℬ(u), by Proposition 3.9, we have that Nℬ(v)=Nℬ(u). By Lemma 3.14, this implies that ℬ3¯({v})=ℬ3¯({u}). In addition, applying the condition for allX⊆U, ℬ3¯(X)=𝒞3¯(X), we can get that ℬ3¯({u})=𝒞3¯({u}) and ℬ3¯({v})=𝒞3¯({v}). It follows that 𝒞3¯({v})=𝒞3¯({u}). By (i) and Proposition 3.11, Nmid𝒞(u)={N𝒞(u)}. Thus by Lemma 3.14, we have that u∈𝒞3¯({u}) and so u∈𝒞3¯({v}). According to Lemma 3.14, this implies that Nmid𝒞(u)={N𝒞(v)}. It follows from Proposition 3.8 that N𝒞(v)⊆N𝒞(u) and thus v∈N𝒞(u). Therefore, Nℬ(u)⊆N𝒞(u). On the other hand, the proof of Nℬ(u)⊇N𝒞(u) is similar to that of Nℬ(u)⊆N𝒞(u). Therefore Nℬ(u)=N𝒞(u).(iii)
We will show thatN𝒞(u)∈Nmid𝒞(x). By the condition, we have that ℬ3̲(Nℬ(u))=𝒞3̲(Nℬ(u)). By (ii), we have that N𝒞(u)=Nℬ(u). Thus ℬ3̲(Nℬ(u))=𝒞3̲(N𝒞(u)). By Theorem 3.7, it is clear that x∈ℬ3̲(Nℬ(u)). Thus x∈𝒞3̲(N𝒞(u)). By Theorem 3.7, this implies that ∃N𝒞(z)∈Nmid𝒞(x) such that N𝒞(z)⊆N𝒞(u) and so z∈N𝒞(u). By (i) and Proposition 3.9, we can conclude that N𝒞(z)=N𝒞(u). This implies that N𝒞(u)∈Nmid𝒞(x).
By (ii) and (iii), we have thatNℬ(u)∈Nmid𝒞(x). Thus Nmidℬ(x)⊆Nmid𝒞(x). In the same way, we can prove that Nmidℬ(x)⊇Nmid𝒞(x). It follows that Nmidℬ(x)=Nmid𝒞(x). This completes the proof of the necessity.For the covering𝒞 of U, since the lower approximation 𝒞3̲ and the upper approximation 𝒞3¯ are dual, they determine each other. That is to say, for two coverings ℬ and 𝒞, ℬ3̲=𝒞3̲ if and only if ℬ3¯=𝒞3¯. From the above analysis and Theorem 3.13, we can obtain the following two corollaries.Corollary 3.15.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then  for allX⊆U,  ℬ3̲(X)=𝒞3̲(X) if and only if  for ally∈U,  Nmidℬ(y)=Nmid𝒞(y).Corollary 3.16.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then  for allX⊆U,  ℬ3¯(X)=𝒞3¯(X) if and only if  for ally∈U,  Nmidℬ(y)=Nmid𝒞(y).Theorem3.13 is an important result for studying the covering reduction of the third type of neighborhood-based rough sets. In Section 4.1, we will present the concept of reduct based on this theorem for the third type of rough set model.


### 3.2. The Fourth Type of Neighborhood-Based Rough Sets and the Maximal Neighborhood Description

In this subsection, we will study the relationship between the fourth type of neighborhood-based rough sets and the notion of maximal neighborhood description. For this purpose, we first explore the properties of maximal neighborhood description.Proposition 3.17.
Let(U,𝒞) be a covering approximation space and  x∈U. Then  for allN(u)∈Nmad(x),  N(x)⊆N(u).Proof.
LetN(u)∈Nmad(x). By Definition 3.2, we have that x∈N(u). Thus by Definition 2.3, N(x)⊆N(u).Proposition 3.18.
Let(U,𝒞) be a covering approximation space and  x,y∈U. If  x∈N(y), then there exists  N(u)∈Nmad(x) such that  N(y)⊆N(u).Proof.
Since𝒞 is a finite covering of U, it follows from Definition 2.3 that the set {N(u)∣u∈U} has only finite elements. We will use this fact to prove the proposition.
Letx∈N(y). Assume that for allN(u)∈Nmad(x), N(y)⊈N(u). Then N(y)∉Nmad(x), hence by Definition 3.2, ∃u1∈U, N(y)⊂N(u1). By the assumption, we have that N(u1)∉Nmad(x). Clearly, x∈N(u1), so again by Definition 3.2, ∃u2∈U, N(u1)⊂N(u2). Thus N(y)⊆N(u2). By the assumption, N(u2)∉Nmad(x). Clearly, x∈N(u2), so again by Definition 3.2, ∃u3∈U, N(u2)⊂N(u3)⋯. Continue in this way, we have an infinite sequence N(y),N(u1),N(u2),…,N(um),… in (U,𝒞) such that N(y)⊂N(u1)⊂N(u2)⊂⋯⊂N(um)⊂⋯. But it is impossible since the set {N(u)∣u∈U} has only finite elements. This completes the proof.By the above proposition, we can easily conclude the following result.Corollary 3.19.
Let(U,𝒞) be a covering approximation space and  x,y∈U. If  x∈N(y), then  N(y)⊆∪Nmad(x).Remark 3.20.
Sincefor allx∈U, x∈N(x), it follows from Proposition 3.18 that there exists N(u)∈Nmad(x) such that N(x)⊆N(u). This implies that for allx∈U, Nmad(x)≠∅.Proposition 3.21.
Let(U,𝒞) be a covering approximation space,  x∈U, and  N(u)∈Nmad(x). If  y∈N(u) then  N(u)∈Nmad(y).Proof.
Suppose thatN(u)∉Nmad(y). Then by y∈N(u) and Definition 3.2, there exists y0∈U such that N(u)⊂N(y0), which contradicts with N(u)∈Nmad(x). Thus N(u)∈Nmad(y).Now we use the concept of maximal neighborhood description to characterize the fourth type of neighborhood-based rough sets.Theorem 3.22.
Let(U,𝒞) be a covering approximation space. Then for  X⊆U,
(3.4)C4̲(X)={x∈U∣∪Nmad(x)⊆X},C4¯(X)=∪{∪Nmad(x)∣x∈X}.Proof.
LetX⊆U. We first show that 𝒞4̲(X)={x∈U∣∪Nmad(x)⊆X}. For all x∈𝒞4̲(X), we will prove that x∈{x∈U∣∪Nmad(x)⊆X}. For allN(u)∈Nmad(x), by Definition 3.2, x∈N(u). Since x∈𝒞4̲(X), it follows from the part (4) of Definition 2.4 that N(u)⊆X. Thus ∪Nmad(x)⊆X. This implies that x∈{x∈U∣∪Nmad(x)⊆X}. Thus 𝒞4̲(X)⊆{x∈U∣∪Nmad(x)⊆X}. On the other hand, for all x∈{x∈U∣∪Nmad(x)⊆X}, we can get that ∪Nmad(x)⊆X. Further, for allu∈U and x∈N(u), by Corollary 3.19, we have that N(u)⊆∪Nmad(x). Thus N(u)⊆X. It follows from the part (4) of Definition 2.4 that x∈𝒞4̲(X) and so {x∈U∣∪Nmad(x)⊆X}⊆𝒞4̲(X). In summary, 𝒞4̲(X)={x∈U∣∪Nmad(x)⊆X}.
Now we show that𝒞4¯(X)=∪{∪Nmad(x)∣x∈X}. For all y∈𝒞4¯(X), by Definition 2.4, there exists z∈U such that N(z)∩X≠∅ and y∈N(z). Taking x∈N(z)∩X, by Corollary 3.19, we have that N(z)⊆∪Nmad(x) and x∈X. Thus N(z)⊆∪{∪Nmad(x)∣x∈X} and so y∈∪{∪Nmad(x)∣x∈X}. Therefore, 𝒞4¯(X)⊆∪{∪Nmad(x)∣x∈X}. On the other hand, for all y∈∪{∪Nmad(x)∣x∈X}, there exists x∈X such that y∈∪Nmad(x). Thus ∃N(u)∈Nmad(x), s.t. y∈N(u). By Definition 3.2, x∈N(u). Hence there exists N(u) such that x∈N(u)∩X≠∅ and y∈N(u). It follows from Definition 2.4 that y∈𝒞4¯(X) and so ∪{∪Nmad(x)∣x∈X}⊆𝒞4¯(X). In summary, 𝒞4¯(X)=∪{∪Nmad(x)∣x∈X}.
This completes the proof of theorem.The following example shows that two different coverings can induce the same the fourth type of neighborhood-based lower and upper approximation operations.Example 3.23 (Two different coverings generate the same the fourth type of neighborhood-based rough sets).
LetU={x1,x2,x3,x4}, C1={x1}, C2={x1,x2}, C3={x3,x4}, ℬ={C1,C2,C3}, and 𝒞={C2,C3}. Clearly, ℬ and 𝒞 are two different coverings of U. By Definition 2.3, it clear that Nℬ(x1)={x1}, Nℬ(x2)={x1,x2}, Nℬ(x3)={x3,x4}=Nℬ(x4), and N𝒞(x1)={x1,x2}=N𝒞(x2), N𝒞(x3)={x3,x4}=N𝒞(x4). It is easy to check that Nmadℬ(x1)=Nmadℬ(x2)={Nℬ(x2)}={x1,x2}, Nmadℬ(x3)=Nmadℬ(x4)={Nℬ(x3)}={x3,x4} and Nmad𝒞(x1)=Nmad𝒞(x2)={N𝒞(x2)}={x1,x2}, Nmad𝒞(x3)=Nmad𝒞(x3)={N𝒞(x4)}={x3,x4}. Thus for allx∈U, Nmadℬ(x)=Nmad𝒞(x) and so for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x). It follows by Theorem 3.22 that ℬ4̲=𝒞4̲ and ℬ4¯=𝒞4¯.In the following, we study the conditions for two coverings generating the same fourth type of neighborhood-based lower and upper approximation operations. Firstly, we present two lemmas.Lemma 3.24.
Let𝒞 be a covering of a nonempty set  U and  x,y∈U. If  N(u)∈Nmad(x) and  y∉N(u), then  u∉∪Nmad(y).Proof.
Suppose thatu∈∪Nmad(y). Then ∃N(v)∈Nmad(y), s.t. u∈N(v). Thus by Definition 2.3, N(u)⊆N(v). Since N(u)∈Nmad(x), it follows from Definition 3.2 that N(u)=N(v). By N(v)∈Nmad(y) and Definition 3.2, it is clear that y∈N(v). Thus y∈N(u), which contradicts the condition y∉N(u). Therefore, u∉∪Nmad(y).Lemma 3.25.
Letℬ and  𝒞 be two coverings of a nonempty set  U. And  ℬ and  𝒞 satisfy the condition that  for allx∈U,  ∪Nmadℬ(x)=∪Nmad𝒞(x). If for  x∈U,  N𝒞(u)∈Nmad𝒞(x),  Nℬ(v)∈Nmadℬ(x), and  N𝒞(u)⊆Nℬ(v), then  N𝒞(u)=Nℬ(v).Proof.
Suppose thatN𝒞(u)⊂Nℬ(v). Then, u∈Nℬ(v). Taking w∈Nℬ(v)-N𝒞(u), that is, w∈Nℬ(v), w∉N𝒞(u). Thus by Nℬ(v)∈Nmadℬ(x) and Proposition 3.21, we have that Nℬ(v)∈Nmadℬ(w) and so u∈∪Nmadℬ(w). On the other hand, since w∉N𝒞(u) and N𝒞(u)∈Nmad𝒞(x), it follows from Lemma 3.24 that u∉∪Nmad𝒞(w). Thus ∪Nmad𝒞(w)≠∪Nmadℬ(w), which contradicts the condition for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x). Therefore, N𝒞(u)=Nℬ(v).Now we present the conditions under which the two different coverings generate the same fourth type of neighborhood-based upper approximation operation.Theorem 3.26.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then the following assertions are equivalent: (1)
for allX⊆U, ℬ4¯(X)=𝒞4¯(X),(2)
for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x),(3)
for allx∈U, Nmadℬ(x)=Nmad𝒞(x),(4)
∪{Nmadℬ(x)∣x∈U}=∪{Nmad𝒞(x)∣x∈U}.Proof.
(1)⇒(2) for allx∈U, by Theorem 3.22, we have that ℬ4¯({x})=∪Nmadℬ(x) and 𝒞4¯({x})=∪Nmad𝒞(x). Since for allX⊆U, ℬ4¯(X)=𝒞4¯(X), it follows that ℬ4¯({x})=𝒞4¯({x}). Thus ∪Nmadℬ(x)=∪Nmad𝒞(x).
(2)⇒(1) It follows directly from Theorem 3.22.
(2)⇒(3) Let x∈U. By assertion (2), ∪Nmadℬ(x)=∪Nmad𝒞(x). Thus, for all Nℬ(u)∈Nmadℬ(x), there exists N𝒞(v)∈Nmad𝒞(x) such that u∈N𝒞(v). Suppose that Nℬ(u)≠N𝒞(v). Then by Lemma 3.25, we have that N𝒞(v)⊈Nℬ(u). Thus there exists w∈N𝒞(v) such that w∉Nℬ(u). By Proposition 3.21, w∈N𝒞(v) implies N𝒞(v)∈Nmad𝒞(w) and so u∈∪Nmad𝒞(w). In addition, by w∉Nℬ(u) and Lemma 3.24, we have that u∉∪Nmadℬ(w). Thus ∪Nmad𝒞(w)≠∪Nmadℬ(w), which is a contradiction with the assertion (2). Therefore, Nℬ(u)=N𝒞(v) and so Nℬ(u)∈Nmad𝒞(x). Thus Nmadℬ(x)⊆Nmad𝒞(x). In the same way, we can prove that Nmadℬ(x)⊇Nmad𝒞(x). Thus Nmadℬ(x)=Nmad𝒞(x).
(3)⇒(2) It is obvious.
(3)⇒(4) It is obvious.
(4)⇒(3) Let x∈U. For all Nℬ(u)∈Nmadℬ(x), clearly, Nℬ(u)∈∪{Nmadℬ(x)∣x∈U}. Since ∪{Nmadℬ(x)∣x∈U}=∪{Nmad𝒞(x)∣x∈U}, there exists N𝒞(v)∈∪{Nmad𝒞(x)∣x∈U} such that Nℬ(u)=N𝒞(v). By Nℬ(u)∈Nmadℬ(x) and Definition 3.2, we have that x∈Nℬ(u). Thus x∈N𝒞(v). Since N𝒞(v)∈∪{Nmad𝒞(x)∣x∈U}, it follows that there exists z∈U such that N𝒞(v)∈Nmad𝒞(z). Thus again by Proposition 3.21, we can have that N𝒞(v)∈Nmad𝒞(x). It follows from Nℬ(u)=N𝒞(v) that Nℬ(u)∈Nmad𝒞(x). Hence Nmadℬ(x)⊆Nmad𝒞(x). In the same way, we can prove that Nmadℬ(x)⊇Nmad𝒞(x). Thus Nmadℬ(x)=Nmad𝒞(x).For the covering𝒞 of U, since the lower approximation 𝒞4̲ and the upper approximation 𝒞4¯ are dual, they determine each other. That is, for two coverings ℬ and 𝒞, ℬ4̲=𝒞4̲ if and only if ℬ4¯=𝒞4¯. From the above analysis and Theorem 3.26, we can obtain the following results.Corollary 3.27.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then the following assertions are equivalent: (1)
for allX⊆U, ℬ4̲(X)=𝒞4̲(X),(2)
for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x),(3)
for allx∈U, Nmadℬ(x)=Nmad𝒞(x),(4)
∪{Nmadℬ(x)∣x∈U}=∪{Nmad𝒞(x)∣x∈U}.Now we present the conditions under which the two different coverings generate the same the fourth type of neighborhood-based rough sets.Theorem 3.28.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then the following assertions are equivalent: (1)
for allX⊆U, ℬ4̲(X)=𝒞4̲(X) and ℬ4¯(X)=𝒞4¯(X),(2)
for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x),(3)
for ally∈U, Nmadℬ(x)=Nmad𝒞(x),(4)
∪{Nmadℬ(x)∣x∈U}=∪{Nmad𝒞(x)∣x∈U}.Proof.
It follows directly from Theorem3.26 and Corollary 3.27.The above theorem is an important result for studying the covering reduction of the fourth type of neighborhood-based rough sets. In Section4.2, we will present the concept of reduct based on this theorem for the fourth type of rough set model.


## 3.1. The Third Type of Neighborhood-Based Rough Sets and the Minimal Neighborhood Description

In the following, we will employ the concept of minimal neighborhood description to characterize the third type of neighborhood-based rough sets. Firstly, we introduce a lemma.Lemma 3.5.
Let(U,𝒞) be a covering approximation space and  x∈U. Then  for allu∈N(x), there exists  N(z)∈Nmid(x) such that  N(z)⊆N(u).Proof.
Since𝒞 is a finite covering of U, it follows from Definition 2.3 that the set {N(u)∣u∈U} has only finite elements. We will use this fact to prove the lemma.
Letu∈N(x). Then N(u)⊆N(x). Assume that for all N(z)∈Nmid(x), N(z)⊈N(u). Then N(u)∉Nmid(x), hence by Definition 3.1, ∃u1∈U, N(u1)⊂N(u). By N(u1)⊂N(u) and the assumption, we have N(u1)∉Nmid(x). Clearly u1∈N(x), so again by Definition 3.1, ∃u2∈U, N(u2)⊂N(u1). Hence N(u2)⊆N(u). By the assumption, N(u2)∉Nmid(x). Clearly, u2∈N(x), so again by Definition 3.1, ∃u3∈U, N(u3)⊂N(u2)⋯. Continue in this way, we have an infinite sequence N(u),N(u1),N(u2),…,N(um),… in (U,𝒞) such that N(u)⊃N(u1)⊃N(u2)⊃⋯⊃N(um)⊃⋯. But it is impossible since the set {N(u)∣u∈U} has only finite elements. This completes the proof.Remark 3.6.
Since for allx∈U, x∈N(x), it follows from Lemma 3.5 that there exists N(z)∈Nmid(x) such that N(z)⊆N(x). This implies that for all x∈U, Nmid(x)≠∅.Theorem 3.7.
Let(U,𝒞) be a covering approximation space. Then for  X⊆U,  𝒞3̲(X)={x∈U∣∃N(u)∈Nmid(x),N(u)⊆X},  𝒞3¯(X)={x∈U∣for allN(u)∈Nmid(x),N(u)∩X≠∅}.Proof.
LetX⊆U. We first show that 𝒞3̲(X)={x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. For all x∈𝒞3̲(X), by the part (3) of Definition 2.4, we have that ∃u∈N(x), N(u)⊆X. By Lemma 3.5, there exists N(z)∈Nmid(x) such that N(z)⊆N(u). This implies that  N(z)⊆X. It follows that x∈{x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. Thus 𝒞3̲(X)⊆{x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. On the other hand, by Definitions 3.1 and 2.4, it is obvious that 𝒞3̲(X)⊇{x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. Hence 𝒞3̲(X)={x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}.
We have proved that𝒞3̲(X)={x∈U∣∃N(u)∈Nmid(x),N(u)⊆X}. By Definition 2.4, we know that 𝒞3̲ and 𝒞3¯ are dual with each other. Thus 𝒞3¯(X)=~𝒞3̲(~X)=~{x∈U∣∃N(u)∈Nmid(x),N(u)⊆~X}=~{x∈U∣∃N(u)∈Nmid(x),N(u)∩X=∅}={x∈U∣ for all N(u)∈Nmid(x),N(u)∩X≠∅}, that is, 𝒞3¯(X)={x∈U∣ for all N(u)∈Nmid(x),N(u)∩X≠∅}.The above theorem establishes the relationship between the third type of neighborhood-based rough sets and the notion of minimal neighborhood description. In order to study further the third type of neighborhood-based rough sets, we will explore the properties of minimal neighborhood description.Proposition 3.8.
Let(U,𝒞) be a covering approximation space and  x∈U. Then  for all N(u)∈Nmid(x),  N(u)⊆N(x).Proof.
For allN(u)∈Nmid(x), by Definition 3.1, it is clear that u∈N(x). Thus by Definition 2.3, we conclude that N(u)⊆N(x).Proposition 3.9.
Let(U,𝒞) be a covering approximation space,  x∈U and  N(u)∈Nmid(x). Then  for all z∈N(u),  N(u)=N(z).Proof.
Letz∈N(u). Then by Definition 2.3, we have that N(z)⊆N(u). By N(u)∈Nmid(x) and Definition 3.1, it is clear that N(u)=N(z).The above proposition shows that every element inNmid(x) is a minimal one.Proposition 3.10.
Let(U,𝒞) be a covering approximation space,  x∈U and  N(u)∈Nmid(x). If  u∈N(z) for  z∈U, then  N(u)∈Nmid(z).Proof.
Letz∈U and u∈N(z). Suppose that N(u)∉Nmid(z). Then by Definition 3.1, we have that there exists y∈U such that N(y)⊂N(u). Thus y∈N(u). By N(u)∈Nmid(x) and Proposition 3.9, this implies that N(y)=N(u), which contradicts the fact that N(y)⊂N(u). Hence N(u)∈Nmid(z).Proposition 3.11.
Let(U,𝒞) be a covering approximation space and  x∈U. Then  for all N(u)∈Nmid(x),  Nmid(u)={N(u)}.Proof.
LetN(u)∈Nmid(x). Clearly, u∈N(u), it follows from Proposition 3.10 that N(u)∈Nmid(u) and so {N(u)}⊆Nmid(u). On the other hand, for all N(z)∈Nmid(u), by Proposition 3.8, we conclude that N(z)⊆N(u) and so z∈N(u). It follows from Proposition 3.9 that N(z)=N(u) and thus N(z)∈{N(u)}. Hence Nmid(u)⊆{N(u)}. In summary, Nmid(u)={N(u)}.In the following, we will use the above properties to study the third type of neighborhood-based generalized rough sets.The following example shows that two distinct coverings can generate the same neighborhood-based lower and upper approximation (the third type of neighborhood-based rough sets).Example 3.12 (Two different coverings generate the same the third type of neighborhood-based rough sets).
LetU={x,y,z}, C1={x}, C2={x,y}, C3={x,z}, C4={x,y,z}, ℬ={C1,C4}, and 𝒞={C1,C2,C3,C4}. Clearly, ℬ and 𝒞 are two different coverings of U. Then by Definition 2.3, we can get that Nℬ(x)={x}, Nℬ(y)={x,y,z}=Nℬ(z) and N𝒞(x)={x}, N𝒞(y)={x,y}, N𝒞(z)={x,z}. By Definition 3.1, it is easy to check that Nmidℬ(x)=Nmidℬ(y)=Nmidℬ(z)={Nℬ(x)}={{x}} and Nmid𝒞(x)=Nmid𝒞(y)=Nmid𝒞(z)={N𝒞(x)}={{x}}. Hence Nmidℬ(x)=Nmid𝒞(x), Nmidℬ(y)=Nmid𝒞(y), and Nmidℬ(z)=Nmid𝒞(z). Thus by Theorem 3.7, it is easy to see that for all X⊆U, ℬ3̲(X)=𝒞3̲(X), and ℬ3¯(X)=𝒞3¯(X).Now we present the conditions under which two coverings generate the same the third type of neighborhood-based rough sets.Theorem 3.13.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then for all  X⊆U,  ℬ3̲(X)=𝒞3̲(X) and  ℬ3¯(X)=𝒞3¯(X) if and only if  for all x∈U,  Nmidℬ(x)=Nmid𝒞(x).In order to prove the theorem, we first introduce a lemma.Lemma 3.14.
Let(U,𝒞) be a covering approximation space. Then  for ally∈U,
(3.3)C3¯({y})={x∈U∣Nmid(x)={N(y)}}.Proof.
By Theorem3.7, we have that 𝒞3¯({y})={x∈U∣for allN(u)∈Nmid(x),N(u)∩{y}≠∅}={x∈U∣for allN(u)∈Nmid(x),y∈N(u)}. By Proposition 3.9, we conclude that {x∈U∣for allN(u)∈Nmid(x),y∈N(u)}={x∈U∣for allN(u)∈Nmid(x), and N(y)=N(u)}={x∈U∣Nmid(x)={N(y)}}. Thus 𝒞3¯({y})={x∈U∣Nmid(x)={N(y)}}.Now we prove our theorem.Proof.
The sufficiency follows directly from Theorem3.7.
Conversely, letx∈U. For all Nℬ(u)∈Nmidℬ(x).(i)
We first show thatN𝒞(u)∈Nmid𝒞(u). By Proposition 3.11, we have that Nmidℬ(u)={Nℬ(u)}. Thus by Lemma 3.14, u∈ℬ3¯({u}). Applying the condition for allX⊆U, ℬ3¯(X)=𝒞3¯(X), we can have that ℬ3¯({u})=𝒞3¯({u}). Thus u∈𝒞3¯({u}). It follows from Lemma 3.14 that Nmid𝒞(u)={N𝒞(u)}. Therefore, N𝒞(u)∈Nmid𝒞(u).(ii)
We will show thatNℬ(u)=N𝒞(u). For all v∈Nℬ(u), by Proposition 3.9, we have that Nℬ(v)=Nℬ(u). By Lemma 3.14, this implies that ℬ3¯({v})=ℬ3¯({u}). In addition, applying the condition for allX⊆U, ℬ3¯(X)=𝒞3¯(X), we can get that ℬ3¯({u})=𝒞3¯({u}) and ℬ3¯({v})=𝒞3¯({v}). It follows that 𝒞3¯({v})=𝒞3¯({u}). By (i) and Proposition 3.11, Nmid𝒞(u)={N𝒞(u)}. Thus by Lemma 3.14, we have that u∈𝒞3¯({u}) and so u∈𝒞3¯({v}). According to Lemma 3.14, this implies that Nmid𝒞(u)={N𝒞(v)}. It follows from Proposition 3.8 that N𝒞(v)⊆N𝒞(u) and thus v∈N𝒞(u). Therefore, Nℬ(u)⊆N𝒞(u). On the other hand, the proof of Nℬ(u)⊇N𝒞(u) is similar to that of Nℬ(u)⊆N𝒞(u). Therefore Nℬ(u)=N𝒞(u).(iii)
We will show thatN𝒞(u)∈Nmid𝒞(x). By the condition, we have that ℬ3̲(Nℬ(u))=𝒞3̲(Nℬ(u)). By (ii), we have that N𝒞(u)=Nℬ(u). Thus ℬ3̲(Nℬ(u))=𝒞3̲(N𝒞(u)). By Theorem 3.7, it is clear that x∈ℬ3̲(Nℬ(u)). Thus x∈𝒞3̲(N𝒞(u)). By Theorem 3.7, this implies that ∃N𝒞(z)∈Nmid𝒞(x) such that N𝒞(z)⊆N𝒞(u) and so z∈N𝒞(u). By (i) and Proposition 3.9, we can conclude that N𝒞(z)=N𝒞(u). This implies that N𝒞(u)∈Nmid𝒞(x).
By (ii) and (iii), we have thatNℬ(u)∈Nmid𝒞(x). Thus Nmidℬ(x)⊆Nmid𝒞(x). In the same way, we can prove that Nmidℬ(x)⊇Nmid𝒞(x). It follows that Nmidℬ(x)=Nmid𝒞(x). This completes the proof of the necessity.For the covering𝒞 of U, since the lower approximation 𝒞3̲ and the upper approximation 𝒞3¯ are dual, they determine each other. That is to say, for two coverings ℬ and 𝒞, ℬ3̲=𝒞3̲ if and only if ℬ3¯=𝒞3¯. From the above analysis and Theorem 3.13, we can obtain the following two corollaries.Corollary 3.15.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then  for allX⊆U,  ℬ3̲(X)=𝒞3̲(X) if and only if  for ally∈U,  Nmidℬ(y)=Nmid𝒞(y).Corollary 3.16.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then  for allX⊆U,  ℬ3¯(X)=𝒞3¯(X) if and only if  for ally∈U,  Nmidℬ(y)=Nmid𝒞(y).Theorem3.13 is an important result for studying the covering reduction of the third type of neighborhood-based rough sets. In Section 4.1, we will present the concept of reduct based on this theorem for the third type of rough set model.


## 3.2. The Fourth Type of Neighborhood-Based Rough Sets and the Maximal Neighborhood Description

In this subsection, we will study the relationship between the fourth type of neighborhood-based rough sets and the notion of maximal neighborhood description. For this purpose, we first explore the properties of maximal neighborhood description.Proposition 3.17.
Let(U,𝒞) be a covering approximation space and  x∈U. Then  for allN(u)∈Nmad(x),  N(x)⊆N(u).Proof.
LetN(u)∈Nmad(x). By Definition 3.2, we have that x∈N(u). Thus by Definition 2.3, N(x)⊆N(u).Proposition 3.18.
Let(U,𝒞) be a covering approximation space and  x,y∈U. If  x∈N(y), then there exists  N(u)∈Nmad(x) such that  N(y)⊆N(u).Proof.
Since𝒞 is a finite covering of U, it follows from Definition 2.3 that the set {N(u)∣u∈U} has only finite elements. We will use this fact to prove the proposition.
Letx∈N(y). Assume that for allN(u)∈Nmad(x), N(y)⊈N(u). Then N(y)∉Nmad(x), hence by Definition 3.2, ∃u1∈U, N(y)⊂N(u1). By the assumption, we have that N(u1)∉Nmad(x). Clearly, x∈N(u1), so again by Definition 3.2, ∃u2∈U, N(u1)⊂N(u2). Thus N(y)⊆N(u2). By the assumption, N(u2)∉Nmad(x). Clearly, x∈N(u2), so again by Definition 3.2, ∃u3∈U, N(u2)⊂N(u3)⋯. Continue in this way, we have an infinite sequence N(y),N(u1),N(u2),…,N(um),… in (U,𝒞) such that N(y)⊂N(u1)⊂N(u2)⊂⋯⊂N(um)⊂⋯. But it is impossible since the set {N(u)∣u∈U} has only finite elements. This completes the proof.By the above proposition, we can easily conclude the following result.Corollary 3.19.
Let(U,𝒞) be a covering approximation space and  x,y∈U. If  x∈N(y), then  N(y)⊆∪Nmad(x).Remark 3.20.
Sincefor allx∈U, x∈N(x), it follows from Proposition 3.18 that there exists N(u)∈Nmad(x) such that N(x)⊆N(u). This implies that for allx∈U, Nmad(x)≠∅.Proposition 3.21.
Let(U,𝒞) be a covering approximation space,  x∈U, and  N(u)∈Nmad(x). If  y∈N(u) then  N(u)∈Nmad(y).Proof.
Suppose thatN(u)∉Nmad(y). Then by y∈N(u) and Definition 3.2, there exists y0∈U such that N(u)⊂N(y0), which contradicts with N(u)∈Nmad(x). Thus N(u)∈Nmad(y).Now we use the concept of maximal neighborhood description to characterize the fourth type of neighborhood-based rough sets.Theorem 3.22.
Let(U,𝒞) be a covering approximation space. Then for  X⊆U,
(3.4)C4̲(X)={x∈U∣∪Nmad(x)⊆X},C4¯(X)=∪{∪Nmad(x)∣x∈X}.Proof.
LetX⊆U. We first show that 𝒞4̲(X)={x∈U∣∪Nmad(x)⊆X}. For all x∈𝒞4̲(X), we will prove that x∈{x∈U∣∪Nmad(x)⊆X}. For allN(u)∈Nmad(x), by Definition 3.2, x∈N(u). Since x∈𝒞4̲(X), it follows from the part (4) of Definition 2.4 that N(u)⊆X. Thus ∪Nmad(x)⊆X. This implies that x∈{x∈U∣∪Nmad(x)⊆X}. Thus 𝒞4̲(X)⊆{x∈U∣∪Nmad(x)⊆X}. On the other hand, for all x∈{x∈U∣∪Nmad(x)⊆X}, we can get that ∪Nmad(x)⊆X. Further, for allu∈U and x∈N(u), by Corollary 3.19, we have that N(u)⊆∪Nmad(x). Thus N(u)⊆X. It follows from the part (4) of Definition 2.4 that x∈𝒞4̲(X) and so {x∈U∣∪Nmad(x)⊆X}⊆𝒞4̲(X). In summary, 𝒞4̲(X)={x∈U∣∪Nmad(x)⊆X}.
Now we show that𝒞4¯(X)=∪{∪Nmad(x)∣x∈X}. For all y∈𝒞4¯(X), by Definition 2.4, there exists z∈U such that N(z)∩X≠∅ and y∈N(z). Taking x∈N(z)∩X, by Corollary 3.19, we have that N(z)⊆∪Nmad(x) and x∈X. Thus N(z)⊆∪{∪Nmad(x)∣x∈X} and so y∈∪{∪Nmad(x)∣x∈X}. Therefore, 𝒞4¯(X)⊆∪{∪Nmad(x)∣x∈X}. On the other hand, for all y∈∪{∪Nmad(x)∣x∈X}, there exists x∈X such that y∈∪Nmad(x). Thus ∃N(u)∈Nmad(x), s.t. y∈N(u). By Definition 3.2, x∈N(u). Hence there exists N(u) such that x∈N(u)∩X≠∅ and y∈N(u). It follows from Definition 2.4 that y∈𝒞4¯(X) and so ∪{∪Nmad(x)∣x∈X}⊆𝒞4¯(X). In summary, 𝒞4¯(X)=∪{∪Nmad(x)∣x∈X}.
This completes the proof of theorem.The following example shows that two different coverings can induce the same the fourth type of neighborhood-based lower and upper approximation operations.Example 3.23 (Two different coverings generate the same the fourth type of neighborhood-based rough sets).
LetU={x1,x2,x3,x4}, C1={x1}, C2={x1,x2}, C3={x3,x4}, ℬ={C1,C2,C3}, and 𝒞={C2,C3}. Clearly, ℬ and 𝒞 are two different coverings of U. By Definition 2.3, it clear that Nℬ(x1)={x1}, Nℬ(x2)={x1,x2}, Nℬ(x3)={x3,x4}=Nℬ(x4), and N𝒞(x1)={x1,x2}=N𝒞(x2), N𝒞(x3)={x3,x4}=N𝒞(x4). It is easy to check that Nmadℬ(x1)=Nmadℬ(x2)={Nℬ(x2)}={x1,x2}, Nmadℬ(x3)=Nmadℬ(x4)={Nℬ(x3)}={x3,x4} and Nmad𝒞(x1)=Nmad𝒞(x2)={N𝒞(x2)}={x1,x2}, Nmad𝒞(x3)=Nmad𝒞(x3)={N𝒞(x4)}={x3,x4}. Thus for allx∈U, Nmadℬ(x)=Nmad𝒞(x) and so for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x). It follows by Theorem 3.22 that ℬ4̲=𝒞4̲ and ℬ4¯=𝒞4¯.In the following, we study the conditions for two coverings generating the same fourth type of neighborhood-based lower and upper approximation operations. Firstly, we present two lemmas.Lemma 3.24.
Let𝒞 be a covering of a nonempty set  U and  x,y∈U. If  N(u)∈Nmad(x) and  y∉N(u), then  u∉∪Nmad(y).Proof.
Suppose thatu∈∪Nmad(y). Then ∃N(v)∈Nmad(y), s.t. u∈N(v). Thus by Definition 2.3, N(u)⊆N(v). Since N(u)∈Nmad(x), it follows from Definition 3.2 that N(u)=N(v). By N(v)∈Nmad(y) and Definition 3.2, it is clear that y∈N(v). Thus y∈N(u), which contradicts the condition y∉N(u). Therefore, u∉∪Nmad(y).Lemma 3.25.
Letℬ and  𝒞 be two coverings of a nonempty set  U. And  ℬ and  𝒞 satisfy the condition that  for allx∈U,  ∪Nmadℬ(x)=∪Nmad𝒞(x). If for  x∈U,  N𝒞(u)∈Nmad𝒞(x),  Nℬ(v)∈Nmadℬ(x), and  N𝒞(u)⊆Nℬ(v), then  N𝒞(u)=Nℬ(v).Proof.
Suppose thatN𝒞(u)⊂Nℬ(v). Then, u∈Nℬ(v). Taking w∈Nℬ(v)-N𝒞(u), that is, w∈Nℬ(v), w∉N𝒞(u). Thus by Nℬ(v)∈Nmadℬ(x) and Proposition 3.21, we have that Nℬ(v)∈Nmadℬ(w) and so u∈∪Nmadℬ(w). On the other hand, since w∉N𝒞(u) and N𝒞(u)∈Nmad𝒞(x), it follows from Lemma 3.24 that u∉∪Nmad𝒞(w). Thus ∪Nmad𝒞(w)≠∪Nmadℬ(w), which contradicts the condition for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x). Therefore, N𝒞(u)=Nℬ(v).Now we present the conditions under which the two different coverings generate the same fourth type of neighborhood-based upper approximation operation.Theorem 3.26.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then the following assertions are equivalent: (1)
for allX⊆U, ℬ4¯(X)=𝒞4¯(X),(2)
for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x),(3)
for allx∈U, Nmadℬ(x)=Nmad𝒞(x),(4)
∪{Nmadℬ(x)∣x∈U}=∪{Nmad𝒞(x)∣x∈U}.Proof.
(1)⇒(2) for allx∈U, by Theorem 3.22, we have that ℬ4¯({x})=∪Nmadℬ(x) and 𝒞4¯({x})=∪Nmad𝒞(x). Since for allX⊆U, ℬ4¯(X)=𝒞4¯(X), it follows that ℬ4¯({x})=𝒞4¯({x}). Thus ∪Nmadℬ(x)=∪Nmad𝒞(x).
(2)⇒(1) It follows directly from Theorem 3.22.
(2)⇒(3) Let x∈U. By assertion (2), ∪Nmadℬ(x)=∪Nmad𝒞(x). Thus, for all Nℬ(u)∈Nmadℬ(x), there exists N𝒞(v)∈Nmad𝒞(x) such that u∈N𝒞(v). Suppose that Nℬ(u)≠N𝒞(v). Then by Lemma 3.25, we have that N𝒞(v)⊈Nℬ(u). Thus there exists w∈N𝒞(v) such that w∉Nℬ(u). By Proposition 3.21, w∈N𝒞(v) implies N𝒞(v)∈Nmad𝒞(w) and so u∈∪Nmad𝒞(w). In addition, by w∉Nℬ(u) and Lemma 3.24, we have that u∉∪Nmadℬ(w). Thus ∪Nmad𝒞(w)≠∪Nmadℬ(w), which is a contradiction with the assertion (2). Therefore, Nℬ(u)=N𝒞(v) and so Nℬ(u)∈Nmad𝒞(x). Thus Nmadℬ(x)⊆Nmad𝒞(x). In the same way, we can prove that Nmadℬ(x)⊇Nmad𝒞(x). Thus Nmadℬ(x)=Nmad𝒞(x).
(3)⇒(2) It is obvious.
(3)⇒(4) It is obvious.
(4)⇒(3) Let x∈U. For all Nℬ(u)∈Nmadℬ(x), clearly, Nℬ(u)∈∪{Nmadℬ(x)∣x∈U}. Since ∪{Nmadℬ(x)∣x∈U}=∪{Nmad𝒞(x)∣x∈U}, there exists N𝒞(v)∈∪{Nmad𝒞(x)∣x∈U} such that Nℬ(u)=N𝒞(v). By Nℬ(u)∈Nmadℬ(x) and Definition 3.2, we have that x∈Nℬ(u). Thus x∈N𝒞(v). Since N𝒞(v)∈∪{Nmad𝒞(x)∣x∈U}, it follows that there exists z∈U such that N𝒞(v)∈Nmad𝒞(z). Thus again by Proposition 3.21, we can have that N𝒞(v)∈Nmad𝒞(x). It follows from Nℬ(u)=N𝒞(v) that Nℬ(u)∈Nmad𝒞(x). Hence Nmadℬ(x)⊆Nmad𝒞(x). In the same way, we can prove that Nmadℬ(x)⊇Nmad𝒞(x). Thus Nmadℬ(x)=Nmad𝒞(x).For the covering𝒞 of U, since the lower approximation 𝒞4̲ and the upper approximation 𝒞4¯ are dual, they determine each other. That is, for two coverings ℬ and 𝒞, ℬ4̲=𝒞4̲ if and only if ℬ4¯=𝒞4¯. From the above analysis and Theorem 3.26, we can obtain the following results.Corollary 3.27.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then the following assertions are equivalent: (1)
for allX⊆U, ℬ4̲(X)=𝒞4̲(X),(2)
for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x),(3)
for allx∈U, Nmadℬ(x)=Nmad𝒞(x),(4)
∪{Nmadℬ(x)∣x∈U}=∪{Nmad𝒞(x)∣x∈U}.Now we present the conditions under which the two different coverings generate the same the fourth type of neighborhood-based rough sets.Theorem 3.28.
Letℬ and  𝒞 be two coverings of a nonempty set  U. Then the following assertions are equivalent: (1)
for allX⊆U, ℬ4̲(X)=𝒞4̲(X) and ℬ4¯(X)=𝒞4¯(X),(2)
for allx∈U, ∪Nmadℬ(x)=∪Nmad𝒞(x),(3)
for ally∈U, Nmadℬ(x)=Nmad𝒞(x),(4)
∪{Nmadℬ(x)∣x∈U}=∪{Nmad𝒞(x)∣x∈U}.Proof.
It follows directly from Theorem3.26 and Corollary 3.27.The above theorem is an important result for studying the covering reduction of the fourth type of neighborhood-based rough sets. In Section4.2, we will present the concept of reduct based on this theorem for the fourth type of rough set model.


## 4. Reduction of the Third and the Fourth Types of Neighborhood-Based Rough Sets

Examples3.12 and 3.23 show that for a covering, it could still be a covering by dropping some of its members. Furthermore, the resulting new covering might still produce the same neighborhood-based lower and upper approximations. Hence, a covering may have “redundant” members, and a procedure is needed to find its “smallest” covering that induces the same neighborhood-based lower and upper approximations. This technique can be used to reduce the redundant information in data mining.In this section, we will investigate the reduction issues about the third and the fourth types of neighborhood-based generalized rough sets. Since for a covering it could not be a covering by dropping some of its members, we need to extend the concepts of neighborhood, minimal neighborhood description, and maximal neighborhood description to a general family of subsets of a universe case so as to reasonably explore the covering reduction of neighborhood-based rough sets.LetU be a nonempty set called the universe of discourse. The class of all subsets of U will be denoted by P(U). Naturally, we present the definitions of generalization of neighborhood, minimal neighborhood description, and maximal neighborhood description.Definition 4.1 (Neighborhood).
LetU be a universe, 𝒞⊆P(U) and x∈U.N𝒞(x)=∩{K∈𝒞∣x∈K} is called the neighborhood of x.Generally, we omit the subscript 𝒞 when there is no confusion.Definition 4.2 (Minimal neighborhood description).
LetU be a universe, 𝒞⊆P(U) and x∈U. The family of sets Nmid𝒞(x)={N(u)∣u∈N(x)∧(for ally∈U∧N(y)⊆N(u)⇒N(y)=N(u))} is called the minimal neighborhood description of the element x. When there is no confusion, we omit the subscript 𝒞.Definition 4.3 (Maximal neighborhood description).
LetU be a universe, 𝒞⊆P(U) and x∈U. The family of sets Nmad𝒞(x)={N(u)∣x∈N(u)∧(for ally∈U∧N(u)⊆N(y)⇒N(u)=N(y))} is called the maximal neighborhood description of the element x. When there is no confusion, we omit the subscript 𝒞.It is easy to see that when𝒞 is a covering of U, Definitions 4.1, 4.2, and 4.3 are coincident with Definitions 2.3, 3.1, and 3.2, respectively.


### 4.1. Reduction of the Third Type of Neighborhood-Based Rough Sets

Throughout this subsection, we always assume that the rough set model which is discussed by us is the third type of neighborhood-based generalized rough sets. So the definitions of a reducible element, an irreducible covering, and a reduct are all based on the third type of neighborhood-based rough sets.A reduct should be able to preserve the original classification power provided by the initial covering. In order to present a reasonable notion of reduct, we first give the definition of a reducible element of a covering.Definition 4.4 (A reducible element about the third type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U and K∈𝒞. If for allx∈U,Nmid𝒞(x)=Nmid𝒞-{K}(x), we say that K is a reducible element of 𝒞. Otherwise, K is an irreducible element of 𝒞.Definition 4.5 (Irreducible covering about the third type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U. If every element of 𝒞 is an irreducible element, we say that 𝒞 is irreducible. Otherwise, 𝒞 is reducible.Definition 4.6 (Reduct about the third type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U and ℬ⊆𝒞. If ℬ is an irreducible covering and for allx∈U,Nmidℬ(x)=Nmid𝒞(x), we say that ℬ is a reduct of 𝒞. Let red3(𝒞)={ℬ∣ℬis a reduct of𝒞}.In the following, we will illustrate that, for a covering, the reduct always exists and is not unique. Further, we will show that every reduct and the initial covering induce the same lower and upper approximation operations.Firstly, we give an important proposition.Proposition 4.7.
Let𝒞 be a covering of a universe  U and  ℬ⊆𝒞. If  ℬ and  𝒞 satisfy the condition that  for allx∈U,  Nmidℬ(x)=Nmid𝒞(x), then  ℬ is a covering of  U.Proof.
Suppose thatℬ is not a covering of U. Then ∪ℬ⊂U. Taking x0∈U-∪ℬ, by Definition 4.1, we have that Nℬ(x0)=∅. Thus by Definition 4.2, Nmidℬ(x0)=∅. On the other hand, since 𝒞 is a covering of U, it follows from Remark 3.6 that Nmid𝒞(x0)≠∅. Thus Nmidℬ(x0)≠Nmid𝒞(x0), which contradicts with the conditions for allx∈U, Nmidℬ(x)=Nmid𝒞(x). This completes the proof.Corollary 4.8.
Let𝒞 be a covering of a universe  U and  K∈𝒞. If  K is a reducible element of  𝒞, then  𝒞-{K} is still a covering of  U.Proof.
It comes directly from Definition4.4 and Proposition 4.7.The following theorem shows that for a covering, there is at least one reduct.Theorem 4.9.
Let𝒞 be a covering of a universe  U. Then there exists  ℬ⊆𝒞 such that  ℬ is a reduct of  𝒞.Proof.
Suppose that for allℬ⊆𝒞, ℬ is not a reduct of 𝒞. Then 𝒞 is not a reduct of 𝒞. Thus by Definition 4.6, 𝒞 is a reducible covering. This implies that there exists K1∈𝒞 such that K1 is a reducible element of 𝒞. We write ℬ1=𝒞-{K1}. By Definition 4.4, we have that for allx∈U, Nmidℬ1(x)=Nmid𝒞(x). Further, by Corollary 4.8, ℬ1 is a covering of U, and clearly, ℬ1⊂𝒞. Thus by the assumption, ℬ1 is not a reduct of 𝒞. Since for allx∈U, Nmidℬ1(x)=Nmid𝒞(x), it follows from Definition 4.6 that ℬ1 is a reducible covering and so there exists K2∈ℬ1 such that K2 is a reducible element of ℬ1. We write ℬ2=ℬ1-{K2}. By Definition 4.4, we have that for allx∈U, Nmidℬ2(x)=Nmidℬ1(x). By for allx∈U, Nmidℬ1(x)=Nmid𝒞(x), this implies that for allx∈U, Nmidℬ2(x)=Nmid𝒞(x). Further, by Corollary 4.8, ℬ2 is a covering of U, and clearly, ℬ2⊂ℬ1⊂𝒞, that is, ℬ2⊂𝒞. Thus by the assumption, ℬ2 is not a reduct of 𝒞⋯. Continue in this way, we have an infinite sequence 𝒞,ℬ1,ℬ2,…,ℬm,… such that 𝒞⊃ℬ1⊃ℬ2⊃⋯⊃ℬm⊃⋯. But it is impossible since the covering 𝒞 has only finite elements. This completes the proof.Actually, the proving process of the above theorem provides a procedure to compute the reduct of a covering of a universe.The following result shows that the definition of reduct is reasonable.Theorem 4.10.
Let𝒞 be a covering of a universe  U. Then for all  ℬ∈red3(𝒞),  ℬ and  𝒞 generate the same the third neighborhood-based lower and upper approximations.Proof.
It follows directly from Definition4.6, Proposition 4.7, and Theorem 3.13.Lemma 4.11.
Let𝒞 be a covering of a universe  U and  ℬ⊆𝒞.  ℬ and  𝒞 satisfy the condition that  for allx∈U,  Nmidℬ(x)=Nmid𝒞(x). Then  for allx∈U,  for allN𝒞(u)∈Nmid𝒞(x), we have that  N𝒞(u)=Nℬ(u) and  Nℬ(u)∈Nmidℬ(x).Proof.
Letx∈U. Then by the condition, Nmidℬ(x)=Nmid𝒞(x). Thus for allN𝒞(u)∈Nmid𝒞(x), there exists Nℬ(v)∈Nmidℬ(x) such that N𝒞(u)=Nℬ(v). Hence u∈Nℬ(v) and by Proposition 4.7, ℬ is a covering of U. Thus, applying Proposition 3.9, we have that Nℬ(v)=Nℬ(u). It follows that N𝒞(u)=Nℬ(u) and Nℬ(u)∈Nmidℬ(x).Proposition 4.12.
Let𝒞 be a covering of a universe  U and  ℬ⊂𝒞.  ℬ and  𝒞 satisfy the condition that  for allx∈U,  Nmidℬ(x)=Nmid𝒞(x). Then  for allK∈𝒞-ℬ,  K is a reducible element of  𝒞.Proof.
LetK∈𝒞-ℬ and x∈U. Then ℬ⊆𝒞-{K}⊆𝒞.(i)
We will show that𝒞-{K} and ℬ are two coverings of U. By the condition and Proposition 4.7, ℬ is a covering of U. Clearly, ℬ⊆𝒞-{K}, thus 𝒞-{K} is also a covering of U.By (i) and the condition, we know that𝒞, 𝒞-{K}, and ℬ are all coverings of U. Hence, in the following process of proof, we can use directly the concepts and conclusions obtained in Section 3.(ii)
We will prove thatfor allz∈U, for allN𝒞(u)∈Nmid𝒞(z), N𝒞(u)=N𝒞-{K}(u). For all N𝒞(u)∈Nmid𝒞(z), by the condition and Lemma 4.11, we have that N𝒞(u)=Nℬ(u). Since ℬ⊆𝒞-{K}⊆𝒞, it follows by Definition 2.3 that N𝒞(u)⊆N𝒞-{K}(u)⊆Nℬ(u)=N𝒞(u). Thus N𝒞(u)=N𝒞-{K}(u).(iii)
We will show thatNmid𝒞(x)⊆Nmid𝒞-{K}(x). For all N𝒞(u)∈Nmid𝒞(x), then by Definition 3.1, u∈N𝒞(x). By N𝒞(x)⊆N𝒞-{K}(x), we have that u∈N𝒞-{K}(x). Thus suppose that N𝒞-{K}(u)∉Nmid𝒞-{K}(x). Then by Definition 3.1, there exists z∈U such that N𝒞-{K}(z)⊂N𝒞-{K}(u). By (ii), we have that N𝒞(u)=N𝒞-{K}(u), thus, N𝒞-{K}(z)⊂N𝒞(u). Clearly, N𝒞(z)⊆N𝒞-{K}(z), thus N𝒞(z)⊂N𝒞(u), which contradicts the fact that N𝒞(u)∈Nmid𝒞(x). Thus N𝒞-{K}(u)∈Nmid𝒞-{K}(x). It follows by (ii) that N𝒞(u)∈Nmid𝒞-{K}(x). Thus Nmid𝒞(x)⊆Nmid𝒞-{K}(x).(iv)
We will show thatNmid𝒞-{K}(x)⊆Nmid𝒞(x). For all N𝒞-{K}(u)∈Nmid𝒞-{K}(x). Since 𝒞-{K}⊆𝒞, it is clear that N𝒞(u)⊆N𝒞-{K}(u). By u∈N𝒞(u) and Lemma 3.5, there exists N𝒞(z)∈Nmid𝒞(u) such that N𝒞(z)⊆N𝒞(u). This implies that N𝒞(z)⊆N𝒞-{K}(u) and so z∈N𝒞-{K}(u). Thus by Proposition 3.9, N𝒞-{K}(z)=N𝒞-{K}(u). Further, by N𝒞(z)∈Nmid𝒞(u) and (ii), we have that N𝒞(z)=N𝒞-{K}(z). Thus N𝒞(z)=N𝒞-{K}(u). In addition, by Lemma 4.11, N𝒞(z)=Nℬ(z) and Nℬ(z)∈Nmidℬ(u). Thus Nℬ(z)=N𝒞-{K}(u) and so u∈Nℬ(z). It follows by Proposition 3.9 that Nℬ(z)=Nℬ(u) and so N𝒞-{K}(u)=Nℬ(u) and Nℬ(u)∈Nmidℬ(u). By Definition 3.1, it is clear that u∈N𝒞-{K}(x). Since B⊆𝒞-{K}, it follows that N𝒞-{K}(x)⊆Nℬ(x). Thus u∈Nℬ(x). It follows by Proposition 3.10 that Nℬ(u)∈Nmidℬ(x) and so N𝒞-{K}(u)∈Nmidℬ(x). Thus, by the condition Nmidℬ(x)=Nmid𝒞(x), we conclude that N𝒞-{K}(u)∈Nmid𝒞(x). It follows that Nmid𝒞-{K}(x)⊆Nmid𝒞(x).
By (iii) and (iv), we have thatNmid𝒞-{K}(x)=Nmid𝒞(x). We have proved that for allx∈U, Nmid𝒞-{K}(x)=Nmid𝒞(x). Thus by Definition 4.4, K is a reducible element of 𝒞.Corollary 4.13.
Let𝒞 be a covering of a universe  U,  K∈𝒞 a reducible element of  𝒞 and  K1∈𝒞-{K}. If  K1 is an irreducible element of  𝒞, then  K1 is an irreducible element of  𝒞-{K}.Proof.
Suppose thatK1 is a reducible element of 𝒞-{K}. Then by Definition 4.4, for allx∈U, Nmid𝒞-{K}(x)=Nmid𝒞-{K,K1}(x). In addition, since K is a reducible element of 𝒞, it follows from Definition 4.4 that for allx∈U, Nmid𝒞(x)=Nmid𝒞-{K}(x). Thus for allx∈U, Nmid𝒞(x)=Nmid𝒞-{K,K1}(x). Clearly, K1∈𝒞-(𝒞-{K,K1}), thus by Proposition 4.12, K1 is a reducible element of 𝒞, which contradicts the condition that K1 is an irreducible element of 𝒞. This completes the proof.The above proposition guarantees that omitting a reducible element in a covering will not make any current irreducible element reducible. Therefore, the set of all irreducible elements of𝒞 is constant. We denote this set by cor3(𝒞), that is, (4.1)cor3(C)={K∣Kis an irreducible element ofC}.The following result establishes the relationship betweencor3(𝒞) and red3(𝒞).Theorem 4.14.
Let𝒞 be a covering of a universe  U. Then  cor3(𝒞)=∩red3(𝒞).Proof.
LetK∈cor3(𝒞). Suppose that K∉∩red3(𝒞). Then there exists ℬ∈red3(𝒞) such that K∉ℬ. Hence K∈𝒞-ℬ. By Definition 4.6 and Proposition 4.12, this implies that K is a reducible element of 𝒞, which contradicts the fact that K∈cor3(𝒞). Hence K∈∩red3(𝒞) and so cor3(𝒞)⊆∩red3(𝒞). On the other hand, let K∈∩red3(𝒞). Suppose that K∉cor3(𝒞). Then K is a reducible element of 𝒞. By Definition 4.4, we have that for allx∈U, Nmid𝒞(x)=Nmid𝒞-{K}(x) and by Corollary 4.8, 𝒞-{K} is a covering of U. Thus by Theorem 4.9, there exists ℬ⊆𝒞-{K} such that ℬ is a reduct of 𝒞-{K}. By Definition 4.6, this implies that ℬ is an irreducible covering and for allx∈U, Nmidℬ(x)=Nmid𝒞-{K}(x). Thus for allx∈U, Nmidℬ(x)=Nmid𝒞(x) and ℬ is an irreducible covering. It follows from Definition 4.6 that ℬ is a reduct of 𝒞. Since ℬ⊆𝒞-{K}, it follows that K∉ℬ, which contradicts the fact that K∈∩red3(𝒞). Thus K∈cor3(𝒞), and so ∩red3(𝒞)⊆cor3(𝒞). In summary, cor3(𝒞)=∩red3(𝒞).The above result states that an element will not be reduced in any reduction procedure if and only if it is irreducible. Hence the irreducible elements will be reserved in any reduction procedure, that is to say,cor3(𝒞) is contained in any reduct of 𝒞. So we can compute the reduct of 𝒞 based on cor3(𝒞).Example 4.15.
LetU={x1,x2,x3,x4}, C1={x1}, C2={x1,x2,x3}, C3={x1,x2,x4}, C4={x1,x2,x3,x4}, and 𝒞={C1,C2,C3,C4}. Clearly, 𝒞 is a covering of U.
By Definition4.2, it easy to check that
(4.2)NmidC(x1)=NmidC(x2)=NmidC(x3)=NmidC(x4)={{x}}.
By Definition4.2, we can get that
(4.3)NmidC-{C1}(x1)=NmidC-{C1}(x2)=NmidC-{C1}(x3)=NmidC-{C1}(x4)={{x1,x2}}.
Hence 𝒞 and 𝒞-{C1} do not satisfy the condition for allx∈U, Nmid𝒞(x)=Nmid𝒞-{C1}(x). It follows from Definition 4.4 that C1 is an irreducible element of 𝒞.
By Definition4.2, we can get that
(4.4)NmidC-{C2}(x1)=NmidC-{C2}(x2)=NmidC-{C2}(x3)=NmidC-{C2}(x4)={{x1}}.
Hence
(4.5)NmidC(x1)=NmidC-{C2}(x1),NmidC(x2)=NmidC-{C2}(x2),NmidC(x3)=NmidC-{C2}(x3),NmidC(x4)=NmidC-{C2}(x4).
It follows from Definition 4.4 that C2 is a reducible element of 𝒞. In the same way, we can check that C3 and C4 are all reducible elements of 𝒞.
Hencecor3(𝒞)={C1}.
Since{C1,C2} and {C1,C3} are not coverings of U, it follows from Corollaries 4.8 and 4.13 that every element of {C1,C2,C3} is an irreducible. Thus {C1,C2,C3} is a reduct of 𝒞.
For{C1,C2,C4}, by Definition 4.2, it is easy to check that
(4.6)Nmid{C1,C2,C4}(x1)=Nmid{C1,C2,C4}-{C2}(x1),Nmid{C1,C2,C4}(x2)=Nmid{C1,C2,C4}-{C2}(x2),Nmid{C1,C2,C4}(x3)=Nmid{C1,C2,C4}-{C2}(x3),Nmid{C1,C2,C4}(x4)=Nmid{C1,C2,C4}-{C2}(x4).
It follows from Definition 4.4 that C2 is a reducible element of {C1,C2,C4}. Further, for {C1,C4}, by Corollaries 4.8 and 4.13, it is clear that C1 and C4 are all irreducible elements of {C1,C4}. Thus it is clear that {C1,C4} is a reduct of 𝒞. A similar analysis to {C1,C3,C4}, we can also get that {C1,C4} is a reduct of 𝒞.
To sum up,𝒞 has two reducts that are {C1,C2,C3} and {C1,C4}. It is easy to see that cor3(𝒞)={C1}={C1,C2,C3}∩{C1,C4}=∩red3(𝒞).The above example also illustrates that for a covering, the reduct is not unique.Remark 4.16.
Let𝒞 be a covering of a universe U. For ℬ∈red3(𝒞), for allK∈ℬ, by Definitions 4.4, 4.5, and 4.6, it is easy to see that ℬ and ℬ-{K} do not satisfy the condition for allx∈U, Nmidℬ(x)=Nmid𝒞(x). Thus by Theorem 3.13, we know that ℬ and ℬ-{K} cannot induce the same lower and upper approximation operations. This illustrates that for allℬ∈red3(𝒞), ℬ is a smallest covering that induces the same the third type of neighborhood-based rough sets.


### 4.2. Reduction of the Third Type of Neighborhood-Based Rough Sets

Throughout this subsection, we always assume that the rough set model which is discussed by us is the fourth type of neighborhood-based generalized rough sets. So the definitions of a reducible element, an irreducible covering and a reduct, are all based on the fourth type of neighborhood-based rough sets.Notation 1.
Let𝒞 be a covering of U. We write NM𝒞=∪{Nmad𝒞(x)∣x∈U}.By Theorem3.28, we know that if NM𝒞=NMℬ, then ℬ and 𝒞 generate the same the forth type of neighborhood-based lower and upper approximation operations. So we can give the following definition of a reducible element.Definition 4.17 (A reducible element about the fourth type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U and K∈𝒞. If NM𝒞=NM𝒞-{K}, we say that K is a reducible element of 𝒞. Otherwise, K is an irreducible element of 𝒞.Definition 4.18 (Irreducible covering about the fourth type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U. If every element of 𝒞 is an irreducible element, we say that 𝒞 is irreducible. Otherwise, 𝒞 is reducible.Definition 4.19 (Reduct about the fourth type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U and ℬ⊆𝒞. If ℬ is irreducible and NMℬ=NM𝒞, we say that ℬ is a reduct of 𝒞. Let red4(𝒞)={ℬ∣ℬis a reduct of𝒞}.The following proposition is basic.Proposition 4.20.
Let𝒞 be a covering of a universe  U and  ℬ⊆𝒞. If  ℬ and  𝒞 satisfy the condition that  NMℬ=NM𝒞, then  ℬ is a covering of  U.Proof.
Suppose thatℬ is not a covering of U. Then ∪ℬ⊂U. Taking x0∈U-∪ℬ, by Definition 4.1, we have that for allu∈U, x0∉Nℬ(u). Thus for allNℬ(u)∈NMℬ, x0∉Nℬ(u). On the other hand, since 𝒞 is a covering of U, it follows from Definition 3.2 that ∪NM𝒞=U. Thus there exists NC(u)∈NM𝒞 such that x0∈NC(u). Hence NC(u)∉NMℬ and so NMℬ≠NM𝒞, which is a contradiction with the condition NMℬ=NM𝒞. Thus ℬ is a covering of U.Corollary 4.21.
Let𝒞 be a covering of a universe  U and  K∈𝒞. If  K is a reducible element of  𝒞, then  𝒞-{K} is still a covering of  U.Proof.
It comes directly from Definition4.17 and Proposition 4.20.In the following, we will illustrate that for a covering, the reduct always exists.Theorem 4.22.
Let𝒞 be a covering of a universe  U. Then there exists  ℬ⊆𝒞 such that  ℬ is a reduct of  𝒞.Proof.
The proof is similar to that of Theorem4.9.Now we show that every reduct and the initial covering induce the same lower and upper approximation operations.Theorem 4.23.
Let𝒞 be a covering of a universe  U. Then for all  ℬ∈red4(𝒞),  ℬ and  𝒞 generate the same the fourth type of neighborhood-based lower and upper approximations.Proof.
By Definition4.19 and Proposition 4.20, ℬ is a covering of U. Thus by Definition 4.19 and Theorem 3.28, for all ℬ∈red4(𝒞), ℬ and 𝒞 generate the same the fourth type of neighborhood-based lower and upper approximations.Lemma 4.24.
Let𝒞 be a covering of a universe  U and  ℬ⊆𝒞.  ℬ and  𝒞 satisfy the condition that  NMℬ=NM𝒞. Then  for allN𝒞(u)∈NM𝒞, we have that  N𝒞(u)=Nℬ(u) and  Nℬ(u)∈NMℬ.Proof.
By the conditions and Proposition4.20, we know that ℬ and 𝒞 are all coverings of U. Hence, in the following process of proof, we can use directly the concepts and conclusions obtained in Section 3.
LetN𝒞(u)∈NM𝒞. Then by NMℬ=NM𝒞, there exists Nℬ(v)∈NMℬ such that N𝒞(u)=Nℬ(v) and so u∈Nℬ(v). By Definition 2.3, it is clear that Nℬ(u)⊆Nℬ(v). In addition, since ℬ⊆𝒞, it follows from Definition 2.3 that N𝒞(u)⊆Nℬ(u). By N𝒞(u)=Nℬ(v), we have that Nℬ(v)⊆Nℬ(u). By Nℬ(v)∈NMℬ, Notation 1 and Definition 3.2, this implies Nℬ(v)=Nℬ(u). Thus N𝒞(u)=Nℬ(u) and Nℬ(u)∈NMℬ.Proposition 4.25.
Let𝒞 be a covering of a universe  U and  ℬ⊂𝒞.  ℬ and  𝒞 satisfy the condition that  NMℬ=NM𝒞. Then  for allK∈𝒞-ℬ,  K is a reducible element of  𝒞.Proof.
LetK∈𝒞-ℬ, then ℬ⊆𝒞-{K}⊆𝒞.(i)
We will show that𝒞-{K} and ℬ are two coverings of U. By the condition and Proposition 4.20, ℬ is a covering of U. Clearly, ℬ⊆𝒞-{K}, thus 𝒞-{K} is also a covering of U.By (i) and the condition, we know that𝒞, 𝒞-{K} and ℬ are all coverings of U. Hence, in the following process of proof, we can use directly the concepts and conclusions obtained in Section 3.(ii)
We will show thatNM𝒞⊆NM𝒞-{K}. For all N𝒞(u)∈NM𝒞, then by Lemma 4.24, N𝒞(u)=Nℬ(u) and Nℬ(u)∈NMℬ. Since ℬ⊆𝒞-{K}⊆𝒞, it follows from Definition 2.3 that N𝒞(u)⊆N𝒞-{K}(u)⊆Nℬ(u). Thus by N𝒞(u)=Nℬ(u), we have that N𝒞-{K}(u)=Nℬ(u). Suppose that N𝒞-{K}(u)∉NM𝒞-{K}. Then N𝒞-{K}(u)∉Nmad𝒞-{K}(u). Thus by Definition 3.2, there exists z∈U such that N𝒞-{K}(u)⊂N𝒞-{K}(z) and so Nℬ(u)⊂N𝒞-{K}(z), which contradicts the fact that Nℬ(u)∈NMℬ. Thus N𝒞-{K}(u)∈NM𝒞-{K}. Combining N𝒞(u)=Nℬ(u) and N𝒞-{K}(u)=Nℬ(u), we can get that N𝒞(u)=N𝒞-{K}(u) and so N𝒞(u)∈NM𝒞-{K}. Thus, NM𝒞⊆NM𝒞-{K}.(iii)
We will show thatNM𝒞-{K}⊆NM𝒞, for allN𝒞-{K}(u)∈NM𝒞-{K}. By ℬ⊆𝒞-{K}, it is clear that N𝒞-{K}(u)⊆Nℬ(u). By u∈Nℬ(u) and Proposition 3.18, there exists Nℬ(z)∈Nmadℬ(u) such that Nℬ(u)⊆Nℬ(z). This implies N𝒞-{K}(u)⊆Nℬ(z). By Notation 1, it is clear that Nℬ(z)∈NMℬ. Since NMℬ=NM𝒞, it follows that there exists N𝒞(v)∈NM𝒞 such that Nℬ(z)=N𝒞(v). Thus N𝒞-{K}(u)⊆N𝒞(v). Clearly, N𝒞(v)⊆N𝒞-{K}(v), hence N𝒞-{K}(u)⊆N𝒞(v)⊆N𝒞-{K}(v). In addition, since N𝒞-{K}(u)∈NM𝒞-{K}, it follows from Notation 1 and Definition 3.2 that N𝒞-{K}(u)=N𝒞-{K}(v). This implies that N𝒞-{K}(u)=N𝒞(v). It follows by N𝒞(v)∈NM𝒞 that N𝒞-{K}(u)∈NM𝒞. Thus NM𝒞-{K}⊆NM𝒞.
By (ii) and (iii), we have thatNM𝒞-{K}=NM𝒞. Thus by Definition 4.17, K is a reducible element of 𝒞.Corollary 4.26.
Let𝒞 be a covering of a universe  U,  K∈𝒞 a reducible element of  𝒞 and  K1∈𝒞-{K}. If  K1 is an irreducible element of  𝒞, then  K1 is an irreducible element of  𝒞-{K}.Proof.
Suppose thatK1 is a reducible element of 𝒞-{K}. Then by Definition 4.17, NM𝒞-{K}=NM𝒞-{K,K1}. Since K is a reducible element of 𝒞, it follows from Definition 4.17 that NM𝒞=NM𝒞-{K}. Thus NM𝒞=NM𝒞-{K,K1}. Clearly, K1∈𝒞-(𝒞-{K,K1}), thus by Proposition 4.25, K1 is a reducible element of 𝒞, which contradicts the condition that K1 is an irreducible element of 𝒞. This completes the proof.The above proposition guarantees that omitting a reducible element in a covering will not make any current irreducible element reducible. Therefore, for a covering𝒞, the set of all irreducible elements is constant. We denote this set by cor4(𝒞), that is, (4.7)cor4(C)={K∣Kis an irreducible element ofC}.Theorem 4.27.
Let𝒞 be a covering of a universe  U. Then  cor4(𝒞)=∩red4(𝒞).Proof.
The proof is similar to that of Theorem4.14.The above result states that an element will not be reduced in any reduction procedure if and only if it is irreducible. Hence the irreducible elements will be reserved in any reduction procedure, that is to say,cor4(𝒞) is contained in any reduct of 𝒞. So we can compute the reduct of 𝒞 based on cor4(𝒞).Example 4.28.
LetU={x1,x2,x3,x4}, C1={x1,x2,x3}, C2={x1,x2,x4}, C3={x1,x2}, C4={x3}, C5={x4}, and 𝒞={C1,C2,C3,C4,C5}. Clearly, 𝒞 is a covering of U.
By Definition4.3 and Notation 1, it is easy to see that NM𝒞={{x1,x2},{x3},{x4}}.
SinceNM𝒞-{C1}={{x1,x2},{x3},{x4}}, it follows that NM𝒞=NM𝒞-{C1}. Thus C1 is a reducible element of 𝒞. In the same way, we can check that C2 and C3 are reducible elements of 𝒞.
SinceNM𝒞-{C4}={{x1,x2,x3},{x4}}, it follows that NM𝒞≠NM𝒞-{C4}. Thus C4 is an irreducible element of 𝒞.
SinceNM𝒞-{C5}={{x1,x2,x4},{x3}}, it follows that NM𝒞≠NM𝒞-{C5}. Thus C5 is an irreducible element of 𝒞.
Hencecor4(𝒞)={C4,C5}.
It is easy to check thatNM{C1,C2,C4,C5}≠NM{C2,C4,C5} and NM{C1,C2,C4,C5}≠NM{C1,C4,C5}. Thus C1 and C2 are irreducible elements of {C1,C2,C4,C5}. By Corollary 4.26, C4 and C5 are also irreducible elements of {C1,C2,C4,C5}. Hence {C1,C2,C4,C5} is an irreducible covering of U. It follows that {C1,C2,C4,C5} is a reduct of 𝒞.
It is easy to check thatNM{C1,C3,C4,C5}=NM{C3,C4,C5} and NM{C1,C3,C4,C5}≠NM{C1,C4,C5}. Thus C1 is a reducible element of {C1,C3,C4,C5}, and C3 is an irreducible element of {C1,C3,C4,C5}. Further, by Corollary 4.26, {C3,C4,C5} is an irreducible covering. Further, it is easy to verify that NM𝒞=NM{C3,C4,C5}. Hence {C3,C4,C5} is a reduct of 𝒞. A similar analysis to {C2,C3,C4,C5}, we can also get that {C3,C4,C5} is a reduct of 𝒞.
To sum up,𝒞 has two reducts that are {C1,C2,C3,C4} and {C3,C4,C5}. It is easy to see that cor4(𝒞)={C3,C4}={C1,C2,C3,C4}∩{C3,C4,C5}=∩red4(𝒞).Remark 4.29.
Let𝒞 be a covering of a universe U. For ℬ∈red4(𝒞), for allK∈ℬ, by Definitions 4.17, 4.18, and 4.19, it is easy to see that ℬ and ℬ-{K} do not satisfy the condition for allx∈U, Nmidℬ(x)=Nmid𝒞(x). Thus by Theorem 3.28, we know that ℬ and ℬ-{K} cannot induce the same lower and upper approximation operations. This illustrates that for allℬ∈red4(𝒞), ℬ is a smallest covering that induces the same the fourth type of neighborhood-based rough sets.


## 4.1. Reduction of the Third Type of Neighborhood-Based Rough Sets

Throughout this subsection, we always assume that the rough set model which is discussed by us is the third type of neighborhood-based generalized rough sets. So the definitions of a reducible element, an irreducible covering, and a reduct are all based on the third type of neighborhood-based rough sets.A reduct should be able to preserve the original classification power provided by the initial covering. In order to present a reasonable notion of reduct, we first give the definition of a reducible element of a covering.Definition 4.4 (A reducible element about the third type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U and K∈𝒞. If for allx∈U,Nmid𝒞(x)=Nmid𝒞-{K}(x), we say that K is a reducible element of 𝒞. Otherwise, K is an irreducible element of 𝒞.Definition 4.5 (Irreducible covering about the third type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U. If every element of 𝒞 is an irreducible element, we say that 𝒞 is irreducible. Otherwise, 𝒞 is reducible.Definition 4.6 (Reduct about the third type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U and ℬ⊆𝒞. If ℬ is an irreducible covering and for allx∈U,Nmidℬ(x)=Nmid𝒞(x), we say that ℬ is a reduct of 𝒞. Let red3(𝒞)={ℬ∣ℬis a reduct of𝒞}.In the following, we will illustrate that, for a covering, the reduct always exists and is not unique. Further, we will show that every reduct and the initial covering induce the same lower and upper approximation operations.Firstly, we give an important proposition.Proposition 4.7.
Let𝒞 be a covering of a universe  U and  ℬ⊆𝒞. If  ℬ and  𝒞 satisfy the condition that  for allx∈U,  Nmidℬ(x)=Nmid𝒞(x), then  ℬ is a covering of  U.Proof.
Suppose thatℬ is not a covering of U. Then ∪ℬ⊂U. Taking x0∈U-∪ℬ, by Definition 4.1, we have that Nℬ(x0)=∅. Thus by Definition 4.2, Nmidℬ(x0)=∅. On the other hand, since 𝒞 is a covering of U, it follows from Remark 3.6 that Nmid𝒞(x0)≠∅. Thus Nmidℬ(x0)≠Nmid𝒞(x0), which contradicts with the conditions for allx∈U, Nmidℬ(x)=Nmid𝒞(x). This completes the proof.Corollary 4.8.
Let𝒞 be a covering of a universe  U and  K∈𝒞. If  K is a reducible element of  𝒞, then  𝒞-{K} is still a covering of  U.Proof.
It comes directly from Definition4.4 and Proposition 4.7.The following theorem shows that for a covering, there is at least one reduct.Theorem 4.9.
Let𝒞 be a covering of a universe  U. Then there exists  ℬ⊆𝒞 such that  ℬ is a reduct of  𝒞.Proof.
Suppose that for allℬ⊆𝒞, ℬ is not a reduct of 𝒞. Then 𝒞 is not a reduct of 𝒞. Thus by Definition 4.6, 𝒞 is a reducible covering. This implies that there exists K1∈𝒞 such that K1 is a reducible element of 𝒞. We write ℬ1=𝒞-{K1}. By Definition 4.4, we have that for allx∈U, Nmidℬ1(x)=Nmid𝒞(x). Further, by Corollary 4.8, ℬ1 is a covering of U, and clearly, ℬ1⊂𝒞. Thus by the assumption, ℬ1 is not a reduct of 𝒞. Since for allx∈U, Nmidℬ1(x)=Nmid𝒞(x), it follows from Definition 4.6 that ℬ1 is a reducible covering and so there exists K2∈ℬ1 such that K2 is a reducible element of ℬ1. We write ℬ2=ℬ1-{K2}. By Definition 4.4, we have that for allx∈U, Nmidℬ2(x)=Nmidℬ1(x). By for allx∈U, Nmidℬ1(x)=Nmid𝒞(x), this implies that for allx∈U, Nmidℬ2(x)=Nmid𝒞(x). Further, by Corollary 4.8, ℬ2 is a covering of U, and clearly, ℬ2⊂ℬ1⊂𝒞, that is, ℬ2⊂𝒞. Thus by the assumption, ℬ2 is not a reduct of 𝒞⋯. Continue in this way, we have an infinite sequence 𝒞,ℬ1,ℬ2,…,ℬm,… such that 𝒞⊃ℬ1⊃ℬ2⊃⋯⊃ℬm⊃⋯. But it is impossible since the covering 𝒞 has only finite elements. This completes the proof.Actually, the proving process of the above theorem provides a procedure to compute the reduct of a covering of a universe.The following result shows that the definition of reduct is reasonable.Theorem 4.10.
Let𝒞 be a covering of a universe  U. Then for all  ℬ∈red3(𝒞),  ℬ and  𝒞 generate the same the third neighborhood-based lower and upper approximations.Proof.
It follows directly from Definition4.6, Proposition 4.7, and Theorem 3.13.Lemma 4.11.
Let𝒞 be a covering of a universe  U and  ℬ⊆𝒞.  ℬ and  𝒞 satisfy the condition that  for allx∈U,  Nmidℬ(x)=Nmid𝒞(x). Then  for allx∈U,  for allN𝒞(u)∈Nmid𝒞(x), we have that  N𝒞(u)=Nℬ(u) and  Nℬ(u)∈Nmidℬ(x).Proof.
Letx∈U. Then by the condition, Nmidℬ(x)=Nmid𝒞(x). Thus for allN𝒞(u)∈Nmid𝒞(x), there exists Nℬ(v)∈Nmidℬ(x) such that N𝒞(u)=Nℬ(v). Hence u∈Nℬ(v) and by Proposition 4.7, ℬ is a covering of U. Thus, applying Proposition 3.9, we have that Nℬ(v)=Nℬ(u). It follows that N𝒞(u)=Nℬ(u) and Nℬ(u)∈Nmidℬ(x).Proposition 4.12.
Let𝒞 be a covering of a universe  U and  ℬ⊂𝒞.  ℬ and  𝒞 satisfy the condition that  for allx∈U,  Nmidℬ(x)=Nmid𝒞(x). Then  for allK∈𝒞-ℬ,  K is a reducible element of  𝒞.Proof.
LetK∈𝒞-ℬ and x∈U. Then ℬ⊆𝒞-{K}⊆𝒞.(i)
We will show that𝒞-{K} and ℬ are two coverings of U. By the condition and Proposition 4.7, ℬ is a covering of U. Clearly, ℬ⊆𝒞-{K}, thus 𝒞-{K} is also a covering of U.By (i) and the condition, we know that𝒞, 𝒞-{K}, and ℬ are all coverings of U. Hence, in the following process of proof, we can use directly the concepts and conclusions obtained in Section 3.(ii)
We will prove thatfor allz∈U, for allN𝒞(u)∈Nmid𝒞(z), N𝒞(u)=N𝒞-{K}(u). For all N𝒞(u)∈Nmid𝒞(z), by the condition and Lemma 4.11, we have that N𝒞(u)=Nℬ(u). Since ℬ⊆𝒞-{K}⊆𝒞, it follows by Definition 2.3 that N𝒞(u)⊆N𝒞-{K}(u)⊆Nℬ(u)=N𝒞(u). Thus N𝒞(u)=N𝒞-{K}(u).(iii)
We will show thatNmid𝒞(x)⊆Nmid𝒞-{K}(x). For all N𝒞(u)∈Nmid𝒞(x), then by Definition 3.1, u∈N𝒞(x). By N𝒞(x)⊆N𝒞-{K}(x), we have that u∈N𝒞-{K}(x). Thus suppose that N𝒞-{K}(u)∉Nmid𝒞-{K}(x). Then by Definition 3.1, there exists z∈U such that N𝒞-{K}(z)⊂N𝒞-{K}(u). By (ii), we have that N𝒞(u)=N𝒞-{K}(u), thus, N𝒞-{K}(z)⊂N𝒞(u). Clearly, N𝒞(z)⊆N𝒞-{K}(z), thus N𝒞(z)⊂N𝒞(u), which contradicts the fact that N𝒞(u)∈Nmid𝒞(x). Thus N𝒞-{K}(u)∈Nmid𝒞-{K}(x). It follows by (ii) that N𝒞(u)∈Nmid𝒞-{K}(x). Thus Nmid𝒞(x)⊆Nmid𝒞-{K}(x).(iv)
We will show thatNmid𝒞-{K}(x)⊆Nmid𝒞(x). For all N𝒞-{K}(u)∈Nmid𝒞-{K}(x). Since 𝒞-{K}⊆𝒞, it is clear that N𝒞(u)⊆N𝒞-{K}(u). By u∈N𝒞(u) and Lemma 3.5, there exists N𝒞(z)∈Nmid𝒞(u) such that N𝒞(z)⊆N𝒞(u). This implies that N𝒞(z)⊆N𝒞-{K}(u) and so z∈N𝒞-{K}(u). Thus by Proposition 3.9, N𝒞-{K}(z)=N𝒞-{K}(u). Further, by N𝒞(z)∈Nmid𝒞(u) and (ii), we have that N𝒞(z)=N𝒞-{K}(z). Thus N𝒞(z)=N𝒞-{K}(u). In addition, by Lemma 4.11, N𝒞(z)=Nℬ(z) and Nℬ(z)∈Nmidℬ(u). Thus Nℬ(z)=N𝒞-{K}(u) and so u∈Nℬ(z). It follows by Proposition 3.9 that Nℬ(z)=Nℬ(u) and so N𝒞-{K}(u)=Nℬ(u) and Nℬ(u)∈Nmidℬ(u). By Definition 3.1, it is clear that u∈N𝒞-{K}(x). Since B⊆𝒞-{K}, it follows that N𝒞-{K}(x)⊆Nℬ(x). Thus u∈Nℬ(x). It follows by Proposition 3.10 that Nℬ(u)∈Nmidℬ(x) and so N𝒞-{K}(u)∈Nmidℬ(x). Thus, by the condition Nmidℬ(x)=Nmid𝒞(x), we conclude that N𝒞-{K}(u)∈Nmid𝒞(x). It follows that Nmid𝒞-{K}(x)⊆Nmid𝒞(x).
By (iii) and (iv), we have thatNmid𝒞-{K}(x)=Nmid𝒞(x). We have proved that for allx∈U, Nmid𝒞-{K}(x)=Nmid𝒞(x). Thus by Definition 4.4, K is a reducible element of 𝒞.Corollary 4.13.
Let𝒞 be a covering of a universe  U,  K∈𝒞 a reducible element of  𝒞 and  K1∈𝒞-{K}. If  K1 is an irreducible element of  𝒞, then  K1 is an irreducible element of  𝒞-{K}.Proof.
Suppose thatK1 is a reducible element of 𝒞-{K}. Then by Definition 4.4, for allx∈U, Nmid𝒞-{K}(x)=Nmid𝒞-{K,K1}(x). In addition, since K is a reducible element of 𝒞, it follows from Definition 4.4 that for allx∈U, Nmid𝒞(x)=Nmid𝒞-{K}(x). Thus for allx∈U, Nmid𝒞(x)=Nmid𝒞-{K,K1}(x). Clearly, K1∈𝒞-(𝒞-{K,K1}), thus by Proposition 4.12, K1 is a reducible element of 𝒞, which contradicts the condition that K1 is an irreducible element of 𝒞. This completes the proof.The above proposition guarantees that omitting a reducible element in a covering will not make any current irreducible element reducible. Therefore, the set of all irreducible elements of𝒞 is constant. We denote this set by cor3(𝒞), that is, (4.1)cor3(C)={K∣Kis an irreducible element ofC}.The following result establishes the relationship betweencor3(𝒞) and red3(𝒞).Theorem 4.14.
Let𝒞 be a covering of a universe  U. Then  cor3(𝒞)=∩red3(𝒞).Proof.
LetK∈cor3(𝒞). Suppose that K∉∩red3(𝒞). Then there exists ℬ∈red3(𝒞) such that K∉ℬ. Hence K∈𝒞-ℬ. By Definition 4.6 and Proposition 4.12, this implies that K is a reducible element of 𝒞, which contradicts the fact that K∈cor3(𝒞). Hence K∈∩red3(𝒞) and so cor3(𝒞)⊆∩red3(𝒞). On the other hand, let K∈∩red3(𝒞). Suppose that K∉cor3(𝒞). Then K is a reducible element of 𝒞. By Definition 4.4, we have that for allx∈U, Nmid𝒞(x)=Nmid𝒞-{K}(x) and by Corollary 4.8, 𝒞-{K} is a covering of U. Thus by Theorem 4.9, there exists ℬ⊆𝒞-{K} such that ℬ is a reduct of 𝒞-{K}. By Definition 4.6, this implies that ℬ is an irreducible covering and for allx∈U, Nmidℬ(x)=Nmid𝒞-{K}(x). Thus for allx∈U, Nmidℬ(x)=Nmid𝒞(x) and ℬ is an irreducible covering. It follows from Definition 4.6 that ℬ is a reduct of 𝒞. Since ℬ⊆𝒞-{K}, it follows that K∉ℬ, which contradicts the fact that K∈∩red3(𝒞). Thus K∈cor3(𝒞), and so ∩red3(𝒞)⊆cor3(𝒞). In summary, cor3(𝒞)=∩red3(𝒞).The above result states that an element will not be reduced in any reduction procedure if and only if it is irreducible. Hence the irreducible elements will be reserved in any reduction procedure, that is to say,cor3(𝒞) is contained in any reduct of 𝒞. So we can compute the reduct of 𝒞 based on cor3(𝒞).Example 4.15.
LetU={x1,x2,x3,x4}, C1={x1}, C2={x1,x2,x3}, C3={x1,x2,x4}, C4={x1,x2,x3,x4}, and 𝒞={C1,C2,C3,C4}. Clearly, 𝒞 is a covering of U.
By Definition4.2, it easy to check that
(4.2)NmidC(x1)=NmidC(x2)=NmidC(x3)=NmidC(x4)={{x}}.
By Definition4.2, we can get that
(4.3)NmidC-{C1}(x1)=NmidC-{C1}(x2)=NmidC-{C1}(x3)=NmidC-{C1}(x4)={{x1,x2}}.
Hence 𝒞 and 𝒞-{C1} do not satisfy the condition for allx∈U, Nmid𝒞(x)=Nmid𝒞-{C1}(x). It follows from Definition 4.4 that C1 is an irreducible element of 𝒞.
By Definition4.2, we can get that
(4.4)NmidC-{C2}(x1)=NmidC-{C2}(x2)=NmidC-{C2}(x3)=NmidC-{C2}(x4)={{x1}}.
Hence
(4.5)NmidC(x1)=NmidC-{C2}(x1),NmidC(x2)=NmidC-{C2}(x2),NmidC(x3)=NmidC-{C2}(x3),NmidC(x4)=NmidC-{C2}(x4).
It follows from Definition 4.4 that C2 is a reducible element of 𝒞. In the same way, we can check that C3 and C4 are all reducible elements of 𝒞.
Hencecor3(𝒞)={C1}.
Since{C1,C2} and {C1,C3} are not coverings of U, it follows from Corollaries 4.8 and 4.13 that every element of {C1,C2,C3} is an irreducible. Thus {C1,C2,C3} is a reduct of 𝒞.
For{C1,C2,C4}, by Definition 4.2, it is easy to check that
(4.6)Nmid{C1,C2,C4}(x1)=Nmid{C1,C2,C4}-{C2}(x1),Nmid{C1,C2,C4}(x2)=Nmid{C1,C2,C4}-{C2}(x2),Nmid{C1,C2,C4}(x3)=Nmid{C1,C2,C4}-{C2}(x3),Nmid{C1,C2,C4}(x4)=Nmid{C1,C2,C4}-{C2}(x4).
It follows from Definition 4.4 that C2 is a reducible element of {C1,C2,C4}. Further, for {C1,C4}, by Corollaries 4.8 and 4.13, it is clear that C1 and C4 are all irreducible elements of {C1,C4}. Thus it is clear that {C1,C4} is a reduct of 𝒞. A similar analysis to {C1,C3,C4}, we can also get that {C1,C4} is a reduct of 𝒞.
To sum up,𝒞 has two reducts that are {C1,C2,C3} and {C1,C4}. It is easy to see that cor3(𝒞)={C1}={C1,C2,C3}∩{C1,C4}=∩red3(𝒞).The above example also illustrates that for a covering, the reduct is not unique.Remark 4.16.
Let𝒞 be a covering of a universe U. For ℬ∈red3(𝒞), for allK∈ℬ, by Definitions 4.4, 4.5, and 4.6, it is easy to see that ℬ and ℬ-{K} do not satisfy the condition for allx∈U, Nmidℬ(x)=Nmid𝒞(x). Thus by Theorem 3.13, we know that ℬ and ℬ-{K} cannot induce the same lower and upper approximation operations. This illustrates that for allℬ∈red3(𝒞), ℬ is a smallest covering that induces the same the third type of neighborhood-based rough sets.


## 4.2. Reduction of the Third Type of Neighborhood-Based Rough Sets

Throughout this subsection, we always assume that the rough set model which is discussed by us is the fourth type of neighborhood-based generalized rough sets. So the definitions of a reducible element, an irreducible covering and a reduct, are all based on the fourth type of neighborhood-based rough sets.Notation 1.
Let𝒞 be a covering of U. We write NM𝒞=∪{Nmad𝒞(x)∣x∈U}.By Theorem3.28, we know that if NM𝒞=NMℬ, then ℬ and 𝒞 generate the same the forth type of neighborhood-based lower and upper approximation operations. So we can give the following definition of a reducible element.Definition 4.17 (A reducible element about the fourth type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U and K∈𝒞. If NM𝒞=NM𝒞-{K}, we say that K is a reducible element of 𝒞. Otherwise, K is an irreducible element of 𝒞.Definition 4.18 (Irreducible covering about the fourth type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U. If every element of 𝒞 is an irreducible element, we say that 𝒞 is irreducible. Otherwise, 𝒞 is reducible.Definition 4.19 (Reduct about the fourth type of lower and upper approximation operations).
Let𝒞 be a covering of a universe U and ℬ⊆𝒞. If ℬ is irreducible and NMℬ=NM𝒞, we say that ℬ is a reduct of 𝒞. Let red4(𝒞)={ℬ∣ℬis a reduct of𝒞}.The following proposition is basic.Proposition 4.20.
Let𝒞 be a covering of a universe  U and  ℬ⊆𝒞. If  ℬ and  𝒞 satisfy the condition that  NMℬ=NM𝒞, then  ℬ is a covering of  U.Proof.
Suppose thatℬ is not a covering of U. Then ∪ℬ⊂U. Taking x0∈U-∪ℬ, by Definition 4.1, we have that for allu∈U, x0∉Nℬ(u). Thus for allNℬ(u)∈NMℬ, x0∉Nℬ(u). On the other hand, since 𝒞 is a covering of U, it follows from Definition 3.2 that ∪NM𝒞=U. Thus there exists NC(u)∈NM𝒞 such that x0∈NC(u). Hence NC(u)∉NMℬ and so NMℬ≠NM𝒞, which is a contradiction with the condition NMℬ=NM𝒞. Thus ℬ is a covering of U.Corollary 4.21.
Let𝒞 be a covering of a universe  U and  K∈𝒞. If  K is a reducible element of  𝒞, then  𝒞-{K} is still a covering of  U.Proof.
It comes directly from Definition4.17 and Proposition 4.20.In the following, we will illustrate that for a covering, the reduct always exists.Theorem 4.22.
Let𝒞 be a covering of a universe  U. Then there exists  ℬ⊆𝒞 such that  ℬ is a reduct of  𝒞.Proof.
The proof is similar to that of Theorem4.9.Now we show that every reduct and the initial covering induce the same lower and upper approximation operations.Theorem 4.23.
Let𝒞 be a covering of a universe  U. Then for all  ℬ∈red4(𝒞),  ℬ and  𝒞 generate the same the fourth type of neighborhood-based lower and upper approximations.Proof.
By Definition4.19 and Proposition 4.20, ℬ is a covering of U. Thus by Definition 4.19 and Theorem 3.28, for all ℬ∈red4(𝒞), ℬ and 𝒞 generate the same the fourth type of neighborhood-based lower and upper approximations.Lemma 4.24.
Let𝒞 be a covering of a universe  U and  ℬ⊆𝒞.  ℬ and  𝒞 satisfy the condition that  NMℬ=NM𝒞. Then  for allN𝒞(u)∈NM𝒞, we have that  N𝒞(u)=Nℬ(u) and  Nℬ(u)∈NMℬ.Proof.
By the conditions and Proposition4.20, we know that ℬ and 𝒞 are all coverings of U. Hence, in the following process of proof, we can use directly the concepts and conclusions obtained in Section 3.
LetN𝒞(u)∈NM𝒞. Then by NMℬ=NM𝒞, there exists Nℬ(v)∈NMℬ such that N𝒞(u)=Nℬ(v) and so u∈Nℬ(v). By Definition 2.3, it is clear that Nℬ(u)⊆Nℬ(v). In addition, since ℬ⊆𝒞, it follows from Definition 2.3 that N𝒞(u)⊆Nℬ(u). By N𝒞(u)=Nℬ(v), we have that Nℬ(v)⊆Nℬ(u). By Nℬ(v)∈NMℬ, Notation 1 and Definition 3.2, this implies Nℬ(v)=Nℬ(u). Thus N𝒞(u)=Nℬ(u) and Nℬ(u)∈NMℬ.Proposition 4.25.
Let𝒞 be a covering of a universe  U and  ℬ⊂𝒞.  ℬ and  𝒞 satisfy the condition that  NMℬ=NM𝒞. Then  for allK∈𝒞-ℬ,  K is a reducible element of  𝒞.Proof.
LetK∈𝒞-ℬ, then ℬ⊆𝒞-{K}⊆𝒞.(i)
We will show that𝒞-{K} and ℬ are two coverings of U. By the condition and Proposition 4.20, ℬ is a covering of U. Clearly, ℬ⊆𝒞-{K}, thus 𝒞-{K} is also a covering of U.By (i) and the condition, we know that𝒞, 𝒞-{K} and ℬ are all coverings of U. Hence, in the following process of proof, we can use directly the concepts and conclusions obtained in Section 3.(ii)
We will show thatNM𝒞⊆NM𝒞-{K}. For all N𝒞(u)∈NM𝒞, then by Lemma 4.24, N𝒞(u)=Nℬ(u) and Nℬ(u)∈NMℬ. Since ℬ⊆𝒞-{K}⊆𝒞, it follows from Definition 2.3 that N𝒞(u)⊆N𝒞-{K}(u)⊆Nℬ(u). Thus by N𝒞(u)=Nℬ(u), we have that N𝒞-{K}(u)=Nℬ(u). Suppose that N𝒞-{K}(u)∉NM𝒞-{K}. Then N𝒞-{K}(u)∉Nmad𝒞-{K}(u). Thus by Definition 3.2, there exists z∈U such that N𝒞-{K}(u)⊂N𝒞-{K}(z) and so Nℬ(u)⊂N𝒞-{K}(z), which contradicts the fact that Nℬ(u)∈NMℬ. Thus N𝒞-{K}(u)∈NM𝒞-{K}. Combining N𝒞(u)=Nℬ(u) and N𝒞-{K}(u)=Nℬ(u), we can get that N𝒞(u)=N𝒞-{K}(u) and so N𝒞(u)∈NM𝒞-{K}. Thus, NM𝒞⊆NM𝒞-{K}.(iii)
We will show thatNM𝒞-{K}⊆NM𝒞, for allN𝒞-{K}(u)∈NM𝒞-{K}. By ℬ⊆𝒞-{K}, it is clear that N𝒞-{K}(u)⊆Nℬ(u). By u∈Nℬ(u) and Proposition 3.18, there exists Nℬ(z)∈Nmadℬ(u) such that Nℬ(u)⊆Nℬ(z). This implies N𝒞-{K}(u)⊆Nℬ(z). By Notation 1, it is clear that Nℬ(z)∈NMℬ. Since NMℬ=NM𝒞, it follows that there exists N𝒞(v)∈NM𝒞 such that Nℬ(z)=N𝒞(v). Thus N𝒞-{K}(u)⊆N𝒞(v). Clearly, N𝒞(v)⊆N𝒞-{K}(v), hence N𝒞-{K}(u)⊆N𝒞(v)⊆N𝒞-{K}(v). In addition, since N𝒞-{K}(u)∈NM𝒞-{K}, it follows from Notation 1 and Definition 3.2 that N𝒞-{K}(u)=N𝒞-{K}(v). This implies that N𝒞-{K}(u)=N𝒞(v). It follows by N𝒞(v)∈NM𝒞 that N𝒞-{K}(u)∈NM𝒞. Thus NM𝒞-{K}⊆NM𝒞.
By (ii) and (iii), we have thatNM𝒞-{K}=NM𝒞. Thus by Definition 4.17, K is a reducible element of 𝒞.Corollary 4.26.
Let𝒞 be a covering of a universe  U,  K∈𝒞 a reducible element of  𝒞 and  K1∈𝒞-{K}. If  K1 is an irreducible element of  𝒞, then  K1 is an irreducible element of  𝒞-{K}.Proof.
Suppose thatK1 is a reducible element of 𝒞-{K}. Then by Definition 4.17, NM𝒞-{K}=NM𝒞-{K,K1}. Since K is a reducible element of 𝒞, it follows from Definition 4.17 that NM𝒞=NM𝒞-{K}. Thus NM𝒞=NM𝒞-{K,K1}. Clearly, K1∈𝒞-(𝒞-{K,K1}), thus by Proposition 4.25, K1 is a reducible element of 𝒞, which contradicts the condition that K1 is an irreducible element of 𝒞. This completes the proof.The above proposition guarantees that omitting a reducible element in a covering will not make any current irreducible element reducible. Therefore, for a covering𝒞, the set of all irreducible elements is constant. We denote this set by cor4(𝒞), that is, (4.7)cor4(C)={K∣Kis an irreducible element ofC}.Theorem 4.27.
Let𝒞 be a covering of a universe  U. Then  cor4(𝒞)=∩red4(𝒞).Proof.
The proof is similar to that of Theorem4.14.The above result states that an element will not be reduced in any reduction procedure if and only if it is irreducible. Hence the irreducible elements will be reserved in any reduction procedure, that is to say,cor4(𝒞) is contained in any reduct of 𝒞. So we can compute the reduct of 𝒞 based on cor4(𝒞).Example 4.28.
LetU={x1,x2,x3,x4}, C1={x1,x2,x3}, C2={x1,x2,x4}, C3={x1,x2}, C4={x3}, C5={x4}, and 𝒞={C1,C2,C3,C4,C5}. Clearly, 𝒞 is a covering of U.
By Definition4.3 and Notation 1, it is easy to see that NM𝒞={{x1,x2},{x3},{x4}}.
SinceNM𝒞-{C1}={{x1,x2},{x3},{x4}}, it follows that NM𝒞=NM𝒞-{C1}. Thus C1 is a reducible element of 𝒞. In the same way, we can check that C2 and C3 are reducible elements of 𝒞.
SinceNM𝒞-{C4}={{x1,x2,x3},{x4}}, it follows that NM𝒞≠NM𝒞-{C4}. Thus C4 is an irreducible element of 𝒞.
SinceNM𝒞-{C5}={{x1,x2,x4},{x3}}, it follows that NM𝒞≠NM𝒞-{C5}. Thus C5 is an irreducible element of 𝒞.
Hencecor4(𝒞)={C4,C5}.
It is easy to check thatNM{C1,C2,C4,C5}≠NM{C2,C4,C5} and NM{C1,C2,C4,C5}≠NM{C1,C4,C5}. Thus C1 and C2 are irreducible elements of {C1,C2,C4,C5}. By Corollary 4.26, C4 and C5 are also irreducible elements of {C1,C2,C4,C5}. Hence {C1,C2,C4,C5} is an irreducible covering of U. It follows that {C1,C2,C4,C5} is a reduct of 𝒞.
It is easy to check thatNM{C1,C3,C4,C5}=NM{C3,C4,C5} and NM{C1,C3,C4,C5}≠NM{C1,C4,C5}. Thus C1 is a reducible element of {C1,C3,C4,C5}, and C3 is an irreducible element of {C1,C3,C4,C5}. Further, by Corollary 4.26, {C3,C4,C5} is an irreducible covering. Further, it is easy to verify that NM𝒞=NM{C3,C4,C5}. Hence {C3,C4,C5} is a reduct of 𝒞. A similar analysis to {C2,C3,C4,C5}, we can also get that {C3,C4,C5} is a reduct of 𝒞.
To sum up,𝒞 has two reducts that are {C1,C2,C3,C4} and {C3,C4,C5}. It is easy to see that cor4(𝒞)={C3,C4}={C1,C2,C3,C4}∩{C3,C4,C5}=∩red4(𝒞).Remark 4.29.
Let𝒞 be a covering of a universe U. For ℬ∈red4(𝒞), for allK∈ℬ, by Definitions 4.17, 4.18, and 4.19, it is easy to see that ℬ and ℬ-{K} do not satisfy the condition for allx∈U, Nmidℬ(x)=Nmid𝒞(x). Thus by Theorem 3.28, we know that ℬ and ℬ-{K} cannot induce the same lower and upper approximation operations. This illustrates that for allℬ∈red4(𝒞), ℬ is a smallest covering that induces the same the fourth type of neighborhood-based rough sets.


## 5. The Two Open Problems

In [28], Yun et al. proposed two open problems how to give sufficient and necessary conditions for {N(x)∣x∈U} to form a partition of U by using only a single covering approximation operator 𝒞i(i=1,4). That is to say, the first one is how to characterize the conditions for {N(x)∣x∈U} to form a partition by applying the first type of generalized approximation operator, and the second one is how to characterize the conditions for {N(x)∣x∈U} to form a partition by applying the fourth type of generalized approximation operator. In this section, we present some conditions under which {N(x)∣x∈U} forms a partition of U. As a result, the two open problems are solved (see Theorems 5.3 and 5.4).Lemma 5.1.
Let𝒞 be a covering of a universe  U. If  {N(x)∣x∈U} forms a partition of  U, then  for allx∈U,  N(x)∩(∪{K∣K∈𝒞,x∉K})=∅.Proof.
Letx∈U. Suppose that N(x)∩(∪{K∣K∈𝒞,x∉K})≠∅. Then we choose u∈N(x)∩(∪{K∣K∈𝒞,x∉K}), that is, u∈N(x) and u∈∪{K∣K∈𝒞,x∉K}. Thus there exists K∈{K∣K∈𝒞,x∉K} such that u∈K. By Definition 2.3, this implies that N(u)⊆K. On the other hand, since {N(x)∣x∈U} forms a partition of U, it follows from u∈N(x) that N(u)=N(x) and so x∈N(u). Thus x∈K. This is a contradiction with K∈{K∣K∈𝒞,x∉K}. Therefore, N(x)∩(∪{K∣K∈𝒞,x∉K})=∅.Lemma 5.2.
Let𝒞 be a covering of a universe  U and  x,z∈U. If  N(z)⊆N(x), then  {K∈𝒞∣z∉K}⊆{K∈𝒞∣x∉K}.Proof.
LetK∈{K∈𝒞∣z∉K}. Suppose that K∉{K∈𝒞∣x∉K}. Then x∈K. By Definition 2.3, this implies that N(x)⊆K. Since N(z)⊆N(x), it follows that N(z)⊆K and so z∈K, which contradicts the fact that K∈{K∈𝒞∣z∉K}. Thus K∈{K∈𝒞∣x∉K}. Hence {K∈𝒞∣z∉K}⊆{K∈𝒞∣x∉K}.Theorem 5.3.
Let𝒞 be a covering of a universe  U. Then  {N(x)∣x∈U} forms a partition of  U if and only if for each  x∈U,  𝒞1¯({x})=N(x).Proof.
Letx∈U. By Lemma 5.1, we have that N(x)∩(∪{K∣K∈𝒞,x∉K})=∅. This implies that N(x)⊆~(∪{K∣K∈𝒞,x∉K}). In addition, by the part (1) of Definition 2.4, we have that ~(∪{K∣K∈𝒞,x∉K})=~(∪{K∣K∈𝒞,K⊆~{x}})=𝒞1¯({x}). Consequently, N(x)⊆𝒞1¯({x}). On the other hand, for ally∈𝒞1¯({x}), then y∈~(∪{K∣K∈𝒞,K⊆~{x}}). Thus y∉∪{K∣K∈𝒞,K⊆~{x}}, that is, y∉∪{K∣K∈𝒞,x∉K}. This implies that for allK∈𝒞, x∉K⇒y∉K. Thus for allK∈𝒞, y∈K⇒x∈K. This implies that {K∣K∈𝒞,y∈K}⊆{K∣K∈𝒞,x∈K} and so ∩{K∣K∈𝒞,y∈K}⊇∩{K∣K∈𝒞,x∈K}, that is, N(y)⊇N(x). Since {N(x)∣x∈U} forms a partition of U, it follows that N(y)=N(x) and so y∈N(x). Thus 𝒞1¯({x})⊆N(x). In summary, 𝒞1¯({x})=N(x). This completes the proof of the necessity.
Conversely, suppose that{N(x)∣x∈U} is not a partition of U. Then there exist N(x),N(y)∈{N(x)∣x∈U} such that N(x)≠N(y) and N(x)∩N(y)≠∅. Taking z∈N(x)∩N(y), then N(z)⊆N(x)∩N(y). Clearly, N(z)≠N(x) or N(z)≠N(y). Without loss of generality, we may assume that N(z)≠N(x), then N(z)⊂N(x). Thus, by Lemma 5.2, we have that {K∈𝒞∣z∉K}⊆{K∈𝒞∣x∉K}. Thus ~(∪{K∈𝒞∣z∉K})⊇~(∪{K∈𝒞∣x∉K}) and so ~(∪{K∈𝒞∣K⊆~{z}})⊇~(∪{K∈𝒞∣K⊆~{x}}). It follows from the part (1) of Definition 2.4 that 𝒞1¯({z})⊇𝒞1¯({x}). By the condition, we have that 𝒞1¯({z})=N(z) and 𝒞1¯({x})=N(x). Thus N(z)⊇N(x), which contradicts with N(z)⊂N(x). Hence {N(x)∣x∈U} forms a partition of U.In fact, the above theorem establishes the relationship between the first type of generalized rough sets and the other types of neighborhood-based rough sets.Theorem 5.4.
Let𝒞 be a covering of a universe  U. Then  {N(x)∣x∈U} forms a partition of  U if and only if for each  x∈U,  𝒞4¯(N(x))=N(x).Proof.
The necessity is obvious.
Conversely, suppose that{N(x)∣x∈U} is not a partition of U. Then there exist N(x),N(y)∈{N(x)∣x∈U} such that N(x)≠N(y) and N(x)∩N(y)≠∅. Taking z∈N(x)∩N(y), then N(z)⊆N(x)∩N(y). Clearly, N(z)≠N(x) or N(z)≠N(y). Without loss of generality, we may assume that N(z)≠N(x), then N(z)⊂N(x). Thus x∉N(z) (Otherwise, by Definition 2.3, N(x)⊆N(z)). In addition, clearly, N(x)∩N(z)≠∅; therefore, by the part (4) of Definition 2.4, we have that x∈𝒞4¯(N(z)). Thus 𝒞4¯(N(z))≠N(z), which contradicts the condition for allx∈U, 𝒞4¯(N(x))=N(x). Thus {N(x)∣x∈U} forms a partition of U.


## 6. Conclusions

This paper defines the concepts of minimal neighborhood description and maximal neighborhood description in neighborhood-based rough set models. We give the new characterizations of the third and the fourth types of neighborhood-based rough sets. By means of these new characterizations, we explore the covering reduction of two types of neighborhood-based rough sets and have shown that the reduct of a covering is the minimal covering that generates the same lower and upper approximations. Clearly, the notions of minimal neighborhood description and maximal neighborhood description play essential roles in the studies of the reduction issues of the third and the fourth types of neighborhood-based rough sets. In fact, the two concepts are the essential characteristics related to the neighborhood-based rough sets. In particular, the notion of maximal neighborhood description is very useful. A similar notion was also discussed in [30]. In the future, we will further study neighborhood-based rough sets by means of these concepts.



---

*Source: 409181-2011-10-24.xml*