1 Introduction

The vagueness and incompleteness of knowledge are common phenomenons in information systems. In order to deal with these knowledge, many theories and methods have been proposed, including rough set theory [1], fuzzy set theory [2], linguistic dynamic systems [3], computing with words [4, 5], and knowledge classifying [6–8].

Rough set theory is based on equivalence relations, however, it has been extended to generalized rough sets based on relations [9–14], covering-based rough sets [15–22], and fuzzy rough sets [23, 24]. And generalized rough sets based on relations are the research concentration of this paper.

Matroids are important structures both from the point of view of theory and from that of application. They have been applied to a number of fields, such as combinatorial optimization, and secret communication. Therefore, matroids are more likely to enrich generalized rough sets based on relations and broaden their applications.

This paper connects generalized rough sets based on relations with matroid theory. Inspired by the rank function of the matroid, we propose the upper approximation number to induce a matroid from a relation. Specifically, a pair of approximation operators, namely, matroid approximation operators, are constructed with the rank function of the matroid induced by a relation. And the matroid approximation operators are compared with the relation approximation operators. Moreover, the closure operator of the matroid is used to characterize generalized rough sets based on relations and the symmetric relation is represented from a matroidal viewpoint.

On the other hand, the inverse problem, this is, how a matroid induces a relation, is discussed. An approach to induce the relation from a matroid is presented. Results show that two inductions are inverse when a relation is an equivalence relation.

The rest of this paper is arranged as follows. Section 2 reviews some fundamental definitions and results of rough sets and matroids. In Sect. 3, the upper approximation number is defined to induce a matroid from a relation. Section 4 constructs a pair of matroid approximation operators with the rank function of the matroid induced by a relation. In Sect. 5, we compare the matroid approximation operators and the relation approximation operators. Section 6 induces a relation from a matroid and studies its properties. In Sect. 7, the relationship between two inductions is studied. Section 8 concludes this paper.

2 Basic definitions

In this section, we review some basic concepts and results of rough sets and matroids. Rough set theory is based on discernibility relations in information systems. Discernibility relations are essentially equivalence relations. And an equivalence relation is a special binary relation. Therefore, rough set theory is extended to generalized rough sets based on relations through extending an equivalence relation to a binary relation.

Definition 1

(Binary relation [9]) Let U be a set, and U × U the product set of U and U. Any subset R of U × U is called a binary relation on U. For all (x, y) ∈ U × U, if (x, y) ∈ R, we say x has relation R with y, and denote this relationship as xRy.

Throughout this paper, a binary relation is simply called a relation. The neighborhood is of importance in generalized rough sets based on relations, and it is used to construct the approximation operators.

Definition 2

(Neighborhood [19]) Let R be a relation on U. For any x ∈ U, we call the set {y ∈ U|xRy} the successor neighborhood of x in R and denote it as \(RN_{R}(x)\). When there is no confusion, we omit the subscript R.

Reflective, symmetric, and transitive properties play important roles in characterizing relations. Rough sets based on them have been studied in more detail, such as generalized rough sets based on the reflective relations.

Definition 3

(Reflective, symmetric, and transitive [9]) Let R be a relation on U.

  • If for all x ∈ U, xRx, we say R is reflective.

  • If for all x, y ∈ U, xRy implies yRx, we say R is symmetric.

  • If for all x, y, z ∈ U, xRy and yRz imply xRz, we say R is transitive.

Definition 4

(Equivalence relation [9]) Let R be a relation on U. If R is reflective, symmetric, and transitive, we say R is an equivalence relation on U.

Definition 5

(Approximation operators [9]) Let R be a relation on U. A pair of operators \(L^{R}, H^{R}: 2^{U}\rightarrow 2^{U}, \) are defined by

$$ \begin{aligned} L^{R}(X)&=\{x|\forall y, xRy\Rightarrow y\in X\}=\{x|RN(x)\subseteq X\},\\ H^{R}(X)&=\{x|\exists y\in X, s.t. xRy\}=\{x|RN(x)\bigcap X\neq \emptyset\},\\ \end{aligned} $$

where x ∈ U, and \(RN(x)=\{y\in U|xRy\}.\,L^{R}, H^{R}\) are called the relation lower, upper approximation operators of R, respectively. we omit the superscript R when there is no confusion.

Because of the duality, only the properties of the relation upper approximation operator are presented. These properties are essential to the connection between generalized rough sets based on relations and matroids.

Proposition 1

[10] Let R be a relation on U. The following properties about the relation upper approximation operator H hold:

  1. (1)

    \(H(\emptyset)=\emptyset; \)

  2. (2)

    For all \(X, Y\subseteq U, \) if \(X\subseteq Y, \) then \(H(X)\subseteq H(Y); \)

  3. (3)

    For all \(X, Y\subseteq U, H(X\bigcup Y)=H(X)\bigcup H(Y). \)

The matroid has many applications in various fields, such as combinatorial optimization and integer programming, partly because of its definition by a number of axiom systems. The following definition of matroids is widely used.

Definition 6

(Matroid [25]) A matroid is a pair \((E, \mathbf{I})\) where E is a finite set, and \(\mathbf{I}\) a family of subsets of E satisfying the following three conditions:

  1. (1)

    \(\emptyset\in \mathbf{I}; \)

  2. (2)

    If \(A\in \mathbf{I}, \) and \(B\subseteq A, \) then \(B\in\mathbf{I}; \)

  3. (3)

    If \(A, B\in \mathbf{I}, \) and |A| < |B|, then there exists c ∈ B − A such that \(A\bigcup\{c\}\in\mathbf{I}, \) where |X| denotes the cardinality of X.

The rank function of a matroid plays a vital role in matroid theory to serve as a quantitative tool. It inspires us to define the upper approximation number to establish the matroidal structure of generalized rough sets based on relations.

Definition 7

(Rank function [25]) Let \(M=(E, \mathbf{I})\) be a matroid. The rank function \(r_{M}\) of M is defined as follows, \(r_{M}(X)=max\{|A|: A\subseteq X, \) and \(A\in\mathbf{I}\}\) for all \(X\subseteq E. \) When there is no confusion, we omit the subscript M.

The connection between a matroid and its rank function is introduced. In fact, one can define a matroid from the perspective of the rank function.

Proposition 2

[25] Let \(M=(E, \mathbf{I})\) be a matroid and r its rank function. For all \(X\subseteq E, r(X)=|X|\) if and only if \(X\in \mathbf{I}. \)

The closure operator of a matroid is defined with the rank function. However, the closure operator can also determine a matroid. In this paper, we use it to characterize generalized rough sets based on relations.

Definition 8

(Closure operator) [25] Let \(M=(E, \mathbf{I})\) be a matroid. The closure operator \(cl_{M}\) of M is defined as \(cl_{M}(X)=\{e\in E|r(X)=r(X\bigcup\{e\})\}\) for all \(X\subseteq E.\) \(cl_{M}(X)\) is called the closure of X in M. When there is no confusion, we omit the subscript M.

In the following proposition, four properties of the closure operator are listed to construct the closure axioms of matroids.

Proposition 3

[25] Let \(M=(E, \mathbf{I})\) be a matroid and cl its closure operator. The following properties about closure operator cl hold:

  1. (1)

    For all \(X\subseteq E, X\subseteq cl(X); \)

  2. (2)

    If \(X\subseteq Y\subseteq E, \) then \(cl(X)\subseteq cl(Y); \)

  3. (3)

    For all \(X\subseteq E, cl(cl(X))=cl(X); \)

  4. (4)

    For all x, y ∈ E, if \(y\in cl(X\bigcup\{x\})-cl(X), \) then \(x\in cl(X\bigcup\{y\}).\)

The following closure axioms show that a closure operator determines a matroid. In other words, matroids can be defined equivalently with the closure operator.

Proposition 4

(Closure axioms) [25] Let E be a finite set. An operator \(cl: 2^{E}\longrightarrow 2^{E}\) is the closure operator of a matroid if and only if it satisfies the properties (1), (2), (3), (4) of Proposition 3.

3 The matroid induced by a relation through the upper approximation number

Inspired by the rank function of a matroid, we define the upper approximation number to induce a matroid from a relation. Its definition borrows ideas from the the relation upper approximation operator and the rank function of the matroid.

Definition 9

(Upper approximation number) Let R be a relation on U, and \(RN(x_{1}), \ldots, RN(x_{m})\) be all different neighborhoods of in R, where \(x_{1}, \ldots, x_{m}\in U. \) For all \(X\subseteq U, \) we can define \(f_{R}(X)=|\{x_{i}\in \{x_{1},\ldots, x_{m}\}: RN(x_{i})\bigcap X\neq\emptyset\}|. f_{R}(X)\) is called the upper approximation number of \(X,\,f_{R}\) the upper approximation number function with respect to R. We omit the subscript R when there is no confusion.

In fact, In Definition 9, the set of all neighborhoods in a relation is regarded as a family of some subsets of the universe; in other words, \(\{RN(x)|x\in U\}=\{RN(x_{1}), \ldots, RN(x_{m})\}. \) Similarly, the lower approximation number can also be defined. So this paper omits the discussion.

Example 1.

Let U = {a, b, c, d}, and R = {(a, a), (a, c), (b, a), (b, c), (b, d), (c, a), (c, b), (d, a)}. Then RN(a) = {a, c}, RN(b) = {a, c, d}, RN(c) = {a, b}, and RN(d) = {a}. {RN(x)|x ∈ U} = {RN(a), RN(b), RN(c), RN(d)}. Suppose X = {a}, Y = {b, c}, then f(X) = |{a, b, c, d}| = 4 since \(X\bigcap RN(a)\neq\emptyset, X\bigcap RN(b) \neq\emptyset, X\bigcap RN(c)\neq\emptyset, \) and \(X\bigcap RN(d)\neq\emptyset.\) Similarly, f(Y) = |{a, b, c}| = 3.

Example 2.

Let U = {a, b, c, d}, and R = {(a, a), (a, c), (b, a), (b, c), (b, d), (c, a), (c, b), (d, a), (d, b)}. Then RN(a) = {a, c}, RN(b) = {a, c, d}, RN(c) = {a, b}, and RN(d) = {a, b}. {RN(x)|x ∈ U} = {RN(a), RN(b), RN(c)} = {RN(a), RN(b), RN(d)}. Suppose X = {a}, Y = {a, c}, Z = {c}. Then f(X) = |{a, b, c}| = 3 since \(RN(a)\bigcap X\neq\emptyset, RN(b)\bigcap X\neq\emptyset, \) and \(RN(c)\bigcap X\neq\emptyset. \) It is the same as f(X) = |{a, b, d}| = 3 since \(RN(a)\bigcap X\neq\emptyset, RN(b)\bigcap X\neq\emptyset, \) and \(RN(d)\bigcap X\neq\emptyset. \) Similarly, f(Y) = |{a, b, c}| = 3, and f(Z) = |{a,b}| = 2.

Some properties are listed to illustrate the upper approximation number function. They are crucial for the establishment of the matroid through a relation.

Proposition 5

Let R be a relation on U, and \(f_{R}\) the upper approximation number function with respect to R. For all \(X, Y\subseteq U\), the following properties hold:

  1. (1)

    \(f_{R}(\emptyset)=0; \)

  2. (2)

    If \(X\subseteq Y \), then \(f_{R}(X)\leq f_{R}(Y); \)

  3. (3)

    \(f_{R}(X\bigcup Y)+f_{R}(X\bigcap Y)\leq f_{R}(X)+f_{R}(Y). \)

Proof

(1) and (2) are straightforward. (3): We need to prove \(f_{R}(X\bigcup Y)+f_{R}(X\bigcap Y)\leq f_{R}(X)+f_{R}(Y), \) i.e., \(|\{x_{i}|RN(x_{i}) \bigcap (X\bigcup Y)\neq\emptyset\}|+|\{x_{i}|RN(x_{i})\bigcap (X\bigcap Y)\neq\emptyset\}|\leq |\{x_{i}|RN(x_{i})\bigcap X\neq\emptyset\}|+|\{x_{i}|RN(x_{i})\bigcap Y\neq\emptyset\}|\). For all \(x_{k}\in \{x_{i}|RN(x_{i})\bigcap (X\bigcup Y)\neq\emptyset\}, RN(x_{k})\bigcap (X\bigcup Y)= (RN(x_{k})\bigcap X) \bigcup ((RN(x_{k})\bigcap Y)\neq\emptyset\), then \(RN(x_{k})\bigcap X\neq\emptyset\) or \(RN(x_{k})\bigcap Y \neq\emptyset. \) Thus \(x_{k}\in \{x_{i}|RN(x_{i})\bigcap X \neq\emptyset\}\) or \(x_{k}\in \{x_{i}|RN(x_{i})\bigcap Y\neq\emptyset\}. \) Similarly, if \(x_{k}\in \{x_{i}|RN(x_{i})\bigcap (X\bigcap Y)\neq\emptyset\}\), then \(RN(x_{k})\bigcap (X\bigcap Y)=(RN(x_{k})\bigcap X) \bigcap (RN(x_{k})\bigcap Y)\neq\emptyset\). Thus \(RN(x_{k})\bigcap X\neq\emptyset\) and \(RN(x_{k})\bigcap Y\neq\emptyset\). This proves \(x_{k}\in \{x_{i}|RN(x_{i})\bigcap X\neq\emptyset\}\) and \(x_{k}\in \{x_{i}|RN(x_{i})\bigcap Y\neq\emptyset\}\). To sum up, this proves \(f_{R}(X\bigcup Y)+f_{R}(X\bigcap Y)\leq f_{R}(X)+f_{R}(Y). \)

The following proposition constructs a matroid from a relation through the upper approximation number. And it lays the foundation for studying generalized rough sets based on relations in the matroidal structure.

Proposition 6

Let R be a relation on \(U, f_{R}\) the upper approximation number function with respect to R. We define

$$ \mathbf{I}(R)=\{A\subseteq U|\,for all\,B\subseteq A, f_{R}(B)\geq |B|\}.$$

Then \(M(R)=(U, \mathbf{I}(R))\) is a matroid.

Proof

\(\emptyset\in\mathbf{I}(R)\) since \(f_{R}(\emptyset)=0=|\emptyset|\). If \(A\in\mathbf{I}(R)\) and \(B\subseteq A, \) then \(f_{R}(A^{\prime})\geq|A^{\prime}|\) for all \(A^{\prime}\subseteq A\). It is straightforward that \(f_{R}(B^{\prime})\geq|B^{\prime}|\) for all \(B^{\prime}\subseteq B\subseteq A. \) Hence \(B\in\mathbf{I}(R)\). For all \(A,B\in\mathbf{I}(R)\) and |A| < |B|, if \(A\bigcup\{c\}\notin \mathbf{I}(R)\) for all c ∈ B − A, then \(|A|\leq f_{R}(A)\leq f_{R}(A\bigcup\{c\})<|A\bigcup\{c\}|\leq|A|+1\leq f_{R}(A)+1\). Hence \(f_{R}(A)=f_{R}(A\bigcup\{c\})=|A|\). For all c, d ∈ B − A and \(c\neq d, f_{R}(A\bigcup\{c,d\})+f_{R}(A)\leq f_{R}(A\bigcup\{c\})+f_{R}(A\bigcup\{d\})=2f(A)\). This is to say, \(f_{R}(A\bigcup\{c,d\})\leq f_{R}(A)\). Conversely, \(f_{R}(A)\leq f_{R}(A\bigcup\{c,d\})\). Thus \(f_{R}(A\bigcup\{c,d\})= f_{R}(A)\). Generally, \(f_{R}(B)=f_{R}(A\bigcup(\bigcup_{c\in B-A}\{c\}))=f_{R}(A) \). Thus \(|A|=f_{R}(A)=f_{R}(B)\geq |B|\), which is contradictory with |A| < |B|. Thus there exists c ∈ B−A such that \(A\bigcup\{c\}\in \mathbf{I}(R).\)

The above proposition shows that any relation generates a matroid, and we call it the matroid induced by the relation. The following proposition shows that the expression of the rank function of the matroid induced by a relation is obtained through the upper approximation number.

Proposition 7

Let R be a relation on \(U, f_{R}\) the upper approximation number function with respect to R. Let \(M(R)=(U, \mathbf{I}(R))\) be the matroid induced by R, and \(r_{M(R)}\) the rank function of M(R). Then \(r_{M(R)}(X)=min_{Y\subseteq X}\{f_{R}(Y)+|X-Y|\}\) for all \(X\subseteq U.\)

Proof

\(X\in\mathbf{I}(R)\Longleftrightarrow \forall Y\subseteq X, f_{R}(Y)\geq|Y|=|X|-|X-Y|\Longleftrightarrow \forall Y\subseteq X, f_{R}(Y)+|X-Y|\geq |X|\Longleftrightarrow min_{Y\subseteq X}\{f_{R}(Y)+|X-Y|\}=|X|\Longleftrightarrow r_{M(R)}(X)=min_{Y\subseteq X}\{f_{R}(Y)+|X-Y|\}. \)

As shown in the following proposition, the rank function of the matroid induced by a relation is equal to the upper approximation number function when the relation is an equivalence relation. In this sense, the upper approximation number function is a generalization of the rank function.

Proposition 8

Let R be an equivalence relation on \(U, f_{R}\) the upper approximation number function with respect to R. Let \(M(R)=(U, \mathbf{I}(R))\) be the matroid induced by R, and \(r_{M(R)}\) the rank function of M(R). Then \(r_{M(R)}(X)=f_{R}(X)\) for all \(X\subseteq U.\)

Proof

Since R is an equivalence relation on U, then\(f_{R}(Y)\leq |Y|\) for all \(Y\subseteq U. \) According to Proposition 7, \(r_{M(R)}(X)=min_{Y\subseteq X}\{f_{R}(Y)+|X-Y|\}\geq min_{Y\subseteq X}\{f_{R}(Y)+f(X-Y)\}\geq min_{Y\subseteq X}\{f_{R}(Y\bigcup (X-Y))+f_{R}(Y\bigcap (X-Y))\}=f_{R}(X). \) Conversely, \(r_{M(R)}(X)=min_{Y\subseteq X}\{f_{R}(Y)+|X-Y|\}\leq f_{R}(X)+|X-X|=f_{R}(X). \). Thus \(r_{M(R)}(X)=f_{R}(X)\) for all \(X\subseteq U. \)

4 Matroid approximation operators of generalized rough sets based on relations

Through the matroid induced by a relation, systematic investigations on generalized rough sets based on relations are made in the matroidal structure. Specifically, we construct a pair of approximation operators with the rank function of the matroid induced by a relation and study their properties.

Definition 10

Let R be a relation on U, M(R) the matroid induced by R. For all \(X\subseteq U \), we can define \(\overline{M}(X)=\{y\in U|r_{M(R)}(X\bigcup\{y\})=r_{M(R)}(X)\}, \underline {M}(X)=(\overline{M}(X^{c}))^{c}, \)

where \(r_{M(R)}\) is the rank function of M(R), and \(X^{c}\) is the complement of X in U. We call \(\overline{M}(X), \underline{M}(X)\) the matroid upper, lower approximations of X, respectively.

Because of the duality, we study only the matroid upper approximation operator. The following proposition lists some properties to reflect the characteristics of the matroid upper approximations.

Proposition 9

Let R be a relation on U. For all \(X, Y\subseteq U\), the following properties on the matroid upper approximations hold:

  1. (1)

    \(\overline{M}(\emptyset)=\emptyset, \overline{M}(U)=U; \)

  2. (2)

    \(X\subseteq \overline{M}(X); \)

  3. (3)

    If \(X\subseteq Y\subseteq U\), then \(\overline{M}(X)\subseteq \overline{Y}; \)

  4. (4)

    \(\overline{M}(\overline{M}(X))=\overline{M}(X); \)

  5. (5)

    For all y, z ∈ U, if \(z\in\overline{M}(X\bigcup\{y\})-\overline{M}(X)\), then \(y\in\overline{M}(X\bigcup\{z\}). \)

The above proposition shows that the matroid upper approximations present some new characteristics, which does not exist in the relation upper approximations, such as the (5) of Proposition 9.

5 Relationship between matroid upper approximations and relation upper approximations

The following propositions show the connection between two upper approximation operators. When the relation is reflective, the matroid upper approximations are smaller than the relation upper approximations.

Proposition 10

Let R be a relation on U. If R is reflective, then \(\overline{M}(X)\subseteq H(X)\) for all \(X\subseteq U. \)

Proof

For all \(y\notin H(X)\), we need to prove \(y\notin\overline{M}(X), \) i.e., \(r_{M(R)}(X)\neq r_{M(R)}(X\bigcup\{y\}). r_{M(R)}(X\bigcup \{y\})=min_{Y\subseteq X\bigcup\{y\}}\{f_{R}(Y)+|X\bigcup \{y\}-Y|\}=min\{min\{f_{R}(Y)+|X\bigcup\{y\}-Y|: Y\subseteq X\bigcup \{y\}, y\in Y\},min\{f_{R}(Y)+|X\bigcup \{y\}-Y|: Y\subseteq X\bigcup \{y\}, y\notin Y\}\} =min\{min\{f_{R}(Y)+|X\bigcup \{y\}-Y|: Y-\{y\}\subseteq X,y\in Y\}, min\{f_{R}(Y)+|X-Y|+1: Y\subseteq X, y\notin Y\}\}=min\{min\{f_{R}(Y^{\prime}\bigcup \{y\})+|X-Y^{\prime}|:Y^{\prime}\subseteq X, y\in Y\}, min\{f_{R}(Y)+|X-Y|+1: Y\subseteq X, y\notin Y\}\}\geq min_{Y\subseteq X}\{f_{R}(Y)+|Y-X|+1\}=r_{M(R)}(X)+1\), since \(f_{R}(Y^{\prime}\bigcup\{y\})\geq f_{R}(Y^{\prime})+1\) for all \(Y^{\prime}\subseteq X\). In fact, \(y\notin H(X)\) implies \(RN(y)\bigcap X =\emptyset\), where \(RN(y)=\{z\in U|yRz\}\). Since R is reflective, then y ∈ RN(y). Denote \(\{RN(x)\}_{x\in U}=\{RN(x_{1}), \ldots, RN(x_{m})\},\) where \(\{x_{1}, \ldots, x_{m}\}\subseteq U\). If \(y\in\{x_{1}, \ldots, x_{m}\} \), then \(Y^{\prime}\bigcap RN(y)=\emptyset\) and \((Y^{\prime}\bigcup \{y\})\bigcap RN(y)\neq \emptyset. \) Thus \(f_{R}(Y^{\prime}\bigcup \{y\})\geq f_{R}(Y^{\prime})+1. \) If \(y\notin\{x_{1}, \ldots, x_{m}\}, \) then there exists \(x_{i}\in\{x_{1}, \ldots, x_{m}\}\) such that \(RN(y)=RN(x_{i}). \) Similarly, \(Y^{\prime}\bigcap RN(x_{i})=\emptyset\) and \((Y^{\prime}\bigcup \{y\})\bigcap RN(x_{i})\neq \emptyset, \) which imply \(f_{R}(Y^{\prime}\bigcup \{y\})\geq f_{R}(Y^{\prime})+1\). Thus \(r_{M(R)}(X\bigcup \{y\})\geq r_{M(R)}(X)+1, \) which implies \(r_{M(R)}(X)\neq r_{M(R)}(X\bigcup \{y\}). \) This completes the proof.

When a relation is an equivalence relation, the matroid upper approximations are equal to the relation upper approximations. In this sense, the matroid upper approximations are a generalization of the upper approximations in rough sets.

Proposition 11

If R is an equivalence relation on U, then \(\overline{M}(X)=H(X)\) for all \(X\subseteq U. \)

Proof

According to Proposition 10, \(\overline{M}(X)\subseteq H(X)\) for all \(X\subseteq U\). Conversely, for all y ∈ H(X), we need to prove \(y\in\overline{M}(X)\), i.e., \(r_{M(R)}(X)=r_{M(R)}(X\bigcup\{y\}).\) According to Proposition 8, we need to prove \(f_{R}(X)=f_{R}(X\bigcup\{y\})\). In fact, since y ∈ H(X), then \(RN(y)\bigcap X\neq\emptyset, \) where RN(y) = {z ∈ U|yRz}. Since R is an equivalence relation on U, then \(f_{R}(X)=f_{R}(X\bigcup\{y\}). \) This completes the proof.

The matroid lower approximation operator has a similar relationship with the relation lower approximation operator. Therefore, we omit the discussion between them.

6 Matroidal approaches to characterize generalized rough sets based on relations

In this section, the closure operator of a matroid is used to characterize generalized rough sets based on relations. We describe the symmetric relation with a property of the closure operator, and the relation upper approximations with the closure.

Proposition 12

Let R be a relation on U. R is symmetric if and only if for all \(X\subseteq U, \) and \(y\in H(X\bigcup\{x\})-H(X), x\in H(X\bigcup\{y\}). \)

Proof

(\(\Longrightarrow\)): For all \(y\in H(X\bigcup\{x\})-H(X), \) \(RN(y)\bigcap (X\bigcup\{x\})\neq\emptyset\) and \(RN(y) \bigcap X=\emptyset\). So \(RN(y)\bigcap\{x\}\neq\emptyset\); in other words, x ∈ RN(y). Because R is symmetric, y ∈ RN(x). So \(y\in RN(x)\bigcap\{y\}\subseteq RN(x)\bigcap(X\bigcup\{y\})\). Thus \(RN(x)\bigcap(X\bigcup\{y\})\neq\emptyset \). So \(x\in H(X\bigcup\{y\})\). \(\Longleftarrow\): For all x, y ∈ U, if x ∈ RN(y), then \(RN(y)\bigcap\{x\}\neq\emptyset; \) in other words, \(y\in H(\{x\})=H(\{x\}\bigcup\emptyset)-H(\emptyset). \) So \(x\in H(\{y\}\bigcup\emptyset)=H(\{y\}). \) Thus \(RN(x)\bigcap\{y\}\neq\emptyset; \) in another word, y ∈ RN(x). This proves R is symmetric.

A type of relation is explored when the relation upper approximation operator is equal to the closure operator of the matroid induced by the relation.

Proposition 13

Let R be a relation on U. R is an equivalence relation if and only if the relation upper approximation operator H of R is equal to the closure operator of the matroid induced by the relation.

Proof

According to literature [10], R is reflective if and only if \(X\subseteq H(X), \) and R is transitive if and only if \(H(H(X))\subseteq H(X)\) for all \(X\subseteq U. \) According to Proposition 12, R is symmetric if and only if for all \(X\subseteq U, \) and \(y\in H(X\bigcup\{x\})-H(X), x\in H(X\bigcup\{y\}). \) Then according to Proposition 3, this completes the proof.

7 The relation induced by a matroid

In the above part, we have discussed how a relation induces a matroid. In this section, how a matroid induces a relation is presented.

Definition 11

Let \(M=(U, \mathbf{I})\) be a matroid. We define the relation R(M) on U as follows:

$$ xR(M)y \Longleftrightarrow y\in cl(\{x\}). $$

R(M) is called the relation induced by M.

According to Definition 11, any matroid induces a relation. An example and some properties are used to illustrate the relation.

Example 3.

Let \(M=(U, \mathbf{I})\) be a matroid, where \(U=\{1,2,3,4\}, \mathbf{I}=\{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}\}. \) Since cl({1}) = {1, 4}, cl({2}) = cl({3}) = {2, 3, 4}, cl({4}) = {4}, then R(M) = {(1, 1), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 4)}.

The following work is to explore the characteristics of the relation induced by a matroid. In fact, the relation is reflective and symmetric.

Proposition 14

Let \(M=(U, \mathbf{I})\) be a matroid, and R(M) the relation induced by M. Then R(M) is reflective and symmetric.

Proof

\(x\in U, \{x\}\subseteq cl(\{x\}), \) i.e., \(x\in cl(\{x\}). \) Hence xR(M)x; in other words, R(M) reflective.

For all \(xR(M)y, y\in cl(\{x\})=cl(\emptyset\bigcup\{x\})-cl(\emptyset), \) then \(x\in cl(\emptyset\bigcup\{y\})=cl(\{y\}). \) Thus yR(M)x. This proves R(M) is symmetric.

The relationship between the closure of a matroid and the relation upper approximation of a set having only one element of the relation induced by the matroid is studied.

Lemma 1.

Let \(M=(U, \mathbf{I})\) be a matroid, and R(M) the relation induced by M. Then \(H^{R(M)}(\{x\})=cl(\{x\})\) for all \(x\in U. \)

Proof

For all \(y\in H^{R(M)}(\{x\})=\{y\in U| RN(y)\bigcap \{x\}\neq\emptyset\}, \) where \(RN(y)=\{z\in U|xR(M)z\}. \) Thus \(x\in RN(y), \) i.e., yR(M)x. Then xR(M)y since R(M) is symmetric. Thus \(y\in cl(\{x\}). \) This proves \(H^{R(M)}(\{x\})\subseteq cl(\{x\}). \) Conversely, for all \(y\in cl(\{x\}), \) then xR(M)y. Then yR(M)x since R(M) is symmetric. Thus \(RN(\{y\})\bigcap\{x\}\neq\emptyset; \) in other words, \(y\in H^{R(M)}(\{x\}). \) This proves \(cl(\{x\})\subseteq H^{R(M)}(\{x\}). \) To sum up, this proves \(H^{R(M)}(\{x\})=cl(\{x\})\) for all \(x\in U. \)

Based on Lemma 1, we establish the relationship between the closure and the relation upper approximation of any set of the relation induced by the matroid.

Proposition 15

Let \(M=(U, \mathbf{I})\) be a matroid, and R(M) the relation induced by M. Then \(H^{R(M)}(X)\subseteq cl(X)\) for all \(X\subseteq U. \)

Proof

For all \(X\subseteq U, H^{R(M)}(X)=H^{R(M)}(\bigcup _{x\in X}\{x\})=\bigcup_{x\in X}H^{R(M)}(\{x\})=\bigcup_{x\in X}cl(\{x\})\subseteq cl(X). \)

The following proposition reflects the relationship between two inductions. In fact, they are inverse when a relation is an equivalence relation.

Proposition 16

Let R be a relation on \(U, M(R)=(U, \mathbf{I}(R))\) the matroid induced by R, and R(M(R)) the relation induced by M(R). If R is an equivalence relation on U, then R(M(R)) = R.

Proof

Since R is an equivalence relation, then for all \((x, y)\in R, RN(x)=RN(y), \) where \(RN(x)=\{z\in U|xRz\}. \) \(r_{M(R)}(\{x, y\})=f_{R}(\{x, y\})=1=r_{M(R)}(\{x\})\) since \(\bigcup_{x\in U}RN(x)=U\) such that \(f_{R}(X)\leq |X|\) for all \(X\subseteq U. \) Thus \(y\in cl_{M(R)}(\{x\}); \) in other words, xR(M(R))y, i.e., \((x, y)\in R(M(R)). \) This proves \(R(M(R))\subseteq R. \) Conversely, for all \((x, y)\in R(M(R)), \) then \(y\in cl_{M(R)}(\{x\}). \) Then \(f_{R}(\{x, y\})=r_{M(R)}(\{x, y\})=r_{M(R)}(\{x\})=f_{R}(\{x\}). \) Thus RN(x) = RN(y); in other words, \((x, y)\in R. \) Hence \(R(M(R))\subseteq R. \) To sum up, this completes the proof.

The equality in Proposition 16 does not hold generally; in other words, a relation is not obtained through the matroid induced by the relation.

Example 4.

Let U = {1, 2, 3, 4}, and R = {(1, 1), (2, 2), (2, 3)}. Then the matroid induced by R is \(M(R)=(U, \mathbf{I}(R)), \) where \(\mathbf{I}(R)=\{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}\}. \) Thus the relation induced by M(R) is R(M(R)) = {(1, 1), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 4)}. It is straightforward \(R(M(R))\nsubseteq R. \)

Example 5.

Let U = {a, b}, and R = {(a, b), (b, a)}. Then R(M(R)) = {(a, a), (b, b)}. Thus \(R\nsubseteq R(M(R)). \)

8 Conclusions

This paper establishes a bridge between generalized rough sets based on relations and matroids. On the one hand, the upper approximation number is defined to induce the matroid from a relation. Then we use matroidal approaches to study generalized rough sets based on relations. On the other hand, the relation is induced by a matroid. Two inductions are inverse when a relation is an equivalence relation. In a word, this paper provides a new perspective, that is, the matroidal perspective, to study rough sets.