# Homomorphisms of Approximation Spaces

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

---

## Abstract

The notion of the homomorphism of approximation spaces is introduced. Some properties
of homomorphism are investigated, and some characterizations of homomorphism are given. Furthermore, the notion of approximation subspace of approximation spaces is introduced. The relations between approximation subspaces and homomorphisms are studied.


---

## Body

## 1.  Introduction

The theory of rough sets [1], proposed by Pawlak, is an effective tool to conceptualize and analyze various types of data. The theory and applications of rough sets have impressively developed. There are many applications of rough set theory especially in data analysis, artificial intelligence, and cognitive sciences [2–4]. Some basic aspects of the research of rough sets and several applications have been presented by Pawlak and Skowron [5–7].In theory, in recent years scholars have put forward many extended rough set models combining with other soft computing theories or relaxing the relation on the universe or broadening the boundary, such as statistical rough set [8], fuzzy rough set [9–11], probabilistic rough set [12], variable precision rough set [13, 14], Bayesian rough set [15] and grey rough set [16]. It is worth noting that proposed in the early 90s, the decision-theoretic rough set model (DTRS) aims to loosen restrictions of conventional rough approximations [17–20]. It is one of the most important probabilistic rough set models. DTRS has gained research attention in recent years [21–27].In a word, researchers have proposed many models based on rough set theory, but there are a few researches focusing on comparison between approximation spaces corresponding to rough set models. In fact, through the comparison between approximation spaces, we can find the difference between them and give the classification of approximation spaces, which can help a decision maker to choose a suitable rough set model for data analysis. The comparison between approximation spaces, in mathematics, can be explained as a mapping between two approximation spaces. A homomorphism may be viewed as a special mapping between approximation spaces, which preserves or transfers properties from one approximation space to another. In this paper, we define the concept of homomorphism between two approximation spaces based on binary relations and study some properties of homomorphism. In addition, the notion of approximation subspace is introduced, and the relationship between homomorphisms and approximation spaces is investigated.The paper is organized as follows. The next section reviews some basic notions of rough sets based on binary relations and some results to be used in the following sections. In Section3, the concept of homomorphism of approximation spaces is defined, and its main properties are examined. In Section 4, we define the concept of approximation subspace and investigate union, intersection, and complement of approximation spaces. In addition, Theorem 4.14 shows that we can induce an isomorphism of approximation spaces by means of a homomorphism.


## 2.  Review of Relation Models and Their Properties

LetU be a finite and nonempty universe. A binary relation R over a universe U is a subset of the Cartesian product U×U. For two elements x,y∈U, if xRy, we say that y is R related to x, x is a predecessor of y, and y is a successor of x. Given a binary relation, the successor neighborhood of x is defined by xR={y∣xRy} and the predecessor neighborhood of y by Ry={x∣xRy}.Definition 2.1 (see [28]).
LetU be a finite and nonempty universe and R⊆U×U a binary relation on the universe. The pair (U,R) is called an approximation space. For any subset X of the universe U, a pair of lower and upper approximations,  R̲X  and  R¯X,  are defined as follows:(2.1)R̲X={x∈U∣xR⊆X},R¯X={x∈U∣xR∩X≠∅}.Definition 2.2 (see [29, 30]).
LetU be a finite and nonempty universe and R a binary relation on U. The relation R is referred to as serial if, for all x∈U, there exists a y∈U such that xRy.R is referred to as inverse serial if, for all x∈U, there existsa y∈U such that yRx.R is referred to as reflexive if, for all x∈U the relationship xRx holds. R is referred to as symmetric if, for all x,y∈U, xRy implies yRx.R is referred to as transitive if, for all x,y,z∈U, xRy and yRz imply xRz.R is referred to as Euclidean if for all x,y,z∈U,xRy and xRz imply yRz. Since the approximation operators are defined through the successor neighborhood, it is more convenient to express equivalently the conditions on a binary relation as follows:Serial:forallx∈U,xR≠∅,Inverse serial:forallx∈U,thereexistsay∈Usuchthatx∈yR,Reflexive:forallx∈U,x∈xR,Symmetric:forallx,y∈U,ifx∈yR,theny∈xR,Transitive:forallx,y∈U,ify∈xR,thenyR⊆xR,Euclidean:forallx,y∈U,ify∈xR,thenxR⊆yR.Theorem 2.3 (see [28]).
LetU be a finite and nonempty universe and  R⊆U×U a binary relation on the universe. The approximation operators satisfy the following properties: for subsets  X,Y⊆U,
(2.2)(L0)R̲X=~R¯~X,(U0)R¯X=~R̲~X,(L1)R̲U=U,(U1)R¯∅=∅,(L2)R̲(X∩Y)=R̲X∩R̲Y,(U2)R¯(X∪Y)=R¯X∪R¯Y,(L3)R̲(X∪Y)⊇R̲X∪R̲Y,(U3)R¯(X∩Y)⊆R¯X∩R¯Y,(L4)X⊆Y⟹R̲X⊆R̲Y,(U4)X⊆Y⟹R¯X⊆R¯Y.With respect to certain special types, say, serial, inverse serial, reflexive, symmetric, transitive, and Euclidean binary relations on the universe of discourseU, the approximation operators have additional properties [28, 29, 31].Theorem 2.4.
LetU be a finite and nonempty universe and  R⊆U×U a binary relation on the universe, then the following assertions hold. (1)
Risserial⟺(U0)R¯U=U.(2)
Risinverseserial⟺R¯{x}≠∅,forallx∈U.(3)
Risreflexive⟺(U6)X⊆R¯X,forallX∈U.(4)
Rissymmetric⟺(U7)X⊆R̲R¯X,forallX∈U.(5)
Ristransitive⟺(L8)R̲X⊆R̲R̲X,forallX∈U.(6)
RisEuclidean⟺(U9)R¯X⊆R̲R¯X,forallX∈U.


## 3.  The Properties of Homomorphisms and Isomorphisms

In this section, we introduce the notion of the homomorphism of approximation spaces and study on the properties of the homomorphisms.We can study the relations between the approximation operators of one approximation space and the approximation operators of the other approximation space by means of mappings. For this purpose, in the following we present the concept of the homomorphism of approximation spaces.Definition 3.1.
LetU1 and U2 be finite and nonempty universes, f:U1→U2 a mapping from U1 to U2,R1 a binary relation on U1, and R2 a binary relation on U2.f is called a lower homomorphism from the approximation space (U1,R1) to the approximation space (U2,R2) if, for all  X⊆U1, f(R1̲X)⊆R2̲f(X).f  is called an upper homomorphism from (U1,R1) to (U2,R2) if, for all X⊆U1,f(R1¯X)⊆R2¯f(X). f is called a homomorphism from (U1,R1) to (U2,R2) if, for all X⊆U1,f(R1̲X)⊆R2̲f(X) and  f(R1¯X)⊆R2¯f(X). An injective homomorphism from (U1,R1) to (U2,R2) is called a monomorphism, a surjective homomorphism an epimorphism, and a bijective homomorphism an isomorphism.Remark 3.2.
In the above definition, it is easy to show thatf is a homomorphism from (U1,R1) to (U2,R2) if and only if f is a lower homomorphism from (U1,R1) to (U2,R2) and f is an upper homomorphism from (U1,R1) to (U2,R2).For better understanding of the definition we illustrate it by the following examples.Example 3.3.
Let(U1,R1) and (U2,R2) be two approximation spaces, where U1={x1,x2}, U2={y1,y2,y3,y4}, R1={(x1,x1),(x2,x2),(x1,x2),(x2,x1)}, and R2={(y1,y1),(y2,y3),(y4,y3)}. f is a mapping from U1 to U2 and f(x1)=y1,f(x2)=y1. It is easy to check that for all X⊆U1, if X≠U1, then R1̲X=∅. Hence, for all X⊂U1,  f(R1̲X)=∅⊆R2̲f(X). If X=U1, then R1̲X=U1. Therefore, f(R1̲X)={y1}⊆{y1}=R2̲f(X) when X=U1. We have shown that for all X⊆U1,f(R1̲X)⊆R2̲f(X). It follows from Definition 3.1 that f is a lower homomorphism from (U1,R1) to (U2,R2).Example 3.4.
Let(U1,R1) and (U2,R2) be two approximation spaces, where R2=U2×U2. f is a mapping from U1 to U2. It is easy to check that for all X⊆U1, if X≠∅ then R2¯f(X)=U2. Hence for all X⊆U and X≠∅, f(R1¯X)⊆U2=R2¯f(X). If X=∅, then by the part (U1) of Theorem 2.3 we have that R1¯X=∅. Therefore, if X=∅, then f(R1¯X)=∅⊆R2¯f(X). We have shown that for all  X⊆U1,f(R1¯X)⊆R2¯f(X). It follows from Definition 3.1 that f is an upper homomorphism from (U1,R1) to (U2,R2).Notation 1.
LetU denote a finite and nonempty set and R⊆U×U an equivalence relation on U. Then let U/R denote the quotient set consisting of equivalence classes of R.Example 3.5.
Let(U1,R1) and (U2,R2) be two approximation spaces, where U1={x1,x2,x3}, U2={y1,y2}, U1/R1={{x1,x2},{x3}}, and U2/R2={{y1},{y2}}. f is a mapping from U1 to U2 and f(x1)=f(x2)=y1, f(x3)=y2. We first show that f is a lower homomorphism from (U1,R1) to (U2,R2). By
(3.1)R1̲∅=R1̲{x1}=R1̲{x2}=∅,
we can get that f(R1̲∅)⊆R2̲f(∅),f(R1̲{x1})⊆R2̲f({x1}),andf(R1̲{x2})⊆R2̲f({x2}). By
(3.2)R1̲{x1,x3}=R1̲{x2,x3}=R1̲{x3}={x3},R2̲{y1,y2}={y1,y2},R2̲{y2}={y2},
we can get that
(3.3)f(R1̲{x1,x3})={y2}⊆{y1,y2}=R2̲f({x1,x3}),f(R1̲{x2,x3})={y2}⊆{y1,y2}=R2̲f({x2,x3}),f(R1̲{x3})={y2}⊆{y2}=R2̲f({x3}).
In addition, by
(3.4)R1̲{x1,x2}={x1,x2},R1̲U1=U1,R2̲{y1}={y1},R2̲U2=U2,
we get that f(R1̲{x1,x2})={y1}⊆{y1}=R2̲f({x1,x2}), f(R1̲U1)=U2⊆U2=R2̲f(U1). We have shown that for all X⊆U1, f(R1̲X)⊆R2̲f(X). It follows from Definition 3.1 that f is a lower homomorphism from (U1,R1) to (U2,R2).
In the following, we will prove thatf is also an upper homomorphism from (U1,R1) to (U2,R2). By R1¯∅=∅, we get that f(R1¯∅)⊆R2¯f(∅). By R1¯{x3}={x3} and R2¯{y2}={y2}, we can get that f(R1¯{x3})={y2}⊆{y2}=R2¯f({x3}). By(3.5)R1¯{x1}=R1¯{x2}=R1¯{x1,x2}={x1,x2},R2¯{y1}={y1},
we can get that
(3.6)f(R1¯{x1})={y1}⊆{y1}=R2¯f({x1}),f(R1¯{x2})={y1}⊆{y1}=R2¯f({x2}),f(R1¯{x1,x2})={y1}⊆{y1}=R2¯f({x1,x2}).
By
(3.7)R1¯{x1,x3}=R1¯{x2,x3}=R1¯U1=U1,R2¯U2=U2,
we can get that
(3.8)f(R1¯{x1,x3})=U2⊆U2=R2¯f({x1,x3}),f(R1¯{x2,x3})=U2⊆U2=R2¯f({x2,x3}),f(R1¯U1)=U2⊆U2=R2¯f(U1).
We have proved that for all X⊆U1, f(R1¯X)⊆R2¯f(X). It follows from Definition 3.1 that f is an upper homomorphism from (U1,R1) to (U2,R2).
In summary, by Remark3.2, f is a homomorphism from (U1,R1) to (U2,R2).Example 3.6.
LetA1=(U1,R1) and A2=(U2,R2) be approximation spaces, where U1={x1,x2,x3}, U2={y1,y2,y3}, U1/R1={{x1,x2},{x3}}, and U2/R2={{y1,y2},{y3}}. f is a mapping from U1 to U2 and f(x1)=y1,f(x2)=y2, and f(x3)=y3. By Definition 3.1, it is easy to show that f is an isomorphism from (U1,R1) to (U2,R2).For better understanding of the upper homomorphism we give the following theorem. In fact, we present a criterion for judging an upper homomorphism.Theorem 3.7.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping,  R1 a binary relation on  U1 and  R2 a binary relation on  U2, then  f is an upper homomorphism from  (U1,R1) to  (U2,R2) if and only if, for all  x∈U1,  f(R1¯{x})⊆R2¯f({x}).Proof.
The necessity follows directly from Definition3.1.
Conversely, for allX⊆U, by the part (U2) of Theorem 2.3, we have that(3.9)f(R1¯X)=f(⋃x∈XR1¯{x})=⋃x∈Xf(R1¯{x}),R2¯f(X)=R2¯f(⋃x∈X{x})=R2¯(⋃x∈Xf({x}))=⋃x∈XR2¯f({x}).
Applying the condition for all x∈U1, f(R1¯{x})⊆R2¯f({x}), we conclude that
(3.10)⋃x∈Xf(R1¯{x})⊆⋃x∈XR2¯f({x}).
Hence,
(3.11)f(R1¯X)⊆R2¯f(X).
We have proved that for all X⊆U, f(R1¯X)⊆R2¯f(X). It follows from Definition 3.1 that f is an upper homomorphism from (U1,R1) to (U2,R2).In the following, whenf:U1→U2 is a bijective from U1 to U2, some characterizations of homomorphisms are given.Theorem 3.8.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a bijective from  U1 to  U2,  R1 a binary relation on  U1, and  R2 a binary relation on  U2, then the following assertions hold: (1)
f is an upper homomorphism from (U1,R1) to (U2,R2) if and only if for all X⊆U1, f(R1̲X)⊇R2̲f(X),(2)
f is a lower homomorphism from (U1,R1) to (U2,R2) if and only if for all X⊆U1, f(R1¯X)⊇R2¯f(X),(3)
f is a homomorphism from (U1,R1) to (U2,R2) if and only if for all X⊆U1, f(R1̲X)⊇R2̲f(X) and f(R1¯X)⊇R2¯f(X),Proof.
(1) Sincef is a bijective, it follows that for all X⊆U1, f(~X) = ~f(X). Hence, f is an upper homomorphism from (U1,R1) to (U2,R2)⇔ for all X⊆U1, f(R1¯X)⊆R2¯f(X)⇔forallX⊆U1,f(R1¯(~X))⊆R2¯f(~X),⇔forallX⊆U1,f(~R1̲(X)) ⊆R2¯(~f(X)),⇔forallX⊆U1,
~f(R1̲(X))⊆~R2̲(f(X)),⇔forallX⊆U1,f(R1̲(X))⊇R2̲(f(X)).This finishes the proof.
(2) It is similar to the proof of (1).
(3) By (1), (2), and Remark3.2, (3) holds.As natural consequences of the above theorem we can obtain the following conclusions.Theorem 3.9.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a bijective,  R1 a binary relation on  U1, and  R2 a binary relation on  U2, then the following assertions are equivalent: (1)
f is an isomorphism from (U1,R1) to (U2,R2),(2)
for allX⊆U1, f(R1̲X)=R2̲f(X),(3)
for allX⊆U1, f(R1¯X)=R2¯f(X).Proof.
The proof follows directly from Definition3.1, Theorems 2.4, and 3.8.The following example shows that if the above mappingf is surjective and satisfies the condition for all X⊆U1, f(R1̲X)=R2̲f(X), then f is not necessarily an isomorphism.Example 3.10.
Let(U1,R1) and (U2,R2) be two approximation spaces, where U1={x1,x2}, U2={y1}, U1/R1={{x1},{x2}}, and U2/R2={{y1}}. f is a mapping from U1 to U2 and f(x1)=f(x2)=y1, then R1̲∅=∅, R1̲{x1}={x1}, R1̲{x2}={x2}, R1̲U1=U1 and R2̲∅=∅, R2̲U2=U2. Hence,
(3.12)f(R1̲∅)=∅=R2̲f(∅),f(R1̲{x1})=U2=R2̲f({x1}),f(R1̲{x2})=U2=R2̲f({x2}),f(R1̲U1)=U2=R2̲f(U1).We have shown that for all X⊆U1, f(R1̲X)=R2̲f(X).
In the following, we shall prove that for allX⊆U1, f(R1¯X)=R2¯f(X). It is easy to check that R¯∅=∅, R¯{x1}={x1}, R¯{x2}={x2}, R¯U1=U1 and R2¯∅=∅, R2¯U2=U2. Hence,(3.13)f(R1¯∅)=∅=R2¯f(∅),f(R1¯{x1})=U2=R2¯f({x1}),f(R1¯{x2})=U2=R2¯f({x2}),f(R1¯U1)=U2=R2¯f(U1).We have shown that for all X⊆U1, f(R1¯X)=R2¯f(X).
Thus, by Definition3.1, f is a homomorphism from (U1,R1) to (U2,R2), but f is not an isomorphism.Corollary 3.11.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a bijective,  R1 a binary relation on  U1, and  R2 a  binary relation on  U2, then  f is an isomorphism from  (U1,R1) to  (U2,R2) if and only if  f-1 is an isomorphism from (U2,R2) to  (U1,R1).Proof.
Sincef is a bijective, it follows that f-1 is a bijective from U2 to U1. For all Y⊆U2, by Theorem 3.9, we have that f(R1̲f-1(Y))=R2̲f(f-1(Y)))=R2̲Y. Hence, R1̲f-1(Y)=f-1(R2̲Y). We have proved that for all Y⊆U2, f-1(R2̲Y)=R1̲f-1(Y). It follows from Theorem 3.9 that f-1 is an isomorphism from (U2,R2) to (U1,R1). The proof of the sufficiency is similar to the proof of the necessity.Notation 2.
The symbolism(U1,R1)≅(U2,R2) signifies that there is at least one isomorphism from approximation space (U1,R1) to approximation space (U2,R2). By Corollary 3.11, we conclude that (U1,R1)≅(U2,R2)⇔(U2,R2)≅(U1,R1).
In the following, some properties of homomorphisms are given. These properties reveal the difference and relationship between two approximation spaces.Theorem 3.12.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a surjective from  U1 to  U2,  R1 a binary relation on  U1, and  R2 a binary relation on  U2. If  f is an upper homomorphism from  (U1,R1) to  (U2,R2), then the following assertions hold: (1)
IfR1 is serial, then R2 is serial,(2)
IfR1 is inverse serial, then R2 is inverse serial,(3)
IfR1 is reflexive, then R2 is reflexive.Proof.
(1) SinceR1 is serial, it follows from part (1) of Theorem 2.4 that R1¯U1=U1. By the condition, f is an upper homomorphism from (U1,R1) to (U2,R2), hence we conclude that f(U1)=f(R1¯U1)⊆R2¯f(U1). In addition, since f is a surjective, it follows that f(U1)=U2. Thus U2⊆R2¯f(U1)=R2¯U2. On the other hand, clearly, U2⊇R2¯U2. Hence, R2¯U2=U2 and so by part (1) of Theorem 2.4, R2 is serial.
(2) By part (2) of Theorem2.4, we need to prove only that for all y∈U2, R2¯{y}≠∅. Let y∈U2. Since f is a surjective, it follows that there exists x∈U1 such that f(x)=y. By the condition, R1 is inverse serial, therefore by part (2) of Theorem 2.4, we have that R1¯{x}≠∅ and so f(R1¯{x})≠∅. Since f is an upper homomorphism from (U1,R1) to (U2,R2), it follows from Definition 3.1 that ∅≠f(R1¯{x})⊆R2¯f({x})=R2¯{f(x)}=R2¯{y}. Thus, R2¯{y}≠∅. This finishes the proof of (2).
(3) By the part (3) of Theorem2.4, we need to prove only that for all Y⊆U2, Y⊆R2¯Y. Let Y⊆U2. Since f is a surjective, it follows that there exists X⊆U1 such that f(X)=Y. By the condition, R1 is reflexive, therefore by the part (3) of Theorem 2.4, we have that X⊆R1¯X and so Y=f(X)⊆f(R1¯X). Since f is an upper homomorphism from (U1,R1) to (U2,R2), it follows from Definition 3.1 that Y⊆f(R1¯X)⊆R2¯f(X)=R2¯Y. Thus, for all Y⊆U2, Y⊆R2¯Y. This finishes the proof of (3).Theorem 3.13.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping from  U1 to  U2,R1 a binary relation on  U1 and  R2 a binary relation on  U2.  f is an epimorphism from  (U1,R1) to  (U2,R2). If  R1 is symmetric, then  R2 is symmetric.Proof.
By the part (4) of Theorem2.4, we need to prove only that for all Y⊆U2, Y⊆R2̲R2¯Y. Let Y⊆U2. Since f is a surjective, it follows that there exists X⊆U1 such that f(X)=Y. By the condition, R1 is symmetric, therefore by part (4) of Theorem 2.4, we have that X⊆R1̲R1¯X and so Y=f(X)⊆f(R1̲R1¯X). Since f is a homomorphism from (U1,R1) to (U2,R2), it follows from Definition 3.1 that f(R1̲R1¯X)⊆R2̲f(R1¯X) and f(R1¯X)⊆R2¯f(X).Thus, by the part (4) of Theorem 2.3, we have that Y⊆f(R1̲R1¯X)⊆R2̲f(R1¯X)⊆R2̲R2¯f(X)=R2̲R2¯Y. Hence for all Y⊆U2, Y⊆R2̲R2¯Y. This finishes the proof of theorem.The following theorem gives main properties of isomorphisms on approximation spaces.Theorem 3.14.
LetU1 and  U2 be finite and nonempty universes,  R1 a binary relation on  U1 and  R2 a binary relation on  U2. If  (U1,R1)≅(U2,R2), then the following assertions hold: (1)
R1 is serial if and only if R2 is serial,(2)
R1 is inverse serial if and only if R2 is inverse serial,(3)
R1 is reflexive if and only if R2 is reflexive,(4)
R1 is transitive if and only if R2 is transitive,(5)
R1 is symmetric if and only if R2 is symmetric,(6)
R1 is Euclidean if and only if R2 is Euclidean,Proof.
By Theorem3.12 and Notation 2, (1), (2) and (3) hold.
(4) We first prove the necessity. By part (5) of Theorem2.4, we need only prove that for all Y⊆U2, R2̲Y⊆R2̲R2̲Y. By the condition (U1,R1)≅(U2,R2), we may assume that f is an isomorphism from (U1,R1) to (U2,R2). Let Y⊆U2. Since f is a surjective, it follows that there exists X⊆U1 such that f(X)=Y. By the condition, R1 is transitive, therefore by part (5) of Theorem 2.4, we have that R1̲X⊆R1̲R1̲X and so f(R1̲X)⊆f(R1̲R1̲X). Since f an isomorphism from (U1,R1) to (U2,R2), it follows from Theorem 3.9 that f(R1̲X)=R2̲f(X) and f(R1̲R1̲X)=R2̲f(R1̲X). Thus, R2̲Y=R2̲f(X)=f(R1̲X)⊆f(R1̲R1̲X)=R2̲f(R1̲X)=R2̲R2̲f(X)=R2̲R2̲Y. Hence for all Y⊆U2, R2̲Y⊆R2̲R2̲Y. So R2 is transitive. By Notation 2, the proof of the sufficiency is similar to the proof of the necessity.
(5) By theorem3.13 and Notation 2, (5) holds.
(6) We first prove the necessity. By part (6) of Theorem2.4, we need only prove that for all Y⊆U2, R2¯Y⊆R2̲R2¯Y. By the condition (U1,R1)≅(U2,R2), we may assume that f is an isomorphism from (U1,R1) to (U2,R2). Let Y⊆U2. Since f is a surjective, it follows that there exists X⊆U1 such that f(X)=Y. By the condition, R1 is Euclidean, therefore by the part (6) of Theorem 2.4, we have that R1¯X⊆R1̲R1¯X and so f(R1¯X)⊆f(R1̲R1¯X). Since f an isomorphism from (U1,R1) to (U2,R2), it follows from Theorem 3.9 that f(R1¯X)=R2¯f(X) and f(R1̲R1¯X)=R2̲f(R1¯X). Thus, R2¯Y=R2¯f(X)=f(R1¯X)⊆f(R1̲R1¯X)=R2̲f(R1¯X)=R2̲R2¯f(X)=R2̲R2¯Y. Hence, for all Y⊆U2, R2¯Y⊆R2̲R2¯Y. So R2 is Euclidean. By Notation 2, the proof of the sufficiency is similar to the proof of the necessity.


## 4.  Approximation Subspaces and Homomorphisms

In mathematics, subspaces are similar to original space and independent of the original space, such as, linear subspaces of linear space subspaces of topological space and. According to ideas, the notion of approximation subspace of approximation space is introduced in this section. For this purpose, we first introduce the following notation.Notation 3.
LetU be a finite and nonempty universe, R⊆U×U a binary relation on U, and S⊆U. Then let R∣S denote the set R∩(S×S), that is, R∣S=R∩(S×S). Clearly, R∣S is a binary relation on S.Definition 4.1.
LetU be a finite and nonempty universe, R a binary relation on U and S⊆U.Then the pair (S,R∣S) is called an approximation subspace of the approximation space (U,R) if for all X⊆S,R∣S̲X=R̲X and R∣S¯X=R¯X.Remark 4.2.
LetU be a finite and nonempty universe, R⊆U×U a binary relation on U, and S⊆U. i is a mapping from S to U and for all x∈S, i(x)=x. If (S,R∣S) is an approximation subspace of (U,R), then by Definitions 3.1 and 4.1, it is easy to check that i is a homomorphism from (S,R∣S) to (U,R).Lemma 4.3.
LetU be a finite and nonempty universe and  R⊆U×U a binary relation on  U. If  R is an equivalence relation on  U, then  R∣S is an equivalence relation on  S.Proof.
(1) SinceR is an equivalence relation on U, it follows that for all x∈S, (x,x)∈R. Hence, (x,x)∈R∩(S×S)=R∣S and so R∣S is reflexive.
(2) Let(x,y)∈R∣S, then (x,y)∈S×S and (x,y)∈R. Clearly, (y,x)∈S×S. Since R is an equivalence relation on U, it follows that (y,x)∈R. Hence (y,x)∈R∩(S×S)=R∣S. Therefore R∣S is symmetric.
(3) Let(x,y),(y,z)∈R∣S, then (x,y),(y,z)∈S×S and (x,y),(y,z)∈R. Clearly (x,z)∈S×S. Since R is an equivalence relation on U, it follows that (x,z)∈R. Hence, (x,z)∈R∩(S×S)=R∣S. Therefore, R∣S is transitive.
By (1), (2), and (3), we conclude thatR∣S is an equivalence relation on S.Note 1.
LetR⊆U×U be an equivalence relation on U, that is, R is reflexive, symmetric, and transitive. The pair (U,R) is called an approximation space. The equivalence relation R partitions the universe U into disjoint subsets called equivalence classes. Elements in the same equivalence class are said to be indistinguishable. Equivalent classes of R are called elementary sets. A union of elementary sets is called an R-definable (composed) set [32]. The empty set is considered to be a R-definable set [33]. Let X⊆U, then it is easy to check that X is an R-definable (composed) set if and only if R̲X=X=R¯X. Clearly, if X,Y⊆U are R-definable sets, then X∪Y, X∩Y and~X are R-definable sets.Lemma 4.4.
LetU be a finite and nonempty universe,  R⊆U×U an equivalence relation on  U and  S⊆U, then  S is an  R-definable set if and only if, for all  x∈S,  [x]R∣S=[x]R.Proof.
We first prove the necessity. Letx∈S. Since S is an R-definable set, it follows that R̲S=S=R¯S and so [x]R⊆S. Hence, for all y∈[x]R, we get that (x,y)∈S×S and (x,y)∈R, which implies (x,y)∈R∩(S×S)=R∣S and so y∈[x]R∣S. Thus [x]R⊆[x]∣R∣S. On the other hand, by R∣S=R∩(S×S), it is clear that [x]R⊇[x]R∣S. So [x]R∣S=[x]R.
Conversely, suppose thatS is not an R-definable set, then R̲S≠R¯S. Hence, there exists y∈U such that [y]R⊈S and [y]R∩S≠∅. Choosing x∈[y]R∩S, namely, x∈[y]R and x∈S. Since R is an equivalence relation on U, it follows that [x]R=[y]R. Hence, [x]R⊈S and x∈S. By Lemma 4.3, we have that R∣S is an equivalence relation on S. Thus, [x]R∣S⊆S and so [x]R∣S≠[x]R. We have proved that supposing that S is not crisp (exact with respect to R), then there exists x∈S such that [x]R∣S≠[x]R. This is a contradiction with the condition for all x∈S, [x]R∣S=[x]R. It follows that S is an R-definable set.WhenR is an equivalence relation in the approximation space (U,R), some characterizations of approximation subspace are given in the following theorem.Theorem 4.5.
LetU be a finite and nonempty universe,  R⊆U×U an equivalence relation on  U and  S⊆U, then the following assertions are equivalent: (1)
S is a R-definable set,(2)
for allX⊆S, R∣S¯X=R¯X,(3)
(S,R∣S) is an approximation subspace of the approximation space (U,R),(4)
for allX⊆S, R∣S̲X=R̲X.Proof.
(1)⇒(2) Let X⊆S, then by part (U4) of Theorem 2.3, we have that R¯X⊆R¯S. Since R is an equivalence relation on U and S is an R-definable set, it follows that R¯S=S. Hence, R¯X⊆R¯S=S and so for all x∈R¯X, we have that x∈S and [x]R∩X≠∅. In addition, by Lemma 4.4, we have that [x]R∣S=[x]R. Hence, [x]R∣S∩X≠∅ and so x∈R∣S¯X. Thus R∣S¯X⊇R¯X. On the other hand, for all x∈R∣S¯X, clearly x∈S and [x]R∣S∩X≠∅. By Lemma 4.4, we have that [x]R∣S=[x]R. Thus, [x]R∩X≠∅, which implies x∈R¯X. Hence R∣S¯X⊆R¯X. Consequently, R∣S¯X=R¯X.
(2)⇒(1) Suppose that S is not an R-definable set, then by Lemma 4.4, there exists x∈S, such that [x]R∣S≠[x]R. By Lemma 4.3, R∣S is an equivalence relation on S, thus R∣S¯{x}=[x]R∣S. On the other hand, R¯{x}=[x]R. Hence, R∣S¯{x}≠R¯{x}. We have proved that supposing that S is not a R-definable set, then there exists X={x}⊆S such that R∣S¯X≠R¯X. This is a contradiction with the condition for all X⊆S, R∣S¯X=R¯X. It follows that S is an R-definable set.
(2)⇒(3) By Definition 4.1, we need to prove only that for all X⊆S, R∣S̲X=R̲X. Since (1)⇔(2), it follows that S is an R-definable set. By Lemma 4.4, we can get that for all x∈S, [x]R∣S=[x]R. For all x∈R∣S̲X, clearly x∈S. Hence, x∈R∣S̲X⇒[x]R∣S⊆X⇒[x]R⊆X⇒x∈R̲X. Thus, R∣S̲X⊆R̲X. On the other hand, since R is an equivalence relation on U, it follows that R̲X⊆X⊆S. Hence, x∈R̲X implies x∈S. Thus, x∈R̲X⇒[x]R⊆X⇒[x]R∣S⊆X⇒x∈R∣S̲X. Therefore R∣S̲X⊇R̲X. It follows that R∣S̲X=R̲X. This completes the proof.
(3)⇒(4) By Definition 4.1, the proof is obvious.
(4)⇒(1) Suppose that S is not an R-definable set, then by Lemma 4.4, there exists x∈S such that [x]R∣S≠[x]R. By R∣S=R∩(S×S), it is easy to check that [x]R∣S⊆[x]R. Hence, [x]R∣S⊂[x]R and so R̲[x]R∣S=∅. On the other hand, by Lemma 4.3, we have that R∣S is an equivalent relation on S. Thus, R∣S̲[x]R∣S=[x]R∣S. Hence, R∣S̲[x]R∣S≠R̲[x]R∣S. We have proved that supposing that S is not an R-definable set, then there exists X=[x]R∣S⊆S such that R∣S̲X≠R̲X. This is a contradiction with the condition for all X⊆S, R∣S̲X=R̲X. This completes the proof.Notation 4.
Let(U,R)  be an approximation space. Let  𝒮𝒫(A) denote the set of all approximation subspaces of  (U,R).Now we consider the union, intersection, and complement of approximation subspaces.Definition 4.6.
Let(U,R) be an approximation space, where U is a finite and nonempty universe, R is an equivalence relation on U, and S,H⊆U.If (S,R∣S),(H,R∣H)∈𝒮𝒫(A), then the union, intersection and complement of approximation subspaces are correspondingly defined as follows:
(4.1)(S,R∣S)∪(H,R∣H)=(S∪H,R∣S∪R∣H),(S,R∣S)∩(H,R∣H)=(S∩H,R∣S∩R∣H),~(S,R∣S)=(~S,R∣~S).Lemma 4.7.
Let(U,R)be an approximation space, where Uis a finite and nonempty universe and  R is an equivalence relation on U, and let  (S,R∣S),(H,R∣H)∈𝒮𝒫(A), then the following assertions hold: (1)
R∣S∪R∣H=R∣S∪H,(2)
R∣S∩R∣H=R∣S∩H.Proof.
(1) For all(x,y)∈R∣S∪H, clearly, y∈[x]R∣S∪H and (x,y)∈(S∪H)×(S∪H). In addition, by Theorem 4.5, we have that S and H are crisp (exact with respect to R), hence S∪H is crisp (exact with respect to R), and so by Lemma 4.4, we have that [x]R∣S∪H=[x]R. (x,y)∈(S∪H)×(S∪H) implies x∈S∪H, namely, x∈S or x∈H. We may assume that x∈S, then by Lemma 4.4, we have [x]R∣S=[x]R. Hence, [x]R∣S∪H=[x]R∣S and so y∈[x]R∣S∪H implies y∈[x]R∣S. Thus, (x,y)∈R∣S. Hence, R∣S∪R∣H⊇R∣S∪H. On the other hand, clearly R∣S=R∩(S×S)⊆R∩((S∪H)×(S∪H))=R∣S∪H and R∣H=R∩(H×H)⊆R∩((S∪H)×(S∪H))=R∣S∪H. Hence, R∣S∪R∣H⊆R∣S∪H. It follows that R∣S∪R∣H=R∣S∪H.
(2) For all(x,y)∈R∣S∩R∣H, clearly, (x,y)∈R∣S=R∩(S×S) and (x,y)∈R∣H=R∩(H×H). Hence, (x,y)∈R, x,y∈S and x,y∈H, which implies (x,y)∈R and x,y∈S∩H. Therefore (x,y)∈R∩((S∩H)×(S∩H))=R∣S∩H. Thus R∣S∩R∣H⊆R∣S∩H. On the other hand, clearly, R∣S=R∩(S×S)⊇R∩((S∩H)×(S∩H))=R∣S∩H and R∣H=R∩(H×H)⊇R∩((S∩H)×(S∩H))=R∣S∩H. Hence, R∣S∩R∣H⊇R∣S∩H. It follows that R∣S∩R∣H=R∣S∩H.It is meaningful to notice that the union, intersection and complement of approximation subspaces still are approximation subspaces.Theorem 4.8.
Let(U,R) be an approximation space, where  U is a finite and nonempty universe and  R an equivalence relation on  U, and  S,H⊆U. If  (S,R∣S),(H,R∣H)∈𝒮𝒫(A), then  (S,R∣S)∪(H,R∣H)∈𝒮𝒫(A),  (S,R∣S)∩(H,R∣H)∈𝒮𝒫(A), and ~(S,R∣S)∈𝒮𝒫(A).Proof.
By Lemma4.7 and Definition 4.6, we have that (S,RS)∪(H,RH)=(S∪H,RS∪RH)=(S∪H,RS∪H), (S,RS)∩(H,RH)=(S∩H,RS∩RH)=(S∩H,RS∩H). It follows from Note 1 and Theorem 4.5 that (S,RS)∪(H,RH)∈𝒮𝒫(A), (S,RS)∩(H,RH)∈𝒮𝒫(A). In addition, by Note 1 and Theorem 4.5, we can get that ~(S,RS)∈𝒮𝒫(A).When the binary relations are equivalence relations in approximation spaces, the important properties of homomorphism are given in the following theorem.Theorem 4.9.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping from  U1 to  U2,  R1 an equivalence relation on  U1, and  R2 an equivalence relation on  U2.  f is a homomorphism from  (U1,R1) to  (U2,R2) and  X⊆U1. If  X is an  R1-definable set, then  f(X) is a  R2-definable set.Proof.
SinceX is an R1-definable set, it follows that R1¯X=R1̲X and so f(R1¯X)=f(R1̲X). In addition, since f is a homomorphism from (U1,R1) to (U2,R2), it follows from Definition 3.1 and Theorem 3.9 that f(R1̲X)=R2̲f(X) and f(R1¯X)=R2¯f(X). Thus, R2¯f(X)=R2̲f(X). Hence, f(X) is an R2-definable set.As natural consequence of the above theorem, we can obtain the following conclusion.Corollary 4.10.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping from  U1 to  U2,  R1 an equivalence relation on  U1, and  R2 an equivalence relation on  U2.  f is a homomorphism from  (U1,R1) to  (U2,R2) and  X⊆U1. If  (X,R∣X) is an approximation subspace of  (U1,R1), then  (f(X),R∣f(X)) is an approximation subspace of  (U2,R2).Proof.
The proof follows directly from Theorems4.5 and 4.9.Notation 5.
LetU1 and U2 be finite and nonempty universes and f:U1→U2 a mapping from U1 to U2. Then let Kf denote the binary relation on U1 and x,y∈U1, xKfy⇔f(x)=f(y). Clearly, Kf is an equivalence relation on U1. U1/Kf denotes the set of all equivalence classes of Kf, that is, U1/Kf={[x]Kf∣x∈U1}.Lemma 4.11.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping,  R1 an equivalence relation on  U1, and  R2 an equivalence relation on  U2. One writes
(4.2)R1/Kf={([x]Kf,[y]Kf)∣[x]Kf,[y]Kf∈U1/Kf,∃u∈[x]Kf,∃v∈[y]Kf,s.t.uR1v}.
Then R1/Kf is a reflexive and symmetric relation on U1/Kf.Proof.
By the definition ofR1/Kf, it is easy to show that if ([x1]Kf,[y1]Kf)=([x]Kf,[y]Kf), then ([x]Kf,[y]Kf)∈R1/Kf⇔([x1]Kf,[y1]Kf)∈R1/Kf. Hence, R1/Kf is a binary relation on U1/Kf. In the following, we shall prove that R1/Kf is reflexive and symmetric.(i)
Let[x]Kf∈U1/Kf, clearly, x∈U1. Since R1 is an equivalence relation on U1, it follows that xR1x. Hence, by the definition of R1/Kf, we have that ([x]Kf,[x]Kf)∈R1/Kf. Thus, R1/Kf is reflexive.(ii)
Let([x]Kf,[y]Kf)∈R1/Kf, then by the definition of R1/Kf, there exist u∈[x]Kf and v∈[y]Kf such that uR1v. Since R1 is an equivalence relation on U1, it follows that vR1u. Hence, there exist v∈[y]Kf and u∈[x]Kf such that vR1u and so by the definition of R1/Kf, ([y]Kf,[x]Kf)∈R1/Kf. Thus, R1/Kf is symmetric.Lemma 4.12.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping,  R1 an equivalence relation on  U1, and  R2 an equivalence relation on  U2.  f is a homomorphism from  (U1,R1) to  (U2,R2). For all  [x]Kf∈U1/Kf, one defines  h([x]Kf)=f(x), then  h is a mapping from  U1/Kf to  U2 and for all  Y⊆U1/Kf,  h(Y)=f(⋃[y]Kf∈Y[y]Kf).Proof.
Let[x]Kf,[y]Kf∈U1/Kf. If [x]Kf=[y]Kf, then by Notation 5, we have that f(x)=f(y). Hence, by the definition of h, we can get that h([x]Kf)=f(x)=f(y)=h([y]Kf). We have proved that for all [x]Kf,[y]Kf∈U1/Kf, if [x]Kf=[y]Kf, then h([x]Kf)=h([y]Kf). Therefore, h is a mapping from U1/Kf to U2.
We shall prove that for allY⊆U1/Kf, h(Y)=f(⋃[y]Kf∈Y[y]Kf). By Notation 5, it is easy to verify that for all [x]Kf∈U1/Kf, f([x]Kf)={f(x)}. Hence, h(Y) =h(⋃[y]Kf∈Y{[y]Kf}) = ⋃[y]Kf∈Y{h([y]Kf)}=⋃[y]Kf∈Y{f(y)}=⋃[y]Kf∈Yf([y]Kf)=f(⋃[y]Kf∈Y[y]Kf). It follows that for all Y⊆U1/Kf, h(Y)=f(⋃[y]Kf∈Y[y]Kf).Lemma 4.13.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping,  R1 an equivalence relation on  U1, and  R2 an equivalence relation on  U2, then(4.3)∀Y⊆U1/Kf,R1/Kf¯Y=⋃[y]Kf∈Y[[y]Kf]R1/Kf.Proof.
Let[y]Kf∈Y. We first show that for all [u]Kf∈[[y]Kf]R1/Kf, [u]Kf∈R1/Kf¯Y. By Lemma 4.11, R1/Kf is symmetric, hence [y]Kf∈[[u]Kf]R1/Kf. Thus, [y]Kf∈[[u]Kf]R1/Kf∩Y≠∅. This implies [u]Kf∈R1/Kf¯Y. Therefore, [[y]Kf]R1/Kf⊆R1/Kf¯Y. It follows that ⋃[y]Kf∈Y[[y]Kf]R1/Kf⊆R1/Kf¯Y.
On the other hand, for all[u]Kf∈R1/Kf¯Y, then [[u]Kf]R1/Kf∩Y≠∅. Hence, there exists [y]Kf∈[[u]Kf]R1/Kf∩Y≠∅ such that [y]Kf∈[[u]Kf]R1/Kf and [y]Kf∈Y. By Lemma 4.11, R1/Kf is symmetric, hence [u]Kf∈[[y]Kf]R1/Kf. Therefore, [u]Kf∈⋃[y]Kf∈Y[[y]Kf]R1/Kf.
It follows thatR1/Kf¯Y⊆⋃[y]Kf∈Y[[y]Kf]R1/Kf.
Thus,R1/Kf¯Y=⋃[y]Kf∈Y[[y]Kf]R1/Kf.An interesting problem is to discuss the isomorphisms of approximation spaces induced by the homomorphisms of approximation spaces. The next theorem shows the very intimate relation between homomorphisms and isomorphisms. The theorem is similar to first isomorphism theorem in group theory.Theorem 4.14.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping from  U1 to  U2,  R1 an equivalence relation on  U1 and  R2 an equivalence relation on  U2. If  f is an epimorphism from  (U1,R1) to  (U2,R2), then  (U1/Kf,R1/Kf)≅(U2,R2).Proof.
For all[x]Kf∈U1/Kf, we define h([x]Kf)=f(x), then by Lemma 4.12, we have that h is a mapping from U1/Kf to U2. Let [x]Kf,[y]Kf∈U1/Kf. If [x]Kf≠[y]Kf, then by Notation 5, we get that f(x)≠f(y). Hence, h([x]Kf)=f(x)≠f(y)=h([y]Kf). We have proved that h is injective. In addition, for all z∈U2, since f is surjective, it follows that there exists x∈U1 such that f(x)=z. Thus for all z∈U2, there exists [x]Kf∈U1/Kf such that h([x]Kf)=f(x)=z. Therefore, h is surjective. It follows that h is a bijective mapping from U1/Kf to U2. By Lemma 4.11, we conclude that R1/Kf is a binary relation on U1/Kf, hence (U1/Kf,R1/Kf) is an approximation space. Since h is a bijective mapping from U1/Kf to U2, it follows from Definition 3.1 and Notation 2 that in order to have (U1/Kf,R1/Kf)≅(U2,R2), we need to prove only that h is a homomorphism from (U1/Kf,R1/Kf) to (U2,R2).
LetY⊆U1/Kf. We shall show that h(R1/Kf̲Y)⊆R2̲h(Y) and h(R1/Kf¯Y)⊆R2¯h(Y). For simplicity, we write(4.4)⋃[y]Kf∈Y[y]Kf=X,
clearly, X⊆U1, and by Lemma 4.12, we have that h(Y)=f(X).
(i) We shall prove that for all[z]Kf∈R1/Kf̲Y, [z]Kf⊆R1̲X. We need to prove only that for all u∈[z]Kf, then u∈R1̲X. By Notation 5, u∈[z]Kf implies [u]Kf=[z]Kf. Let t∈[u]R1, then by the definition of R1/Kf, we have that ([u]Kf,[t]Kf)∈R1/Kf. Hence, ([z]Kf,[t]Kf)=([u]Kf,[t]Kf)∈R1/Kf, that is, ([z]Kf,[t]Kf)∈R1/Kf and so [t]Kf∈[[z]Kf]R1/Kf. We have proved that for all t∈[u]R1, [t]Kf∈[[z]Kf]R1/Kf. Thus, ⋃t∈[u]R1{[t]Kf}⊆[[z]Kf]R1/Kf. In addition, since [z]Kf∈R1/Kf̲Y, it follows that [[z]Kf]R1/Kf⊆Y. Hence, ⋃t∈[u]R1{[t]Kf}⊆Y and so ⋃t∈[u]R1[t]Kf⊆⋃[y]Kf∈Y[y]Kf=X. This implies [u]R1⊆⋃t∈[u]R1[t]Kf⊆X, that is, [u]R1⊆X. Thus u∈R1̲X. It follows that [z]Kf⊆R1̲X.
(ii) We shall prove thath(R1/Kf̲Y)⊆R2̲h(Y). By (i), we have that for all [z]Kf∈R1/Kf̲Y, [z]Kf⊆R1̲X and so for all [z]Kf∈R1/Kf̲Y, f([z]Kf)⊆f(R1̲X). Therefore, by Lemma 4.12, we have that
(4.5)h(R1/Kf̲Y)=f(⋃[z]Kf∈R1/Kf̲Y[z]Kf)=⋃[z]Kf∈R1/Kf̲Yf([z]Kf)⊆⋃[z]Kf∈R1/Kf̲Yf(R1̲X)=f(R1̲X),
that is, h(R1/Kf̲Y)⊆f(R1̲X). In addition, since f is a homomorphism from (U1,R1) to (U2,R2), it follows that f(R1̲X)⊆R2̲f(X). Thus,
(4.6)h(R1/Kf̲Y)⊆f(R1̲X)⊆R2̲f(X)=R2̲h(Y).
We have proved that h(R1/Kf̲Y)⊆R2̲h(Y).
(iii) Let[y]Kf∈Y. We shall prove that for all [u]Kf∈[[y]Kf]R1/Kf, f([u]Kf)⊆f(R1¯X). By the definition of R1/Kf, there exist s∈[y]Kf and t∈[u]Kf such that sR1t. Hence, s∈[t]R1∩[y]Kf≠∅. Since [y]Kf∈Y, it follows that [t]R1∩(⋃[y]Kf∈Y[y]Kf)≠∅, namely, [t]R1∩X≠∅. This implies t∈R1¯X and so f(t)∈f(R1¯X). In addition, since t∈[u]Kf, it follows from Notation 5 that f([u]Kf)={f(t)}. Thus, f([u]Kf)⊆f(R1¯X).
(iv) We shall prove thath(R1/Kf¯Y)⊆R2¯h(Y). By Lemma 4.13, we get that
(4.7)h(R1/Kf¯Y)=h(⋃[y]Kf∈Y[[y]Kf]R1/Kf)=⋃[y]Kf∈Yh([[y]Kf]R1/Kf).
By Lemma 4.12, we have that
(4.8)h([[y]Kf]R1/Kf)=f(⋃[u]Kf∈[[y]Kf]R1/Kf[u]Kf)=⋃[u]Kf∈[[y]Kf]R1/Kff([u]Kf).
Thus, h(R1/Kf¯Y)=⋃[y]Kf∈Yh([[y]Kf]R1/Kf)=⋃[y]Kf∈Y⋃[u]Kf∈[[y]Kf]R1/Kff([u]Kf), that is, h(R1/Kf¯Y)=⋃[y]Kf∈Y⋃[u]Kf∈[[y]Kf]R1/Kff([u]Kf). By (iii), we have that for all [y]Kf∈Y and all [u]Kf∈[[y]Kf]R1/Kf, f([u]Kf)⊆f(R1¯X). Hence,
(4.9)h(R1/Kf¯Y)=⋃[y]Kf∈Y⋃[u]Kf∈[[y]Kf]R1/Kff([u]Kf)⊆⋃[y]Kf∈Y⋃[u]Kf∈[[y]Kf]R1/Kff(R1¯X)=f(R1¯X),
that is, h(R1/Kf¯Y)⊆f(R1¯X). In addition, since f is a homomorphism from (U1,R1) to (U2,R2), it follows from Definition 3.1 that f(R1¯X)⊆R2¯f(X)=R2¯h(Y). Therefore h(R1/Kf¯Y)⊆f(R1¯X)⊆R2¯h(Y), that is, h(R1/Kf¯Y)⊆R2¯h(Y).
(v) By (ii), (iv), and Definition3.1, we conclude that h is a homomorphism (U1/Kf,R1/Kf) to (U2,R2). Since h is bijective, it follows from Definition 3.1 that h is an isomorphism from (U1/Kf,R1/Kf) to (U2,R2). Thus, by Notation 2, we conclude that (U1/Kf,R1/Kf)≅(U2,R2). This completes the proof.In the following, we extend Theorem4.14 to more general cases.Corollary 4.15.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping,  R1 an equivalence relation on  U1, and  R2 an equivalence relation on  U2. If  f is a homomorphism from  (U1,R1) to  (U2,R2), then  (U1/Kf,R1/Kf)≅(f(U1),R2∣f(U1)).Proof.
For allX⊆U1, since f is a homomorphism from (U1,R1) to (U2,R2), it follows from Definition 3.1 that f(R1̲X)⊆R2̲f(X) and f(R1¯X)⊆R2¯f(X). In addition, By Corollary 4.10, we have that (f(U1),R2∣f(U1)) is an approximation subspace of (U2,R2). Since f(X)⊆f(U1), it follows from Definition 4.1 that R2̲f(X)=R2∣f(U1)̲f(X) and R2¯f(X)=R2∣f(U1)¯f(X). Thus f(R1̲X)⊆R2∣f(U1)̲f(X) and f(R1¯X)⊆R2∣f(U1)¯f(X). We have proved that for all X⊆U1, f(R1̲X)⊆R2∣f(U1)̲f(X) and f(R1¯X)⊆R2∣f(U1)¯f(X). Hence, by Definition 3.1, we have that f is a homomorphism from (U1,R1) to (f(U1),R2∣f(U1)). Clearly, f is a surjective mapping from U1 to f(U1); therefore, f is an epimorphism from (U1,R1) to (f(U1),R2∣f(U1)). It follows from Theorem 4.14 that (U1/Kf,R1/Kf)≅(f(U1),R2∣f(U1)).Corollary 4.16.
LetU1 and  U2 be finite and nonempty universes,  f:U1→U2 a mapping,  R1 an equivalence relation on  U1, and  R2 an equivalence relation on  U2. If  f is a homomorphism from  (U1,R1) to  (U2,R2), then  R1/Kf is an equivalence relation on  U1/Kf.Proof.
By Corollary4.15, we have that (U1/Kf,R1/Kf)≅(f(U1),R2∣f(U1)). by Lemma 4.3, we have that R2∣f(U1) is an equivalence relation on f(U1). It follows from Theorem 3.14 that R1/Kf is an equivalence relation on U1/Kf.In fact,R1/Kf may not be an equivalence relation on U1/Kf when f is not a homomorphism from (U1,R1) to (U2,R2). The above results show that R1/Kf is an equivalence relation on U1/Kf when f is a homomorphism from (U1,R1) to (U2,R2).


## 5.  Conclusions

In this paper, we present the notion of the homomorphism of approximation spaces. A homomorphism may be viewed as a special mapping between two approximation spaces. By means of this concept, we establish the relationships between two universes. In this way, one can make inference in one universe, based on information about another universe. In addition, we give the notion of approximation subspaces of approximation spaces, and investigate the properties of approximation subspaces by means of homomorphism. In the future, we will introduce a similar notion of homomorphism into covering-based rough set model in order to deepen understanding of this model.



---

*Source: 185357-2012-05-13.xml*