The Orders of Magnitude Models as Qualitative Algebras

1. Introduction

Economists made a handsome contribution to the in­ terest of reasoning about systems behaviour in a qualitative way . In the sixties, they showed that qualitative models could provide a good represen­ tation of some economic systems and that meaning­ ful conclusions could be drawn from pure qualita­ tive data . Without elaborating on a well-defined mathematical framework, such concepts as qualita­ tive vectors and matrices, qualitative linear sys­ number of methods like comparative statics were then proposed to solve qualitative-model -based problems [Lancaster, 1962, Lancaster, 1966, May­

tems , qualitative solutions , were introduced . A bee , 1980 , Quirk , 1981, Ritschard, 1983] .

After sometime, the qualitative approach reemerged at the beginning of the eighties in such varied areas as Control Theory [Caloud, 1987, Gentil et al . , 1987 , Trave and Kaszkurewicz , 1986, Trave , 1988, Trave-Massuyes , 1989] and Artificial Intel­ ligence [De Kleer and Brown , 1984, Dormoy, 1987 , Dormoy , 1988 , Forbus , 1984 , Kuipers, 1984 , Raiman ,

*on leave fr~m seccio de Matematiques i Informati­ ca de E.T.S . d'Arquitectura de Barcelona, U. P.C . , (Spain) ; in collaboration with C. E.A.B .-C. S. I . C.

(Spain) .

1986, Piera and Trave -Massuyes, 1989 , Trave-Massu­ yes et al . , 1989]. The interest of the Artificial Intelligence community in qualitative methods was motivated by the need for a representation of the physical world close to human patterns . Indeed, Qualitative Physics [De Kleer and Brown, 1984, Forbus, 1984, Kuipers, 1984] originate from the idea of modeling human understanding and reasoning about the physical systems in order to implement computer modules including this specific intelli­ gence. As a matter of fact, when they examine a device, humans do not solve differential equations . Instead , reasoning relies on structural decomposi­ tions, common sense and basic physical laws. These basic "reasoning pieces" are then combined by some qualitative calculus so that , "mysteriously", such questions as : "What is the use of the device?", "How does it work?" , "Why does not it work normal­ ly?" ... can be answered. Humans are therefore able to provide a scheme of the functionality and beha­ viour of systems in a very efficient way without requiring formal physics . Qualitative Physics try to reproduce this procedure.

Although new approaches, such as order of magnitu­ de reasoning [Dubois and Prade , 1988, Raiman, 1986], are currently presented, the word "qualita­ tive" still remains associated with a qualitative calculus based on signs. People using qualitative methods in different areas of application have provided models , tools, and methods for handling the qualitative space (+,-,0,?} and a set of ma­ thematical qualitative concepts are now available for solving qualitative-model-based problems. Howe­ ver, they were introduced without connection, when­ ever practical problems required new theoretical investigations.

To our knowledge, no pure theoretical work has been developed towards a well-defined qualitative algebraic structure . Even the mathe~atical proper­ ties of (+ , - , 0,?} are not accurately known . It is the authors opinion that henceforth, advances in applied investigations will closely depend on

theoretical knowledge .

It therefore seems natural in this paper to first present the axiomatic of the qualitative equality . Then , these properties of the qualitative equality necessary for a good understanding of the main re­ sults of the paper are given.

On the other hand, we consider the interesting extension of the sign-based model, involving order of magnitudes, recently introduced in [Dubois and Prade, 1988]. The major aim of this paper is to show that both models can be unified under a gene­ ral algebraic structure called qualitative algebra. Moreover, they can be viewed as two particular ca­ ses of those models which are generated from a real line partition. The finer the partition, the sharper the degree of refinment of order of magni­ tude becomes. Thus any of these models can be structured as a qualitative algebra (Theorem 5.1).

Further, it is shown that these models are embed­ ded into one another as qualitative subalgebras (Theorem 5.2). This has a very important practical implication since during a calculation, one can move from one model to the next, depending on the degree of refinment locally required.

2. Qualitative equality

In Qualitative Physics, reasoning about magnitudes of objects has often been addressed by considering a model based on three labels: positive, negative, and zero. This has not, however, been sufficient to satisfy some elementary mathematical proper­ ties, e.g. closeness of addition. A good model was shown to require a lower level of specification given by the label "indeterminate",that is, either positive, negative or zero. Put together, these four labels make up what is referred to as the Universe of Description 1 of the qualitative model (Q-model). Indeed, this particular case illustra­ tes a general rule of major importance : "the same object can have different qualitative descriptions (Q-descriptions) according to the level of speci­ fication considered". The higher a Q-description, the more quantitative it tends to become implying thus the highest possible level of specification.

Within this scheme, it may be questioned whether two objects described qualitatively are equal. It seems natural to consider them as qualitatively equal if they are equal at some level of specifi­ cation of our universe of description. This rela­ tion will be termed qualitative equality and can be formalized as follows.

Consider a non empty set S (Universe of descrip­ tion),and an order relation~ defined on S. Quali­ tative equality (Q-equality) refers to the binary relation induced by ~ on S and defined by:

a~ if there exists xES such that x~a and x~.

It can be noticed that this definition agrees with the above discussion.

The Q-equality is reflexive and symmetric. Howe­ ver, it is not usually transitive. A simple exam­ ple showing the absence of transitivity is as follows. Consider S- (a,b,c,d} and the order rela­ tion given by the following figure:

then, it clearly appears that bZa, a~ and b*c.

On the other hand, the order relation may be such that all the elements of S are Q-equal, implying that the Q-equality is trivially transitive. This corresponds to what we call degenerated Q-equality. Notice however that, in all cases, transitivity is preserved if the middle element is ~ to the two others.

Characterizing the order relations which induce transitive Q-equalities on one side and degenera­ ted Q-equalities on the other side is particularly interesting. A detailed study can be found in [Piera and Trave-Massuyes, 1989].

3. Basic elements

Consider a set S and a Q-equality, then given aES we call Sa and Ia the following subsets of S:

It can be stated that (S,~) is irreducible if gi­ ven a,bES such that Sa=Sb, then a-b.

An element aES is restricted to Sa x,yES 8 , x~y. From properties can be called a basic element of ~ if ~ is degenerated, i.e., if for all these definitions, the following deduced

• (i) If x~y. then sxcsy.
• (ii) a is a basic element of ~if, and only if, ~ is degenerated on Ia.
• (iii) If a is a basic element and sbcsa, then b is also basic and sb-sa. In particular, if a is basic, for all b~a. b is basic.
• (iv) If x:::::a, and a is basic, then there exists a basic element b such that b~x.

If S is finite, the basic elements are the minimal elements of~. However, not all Q-equalities have basic elements. For example, given the set of na­ tural numbers N, xEN is said to be on the k level, kENU(O}, if 2k~x<2k+l. We define an order relation on N, denoted by ~N , such that for any x,yEN on the levels s and r respectively, we have

~N can be graphically depicted as follows

The Q-equality induced by ~N has no basic elements since for any nEN, we have 2n, 2n+lEin and 2n*2n+l.

Thus (S.~) is said to be basically complete if for all xES, there exists a basic element aES such that x~a. In particular, if S is finite, then S is basically complete.

Consider that (S.~) is basically complete and de­ note B-{aES; a is basic} . BcB is said to be a qua­ litat i ve base (Q-base) of S if B fulfils the fol ­ lowing conditions:

(i) For any xES, there exists aEB such that x~a; (ii) (B.~) is irreducible .

It is clear that any basically complete set S has a base . If B and B' are two bases of S , then they share the same cardinality . The number of elements of a base is therefore a qualitative invariant of S . Consequently, this number can be defined as the dimension of S [Piera and Trave -Massuyes, 1989].

If (S , ~) is irreducible and basically then S has a unique base B, and for any exists a unique subset Bx of B such that complete , xES there s - u sa . x aEBx

The Q-models which are useful sics belong to this category . in Qualitative Phy -

Finally , given (S.~). (T . ~). and an application f from S toT , f is said to be a qualitative mor­ phism (Q-morphism) if it maintains Q- equality , i . e . , for all a , bES such that a~. we have f(a)~f(b).

4 . Qualitative algebras

First , consider a problem ar~s~ng from the Q-equa­ lity concept . When defining operations between objects of a given set, they are of course always compatible with the classical equality. This is not true of the Q-equality and attention must be paid to the operations which must satisfy the com­ patibility property . Therefore , given a set S, S70, a Q-equality defined on S and an internal operation denoted*· *must be compatible with-, i.e. , for all a ,b,c , dES such that a~ and c~. we have a*c~*d .

Naturally if * is compatible with the order rela­ tion which induces the Q-~quality ~ . then * is al­ so compatible with ~. The converse is not true . Indeed, if ~ is degenerated, then any operation defined on S is compatible with ~ whereas it can­ not be assured that it is so with the order relation .

Consider a set S, S70, on which we define a Q-equality ~and two internal operations, denoted + and*, which are compatible with~ and satisfy the following properties :

• (i) + and * are qualitatively associative (Q-as ­ sociative), i.e ., for all a ,b,cES, we have a+(b+c)~(a+b)+c and a*(b*c)~(a*b)*c.
• (ii) +, * are qualitatively commutative (Q-commu­ tative), i . e . , for all a,bES, a+~+a and a*b~*a .
• (iii) the product * is qualitatively distributive (Q-distributive) with respect to the sum +, i.e., for all a,b,cES , we have a*(b+c)~ (a*b)+(a*c).

Then , (S.~,+.*) is said to be a qualitative alge­ bra (Q-algebra).

If the Q-equality ~ is degenerated, then (S , ~,+.*) is called a degenerated Q-algebra . Besides, if the commutativity, associativity, and distributivity of the two internal operations of a Q-algebra are satisfied by using - instead of~. (S . ~ , +,*) is then said to be a strict Q-algebra.

Notice that the definition of Q- algebra does not the existence of relevant elements with to the operations . In particlar, neither nor zero elements are required. This ful­ require respect neutral fils our structure objective of defining the most general which could simultaneously capture the essential properties for calculation .

A Q-algebra (S.~,+.*) is said to have neutral (ze ­ ro) element with respect to the sum (product) if there exists o.Es (e.ES) such that for all aES, a+O. - O.+a- a (e.+a- a+e. - e.). In the definitions of zero and neutral elements, the strict equality is imposed . This is because it seems natural to re­ quire them to be "qualitatively unique", in the sense that if two non strictly equal elements are zero (neutral) , they should be Q-equal . This is not satisfied when using the Q-equality in the definitions . For example, consider A- {a,b,c} and

a the order relation ~ \ . We define two internal b c

operations +and* such that (A.~,+,*) is a Q-al­ gebra and e. - a. Then , we have~ · · c~+ and b*c . This does not occur if the strict equality is used since strict uniqueness is even guaranteed .

Consider a Q-algebra (S. ~, + . *) and TCC, T70. T is said to be a qualitative subalgebra (Q-subalgebra) of S if (T , ~.+.*) is a Q-algebra .

It is interesting to point out that all the Q-sub­ algebras of a strict Q-algebra are also strict . On the other hand, a non strict Q-algebra may have strict and non strict Q-subalgebras.

Given A and B, two Q-algebras and f, a mapping from A on to B. f is said to be a Q-morphism of algebras if f preserves the qualitative equality and satisfies the two following conditions :

• (i) f(a+b)~f(a)+f(b) ;
• (ii) f(a*b)~f(a)*f(b) .

If f is a one-to-one mapping, then f is called a qualitative isomorphism of algebras (Q-isomor ­ phism).

5. Qualitative algebras of orders of magnitude

In Qualitative Physics, the word "qualitative" re­ mains associated with a qualitative sign-based calculus. Working with signs was shown to provide an aggregation level similar to the one involved in human reasoning about the physical world . In­ deed, this reasoning is mainly based on the varia­ tions of significant quantities , which c an be for­ mally represented by the signs of the derivatives . On the other hand, this approach was shown to be an alternative for managing unprecise knowledge . Thus the knowledge of parameter signs in a model sometimes suffices to draw significant conclusions on the modelled system.

The qualitative procedure consists of partitioning the real line in three classes by considering the equivalence relation given by the same sign on the set of reals ~ - Labels + , 0, and - are chosen to represent the classes of positive, zero , and nega­ tive real numbers , respectively . These three la­ bels thus constitute the highest level of specifi­ cation of our Q-model. Now, a lower level of spe­ cification is necessary to handle real numbers with indeterminate sign. It is represented by la­ bel ? . The universe of description of this model is thus S- {+,0,-,?) . An order relation ~ is defi­ ned, which should convey the idea that the higher the level of specification, the lower the possibi­ lity of Q-equality. ~ is represented below:

+ 0 -

Notice that Q-equality ~ induced by ~ is reflexi­ ve, symmetric but not transitive. But, in accor­ dance with section 2, transitivity exists if the middle element is ~ to the two others, i . e . , if the middle element is different from?.

Two internal operations 9 and ® are defined by :

These operations are compatible with the Q-equali­ ty ~ induced by ~ - The tables also show that 9 and ® are associative and commutative in the strict sense. Distributivity of 9 with respect to ® is also strictly verified . These conditions provide (S.~,9 , ®) with a structure of strict Q-algebra. (S , ~,9,®) is referred to as the Q-algebra of signs .

Notice that the Q-algebra of signs has neutral and zero elements for 9 and ®. Put together, this pro­ perty and the fact that it is a strict Q-algebra make it very suitable for qualitative calculus purposes [Trave-Massuyes et al., 1989].

An interesting extension of this model was recent ­ ly proposed in [Dubois and Prade, 1988] . The main idea was to include orders of magnitude, advanta­ geously setting total inde termination (specifica­ tion level ?) further away by creating new levels of specification. The real line is now partitioned into seven classes with associated labels: negati­ ve large (NL) , negative medium (NM) , negative small (NS) , zero (0), positive small (PS) , positi­ ve medium (PM) , positive large (PL) .

- - - - ----+- -- - ---+-- - -----+-- - -----+-------+- -- -- --

The set S 1 - {NL,NM,NS,O,PS,PM,PL), ordered by NL< NM<NS<O<PS<PM<PL, constitutes the highest level of specification. Between this level and the lowest one given by ?, the actual partitioning induces four new ordered levels of specification. Inter­ preting the labels as intervals, the four levels correspond to the union of two, three, four, and five adjacent intervals. Labels within these le­ vels are denoted [a,b] , where a,bES 1 - {0) and a<b. [a ,b] represents the interval obtained from the union of the intervals associated with a and b and the one in between . Our universe of description is S- s 1 U{[NL ,NM],[NM ,NS] , .. . ,[NL , PM],[NM,PL],?l and the order relation ~ can be represented as follows :

It is easy to see that S is basically complete (S 1 is a base and is unique) and irreducible.

When defining the symbolic tables for the internal operations 9 and ®, we must of remain consistent with the real line operations. Here, a few pro­ blems arise since the qualitative result may dif­ fer from the boundaries of the intervals. For example, if 10 is the upper boundary of PS, then PS+PS- [PS , PM] if the upper boundary of PM is grea­ ter than or equal to 20 . If it is less than 20, then PS+PS=+ . Similar situations occur for the product, in particular with respect to the posi­ tion of numbers 1 and -1 . This shows a fundamental difference between this model and the one based on signs. Indeed, here tables for 9 and ® are not unique. Their number is finite however and two specific tables for 9 and ® will be suitable for a whole class of practical problems .

Nevertheless, the essential point is that, irres ­ pective of the specific pair of operations, they always provide (S.~) with a structure of Q-alge­ bra . This result will come as a particular case of the Theorem 5 . 1 below. The Q-model so far conside­ red is indeed a particular case within the follo­ wing general framework . Let us show that any fini­ te interval partition s 1 of the real line such that {0)ES 1 gives rise to a Q-model . 2 Given A,BES 1 A is said to be anterior to B, denoted A$B, if for any aEA, there exists bEB such that a~. Of course the binary relation "be anterior to" is a total order relation on s 1 . m 5 and M 5 denote the minimal and maximal element respectively . The complete universe of description induced by s 1 , denoted S , is built from s 1 in the following way : AES if A- {0) or A- [B 1 ,B 2 ] , such that B 1 ,B 2 Es 1 - { {0)) , B1 ~B 2 , and for all BES 1 such that B 1 ~~ 2 · then BEA . Now, the following order relation is defined on S :

2 More generally, this can be ext ended to infinite interval partitions of the [Trave-Massuyes et al., 1989] but this the scope of this p'aper. arbitrary real line is beyond

Graphically, this order relation can be represen­ ted by a tree such that the elements of s 1 consti­ tute the base and the number of levels is equal to the cardinal of s 1 minus 1. With the above cons­ truction of S, (S.~) is basically complete and ir­ reducible and s 1 is the base of S.

The qualitative sum 0 is said to be consistent with the usual real line sum+ if, for all A,BES, A0BES corresponds to the smallest set - in the sence of inclusion - containing A+B. Consistency for the qualitative product is defined in a simi­ lar way. The partition s 1 determines thus one and only one pair of operations (0,®) on (S.~) which are consistent with the usual real line sum and product. The pair (0,®) is then called ~-consis­ tent.

Theorem 5.1 . Given a finite interval partition of the real line s 1 , such that (0)ES 1 , consider the complete universe of description S induced by s 1 . Then, the pair of ~-consistent internal operations (0,®) defined on S provides (S.~) with a structure of Q-algebra.

Proof. Let us show that 0 is Q-associative. Consi­ der X,Y,ZES and let A-X0(Y0Z) and C-(XsY)0Z. Con­ sider x,y,z~ such that xEX, yEY, and zEZ. Let be x+(y+z)-a~. there exists BES 1 such that aEB, then we have ~A. Because + is associative on ~. a=(x+y)+zEC and since aEB, we also have ~- B is a basic element, therefore A~.

The remaining properties of 0 and ® can be proved in a similar way.

Notice that guaranteed. wing finite only the qualitative properties are For example , consider s 1 , the folio­ interval partition of ~:

Then A=NM+(PS+PM) - NM+[PM,PL] - [NM,PL] and C-(NM+PS) +PM=[NM,NL]+PM=[NM,PM]. So A~ but A~.

The following result has a major practical impli­ cation . It is shown that the models obtained from a sequence of finer and finer partitions are em­ bedded into one another as Q-subalgebras . In other words, variables described at different levels of prec1s1on can be considered together by moving from one ·model to the next.

Theorem 5.2. Given two finite interval partitions T 1 and S 1 of the real line such that (0) belongs to both and denote by S and T the corresponding complete universe of description . (0 5 ,® 5 ), (0T,®T) denote the ~-consistent pairs of operations defi­ ned on S and T, respectively. Under these assump­ tions, if T, is a partition finer than s,. then (S,~T.0T,®T} is a Q-subalgebra of (T.~T.0T,®T) . Further, relation -r and operators 0T and ®T res­ tricted to setS are identical to ~ 5 · 0 5 , and ® 5 , respectively.

Proof. If T 1 is finer than S 1 , then any element of S is also element ofT. Let us show that ~T res­ tricted to S is ~ 5 . Given A,CES such that A~TC, which means that there exists BET 1 such that ~TA and ~TC (1) . Since T 1 is finer than S 1 , there exists BES 1 such that ~TB. It is clear that A~rB and ~TB (since (1)). But A,C,BES and T 1 is finer than s 1 , therefore A~ 5 B and C~ 5 B. Since BES 1 , we get A~ 5 c.

It can be similarly proved that 0T and ®T restric­ ted to S are equal to 0 5 and ® 5 . Then, S is a Q-subalgebra of T.

In the Q-model proposed in [Dubois and Prade, 1989] and described at the begining of this sec­ tion, it was noted that different Q-algebras could be built depending on the position of the bounda­ ries of the intervals. The following result shows that all these Q-algebras are Q-isomorphous and can therefore be considered as identical from the qualitative point of view.

Theorem 5.3. Consider s 1 and T 1 two finite inter­ val partitions of the real line such that (0) be­ longs to both, and S and T the corresponding com­ plete universes of description induced by S 1 and T 1 , respectively. The Q-algebras built on S and T are Q-isomorphous if , and only if, there exists a one-to-one mapping f from s 1 on to T 1 such that f((OJ) - (0) and that f maintains the relation~-

Proof . Due to space limitations, the proof is omitted (see [18]).

6. Conclusion

This paper represents the first attempt at provi­ ding a unifying mathematical framework to qualita­ tive models so far used in Qualitative Physics . An axiomatic of the qualitative equality is indeed determined and a general algebraic structure cal­ led qualitative algebra is defined. Rather than going into deep theoretical developments, it see­ med better to confine this paper to two crucial points. First, the usual model (+,-,0,?) as well as the extended one proposed in [Dubois and Prade, 1989] belong to the same class of models. Second, any of these models present the structure of qua­ litative algebra. The imbrications of these models as subalgebras and the characterization of quali­ tatively isomorphous models are then considered.

The basic point is that as research progresses, numerous points become clearer on the specific models we already used. "Evident" relationships and overlappings occur which reinforce our belief that, from now on, advances in application fields will closely depend on theoretical results. Inves­ tigations are therefore underway to determine the underlying properties of qualitative equality and further, of qualitative algebras [Piera and Trave ­ Massuyes, 1989, Trave-Massuyes et al., 1989]. Qua­ litative vectorial spaces structures will be con­ sidered in the near future. This will provide us with the necessary tools enabling us to approach qualitative calculus.

• Acknowledgments . The authors are thankful to Dr. J . L. Dormoy for his fruitful comments and remarks.