# Geometric Lattice Structure of Covering and Its Application to Attribute Reduction through Matroids

Authors: Aiping Huang; William Zhu
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The reduction of covering decision systems is an important problem in data mining,
and covering-based rough sets serve as an efficient technique to process the problem.
Geometric lattices have been widely used in many fields, especially greedy algorithm
design which plays an important role in the reduction problems. Therefore, it is meaningful
to combine coverings with geometric lattices to solve the optimization problems.
In this paper, we obtain geometric lattices from coverings through matroids and then
apply them to the issue of attribute reduction. First, a geometric lattice structure of a
covering is constructed through transversal matroids. Then its atoms are studied and
used to describe the lattice. Second, considering that all the closed sets of a finite matroid
form a geometric lattice, we propose a dependence space through matroids and
study the attribute reduction issues of the space, which realizes the application of geometric
lattices to attribute reduction. Furthermore, a special type of information system
is taken as an example to illustrate the application. In a word, this work points out an
interesting view, namely, geometric lattice, to study the attribute reduction issues of
information systems.


---

## Body

## 1. Introduction

Rough set theory [1], based on equivalence relations, was proposed by Pawlak to deal with the vagueness and incompleteness of knowledge in information systems. It has been widely applied to many practical applications in various areas, such as attribute reductions [2–4] and rule extractions [5]. In order to extend rough set theory's applications, some scholars have extended the theory to generalized rough set theory based on tolerance relation [6], similarity relation [7], and arbitrary binary relation [8, 9]. Through extending a partition to a covering, rough set theory has been generalized to covering-based rough set theory [9, 10]. Because of its high efficiency in many complicated problems such as knowledge reduction and rule learning in incomplete information system, covering-based rough set theory has been attracting increasing research interest [11–18].A lattice is suggested by the form of the Hasse diagram depicting it. In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum (also called a least upper bound or join) and a unique infimum (also called a greatest lower bound or meet). They encode the algebraic behavior of the entailment relation and such basic logical connectives as “and” (conjunction) and “or” (disjunction), which results in adequate algebraic semantics for a variety of logical systems. Lattices, especially geometric lattices, are important algebraic structures and are used extensively in both theoretical and applicable fields, such as rough sets [19, 20], formal concept analysis [21–23], and domain theory [24, 25].Matroid theory [26, 27] borrows extensively from linear algebra and graph theory. There are dozens of equivalent ways to characterize a matroid. Significant definitions of a matroid include those in terms of independent sets, bases, circuits, closed sets or flats, and rank functions, which provides well-established platforms to connect with other theories. In applications, matroids have been widely used in many fields such as combinatorial optimization, network flows, and algorithm design, especially greedy algorithm design [28, 29]. Studying rough sets with matroids is helpful to enrich the theory system and to extend the applications of rough sets. Some works on the connection between rough sets and matroids have been conducted [30–39].In this paper, we pay our attention to geometric lattice structures of coverings and their applications to attribute reduction issues of information systems. First, a geometric lattice of a covering is constructed through the transversal matroid induced by the covering. Then its atoms are studied and used to characterize the lattice structure. It is interesting that any element of the lattice can be expressed as the union of all closures of single-point sets in the element. Second, we apply the obtained geometric lattice to attribute reduction issues in information systems. It is interesting that a subset of a finite nonempty set is a reduct of the information system if and only if it is a minimal set with respect to the property of containing an element from each nonempty complement of any coatom of the lattice.The rest of this paper is organized as follows. In Section2, we recall some fundamental concepts related to rough sets, lattices, and matroids. Section 3 presents a geometric lattice of a covering and characterizes the structure by the atoms of the lattice. In Section 4, we apply the obtained geometric lattices to the attribute reduction issues of information systems. Finally, this paper is concluded and further work is pointed out in Section 5.


## 2. Preliminaries

In this section, we review some basic concepts of rough sets, matroids, and geometric lattices.


### 2.1. Rough Sets

Rough set theory is a new mathematical tool for imprecise and incomplete data analysis. It uses equivalence relations (resp. partitions) to describe the knowledge we can master. In this subsection, we introduce some concepts of rough sets used in this paper.Definition 1 (covering and partition).
LetU be a universe and 𝒞 a family of subsets of U. If none of subsets in 𝒞 are empty and ⋃‍𝒞=U, then 𝒞 is called a covering of U. The element of 𝒞 is called a covering block. If 𝒫 is a covering of U and it is a family of pairwise disjoint subsets of U, then 𝒫 is called a partition of U.It is clear that a partition is certainly a covering, so the concept of a covering is an extension of the concept of a partition.Definition 2 (approximation operators [1]).
LetU be a finite set and R an equivalent relation (reflexive, symmetric, and transitive) on U. For all X⊆U, the lower and upper approximations of X are, respectively, defined as follows:
(1)R*(X)={x∈U:[x]R⊆X},R*(X)={x∈U:[x]R⋂‍X≠∅},
where [x]R is called the equivalence class of x with respect to R.


### 2.2. Matroids

Matroid theory borrows extensively from the terminology of linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields, such as independent sets, bases, and the rank function.Definition 3 (matroid [27]).
A matroid is an ordered pair(U,ℐ) consisting of a finite set U and a collection ℐ of subsets of U satisfying the following three conditions.(I1)
∅∈ℐ.(I2)
IfI∈ℐ and I′⊆I, then I′∈ℐ.(I3)
IfI1,I2∈ℐ and |I1|<|I2|, then there is an element e∈I2-I1 such that I1⋃‍{e}∈ℐ, where |X| denotes the cardinality of X.LetM=(U,ℐ) be a matroid. The members of ℐ are the independent sets of M. A set in ℐ which is maximal in the sense of inclusion is called a based of M. If X∉ℐ, X is called a dependent set of M. In the sense of inclusion, a minimal dependent subset of U is called a circuit of M. The collections of the bases and the circuits of matroid M are denoted by ℬ(M) and 𝒞(M), respectively. The rank function of matroid M is a function rM:2U→N defined by rM(X)=max⁡{|I|:I⊆X,I∈ℐ}, where X⊆U. For each X⊆U, we say that clM(X)={a∈U:rM(X)=rM(X⋃‍{a})} is the closure of X in M. If clM(X)=X, X is called a closed set of M. For any X⊆U, if clM(X)=X and rM(X)=rM(U)-1, then X is called a hyperplane in M. The rank function of a matroid, directly analogous to a similar theorem of linear algebra, has the following proposition.Proposition 4 (rank axiom [27]).
LetU be a set. A function r:2U→N is the rank function of a matroid on U if and only if it satisfies the following conditions.(R1)
For allX⊆U,0≤r(X)≤|X|.(R2)
IfX⊆Y⊆U, thenr(X)≤r(Y).(R3)
IfX,Y⊆U, thenr(X⋃‍Y)+r(X⋂‍Y)≤r(X)+r(Y).The following proposition is the closure axiom of a matroid. It means that an operator satisfies the following four conditions if and only if it is the closure operator of a matroid.Proposition 5 (closure axiom [27]).
LetU be a set. A function cl:2U→2U is the closure operator of a matroid on U if and only if it satisfies the following conditions.(1)
IfX⊆U, thenX⊆cl(X).(2)
IfX⊆Y⊆U, thencl(X)⊆cl(Y).(3)
IfX⊆U,cl(cl(X))=cl(X).(4)
IfX⊆U, x∈U, andy∈cl(X⋃‍{x})-cl(X), thenx∈cl(X⋃‍{y}).Transversal theory is a branch of matroids. It shows how to induce a matroid, namely, transversal matroid from a family of subsets of a set. Hence, transversal matroids establish a bridge between a collection of subsets of a set and a matroid.Definition 6 (transversal [27]).
LetS be a nonempty finite set and J={1,2,…,m}. ℱ={F1,F2,…,Fm} denotes a family of subsets of S. A transversal or system of distinct representatives of {F1,F2,…,Fm} is a subset {e1,e2,…,em} of S such that ei∈Fi for all i∈J. If, for a subset K of J, X is a transversal of {Fi:i∈K}, then X is called a partial transversal of {F1,F2,…,Fm}.Example 7.
LetS={1,2,3,4,5}, F1={1,3}, F2={2,3}, and F3={3,4}. For ℱ={F1,F2,F3}, T={2,3,4} is a transversal of ℱ because 2∈F2, 3∈F1, and 4∈F3. T′={2,4} is a partial transversal of ℱ because there exists a subset of ℱ, that is, {F2,F3}, such that T′ is a transversal of it.The following proposition shows what kind of matroid is a transversal matroid.Proposition 8 (transversal matroid [27]).
Letℱ={Fi:i∈J} be a family of subsets of U. M(ℱ)=(U,ℐ(ℱ)) is a matroid, where ℐ(ℱ) is the family of all partial transversals of ℱ. One calls M(ℱ)=(U,ℐ(ℱ)) the transversal matroid induced by ℱ.Example 9 (continued from Example7).
M
(
ℱ
)
=
(
U
,
ℐ
(
ℱ
)
) is a matroid, where ℐ(ℱ)={∅,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4}}.


### 2.3.  Geometric Lattice

A lattice is a poset(ℒ,≤) such that, for every pair of elements, the least upper bound and greatest lower bound of the pair exist. Formally, if x and y are arbitrary elements of ℒ, then ℒ contains elements x∨y and x∧y. The element a of ℒ is an atom of lattice (ℒ,≤) if it satisfies the condition: 0<a and there is no x∈ℒ such that 0<x<a. The element a of ℒ is a coatom of lattice (ℒ,≤) if it satisfies the condition a<1 and there is no x∈ℒ such that a<x<1. The following lemma gives another definition of a geometric lattice from the viewpoint of matroids. In fact, the set of all closed sets of a matroid, ordered by inclusion, is a geometric lattice.Proposition 10 (see [27]).
A latticeℒ is a geometric lattice if and only if it is the lattice of closed sets of a matroid.The above proposition indicates that(ℒ(M),⊆) is a geometric lattice, where ℒ(M) denotes the collection of all closed sets of matroid M. The operations join and meet of the lattice are, respectively, defined as X∧Y=X⋂‍Y and X∨Y=clM(X⋃‍Y) for all X,Y∈ℒ(M). Moreover, the height of any element of the lattice is equal to the rank of the element in M. As we know, the atoms of a lattice are precisely the elements of height one. Therefore, the collection of the atoms of the lattice is the family of the sets which are closed sets of matroid M and have value 1 as their ranks.


## 2.1. Rough Sets

Rough set theory is a new mathematical tool for imprecise and incomplete data analysis. It uses equivalence relations (resp. partitions) to describe the knowledge we can master. In this subsection, we introduce some concepts of rough sets used in this paper.Definition 1 (covering and partition).
LetU be a universe and 𝒞 a family of subsets of U. If none of subsets in 𝒞 are empty and ⋃‍𝒞=U, then 𝒞 is called a covering of U. The element of 𝒞 is called a covering block. If 𝒫 is a covering of U and it is a family of pairwise disjoint subsets of U, then 𝒫 is called a partition of U.It is clear that a partition is certainly a covering, so the concept of a covering is an extension of the concept of a partition.Definition 2 (approximation operators [1]).
LetU be a finite set and R an equivalent relation (reflexive, symmetric, and transitive) on U. For all X⊆U, the lower and upper approximations of X are, respectively, defined as follows:
(1)R*(X)={x∈U:[x]R⊆X},R*(X)={x∈U:[x]R⋂‍X≠∅},
where [x]R is called the equivalence class of x with respect to R.


## 2.2. Matroids

Matroid theory borrows extensively from the terminology of linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields, such as independent sets, bases, and the rank function.Definition 3 (matroid [27]).
A matroid is an ordered pair(U,ℐ) consisting of a finite set U and a collection ℐ of subsets of U satisfying the following three conditions.(I1)
∅∈ℐ.(I2)
IfI∈ℐ and I′⊆I, then I′∈ℐ.(I3)
IfI1,I2∈ℐ and |I1|<|I2|, then there is an element e∈I2-I1 such that I1⋃‍{e}∈ℐ, where |X| denotes the cardinality of X.LetM=(U,ℐ) be a matroid. The members of ℐ are the independent sets of M. A set in ℐ which is maximal in the sense of inclusion is called a based of M. If X∉ℐ, X is called a dependent set of M. In the sense of inclusion, a minimal dependent subset of U is called a circuit of M. The collections of the bases and the circuits of matroid M are denoted by ℬ(M) and 𝒞(M), respectively. The rank function of matroid M is a function rM:2U→N defined by rM(X)=max⁡{|I|:I⊆X,I∈ℐ}, where X⊆U. For each X⊆U, we say that clM(X)={a∈U:rM(X)=rM(X⋃‍{a})} is the closure of X in M. If clM(X)=X, X is called a closed set of M. For any X⊆U, if clM(X)=X and rM(X)=rM(U)-1, then X is called a hyperplane in M. The rank function of a matroid, directly analogous to a similar theorem of linear algebra, has the following proposition.Proposition 4 (rank axiom [27]).
LetU be a set. A function r:2U→N is the rank function of a matroid on U if and only if it satisfies the following conditions.(R1)
For allX⊆U,0≤r(X)≤|X|.(R2)
IfX⊆Y⊆U, thenr(X)≤r(Y).(R3)
IfX,Y⊆U, thenr(X⋃‍Y)+r(X⋂‍Y)≤r(X)+r(Y).The following proposition is the closure axiom of a matroid. It means that an operator satisfies the following four conditions if and only if it is the closure operator of a matroid.Proposition 5 (closure axiom [27]).
LetU be a set. A function cl:2U→2U is the closure operator of a matroid on U if and only if it satisfies the following conditions.(1)
IfX⊆U, thenX⊆cl(X).(2)
IfX⊆Y⊆U, thencl(X)⊆cl(Y).(3)
IfX⊆U,cl(cl(X))=cl(X).(4)
IfX⊆U, x∈U, andy∈cl(X⋃‍{x})-cl(X), thenx∈cl(X⋃‍{y}).Transversal theory is a branch of matroids. It shows how to induce a matroid, namely, transversal matroid from a family of subsets of a set. Hence, transversal matroids establish a bridge between a collection of subsets of a set and a matroid.Definition 6 (transversal [27]).
LetS be a nonempty finite set and J={1,2,…,m}. ℱ={F1,F2,…,Fm} denotes a family of subsets of S. A transversal or system of distinct representatives of {F1,F2,…,Fm} is a subset {e1,e2,…,em} of S such that ei∈Fi for all i∈J. If, for a subset K of J, X is a transversal of {Fi:i∈K}, then X is called a partial transversal of {F1,F2,…,Fm}.Example 7.
LetS={1,2,3,4,5}, F1={1,3}, F2={2,3}, and F3={3,4}. For ℱ={F1,F2,F3}, T={2,3,4} is a transversal of ℱ because 2∈F2, 3∈F1, and 4∈F3. T′={2,4} is a partial transversal of ℱ because there exists a subset of ℱ, that is, {F2,F3}, such that T′ is a transversal of it.The following proposition shows what kind of matroid is a transversal matroid.Proposition 8 (transversal matroid [27]).
Letℱ={Fi:i∈J} be a family of subsets of U. M(ℱ)=(U,ℐ(ℱ)) is a matroid, where ℐ(ℱ) is the family of all partial transversals of ℱ. One calls M(ℱ)=(U,ℐ(ℱ)) the transversal matroid induced by ℱ.Example 9 (continued from Example7).
M
(
ℱ
)
=
(
U
,
ℐ
(
ℱ
)
) is a matroid, where ℐ(ℱ)={∅,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4}}.


## 2.3.  Geometric Lattice

A lattice is a poset(ℒ,≤) such that, for every pair of elements, the least upper bound and greatest lower bound of the pair exist. Formally, if x and y are arbitrary elements of ℒ, then ℒ contains elements x∨y and x∧y. The element a of ℒ is an atom of lattice (ℒ,≤) if it satisfies the condition: 0<a and there is no x∈ℒ such that 0<x<a. The element a of ℒ is a coatom of lattice (ℒ,≤) if it satisfies the condition a<1 and there is no x∈ℒ such that a<x<1. The following lemma gives another definition of a geometric lattice from the viewpoint of matroids. In fact, the set of all closed sets of a matroid, ordered by inclusion, is a geometric lattice.Proposition 10 (see [27]).
A latticeℒ is a geometric lattice if and only if it is the lattice of closed sets of a matroid.The above proposition indicates that(ℒ(M),⊆) is a geometric lattice, where ℒ(M) denotes the collection of all closed sets of matroid M. The operations join and meet of the lattice are, respectively, defined as X∧Y=X⋂‍Y and X∨Y=clM(X⋃‍Y) for all X,Y∈ℒ(M). Moreover, the height of any element of the lattice is equal to the rank of the element in M. As we know, the atoms of a lattice are precisely the elements of height one. Therefore, the collection of the atoms of the lattice is the family of the sets which are closed sets of matroid M and have value 1 as their ranks.


## 3. Geometric Lattice Structure of Covering through Matroids

As we know, a collection of all the closed sets of a matroid, in the sense of inclusion, is a geometric lattice. In this section, we convert a covering to a matroid through transversal matroids and then study the lattice of all the closed sets of the matroid. By this way, we realize the purpose to construct a geometric lattice structure from a covering.LetU be a nonempty and finite set and ℱ a collection of nonempty subsets of U. As shown in Proposition 8, M(ℱ) is the transversal matroid induced by ℱ and we denote the geometric lattice of ℱ by (ℒ(M(ℱ)),⊆). When ℱ is a covering 𝒞, the geometric lattice corresponding to it is denoted by (ℒ(M(𝒞)),⊆). For convenience, we substitute x for {x} in the following discussion.


### 3.1. Atoms of the Geometric Lattice Structure Induced by a Covering

Atoms of a geometric lattice are elements that are minimal among the nonzero elements and can be used to express the lattice. Therefore, atoms play an important role in the lattices. In this subsection, we study the atoms of the geometric lattice structure induced by a covering.A covering of universe of objects is the collection of some basic knowledge we master; therefore it is important to be studied in detail. The following theorem provides some equivalence characterizations for a covering from the viewpoint of matroids.Lemma 11 (see [27]).
LetM be a matroid of U and X⊆U. ThenrM(X)=rM(clM(X)).Lemma 12 (see [27]).
LetM be a matroid of U and X,Y⊆U. If X⊆Y and rM(X)=rM(Y), then clM(X)=clM(Y).Theorem 13.
Letℱ be a family of nonempty subsets of U and ℱ≠∅. The following statements are equivalent.(1)
ℱ is a covering of U.(2)
clℱ(∅)=∅.(3)
{clℱ(x):x∈U} is a partition of U.(4)
{clℱ(x):x∈U} is the collection of the atoms of (ℒ(M(ℱ)),⊆).Proof.
“(1)⇒(2)”: According to the definition of transversal matroids, any partial transversal is an independent set. Since ℱ is a covering, any single-point set is an independent set. Therefore, clM(ℱ)(∅)=∅.
“(2)⇒(4)”: For all x∈U, clM(ℱ)(clM(ℱ)(x))=clM(ℱ)(x), then clM(ℱ)(x)∈ℒ(M(ℱ)). Since clM(ℱ)(∅)=∅, any single-point set is an independent set; that is, for all x∈U, rM(ℱ)(x)=1. Utilizing Lemma 11, we have rM(ℱ)(clM(ℱ)(x))=rM(ℱ)(x)=1. Thus, for all x∈U, clM(ℱ)(x) is an atom of the lattice (ℒ(M(ℱ)),⊆). Conversely, if A is an atom of the lattice (ℒ(M(ℱ)),⊆), then clM(ℱ)(A)=A and rM(ℱ)(A)=1. It is clear that A≠∅. Pitch x∈A; then rM(ℱ)(x)=1=rM(ℱ)(A). Utilizing Lemma 12, we have clM(ℱ)(x)=clM(ℱ)(A)=A. Therefore, we have proved the result.
“(4)⇒(3)”: We firstly prove that, for all x,y∈U, if clM(ℱ)(x)⋂‍clM(ℱ)(y)≠∅, then clM(ℱ)(x)=clM(ℱ)(y). We may as well suppose z∈clM(ℱ)(x)⋂‍clM(ℱ)(y). Then clM(ℱ)(∅)⊆clM(ℱ)(z)⊆clM(ℱ)(x) and clM(ℱ)(∅)⊆clM(ℱ)(z)⊆clM(ℱ)(y). We conclude that clM(ℱ)(∅)≠clM(ℱ)(z). Otherwise, rM(ℱ)(clM(ℱ)(z))=rM(ℱ)(clM(ℱ)(∅))=rM(ℱ)(∅)=0, which contradicts that clM(ℱ)(z) is an atom. Thus clM(ℱ)(∅)⊂clM(ℱ)(z)⊆clM(ℱ)(x) and clM(ℱ)(∅)⊂clM(ℱ)(z)⊆clM(ℱ)(y). According to the definition of atoms, we have clM(ℱ)(x)=clM(ℱ)(z)=clM(ℱ)(y). For all x∈U, x∈clM(ℱ)(x), then clM(ℱ)(x)≠∅. Moreover, U=⋃x∈U‍{x}⊆⋃x∈U‍clM(ℱ)(x)⊆⋃x∈U‍U=U; that is, U=⋃x∈U‍clM(ℱ)(x). Hence {clM(ℱ)(x):x∈U} is a partition of U.
“(3)⇒(1)”: Since {clℱ(x):x∈U} is a partition of U, for any distinct elements clM(ℱ)(u) and clM(ℱ)(v) of {clM(ℱ)(x):x∈U}, clM(ℱ)(u)⋂‍clM(ℱ)(v)=∅. Thus clM(ℱ)(∅)⊆clM(ℱ)(u) and clM(ℱ)(∅)⊆clM(ℱ)(v). Hence clM(ℱ)(∅)⊆clM(ℱ)(u)⋂‍clM(ℱ)(v)=∅. As with ∅⊆clM(ℱ), we have clM(ℱ)(∅)=∅. Thus, for all x∈U, x is an independent set; that is, there exists Fx∈ℱ such that x∈Fx. Hence, U=⋃x∈U‍{x}⊆⋃x∈U‍Fx⊆⋃‍ℱ⊆U. Thus ⋃‍ℱ=U. Since ℱ is a family of nonempty subsets of U and ℱ≠∅, we know ∅∉F. Therefore, we have proved that ℱ is a covering of U.Theorem13 indicates that the closure of any single-point set is an atom of lattice ℒ(M(𝒞)). Based on the fact, we obtain all the atoms of the lattice from covering C directly.Definition 14 (see [20]).
Let𝒞={K1,K2,…,Km} be a covering of a finite set U={x1,x2,…,xn}. One defines(i)
A={Ki-⋃j=1,j≠im‍Kj:Ki-⋃j=1,j≠im‍Kj≠∅,i∈{1,2,…,m}}={A1,A2,…,As};(ii)
B=U-⋃i=1s‍Ai.Remark 15.
For alli∈{1,2,…,s} and x∈Ai, there exists only one block of covering C such that x belongs to it, and there exist at least two blocks of covering C such that y belongs to them for all y∈B.One example is provided to illustrate the above definition.Example 16.
LetU={1,2,3,4,5} and 𝒞={K1,K2,K3}, where K1={1,3}, K2={2,3}, and K3={3,4,5}. Then K1-K2⋃‍K3={1,3}-{2,3,4,5}={1}. In this way, we can obtain A={{1},{2},{4,5}} and B=U-⋃‍A=U-{1,2,4,5}={3}.In fact, the closure of any singleton set of universeU in matroid M(𝒞) is an element of A or a single-point set of B. In order to reveal the fact better, we need the two lemmas below.Lemma 17.
Let𝒞 be a covering of U. For all x∈U, there exists K∈𝒞 such that clM(𝒞)(x)⊆K.Proof.
For allx∈U, we take that K∈𝒞 satisfies x∈K then clM(𝒞)(x)⊆K. In fact, for all y∉K, there exists K′≠K such that y∈K′ because 𝒞 is a covering of U. That implies that {x,y} is an independent set because there exist K,K′∈𝒞 such that x∈K and y∈K′. Thus, rM(𝒞)({x,y})=2≠1=rM(𝒞)(x) which implies that y∉clM(𝒞)(x). Therefore, we prove the result.Lemma 18.
Let𝒞 be a covering of U. For all x∈U, if |clM(𝒞)(x)|≥2, then there exists only one block K of 𝒞 such that clM(𝒞)(x)⊆K.Proof.
According to Lemma17, we know there exists K∈𝒞 such that clM(𝒞)(x)⊆K for all x∈U. Now, we need to prove the uniqueness of K. Suppose there exists the other block K′ such that clM(𝒞)(x)⊆K′. We claim that clM(𝒞)(x)={x}; otherwise, there exists y≠x such that y∈clM(𝒞)(x) because we have had x∈clM(𝒞)(x). That implies that rM(ℱ)({x,y})=rM(𝒞)(x)=1. However, there exist two blocks K and K′ such that clM(𝒞)(x) is contained in them. Thus rM(𝒞)({x,y})=2, which implies a contradiction! Hence clM(𝒞)(x)={x}, that is, |clM(𝒞)(x)|=1, which contradicts the assumption |clM(𝒞)(x)|≥2.Proposition 19.
Let𝒞 be a covering of U. Then {clM(𝒞)(x):x∈U}={A1,A2,…,As}⋃‍{{x}:x∈B}.Proof.
For allclM(𝒞)(x)∈{clM(𝒞)(x):x∈U}, if |clM(𝒞)(x)|=1, then clM(𝒞)(x)={x} because x∈clM(𝒞)(x). Since 𝒞 is a covering, there exists a block K of 𝒞 such that x∈K. If K is a unique block of 𝒞 such that x∈K, then there exists Ai∈A such that x∈Ai. Moreover, Ai={x}; otherwise, there exists y≠x such that y∈Ai. According to the definition of Ai, we have rM(𝒞)({x,y})=rM(𝒞)(x), that is, y∈clM(𝒞)(x), which contradicts the assumption |clM(𝒞)(x)|=1. Hence clM(𝒞)(x)={x}=Ai. If K is not a unique block of 𝒞 such that x∈K, then x∉Ai for all i∈{1,2,…,s}. That implies that x∈B. Therefore, clM(𝒞)(x)={x}, where x∈B. If |clM(𝒞)(x)|≠1, then |clM(𝒞)(x)|≥2. According to Lemma 18, we know there exists only one block Ki such that clM(𝒞)(x)⊆Ki. According to the definition of A, there exists Aj∈A such that x∈clM(𝒞)(x)⊆Aj. For all y∈Aj and y≠x, we know rM(𝒞)({x,y})=rM(𝒞)(x). Thus y∈clM(𝒞)(x); that is, Aj⊆clM(𝒞)(x); therefore, Aj=clM(𝒞)(x). From the above discussion, we conclude that {clM(𝒞)(x):x∈U}⊆{A1,A2,…,As}⋃‍{{x}:x∈B}.
Next, we prove{A1,A2,…,As}⋃‍{{x}:x∈B}⊆{clM(𝒞)(x):x∈U}. For all Ai∈{A1,A2,…,As}, we know there exists a unique block K∈𝒞 such that Ai⊆K. Thus rM(𝒞)(Ai)=1. Pitch y∈Ai. Since 𝒞 is a covering, rM(𝒞)(y)=1. Thus rM(𝒞)(Ai)=rM(𝒞)(y). Utilizing Lemma 12, we have clM(𝒞)(y)=clM(𝒞)(Ai), which implies that Ai⊆clM(𝒞)(y). For all x∈clM(𝒞)(y), rM(𝒞)({x,y})=1; that is, there exists a unique block K of 𝒞 such that {x,y}⊆K. Thus x∈Ai. Therefore clM(𝒞)(y)⊆Ai which implies that {A1,A2,…,As}⊆{clM(𝒞)(x):x∈U}. For all x∈B, we claim that clM(𝒞)(x)={x}. Since {x}⊆clM(𝒞)(x), we just need to prove clM(𝒞)(x)⊆{x}; otherwise, there exists y∈U and y≠x such that y∈clM(𝒞)(x). Utilizing Lemma 18, there is only one block K of 𝒞 such that {x,y}⊆K. According to the definition of Ai(i∈{1,2,…,s}), we know there exists Aj(j∈{1,2,…,s}) such that x∈Aj, thus x∉B which contradicts the assumption that x∈B.The following result is the combination of Theorem13 and Proposition 19. It presents the atoms of lattice (ℒ(M(𝒞)),⊆) from covering C directly.Corollary 20.
Let𝒞 be a covering of U. {A1,A2,…,As}⋃‍{{x}:x∈B} is the family of atoms of lattice (ℒ(M(𝒞)),⊆).Corollary20 can also be found in [20]. It provides a method to obtain the atoms of the geometric lattice induced by a covering from the covering directly. We obtain the result from the other different perspective in this paper.Example 21 (continued from Example16).
Based on Corollary20, the collection of the atoms of lattice (ℒ(M(𝒞)),⊆) is {{1},{2},{3},{4,5}}.


### 3.2.  Atoms Characterization for the Geometric Lattice Induced by a Covering

In Section3.1, we have studied the atoms of the geometric lattice induced by a covering and have provided a method to obtain the atoms from the covering directly. As we know, any element of a geometric lattice can be expressed as the joint of some atoms of the lattice. In this subsection, we characterize the geometric lattice induced by a covering through the atoms of it by the union operation. In fact, any element of the lattice can be indicated as the union of all closures of single-point sets in the element. At the beginning of this subsection, we define two operators from the viewpoint of matroids.Definition 22.
LetM be a matroid on U and X⊆U. One can define the following two operators:
(2)LM(X)={x∈U:clM(x)⊆X},HM(X)={x∈U:clM(x)⋂‍X≠∅}.
One call the two operators are lower and upper approximation operators induced by M.In fact,clM(x) can be regarded as the successor neighborhood of x with respect to the relation RM defined as xRMy⇔y∈clM(x). It is clear that RM is a reflexive and transitive relation. When M=M(𝒞), the relation RM(𝒞) is an equivalence relation on U. Therefore, LM(𝒞)=(RM(𝒞))* and HM(𝒞)=(RM(𝒞))*. In the following discussion, we study the relationship between the two operators and the elements of the lattice ℒ(M(𝒞)). Then, based on the relationship, we realize the purpose to characterize the lattice through the atoms of it by using union operator. Firstly, we have the following lemma.Lemma 23.
LetR be an equivalence relation of U. For all X⊆U, if R*(X)=X, then R*(X)=X.Proof.
It is clear thatX={x∈U:[x]R⊆X}⊆{x∈U:[x]R⋂‍X≠∅}=R*(X). For all y∈R*(X), [y]R⋂‍X≠∅. Suppose z∈[y]R⋂‍X. Then y∈[y]R=[z]R⊆X; hence R*(X)⊆X.In fact, any closed set of the matroid induced by a covering is a fixed point of the two operators induced by the covering.Proposition 24.
Let𝒞 be a covering of U. If X∈ℒ(M(𝒞)), then LM(𝒞)(X)=X=HM(𝒞)(X).Proof.
Utilizing Lemma23, we need prove that X=LM(𝒞)(X). For all y∈LM(𝒞)(X), y∈clM(𝒞)(y)⊆X; thus LM(𝒞)(X)⊆X. Conversely, according to (2) of Proposition 5, we know for all y∈X, clM(𝒞)(y)⊆X. Thus X⊆LM(𝒞)(X). Hence X=LM(𝒞)(X).Based on the above result, any element of the geometric lattice induced by a covering can be expressed as the union of all closures of single-point sets in the element.Theorem 25.
Let𝒞 be a covering of U. For all X∈ℒ(M(𝒞)), X=⋃x∈X‍clM(𝒞)(x).Proof.
It is obvious whenX=∅. According to Proposition 24, we have X={x∈U:clM(𝒞)(x)⊆X}. Then x∈clM(𝒞)(x)⊆X for all x∈X. Thus X=⋃x∈X‍{x}⊆⋃x∈X‍clM(𝒞)(x)⊆X. Therefore X=⋃x∈X‍clM(𝒞)(x).Example 26.
Suppose𝒞 is the one shown in Example 16. According to Example 21 and Proposition 19, we have clM(𝒞)(∅)=∅, clM(𝒞)(1)={1}, clM(𝒞)(2)={2}, clM(𝒞)(3)={3}, and clM(𝒞)(4)=clM(𝒞)(5)={4,5}. Since X=⋃x∈X‍clM(𝒞)(x) for all X∈ℒ(M(𝒞)), we obtain ℒ(M(𝒞))={∅,{1},{2},{3},{4,5},{1,2},{1,3},{1,4,5},{2,3},{2,4,5},{3,4,5},{1,2,3,4,5}}, and the geometric lattice (ℒ(M(𝒞)),⊆) is shown in Figure 1.Figure 1
The geometric lattice of(ℒ(M(𝒞)),⊆).


## 3.1. Atoms of the Geometric Lattice Structure Induced by a Covering

Atoms of a geometric lattice are elements that are minimal among the nonzero elements and can be used to express the lattice. Therefore, atoms play an important role in the lattices. In this subsection, we study the atoms of the geometric lattice structure induced by a covering.A covering of universe of objects is the collection of some basic knowledge we master; therefore it is important to be studied in detail. The following theorem provides some equivalence characterizations for a covering from the viewpoint of matroids.Lemma 11 (see [27]).
LetM be a matroid of U and X⊆U. ThenrM(X)=rM(clM(X)).Lemma 12 (see [27]).
LetM be a matroid of U and X,Y⊆U. If X⊆Y and rM(X)=rM(Y), then clM(X)=clM(Y).Theorem 13.
Letℱ be a family of nonempty subsets of U and ℱ≠∅. The following statements are equivalent.(1)
ℱ is a covering of U.(2)
clℱ(∅)=∅.(3)
{clℱ(x):x∈U} is a partition of U.(4)
{clℱ(x):x∈U} is the collection of the atoms of (ℒ(M(ℱ)),⊆).Proof.
“(1)⇒(2)”: According to the definition of transversal matroids, any partial transversal is an independent set. Since ℱ is a covering, any single-point set is an independent set. Therefore, clM(ℱ)(∅)=∅.
“(2)⇒(4)”: For all x∈U, clM(ℱ)(clM(ℱ)(x))=clM(ℱ)(x), then clM(ℱ)(x)∈ℒ(M(ℱ)). Since clM(ℱ)(∅)=∅, any single-point set is an independent set; that is, for all x∈U, rM(ℱ)(x)=1. Utilizing Lemma 11, we have rM(ℱ)(clM(ℱ)(x))=rM(ℱ)(x)=1. Thus, for all x∈U, clM(ℱ)(x) is an atom of the lattice (ℒ(M(ℱ)),⊆). Conversely, if A is an atom of the lattice (ℒ(M(ℱ)),⊆), then clM(ℱ)(A)=A and rM(ℱ)(A)=1. It is clear that A≠∅. Pitch x∈A; then rM(ℱ)(x)=1=rM(ℱ)(A). Utilizing Lemma 12, we have clM(ℱ)(x)=clM(ℱ)(A)=A. Therefore, we have proved the result.
“(4)⇒(3)”: We firstly prove that, for all x,y∈U, if clM(ℱ)(x)⋂‍clM(ℱ)(y)≠∅, then clM(ℱ)(x)=clM(ℱ)(y). We may as well suppose z∈clM(ℱ)(x)⋂‍clM(ℱ)(y). Then clM(ℱ)(∅)⊆clM(ℱ)(z)⊆clM(ℱ)(x) and clM(ℱ)(∅)⊆clM(ℱ)(z)⊆clM(ℱ)(y). We conclude that clM(ℱ)(∅)≠clM(ℱ)(z). Otherwise, rM(ℱ)(clM(ℱ)(z))=rM(ℱ)(clM(ℱ)(∅))=rM(ℱ)(∅)=0, which contradicts that clM(ℱ)(z) is an atom. Thus clM(ℱ)(∅)⊂clM(ℱ)(z)⊆clM(ℱ)(x) and clM(ℱ)(∅)⊂clM(ℱ)(z)⊆clM(ℱ)(y). According to the definition of atoms, we have clM(ℱ)(x)=clM(ℱ)(z)=clM(ℱ)(y). For all x∈U, x∈clM(ℱ)(x), then clM(ℱ)(x)≠∅. Moreover, U=⋃x∈U‍{x}⊆⋃x∈U‍clM(ℱ)(x)⊆⋃x∈U‍U=U; that is, U=⋃x∈U‍clM(ℱ)(x). Hence {clM(ℱ)(x):x∈U} is a partition of U.
“(3)⇒(1)”: Since {clℱ(x):x∈U} is a partition of U, for any distinct elements clM(ℱ)(u) and clM(ℱ)(v) of {clM(ℱ)(x):x∈U}, clM(ℱ)(u)⋂‍clM(ℱ)(v)=∅. Thus clM(ℱ)(∅)⊆clM(ℱ)(u) and clM(ℱ)(∅)⊆clM(ℱ)(v). Hence clM(ℱ)(∅)⊆clM(ℱ)(u)⋂‍clM(ℱ)(v)=∅. As with ∅⊆clM(ℱ), we have clM(ℱ)(∅)=∅. Thus, for all x∈U, x is an independent set; that is, there exists Fx∈ℱ such that x∈Fx. Hence, U=⋃x∈U‍{x}⊆⋃x∈U‍Fx⊆⋃‍ℱ⊆U. Thus ⋃‍ℱ=U. Since ℱ is a family of nonempty subsets of U and ℱ≠∅, we know ∅∉F. Therefore, we have proved that ℱ is a covering of U.Theorem13 indicates that the closure of any single-point set is an atom of lattice ℒ(M(𝒞)). Based on the fact, we obtain all the atoms of the lattice from covering C directly.Definition 14 (see [20]).
Let𝒞={K1,K2,…,Km} be a covering of a finite set U={x1,x2,…,xn}. One defines(i)
A={Ki-⋃j=1,j≠im‍Kj:Ki-⋃j=1,j≠im‍Kj≠∅,i∈{1,2,…,m}}={A1,A2,…,As};(ii)
B=U-⋃i=1s‍Ai.Remark 15.
For alli∈{1,2,…,s} and x∈Ai, there exists only one block of covering C such that x belongs to it, and there exist at least two blocks of covering C such that y belongs to them for all y∈B.One example is provided to illustrate the above definition.Example 16.
LetU={1,2,3,4,5} and 𝒞={K1,K2,K3}, where K1={1,3}, K2={2,3}, and K3={3,4,5}. Then K1-K2⋃‍K3={1,3}-{2,3,4,5}={1}. In this way, we can obtain A={{1},{2},{4,5}} and B=U-⋃‍A=U-{1,2,4,5}={3}.In fact, the closure of any singleton set of universeU in matroid M(𝒞) is an element of A or a single-point set of B. In order to reveal the fact better, we need the two lemmas below.Lemma 17.
Let𝒞 be a covering of U. For all x∈U, there exists K∈𝒞 such that clM(𝒞)(x)⊆K.Proof.
For allx∈U, we take that K∈𝒞 satisfies x∈K then clM(𝒞)(x)⊆K. In fact, for all y∉K, there exists K′≠K such that y∈K′ because 𝒞 is a covering of U. That implies that {x,y} is an independent set because there exist K,K′∈𝒞 such that x∈K and y∈K′. Thus, rM(𝒞)({x,y})=2≠1=rM(𝒞)(x) which implies that y∉clM(𝒞)(x). Therefore, we prove the result.Lemma 18.
Let𝒞 be a covering of U. For all x∈U, if |clM(𝒞)(x)|≥2, then there exists only one block K of 𝒞 such that clM(𝒞)(x)⊆K.Proof.
According to Lemma17, we know there exists K∈𝒞 such that clM(𝒞)(x)⊆K for all x∈U. Now, we need to prove the uniqueness of K. Suppose there exists the other block K′ such that clM(𝒞)(x)⊆K′. We claim that clM(𝒞)(x)={x}; otherwise, there exists y≠x such that y∈clM(𝒞)(x) because we have had x∈clM(𝒞)(x). That implies that rM(ℱ)({x,y})=rM(𝒞)(x)=1. However, there exist two blocks K and K′ such that clM(𝒞)(x) is contained in them. Thus rM(𝒞)({x,y})=2, which implies a contradiction! Hence clM(𝒞)(x)={x}, that is, |clM(𝒞)(x)|=1, which contradicts the assumption |clM(𝒞)(x)|≥2.Proposition 19.
Let𝒞 be a covering of U. Then {clM(𝒞)(x):x∈U}={A1,A2,…,As}⋃‍{{x}:x∈B}.Proof.
For allclM(𝒞)(x)∈{clM(𝒞)(x):x∈U}, if |clM(𝒞)(x)|=1, then clM(𝒞)(x)={x} because x∈clM(𝒞)(x). Since 𝒞 is a covering, there exists a block K of 𝒞 such that x∈K. If K is a unique block of 𝒞 such that x∈K, then there exists Ai∈A such that x∈Ai. Moreover, Ai={x}; otherwise, there exists y≠x such that y∈Ai. According to the definition of Ai, we have rM(𝒞)({x,y})=rM(𝒞)(x), that is, y∈clM(𝒞)(x), which contradicts the assumption |clM(𝒞)(x)|=1. Hence clM(𝒞)(x)={x}=Ai. If K is not a unique block of 𝒞 such that x∈K, then x∉Ai for all i∈{1,2,…,s}. That implies that x∈B. Therefore, clM(𝒞)(x)={x}, where x∈B. If |clM(𝒞)(x)|≠1, then |clM(𝒞)(x)|≥2. According to Lemma 18, we know there exists only one block Ki such that clM(𝒞)(x)⊆Ki. According to the definition of A, there exists Aj∈A such that x∈clM(𝒞)(x)⊆Aj. For all y∈Aj and y≠x, we know rM(𝒞)({x,y})=rM(𝒞)(x). Thus y∈clM(𝒞)(x); that is, Aj⊆clM(𝒞)(x); therefore, Aj=clM(𝒞)(x). From the above discussion, we conclude that {clM(𝒞)(x):x∈U}⊆{A1,A2,…,As}⋃‍{{x}:x∈B}.
Next, we prove{A1,A2,…,As}⋃‍{{x}:x∈B}⊆{clM(𝒞)(x):x∈U}. For all Ai∈{A1,A2,…,As}, we know there exists a unique block K∈𝒞 such that Ai⊆K. Thus rM(𝒞)(Ai)=1. Pitch y∈Ai. Since 𝒞 is a covering, rM(𝒞)(y)=1. Thus rM(𝒞)(Ai)=rM(𝒞)(y). Utilizing Lemma 12, we have clM(𝒞)(y)=clM(𝒞)(Ai), which implies that Ai⊆clM(𝒞)(y). For all x∈clM(𝒞)(y), rM(𝒞)({x,y})=1; that is, there exists a unique block K of 𝒞 such that {x,y}⊆K. Thus x∈Ai. Therefore clM(𝒞)(y)⊆Ai which implies that {A1,A2,…,As}⊆{clM(𝒞)(x):x∈U}. For all x∈B, we claim that clM(𝒞)(x)={x}. Since {x}⊆clM(𝒞)(x), we just need to prove clM(𝒞)(x)⊆{x}; otherwise, there exists y∈U and y≠x such that y∈clM(𝒞)(x). Utilizing Lemma 18, there is only one block K of 𝒞 such that {x,y}⊆K. According to the definition of Ai(i∈{1,2,…,s}), we know there exists Aj(j∈{1,2,…,s}) such that x∈Aj, thus x∉B which contradicts the assumption that x∈B.The following result is the combination of Theorem13 and Proposition 19. It presents the atoms of lattice (ℒ(M(𝒞)),⊆) from covering C directly.Corollary 20.
Let𝒞 be a covering of U. {A1,A2,…,As}⋃‍{{x}:x∈B} is the family of atoms of lattice (ℒ(M(𝒞)),⊆).Corollary20 can also be found in [20]. It provides a method to obtain the atoms of the geometric lattice induced by a covering from the covering directly. We obtain the result from the other different perspective in this paper.Example 21 (continued from Example16).
Based on Corollary20, the collection of the atoms of lattice (ℒ(M(𝒞)),⊆) is {{1},{2},{3},{4,5}}.


## 3.2.  Atoms Characterization for the Geometric Lattice Induced by a Covering

In Section3.1, we have studied the atoms of the geometric lattice induced by a covering and have provided a method to obtain the atoms from the covering directly. As we know, any element of a geometric lattice can be expressed as the joint of some atoms of the lattice. In this subsection, we characterize the geometric lattice induced by a covering through the atoms of it by the union operation. In fact, any element of the lattice can be indicated as the union of all closures of single-point sets in the element. At the beginning of this subsection, we define two operators from the viewpoint of matroids.Definition 22.
LetM be a matroid on U and X⊆U. One can define the following two operators:
(2)LM(X)={x∈U:clM(x)⊆X},HM(X)={x∈U:clM(x)⋂‍X≠∅}.
One call the two operators are lower and upper approximation operators induced by M.In fact,clM(x) can be regarded as the successor neighborhood of x with respect to the relation RM defined as xRMy⇔y∈clM(x). It is clear that RM is a reflexive and transitive relation. When M=M(𝒞), the relation RM(𝒞) is an equivalence relation on U. Therefore, LM(𝒞)=(RM(𝒞))* and HM(𝒞)=(RM(𝒞))*. In the following discussion, we study the relationship between the two operators and the elements of the lattice ℒ(M(𝒞)). Then, based on the relationship, we realize the purpose to characterize the lattice through the atoms of it by using union operator. Firstly, we have the following lemma.Lemma 23.
LetR be an equivalence relation of U. For all X⊆U, if R*(X)=X, then R*(X)=X.Proof.
It is clear thatX={x∈U:[x]R⊆X}⊆{x∈U:[x]R⋂‍X≠∅}=R*(X). For all y∈R*(X), [y]R⋂‍X≠∅. Suppose z∈[y]R⋂‍X. Then y∈[y]R=[z]R⊆X; hence R*(X)⊆X.In fact, any closed set of the matroid induced by a covering is a fixed point of the two operators induced by the covering.Proposition 24.
Let𝒞 be a covering of U. If X∈ℒ(M(𝒞)), then LM(𝒞)(X)=X=HM(𝒞)(X).Proof.
Utilizing Lemma23, we need prove that X=LM(𝒞)(X). For all y∈LM(𝒞)(X), y∈clM(𝒞)(y)⊆X; thus LM(𝒞)(X)⊆X. Conversely, according to (2) of Proposition 5, we know for all y∈X, clM(𝒞)(y)⊆X. Thus X⊆LM(𝒞)(X). Hence X=LM(𝒞)(X).Based on the above result, any element of the geometric lattice induced by a covering can be expressed as the union of all closures of single-point sets in the element.Theorem 25.
Let𝒞 be a covering of U. For all X∈ℒ(M(𝒞)), X=⋃x∈X‍clM(𝒞)(x).Proof.
It is obvious whenX=∅. According to Proposition 24, we have X={x∈U:clM(𝒞)(x)⊆X}. Then x∈clM(𝒞)(x)⊆X for all x∈X. Thus X=⋃x∈X‍{x}⊆⋃x∈X‍clM(𝒞)(x)⊆X. Therefore X=⋃x∈X‍clM(𝒞)(x).Example 26.
Suppose𝒞 is the one shown in Example 16. According to Example 21 and Proposition 19, we have clM(𝒞)(∅)=∅, clM(𝒞)(1)={1}, clM(𝒞)(2)={2}, clM(𝒞)(3)={3}, and clM(𝒞)(4)=clM(𝒞)(5)={4,5}. Since X=⋃x∈X‍clM(𝒞)(x) for all X∈ℒ(M(𝒞)), we obtain ℒ(M(𝒞))={∅,{1},{2},{3},{4,5},{1,2},{1,3},{1,4,5},{2,3},{2,4,5},{3,4,5},{1,2,3,4,5}}, and the geometric lattice (ℒ(M(𝒞)),⊆) is shown in Figure 1.Figure 1
The geometric lattice of(ℒ(M(𝒞)),⊆).


## 4. Application of Geometric Lattice in Attribute Reduction

In Section3, we have studied the geometric lattice structure induced by a covering in detail. In this section, we study how to apply the lattice to attribute reductions from an expanded perspective. Considering the fact that an information system can be converted to a dependence space, the fact that studying the reduction issues of the dependence space is equal to studying the issues of the information system, and the fact that a geometric lattice is the lattice of all the closed sets of a finite matroid, hence we take the following measures to realize our purpose. First, we construct one dependence space through a matroid and obtain all the reducts of the space. Second, we built the other dependence space from an information system. Through making these two spaces equal, we realize the purpose to apply geometric lattices to the issues of attribute reduction of information systems.


### 4.1. Application of Geometric Lattice in the Reduction Issue of Dependence Space

In this subsection, we apply the geometric lattices to the reduction problems of dependence spaces. First, we make certain that what is dependence space. The concept of dependence space can be found in [40]; the following lemma introduces it from the viewpoint of set theory.Lemma 27 (see [40]).
LetU be a finite nonempty set. For all 𝒯⊆2U, denote
(3)Γ(𝒯)={(B1,B2)∈P(U)×P(U):B1⊆X⟺B2⊆X,∀X∈𝒯}.
Then (U,Γ(𝒯)) is a dependence space.For a geometric lattice induced by a matroid, one can use its coatoms, namely the hyperplanes of the matroid, to induce a dependence space(U,Γ(ℋ(M))). Before studying the reduction issues of the dependence space, we review the concepts of consistent sets and reducts defined in dependence spaces.Let(U,Θ) be a dependence space. A subset B(⊆U) is called a consistent set if B is minimal with respect to inclusion in its Θ-class. A subset B is called a reduct of (U,Θ), if (B,U)∈Θ and B is a consistent set.In fact, the issue of reduction of dependence space(U,Γ(𝒯)) has been discussed in detail in [40].Lemma 28 (see [40]).
B
(
⊆
U
) is a reduct of (U,Γ(𝒯)) if and only if B∈Min⁡({D′⊆U:D⋂‍D′≠∅(forallD∈𝒯¯)}), where 𝒯¯={D≠∅,U-D∈𝒯}.Therefore, we can obtain the following result. It indicates that a subset of a finite nonempty set is a reduct of the dependence space induced by the coatoms of a geometric lattice if and only if it is a minimal set with respect to the property of containing an element from each nonempty complement of any coatom of the lattice. The symbolCom appearing in the proposition below is defined as Com(𝒜)={X⊆U:U-X∈𝒜}, where 𝒜 is a family of subsets of U.Proposition 29.
B is a reduct of (U,Γ(ℋ(M))) if and only if B∈Min⁡({B⊆U:B⋂‍C≠∅(forallC∈Com(ℋ(M))}).Proof.
According to the definition of hyperplane, we knowU∉ℋ(M). It implies that ∅∉Com(ℋ(M)). Combining Proposition 33 and Lemma 28, we obtain the result.Example 30.
Suppose lattice is the one shown in Example26. Then the coatoms ℋ(M) of the lattice are {{1,2},{1,3},{2,3},{1,4,5},{2,4,5},{3,4,5}} and Com(ℋ(M))={{3,4,5},{2,4,5},{1,4,5},{2,3},{1,3},{1,2}}. They are all nonempty sets. According to Proposition 29, the set of all the reducts of (U,𝒯(ℋ(M))) is {{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{2,3,4},{2,3,5}}.Considering that geometric lattices have a closed relation with matroids, we define the other dependence space from the viewpoint of matroids. It is interesting that the dependence space is equal to the one(U,Γ(ℋ(M))), which provides us with the other approach to realize the purpose to apply the geometric lattice to attribute reduction in Section 4.2.Definition 31.
LetM be a matroid on U. One can define an equivalence relation on 2U as follows: for all B,C⊆U,
(4)BΘMC⟺clM(B)=clM(C).Lemma 32 (see [30]).
LetM be a matroid on U. For all X⊆U,
(5)clM(X)={UrM(X)=rM(U),⋂‍{H∈ℋ(M):X⊆H}rM(X)≠rM(U).Proposition 33.
LetM be a matroid on U. (U,ΘM) is a dependence space and Γ(ℋ(M))=ΘM.Proof.
If(B1,B2)∈Γ(ℋ(M)), then B1⊆H⇔B2⊆H for all H∈ℋ(M). We know rM(B1)≠rM(U)≠rM(B2). According to Lemma 32, we have clM(B1)=⋂‍{H∈ℋ(M):B1⊆H}=⋂‍{H∈ℋ(M):B2⊆H}=clM(B2). Thus (B1,B2)∈ΘM which implies that Γ(ℋ(M))⊆ΘM. If (B1,B2)∈ΘM, then clM(B1)=cl⁡M(B2). For all H∈ℋ(M), if B1⊆H, then clM(B1)⊆clM(H)=H. Thus B2⊆clM(B2)=clM(B1)⊆H. Similarly, we can prove the result: for all H∈ℋ(M), if B2⊆H, then B1⊆H. Therefore, ΘM⊆Γ(ℋ(M)). According to Lemma 27, we know (U,ΘM) is a dependence space.


### 4.2.  An Application to Information Systems

In Section4.1, we propose two methods to solve the problems of reduction in dependence spaces from matroids and geometric lattices, respectively. In this subsection, we apply the methods to information systems. First, we introduce the concept of information systems.Definition 34 (information system [40]).
An information system is a quadruple form(U,A,F,V), where U={x1,x2,…,xn} is a nonempty finite set of objects, A={a1,a2,…,am} is a nonempty finite set of attributes, Vj∈V={V1,V2,…,Vm} is the domain of attribute aj, and F={fj:j≤m} is a set of information function such that fj(xi)∈Vj for all xi∈U.In an information system,F, which describes the connection between U and A, is a basis for knowledge discovery. Here, we assume that the information system is complete. Let (U,A,F,V) be an information system. For any B⊆A, the indiscernibility relation is defined as(6)RB={(xi,xj)∈U×U:fl(xi)=fl(xj),∀al∈B}.
Specifically, for any attribute b∈A,
(7)Rb={(xi,xj)∈U×U:fb(xi)=fb(xj)}.
It is obvious that RB=⋂b∈B‍Rb and RB, Rb are equivalence relations of U. Based on the above two equivalence relations, we have the following two equivalence relations:
(8)R={(B1,B2)∈2A×2A:RB1=RB2},R0={(b,c)∈A×A,Rb=Rc}.It was noted in [40] that R is an equivalence relation on A and the pair (A,R) is a dependence space. In an information system, B is referred to as a consistent set if RB=RA, and if B is a consistent set and RB-{b}≠RA (for all b∈B), then B is referred to as a reduct of the information system. We find that the reducts defined in the information system are the reducts defined in the dependence space (A,R). In the following discussion, we solve the issues of attribute reduction of information systems starting with the operator R0*. As we know, the upper approximation operator R0* is a closure operator of a matroid. Similar to Definition 31, we have the following equivalence relation.Definition 35.
LetA be a finite nonempty set. For all X,Y⊆A, one can define an equivalence relation Θ of 2A as follows:
(9)XΘY⟺R0*(X)=R0*(Y).According to Proposition33, we know (A,Θ) is a dependence space, and we can obtain all the reducts of the space through Proposition 29. Next, we want to find out all the reducts of (A,R) with the aid of the space (A,Θ). The proposition below establishes the relation between Θ and R.Proposition 36.
For allX,Y⊆A, if RX=RY⇒R0*(X)=R0*(Y), then Θ=R.Proof.
We need to proveR0*(X)=R0*(Y)⇒RX=RY. If RX≠RY, then we may as well suppose that there exists (xi,xj)∈RX-RY. Thus for all a∈X, (xi,xj)∈Ra and there exists b∈Y such that (xi,xj)∉Rb. Consequently, Rb≠Ra for all a∈X. That implies that b∉R0*(X)={x∈A,[x]R0⋂‍X≠∅}. It is clear that b∈R0*(Y) because b∈Y and b∈[b]R0. Therefore, R0*(X)≠R0*(Y), a contradiction! Hence we have R0*(X)=R0*(Y)⇒RX=RY. According to the assumption, we have RX=RY⇒R0*(X)=R0*(Y). Therefore Θ=R.When an information system satisfies the condition presented in Proposition36, then we can find and prove a method to attribute reduction of the information system. The method is described as follows: arbitrarily select an element in each Pi(∈A/R0) to compose a new set, which is just the reduct of the information system.Proposition 37.
Let(U,A,F,V) be an information system and A/R0={P1,P2,…,Ps}. For all X,Y⊆A, if RX=RY⇒R0*(X)=R0*(Y), then the following condition holds: B is a reduct of (U,A,F,V) if and only if B={p1,p2,…,ps}, where pi∈Pi, 1≤i≤s.Proof.
SupposeR0* is a closure operator of matroid M. It is clear that ℋ(M)={A-Pi:i=1,2,…,s}. According to Propositions 29 and 36, we have that B is a reduct of (U,A,F,V) if and only if B∈Min⁡({B⊆A:B⋂‍C≠∅(forallC∈Com(ℋ(M)))})=Min⁡({B⊆A:B⋂‍C≠∅(forallC∈A/R0)})={B⊆A:|B⋂‍Pi|=1,i=1,2,…,s}.A relation table entirely determines an information system. The following example presents how to use above results to find all the reducts of an information system.Example 38.
Let(U,A,F,V) be an information system which is shown in Table 1. It is obvious that U/Ra1=U/Ra3=U/R{a1,a3}={{x1}, {x2,x3,x4}}, U/Ra2={{x1,x4},{x2},{x3}}, and U/R{a1,a2}=U/R{a2,a3}=U/R{a1,a2,a3}={{x1},{x2},{x3},{x4}}. Then R0={{a1,a3},{a2}}. It is easy to check that any two subsets X and Y of A satisfy the condition: RX=RY⇒R0*(X)=R0*(X). Hence we can obtain that all the reducts of (U,A,F,V) are {a1,a2} and {a2,a3}.Table 1
An information system.
U
Outlook (a1)
Temperature (a2)
Humidity (a3)
x
1
Sunny
Hot
High
x
2
Rain
Mild
Normal
x
3
Rain
Cool
Normal
x
4
Rain
Hot
Normal


## 4.1. Application of Geometric Lattice in the Reduction Issue of Dependence Space

In this subsection, we apply the geometric lattices to the reduction problems of dependence spaces. First, we make certain that what is dependence space. The concept of dependence space can be found in [40]; the following lemma introduces it from the viewpoint of set theory.Lemma 27 (see [40]).
LetU be a finite nonempty set. For all 𝒯⊆2U, denote
(3)Γ(𝒯)={(B1,B2)∈P(U)×P(U):B1⊆X⟺B2⊆X,∀X∈𝒯}.
Then (U,Γ(𝒯)) is a dependence space.For a geometric lattice induced by a matroid, one can use its coatoms, namely the hyperplanes of the matroid, to induce a dependence space(U,Γ(ℋ(M))). Before studying the reduction issues of the dependence space, we review the concepts of consistent sets and reducts defined in dependence spaces.Let(U,Θ) be a dependence space. A subset B(⊆U) is called a consistent set if B is minimal with respect to inclusion in its Θ-class. A subset B is called a reduct of (U,Θ), if (B,U)∈Θ and B is a consistent set.In fact, the issue of reduction of dependence space(U,Γ(𝒯)) has been discussed in detail in [40].Lemma 28 (see [40]).
B
(
⊆
U
) is a reduct of (U,Γ(𝒯)) if and only if B∈Min⁡({D′⊆U:D⋂‍D′≠∅(forallD∈𝒯¯)}), where 𝒯¯={D≠∅,U-D∈𝒯}.Therefore, we can obtain the following result. It indicates that a subset of a finite nonempty set is a reduct of the dependence space induced by the coatoms of a geometric lattice if and only if it is a minimal set with respect to the property of containing an element from each nonempty complement of any coatom of the lattice. The symbolCom appearing in the proposition below is defined as Com(𝒜)={X⊆U:U-X∈𝒜}, where 𝒜 is a family of subsets of U.Proposition 29.
B is a reduct of (U,Γ(ℋ(M))) if and only if B∈Min⁡({B⊆U:B⋂‍C≠∅(forallC∈Com(ℋ(M))}).Proof.
According to the definition of hyperplane, we knowU∉ℋ(M). It implies that ∅∉Com(ℋ(M)). Combining Proposition 33 and Lemma 28, we obtain the result.Example 30.
Suppose lattice is the one shown in Example26. Then the coatoms ℋ(M) of the lattice are {{1,2},{1,3},{2,3},{1,4,5},{2,4,5},{3,4,5}} and Com(ℋ(M))={{3,4,5},{2,4,5},{1,4,5},{2,3},{1,3},{1,2}}. They are all nonempty sets. According to Proposition 29, the set of all the reducts of (U,𝒯(ℋ(M))) is {{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{2,3,4},{2,3,5}}.Considering that geometric lattices have a closed relation with matroids, we define the other dependence space from the viewpoint of matroids. It is interesting that the dependence space is equal to the one(U,Γ(ℋ(M))), which provides us with the other approach to realize the purpose to apply the geometric lattice to attribute reduction in Section 4.2.Definition 31.
LetM be a matroid on U. One can define an equivalence relation on 2U as follows: for all B,C⊆U,
(4)BΘMC⟺clM(B)=clM(C).Lemma 32 (see [30]).
LetM be a matroid on U. For all X⊆U,
(5)clM(X)={UrM(X)=rM(U),⋂‍{H∈ℋ(M):X⊆H}rM(X)≠rM(U).Proposition 33.
LetM be a matroid on U. (U,ΘM) is a dependence space and Γ(ℋ(M))=ΘM.Proof.
If(B1,B2)∈Γ(ℋ(M)), then B1⊆H⇔B2⊆H for all H∈ℋ(M). We know rM(B1)≠rM(U)≠rM(B2). According to Lemma 32, we have clM(B1)=⋂‍{H∈ℋ(M):B1⊆H}=⋂‍{H∈ℋ(M):B2⊆H}=clM(B2). Thus (B1,B2)∈ΘM which implies that Γ(ℋ(M))⊆ΘM. If (B1,B2)∈ΘM, then clM(B1)=cl⁡M(B2). For all H∈ℋ(M), if B1⊆H, then clM(B1)⊆clM(H)=H. Thus B2⊆clM(B2)=clM(B1)⊆H. Similarly, we can prove the result: for all H∈ℋ(M), if B2⊆H, then B1⊆H. Therefore, ΘM⊆Γ(ℋ(M)). According to Lemma 27, we know (U,ΘM) is a dependence space.


## 4.2.  An Application to Information Systems

In Section4.1, we propose two methods to solve the problems of reduction in dependence spaces from matroids and geometric lattices, respectively. In this subsection, we apply the methods to information systems. First, we introduce the concept of information systems.Definition 34 (information system [40]).
An information system is a quadruple form(U,A,F,V), where U={x1,x2,…,xn} is a nonempty finite set of objects, A={a1,a2,…,am} is a nonempty finite set of attributes, Vj∈V={V1,V2,…,Vm} is the domain of attribute aj, and F={fj:j≤m} is a set of information function such that fj(xi)∈Vj for all xi∈U.In an information system,F, which describes the connection between U and A, is a basis for knowledge discovery. Here, we assume that the information system is complete. Let (U,A,F,V) be an information system. For any B⊆A, the indiscernibility relation is defined as(6)RB={(xi,xj)∈U×U:fl(xi)=fl(xj),∀al∈B}.
Specifically, for any attribute b∈A,
(7)Rb={(xi,xj)∈U×U:fb(xi)=fb(xj)}.
It is obvious that RB=⋂b∈B‍Rb and RB, Rb are equivalence relations of U. Based on the above two equivalence relations, we have the following two equivalence relations:
(8)R={(B1,B2)∈2A×2A:RB1=RB2},R0={(b,c)∈A×A,Rb=Rc}.It was noted in [40] that R is an equivalence relation on A and the pair (A,R) is a dependence space. In an information system, B is referred to as a consistent set if RB=RA, and if B is a consistent set and RB-{b}≠RA (for all b∈B), then B is referred to as a reduct of the information system. We find that the reducts defined in the information system are the reducts defined in the dependence space (A,R). In the following discussion, we solve the issues of attribute reduction of information systems starting with the operator R0*. As we know, the upper approximation operator R0* is a closure operator of a matroid. Similar to Definition 31, we have the following equivalence relation.Definition 35.
LetA be a finite nonempty set. For all X,Y⊆A, one can define an equivalence relation Θ of 2A as follows:
(9)XΘY⟺R0*(X)=R0*(Y).According to Proposition33, we know (A,Θ) is a dependence space, and we can obtain all the reducts of the space through Proposition 29. Next, we want to find out all the reducts of (A,R) with the aid of the space (A,Θ). The proposition below establishes the relation between Θ and R.Proposition 36.
For allX,Y⊆A, if RX=RY⇒R0*(X)=R0*(Y), then Θ=R.Proof.
We need to proveR0*(X)=R0*(Y)⇒RX=RY. If RX≠RY, then we may as well suppose that there exists (xi,xj)∈RX-RY. Thus for all a∈X, (xi,xj)∈Ra and there exists b∈Y such that (xi,xj)∉Rb. Consequently, Rb≠Ra for all a∈X. That implies that b∉R0*(X)={x∈A,[x]R0⋂‍X≠∅}. It is clear that b∈R0*(Y) because b∈Y and b∈[b]R0. Therefore, R0*(X)≠R0*(Y), a contradiction! Hence we have R0*(X)=R0*(Y)⇒RX=RY. According to the assumption, we have RX=RY⇒R0*(X)=R0*(Y). Therefore Θ=R.When an information system satisfies the condition presented in Proposition36, then we can find and prove a method to attribute reduction of the information system. The method is described as follows: arbitrarily select an element in each Pi(∈A/R0) to compose a new set, which is just the reduct of the information system.Proposition 37.
Let(U,A,F,V) be an information system and A/R0={P1,P2,…,Ps}. For all X,Y⊆A, if RX=RY⇒R0*(X)=R0*(Y), then the following condition holds: B is a reduct of (U,A,F,V) if and only if B={p1,p2,…,ps}, where pi∈Pi, 1≤i≤s.Proof.
SupposeR0* is a closure operator of matroid M. It is clear that ℋ(M)={A-Pi:i=1,2,…,s}. According to Propositions 29 and 36, we have that B is a reduct of (U,A,F,V) if and only if B∈Min⁡({B⊆A:B⋂‍C≠∅(forallC∈Com(ℋ(M)))})=Min⁡({B⊆A:B⋂‍C≠∅(forallC∈A/R0)})={B⊆A:|B⋂‍Pi|=1,i=1,2,…,s}.A relation table entirely determines an information system. The following example presents how to use above results to find all the reducts of an information system.Example 38.
Let(U,A,F,V) be an information system which is shown in Table 1. It is obvious that U/Ra1=U/Ra3=U/R{a1,a3}={{x1}, {x2,x3,x4}}, U/Ra2={{x1,x4},{x2},{x3}}, and U/R{a1,a2}=U/R{a2,a3}=U/R{a1,a2,a3}={{x1},{x2},{x3},{x4}}. Then R0={{a1,a3},{a2}}. It is easy to check that any two subsets X and Y of A satisfy the condition: RX=RY⇒R0*(X)=R0*(X). Hence we can obtain that all the reducts of (U,A,F,V) are {a1,a2} and {a2,a3}.Table 1
An information system.
U
Outlook (a1)
Temperature (a2)
Humidity (a3)
x
1
Sunny
Hot
High
x
2
Rain
Mild
Normal
x
3
Rain
Cool
Normal
x
4
Rain
Hot
Normal


## 5. Conclusions

In this paper, we have constructed a geometric lattice from a covering through the transversal matroid induced by the covering and have used atoms of the lattice to characterize the lattice. Furthermore, we have applied the lattice to the attribute reduction issues of information systems. Though some works have been studied in this paper, there are also many interesting topics deserving further investigation. In the future, we will study algorithm implementations of the attribute reduction issues in information systems through geometric lattices.



---

*Source: 183621-2014-02-11.xml*