A Set Theory For Soft Computing

A Unified View of Fuzzy Sets via Neighbrohoods

T. Y. Lin

Department of Mathematics and Computer Science,

San Jose State University, San Jose, California 95192-0103,

and

Berkeley Initiative in Soft Computing,

Department of Electrical Engineering and Computer Science

University of California, Berkeley, California 94720

Abstract

The notion of fuzzy is context dependent, so for each context very often there is a fuzzy theory. Present papers use the notion of neighborhood systems to unify them. A neighborhood system is an association that assigns to each datum a list of data (a neighborhood). Rough sets and topological spaces are special cases. A “real world” fuzzy set should allow small amount of perturbation, so it should have an elastic membership function. Mathematically, such an elastic membership function can be expressed by a highly structured subset of membership function space. Structured sets can be singletons, equivalence classes, neighborhoods, or their fuzzified versions. This paper proposed fuzzy sets should be abstractly defined by such structures and are termed soft sets (sofsets). Based on such structures, W-sofset, F-sofset, P-sofset, B-sofset, C-sofset, N-sofset, FP-sofset, and FF-sofsets have been identified. In this sequence, a predecessor is always a special case of a successor. Each type represents some implicit form of classical fuzzy theory. It is hoped that such a unified view will provide a useful set theory for soft computing. Some applications will be reported in the near future.

1.Introduction

Fuzzy sets have been here for more than three decades [1]. Various theories have been proposed. Each theory, however, is often driven or motivated by some specific applications. Unavoidably applications specific contexts may have been implicitly formulated into these formal theories. In this paper, we attempt to examine mere fuzzy set theory from the point of view of pure mathematics, precise and unmotivated. Our ultimate goal is a unified axiomatic fuzzy set theory. At this moment, however, the goal is far from our reach. Our strategy is not to impose any idea and develop the theory around few very fundamental questions: For example,

Should a membership function be regarded as the (only) characteristic function of a fuzzy set?

Following the strategy we allow both. Fuzzy set whose membership function is the only characteristic function is called weighted soft sets, abbreviated as W-sofsets. W-sofset theory is a new theory of mathematical analysis. Functions are studied from the point of view of new interpretations. Namely, a function value is interpreted as a weight of membership. On the other hand, we believe that ideal membership functions for real world fuzzy sets are made from elastic material, because fuzzy sets should be able to tolerate certain amount of perturbation or stretching. Could elasticity be expressed mathematically? Each perturbation is a new function, so mathematically such an elastic membership function must consist of a set of functions, each of which can be continuously stretched into another function. Such a set of functions is a highly structured subset of membership function space. In [11], we have construct such a subset and show that it is a neighborhood. In this paper, we have decided to take axiomatic approach. We simply define a fuzzy set, called soft set, by an “abstract structured set” of membership function space. Such a structured subset may be an equivalence class, a neighborhood, or fuzzified structures in the membership function space. These sofsets are called W-sofsets, F-sofsets, P-sofsets, R-sofsets, FP-sofsets, and FF-sofsets. The last one is closely related to type one fuzzy sets [18]. Soft sets are intend to capture and to defuse the conflicts among existing fuzzy theories. We hope readers will be convinced that soft set theory is a consistent and unified theory implied implicitly by existing fuzzy theories.

The central notion here is neighborhood systems. It is an abstraction of “near” or “negligible distances” in geometry. A neighborhood system is an association that assigns each datum a list of data that may or may not contain the datum. It is natural and implementable. The concept is the primitive notion for topological spaces [2], implicitly in rough set theory, is explicitly used in modal logic [3], and even is defined in a text on evolutionary computing ([4], pp. 38). Our interested are stemmed from approximate retrieval in databases and approximate reasoning in knowledge bases [5, 6, 7, 8, 9, 10]. For references, we recall that a space that is equipped with a neighborhood system is called Frechet (V) space [2] by topologists.

Finally, we would like to comment that Zadeh’s full agenda is both profound and comprehensive. It fuzzifies not only mathematics, but also its foundation. At this point, however, we will only fuzzify mathematics, but notits foundation. So current and soft mathematics can co-exist and can beused consistently to solve real world problems.

As we have pointed out in RSSC’94 [14,15], the developments of various generalized set theories form a beginning of a "soft mathematics” and may provide a foundation for soft computing. This paper is one of our attempt to provide a solid set theory for soft computing.

2. Membership Function Space

2.1. Neighborhood systems

Neighborhood systemsexpress the semantics of nearby. Let p be an object (or datum) in the universe or space X. A neighborhood, denoted by N(p), or simply N, of p is a non-empty subset (or a list) of X, which may or may not contain the object p. Any subset that contains a neighborhood is a neighborhood. A neighborhood systemof object p, denoted by NS(p), is a non-empty maximal family of neighborhoods of p. A neighborhood systemof X, denoted by NS(X) is the collection of NS (p) for all objects p in X. If a neighborhood system NS(X) that satisfies certain axioms ([17], pp. 56), then X is a topological space. In general, X is a Frechet (V) space [2]. Note that one can interprets a covering of X as a neighborhood system NS(X), by taking all covers of the object p as NS(p). In particular, a partition of X is neighborhood system of X. From this view, rough set theory is a special case of the neighborhood system theory. Main focus of this paper is on neighborhood systems in membership function spaces.

2.2.Fuzzy sets

Fuzzy sets are defined by membership functions. However, to express a “real world” fuzzy sets, intuitively, we need an “elastic” membership function that can tolerate small amount of continuous stretching. Could we express such intuition mathematically? As we have explain in the Introduction that the answer is yes. Each stretch produces a new membership function. So a fuzzy set should be defined by (1) a collection of membership functions, moreover (2) such membership functions should be able to transform among themselves. In [11], Lin explicitly defined and studied such transformations. Though the construction is generic, conceivably there could have many more. So in this paper, we approach the problem, more axiomatically in the sense that we will not refer to any internal specific construction, but to its external properties. A real world fuzzy set is defined abstractly by a neighborhood systems of membership function space. Our goal is to understand real world fuzzy set, neighborhood systems translate the real world problem into a mathematical problem. So our ultimate goal is to axiomatize fuzzy sets through such neighborhood systems.

2.3. Membership function space

Membership function space will be the focal point of our discussion. To avoid monotonous, we will use terms, such as, space, family, and collection as synonym of crispy set. A space often refers to a very large set; a collection or a family often refers to a set of sets. Let U be the universe of discourse, and let

FX : U  M

be a map, where M is, in general, a membership space [18]. FX is called a membership function; FX(x) is called the grade or degree of membership of x  U. If M is the set of two elements {0, 1}, then FX is the characteristic function of a classical crispy set. If M is a unit interval, then FX is the membership function of a classical fuzzy set. We will focus on classical fuzzy sets. From now onM will be the unit interval [0, 1].

Let F be a collection of fuzzy sets on U. Each fuzzy set is defined by a neighborhood (may be a singleton) in the membership function space; let Col be a neighborhood system. Let MF(U) be the total space of membership functions under consideration, i.e.. MF(U) is the total union of all membership functions representing F, namely the union of members in Col:

MF(U) = Col

Col is a neighborhood system on MF(U).

3. A Taxonomy For Soft Sets (Sofset)

Depending on the nature of Col, we have various types of fuzzy sets. To avoid confusing, we will call the fuzzy sets defined by Col soft sets (or sofset). Here is a list of soft sets. A soft set will be called a

(1)W-sofset: Weighted Soft Set (Mathematical Soft Set or Quantitative Soft Set), if Colconsists of singletons. Every membership function is treated as a characteristic function of a soft set. Many classical fuzzy theorists have implicitly taken this view. For clarity, when we refer their works, we will use, in stead of fuzzy set, weighted soft set, also we will say each element in a soft set has a weight(instead of grade). M-soft set theory is essentially a “new” mathematical analysis of real variables where one studies functions from the point of view of weighted memberships.

(2) F-Sofset: Finite-multi Soft Set, if Col consists of finite sets. See Section 5.2 for more details.

(3) P-Sofset: Partitioned Soft Set, if Colforms a crispy partition. This is mathematically a most beautiful theory. Realizing that a fuzzy set (that tolerates perturbation) has to be represented by a set of membership functions. Each set represents one and only one fuzzy set. Then the space of membership functions is partitioned into equivalence classes. So P-sofset theory is very elegant and beautiful. However, one may wander how could there be a natural partition in a “continuous” membership function space. This lead us to a more general point of view, namely, the next few items.

(4) B-Sofset: Basic Neighborhood Soft Set, if Colforms a basic neighborhood system (i.e., the neighborhood system is defined by a binary relation). Basic neighborhoods are geometric view of binary relation. Intuitively, related membership functions are “geometrically” near to each other. A basic neighborhood system is an abstract binary relation, so it may include some “unexpected” cases. To illustrate, let consider the following measure theoretical (probabilistic) example. Two membership functions are measure theoretical near, if their difference are “small.” In other words, two membership functions, FX and GX, (for the same soft set X) are measure theoretical near, if for any given  > 0,

|| FX(x) - GX(x)|| < 

where || .. || = (sup x | FX(x) - GX(x)|)/(U), sup x is the supremum (taking through all the point x in the universe), and (U) is the total measure of the universe. In a finite universe, (1) a commonly used measure is the counting measure, so (U) is the cardinal number of the universe U, and (2) one often replace sup x by summation x [22].

(5) C-Sofset: Covering Soft Set, if Colforms a covering.

(6) N-Sofset: Neighborhood Soft Set (Real World Soft Set or Qualitative Soft Set), if Col forms a neighborhood system. This is most general case in this discussion. It includes (4) and (5) as special case.

Note that the types of soft sets defined above in cases (1), (2), (3), (4), and (6) form an increasing sequence (of generality), namely, (i) is a special case of (j), if i < j. (4) and (5) are incomparable, and both are special case of (6).

Further, we will consider briefly the case that Col is a family of weighted sofset (i.e., “classical” fuzzy sets). We will leave the details in next paper, we just briefly mention two interesting cases:

(7) FP-Sofset: Fuzzy-Partitioned Soft Sets, if Col forms a fuzzy (weighted) partition.

(8) FF-Softset: Double Fuzzy Soft Sets, if Col forms a fuzzy (weighted) covering.

In literature, there are two generalizations on crispy partition [2], [19, pp. 216]:

(1)Col is called a fuzzy partition, if =1, where the sum is over all FX Col [2].

(2)Col is called a fuzzy partition, if

inf x Max {FX(x)} > 0

sup x Min {FX(x), FY(x)} < 1,  FX and FY Col

(3) Col is called a fuzzy covering, if > 0, where the sum is over all FX Col.

To motivate readers properly, we will center around few fundamental questions [11].

4. Is A Membership Function Adequate for A Fuzzy Set?

4.1. Conflicting views

The intuitive notion of fuzzy sets may be different for each individual author:

View 1: Some authors, e.g., Negoita and Ralescu believe that a fuzzy set is defined by one and only one membership functions ([18], pp. 12).

View 2: Others, e.g., Kandel believe a fuzzy set could have several membership functions ([16], pp. 4).

4.2. Implicit positive answer W-sofset

W-sofset is the case for positive answer (to the title of this subsection). Algebraic results in the literature are often based on an implicit assumption that a fuzzy set has one and only one membership function. For example, let us consider the set operation “union.” Let

FK: U  [0, 1],

GK: U  [0, 1]

be two membership functions that represent the same fuzzy set K (denoted by FK  GK.). Likewise,

FH: U  [0, 1],

GH: U  [0, 1]

represent the same fuzzy set H (denoted by FH  GH.) Then we have two “union membership functions”

FZ = s(FK, FH)

GZ = s(GK, GH)

where s is any s-norm. Now if the “union” Z = H  K does exist, we must be able to show that “two” unions,

FZ ?? GZ.

are indeed equal. In other words, we have to show that “ ?? ” is indeed “”. However, no contemporary authors have attempted to validate such equality ” . “ So we conclude that they must have implicitly assumed a fuzzy set is defined by one and only membership function. Observing that in the arguments above, we have not chosen t- or s-norm explicitly. So conlusion are valid for any binary operation. So,

any algebraic operations, such as s- and t-norms are W-sofset operations only; they may not be legitimate for other sofsets.

4.3. Serious implications from positive answer

Dofuzzy numbers exist ?

One has to be quite cautious here, for example, the theory of fuzzy real number may no longer valid in this context, namely, W-softsets. Note that since we have only one membership function for each fuzzy number, we have to select membership functions so carefully that they are closed under extended operations ([18 ], pp. 57). Such a selection is not obvious: Can one find a membership function of fuzzy number, say 2, such that it satisfies follwoing equalities ?

2 = 1+1= 2/1 = 4/2 = 6/3 = ....

One possible way is to define (1) fuzzy integers first, then use them to construct (2) fuzzy real numbers; we will study this in next paper. For fuzzy integers we can proceed as follows:

Step 1: Select a membership function for each prime integer. They are prime fuzzy integers.

Step 2: Fuzzy integer is the extended product of prime fuzzy integers.

5. Do fuzzy set theoretical operations exit?

5.1. t-/s-norms may not relate to logic connective

In last section, we have shown that the fuzzy set operations defined in the literature are valid for W-sofsets only (may be invalid for other types of sofsets). Moreover, we would like to point out, however, that contrary to the common belief, our study shows that fuzzy set operationsmay not exist in the same sense as classical set theory. In other words, such set operations are not derived or related to logical connective of fuzzy propositions [20].

As W-sofsets are uniquely identified with their membership functions, intrinsically, the theory of W-sofsets is merely a new function theory of real variables in mathematics.

5.2 New types of fuzzy set operations - F-Sofsets

The motivation of introducing F-sofsets is derived from our analysis of fuzzy set theoretical operations.All crispy set operations are associated to logical connective of propositions naturally. However, we found that s- and t-norm operations (including min and max) have no natural or obvious associations with logical connective of fuzzy propositions (in the domain of the “intuitive fuzzy logic” of daily life) [20]. We believe that classical fuzzy set theoretical operations, such as s- and t-norms, are driven by analogy, not by the nature of “intuitive fuzzy logic”. So we set forth to search for “other natural” fuzzy set theoretical operations.

In classical modal logic, one associates naturally a proposition with a characteristic function (of crispy set); we will call it crispy association. By extending the truth values to real values, we can also associate each fuzzy proposition with a membership function; we will call it fuzzy association [19]. A natural question is: Does this new association enjoy the same beautiful properties as the crispy one? In crispy case, the association relates logic connective to set operations. Do we have the same for fuzzy association?

Our analysis indicates that the fuzzy association is syntactically rather mysterious. The existence of various t- and s-norms indicates that they have no natural association to fuzzy logic connective. In [20], we have given several examples from common sense that the “naive” association may not exist. However, the association indeed does exist in slightly different level. It is on the level of finite collections:

(1) A primitive proposition associates a primitive fuzzy set (an object specified by a membership function).

(2) A finite collection of fuzzy propositions (regarded as a conjunction) associates a fuzzy set of new type (an object specified by a finite collection of membership functions).

The “new type of fuzzy sets” is precisely F-sofset, where conjunction, inference, and disjunction of F-sofsets can be interpreted by logical connective in “intuitive fuzzy logic” of daily life. In [20], F-sofsets are called complex fuzzy sets. From database prospect, F-sofsets have a nice interpretation: Context free fuzzy sets are databases, F-sofsets are base relations, and inferences are Armstrong inferences, and etc.. Our research in this direction is still in work in progress.

6. Could a membership function represent several fuzzy sets ?

We believe it does, nevertheless, we will consider all possible answers.

6.1. Negative answer P-Sof sets

So a membership function can represent at most one fuzzy set. So the space MF(U) of membership functions is partitioned into equivalence classes. Each equivalence class represents one and only one fuzzy set. Such fuzzy sets are P-sofsets. Mathematically, this view is the most elegant one. Unfortunately, it may not be realistic. One will realize, however after a moment of reflection, that MF(U) may be a “continuous” family of real valued functions. Very unlikely there is a natural partition on such MF(U)’s. We are forced to accept more general and realistic view. Of course, there are situations in which MF(U) has very natural partitions. Rough-fuzzy logic controllers often work in such environments [21, 22].

6.2. Positive answer“Serious” implications
N-sofsets

Ideally, as we have explained in the Introduction that a real world fuzzy set should be defined by an elastic membership function. Mathematically, one can express such an elastic membership function by a set of membership functions that are very “near” to each other. In other words, they belong to the same neighborhood. In general, Col is a neighborhood system, not a crispy partition. Overlapping does occur in neighborhoods. So a membership function could lie in two neighborhoods. In other words, a membership function may represent two fuzzy sets. Such fuzzy sets are N-sofsets. There are two types of sub-sofsets: (1) B-sofsets: Col is defined by a binary relation (geometrically, a basic neighborhood system). (2) B-sofsets: Col is defined by a covering.