# Matroidal Structure of Rough Sets Based on Serial and Transitive Relations

Authors: Yanfang Liu; William Zhu
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

The theory of rough sets is concerned with the lower and upper approximations of objects through a binary relation on a universe. It has been applied to machine learning, knowledge discovery, and data mining. The theory of matroids is a generalization of linear independence in vector spaces. It has been used in combinatorial optimization and algorithm design. In order to take advantages of both rough sets and matroids, in this paper we propose a matroidal structure of rough sets based on a serial and transitive relation on a universe. We define the family of all minimal neighborhoods of a relation on a universe and prove it satisfies the circuit axioms of matroids when the relation is serial and transitive. In order to further study this matroidal structure, we investigate the inverse of this construction: inducing a relation by a matroid. The relationships between the upper approximation operators of rough sets based on relations and the closure operators of matroids in the above two constructions are studied. Moreover, we investigate the connections between the above two constructions.


---

## Body

## 1. Introduction

The theory of rough sets [1] proposed by Pawlak is an extension of set theory for handling incomplete and inexact knowledge in information and decision systems. And it has been successfully applied to many fields, such as machine learning, granular computing [2], data mining, approximate reasoning, attribute reduction [3–6], and rule induction [7, 8]. For an equivalence relation on a universe, a rough set is a formal approximation of a crisp set in terms of a pair of sets which give the lower and the upper approximations of the original set. In order to meet many real applications, the rough sets have been extended to generalized rough sets based on relations [9–14] and covering-based rough sets [15–17]. In this paper, we focus on generalized rough sets based on relations.Matroid theory [18] proposed by Whitney is a generalization of linear algebra and graph theory. And matroids have been used in diverse fields, such as combinatorial optimization, algorithm design, information coding, and cryptology. Since a matroid can be defined by many different but equivalent ways, matroid theory has powerful axiomatic systems. Matroids have been connected with other theories, such as rough sets [19–22], generalized rough sets based on relations [23, 24], covering-based rough sets [25, 26] and lattices [27–29].Rough sets and matroids have their own application fields in the real world. In order to make use of both rough sets and matroids, researchers have combined them with each other and connected them with other theories. In this paper, we propose a matroidal structure based on a serial and transitive relation on a universe and study its relationships with the lower and upper approximations of generalized rough sets based on relations.First, we define a family of sets of a relation on a universe, and we call it the family of all minimal neighborhoods of the relation. When the relation is serial and transitive, the family of all minimal neighborhoods satisfies the circuit axioms of matroids, then a matroid is induced. And we say the matroid is induced by the serial and transitive relation. Moreover, we study the independent sets of the matroid through the neighborhood and the lower and upper approximation operators of generalized rough sets based on relations, respectively. A sufficient and necessary condition, when different relations generate the same matroid, is investigated. And the relationships between the upper approximation operator of a relation and the closure operator of the matroid induced by the relation are studied. We employ a special type of matroids, called 2-circuit matroids, which is introduced in [22]. When a relation is an equivalence relation, the upper approximation operator of the relation is equal to the closure operator of the matroid induced by the relation if and only if the matroid is a 2-circuit matroid. In order to study the matroidal structure of the rough set based on a serial and transitive relation, we investigate the inverse of the above construction. In other words, we construct a relation from a matroid. Through the connectedness in a matroid, a relation can be obtained and proved to be an equivalence relation. A sufficient and necessary condition, when different matroids induce the same relation, is studied. Moreover, the relationships between the closure operator of a matroid and the upper approximation operator of the relation induced by the matroid are investigated. Especially, for a matroid on a universe, its closure operator is equal to the upper approximation operator of the induced equivalence relation if and only if the matroid is a 2-circuit matroid.Second, the relationships between the above two constructions are studied. On the one hand, for a matroid on a universe, it can induce an equivalence relation, and the equivalence relation can generate a matroid; we prove that the circuit family of the original matroid is finer than one of the induced matroid. And the original matroid is equal to the induced matroid if and only if the circuit family of the original matroid is a partition. On the other hand, for a reflexive and transitive relation on a universe, it can generate a matroid, and the matroid can induce an equivalence relation, then the relationship between the equivalence relation and the original relation is studied. The original relation is equal to the induced equivalence relation if and only if the original relation is an equivalence relation.The rest of this paper is organized as follows. In Section2, we recall some basic definitions of generalized rough sets based on relations and matroids. In Section 3, we propose two constructions between relations and matroids. For a relation on a universe, Section 3.1 defines a family of sets called the family of all minimal neighborhoods and proves it to satisfy the circuit axioms of matroids when the relation is serial and transitive. The independent sets of the matroid are studied. And the relationships between the upper approximation operator of a relation and the closure operator of the matroid induced by the relation are investigated. In Section 3.2, through the circuits of a matroid, we construct a relation and prove it to be an equivalence relation. The relationships between the closure operator of the matroid and the upper approximation operator of the induced equivalence relation are studied. Section 4 represents the relationships between the two constructions proposed in Section 3. Finally, we conclude this paper in Section 5.


## 2. Preliminaries

In this section, we recall some basic definitions and related results of generalized rough sets and matroids which will be used in this paper.


### 2.1. Relation-Based Generalized Rough Sets

Given a universe and a relation on the universe, they form a rough set. In this subsection, we introduce some concepts and properties of generalized rough sets based on relations [13]. The neighborhood is important and used to construct the approximation operators.Definition 2.1 ((neighborhood) see [13]).
LetR be a relation on U. For any x∈U, we call the set RNR(x)={y∈U:xRy} the successor neighborhood of x in R. When there is no confusion, we omit the subscript R.In the following definition, we introduce the lower and upper approximation operators of generalized rough sets based on relations through the neighborhood.Definition 2.2 ((lower and upper approximation operators) see [13]).
LetR be a relation on U. A pair of operators LR,HR:2U→2U are defined as follows: for all X⊆U,
(2.1)LR(X)={x∈U:RN(x)⊆X},HR(X)={x∈U:RN(x)∩X≠∅}.LRandHR are called the lower and upper approximation operators of R, respectively. We omit the subscript R when there is no confusion.We present properties of the lower and upper approximation operators in the following proposition.Proposition 2.3 (see [13]).
LetR be a relation on U and Xc the complement of X in U. For all X,Y⊆U,(1L)
L(U)=U;(1H)
H(∅)=∅;(2L)
X⊆Y⇒L(X)⊆L(Y);(2H)
X⊆Y⇒H(X)⊆H(Y);(3L)
L(X∩Y)=L(X)∩L(Y);(3H)
H(X∪Y)=H(X)∪H(Y);(4LH)
L(Xc)=(H(X))c.In [30], Zhu has studied the generalized rough sets based on relations and investigated conditions for a relation to satisfy some of common properties of classical lower and upper approximation operators. In the following proposition, we introduce one result used in this paper.Proposition 2.4.
LetR be a relation on U. Then,
(2.2)Risreflexive⟺X⊆H(X)∀X⊆U.In the following definition, we use the neighborhood to describe a serial relation and a transitive relation on a universe.Definition 2.5 (see [13]).
LetR be a relation on U.(1)
R is serial ⇔forallx∈U[RN(x)≠∅];(2)
R is transitive ⇔forallx,y∈U[y∈RN(x)⇒RN(y)⊆RN(x)].


### 2.2. Matroids

Matroids have many equivalent definitions. In the following definition, we will introduce one that focuses on independent sets.Definition 2.6 ((matroid) see [18]).
A matroid is a pairM=(U,I) consisting of a finite universe U and a collection I of subsets of U called independent sets satisfying the following three properties:(I1)
∅∈I;(I2)
ifI∈I and I′⊆I, then I′∈I;(I3)
ifI1,I2∈I, and |I1|<|I2|, then there exists u∈I2-I1 such that I1∪{u}∈I, where |I| denotes the cardinality of I.Since the above definition is from the viewpoint of independent sets to represent matroids, it is also called the independent set axioms of matroids. In order to make some expressions brief, we introduce several symbols as follows.Definition 2.7 (see [18]).
LetU be a finite universe and A a family of subsets of U. Several symbols are defined as follows:
(2.3)FMIN(A)={X∈A:∀Y∈A,Y⊆X⇒X=Y};Upp(A)={X⊆U:∃A∈As.t.A⊆X};Opp(A)={X⊆U:X∉A}.In a matroid, a subset is a dependent set if it is not an independent set. Any circuit of a matroid is a minimal-dependent set.Definition 2.8 ((circuit) see [18]).
LetM=(U,I) be a matroid. Any minimal-dependent set in M is called a circuit of M, and we denote the family of all circuits of M by C(M), that is, C(M)=FMIN(Opp(I)).A matroid can be defined from the viewpoint of circuits, in other words, a matroid uniquely determines its circuits, and vice versa.Proposition 2.9 ((circuit axioms) see [18]).
LetC be a family of subsets of U. Then there exists M=(U,I) such that C=C(M) if and only if C satisfies the following conditions:(C1)
∅∉C;(C2)
ifC1,C2∈C, and C1⊆C2, then C1=C2;(C3)
ifC1,C2∈C, C1≠C2, and c∈C1∩C2, then there exists C3∈C such that C3⊆C1∪C2-{c}.The closure operator is one of the important characteristics of matroids. A matroid and its closure operator can uniquely determine each other. In the following definition, we use the circuits of matroids to represent the closure operator.Definition 2.10 ((closure) see [18]).
LetM=(U,I) be a matroid and X⊆U.
(2.4)clM(X)=X∪{u∈Xc:∃C∈C(M)s.t.u∈C⊆X∪{u}}
is called the closure of X with respect to M. And clM is the closure operator of M.


## 2.1. Relation-Based Generalized Rough Sets

Given a universe and a relation on the universe, they form a rough set. In this subsection, we introduce some concepts and properties of generalized rough sets based on relations [13]. The neighborhood is important and used to construct the approximation operators.Definition 2.1 ((neighborhood) see [13]).
LetR be a relation on U. For any x∈U, we call the set RNR(x)={y∈U:xRy} the successor neighborhood of x in R. When there is no confusion, we omit the subscript R.In the following definition, we introduce the lower and upper approximation operators of generalized rough sets based on relations through the neighborhood.Definition 2.2 ((lower and upper approximation operators) see [13]).
LetR be a relation on U. A pair of operators LR,HR:2U→2U are defined as follows: for all X⊆U,
(2.1)LR(X)={x∈U:RN(x)⊆X},HR(X)={x∈U:RN(x)∩X≠∅}.LRandHR are called the lower and upper approximation operators of R, respectively. We omit the subscript R when there is no confusion.We present properties of the lower and upper approximation operators in the following proposition.Proposition 2.3 (see [13]).
LetR be a relation on U and Xc the complement of X in U. For all X,Y⊆U,(1L)
L(U)=U;(1H)
H(∅)=∅;(2L)
X⊆Y⇒L(X)⊆L(Y);(2H)
X⊆Y⇒H(X)⊆H(Y);(3L)
L(X∩Y)=L(X)∩L(Y);(3H)
H(X∪Y)=H(X)∪H(Y);(4LH)
L(Xc)=(H(X))c.In [30], Zhu has studied the generalized rough sets based on relations and investigated conditions for a relation to satisfy some of common properties of classical lower and upper approximation operators. In the following proposition, we introduce one result used in this paper.Proposition 2.4.
LetR be a relation on U. Then,
(2.2)Risreflexive⟺X⊆H(X)∀X⊆U.In the following definition, we use the neighborhood to describe a serial relation and a transitive relation on a universe.Definition 2.5 (see [13]).
LetR be a relation on U.(1)
R is serial ⇔forallx∈U[RN(x)≠∅];(2)
R is transitive ⇔forallx,y∈U[y∈RN(x)⇒RN(y)⊆RN(x)].


## 2.2. Matroids

Matroids have many equivalent definitions. In the following definition, we will introduce one that focuses on independent sets.Definition 2.6 ((matroid) see [18]).
A matroid is a pairM=(U,I) consisting of a finite universe U and a collection I of subsets of U called independent sets satisfying the following three properties:(I1)
∅∈I;(I2)
ifI∈I and I′⊆I, then I′∈I;(I3)
ifI1,I2∈I, and |I1|<|I2|, then there exists u∈I2-I1 such that I1∪{u}∈I, where |I| denotes the cardinality of I.Since the above definition is from the viewpoint of independent sets to represent matroids, it is also called the independent set axioms of matroids. In order to make some expressions brief, we introduce several symbols as follows.Definition 2.7 (see [18]).
LetU be a finite universe and A a family of subsets of U. Several symbols are defined as follows:
(2.3)FMIN(A)={X∈A:∀Y∈A,Y⊆X⇒X=Y};Upp(A)={X⊆U:∃A∈As.t.A⊆X};Opp(A)={X⊆U:X∉A}.In a matroid, a subset is a dependent set if it is not an independent set. Any circuit of a matroid is a minimal-dependent set.Definition 2.8 ((circuit) see [18]).
LetM=(U,I) be a matroid. Any minimal-dependent set in M is called a circuit of M, and we denote the family of all circuits of M by C(M), that is, C(M)=FMIN(Opp(I)).A matroid can be defined from the viewpoint of circuits, in other words, a matroid uniquely determines its circuits, and vice versa.Proposition 2.9 ((circuit axioms) see [18]).
LetC be a family of subsets of U. Then there exists M=(U,I) such that C=C(M) if and only if C satisfies the following conditions:(C1)
∅∉C;(C2)
ifC1,C2∈C, and C1⊆C2, then C1=C2;(C3)
ifC1,C2∈C, C1≠C2, and c∈C1∩C2, then there exists C3∈C such that C3⊆C1∪C2-{c}.The closure operator is one of the important characteristics of matroids. A matroid and its closure operator can uniquely determine each other. In the following definition, we use the circuits of matroids to represent the closure operator.Definition 2.10 ((closure) see [18]).
LetM=(U,I) be a matroid and X⊆U.
(2.4)clM(X)=X∪{u∈Xc:∃C∈C(M)s.t.u∈C⊆X∪{u}}
is called the closure of X with respect to M. And clM is the closure operator of M.


## 3. Two Constructions between Matroid and Relation

In this section, we propose two constructions between a matroid and a relation. One construction is from a relation to a matroid, and the other construction is from a matroid to a relation.


### 3.1. Construction of Matroid by Serial and Transitive Relation

In [19], for an equivalence relation on a universe, we present a matroidal structure whose family of all circuits is the partition induced by the equivalence relation. Through extending equivalence relations, in this subsection, we propose a matroidal structure which is based on a serial and transitive relation. First, for a relation on a universe, we define a family of sets, namely, the family of all minimal neighborhoods.Definition 3.1 (the family of all minimal neighborhoods).
LetR be a relation on U. We define a family of sets with respect to R as follows:
(3.1)C(R)=FMIN{RN(x):x∈U}.
We call C(R) the family of all minimal neighborhoods of R.In the following proposition, we will prove the family of all minimal neighborhoods of a relation on a universe satisfies the circuit axioms of matroids when the relation is serial and transitive.Proposition 3.2.
LetR be a relation on U. If R is serial and transitive, then C(R) satisfies (C1), (C2), and (C3) in Proposition 2.9.Proof.
(C1): SinceR is a serial relation, according to (1) of Definition 2.5, then ∅∉C(R).
(C2): According to Definitions3.1 and 2.7, it is straightforward that C(R) satisfies (C2).
(C3): IfC1,C2∈C(R), and C1≠C2, then there exist x1,x2∈U, and x1≠x2 such that C1=RN(x1),C2=RN(x2). If x∈C1∩C2, that is, x∈RN(x1)∩RN(x2), then x∈RN(x1) and x∈RN(x2). Since R is a transitive relation, according to (2) of Definition 2.5, we can obtain that RN(x)⊆RN(x1) and RN(x)⊆RN(x2). According to Definition 3.1, we can obtain RN(x)=RN(x1)=RN(x2) which is contradictory with RN(x1)≠RN(x2). Therefore, for any C1,C2∈C(R), and C1≠C2, C1∩C2=∅ when R is transitive, then, it is straightforward to see that C(R) satisfies (C3) in Proposition 2.9.It is natural to ask the following question: “when the family of all minimal neighborhoods of a relation satisfies the circuit axioms of matroids, is the relation serial and transitive?”. In the following proposition, we will solve this issue.Proposition 3.3.
LetR be a relation on U. If C(R) satisfies (C1), (C2), and (C3) in Proposition 2.9, then R is serial.Proof.
According to (C1) of Proposition2.9 and Definition 3.1, RN(x)≠∅ for any x∈U. According to Definition 2.5, R is serial.When the family of all minimal neighborhoods of a relation satisfies the circuit axioms of matroids, the relation is not always a transitive relation as shown in the following example.Example 3.4.
LetU={1,2,3} and R={(1,2),(1,3),(2,1),(2,3),(3,1)} a relation on U. Since RN(1)={2,3},RN(2)={1,3},RN(3)={1}, then C(R)={{1},{2,3}}. According to Proposition 2.9, C(R) satisfies the circuit axioms of matroids. We see that (1,2)∈R,(2,1)∈R, but (1,1)∉R,(2,2)∉R, so R is not transitive.In this paper, we consider that the family of all minimal neighborhoods of a relation can generate a matroid when the relation is serial and transitive.Definition 3.5.
LetR be a serial and transitive relation on U. The matroid with C(R) as its circuit family is denoted by M(R)=(U,I(R)), where I(R)=Opp(Upp(C(R))). We say M(R) is the matroid induced by R.The matroid induced by a serial and transitive relation can be illustrated by the following example.Example 3.6.
LetU={1,2,3} and R={(1,1),(1,3),(2,1),(2,3),(3,3)} a serial and transitive relation on U. Since RN(1)=RN(2)={1,3},RN(3)={3}, then C(R)={{3}}. Therefore, M(R)=(U,I(R)) where I(R)={∅,{1},{2},{1,2}}.Generally speaking, a matroid is defined from the viewpoint of independent sets. In the following, we will investigate the independent sets of the matroid induced by a serial and transitive relation.Proposition 3.7.
LetR be a serial and transitive relation on U and M(R) the matroid induced by R. Then,
(3.2)I(R)={I⊆U:∀x∈U,RN(x)⊈I}.Proof.
According to Definition3.5, I(R)=Opp(Upp(C(R))).(⊆):
for allX∉Opp(Upp(C(R))), that is, X∈Upp(C(R)), according to Definitions 2.7 and 3.1, there exists x∈U such that RN(x)⊆X. Hence X∉{I⊆U:forallx∈U,RN(x)⊈I}, that is, X∉I(R). This proves that I(R)⊆Opp(Upp(C(R))).(⊇):
supposeX∉I(R), that is, X∉{I⊆U:forallx∈U,RN(x)⊈I}. Then there exists x∈U such that RN(x)⊆X, in other words, X∈Upp(C(R)), that is, X∉Opp(Upp(C(R))). This proves that I(R)⊇Opp(Upp(C(R))).To illustrate the independent sets of a matroid induced by a serial and transitive relation, the following example is given.Example 3.8.
LetU={1,2,3} and R={(1,3),(2,3),(3,3)} a serial and transitive relation on U. Since RN(1)=RN(2)=RN(3)={3}, then {3}⊈∅,{3}⊈{1},{3}⊈{2},{3}⊈{1,2}. Therefore M(R)=(U,I(R)) where I(R)={∅,{1},{2},{1,2}}.The lower and upper approximation operators are constructed through the neighborhood in generalized rough sets based on relations. In the following proposition, we will study the independent sets of the matroid induced by a serial and transitive relation through the lower approximation operator.Proposition 3.9.
LetR be a serial and transitive relation on U and M(R) the matroid induced by R. Then,
(3.3)I(R)={I⊆U:L(I)=∅}.Proof.
According to Definition2.2 and Proposition 3.7, it is straightforward.Because of the duality of the lower and upper approximation operators, we obtain the independent sets of the matroid induced by a serial and transitive relation through the upper approximation operator.Corollary 3.10.
LetR be a serial and transitive relation on U and M(R) the matroid induced by R. Then,
(3.4)I(R)={I⊆U:H(Ic)=U}.Proof.
According to (4LH) of Propositions2.3 and 3.9, it is straightforward.From Examples3.6 and 3.8, we see that two different relations on a universe generate the same matroid. We study under what conditions two relations on a universe can generate the same matroid. If a relation is transitive, then the reflexive closure of the relation is transitive, but the symmetric closure of the relation is not always transitive. Therefore, we consider the relationship between the matroids induced by a serial and transitive relation and the reflexive closure of the relation. First, we introduce the reflexive closure of a relation on a nonempty universe.Definition 3.11 ((reflexive closure of a relation) see [31]).
LetU be a nonempty universe and R a relation on U. We denote r(R) as the reflexive closure of R, where r(R)=R∪{(x,x):x∈U}.The relationship between the two matroids induced by a serial and transitive relation and its reflexive closure is studied in the following proposition.Proposition 3.12.
LetR be a serial and transitive relation on U. Then M(R)=M(r(R)).Proof.
According to Proposition2.9, we need only to prove C(R)=C(r(R)). According to Definition 3.1, C(R)=FMIN{RNR(x):x∈U} and C(r(R))=FMIN{RNr(R)(x):x∈U}. According to Definition 3.11, r(R)=R∪{(x,x):x∈U}, then C(r(R))=FMIN{RNR(x)∪{x}:x∈U}.(⊆):
for allRNR(x)∈C(R), on the one hand, x∈RNR(x), then RNR(x)∈C(r(R)). On the other hand, x∉RNR(x). Since R is serial, then there exists y∈U such that y∈RNR(x). Since R is transitive, then RNR(y)⊆RNR(x). And RNR(x)∈C(R), then y∈RNR(y)=RNR(x). Therefore, {y}∪RNR(y)⊂{x}∪RNR(x), that is, RNR(y)∈C(r(R)). In other words, RNR(x)∈C(r(R)). Hence C(R)⊆C(r(R)).(⊇):
for allRNr(R)(x)∈C(r(R)), that is, RNR(x)∪{x}∈C(r(R)). If x∈RNR(x), then RNr(R)(x)∈C(R). If x∉RNR(x), that is, RNR(x)⊂RNr(R)(x), then RNR(x)∈C(R). If RNR(x)∉C(R), then there exists y∈U such that RNR(y)⊂RNR(x) and RNR(y)∈C(R). Since R is serial, then there exists z∈U such that z∈RNR(y). And R is transitive, then RNR(z)⊆RNR(y). Therefore z∈RNR(z)=RNR(y), that is, RNR(z)∪{z}=RNR(y). Hence RNR(z)∪{z}⊂RNR(x)⊂RNR(x)∪{x} which is contradictory with RNR(x)∪{x}∈C(r(R)). Since R is serial, then there exists y∈U such that y∈RNR(x). Since R is transitive, then RNR(y)⊆RNR(x). And RNR(x)∈C(R), then y∈RNR(y)=RNR(x), that is, {y}∪RNR(y)⊂{x}∪RNR(x) which is contradictory with RNR(x)∪{x}∈C(r(R)). Hence RNr(R)(x)∈C(R), that is, C(r(R))⊆C(R).In fact, for a universe, any different relations generate the same matroid if and only if the families of all minimal neighborhoods are equal to each other according to Proposition2.9.It is known that the upper approximation operator induced by a reflexive and transitive relation is exactly the closure operator of a topology [11, 32, 33]. We see that a matroid has its own closure operator. In this paper, we will not discuss the relationship between the closure operator of a topology and one of a matroid. We will study the connection between the upper approximation operator of a rough set and the closure operator of a matroid. In the following, we investigate the relationship between the upper approximation operator of a relation and the closure operator of the matroid induced by the relation.In a matroid, the closure of any subset contains the subset itself. When a relation on a universe is reflexive, the upper approximation of any subset contains the subset itself. If a relation is reflexive, then it is serial. According to Definition3.1, a reflexive and transitive relation can induce a matroid. We will study the relationship between the upper approximation operator induced by a reflexive and transitive relation and the closure operator of the matroid induced by the relation. A counterexample is given in the following.Example 3.13.
LetU={1,2,3} and R={(1,1),(1,3),(2,2),(2,3),(3,3)} a reflexive and transitive relation on U. Since RN(1)={1,3},RN(2)={2,3},RN(3)={3}, then C(R)={{3}}. Therefore, clM(R)(∅)={3},clM(R)({3})={3}. Since HR(∅)=∅,HR({3})={1,2,3}, then HR(∅)⊆clM(R)(∅) and HR({3})⊇clM(R)({3}).From the above example, we see that the closure operator of the matroid induced by a reflexive and transitive relation dose not correspond to the upper approximation operator of the relation. A condition, when the closure operator contains the upper approximation operator, is studied in the following proposition. First, we present a remark.Remark 3.14.
SupposeR is an equivalence relation on U. According to Definition 2.2 and Proposition 2.4, HR(X)=X∪{u∈Xc:∃x∈X s.t. x∈RNR(u)}. According to Definition 3.1, C(R)={RNR(x):x∈U}.Proposition 3.15.
LetR be an equivalence relation on U and M(R) the matroid induced by R. If for all C∈C(R),|C|≤2, then HR(X)⊆clM(R)(X) for all X⊆U.Proof.
According to Definition2.10, we need only to prove that {u∈Xc:∃x∈X s.t. x∈RNR(u)}⊆{u∈Xc:RNR(u)⊆X∪{u}}. Since R is an equivalence relation, and for all C∈C(R),|C|≤2, then x∈RNR(x) and |RNR(x)|≤2 for all x∈U. When |RNR(x)|=1, that is, RNR(x)={x}, then {u∈Xc:∃x∈X s.t. x∈RNR(u)}=∅, therefore {u∈Xc:∃x∈X s.t. x∈RNR(u)}⊆{u∈Xc:RNR(u)⊆X∪{u}}. When |RNR(x)|=2, for all u∈{u∈Xc:∃x∈X s.t. x∈RNR(u)},RNR(u)={x,u}, then RNR(u)⊆X∪{u}, that is, {u∈Xc:∃x∈X s.t. x∈RNR(u)}⊆{u∈Xc:RNR(u)⊆X∪{u}}. To sum up, this completes the proof.In fact, for an equivalence relation on a universe and any subset of the universe, its closure with respect to the induced matroid can be expressed by the union of its upper approximation with respect to the relation and the family of some elements whose neighborhood is equal to itself.Proposition 3.16.
LetR be an equivalence relation on U and M(R) the matroid induced by R. If for all C∈C(R),|C|≤2, then clM(R)(X)=HR(X)∪{u∈Xc:RNR(u)={u}} for all X⊆U.Proof.
We need only to prove{u∈Xc:RNR(u)⊆X∪{u}}={u∈Xc:∃x∈X s.t. x∈RNR(u)}∪{u∈Xc:RNR(u)={u}}. Since R is equivalence relation and |C|≤2 for all C∈C(R), then |RNR(x)|≤2 for all x∈U. Therefore, it is straightforward to obtain {u∈Xc:RNR(u)⊆X∪{u}}={u∈Xc:∃x∈X s.t. x∈RNR(u)}∪{u∈Xc:RNR(u)={u}}, that is, clM(R)(X)=HR(X)∪{u∈Xc:RNR(u)={u}}.Similarly, can the upper approximation operator of an equivalence relation contain the closure operator of the matroid induced by the equivalence relation when the cardinality of any circuit of the matroid is equal or greater than 2?Proposition 3.17.
LetR be an equivalence relation on U and M(R) the matroid induced by R. If for all C∈C(R),|C|≥2, then clM(R)(X)⊆HR(X) for all X⊆U.Proof.
According to Definition2.10, we need only to prove {u∈Xc:∃C∈C(R) s.t. u∈C⊆X∪{u}}⊆{u∈Xc:∃x∈X s.t. x∈RNR(u)}. For all u∈{u∈Xc:∃C∈C(R) s.t. u∈C⊆X∪{u}}, then RNR(u)⊆X∪{u}. And |RNR(u)|≥2, then there exists at least an element x∈X such that x∈RNR(u), that is, u∈{u∈Xc:∃x∈X s.t. x∈RNR(u)}. To sum up, this completes the proof.A sufficient and necessary condition, when the upper approximation operator of an equivalence relation is equal to the closure operator of the matroid induced by the equivalence relation, is investigated in the following theorem. First, we introduce a special matroid called 2-circuit matroid.Definition 3.18 ((2-circuit matroid) see [22]).
LetM=(U,I) be a matroid. If for all C∈C(M),|C|=2, then we say M is a 2-circuit matroid.Theorem 3.19.
LetR be an equivalence relation on U and M(R) the matroid induced by R. M(R) is a 2-circuit matroid if and only if HR(X)=clM(R)(X) for all X⊆U.Proof.
According to Definition2.10, we need only to prove for all x∈U, |RNR(x)|=2 if and only if {u∈Xc:∃x∈X s.t. x∈RNR(u)}={u∈Xc:RNR(u)⊆X∪{u}} for all X⊆U.(⇒):
according to Propositions3.15 and 3.17, it is straightforward.(⇐):
we prove this by reductio.
On the one hand, suppose there existsx∈U such that |RNR(x)|=1. Suppose X=∅. Then x∈{u∈Xc:RNR(u)⊆X∪{u}}. According to (1H) of Proposition 2.3, HR(∅)=∅. Therefore HR(∅)⊂clM(R)(∅) which is contradictory with HR(X)=clM(R)(X) for all X⊆U.
On the other hand, suppose there existsy∈U such that |RNR(y)|≥3. Suppose X∩RNR(y)={x}, then y∈{u∈Xc:∃x∈X s.t. x∈RNR(u)}. Since y∈RNR(y)⊈X, then RNR(y)⊈X∪{y}, which is contradictory with {u∈Xc:∃x∈X s.t. x∈RNR(u)}={u∈Xc:RNR(u)⊆X∪{u}} for all X⊆U. Therefore, for all x∈U, |RNR(x)|=2.


### 3.2. Construction of Equivalence Relation by Matroid

In order to further study the matroidal structure of the rough set based on a serial and transitive relation, we consider the inverse of the construction in Section3.1: inducing a relation by a matroid. Firstly, through the connectedness in a matroid, a relation can be obtained.Definition 3.20 (see [34]).
LetM=(U,I) be a matroid. We define a relation R(M) on U as follows: for all x,y∈U,
(3.5)(x,y)∈R(M)⟺x=yor∃C∈C(M)s.t.{x,y}⊆C.
We say R(M) is induced by M.The following example is to illustrate the construction of a relation from a matroid.Example 3.21.
LetM=(U,I) be a matroid, where U={1,2,3} and I={∅,{1}}. Since C(M)={{2},{3}}, then according to Definition 3.20, R(M)={(1,1),(2,2),(3,3)}.In fact, according to Definition3.20, the relation induced by a matroid is an equivalence relation.Proposition 3.22 (see [34]).
LetM=(U,I) be a matroid. Then R(M) is an equivalence relation on U.The following example is presented to illustrate that different matroids generate the same relation.Example 3.23.
LetM1=(U,I1),M2=(U,I2) be two matroids where U={1,2,3},I1={∅,{1},{2}} and I2={∅,{1},{2},{3},{1,3},{2,3}}. Since C(M1)={{1,2},{3}},C(M2)={{1,2}}, according to Definition 3.20, then R(M1)=R(M2)={(1,1),(1,2),(2,1),(2,2),(3,3)}.Similarly, we will study the relationship between the closure operator of a matroid and the upper approximation operator of the equivalence relation induced by the matroid in the following proposition.Proposition 3.24.
LetM=(U,I) be a matroid and R(M) the relation induced by M. If clM(∅)=∅, then clM(X)⊆HR(M)(X) for all X⊆U.Proof.
SinceR(M) is an equivalence relation, according to Definition 2.10, we need only to prove {u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}⊆{u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}. Since clM(∅)=∅, then {x}∉C(M) for all x∈U. For all u∈{u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}, there exists at least one element x∈X such that {x,u}⊆C⊆X∪{u}. According to Definition 3.20, (u,x)∈R(M), that is, x∈RNR(M)(u). Therefore u∈{u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}. To sum up, this completes the proof.The above proposition can be illustrated by the following example.Example 3.25.
LetM=(U,I) be a matroid where U={1,2,3} and I={∅,{1},{2},{3},{1,2},{1,3},{2,3}}. Since C(M)={{1,2,3}},  then R(M)=U×U. Therefore clM(∅)=∅,clM({1})={1},clM({2})={2},clM({3})={3},clM({1,2})=clM({1,3})=clM({2,3})=clM({1,2,3})={1,2,3} and HR(M)(∅)=∅,HR(M)({1})= HR(M)({2})=HR(M)({3})=HR(M)({1,2})= HR(M)({1,3})=HR(M)({2,3})=HR(M)({1,2,3})={1,2,3}. Hence for all X⊆U, clM(X)⊆HR(M)(X).According to Proposition3.24, the closure operator of a matroid is contained in the upper approximation operator of the relation induced by the matroid, when the closure of empty set is equal to empty set. We consider an issue that when the closure of empty set is not equal to empty set, can the closure operator contain the upper approximation operator? A counterexample is given in the following.Example 3.26.
LetU={1,2,3,4} and M a matroid on U, where C(M)={{1,2,3},{4}}. Since clM(∅)={4}, then clM({1})={1,4}. Since U/R(M)=C(M), then HR(M)({1})={1,2,3}. Therefore, HR(M)({1})⊈clM({1}).Under what condition the closure operator contains the upper approximation operator? In the following proposition, we study this issue.Proposition 3.27.
LetM=(U,I) be a matroid and R(M) the relation induced by M. If for all C∈C(M),|C|≤2, then HR(M)(X)⊆clM(X) for all X⊆U.Proof.
According to Proposition3.22 and Definitions 2.2 and 2.10, we need only to prove {u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}⊆{u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}. For all u∈{u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}, then (u,x)∈R(M). According to Definition 3.20, there exists C∈C(M) such that {x,u}⊆C. Since for all C∈C(M),|C|≤2, then C={x,u}, that is, u∈C⊆X∪{u}. Therefore, u∈{u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}. To sum up, this completes the proof.In the following theorem, we investigate a sufficient and necessary condition when the closure operator of a matroid is equal to the upper approximation operator of the relation induced by the matroid.Theorem 3.28.
LetM=(U,I) be a matroid and R(M) the relation induced by M. For all X⊆U, HR(M)(X)=clM(X) if and only if C(M)=∅ or M is a 2-circuit matroid.Proof.
(1) SinceC(M)=∅, according to Definition 3.20, R(M)={(x,x):x∈U}. According to Definition 2.10, for all X⊆U, clM(X)=X. And according to Definition 2.2, for all X⊆U, HR(M)(X)=X. Therefore, clM(X)=HR(M)(X)=X for all X⊆U. Similarly, if clM(X)=HR(M)(X)=X, then C(M)=∅.
(2) According to Proposition3.22 and Definitions 2.2 and 2.10, we need only to prove {u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}={u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}} if and only if M is a 2-circuit matroid.(⇐):
sinceM is a 2-circuit matroid, then for all C∈C(M),|C|=2. {u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}={u∈Xc:∃x∈X s.t. (x,u)∈R(M)}={u∈Xc:∃x∈X s.t. ∃C∈C(M), {x,u}⊆C}={u∈Xc:∃C∈C(M), s.t. {x,u}=C⊆X∪{u}}= {u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}.(⇒):
according to Propositions3.24 and 3.27, it is straightforward.


## 3.1. Construction of Matroid by Serial and Transitive Relation

In [19], for an equivalence relation on a universe, we present a matroidal structure whose family of all circuits is the partition induced by the equivalence relation. Through extending equivalence relations, in this subsection, we propose a matroidal structure which is based on a serial and transitive relation. First, for a relation on a universe, we define a family of sets, namely, the family of all minimal neighborhoods.Definition 3.1 (the family of all minimal neighborhoods).
LetR be a relation on U. We define a family of sets with respect to R as follows:
(3.1)C(R)=FMIN{RN(x):x∈U}.
We call C(R) the family of all minimal neighborhoods of R.In the following proposition, we will prove the family of all minimal neighborhoods of a relation on a universe satisfies the circuit axioms of matroids when the relation is serial and transitive.Proposition 3.2.
LetR be a relation on U. If R is serial and transitive, then C(R) satisfies (C1), (C2), and (C3) in Proposition 2.9.Proof.
(C1): SinceR is a serial relation, according to (1) of Definition 2.5, then ∅∉C(R).
(C2): According to Definitions3.1 and 2.7, it is straightforward that C(R) satisfies (C2).
(C3): IfC1,C2∈C(R), and C1≠C2, then there exist x1,x2∈U, and x1≠x2 such that C1=RN(x1),C2=RN(x2). If x∈C1∩C2, that is, x∈RN(x1)∩RN(x2), then x∈RN(x1) and x∈RN(x2). Since R is a transitive relation, according to (2) of Definition 2.5, we can obtain that RN(x)⊆RN(x1) and RN(x)⊆RN(x2). According to Definition 3.1, we can obtain RN(x)=RN(x1)=RN(x2) which is contradictory with RN(x1)≠RN(x2). Therefore, for any C1,C2∈C(R), and C1≠C2, C1∩C2=∅ when R is transitive, then, it is straightforward to see that C(R) satisfies (C3) in Proposition 2.9.It is natural to ask the following question: “when the family of all minimal neighborhoods of a relation satisfies the circuit axioms of matroids, is the relation serial and transitive?”. In the following proposition, we will solve this issue.Proposition 3.3.
LetR be a relation on U. If C(R) satisfies (C1), (C2), and (C3) in Proposition 2.9, then R is serial.Proof.
According to (C1) of Proposition2.9 and Definition 3.1, RN(x)≠∅ for any x∈U. According to Definition 2.5, R is serial.When the family of all minimal neighborhoods of a relation satisfies the circuit axioms of matroids, the relation is not always a transitive relation as shown in the following example.Example 3.4.
LetU={1,2,3} and R={(1,2),(1,3),(2,1),(2,3),(3,1)} a relation on U. Since RN(1)={2,3},RN(2)={1,3},RN(3)={1}, then C(R)={{1},{2,3}}. According to Proposition 2.9, C(R) satisfies the circuit axioms of matroids. We see that (1,2)∈R,(2,1)∈R, but (1,1)∉R,(2,2)∉R, so R is not transitive.In this paper, we consider that the family of all minimal neighborhoods of a relation can generate a matroid when the relation is serial and transitive.Definition 3.5.
LetR be a serial and transitive relation on U. The matroid with C(R) as its circuit family is denoted by M(R)=(U,I(R)), where I(R)=Opp(Upp(C(R))). We say M(R) is the matroid induced by R.The matroid induced by a serial and transitive relation can be illustrated by the following example.Example 3.6.
LetU={1,2,3} and R={(1,1),(1,3),(2,1),(2,3),(3,3)} a serial and transitive relation on U. Since RN(1)=RN(2)={1,3},RN(3)={3}, then C(R)={{3}}. Therefore, M(R)=(U,I(R)) where I(R)={∅,{1},{2},{1,2}}.Generally speaking, a matroid is defined from the viewpoint of independent sets. In the following, we will investigate the independent sets of the matroid induced by a serial and transitive relation.Proposition 3.7.
LetR be a serial and transitive relation on U and M(R) the matroid induced by R. Then,
(3.2)I(R)={I⊆U:∀x∈U,RN(x)⊈I}.Proof.
According to Definition3.5, I(R)=Opp(Upp(C(R))).(⊆):
for allX∉Opp(Upp(C(R))), that is, X∈Upp(C(R)), according to Definitions 2.7 and 3.1, there exists x∈U such that RN(x)⊆X. Hence X∉{I⊆U:forallx∈U,RN(x)⊈I}, that is, X∉I(R). This proves that I(R)⊆Opp(Upp(C(R))).(⊇):
supposeX∉I(R), that is, X∉{I⊆U:forallx∈U,RN(x)⊈I}. Then there exists x∈U such that RN(x)⊆X, in other words, X∈Upp(C(R)), that is, X∉Opp(Upp(C(R))). This proves that I(R)⊇Opp(Upp(C(R))).To illustrate the independent sets of a matroid induced by a serial and transitive relation, the following example is given.Example 3.8.
LetU={1,2,3} and R={(1,3),(2,3),(3,3)} a serial and transitive relation on U. Since RN(1)=RN(2)=RN(3)={3}, then {3}⊈∅,{3}⊈{1},{3}⊈{2},{3}⊈{1,2}. Therefore M(R)=(U,I(R)) where I(R)={∅,{1},{2},{1,2}}.The lower and upper approximation operators are constructed through the neighborhood in generalized rough sets based on relations. In the following proposition, we will study the independent sets of the matroid induced by a serial and transitive relation through the lower approximation operator.Proposition 3.9.
LetR be a serial and transitive relation on U and M(R) the matroid induced by R. Then,
(3.3)I(R)={I⊆U:L(I)=∅}.Proof.
According to Definition2.2 and Proposition 3.7, it is straightforward.Because of the duality of the lower and upper approximation operators, we obtain the independent sets of the matroid induced by a serial and transitive relation through the upper approximation operator.Corollary 3.10.
LetR be a serial and transitive relation on U and M(R) the matroid induced by R. Then,
(3.4)I(R)={I⊆U:H(Ic)=U}.Proof.
According to (4LH) of Propositions2.3 and 3.9, it is straightforward.From Examples3.6 and 3.8, we see that two different relations on a universe generate the same matroid. We study under what conditions two relations on a universe can generate the same matroid. If a relation is transitive, then the reflexive closure of the relation is transitive, but the symmetric closure of the relation is not always transitive. Therefore, we consider the relationship between the matroids induced by a serial and transitive relation and the reflexive closure of the relation. First, we introduce the reflexive closure of a relation on a nonempty universe.Definition 3.11 ((reflexive closure of a relation) see [31]).
LetU be a nonempty universe and R a relation on U. We denote r(R) as the reflexive closure of R, where r(R)=R∪{(x,x):x∈U}.The relationship between the two matroids induced by a serial and transitive relation and its reflexive closure is studied in the following proposition.Proposition 3.12.
LetR be a serial and transitive relation on U. Then M(R)=M(r(R)).Proof.
According to Proposition2.9, we need only to prove C(R)=C(r(R)). According to Definition 3.1, C(R)=FMIN{RNR(x):x∈U} and C(r(R))=FMIN{RNr(R)(x):x∈U}. According to Definition 3.11, r(R)=R∪{(x,x):x∈U}, then C(r(R))=FMIN{RNR(x)∪{x}:x∈U}.(⊆):
for allRNR(x)∈C(R), on the one hand, x∈RNR(x), then RNR(x)∈C(r(R)). On the other hand, x∉RNR(x). Since R is serial, then there exists y∈U such that y∈RNR(x). Since R is transitive, then RNR(y)⊆RNR(x). And RNR(x)∈C(R), then y∈RNR(y)=RNR(x). Therefore, {y}∪RNR(y)⊂{x}∪RNR(x), that is, RNR(y)∈C(r(R)). In other words, RNR(x)∈C(r(R)). Hence C(R)⊆C(r(R)).(⊇):
for allRNr(R)(x)∈C(r(R)), that is, RNR(x)∪{x}∈C(r(R)). If x∈RNR(x), then RNr(R)(x)∈C(R). If x∉RNR(x), that is, RNR(x)⊂RNr(R)(x), then RNR(x)∈C(R). If RNR(x)∉C(R), then there exists y∈U such that RNR(y)⊂RNR(x) and RNR(y)∈C(R). Since R is serial, then there exists z∈U such that z∈RNR(y). And R is transitive, then RNR(z)⊆RNR(y). Therefore z∈RNR(z)=RNR(y), that is, RNR(z)∪{z}=RNR(y). Hence RNR(z)∪{z}⊂RNR(x)⊂RNR(x)∪{x} which is contradictory with RNR(x)∪{x}∈C(r(R)). Since R is serial, then there exists y∈U such that y∈RNR(x). Since R is transitive, then RNR(y)⊆RNR(x). And RNR(x)∈C(R), then y∈RNR(y)=RNR(x), that is, {y}∪RNR(y)⊂{x}∪RNR(x) which is contradictory with RNR(x)∪{x}∈C(r(R)). Hence RNr(R)(x)∈C(R), that is, C(r(R))⊆C(R).In fact, for a universe, any different relations generate the same matroid if and only if the families of all minimal neighborhoods are equal to each other according to Proposition2.9.It is known that the upper approximation operator induced by a reflexive and transitive relation is exactly the closure operator of a topology [11, 32, 33]. We see that a matroid has its own closure operator. In this paper, we will not discuss the relationship between the closure operator of a topology and one of a matroid. We will study the connection between the upper approximation operator of a rough set and the closure operator of a matroid. In the following, we investigate the relationship between the upper approximation operator of a relation and the closure operator of the matroid induced by the relation.In a matroid, the closure of any subset contains the subset itself. When a relation on a universe is reflexive, the upper approximation of any subset contains the subset itself. If a relation is reflexive, then it is serial. According to Definition3.1, a reflexive and transitive relation can induce a matroid. We will study the relationship between the upper approximation operator induced by a reflexive and transitive relation and the closure operator of the matroid induced by the relation. A counterexample is given in the following.Example 3.13.
LetU={1,2,3} and R={(1,1),(1,3),(2,2),(2,3),(3,3)} a reflexive and transitive relation on U. Since RN(1)={1,3},RN(2)={2,3},RN(3)={3}, then C(R)={{3}}. Therefore, clM(R)(∅)={3},clM(R)({3})={3}. Since HR(∅)=∅,HR({3})={1,2,3}, then HR(∅)⊆clM(R)(∅) and HR({3})⊇clM(R)({3}).From the above example, we see that the closure operator of the matroid induced by a reflexive and transitive relation dose not correspond to the upper approximation operator of the relation. A condition, when the closure operator contains the upper approximation operator, is studied in the following proposition. First, we present a remark.Remark 3.14.
SupposeR is an equivalence relation on U. According to Definition 2.2 and Proposition 2.4, HR(X)=X∪{u∈Xc:∃x∈X s.t. x∈RNR(u)}. According to Definition 3.1, C(R)={RNR(x):x∈U}.Proposition 3.15.
LetR be an equivalence relation on U and M(R) the matroid induced by R. If for all C∈C(R),|C|≤2, then HR(X)⊆clM(R)(X) for all X⊆U.Proof.
According to Definition2.10, we need only to prove that {u∈Xc:∃x∈X s.t. x∈RNR(u)}⊆{u∈Xc:RNR(u)⊆X∪{u}}. Since R is an equivalence relation, and for all C∈C(R),|C|≤2, then x∈RNR(x) and |RNR(x)|≤2 for all x∈U. When |RNR(x)|=1, that is, RNR(x)={x}, then {u∈Xc:∃x∈X s.t. x∈RNR(u)}=∅, therefore {u∈Xc:∃x∈X s.t. x∈RNR(u)}⊆{u∈Xc:RNR(u)⊆X∪{u}}. When |RNR(x)|=2, for all u∈{u∈Xc:∃x∈X s.t. x∈RNR(u)},RNR(u)={x,u}, then RNR(u)⊆X∪{u}, that is, {u∈Xc:∃x∈X s.t. x∈RNR(u)}⊆{u∈Xc:RNR(u)⊆X∪{u}}. To sum up, this completes the proof.In fact, for an equivalence relation on a universe and any subset of the universe, its closure with respect to the induced matroid can be expressed by the union of its upper approximation with respect to the relation and the family of some elements whose neighborhood is equal to itself.Proposition 3.16.
LetR be an equivalence relation on U and M(R) the matroid induced by R. If for all C∈C(R),|C|≤2, then clM(R)(X)=HR(X)∪{u∈Xc:RNR(u)={u}} for all X⊆U.Proof.
We need only to prove{u∈Xc:RNR(u)⊆X∪{u}}={u∈Xc:∃x∈X s.t. x∈RNR(u)}∪{u∈Xc:RNR(u)={u}}. Since R is equivalence relation and |C|≤2 for all C∈C(R), then |RNR(x)|≤2 for all x∈U. Therefore, it is straightforward to obtain {u∈Xc:RNR(u)⊆X∪{u}}={u∈Xc:∃x∈X s.t. x∈RNR(u)}∪{u∈Xc:RNR(u)={u}}, that is, clM(R)(X)=HR(X)∪{u∈Xc:RNR(u)={u}}.Similarly, can the upper approximation operator of an equivalence relation contain the closure operator of the matroid induced by the equivalence relation when the cardinality of any circuit of the matroid is equal or greater than 2?Proposition 3.17.
LetR be an equivalence relation on U and M(R) the matroid induced by R. If for all C∈C(R),|C|≥2, then clM(R)(X)⊆HR(X) for all X⊆U.Proof.
According to Definition2.10, we need only to prove {u∈Xc:∃C∈C(R) s.t. u∈C⊆X∪{u}}⊆{u∈Xc:∃x∈X s.t. x∈RNR(u)}. For all u∈{u∈Xc:∃C∈C(R) s.t. u∈C⊆X∪{u}}, then RNR(u)⊆X∪{u}. And |RNR(u)|≥2, then there exists at least an element x∈X such that x∈RNR(u), that is, u∈{u∈Xc:∃x∈X s.t. x∈RNR(u)}. To sum up, this completes the proof.A sufficient and necessary condition, when the upper approximation operator of an equivalence relation is equal to the closure operator of the matroid induced by the equivalence relation, is investigated in the following theorem. First, we introduce a special matroid called 2-circuit matroid.Definition 3.18 ((2-circuit matroid) see [22]).
LetM=(U,I) be a matroid. If for all C∈C(M),|C|=2, then we say M is a 2-circuit matroid.Theorem 3.19.
LetR be an equivalence relation on U and M(R) the matroid induced by R. M(R) is a 2-circuit matroid if and only if HR(X)=clM(R)(X) for all X⊆U.Proof.
According to Definition2.10, we need only to prove for all x∈U, |RNR(x)|=2 if and only if {u∈Xc:∃x∈X s.t. x∈RNR(u)}={u∈Xc:RNR(u)⊆X∪{u}} for all X⊆U.(⇒):
according to Propositions3.15 and 3.17, it is straightforward.(⇐):
we prove this by reductio.
On the one hand, suppose there existsx∈U such that |RNR(x)|=1. Suppose X=∅. Then x∈{u∈Xc:RNR(u)⊆X∪{u}}. According to (1H) of Proposition 2.3, HR(∅)=∅. Therefore HR(∅)⊂clM(R)(∅) which is contradictory with HR(X)=clM(R)(X) for all X⊆U.
On the other hand, suppose there existsy∈U such that |RNR(y)|≥3. Suppose X∩RNR(y)={x}, then y∈{u∈Xc:∃x∈X s.t. x∈RNR(u)}. Since y∈RNR(y)⊈X, then RNR(y)⊈X∪{y}, which is contradictory with {u∈Xc:∃x∈X s.t. x∈RNR(u)}={u∈Xc:RNR(u)⊆X∪{u}} for all X⊆U. Therefore, for all x∈U, |RNR(x)|=2.


## 3.2. Construction of Equivalence Relation by Matroid

In order to further study the matroidal structure of the rough set based on a serial and transitive relation, we consider the inverse of the construction in Section3.1: inducing a relation by a matroid. Firstly, through the connectedness in a matroid, a relation can be obtained.Definition 3.20 (see [34]).
LetM=(U,I) be a matroid. We define a relation R(M) on U as follows: for all x,y∈U,
(3.5)(x,y)∈R(M)⟺x=yor∃C∈C(M)s.t.{x,y}⊆C.
We say R(M) is induced by M.The following example is to illustrate the construction of a relation from a matroid.Example 3.21.
LetM=(U,I) be a matroid, where U={1,2,3} and I={∅,{1}}. Since C(M)={{2},{3}}, then according to Definition 3.20, R(M)={(1,1),(2,2),(3,3)}.In fact, according to Definition3.20, the relation induced by a matroid is an equivalence relation.Proposition 3.22 (see [34]).
LetM=(U,I) be a matroid. Then R(M) is an equivalence relation on U.The following example is presented to illustrate that different matroids generate the same relation.Example 3.23.
LetM1=(U,I1),M2=(U,I2) be two matroids where U={1,2,3},I1={∅,{1},{2}} and I2={∅,{1},{2},{3},{1,3},{2,3}}. Since C(M1)={{1,2},{3}},C(M2)={{1,2}}, according to Definition 3.20, then R(M1)=R(M2)={(1,1),(1,2),(2,1),(2,2),(3,3)}.Similarly, we will study the relationship between the closure operator of a matroid and the upper approximation operator of the equivalence relation induced by the matroid in the following proposition.Proposition 3.24.
LetM=(U,I) be a matroid and R(M) the relation induced by M. If clM(∅)=∅, then clM(X)⊆HR(M)(X) for all X⊆U.Proof.
SinceR(M) is an equivalence relation, according to Definition 2.10, we need only to prove {u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}⊆{u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}. Since clM(∅)=∅, then {x}∉C(M) for all x∈U. For all u∈{u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}, there exists at least one element x∈X such that {x,u}⊆C⊆X∪{u}. According to Definition 3.20, (u,x)∈R(M), that is, x∈RNR(M)(u). Therefore u∈{u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}. To sum up, this completes the proof.The above proposition can be illustrated by the following example.Example 3.25.
LetM=(U,I) be a matroid where U={1,2,3} and I={∅,{1},{2},{3},{1,2},{1,3},{2,3}}. Since C(M)={{1,2,3}},  then R(M)=U×U. Therefore clM(∅)=∅,clM({1})={1},clM({2})={2},clM({3})={3},clM({1,2})=clM({1,3})=clM({2,3})=clM({1,2,3})={1,2,3} and HR(M)(∅)=∅,HR(M)({1})= HR(M)({2})=HR(M)({3})=HR(M)({1,2})= HR(M)({1,3})=HR(M)({2,3})=HR(M)({1,2,3})={1,2,3}. Hence for all X⊆U, clM(X)⊆HR(M)(X).According to Proposition3.24, the closure operator of a matroid is contained in the upper approximation operator of the relation induced by the matroid, when the closure of empty set is equal to empty set. We consider an issue that when the closure of empty set is not equal to empty set, can the closure operator contain the upper approximation operator? A counterexample is given in the following.Example 3.26.
LetU={1,2,3,4} and M a matroid on U, where C(M)={{1,2,3},{4}}. Since clM(∅)={4}, then clM({1})={1,4}. Since U/R(M)=C(M), then HR(M)({1})={1,2,3}. Therefore, HR(M)({1})⊈clM({1}).Under what condition the closure operator contains the upper approximation operator? In the following proposition, we study this issue.Proposition 3.27.
LetM=(U,I) be a matroid and R(M) the relation induced by M. If for all C∈C(M),|C|≤2, then HR(M)(X)⊆clM(X) for all X⊆U.Proof.
According to Proposition3.22 and Definitions 2.2 and 2.10, we need only to prove {u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}⊆{u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}. For all u∈{u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}, then (u,x)∈R(M). According to Definition 3.20, there exists C∈C(M) such that {x,u}⊆C. Since for all C∈C(M),|C|≤2, then C={x,u}, that is, u∈C⊆X∪{u}. Therefore, u∈{u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}. To sum up, this completes the proof.In the following theorem, we investigate a sufficient and necessary condition when the closure operator of a matroid is equal to the upper approximation operator of the relation induced by the matroid.Theorem 3.28.
LetM=(U,I) be a matroid and R(M) the relation induced by M. For all X⊆U, HR(M)(X)=clM(X) if and only if C(M)=∅ or M is a 2-circuit matroid.Proof.
(1) SinceC(M)=∅, according to Definition 3.20, R(M)={(x,x):x∈U}. According to Definition 2.10, for all X⊆U, clM(X)=X. And according to Definition 2.2, for all X⊆U, HR(M)(X)=X. Therefore, clM(X)=HR(M)(X)=X for all X⊆U. Similarly, if clM(X)=HR(M)(X)=X, then C(M)=∅.
(2) According to Proposition3.22 and Definitions 2.2 and 2.10, we need only to prove {u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}={u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}} if and only if M is a 2-circuit matroid.(⇐):
sinceM is a 2-circuit matroid, then for all C∈C(M),|C|=2. {u∈Xc:∃x∈X s.t. x∈RNR(M)(u)}={u∈Xc:∃x∈X s.t. (x,u)∈R(M)}={u∈Xc:∃x∈X s.t. ∃C∈C(M), {x,u}⊆C}={u∈Xc:∃C∈C(M), s.t. {x,u}=C⊆X∪{u}}= {u∈Xc:∃C∈C(M) s.t. u∈C⊆X∪{u}}.(⇒):
according to Propositions3.24 and 3.27, it is straightforward.


## 4. Relationships between the Two Constructions

In this section, we study the relationships between the two constructions in Section3. The first construction takes a relation and yields a matroid, and the second construction takes a matroid and then yields a relation. Firstly, given a matroid, it can generate an equivalence relation, and the equivalence relation can generate a matroid, then the connection between the original matroid and the induced matroid is built. In order to study the connection, we introduce the definition of the finer set family on a universe.Definition 4.1.
LetF1,F2 be two set families on U. If for all F1∈F1, there exists F2∈F2 such that F1⊆F2, then we say F1 is finer than F2 and denote it as F1≤F2.In the following proposition, we will represent the relationship between the circuits of a matroid and the circuits of the matroid induced by the equivalence relation which is generated by the original matroid.Proposition 4.2.
LetM=(U,I) be a matroid. Then C(M)≤C(M(R(M))).Proof.
For allC∈C(M), suppose x,y∈C. According to Definition 3.20, we can obtain (x,y)∈R(M). According to Proposition 3.22, R(M) is an equivalence relation on U, then x,y∈RNR(M)(x). According to Definitions 3.1 and 3.5, C(M(R(M)))=FMIN{RNR(M)(z):z∈U}. Since FMIN{RNR(M)(z):z∈U}=U/R(M) and RNR(M)(x)∈U/R(M), then there exists RNR(M)(x)∈C(M(R(M))) such that C⊆RNR(M)(x). According to Definition 4.1, C(M)≤C(M(R(M))).In order to further comprehend Proposition4.2, the following example is given.Example 4.3.
LetM=(U,I) a matroid, where U={1,2,3} and I={∅,{1},{2},{3}}. Since C(M)={{1,2},{1,3},{2,3}}, according to Definition 3.20, R(M)={(1,1),(1,2),(1,3), (2,2),(2,1),(2,3),(3,3),(3,1),(3,2)}. According to Definitions 3.1 and 3.5, C(M(R(M)))={{1,2,3}}. Therefore C(M)≤C(M(R(M))).A matroid can induce an equivalence relation, and the equivalence relation can generate a matroid, then a sufficient and necessary condition when the original matroid is equal to the induced matroid is studied in the following theorem.Theorem 4.4.
LetM=(U,I) be a matroid. Then, M(R(M))=M if and only if C(M) is a partition on U.Proof.
According to Proposition3.7, we need only to prove C(M)=C(M(R(M))) if and only if C(M) is a partition on U.(⇒):
according to Proposition3.22, R(M) is an equivalence relation on U. According to Definitions 3.1 and 3.5, C(M(R(M)))=U/R(M). Since C(M)=C(M(R(M))), then C(M) is a partition on U.(⇐):
ifC(M) is a partition on U, according to Definition 3.20, then U/R(M)=C(M). According to Definitions 3.1 and 3.5, then C(M(R(M)))=U/R(M). Therefore C(M)=C(M(R(M))).Similarly, a serial and transitive relation can generate a matroid, and the matroid can generate an equivalence relation, then the relationship between the original relation and the induced equivalence relation is studied as follows. First, we present a lemma about the transitivity of a relation.Lemma 4.5.
LetR be a transitive relation on U. For all RN(x),RN(y)∈FMIN{RN(z):z∈U}, if RN(x)≠RN(y), then RN(x)∩RN(y)=∅.Proof.
SupposeRN(x)∩RN(y)≠∅, then there exists z∈U such that z∈RN(x)∩RN(y), that is, z∈RN(x),z∈RN(y). According to Definition 2.5, RN(z)⊆RN(x),RN(z)⊆RN(y). Since RN(x)≠RN(y), then RN(z)⊂RN(x),RN(z)⊂RN(y), which is contradictory with RN(x),RN(y)∈FMIN{RN(z):z∈U}. Therefore, RN(x)∩RN(y)=∅.If a relation is reflexive, then it is also serial. Therefore, a reflexive and transitive relation can generate a matroid according to Definition3.5.Proposition 4.6.
LetR be a reflexive and transitive relation on U. Then R(M(R))⊆R.Proof.
According to Definitions3.20, 3.1, and 3.5, we can obtain that for all (x,y)∈R(M(R)), if x≠y, then there exists z∈U such that {x,y}⊆RN(z)∈FMIN{RNR(x):x∈U}, that is, x∈RNR(z),y∈RNR(z). Since R is reflexive and transitive, then x∈RNR(x)⊆RNR(z), that is, x∈RNR(x)∩RNR(z). Since RNR(z)∈FMIN{RNR(x):x∈U}, according to Lemma 4.5, RNR(x)=RNR(z), then z∈RNR(x), that is, (x,z)∈R. Since y∈RNR(z), that is, (z,y)∈R, and R is transitive, then (x,y)∈R. Since R is reflexive, then (x,x)∈R for all x∈U. Hence R(M(R))⊆R.The above proposition can be illustrated by the following example.Example 4.7.
LetU={1,2,3,4} and R={(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(3,2),(4,4)} a reflexive and transitive relation on U. Since RNR(1)={1,2,3},RNR(2)=RNR(3)={2,3},RNR(4)={4}, then C(M(R))=FMIN{RNR(x):x∈U}={{2,3},{4}}. Therefore, R(M(R))={(1,1),(2,2),(2,3), (3,3),(3,2),(4,4)}. We can see that R(M(R))⊆R.A sufficient and necessary condition, when the relation is equal to the induced equivalence relation, is investigated in the following theorem.Theorem 4.8.
LetR be a serial and transitive relation on U. Then, R(M(R))=R if and only if R is an equivalence relation.Proof.
(⇒) according to Proposition 3.22, R(M(R)) is an equivalence relation on U. Since R(M(R))=R, then R is an equivalence relation.
(⇐)R is an equivalence relation, then C(M(R))=U/R. According to Definition 3.20 and Proposition 3.22, it is straightforward to prove that R(M(R))=R.


## 5. Conclusions

In order to broaden the theoretical and application fields of rough sets and matroids, their connections with other theories have been built. In this paper, we connected matroids and generalized rough sets based on relations. For a serial and transitive relation on a universe, we proposed a matroidal structure through the neighborhood of the relation. First, we defined the family of all minimal neighborhoods of a relation on a universe and proved it to satisfy the circuit axioms of matroids when the relation was serial and transitive. The independent sets of the matroid were studied, and the connections between the upper approximation operator of the relation and the closure operator of the matroid were investigated. In order to study the matroidal structure of the rough set based on a serial and transitive, we investigated the inverse of the above construction: inducing a relation by a matroid. Through the connectedness in a matroid, a relation was obtained and proved to be an equivalence relation. And the closure operator of the matroid was equal to the upper approximation operator of the induced equivalence relation if and only if the matroid was a 2-circuit matroid. Second, the relationships between the above two constructions were investigated. For a matroid on a universe, it induced an equivalence relation, and the equivalence relation generated a matroid, then the original matroid was equal to the induced matroid if and only if the circuit family of the original matroid was a partition on the universe. For a serial and transitive relation on a universe, it generated a matroid, and the matroid induced an equivalence relation, then the original relation was equal to the induced equivalence relation if and only if the original relation was an equivalence relation.



---

*Source: 429737-2012-12-04.xml*