4.5. Operations and Quotient Structures
There is a variety of operations defined on a domain. In fact, an operation implicitly defines an interrelationship among elements of the domain. Under different grain-size worlds, the following issues should be answered. The induction of a corresponding operation on a quotient space from an operation defined on its original space, and the synthesis of two operations defined on different grain-size spaces becomes a new operation on their synthetic space, i.e. a finer space.
Let us consider two simple examples.
Example 4.10
is a set of non-negative integers, 
is a quotient set of X denoted by 
, where 
.Let ‘+’ be a common addition operation on X. Define an operation on 
as follows.
as follows.
Let 
be a natural projection.
be a natural projection.Obviously, for 
, we have 
.
, we have .It implies that the projection of the sum ‘+’ of any two elements x and y on X is identical to the sum ‘
’ of the projections of these two elements on 
. Projection p with the preceding property is called a ‘homomorphism transform’ from 
. Operation ‘
’ can be regarded as an induced addition operation on 
from the addition operation ‘+’ on X.
’ of the projections of these two elements on . Projection p with the preceding property is called a ‘homomorphism transform’ from . Operation ‘’ can be regarded as an induced addition operation on from the addition operation ‘+’ on X.Unfortunately, there is not such an induced operation for many operations in general.
Example 4.11
is a one-dimensional Euclidean space, 
is a quotient space of X, where 
.Now we discuss operation ‘+’ on X. We show there does not have any induced operation ‘
’ on 
such that projection 
is homomorphic.
’ on such that projection is homomorphic.Proof
By reduction to absurdity, otherwise assume there is an induced operation 
on X1.
on X1.By taking 
and 
, from the homomorphism property of p we have
and , from the homomorphism property of p we have
If taking 
and 
, then we have
and , then we have
This is a contradiction, and hence there does not have to be any induced operation such that p is homomorphic.
However, in what conditions does a homomorphic-induced operation exist? In modem algebra, for some structures such as groups there are some related results. A result is given below as an example.
Example 4.12
X is a group, 
is a normal sub-group of X. Let 
be a quotient group of X with respect to 
. An induced operation is defined on 
as follows.
is a normal sub-group of X. Let be a quotient group of X with respect to . An induced operation is defined on as follows.
If p is a 
projection, then p is a homomorphism transformation.
projection, then p is a homomorphism transformation.From the example, it is known that only under certain conditions can an operation with homomorphism property on a quotient space be induced.
Assume that N is an operation on X and 
is a quotient space of X. If there exists an operation 
on 
such that 
is a homomorphism projection, then 
is said to be a quotient operation on 
with respect to N, or simply a quotient operation.
is a quotient space of X. If there exists an operation on such that is a homomorphism projection, then is said to be a quotient operation on with respect to N, or simply a quotient operation.As mentioned before, generally, there is not a quotient operation on a quotient space. Similar to semi-order discussed in Chapter 1, we can adjust the quotient space by merging and refining approaches such that a corresponding quotient operation exists.
4.5.1. The Existence of Quotient Operations
X is a domain. 
is the coarsest quotient space of X, namely, a quotient space regarding all elements of X as an equivalence class.
is the coarsest quotient space of X, namely, a quotient space regarding all elements of X as an equivalence class.Assume that N is a binary-operation on X, namely
Given a quotient space 
of X, obviously, we have 
.
of X, obviously, we have .It is obvious that N has a corresponding quotient operation 
on 
as long as we define 
.
on as long as we define .If there is not a quotient operation 
on 
, the problem is whether the finest quotient space 
exists such that
exists such that
on , the problem is whether the finest quotient space exists such that
exists such that
If such quotient operations exists, 
and 
are operational lower and upper bound spaces of 
with respect to operation N, respectively, 
and 
are lower and upper quotient operations of N corresponding to 
, respectively, or simply lower and upper quotient operations of 
.
and are operational lower and upper bound spaces of with respect to operation N, respectively, and are lower and upper quotient operations of N corresponding to , respectively, or simply lower and upper quotient operations of .Obviously, if 
, then 
is a quotient operation on 
.
, then is a quotient operation on .We next discuss the existence of upper and lower quotient operations.
Proposition 4.2
X is domain. N is a binary-operation on X. 
is a quotient space of X. There exist upper and lower quotient operations of N corresponding to 
.
is a quotient space of X. There exist upper and lower quotient operations of N corresponding to .Proof
Let
Since 
and 
, i.e., A and B are non-empty, from Proposition 1.2 in Chapter 1, we know that all quotient spaces of X constitute a complete semi-order lattice according to the quotient inclusion relation. Therefore, there exist both the least upper bound space 
on A and the greatest lower bound space 
on B.
and , i.e., A and B are non-empty, from Proposition 1.2 in Chapter 1, we know that all quotient spaces of X constitute a complete semi-order lattice according to the quotient inclusion relation. Therefore, there exist both the least upper bound space on A and the greatest lower bound space on B.We only need to show there exist quotient operations on 
and 
, respectively.
and , respectively.From the definition of the least upper bound space, we can see that for 
, there exists 
such that 
, where 
is the projection from 
. Regarding 
and 
as sub-sets of X and 
, we have 
. As stated above, it is known that 
has a quotient operation 
.
, there exists such that , where is the projection from . Regarding and as sub-sets of X and , we have . As stated above, it is known that has a quotient operation .For 
, let 
and 
, where 
. From 
, letting 
, since 
, we have 
.
, let and , where . From , letting , since , we have .Define 
. Since 
, then given 
letting 
and 
, 
and 
are unique. Therefore, c defined above is unique, namely, 
is uniquely defined.
. Since , then given letting and , and are unique. Therefore, c defined above is unique, namely, is uniquely defined.We next only need to prove that 
is homomorphic.
is homomorphic.Let 
and 
.
and .Since 
is the least upper bound space of 
, we have that for 
,
holds.
is the least upper bound space of , we have that for , holds.Given 
, let 
and 
.
, let and .Assume 
. Let 
and 
. Since 
is a quotient operation, we have 
.
. Let and . Since is a quotient operation, we have .By intersection operation, we have
From the definition of 
, we have 
.
, we have .Finally, we can write
Namely, 
is a quotient operation on 
. In other words, 
is a lower quotient operation of X1.
is a quotient operation on . In other words, is a lower quotient operation of X1.We now prove there is an upper quotient operation of X1.
Let 
be the infimum of B. For 
, let
be the infimum of B. For , let
We now show that any two elements in d are 
-equivalent, where 
is an equivalence relation corresponding to 
.
-equivalent, where is an equivalence relation corresponding to .
, 
is assumed to be an equivalence relation corresponding to 
. 
is a projection from 
. 
is a quotient operation on 
.Given 
and 
, let 
and 
. Since 
and 
is the infimum of B, there exist 
such that
and , let and . Since and is the infimum of B, there exist such that
There is no lost generality in assuming that 
, we have
, we have
Since 
, we have 
.
, we have .Thus, 
.
.As 
is the infimum of B, from the definition of infimum we obtain 
.
is the infimum of B, from the definition of infimum we obtain .Similarly, for 
, 
and 
are 
-equivalent.
, and are -equivalent.We conclude that any two of elements in d are 
-equivalent.
-equivalent.Let c be an equivalence class on 
containing d. Define 
.
containing d. Define .From the result above, c is uniquely defined and satisfies
is a projection from 
.
is a projection from .It follows that 
is an upper quotient operation of N with respect to 
is an upper quotient operation of N with respect to 4.5.2. The Construction of Quotient Operations
We have proved that for any quotient space there exist unique upper and lower quotient operations. Now we discuss the construction of them, namely, 
and 
, when X, N and X1 are given, especially, if X is a finite set. In this section, X is assumed to be a finite set.
and , when X, N and X1 are given, especially, if X is a finite set. In this section, X is assumed to be a finite set.Lower Quotient Operation
N is a binary-operation on X. 
is a quotient space of X. 
is an equivalence relation corresponding to 
.
is a quotient space of X. is an equivalence relation corresponding to .Define relation 
recursively as follows.
recursively as follows.
Let 
. Generally, define 
.
. Generally, define .Since X is a finite set, there exists a minimal integer n such that 
.
.Let 
be an equivalence relation with 
as its base. Namely,
be an equivalence relation with as its base. Namely,
Let X be a quotient space with respect to 
. For 
, let
. For , let
We next show that any two of elements in d are 
-equivalent.
-equivalent.For 
, there exist 
and 
such that 
and 
.
, there exist and such that and .From the definition of 
, there exist 
and 
such that 
and 
.
, there exist and such that and .Letting 
then 
. Since 
, have 
,
.
then . Since , have ,.Especially, 
, hence 
.
, hence .Namely, any two of elements in d are 
equivalent.
equivalent.Let c be an equivalence class in X containing d. Hence c is an element of 
.
.Define 
, from the definition, N is uniquely defined. Similar to Proposition 4.2, it can be proved that N is a quotient operation on 
.
, from the definition, N is uniquely defined. Similar to Proposition 4.2, it can be proved that N is a quotient operation on .Finally, it only needs to show that 
is the upper bound of a family of quotient spaces A defined in Section 4.5.1.
is the upper bound of a family of quotient spaces A defined in Section 4.5.1.Suppose there exists a quotient operation 
on space 
and 
is an equivalence relation corresponding to 
.
on space and is an equivalence relation corresponding to .Since 
, 
. Namely, from 
, we have 
.
, . Namely, from , we have .By induction, when i=1, 
holds. Assuming that for 
holds, we next show that for 
the conclusion holds as well.
holds. Assuming that for holds, we next show that for the conclusion holds as well.From 
and based on the definition of relation 
, we have two cases.
and based on the definition of relation , we have two cases.One is 
, and then we have 
. Or there exist 
and 
such that 
and 
. Then 
and 
.
, and then we have . Or there exist and such that and . Then and .Since 
is a quotient operation, we can write
is a quotient operation, we can write
That is, 
holds.
holds.By induction, for any 
, we have 
. Since 
is an equivalence relation with 
as its base, we have 
.
, we have . Since is an equivalence relation with as its base, we have .Therefore, X is the upper space of A. And N is the lower quotient operation of N with respect to 
.
.The above result is stated by the proposition below.
Proposition 4.3
X is a finite set. X1 is a quotient space of X. N is a binary-operation on X. The operation N defined as before is the lower quotient operation of X1, and X is the operational lower bound space of X1 with respect to N.
Example 4.13
Assume that 
. Operation ‘+’ on X is defined as
. Operation ‘+’ on X is defined as
Let 
, where 
. Find the lower quotient operation and the lower bound space on 
with respect to operation ‘+’.
, where . Find the lower quotient operation and the lower bound space on with respect to operation ‘+’.Solution
Let 
be an equivalence relation with respect to 
. Now we find 
.
be an equivalence relation with respect to . Now we find .Since 
, we have 
.
, we have .Similarly, 
.
.It is easy to know that 
. Namely,
. Namely,
Operation 
defined on 
is as follows
defined on is as followsUpper Quotient Operation
X is a domain. N is a binary-operation on X. 
is a quotient space of X. 
is an equivalence relation corresponding to 
.
is a quotient space of X. is an equivalence relation corresponding to .Define 
recursively as follows.
recursively as follows.
and for 
, 
and 
hold.Let 
It is easy to show by induction that 
is an equivalence relation.
is an equivalence relation.Generally, define 
. Since X is finite, there exists a minimal integer 
such that 
.
. Since X is finite, there exists a minimal integer such that .Let 
. 
is a quotient space corresponding to 
. Now we define an operation 
on 
as follows.
. is a quotient space corresponding to . Now we define an operation on as follows.
We first show that any two of elements in d are 
-equivalent.
-equivalent.For 
, assume that 
and 
, where 
and 
, namely, 
and 
.
, assume that and , where and , namely, and .Since 
we can write 
and 
we can write and From the definition of 
, it follows that 
.
, it follows that .Namely, 
holds.
holds.By letting c be an element of 
containing d, obviously c is uniquely defined by a and b.
containing d, obviously c is uniquely defined by a and b.Define 
. We next show that 
is a quotient operation on 
.
. We next show that is a quotient operation on .For 
, letting 
and 
, then 
.
, letting and , then .Moreover, 
.
.Since c is an element of 
and 
, then 
.
and , then .Thus, 
.
.Finally, we show that quotient space 
is the infimum of a family of quotient spaces B defined in Section 4.5.1.
is the infimum of a family of quotient spaces B defined in Section 4.5.1.Given 
, 
is its corresponding equivalence relation. Since 
, namely, for 
, if 
then 
holds.
, is its corresponding equivalence relation. Since , namely, for , if then holds.By induction on i, assuming that for i<k, if 
then 
. We show next that the conclusion still holds for i=k.
then . We show next that the conclusion still holds for i=k.Assume that 
and 
. From the induction assumption, for 
, 
and 
hold.
and . From the induction assumption, for , and hold.Since 
, there exists a quotient operation 
such that
is a projection from 
.
, there exists a quotient operation such that
is a projection from .We have 
.
.Similarly, 
.
.From the induction assumption, it is known that for k-1
From the definition of 
, obtain 
.
, obtain .By induction, for 
, 
holds. Namely, 
holds or 
.
, holds. Namely, holds or .There is a quotient operation on 
and 
is the infimum of B. In other words, 
is the upper quotient operation on 
.
and is the infimum of B. In other words, is the upper quotient operation on .We have the following proposition.
Proposition 4.4
X is a finite set. X1 is a quotient set of X. N is a binary-operation on X. 
defined above, i.e., 
, is the upper quotient operation on X1 and 
is the operational upper bound space of X1 with respect to N.
defined above, i.e., , is the upper quotient operation on X1 and is the operational upper bound space of X1 with respect to N.The approach for constructing 
and 
shown in Proposition 4.4 can be improved so that it is easy to be computed.
and shown in Proposition 4.4 can be improved so that it is easy to be computed.(X,N) is given, where X is a finite set. 
is a quotient space of X. 
is an equivalence relation corresponding to 
.
is a quotient space of X. is an equivalence relation corresponding to .Let 
. Define a relation 
as follows.
. Define a relation as follows.
while for 
, have 
and 
.Let 
. Generally, define 
.
. Generally, define .It is easy to prove that 
is an equivalence relation.
is an equivalence relation.Since X is a finite set, there exists a minimal integer n such that 
.
.Let 
and 
be a quotient space corresponding to 
.
and be a quotient space corresponding to .
, define
Let c be an equivalence class on 
containing d
containing dDefine 
.
.We have a proposition below.
Proposition 4.5
Under the definition and notations above, 
is an operational upper bounded space of X1, and 
is an upper quotient operation of X1 with respect to N.
is an operational upper bounded space of X1, and is an upper quotient operation of X1 with respect to N.Proof
The proposition can be proved in much the same way as that in Proposition 4.4.
Note that definition 
differs from definition 
(see Section 4.5.2). The former is that for all 
, 
and 
hold. However, the latter is that for all 
, 
and 
hold. Obviously, the former is a specific case of the latter. Therefore, finding 
from 
is much easier than from 
.
differs from definition (see Section 4.5.2). The former is that for all , and hold. However, the latter is that for all , and hold. Obviously, the former is a specific case of the latter. Therefore, finding from is much easier than from .Note that instead of definition 
, we may use definition 
and for 
, 
and 
hold.
, we may use definition and for , and hold.Assume that n is a minimal integer such that 
.
.Let 
and 
be a quotient space corresponding to 
. We have the following property.
and be a quotient space corresponding to . We have the following property.Property 4.1
For 
, letting 
, we can see that 
is an element of 
, where 
is a projection from X to 
.
, letting , we can see that is an element of , where is a projection from X to .This property indicates that the result obtained from operation N on 
is uniquely defined on 
. Sometimes, for example in qualitative reasoning, it’s only needed that the quotient space rather than its quotient operation corresponding to N has such a property. Generally, 
, sometimes it’s only needed to find 
instead of 
so that the computational complexity will be reduced.
is uniquely defined on . Sometimes, for example in qualitative reasoning, it’s only needed that the quotient space rather than its quotient operation corresponding to N has such a property. Generally, , sometimes it’s only needed to find instead of so that the computational complexity will be reduced.To illustrate the procedure of finding (
, 
), we give an example below.
, ), we give an example below.Example 4.14
Assume that 
. Define an operation 
on X as
. Define an operation on X as
Let quotient space 
. Find the upper quotient operation 
on 
with respect to 
.
. Find the upper quotient operation on with respect to .Solution
Let 
be an equivalence relation corresponding to 
. Find 
.
be an equivalence relation corresponding to . Find .Let 
and 
.
and .Since 
and 
, 
and 
are not equivalent with respect to 
.
and , and are not equivalent with respect to .Similarly, 
and 
, 
and 
are not 
-equivalent. However, 
and 
. Therefore, 
is decomposed into 
and 
.
and , and are not -equivalent. However, and . Therefore, is decomposed into and .Similarly, it can be proved that 
and 
.
and .Finally, we have 
.
.We observe that 
. Namely, 
.
. Namely, .Let 
.
.We have a quotient operation 
on 
as follows.
on as follows.Note that since operation 
is commutative, the table above is symmetric.
is commutative, the table above is symmetric.The above approach is only available when X is finite. When X is an infinite set, finding the upper (lower) quotient operation is more complicated. We next show some specific cases, i.e., X is a real set.
Quotient Operations on Real Quotient Spaces
X is a one-dimensional Euclidean space, i.e., real axis. Let quotient space 
or simply 
. This kind of quotient space is used in qualitative reasoning with numbers extensively (Murthy, 1988; William, 1988). We will discuss the structure of upper (lower) quotient operation of common ‘addition’ and ‘multiplication’ with respect to 
below.
or simply . This kind of quotient space is used in qualitative reasoning with numbers extensively (Murthy, 1988; William, 1988). We will discuss the structure of upper (lower) quotient operation of common ‘addition’ and ‘multiplication’ with respect to below.Common ‘addition’ on X is denoted by N. We find the upper (or lower) quotient operation of N with respect to 
.
.It’s obvious that the quotient space corresponding to the lower quotient operation N of N with respect to 
is 
, i.e., the coarsest quotient space.
is , i.e., the coarsest quotient space.We now show that the quotient space corresponding to the upper quotient operation 
on 
is 
.
on is .Assume that 
. If a contains more than one element of X, then assume that 
. Since 
is a quotient operation, letting 
we have
. If a contains more than one element of X, then assume that . Since is a quotient operation, letting we have
Namely, 
or 
, where 
:
is a projection.
or , where : is a projection.Since 
, we have 
. But 
, this is a contradiction. Therefore, any element of 
can only contain one element of X at most, i.e., 
.
, we have . But , this is a contradiction. Therefore, any element of can only contain one element of X at most, i.e., .From the discussion above, unfortunately, the upper (lower) bound space with respect to 
is the finest (coarsest) space. This is worthless. We will find a new way to solve the problem in the subsequent section.
is the finest (coarsest) space. This is worthless. We will find a new way to solve the problem in the subsequent section.Now we discuss the quotient operation of common ‘multiplication’.
The common multiplication on X is denoted by 
. We find the upper (lower) quotient operation of 
with respect to 
.
. We find the upper (lower) quotient operation of with respect to .
For simplicity, let 
and 
.
and .It is obvious that 
is a quotient operation on 
and satisfies:
is a quotient operation on and satisfies:(1) 
, 
thus 
is an identity element on 
.
, thus is an identity element on .(2) 
is commutative and associative, so an integral power of an element on 
can be defined as follows.
is commutative and associative, so an integral power of an element on can be defined as follows.
, define 
, where n is an integer. Thus, 
, 
. When 
, for any a, 
holds4.5.3. The Approximation of Quotient Operations
In the preceding section, we have shown that in the quotient space 
of real space X, the upper and lower space corresponding to ‘addition’ operation are the finest and coarsest ones, respectively. So the upper and lower quotient operations obtained are valueless in reality. But in qualitative reasoning with numbers, space 
is widely used. We need to find a way to extricate ourselves from this predicament.
of real space X, the upper and lower space corresponding to ‘addition’ operation are the finest and coarsest ones, respectively. So the upper and lower quotient operations obtained are valueless in reality. But in qualitative reasoning with numbers, space is widely used. We need to find a way to extricate ourselves from this predicament.First let us see an example.
Example 4.15
A bathtub is shown in Fig. 4.8. 
is the variation of input flow. 
is the variation of output flow. H is the variation of gage height. We have
is the variation of input flow. is the variation of output flow. H is the variation of gage height. We have
Let 
, we obtain 
.
, we obtain .From the preceding formula, it is known that the sign of H can’t be determined exactly by the signs of 
and 
. Namely, we can’t judge the value of H exactly on quotient space 
.
and . Namely, we can’t judge the value of H exactly on quotient space .
If 
is fixed, for example, 
, then refining 
we have 
as follows
is fixed, for example, , then refining we have as follows
The elements of 
are denoted by 
and 
, respectively.
are denoted by and , respectively.Hence, we have
In other words, if 
then the sign of H can be decided exactly by the variation of 
on 
. Or the value of H on 
can be determined by the value of 
on 
uniquely.
then the sign of H can be decided exactly by the variation of on . Or the value of H on can be determined by the value of on uniquely.The example shows that under some given initial conditions, when we analyze a system at 
space, it is not necessary to find the upper (lower) quotient operation on 
with respect to N. As long as 
is properly refined, it can still meet the demand of a certain qualitative analysis.
space, it is not necessary to find the upper (lower) quotient operation on with respect to N. As long as is properly refined, it can still meet the demand of a certain qualitative analysis.Two refinement approaches are given below.
Successive Refinement Method
N is a binary-operation on X denoted by 
. 
is a quotient space of X. 
:
is a projection.
. is a quotient space of X. : is a projection.Define an operation on 
as follows. It is called a pseudo-quotient operation corresponding to N.
as follows. It is called a pseudo-quotient operation corresponding to N.
If in the right hand side of the formula, for 
, 
is an element of 
, then 
is a quotient operation on 
, otherwise 
is a pseudo-quotient operation. Now transforming the problem represented at space 
to space 
, if we find some results obtained from operation 
are not unique on 
, for example, 
is not single value on 
, then 
and 
are refined. After refinement, if some results of operation 
we are interested in are still not single-valued, the refining process continues until all results we needed are single-valued.
, is an element of , then is a quotient operation on , otherwise is a pseudo-quotient operation. Now transforming the problem represented at space to space , if we find some results obtained from operation are not unique on , for example, is not single value on , then and are refined. After refinement, if some results of operation we are interested in are still not single-valued, the refining process continues until all results we needed are single-valued.If a problem represented at space 
is deterministic, the refining process can go on until a proper space is obtained. If a problem represented at 
is not completely certain, the proper space may not be found.
is deterministic, the refining process can go on until a proper space is obtained. If a problem represented at is not completely certain, the proper space may not be found.Let us see Example 4.15 again.
From 
, when 
and 
, we can see that the value of 
on space 
is not single-valued. The equivalence classes 
and 
that 
and 
belong to must further be refined.
, when and , we can see that the value of on space is not single-valued. The equivalence classes and that and belong to must further be refined.Generally, for the sum of 
, if 
and 
, then letting 
be an integer, intervals 
and 
are divided into 
and 
, respectively. Thus, the sum of 
can be listed as follows.
, if and , then letting be an integer, intervals and are divided into and , respectively. Thus, the sum of can be listed as follows.After refinement, only two out of nine combinations are uncertain. If the values that we are interested in are not contained in these two uncertain classes, we will have a proper space 
and in the space the sum ‘+’ can be uniquely defined. Otherwise, space 
will further be decomposed.
and in the space the sum ‘+’ can be uniquely defined. Otherwise, space will further be decomposed.The deficiency of the method is that we don’t have a clear and definite criterion for judging what the proper refinement is needed.
Next, we give a successive approximation of the refinement method similar to the approach for finding 
, when X is finite (see Propositions 4.4 and 4.5).
, when X is finite (see Propositions 4.4 and 4.5).Successive Approximation
Given (X,N). 
is a quotient space of X corresponding to 
. Let 
be a sequence of elements on X
is a quotient space of X corresponding to . Let be a sequence of elements on XDefine a relation 
as follows
as follows
Generally, define
We show that 
is an equivalence relation below.
is an equivalence relation below.From induction on n, when n=1, for 
and 
, 
.
and , .Since 
is an equivalence relation, we have that 
and 
, 
. Hence, 
holds.
is an equivalence relation, we have that and , . Hence, holds.Namely, R(x1) is an equivalence relation.
Assuming that for 
, 
is an equivalence relation, we show that 
is also an equivalence relation.
, is an equivalence relation, we show that is also an equivalence relation.We only need to show that the transitivity of the relation holds.
Assume that 
. From the definition of 
, we know that 
. Since 
is an equivalence relation, 
. Again from 
and 
, we have 
.
. From the definition of , we know that . Since is an equivalence relation, . Again from and , we have .Similarly, 
.
.Therefore, 
.
.We obtain that 
is an equivalence relation.
is an equivalence relation.By induction, we conclude that 
is an equivalence relation.
is an equivalence relation.Let 
be a quotient space corresponding to 
. Hence, the results obtained from operation N on any element in 
and one of elements 
are unique. Namely, for 
, by letting 
, 
or 
is an element of 
, where 
is a projection.
be a quotient space corresponding to . Hence, the results obtained from operation N on any element in and one of elements are unique. Namely, for , by letting , or is an element of , where is a projection.To a certain degree 
can be regarded as an approximation of 
. Here, a sequence of elements 
is selected in accordance with specific conditions, for example, the initial values. The deficiency of the method is that 
, 
may not be ensured to be single-valued on 
.
can be regarded as an approximation of . Here, a sequence of elements is selected in accordance with specific conditions, for example, the initial values. The deficiency of the method is that , may not be ensured to be single-valued on .Since 
the successive approximation method is regarded as a refinement one as well.
the successive approximation method is regarded as a refinement one as well.To show the refining process, we give a simple example.
Example 4.16
X is a real set. N is a common addition. 
. Taking a sequence {–3, 2, 10, –8,…} of elements on X, find the successive approximation of N with respect to 
.
. Taking a sequence {–3, 2, 10, –8,…} of elements on X, find the successive approximation of N with respect to .Solution
is an equivalence relation corresponding to 
. From 
and 
, we have 
: 
.From 
and 
, we have
and , we have
Similarly,
A sequence 
of elements on X is given. With 
and zero as points of division, divide interval 
into (n+2) open sets. It’s easy to know that 
is just a quotient space composed by the corresponding (n+2) open sets and (n+1) points of division.
of elements on X is given. With and zero as points of division, divide interval into (n+2) open sets. It’s easy to know that is just a quotient space composed by the corresponding (n+2) open sets and (n+1) points of division.We summarize the methods for finding 
, 
and the approximation of 
in Table 4.6, where X is a domain, N is a binary-operation on X, 
is a quotient space of X, and 
is its corresponding equivalence relation.
, and the approximation of in Table 4.6, where X is a domain, N is a binary-operation on X, is a quotient space of X, and is its corresponding equivalence relation.4.5.4. Constraints and Quotient Constraints
In many reasoning processes, we are confronted with a variety of constraints. Therefore, in a hierarchical reasoning process, the constraint propagation across different grain-size worlds must be considered.
The Definition of Constraints
Table 4.6
The formulas for finding 
and the approximation of 
| X is a finite set | Find  |  |
Find  |  | |
 | ||
| X is an infinite set | Given a set . Find the approximation of  |  |
Definition 4.2
If C is a subset of a product space 
, then C is said to be a constraint on X and Y. When X=Y, C is simply called a constraint on X.
, then C is said to be a constraint on X and Y. When X=Y, C is simply called a constraint on X.From the definition, it is known that a constraint C on X and Y is a relation on X and Y.
For 
, let 
.
, let .C(x) is said to be a section of C at x∈X.
Similarly, a section 
of C at 
can be defined.
of C at can be defined.For example, 
is a function.
is a function.Letting 
, then C is a constraint corresponding to function 
.
, then C is a constraint corresponding to function .Again, given inequality 
, by letting 
, then C is a constraint corresponding to 
.
, by letting , then C is a constraint corresponding to .If N is a binary-operation on X, letting
and X. In other words, an operation can be regarded as a constraint.
and X. In other words, an operation can be regarded as a constraint.We next discuss the representations of constraints at different grain-size worlds.
Quotient Constraints
First, we consider the quotient space representation of a product space.
is a product space, 
and 
are quotient spaces of X and Y, respectively. Their corresponding equivalence relations are 
and 
, respectively. Define an equivalence relation 
on Z as
is a quotient space of Z corresponding to equivalence relation R. On the other hand, the product space 
of 
and 
can be proved to be equivalent to 
, when viewing 
as a quotient space of Z. Therefore, in the following discussion we will use 
to represent the quotient space corresponding to R, and R is the equivalence relation of 
.Definition 4.3
C is a constraint on X and Y. 
and 
are quotient spaces of X and Y, respectively. Their corresponding equivalence relations are 
and 
, respectively. Define
and are quotient spaces of X and Y, respectively. Their corresponding equivalence relations are and , respectively. Define
and 
are said to be outer and inner quotient constraints on 
and 
. If 
, 
is said to be a quotient constraint on 
and 
.Example 4.17
and 
both are intervals [0,d] of real numbers. 
, where 
, 
, 
, 
, and 
, where 
, 
, 
, 
and 
are quotient spaces of X and Y, respectively. C, 
and 
are shown in Fig. 4.9.When using 
as a quotient constraint on quotient spaces 
and 
, the strong point is that the homomorphism principle is satisfied. Namely, if a problem on X has a solution satisfying constraint C, then the same problem on 
must have a solution satisfying constraint 
. If set 
is much larger than C, under the weak constraint 
the solution on 
may not provide a useful cue for solving the same problem on X. Therefore, some stronger constraint 
may be used to narrow the problem-solving space on X but it doesn’t guarantee the satisfaction of the homomorphism principle.
as a quotient constraint on quotient spaces and , the strong point is that the homomorphism principle is satisfied. Namely, if a problem on X has a solution satisfying constraint C, then the same problem on must have a solution satisfying constraint . If set is much larger than C, under the weak constraint the solution on may not provide a useful cue for solving the same problem on X. Therefore, some stronger constraint may be used to narrow the problem-solving space on X but it doesn’t guarantee the satisfaction of the homomorphism principle.Example 4.18
In qualitative reasoning with numbers, Kuipers (1988) presented a concept of ‘envelope constraints’. We next show the relationship between his notion of ‘constraint’ and ours.
Assume that 
and 
, where 
, 
, and 
is a real set.
and , where , , and is a real set.If 
is a set-valued mapping from X to 
and satisfies
is just the envelope constraint of x and y defined by Kuipers. 
and 
are called upper and lower envelopes, respectively and denoted by 
.
is a set-valued mapping from X to and satisfies
is just the envelope constraint of x and y defined by Kuipers. and are called upper and lower envelopes, respectively and denoted by .
Let
From our definition, C is a constraint on X and 
, and it’s just the envelope constraint 
. It is obvious that the envelope constraint is a specific case of the constraint defined in this section.
, and it’s just the envelope constraint . It is obvious that the envelope constraint is a specific case of the constraint defined in this section.Kuipers also presented an envelope constraint propagation approach. We cite it here.
The upper and lower envelopes 
and 
of the constraint between x and y are given as shown in Fig. 4.10. Let 
and 
be the variation range of y and x, respectively. Now, we find the new variation range of x, when range 
propagates across 
.
and of the constraint between x and y are given as shown in Fig. 4.10. Let and be the variation range of y and x, respectively. Now, we find the new variation range of x, when range propagates across .According to the envelope constraint propagation method, projecting the lower endpoint of 
across envelope 
, we have a point b2 on X. Similarly, when projecting the upper endpoint of r(y) across envelope 
, we have 
. Finally, we obtain an interval 
on X. Letting 
, we have 
. This is a new variation range of X.
across envelope , we have a point b2 on X. Similarly, when projecting the upper endpoint of r(y) across envelope , we have . Finally, we obtain an interval on X. Letting , we have . This is a new variation range of X.From our viewpoint, a quotient space of 
is defined as
is defined as
Let
Finding the projection 
of C on 
and the section 
of 
at 
, we have 
. Namely, 
.
of C on and the section of at , we have . Namely, .The section 
indicates the variation range of x under the constraint C when 
. By intersecting 
with 
, we have an interval 
. This is the same as the variation range of x obtained by the Kuipers method. Therefore, the envelope constraint propagation presented by Kuipers is a specific example of the quotient constraint construction methods.
indicates the variation range of x under the constraint C when . By intersecting with , we have an interval . This is the same as the variation range of x obtained by the Kuipers method. Therefore, the envelope constraint propagation presented by Kuipers is a specific example of the quotient constraint construction methods.
The Relationship of Constraints
Projection of Constraints
C is a constraint on X and Y. 
and 
are quotient spaces of X and Y, respectively. Now, we find a constraint on 
and 
corresponding to C.
and are quotient spaces of X and Y, respectively. Now, we find a constraint on and corresponding to C.We have defined the equivalence relation corresponding to quotient space 
of 
. However, C is a subset of 
. The constraint on 
and 
should be a subset of 
. Naturally, the induced constraint of C on 
and 
is defined as p(C), where p is a projection from 
.
of . However, C is a subset of . The constraint on and should be a subset of . Naturally, the induced constraint of C on and is defined as p(C), where p is a projection from .It is easy to know that 
, where 
is the outer quotient constraint of C.
, where is the outer quotient constraint of C.The combination of Constraints
and 
are two constraints on X and Y. If the combination 
of constraints 
and 
has to satisfy both constraints C1 and C2, then it’s denoted by
If the combination constraint 
is only expected to satisfy either 
or 
, then it’s denoted by
is only expected to satisfy either or , then it’s denoted by
The Synthesis of Constraints
and 
are quotient spaces of X. 
and 
are quotient spaces of Y. 
(or 
) is a constraint on 
and 
(or 
and 
). We now find the synthesis of constraints 
and 
.The synthesis of constraints 
and 
is defined as follows.
and is defined as follows.Let 
be the supremum of 
and 
, 
be the supremum of 
and 
, 
and 
be the projections from 
to 
and 
, respectively.
be the supremum of and , be the supremum of and , and be the projections from to and , respectively.Let 
and 
.
and .Define 
, 
is said to be an inner synthetic constraint of 
and 
.
, is said to be an inner synthetic constraint of and .Define 
, 
is said to be an outer synthetic constraint of 
and 
.
, is said to be an outer synthetic constraint of and .According to different situations, any 
can be chosen as synthetic constraint of 
and 
.
can be chosen as synthetic constraint of and .The synthesis of 
and 
can also be constructed in much the same way as that stated in Chapter 3. To illustrate we show an example below.
and can also be constructed in much the same way as that stated in Chapter 3. To illustrate we show an example below.Example 4.19
X and Y are real sets. Lebesgue measures 
and 
are defined on X and Y, respectively.
and are defined on X and Y, respectively.Let 
and 
be quotient spaces of X and Y, respectively. Assume that each element of 
and 
, i=1,2, is measurable on 
and 
, respectively.
and be quotient spaces of X and Y, respectively. Assume that each element of and , i=1,2, is measurable on and , respectively.
is a measurable set on 
, i=1,2. A measure 
on product space 
is defined as a product measure of 
and 
.Let 
be the supremum space of 
and 
. 
be the supremum space of 
and 
. Since all elements on 
and 
are measurable on X and Y, respectively, the elements of 
and 
are measurable as well.
be the supremum space of and . be the supremum space of and . Since all elements on and are measurable on X and Y, respectively, the elements of and are measurable as well.Let 
, i=1,2, be a projection from 
.
, i=1,2, be a projection from .Assume that 
is a measurable set on 
and satisfies
indicates the symmetric difference between A and B and is defined as
is a measurable set on and satisfies
indicates the symmetric difference between A and B and is defined as
indicates the measure of A on 
.Namely, the synthetic constraint of 
and 
is defined as a set 
on 
such that the sum of the measures of its symmetric differences with 
and 
is minimum.
and is defined as a set on such that the sum of the measures of its symmetric differences with and is minimum...................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.