Klir G.J. Uncertainity and Information. Foundations of Generalized Information Theory

Подождите немного. Документ загружается.

of these propositions is expressed symbolically by a slash crossing the opera-

tor.That is x œ A, A À B, and A π B represent, respectively, x is not an element

of A, A is not a proper subset of B, and A is not equal to B.

The family of all subsets of a given set A is called the power set of A, and

it is usually denoted by P(A). The family of all subsets of P(A) is called a

second-order power set of A; it is denoted by P

(A), which stands for P(P(A)).

Similarly, higher-order power sets P

(A), P

(A),...can be deﬁned.

For any ﬁnite universal set, it is convenient to deﬁne its various subsets by

their characteristic functions arranged in a tabular form, as shown in Table 1.1

for X = {x

, x

}. In this case, each set, A, of X is deﬁned by a triple ·c

), c

)Ò. The order of these triples in the table is not signiﬁcant, but it

is useful for discussing typical examples in this book to list subsets containing

one element ﬁrst, followed by subsets containing two elements and so on.

The intersection of sets A and B is a new set, A « B, that contains every

object that is simultaneously an element of both the set A and the set B.IfA

= {1, 3, 5, 7, 9} and B = {1, 2, 3, 4, 5}, then A « B = {1, 3, 5}. The union of sets A

and B is a new set, A » B, which contains all the elements that are in set A or

in set B. With the sets A and B deﬁned previously, A » B = {1, 2, 3, 4, 5, 7, 9}.

The complement of a set A, denoted A

, is the set of all elements of the uni-

versal set that are not elements of A. With A = {1, 3, 5, 7, 9} and the universal

set X = {1, 2, 3, 4, 5, 6, 7, 8, 9}, the complement of A is A

= {2, 4, 6, 8}. A related

set operation is the set difference, A - B, which is deﬁned as the set of all ele-

ments of A that are not elements of B. With A and B as deﬁned previously, A

- B = {7, 9} and B - A = {2, 4}. The complement of A is equivalent to X - A.

All the concepts of set theory can be recast in terms of the characteristic

functions of the sets involved. For example we have that A Õ B if and only if

(x) £ c

(x) for all x ŒX. Similarly,

The phrase “for all” occurs so often in set theory that a special symbol, ",

is used as an abbreviation. Similarly, the phrase “there exists” is abbreviated

ccc

AB A B

xxx

()

() ()

{}

()

() ()

{}

min , ,

max , .

12 1. INTRODUCTION

Table 1.1. Deﬁnition of All Subsets, A, of Set X = {x

, x

} by Their Characteristic Functions

A:0 0 0

10 0

01 0

00 1

11 0

10 1

01 1

11 1

as $. For example, the deﬁnition of set equality can be restated as A = B if and

only if c

(x) = c

(x), "x ŒX.

The size of a ﬁnite set, called its cardinality, is the number of elements it

contains. If A = {1, 3, 5, 7, 9}, then the cardinality of A, denoted by |A|, is 5. A

set may be empty, that is, it may contain no elements. The empty set is given a

special symbol ∆; thus ∆={} and |∆| = 0. When A is ﬁnite, then

The most fundamental properties of the set operations of absolute com-

plement, union, and intersection are summarized in Table 1.2, where sets A,

B, and C are assumed to be elements of the power set P(X) of a universal set

X. Note that all the equations in this table that involve the set union and inter-

section are arranged in pairs.The second equation in each pair can be obtained

from the ﬁrst by replacing ∆, », and « with X, «, and », respectively, and vice

versa.These pairs of equations exemplify a general principle of duality: for each

valid equation in set theory that is based on the union and intersection oper-

ations, there is a corresponding dual equation, also valid, that is obtained by

the replacement just speciﬁed.

Any two sets that have no common members are called disjoint. That is,

every pair of disjoint sets, A and B, satisﬁes the equation

AB«=Ø.

PPAA

()

=22

,,. etc

1.4. RELEVANT TERMINOLOGY AND NOTATION 13

Table 1.2. Fundamental Properties of Set Operations

Involution A

= A

Commutativity A » B = B » A

A « B = B « A

Associativity (A » B) » C = A » (B » C)

(A « B) « C = A « (B « C)

Distributivity A « (B » C) = (A « B) » (A « C)

A » (B « C) = (A » B) « (A » C)

Idempotence A » A = A

A « A = A

Absorption A » (A « B) = A

A « (A » B) = A

Absorption by X and ⭋ A » X = X

A « ⭋ = ⭋

Identity A » ⭋ = A

A « X = A

Law of contradiction A « A

= ⭋

Law of excluded middle A » A

= X

De Morgan’s laws

ABAB

A family of pairwise disjoint nonempty subsets of a set A is called a partition

on A if the union of these subsets yields the original set A. A partition on A

is usually denoted by the symbol p(A). Formally,

is a partition on A iff (i.e., if and only if)

for each pair i, j ŒI, i π j, and

Members of p(A), which are subsets of A, are usually referred to as blocks of

the partition. Each member of A belongs to one and only one block of p(A).

Given two partitions p

(A) and p

(A), we say that p

(A) is a reﬁnement of

(A) iff each block of p

(A) is included in some block of p

(A). The reﬁne-

ment relation on the set of all partitions of A, P(A), which is denoted by £

(i.e., p

(A) £ p

(A) in our case), is a partial ordering. The pair ·P(A), £Òis a

lattice, referred to as the partition lattice of A.

Let A = {A

, A

,...,A

} be a family of sets such that

Then, A is called a nested family, and the sets A

and A

are called the inner-

most set and the outermost set, respectively. This deﬁnition can easily be

extended to inﬁnite families.

The ordered pair formed by two objects x and y, where x ŒX and y ŒY,is

denoted by ·x, yÒ. The set of all ordered pairs, where the ﬁrst element is con-

tained in a set X and the second element is contained in a set Y, is called a

Cartesian product of X and Y and is denoted as X ¥ Y. If, for example, X = {1,

2} and Y = {a, b}, then X ¥ Y = {·1, aÒ, ·1, bÒ, ·2, aÒ, ·2, bÒ}. Note that the size of

X ¥ Y is the product of the size of X and the size of Y when X and Y are ﬁnite:

|X ¥ Y|=|X|·|Y|. It is not required that the Cartesian product be deﬁned on

distinct sets. A Cartesian product X ¥ X is perfectly meaningful. The symbol

is often used instead of X ¥ X. If, for example, X = {0, 1}, then X

= {·0, 0Ò,

·0, 1Ò, ·1, 0Ò, ·1, 1Ò}. Any subset of X ¥ Y is called a binary relation.

Several important properties are deﬁned for binary relations R Õ X

. They

are: R is reﬂexive iff ·x, xÒŒR for all x ŒX; R is symmetric iff for every

·x, yÒŒR it is also ·y, xÒŒR;R is antisymmetric iff ·x, yÒŒR and ·y,xÒŒR implies

x = y; R is transitive iff ·x, yÒŒR and ·y, zÒŒR implies ·x, zÒŒR. Relations that

are reﬂexive, symmetric, and transitive are called equivalence relations. Rela-

tions that are reﬂexive and symmetric are called compatibility relations. Rela-

AA i n

Õ=-

12 1for all , , ..., .

«πØ

p AAiIAAA

iii

()

=ŒÕπ

{}

,, Ø

14 1. INTRODUCTION

tions that are reﬂexive, antisymmetric, and transitive are called partial order-

ings. When R is a partial ordering and ·x,yÒŒR, it is common to write x £ y

and say that x precedes y or, alternatively, that x is smaller than or equal to y.

A partial ordering £ on X does not guarantee that all pairs of elements x,

y in X are comparable in the sense that either x £ y or y £ x. If all pairs of ele-

ments are comparable, the partial ordering becomes total ordering (or linear

ordering).Such an ordering is characterized by—in addition to reﬂexivity, tran-

sitivity, and antisymmetry—a property of connectivity: for all x, y ŒX, x π y

implies either x £ y or y £ x.

Let X be a set on which a partial ordering is deﬁned and let A be a subset

of X. If x ŒX and x £ y for every y ŒA, then x is called a lower bound of A on

X with respect to the partial ordering. If x ŒX and y £ x for every y ŒA, then

x is called an upper bound of A on X with respect to the partial ordering. If a

particular lower bound of A succeeds (is greater than) any lower bound of A,

then it is called the greatest lower bound,or inﬁmum, of A. If a particular upper

bound precedes (is smaller than) every other upper bound of A, then it is

called the least upper bound, or supremum, of A.

A partially ordered set X any two elements of which have a greatest lower

bound (also referred to as a meet) and a least upper bound (also referred to

as a join) is called a lattice. The meet and join elements of x and y in X are

often denoted by x Ÿ y and x ⁄ y, respectively. Any lattice on X can thus be

deﬁned not only by the pair ·X, £Ò, where £ is an appropriate partial ordering

of X, but also by the triple ·X, Ÿ, ⁄Ò, where Ÿ and ⁄ denote the operations of

meet and join.

A partially ordered set, any two elements of which have only a greatest

lower bound, is called a lower semilattice or meet semilattice. A partially

ordered set, any two elements of which have only a least upper bound, is called

an upper semilattice or join semilattice.

Elements of the power set P(X) of a universal set X (or any subset of X)

can be ordered by the set inclusion Õ. This ordering, which is only partial,

forms a lattice in which the join (least upper bound, supremum) and meet

(greatest lower bound, inﬁmum) of any pair of sets A, B ŒP(X) is given by A

» B and A « B, respectively. This lattice is distributive (due to the distributive

properties of » and « listed in Table 1.2) and complemented (since each set

in P(X) has its complement in P(X)); it is usually called a Boolean lattice

or a Boolean algebra. The connection between the two formulations of

this important lattice, ·P(X), ÕÒ and ·P(X), », «Ò, is facilitated by the

equivalence

where “iff” is a common abbreviation of the phrase “if and only if” or its alter-

native “is equivalent to.” This convenient abbreviation is used throughout this

book.

AB AB B AB A AB XÕ»= «= Œ

()

iff and for any , ,P

1.4. RELEVANT TERMINOLOGY AND NOTATION 15

If R Õ X ¥ Y, then we call R a binary relation between X and Y. If

·x, yÒŒR, then we also write R(x, y) or xRy to signify that x is related to y by

R. The inverse of a binary relation R on X ¥ Y, which is denoted by R

-1

, is a

binary relation on Y ¥ X such that

For any pair of binary relations R Õ X ¥ Y and Q Õ Y ¥ Z, the composition

of R and Q, denoted by R

Q, is a binary relation on X ¥ Z deﬁned by the

formula

If a binary relation on X ¥ Y is such that each element x ŒX is related to

exactly one element of y ŒY, the relation is called a function, and it is usually

denoted by a lowercase letter. Given a function f, this unique assignment

of one particular element y ŒY to each element x ŒX is often expressed as

f(x) = y. Set X is called a domain of f and Y is called its range. The domain

and range of function f are usually speciﬁed in the form f: X Æ Y; the arrow

indicates that function f maps elements of set X to elements of set Y; f is called

a completely speciﬁed function iff each element x ŒX is included in at least one

pair ·x, y = f(x)Ò and it is called an onto function iff each element y ŒY is

included in at least one pair ·x, y = f(x)Ò. If the domain of a function (and pos-

sibly also its range) is a set of functions, then it is common to call such a func-

tion a functional.

The inverse of a function f is another function, f

-1

, which maps elements of

set Y to disjoint subsets of set X. If f is a completely speciﬁed and onto func-

tion, then f

-1

maps elements of set Y to blocks of the unique partition, p

(X),

that is induced on the set X by function f. This partition consists of |Y| subsets

of X,

where

for each y ŒY. Function f

-1

thus has the form

and is deﬁned by the assignment f

-1

(y) = X

for each y ŒY.

The notion of a Cartesian product is not restricted to ordered pairs. It may

involve ordered n-tuples for any n ≥ 2. An n-dimensional Cartesian product

for some particular n is the set of all ordered n-tuples that can be formed from

fY X

()

: p

XxXfxy

=Œ

()

{}

XXyY

()

=Œ

{}

RQ xz xy R yz Q yo =ŒŒ

{}

,, , . and for some

yx R xy R,,.ŒŒ

-1

iff

16 1. INTRODUCTION

the designated sets in a manner analogous to forming ordered pairs of a 2-

dimensional Cartesian product. When the n-tuples are formed from a single

set, say, set X, then the n-dimensional Cartesian product is usually denoted by

the symbol X

. For example, if X = {0, 1}, then X

= {·0, 0, 0Ò, ·0, 0, 1Ò, ·0, 1, 0Ò,

·0, 1, 1Ò, ·1, 0, 0Ò, ·1, 0, 1Ò, ·1, 1, 0Ò, ·1, 1, 1Ò}. Any subset of a given n-dimensional

Cartesian product is called an n-dimensional relation.

Several important concepts are associated with n-dimensional relations for

any ﬁnite n ≥ 2. For the sake of simplicity, let us deﬁne them in terms of a

ternary relation R Õ X ¥ Y ¥ Z. Generalizations to n > 3 are obvious. A pro-

jection of R into one of its dimensions, say, dimension X, is the set

The symbol [R Ø X] indicates that R is projected into dimension X. Pro-

jections [R Ø Y] and [R Ø Z] are deﬁned in a similar way. A projection of R

into two of its dimensions, say, X ¥ Y, is the set

Projections [R Ø X ¥ Z] and [R Ø Y ¥ Z] are deﬁned in a similar way.

A cylindric extension of projection [R Ø X] of a ternary relation R Õ X ¥ Y

¥ Z with respect to Y ¥ Z is the set

Similarly, a cylindric extension of projection [R Ø X ¥ Y] with respect to dimen-

sion Z is the set

The intersection of cylindric extensions of any given set P of projections of

relation R is called a cylindric closure of R with respect to projections in P.

For any pair of binary relations R Õ X ¥ Y and Q Õ Y ¥ Z, the join of R

and Q, denoted by R

Q, is a ternary relation on X ¥ Y ¥ Z deﬁned by the

formula

Observe that

Important subsets of ⺢ are intervals of real numbers. Four types of inter-

vals of real numbers between a and b are distinguished: Closed intervals,[a,

b], which contain the endpoints a and b; open intervals,(a, b), which do not

RQ RQ X Zo =Ø¥

[]

R Q xyz X Y Z xy R yz Q

,, , , .=Œ¥¥Œ Œ

{}

and

R X Y Z xyz X Y Z xy X YØ¥

[]

≠

()

=Œ¥¥Œ¥

{}

,, , .

RX YZ xyz XYZx RXØ

[]

≠¥

()

=Œ¥¥ŒØ

[]

{}

,, .

RXY xy XY xyz R zZØ¥

[]

=Œ¥ Œ Œ

{}

,,, . for some

RX x X xyz R yz YZØ

[]

=Œ Œ Œ¥

{}

,, , . for some

1.4. RELEVANT TERMINOLOGY AND NOTATION 17

contain the endpoints; semiopen intervals,(a, b] (left-open interval) and [b, a)

(right-open interval), which do not contain the left-end point and the right-

end point, respectively.

An important and frequently used universal set is the set of all points in n-

dimensional Euclidean vector space ⺢

for some n ≥ 1 (i.e., all n-tuples of real

numbers). Sets deﬁned in terms of ⺢

are often required to possess a property

referred to as convexity. A subset A of ⺢

is called convex iff, for every pair

of points

in A and every real number l Œ[0, 1], the point

is also in A. In other words, a subset A of ⺢

is convex iff, for every pair of

points r and s in A, all points located on the straight-line segment connecting

r and s are also in A.

In ⺢, any set deﬁned by a single interval of real numbers is convex; any set

deﬁned by more than one interval that does not contain some points between

the intervals is not convex. For example, the set A = [0, 2] » [3, 5] is not convex,

as can be shown by producing one of an inﬁnite number of possible coun-

terexamples: let r = 1, s = 4, and l = 0.4; then, lr + (1 - l)s = 2.8 and 2.8 œ A.

Let R denote any set of real numbers (i.e., R Õ ⺢). If there is a real number

r (or a real number s) such that x £ r (or x ≥ s, respectively) for every x ŒR,

then r is called an upper bound of R (or a lower bound of R), and we say that

R is bounded above by r (or bounded below by s).

For any set of real numbers R that is bounded above, a real number r is

called the supremum of R iff:

(a) r is an upper bound of R.

(b) No number less than r is an upper bound of R.

If r is the supremum of R, we write r = sup R. If R has a maximum, then sup

R = max R. For example, sup(0, 1) = sup[0, 1] = 1, but only max[0, 1] = 1;

maximum of the open interval (0, 1) does not exist.

For any set of real numbers R that is bounded below, a real number s is

called the inﬁmum of R iff:

(a) s is a lower bound of R.

(b) No number greater than s is a lower bound of R.

If s is the inﬁmum of R, we write s = inf R. If R has a minimum, then

inf R = min R.

t =+-

()

Œllrsi

iin

1 ⺞

rs=Œ = Œri si

in in

⺞⺞and

18 1. INTRODUCTION

Classical sets must satisfy two basic requirements. First, members of each

set must be distinguishable from one another; and second, for any given set

and any given object, it must be possible to determine whether the object is,

or is not, a member of the set.

Fuzzy sets, which play an important role in GIT, differ from classical sets

by rejecting the second requirement. Contrary to classical sets, fuzzy sets are

not required to have sharp boundaries that distinguish their members from

other objects. The membership in a fuzzy set is not a matter of afﬁrmation or

denial, as it is in a classical set, but a matter of degree.

Due to their sharp boundaries, classical sets are usually referred to in fuzzy

literature as crisp sets. This convenient and well-established term is adopted

in this book. Also adopted is the usual notation, according to which both crisp

and fuzzy sets are denoted by capital letters. This is justiﬁed by the fact that

crisp sets are special (degenerate) fuzzy sets.

Each fuzzy set is deﬁned in terms of a relevant crisp universal set by a

function analogous to the characteristic function of crisp sets. This function

is called a membership function. As explained in Chapter 7, the form of this

function depends on the type of fuzzy set that is deﬁned by it. For the

most common fuzzy sets, referred to as standard fuzzy sets, the member-

ship function used for deﬁning a fuzzy set A on a given universal set X

assigns to each element x of X a real number in the unit interval [0, 1].

This number is interpreted as the degree of membership of x in A. When only

the extreme values, 0 and 1, are assigned to each x ŒX, the membership

function becomes formally equivalent to a characteristic function that deﬁnes

a crisp set. However, there is subtle conceptual difference between the

two functions. Contrary to the symbolic role of the numbers in characteris-

tic functions of crisp sets, numbers assigned to objects by membership

functions of standard fuzzy sets clearly have a numerical signiﬁcance. This

signiﬁcance is preserved when crisp sets are viewed (from the standpoint

of fuzzy set theory) as special fuzzy sets. For example, when we calculate an

average of two or more membership functions, we obtain a membership

function that deﬁnes a meaningful standard fuzzy set. On the other hand,

an average of two or more characteristic functions is not a meaningful

characteristic function.

Two distinct notations are most commonly employed in the literature to

denote membership functions. In one of them, the membership function of a

fuzzy set A is denoted by m

, and its form for standard fuzzy sets is

For each x ŒX, the value m

(x) is the degree of membership of x in A. In the

second notation, the membership function is denoted by A and, of course, has

the same form

AX:,.Æ

[]

X:,.Æ

[]

1.4. RELEVANT TERMINOLOGY AND NOTATION 19

Clearly, A(x) is again the degree of membership of x in A.

According to the ﬁrst notation, the symbol of the fuzzy set is distinguished

from the symbol of its membership function. According to the second nota-

tion, this distinction is not made, but no ambiguity results from this double use

of the same symbol, since each fuzzy set is uniquely deﬁned by one particular

membership function. In this book, the second notation is adopted; it is

simpler, and, by and large, more popular in the current literature on fuzzy set

theory. Since crisp sets are viewed from the standpoint of fuzzy set theory as

special fuzzy sets, the same notation is used for them.

By exploiting degrees of membership, fuzzy sets are capable of expressing

gradual transitions from membership to nonmembership. This expressive

capability has wide utility. For example, it allows us to capture, at least in a

crude way, meanings of expressions in natural language, most of which are

inherently vague. Membership degrees in these fuzzy sets express compatibil-

ities of relevant objects with the linguistic expression that the sets attempt to

capture. Crisp sets are hopelessly inadequate for this purpose.

Consider the four membership functions whose graphs are shown in Figure

1.4.These functions are deﬁned on the set of nonnegative real numbers. Func-

tions A and B deﬁne crisp sets, which are viewed here (from the fuzzy set per-

spective) as special fuzzy sets. Set A consists of a single object, the number 3;

set B consists of all real numbers in the closed interval [2, 4]. Functions C and

D deﬁne genuine fuzzy sets. Set C captures (in appropriate context) linguistic

expressions such as around 3, close to 3, or approximately 3. It may thus be

viewed as a fuzzy number. Similarly, fuzzy set D may be viewed as a fuzzy

interval.

Observe that the crisp set B in Figure 1.4 also consists of numbers that are

around 3. However, the sharp boundaries of the set are at odds with the vague

term around. The meaning of the term is certainly not captured, for example,

by excluding the number 1.999999 while including the number 2. The abrupt

transitions from membership to nonmembership make crisp sets virtually

unusable for capturing meanings of linguistic terms of natural language.

To explain the role of fuzzy set theory in GIT, an overview of its funda-

mentals is presented in Chapter 7.

1.5. AN OUTLINE OF THE BOOK

The objective of this book is to survey the current level of development of

GIT. The material, which is presented in a textbook-like manner, is organized

in the following way.

After setting the stage in this introductory chapter, the actual survey begins

with overviews of the two classical uncertainty theories. These are theories

based on the notion of possibility (Chapter 2) and the notion of probability

(Chapter 3). Due to extensive coverage of these theories in the literature,

especially the one based on probability, only the most fundamental features

20 1. INTRODUCTION

of these theories are covered. However, Notes in the two chapters guide the

reader through the literature dealing with these classical uncertainty theories.

The next part of the book (Chapters 4–6) is oriented toward introducing

some generalizations of the classical probability-based uncertainty theory.

These generalizations are obtained by replacing the additivity requirement of

probability measures with the weaker requirement of monotonicity of monot-

one measures, but they are still formalized within the language of classical set

theory. These theories may be viewed as theories of imprecise probabilities of

various types.While the focus in Chapter 4 is on common properties of uncer-

tainty functions in all these theories, Chapter 5 is concerned with distinctive

properties of the individual theories. Covered are only theories that had been

well developed when this book was written. Functionals for measuring uncer-

tainty in the introduced theories are examined in Chapter 6. These function-

1.5. AN OUTLINE OF THE BOOK 21

A(x)

•

35x

•

35x

•

35x

Figure 1.4. Examples of membership functions of fuzzy sets.