Matroidal Structure of Rough Sets from the Viewpoint of Graph Theory

Definition 2.1 (Neighborhood [36]). Let R be a relation on U. For all x ∈ U, RN_R(x) = {y ∈ U : xRy} is called the successor neighborhood of x in R. When there is no confusion, we omit the subscript R.

Definition 2.2 (Upper approximation number [32]). Let R be a relation on U. For all X⊆U, $$ is called the upper approximation number of X with respect to R.

Definition 2.3 (Matroid [39]). A matroid M is a pair (E, ℐ), where E (called the ground set) is a finite set and ℐ (called the independent sets) is a family of subsets of E satisfying the following axioms:

•  

  I1 ∅ ∈ ℐ;

•  

  I2 if I ∈ ℐ and I^′⊆I, then I^′ ∈ ℐ;

•  

  I3 if I₁, I₂ ∈ ℐ and |I₁ | <|I₂|, then ∃e ∈ I₂ − I₁ such that I₁ ∪ {e} ∈ ℐ,

Example 2.4. Let E = {a, b, c}, ℐ = {{a, b}, {b, c}, {a}, {b}, {c}, ∅}. Then (E, ℐ) is a matroid, which satisfies the axioms (I1)~(I3). And each element of ℐ is an independent set. {a, b, c} and {a, c} are only two dependent sets of (E, ℐ).

Definition 2.5 (Circuit [39]). Let M be a matroid. A minimal dependent set is called a circuit of M, and the set of all circuits of M is denoted by 𝒞(M), that is, 𝒞(M) = Min (Opp(ℐ)).

Theorem 2.6 (Circuit axioms [39]). Let 𝒞 be a family of subsets of E. Then there exists M(E, ℐ) such that 𝒞 = 𝒞(M) if and if only 𝒞 satisfies the following properties:

•  

  C1 ∅ ∉ 𝒞;

•  

  C2 if C₁, C₂ ∈ 𝒞 and C₁⊆C₂, then C₁ = C₂;

•  

  C3 if C₁, C₂ ∈ 𝒞, C₁ ≠ C₂, and ∃e ∈ C₁∩C₂, then ∃C₃ ∈ 𝒞 such that C₃⊆(C₁ ∪ C₂)−{e}.

Definition 2.7 (Base [39]). Let M be a matroid. A maximal independent set of M is called a base of M; the set of all bases of M is denoted by ℬ(M), that is, ℬ(M) = Max (ℐ).

Definition 2.8 (Rank function [39]). Let M = M(E, ℐ) be a matroid. Then the rank function r_M of M is defined as: for all X⊆E,

Definition 2.9 (Closure [39]). Let M = M(E, ℐ) be a matroid. For all X⊆E, the closure operator cl _M of M is defined as follows:

Definition 2.10 (Hyperplane [39]). Let M = (E, ℐ) be a matroid. H⊆E is called a hyperplane of M if H is a closed set of M and r_M(H) = r_M(E) − 1. And ℋ(M) represents the family of all hyperplanes of M.

Definition 3.1 (Complete graph [38]). A complete graph is a simple undirected graph whose vertices are pairwise adjacent. A complete graph whose cardinality of vertex set is equal to n is denoted by K_n.

In rough sets, an equivalence relation can generally be regarded as an indiscernibility relation. That means any two different elements in the same equivalence class are indiscernible. In order to interpret this phenomenon from the viewpoint of graph theory, we can consider the two elements as two vertices and the indiscernibility relation between them as an edge connecting the two vertices. Then an equivalence class is represented by a complete graph. For a better understanding of it, an example is served as follows.

Example 3.2. Let U = {a, b, c, d, e, f, g, h} be the universe, R an equivalence relation, and U/R = {T₁, T₂, T₃} = {{a},  {b, c},  {d, e, f, g, h}}. Then each equivalence class can be transformed to a complete graph showed in Figure 1.

Example 3.3 (Continued from Example 3.2). For any equivalence class in U/R, it can be represented by a cycle. As shown in Figure 2, the equivalence class T₁, T₂, and T₃ are represented by Figures 2(a), 2(b), and 2(c), respectively.

Proposition 4.1. Let ℐ_P = {X⊆U : G_P[X] is an empty graph}. Then there is a matroid M on U such that ℐ(M) = ℐ_P.

Proof. According to Definition 2.3, we just need to prove that ℐ_P satisfies axioms (I1)~(I3). It is obvious that (I1) and (I2) hold. Suppose that X, Y ∈ ℐ_P and |X | <|Y|. Because G_P[X] and G_P[Y] are empty graphs, according to the definition of E_P, each x ∈ X belongs to a different equivalence class with the others of X and the same to each y ∈ Y. Since |X | <|Y|, thus there must be at least one element y₀ ∈ Y such that y₀ belongs to some equivalence class which does not include any element of X. Therefore, X ∪ {y₀} ∈ ℐ_P. As a result, ℐ_P satisfies (I3). That is, there exists a matroid M on U such that ℐ(M) = ℐ_P.

Definition 4.2 (The first type of matroid induced by a partition). The first type of matroid induced by a partition P over U, denoted by I-MIP, is such a matroid whose ground set E = U and independent sets ℐ = {X⊆U : G_P[X] is an empty graph}.

Proposition 4.3. Let M_P = (U, ℐ_P) be an I-MIP. Then for all X⊆U, X ∈ ℐ_P if and only if for all   T ∈ P such that |X∩T | ≤ 1.

Proof. (⇒): If X ∈ ℐ_P, then G_P[X] is an empty graph. According to the definition of E_P, each element of X comes from a different equivalence class with the others of X. That is, for all T ∈ P, |X∩T | ≤ 1.

(⇐): Let X⊆U. If for all T ∈ P, |X∩T | ≤ 1, then G_P[X] is an empty graph. Therefore, X ∈ ℐ_P.

Theorem 4.4. Let M be a matroid induced by P. Then M is an I-MIP if and only if for all C ∈ 𝒞(M), |C | = 2.

Proof. According to Definition 2.3, we know that ℐ(M)⊆2^U. If ℐ(M) = 2^U, then M is a I-MIP induced by P = {{x} : x ∈ U}. In this case, according to (2.2), 𝒟(M) = ∅ and 𝒞(M) = ∅. It indicates that there is not any circuit in 𝒞(M), and, therefore, we do not need to care whether the cardinality of each circuit of 𝒞(M) is equal to 2. That is, 𝒞(M) = ∅ is compatible with the description that for all C ∈ 𝒞(M), |C | = 2. Similarly, if 𝒞(M) = ∅, then M is a I-MIP induced by P = {{x} : x ∈ U}. So, Theorem 4.4 is true when the set of circuits of M is empty.

Next, we prove that Theorem 4.4 is true when the set of circuits of M is nonempty.

(⇒): According to (2.2), 𝒟(M) = 2^U − ℐ_P. Therefore, in terms of Definition 4.2 and Proposition 4.1, for all X⊆U, X ∈ 𝒟(M) if and only if G_P[X] is not an empty graph. That is, there is at least one edge in G_P[X]. Obviously, the set of endpoints of each edge of G_P[X] is a dependent set. So, for all X ∈ 𝒟(M), there is a set Y composed of the endpoints of some edge of G_P[X] such that Y⊆X. According to Definition 2.5, Y ∈ 𝒞(M) and X ∉ 𝒞(M). That is, for all C ∈ 𝒞(M), |C | = 2.

(⇐): 𝒟(M) = {X⊆U : ∃C ∈ 𝒞(M)   s.t.  C⊆X}. According to (2.2), ℐ(M) = 2^U − 𝒟(M). Therefore, for all I ∈ ℐ(M), ∄C ∈ 𝒞(M) such that C⊆I, that is, for all C ∈ 𝒞(M), |C  ∩    I | ≤ 1. So, for all C₁, C₂ ∈ 𝒞(M); if I ∩  C₁ ≠ ∅, then I ∩  C₂ = C₁   ∩   C₂. According to Theorem 2.6, if C₁ ∩ C₂ ≠ ∅, then ∃C₃ ∈ 𝒞(M) such that C₃ = C₁  ∪  C₂   −  C₁∩C₂. For all C_i ∈ 𝒞(M), let $$. Then $$. Furthermore, if C₁  ∩  C₂ = ∅, then $$. If for all C ∈ 𝒞(M), I ∩ C = ∅, then for all y ∈ I, ∄C ∈ 𝒞(M) such that y ∈ C. Thus, $$ is a partition over U. So ℐ(M) = {I⊆U : for  all  X ∈ P_𝒞(M),    | I  ∩  X | ≤ 1}. According to Definition 4.2, M = (U, ℐ) is a I-MIP.

Summing up, Theorem 4.4 is true.

Theorem 4.5. Let 𝒫 be the collection of all partitions over U, ℳ the set of all I-MIP induced by partitions of 𝒫, f : 𝒫 → ℳ, that is, for all P ∈ 𝒫, f(P) = M_P, where M_P is the I-MIP induced by P. Then f satisfies the following conditions:

• (1)

  for all P₁, P₂ ∈ 𝒫, and if P₁ ≠ P₂ then f(P₁) ≠ f(P₂),

• (2)

  for all M ∈ ℳ, ∃P_M ∈ 𝒫 s.t. f(P_M) = M.

Proof. (1) Let P₁, P₂ ∈ 𝒫, P₁ ≠ P₂, and $$, $$ are two I-MIP induced by P₁ and P₂, respectively. We need to prove that there is an $$ such that $$, or there is an $$ such that $$. Because P₁ ≠ P₂, there is at least one equivalence class T₁ ∈ P₁ such that T₁ ∉ P₂. If ∃T₂ ∈ P₂ such that T₁ ⊂ T₂, then ∃X⊆U and $$ such that X∩(T₂ − T₁) ≠ ∅. That means $$. Else, there at least two equivalence classes T_2i, T_2j ∈ P₂ such that T_2i∩T₁ ≠ ∅ and T_2j∩T₁ ≠ ∅. That is, there is a set $$ such that Y∩T_2i∩T₁ ≠ ∅ and Y∩T_2j∩T₁ ≠ ∅. Obviously, according to Proposition 4.3, $$.

(2) Let M = (U, ℐ) be a I-MIP, for all x ∈ U, C_x = {x}∪(∪{C ∈ 𝒞(M) : C∩{x} ≠ ∅}). According to Theorem 4.4, for all y ∈ U and y ∉ C_x, then C_x∩C_y = ∅. Therefore, we can get a family C_U = {C_x : x ∈ U}. It is obvious that ∪C_U = U. Therefore, C_U is a partition of U. That is, C_U ∈ 𝒫 and f(C_U) = M.

Proposition 4.6. Let M_P be the I-MIP induced by P, Y⊆U, and G_P[Y] = (Y, E_Y) a subgraph of G_P. Then ℬ_P = {X⊆U:|X | = |P | ∧E_X = ∅} is the set of bases of M_P.

Proof. According to Definition 2.7, we need to prove that ℬ(M_P) = ℬ_P, namely, Max (ℐ_P) = {X⊆U:|X | = |P | ∧E_X = ∅}. In terms of Proposition 4.3, for all I ∈ ℐ_P, |I∩T | ≤ 1 for all T ∈ P. So, for all I ∈ ℬ(M_P), |I | = |P|. According to Proposition 4.1 and Definition 4.2, for all I ∈ ℬ(M_P), G_P[I] is an empty graph, that is, I ∈ ℬ_P. Similarly, we can prove in the same way that for all X ∈ ℬ_P, X ∈ ℬ(M_P). That is, ℬ(M_P) = ℬ_P.

Corollary 4.7. Let X⊆U. Then X ∈ ℬ_P if and only if for all  T ∈ P, |X∩T | = 1.

Proof.  According to Proposition 4.6, it is straightforward.

Corollary 4.8. ∪ℬ_P = U.

Proof. According to Proposition 4.6, it is straightforward.

Proposition 4.9. Let M_P = (U, ℐ_P) be the I-MIP induced by P. Then 𝒞_P = {{x, y} : xy ∈ E_P} is the set of circuits of M_P.

Proof. According to Definition 2.5, we need to prove 𝒞(M_P) = 𝒞_P, that is, Min (Opp(ℐ_P)) = {{x, y} : xy ∈ E_P}. 𝒟(M) = Opp(ℐ_P), for all I ∈ 𝒟(M), ∃x, y ∈ I such that xy ∈ E(G_P[I]). Furthermore, xy ∈ E_P. If {x, y} ⊂ I, then {x, y} ∈ 𝒞(M_P) and I ∉ 𝒞(M_P); else, {x, y} = I ∈ 𝒞(M_P). So, for all I ∈ 𝒞(M_P), I ∈ 𝒞_P. Similarly, for all {x, y} ∈ 𝒞_P, ∃I ∈ 𝒟(M_P) such that {x, y}⊆I. Therefore, {x, y} ∈ 𝒞(M_P). As a result, 𝒞_P = {{x, y} : xy ∈ E_P}.

Proposition 4.10. Let M_P be the I-MIP induced by P. Then 𝒞₊ = {X⊆U : ∃T ∈ P   s.t.  X⊆T∧|X| = 2} is the set of circuits of M_P.

Proof. According to Proposition 4.3, for all X ∈ 𝒞₊, X is a dependent set, that is, X ∈ 𝒟(M_P). In terms of Proposition 4.9, X ∈ 𝒞(M_P). Similarly, for all I ∈ 𝒞(M_P), according to Proposition 4.9, I ∈ 𝒞₊. That is, 𝒞₊ is the set of circuits of M_P.

Corollary 4.11. 𝒞_P = 𝒞₊.

Proposition 4.12. Let M_P be the I-MIP induced by P. Then for all x ∈ U,

Proof. According to Proposition 4.10, for all T ∈ P, if x ∈ T then {x, y} ∈ 𝒞(M_P) for each y ∈ T − {x}. And for any y ∈ U and y ∉ T, {x, y} ∉ 𝒞(M_P). Therefore, T = [x] _R = {x}∪{y ∈ U : {x, y} ∈ 𝒞(M_P)}.

Proposition 4.13. Let M_P be the I-MIP induced by P. Then for all X⊆U, r_P(X) = max {|Y| : Y⊆X, G_P[Y]  is  an  empty  graph} is the rank of X in M_P.

Proposition 4.14. Let M_P be the I-MIP induced by P. Then for all X⊆U, cl _P(X) = X ∪ {y ∈ U − X : x ∈ X∧xy ∈ E_P} is the closure of X in M_P.

Proof. According to Definition 2.9, we need to prove that $$, that is, $$. It is obvious that, for all X⊆U, X⊆cl _P(X). So, we just need to prove that for all y ∈ U − X if there is an element x ∈ X such that xy ∈ E_P if and if only $$. According to (3.1), xy ∈ E_P if and if only x and y belong to the same equivalence. According to Definition 2.8, for all X⊆U, $$ is equal to the number of the maximal independent set contained in X. According to Proposition 4.3, for all X^′⊆X; if X^′ is a maximal independent set contained in X, then X^′   ∪   {y} is not an independent set. That is, $$. Thus, for all x ∈ U, x ∈ cl _P(X) if and if only $$.

Corollary 4.15. Let x ∈ U. For all T ∈ P; if x ∈ T then cl _P({x}) = cl _P(T).

Proposition 4.16. Let M_P be the I-MIP induced by P. Then ℋ_P = {U   −   T : T ∈ P} is the hyperplane of M_P.

Proof. According to (4.5) and Proposition 4.6, we know that the rank of the I-MIP induced by P is equal to |P|. Furthermore, in terms of Proposition 4.14 and Corollary 4.15, for all T ∈ P, U − T is a closed set and $$. So U − T ∈ ℋ(M_P), that is, for all X ∈ ℋ_P, X ∈ ℋ(M_P). Similarly, we can get that for all X ∈ ℋ(M_P), X ∈ ℋ_P.

Proposition 4.17. Let M_P be the I-MIP induced by P, ℬ(M_P) = ℬ_P. Then for all X⊆U,

Proof. For all B ∈ ℬ_P, B∩X is an independent set contained in X. Because B_X is a base having the maximal intersection with X, $$. Furthermore, for all y ∈ B_X − X, [y] _R∩X = ∅. Let S₁ = {[y] _R : y ∈ B_X − X} and S₂ = P − S₁. Then $$. If B_X − X⊆B, then B − (B_X − X)⊆∪S₂. According to Corollary 4.7, for all Y⊆∪S₂, if for all T ∈ (P − S₂) and |Y∩T | = 1, then Y ∪ (B_X − X) ∈ ℬ_P. And ∪{Y⊆∪S₂ : for  all  T ∈ (P − S₂), |Y∩T | = 1} = ∪S₂. Therefore, ∪S₂ = ∪{B − (B_X − X) : B ∈ ℬ_P∧(B_X − X)⊆B}. That is, $$.

Proposition 4.18. Let M_P be the I-MIP induced by P, 𝒞(M_P) = 𝒞_P. Then for all X⊆U,

Proof. According to Proposition 4.10 and Corollary 4.11, for all  C ∈ 𝒞_P,    ∃ T ∈ P such that C⊆T. |C∩X | = 1 means that each element of C does not certainly belong either to X or to ~X. And then ∪{C ∈ 𝒞_P:|C∩X | = 1} is the collection of all elements, which do not certainly belong either to X or to ~X. So BN_R(X) = ∪{C ∈ 𝒞_P:|C∩X | = 1}.

Proposition 4.19. Let M_P be the I-MIP induced by P, 𝒞(M_P) = 𝒞_P. Then for all X⊆U,

Proof. According to the definition of the boundary region and Proposition 4.18, it is straightforward.

Corollary 4.20. Let M_P be the I-MIP induced by P, 𝒞(M_P) = 𝒞_P and X⊆U. Then for all C ∈ 𝒞_P, $$ if and only if for all x ∈ X, {x} ∈ P.

Proof. (⇒): According to Proposition 4.10 and Corollary 4.11, if for all $$, then for all T ∈ P and |T | ≥ 2, T∩X = ∅. That is, for all x ∈ X, {x} ∈ P.

(⇐): It is straightforward.

Proposition 4.21. Let M_P be the I-MIP induced by P, $$. Then for all X⊆U, the following equations hold:

• (1)

  $$,

• (2)

  $$,

• (3)

  $$.

Proof. (1) According to Proposition 4.13, r_P(X) = |Y| where Y⊆X and for all T ∈ P, |Y∩T | ≤ 1. Let T ∈ P. If |Y∩T | = 0, then T∩X = ∅ and for all t ∈ T, r_P(X) = r_P(X ∪ {t}) − 1, that is, $$ and for all t ∈ T, t ∉ {x ∈ U : r_P(X) = r_P(X ∪ {x})}; else, if |Y∩T | = 1, then X∩T ≠ ∅ and for all x ∈ T, r_P(X) = r_P(X ∪ {x}), that is, $$ and for all t ∈ T, t ∈ {x ∈ U : r_P(X) = r_P(X ∪ {x})}. That is, $$.

Similarly, we can prove that (2) and (3) are true.

Proposition 4.22. Let M_P be the I-MIP induced by P, $$. Then for all X⊆U,

Proof. According to Proposition 4.14 and Corollary 4.15, we can get that cl _P(X) = ∪{T ∈ P : x ∈ X  ∧  x ∈ T}. Therefore, according to the definition of the upper approximation, it is obvious that $$.

Proposition 4.23. Let M_P be the I-MIP induced by P, ℋ(M_P) = ℋ_P. Then for all X⊆U,

Proof. According to Proposition 4.16, for all H ∈ ℋ_P, U − H ∈ P, that is, ~H ∈ P. And if X − H ≠ ∅, then X∩(~H) ≠ ∅. Therefore, in terms of (2.1), $$. Thus, $$.

Proposition 5.1. Let $$. Then there exists a matroid M^′ on U such that $$.

Proof. According to Definition 2.3, we need to prove that $$ satisfies (I1)~(I3). In terms of Section 3.2, for all T ∈ P, C_T is the cycle whose vertices set is T, that is, C_T = (T, E_T) where E_T is the set of edges of C_T. So, it is obvious that $$ satisfies (I1) and (I2). Here, we just need to prove $$ satisfies (I3).

Let $$, |I₁ | <|I₂| and I₂ − I₁ = {e₁, e₂, …, e_m}(1 ≤ m≤|U|). Suppose that for all e_i ∈ I₂ − I₁ for 1 ≤ i ≤ m, $$ such that $$, that is, $$. Because $$, $$. It is obvious that $$. So $$. Since |I₂ | = |I₂ − I₁ | +|I₂∩I₁|, we can get that |I₁ | ≥|I₂|. It is contradictory with the known conditions that |I₁ | <|I₂|. So ∃e_i ∈ I₂ − I₁ such that for all T ∈ P, T ⊈ I₁ ∪ {e_i}, namely, $$. That is $$. As a result, $$ satisfies (I1)~(I3). That is, there exists a matroid M^′ on U such that $$.

Definition 5.2 (The second type of matroid induced by a partition). The second type of matroid induced by a partition P over U, denoted by II-MIP, is such a matroid whose ground set E = U and independent sets ℐ = {X⊆U : for  all  T ∈ P,   C_T ⊈ G[X]}.

Proposition 5.3. Let $$ where n = |P|. Then $$ is a II-MIP.

Proof. Because S_i ⊂ T_i, for all $$, X∩T ⊂ T for each T ∈ P. That means for all T ∈ P, $$, that is, $$. Conversely, for all $$, since for all T ∈ P, $$, we can get that T ⊈ X, that is, T∩X ⊂ T. So $$. As a result, $$ is a II-MIP.

Corollary 5.4. $$.

Theorem 5.5. Let M = (U, ℐ) be a matroid. Then M is a II-MIP if and only if for all C₁, C₂ ∈ 𝒞(M), C₁∩C₂ = ∅ and ∪𝒞(M) = U.

Proof. (⇒): Let M = (U, ℐ) be the II-MIP induced by P. Therefore, for all T ∈ P, T ∉ ℐ, and for all X ⊂ T, X ∈ ℐ. And then for all T ∈ P, T ∈ 𝒟(M). So, according to (2.2) and Definition 2.5, 𝒞(M) = P. Thus, for all C₁, C₂ ∈ 𝒞(M), C₁∩C₂ = ∅, and ∪𝒞(M) = U.

(⇐): Since for all C₁, C₂ ∈ 𝒞(M), C₁∩C₂ = ∅, and ∪𝒞(M) = U, we can regard the 𝒞(M) as a partition over U. Furthermore, 𝒟(M) = {X⊆U : ∃C ∈ 𝒞(M)  s.t.  C⊆X}. Because ℐ = 2^U − 𝒟(M), for all X ∈ ℐ, ∄C ∈ 𝒞(M) such that C⊆X. According to Proposition 5.1 and Definition 5.2, we can get that $$. That is, M = (U, ℐ) is a II-MIP.

Theorem 5.6. Let 𝒫 be the collection of all partitions over U, ℳ^′ the set of all II-MIP induced by partitions of 𝒫, g : 𝒫 → ℳ^′, that is, for all P ∈ 𝒫, $$ where $$ is the II-MIP induced by P. Then g satisfy the following conditions:

• (1)

  for all P₁, P₂ ∈ 𝒫, if P₁ ≠ P₂ then g(P₁) ≠ g(P₂),

• (2)

  for all $$  s.t. $$.

Proof. (1) Let P₁ and P₂ are two different partitions over U, and $$, $$ are two II-MIP induced by P₁ and P₂, respectively. We need to prove that there is an $$ such that $$, or there is an $$ such that $$. Because P₁ ≠ P₂, there must be an equivalence class T₁ ∈ P₁ such that T₁ ∉ P₂. Suppose that for all T ∈ P₂, T₁  ⊈  T. Then ∃X ⊂ T₁ such that X ∈ {S : S ⊂ T₁} and X ∉ {S : S ⊂ T,   for  all  T ∈ P₂}. According to Proposition 5.3, $$ and $$. Conversely, if ∃T₂ ∈ P₂ such that T₁⊆T₂, then ∃X ⊂ T₂ such that X ∈ {S : S ⊂ T₂} and X ∉ {S : S ⊂ T,   for  all  T ∈ P₁}. Thus, according to Proposition 5.3, $$ and $$.

(2) Let M^′ = (U, ℐ^′) be a II-MIP matroid. According to Theorem 5.5, 𝒞(M^′) is a partition on U. That is, g(𝒞(M^′)) = M^′.

Proposition 5.7. Let $$ be the II-MIP induced by P, n = |P|. Then $$ is the set of bases of $$.

Proof. According to Definition 2.7, Proposition 5.3, and Corollary 5.4, it is straightforward.

Corollary 5.8. $$ does not contain a cycle}).

Proof. According to Propositions 5.1 and 5.7, it is straightforward.

Corollary 5.9. Let $$. Then $$.

Proposition 5.10. Let $$ be the II-MIP induced by P. Then $$ is the set of circuits of $$.

Proof. According to Theorem 5.5, it is straightforward.

Corollary 5.11. $$ is a cycle}.

Proof. According to the definition of $$ and Proposition 5.10, it is straightforward.

Proposition 5.12. Let $$ be the II-MIP induced by P. Then for all X⊆U, $$ is the rank of X in $$.

Proof. According to Definition 2.8 and Proposition 5.3, it is straightforward.

Theorem 5.13. Let $$ be the II-MIP induced by P, $$, and X⊆U an R-definable set. For all Y⊆U, if X∩Y = ∅, then $$.

Proof. Because X is an R-definable set and X∩Y = ∅, according to Proposition 5.3 and Corollary 5.4, for all I₁∈ Max$$ and for all I₂∈ Max$$, I₁∩I₂ = ∅. Furthermore, $$ and I₁ ∪ I₂ ∈ Max ({Z⊆X ∪ Y : for  all  T ∈ P, T ⊈ Z}). According to Definition 2.8, $$ and $$. Because I₁∩I₂ = ∅, |I₁ ∪ I₂ | = |I₁ | + I₂. As a result, $$.

Definition 5.14 (Lower approximation number). Let R be a relation on U. For all X⊆U, f_*R(X) = |{RN_R(x) : x ∈ U∧RN_R(x)⊆X}| is called the lower approximation number of X with respect to R. When there is no confusion, we omit the subscript R.

Example 5.15. Let U = {a, b, c, d, e, f, g, h} be the universe, R an equivalence relation over U, and U/R = {T₁, T₂, T₃, T₄} = {{a, b}, {c}, {d, e, f}, {g, h}}. Compute the lower approximation numbers of X₁, X₂, and X₃ where X₁ = {a, b, c}, X₂ = {a, d, g}, and X₃ = {a, c, g, h}.

Because R is an equivalence relation, according to Definition 2.1, for all x ∈ U, RN_R(x) = [x] _R. Therefore, we can get that f_*(X₁) = |{T₁, T₂}| = 2, f_*(X₂) = |∅ | = 0, and f_*(X₃) = |{T₂, T₄}| = 2.

Similarly, according to Definition 2.2, we can get that f^*(X₁) = |{T₁, T₂}| = 2, f^*(X₂) = |{T₁, T₃, T₄}| = 3, and f^*(X₃) = |{T₁, T₂, T₄}| = 3.

Theorem 5.16. Let $$ be the II-MIP induced by P, $$. Then for all X⊆U, $$.

Proof. Let A⊆X be the largest R-definable set contained in X. Then X = A ∪ (X − A). Thus X − A is an R-indefinable set and for all T ∈ P, T ⊈ X − A. According to Proposition 5.12 and Definition 5.14, $$ and $$. Therefore, in terms of Theorem 5.13, $$.

Lemma 5.17. Let $$ be the II-MIP induced by P, $$. Then for all X⊆U, $$.

Proof. Let A⊆X be the largest R-definable set contained in X and B⊆   ~ X the largest R-definable set contained in ~X. Then, in terms of Theorem 5.16, $$ and $$. So $$.

Lemma 5.18. Let $$ be the II-MIP induced by P, $$. Then for all X⊆U, X is an R-definable set if and only if $$.

Proof. (⇒): According to Theorems 5.13 and 5.16 and Lemma 5.17, it is straightforward.

(⇐): According to Lemma 5.17, |P | = f_*(X) + f_*(~X). Then, according to Definition 5.14, X is an R-definable set.

Proposition 5.19. Let $$ be the II-MIP induced by P. Then for all X⊆U, $$ is the closure of X in $$.

Proof. According to Proposition 5.12, for all x ∈ X, $$. Then, in terms of Definition 2.9, $$. Let Y_X⊆X and $$. For all x ∈ U − X, if $$ then $$. According to Proposition 5.12, for all T ∈ P, T ⊈ Y_X. That means ∃T ∈ P such that T⊆Y_X  ∪  {x}, that is, ∃Y⊆Y_X such that Y ∪ {x} ∈ P. As a result $$.

Proposition 5.20. Let $$ be the II-MIP induced by P. Then $$ is the hyperplane of $$.

Proof. According to Definition 2.10, we need to prove that for all $$, H is a close set of $$, and $$. And more, we need to prove that for all Y⊆U, if $$, then Y is not a hyperplane of $$.

•  

  (1) Is a close set of $$.

•  

  For all $$, there is an equivalence class T ∈ P and a subset X⊆T such that |X | = 2 and H = U − X. Therefore, for all Y⊆H and for all x ∈ X, Y ∪ {x} is not an equivalence class, that is, Y ∪ {x} ∉ P. That is, the set {x ∈ X : ∃Y⊆H  s.t.  Y ∪ {x} ∈ P} = ∅. Thus, according to Proposition 5.19, $$. That is to say H is a close set of $$.

•  

  $$, $$.

•  

  For any T ∈ P, since T is R-definable, by Theorem 5.13

  $$ ()

•  

  That is,

  $$ ()

•  

  Furthermore, since ~T is also R-definable, by Theorem 5.13

  $$ ()

•  

  That is,

  $$ ()

•  

  Therefore, from (5.2) and (5.4), $$.

•  

  (3)  For  all  Y⊆U, if $$, then Y is not a hyperplane of $$.

•  

  If $$, then there are two cases.

•  

  (1)   | U − Y | = 2 and U − Y ⊈ T, for all T ∈ P.

•  

  (2)   | U − Y | ≠ 2.

•  

  Next, we discuss these two cases, respectively.

Case 1. By Proposition 5.19, $$ so Y is not a close set.

Case 2. if |U − Y | = 1, then $$ so Y is not a close set. If |U − Y | > 2, then suppose that $$. In that case, for T ∈ P such that (U − Y)∩T ≠ ∅, |(U − Y)∩T | ≥ 2. So

In that case, $$ is not equal to $$.

Proposition 5.21. Let $$ be the II-MIP induced by P, $$. Then for all  X⊆U,

Proof. According to Proposition 5.10, (2.1), it is straightforward.

Proposition 5.22. Let $$ be the II-MIP induced by P, $$. Then for all X⊆U,

Proof. According to Lemma 5.18, for all X⊆U, if $$, then X is an R-definable set. So $$ is the largest R-definable set contained in X. And $$ is the smallest R-definable set contained X. And then, according to (2.1), it is straightforward.

Proposition 5.23. Let $$ be the II-MIP induced by P, $$. Then for all X⊆U,

Proof. For all T ∈ P, if T⊆X, then for all x ∈ T, T − {x}⊆X. According to Proposition 5.19, $$. That is, $$. In terms of (2.1), $$.