SPOJITÉ MĚŘITELNÉ STRUKTURY S OPERACÍ SKLÁDÁNÍ

Continuous measurable concatenation structures

Spojité měřitelné struktury s operací skládání

Jiří Vaníček

Adresa autora:

Doc. RNDr. Jiří Vaníček, CSc., katedra informačního inženýrství, PEF, ČZU, Kamýcká 129, 165 21 PRAHA 6 a Úřad pro státní informční systém, Havelkova 22, 160 00 PRAHA 6

vanicek@pef.czu.cz, vanicek@usiscr.cz

Anotace:

Jsou vyšetřovány empirické struktury s relací slabého uspořádání, vyjadřujícího preference a dále s operací skládání, která nemusí být nutně asociativní. Měřením se nazývá homeomorfismus takovýchto struktur do množiny reálných čísel, zachovávající slabé uspořádání a operaci skládání, které ovšem může v číselné formální struktuře odpovídat obecnější operace, než pouhé sčítání či násobení čísel. Jsou odvozeny podmínky, za kterých je takovýto homeomorfismus možný, to je podmínky pro to, aby bylo možné takovouto strukturu popsat čísly, představujícími hodnoty získané měřením. Dále jsou diskutovány podmínky, za kterých je měření spojité vzhledem k topologii dané slabým uspořádáním ve vyšetřované empirické struktuře a za kterých je tato empirická struktura isomorfní intervalu reálných čísel. Je definován pojem zúplnění empirické struktury a jsou vyšetřeny podmínky, za kterých zúplnění existuje.

Práce je příspěvkem k obecné teorii měření, která odpovídá na otázku kdy a do jaké míry čísla jsou či nejsou vhodným prostředkem pro popis podstatných vlastností reálných objektů. Motivací pro vyšetřování takovýchto struktur může být například měření jakosti, složitosti či pracnosti informačních systémů nebo softwarových produktů. Lze však nalézt i řadu jiných důležitých aplikací, u kterých skládání není asociativní.

Summary:

Empirical structures with the relation of weak order, described preferences and the concatenation operation, not necessary associative are investigated. Measurement is called a homeomorphism such structures into the set of real numbers, which preserves a weak order and the concatenation operation, mapped in the formal numerical structure to the more general operation as a simple adding or multiplying of numbers. Conditions for the existence of such a homeomorphism are derived, i.e. the condition for the description of the structure using numbers, which are values obtain by measurement, are derived. Further conditions for the continuity of measurement with respect to the weak order topology in the investigated empirical structure and conditions for the isomorphism of such a structure to real interval are derived. The concept of completition of empirical structure is defined and the conditions for the existence of such a completition are derived.

The paper is the contribution to the general measurement theory, which answer the question why and in which manner are numbers the suitable mean for the description of substantial attributes of real objects. The motivation for the investigation of such structures can be for example the measurement of the quality and complexity of information systems or software product and estimation of the effort for there implementation. However lot of another interesting situation in which the concatenation is not associative can be find.

Klíčová slova:

díra v uspořádání; Dodekindova úplnost; homeomorfismus; mezera v uspořádání; měření; struktury se skládáním; měřitelné struktury; spojité měřitelné struktury; zúplnění

Key words:

concatenation structure; completition; continuous measurable structure; Dodekind completeness; homeomorphism; measurement; measurable structure; order gaps; order holes

1 Introduction

The general problem of measurement is a representation of a given empirical structure using some numerical relation system. The purpose of performing such a mapping is to be able to manipulate data in the numerical system and use the results to draw conclusions about the attribute in the empirical system. In this paper we shall investigated a empirical system A with one relation × h of our preferences, which is in fact a weak order (i. e. it is reflexive transitive, but the relations a × h b and b× h a does not necessary imply a = b - this situation let us denote a h b, if a × h b and not (a h b) we shall use the notation a × b) , and one concatenation operation Ě for empirical objects which is not necessary total (not necessary every two empirical objects can be concatenating). Such an ordered triple A = (A, × h , Ě ) is called empirical structure. The measurement can be defined as a mapping j of the set A into some subset of the set Re of all real numbers with the normal order Ł and some concatenation operation Ĺ , defined for numbers, which preserves the weak order and the concatenation operation. Such a mapping is called a homeomorphism between the structure a and the numerical structure (Re, Ł , Ĺ ). In many practical situations, for example when the software is integrated from several parts or for the integration of the information system from its components this representation, called measurement, is not additive. The brief study of nonadditive measurement is given in [Van99].

2 Nonassociative concatenation

In many practical situations, for example the concatenation operation Ě is not necessary associative. In this case of course any additive measurement does not exists.

We shall repeat here the main definitions and theorems from [Van99]:

Definition 1 :Let A be a nonempty set and × h a binary relation on A and Ě a partial binary operation on A with a nonempty domain B Í A ´ A. The ordered triple A = (A, × h , Ě ) is called a concatenation structure if and only if the following conditions are satisfied:

1. Weak order: The relation × h is a weak order on A.

2. Local definability: if a Ě b is defined ((a, b) Î B) , c × h a and d × h b, then c Ě d is also defined.

3. Monotonicity: If a Ě c and b Ě c are defined then a × h b if and only if a Ě c × h b Ě c. If c Ě a and c Ě b are defined then a × h b if and only if c Ě a × h c Ě b.

The concatenation structure is said to be a measurable structure if in addition there is:

4. Positive: Whenever b Ě a is defined a × a Ě b and b × a Ě b.

5. Restrictedly solvable: Whenever b × h a there exists a c Î A such that either b Ě c is defined and b × b Ě c × h a or a Ě c is defined and b × a Ě c × h a.

6. Archimedean in standard sequences: Does not exists an infinite bounded standard sequences defined for J = {1, 2, …} inductively as follows: a(1) = a; a(n) = a(n-1) Ě a, if the right side is defined.

Theorem 1:Let A = (A, × h , Ě ) be a measurable concatenation structure. Then the following holds:

1. There exists a numerical measurable concatenation structure R = (Re, Ł , Ĺ ) such that there exists a homeomorphism j of A into R.

2. If j is a homeomorphism of A into R then y is another such a homeomorphism into R* = (Re, Ł , Ĺ * ) if and only if there exists a strictly increasing function g from y (A) into j (A) such that for all a Î A is j (a) = g(y (a)) and such that the numerical operations Ĺ and Ĺ * are related as follows: x Ĺ * y is defined if and only if g(x) Ĺ g(y) is defined and why they are defined it holds:

x Ĺ * y = g-1(g(x) Ĺ g(y)).

The theorem in its essence says that all measurable concatenation structures are such that the usual conditions for the purely ordinal representation are met, which means there is a countable order-dense subset. Thus it merely asserts that the objects in the set A can be given numerical labels in a way that preserves order. If it can be done at all, it can be done in many ways. Any strictly increasing function defined on the set of numerical labels that is just as good, and any two sets of labels must be related by a strictly increasing function, since both preserve order. This theorem is the analogue of the known theorem from [KLST71] concerning extensive structures and ratio scale type measurement.

3 Order isomorphism to real intervals

The first task is to characterise those simple orders that are order-isomorphic to intervals in Re. This is a classical well-studied mathematical concept for which the following necessary and sufficient conditions are identified:

1. The simple order must have a countable order-dense subset, since that is a necessary and sufficient condition for an order-isomorphism with some infinite subset of the reals.

2. There must be no "gabs" in the order. If a × h c and there is no b such that a × h b × h c then there would be a corresponding gap between the values j (a) and j (c)for an isomorphism j , and so the mapping could not be onto an interval.

3. There must not be "holes" i.e. the simple order must be Dodekind complete.

These three conditions are independent of one another (for example, the integers have gaps but not holes, the rationals have holes but not gaps, and a lexicographic ordering of the plane has neither gaps not holes but has no countable order-dense subset). There are also sufficient because the first condition guarantees the existence of a continuous isomorphism into Re, the last two are equivalent to the statement that the simple order is connected in the order topology and the image of the connected space by a continuous mapping is connected. Such subsets of Re have to be an interval. The result should be formulated as a

Theorem 2: A total order is isomorphic to a real interval if and only if it is topological connected and has a countable order-dense subset. It is topologically connected if and only if it has no gaps (that is for each a × h c there exists b, such that a × h b × h c) and is Dodekind complete. In case of measurable structures with no minimal element, there can be no gaps. If in addition there is no maximal element, then the interval cannot include its endpoints, and so the interval can be taken to be all of Re+. Therefore the following is proved:

Corollary to the Theorem 2:If A = (A, × h , Ě ) is a measurable structure which is Dodekind complete an has no maximal element, then there exists a measurable structure R = (Re+, Ł , Ĺ ) and a continuous homeomorphism j from A into Re, such that j (A) = Re+.

The effect of this corollary is to reduce any question about the impact of added properties, e.g. associativity, on the representation to the study of corresponding functional equations in the field of real numbers.

Representational measurement has pursued two somewhat different goals. One approach emphasises algebraic and counting aspects, and thereby includes numerical representation of finite or countable structures. Another goal is to achieve measurement into real intervals to permit standard machinery of mathematical analysis, for example functional or differential equations. Finite algebraic models can be described using algebraic axioms only. But if the number of elements grows, these finite structures converge to an infinite one and such axioms as the Archimedean are in question. For using the mathematical analysis principles, the notion of limit is necessary and therefore the topological assertions are useful. The question is how purely algebraic structures approximate the infinite ones and also the noncountable ones.

4 Continuous measurable structures

Definition 2: Let A = (A, × h , Ě ) be a measurable concatenation structure.

1. A is called to be continuous if and only if the operation Ě is a continuous function as a function defined on A ´ A in the relative product order topology on its domain and order topology in its range.

2. A is called to be lower semicontinuous if has no minimal element and whenever a Ě b is defined and c × a Ě b, then there exists an a´ Î A such that a × a´ and c × a´Ě b and also exists b´Î A such that b´ × b and c × a Ě b´.

3. A is called to be upper semicontinuous if has no minimal element and whenever a Ě b is defined and a Ě b × c, then the both following are true: if a × a´´ and a´´ Ě b is defined, then there exists an a´ between a and a´ such that a´ Ě b × c and if b × b and a Ě b´´ is defined, then there exists a b´ between b´´ and b such that a Ě b´ × c.

Both lower and upper semicontinuity have to be defined in two parts because they actually assert the right-concatenation a ® a Ě b and left concatenation a ® a Ě b are semicontinuous. The definition of upper semicontinuity is more complicated than that if the lower because when a Ě b × c we need some additional condition to assert that there exists some larger a or b such that a Ě b or a Ě b is defined. It is clear that the combination of upper and lower semicontinuity is equivalent to the continuity of concatenation in each variable separately. Continuity is defined as continuity in both two variables simultaneously. In general continuity in two variables is mire strong then continuity in each separately. But for strictly increasing functions both this concepts are equivalent and therefore the following theorem can be proved:

Theorem 3:Let A = (A, × h , Ě ) be a measurable concatenation structure with no minimal element. It is continuous if and only if it is both lower and upper semicontinuous.

For the numerical representation of continuous measurable structure the following theorem can be proved:

Theorem 4: Let A be a measurable concatenation structure. The following holds:

1. There exists a homeomorphism j that is a continuous function using the order topology of A and the relative topology of the homeomorphic image R = (Re, Ł , Ĺ ).

2. If A is continuous, then under j from the point 1., then R is also continuous concatenation structure.

3. Suppose j and y are homeomorphisms related by the strictly increasing function h, i.e. y = h ° j and j is continuous. Then y is continuous if and only if h and h-1 are continuous functions.

This result is deeper then the general theorem about the existence of homeomorphism into the numerical measurable concatenation structure. It assures that the representation are continuous using the normal or relative (i.e. open set) topology in the subset of Re, rather then a special order topology for each set of labels.

5 Completions of total orders and concatenation structures

Having shown that Dodekind complete structures are the ones that map onto Re+, we now turn to the question of which measurable concatenation structures can be densely embedded in Dodekind complete structures as rationals are dense in reals. For this embedding the similar construction as a definition of reals by the cuts in rationals can be used, but the problem is little bit more complicated. The reason that the problem is tricky is that even a measurable concatenation structure with no minimal element has no gaps, if it has a hole, then the attempt to fill that hole can produce a gap when the concatenation is discontinuous.

Let us remark that we can concentrated to a problem in into total orders only. In the case of weak order we can move the consideration into the factor space of A/h of classes of equivalent elements.

Definition 3: Let A = (A, × h ) be a total order without gaps. A completion of Ais a pair(A, F ) such that:

1. A = (A, × h ) is topological connected simple order.

2. F is an isomorphism fromA into A.

3. F (A) is order dense inA.

4. ais an extremum of A if and only if a = F (a), wherea is an extremum ofA.

To generalise this, one can drop the phrase ”without gaps” and then add the requirement that a, b Î A are the endpoints of a gap in A if and only if a = F (a) and b= F (b), where a and b are endpoints of a gap in A. This guarantees that the completion has exactly those topologically connected components (interval without gaps) that reflect the gap structure of A.

The following existence theorem can be proved:

Theorem 5:

1. If A is simple order without gaps, then there exists a completion of A. All completions are unique up to isomorphism.

2. If measurable concatenation structure is strictly ordered, closed (i. e. a Ě b is defined for all a,b Î A) and without gaps, then it has at most one Dodekind completion.

Therefore the Dodekind completition of measurable structures is possible in most situations of the practical interest.

References:

[KLST71] Krantz, D.H.; Luce, R.D.; Suppers, P and Tversky, A.: Foundation of Measurement,Vol. I. Additive and Polynomial Representation. Accademic Press Inc., San Diego, New York, Boston, London, Sydney, Tokyo, Toronto, 1971, 384p., ISBN 0-12-425403-9

[LKST90] Luce, R.D.; Krantz, D.H.; Suppers, P and Tversky, A.: Foundation of Measurement, Vol. III. Representation, Axiomatization and Invariance. Academic Press Inc., San Diego, New York, Boston, London, Sydney, Tokyo, Toronto, 1971, 341p., ISBN 0-12-425403-9

[Van98] Vaníček, J.:Information System Quality and Complexity in Imperative and Object-Oriented Environment. In: Proc. EUNIS98, Congress on European Co-operation in Higher Education Information Systems, 21.- 22., Sept. 1998, Vrana, I. Edit., Prague, 1998, pp. 75-80, ISBN 80-213-0420-0

[Van99] Vaníček, J.:Nonadditive Representation of Measurement Results. Sborník příspěvků z odborné konference k aktuálním otázkám české ekonomiky a univerz80-itního ekonomického vzdělávání. Provozně ekonomická fakulta Mendelovy zemědělské a lesnické univerzity v Brně, Brno 1999. 2. díl, ISBN 80-86515-87-8