MATHEMATICAL BACKGROUND This supplementary chapter(present on the CD-ROM version of the book only)describes some of the mathematical concepts behind the graphical techniques introduced in chapter 32 of Object-Oriented Software Construction,second edition.It is extracted from the ISE manual on EiffelBuild [M 1995e]. The conventions,and any cross-reference that you may encounter in this chapter, are those of [M 1995e]rather than the rest of Object-Oriented Software Construction. Pages are numbered 1076.1,1076.2 and so on to avoid any confusion with the page numbers of the rest of the book,as they appear in the printed version
MATHEMATICAL BACKGROUND This supplementary chapter (present on the CD-ROM version of the book only) describes some of the mathematical concepts behind the graphical techniques introduced in chapter 32 of Object-Oriented Software Construction, second edition. It is extracted from the ISE manual on EiffelBuild [M 1995e]. The conventions, and any cross-reference that you may encounter in this chapter, are those of [M 1995e] rather than the rest of Object-Oriented Software Construction. Pages are numbered 1076.1, 1076.2 and so on to avoid any confusion with the page numbers of the rest of the book, as they appear in the printed version
32A Mathematical background 32A.1 OVERVIEW EiffelBuild relies on simple properties of functions.This chapter presents a summary of the necessary notions. You can use EiffelBuild without having read this discussion,and in fact if you are eager to get your hands on EiffelBuild you may prefer to skip this chapter on first reading and move immediately to the following chapter and the Guided Tour.But an understanding of the elementary mathematical notions discussed below will help you get the most out of EiffelBuild,especially for advanced uses. "Introduction to the Theory Many of the topics of this chapter are also useful for the formal study of of Programming programming languages,and are covered in more details in the book Introduction to the Languages",Prentice Hall. 1991.ISBN013.4985109 Theory of Programming Languages 0-13498502-8pbk. 32A.2 FINITE SETS,CARTESIAN PRODUCT A finite set may be given by the list of its members in braces,for example PERSONHelene,Kiyoko,Laura,Roberto,Helmut) COUNTRY Japan,France,Italy,UK where A means "is defined as". A note about naming conventions:the example sets used in this chapter,such as PERSON and COUNTRY,follow the Eiffel rules for types(classes):they are written in upper-case letters,and use the singular rather than the plural.So PERSON denotes a set of persons and COUNTRY a set of countries.A mathematical text might call these sets PEOPLE and COUNTR/ES,but for a programmer it is more attractive to think of declarations of the form Helene:PERSON --(Eiffel syntax) meaning"Helene represents an object of type PERSON",hence the singular. If X and Y are sets,then Xx Y,called the cartesian product of these sets,is the set of all pairs of the form <x,y>where x is a member of X and y is a member of Y.For example the set PERSON x COUNTRY contains all the pairs such as <Helene,Japan>, <Helene,France>,...,<Kiyoko,Japan>,<Kiyoko,France>and so on. Cartesian product is also applicable to infinite sets.For example if N is the set of natural (non-negative)integers,then N x N is the set of all possible pairs of natural integers
32A Mathematical background 32A.1 OVERVIEW EiffelBuild relies on simple properties of functions. This chapter presents a summary of the necessary notions. You can use EiffelBuild without having read this discussion, and in fact if you are eager to get your hands on EiffelBuild you may prefer to skip this chapter on first reading and move immediately to the following chapter and the Guided Tour. But an understanding of the elementary mathematical notions discussed below will help you get the most out of EiffelBuild, especially for advanced uses. Many of the topics of this chapter are also useful for the formal study of programming languages, and are covered in more details in the book Introduction to the Theory of Programming Languages. 32A.2 FINITE SETS, CARTESIAN PRODUCT A finite set may be given by the list of its members in braces, for example PERSON {Hélène, Kiyoko, Laura, Roberto, Helmut} COUNTRY {Japan, France, Italy, UK} where means “is defined as”. A note about naming conventions: the example sets used in this chapter, such as PERSON and COUNTRY, follow the Eiffel rules for types (classes): they are written in upper-case letters, and use the singular rather than the plural. So PERSON denotes a set of persons and COUNTRY a set of countries. A mathematical text might call these sets PEOPLE and COUNTRIES, but for a programmer it is more attractive to think of declarations of the form Hélène: PERSON -- (Eiffel syntax) meaning “Hélène represents an object of type PERSON”, hence the singular. If X and Y are sets, then X × Y, called the cartesian product of these sets, is the set of all pairs of the form <x, y> where x is a member of X and y is a member of Y. For example the set PERSON × COUNTRY contains all the pairs such as <Hélène, Japan>, <Hélène, France>, ..., <Kiyoko, Japan>, <Kiyoko, France> and so on. Cartesian product is also applicable to infinite sets. For example if N is the set of natural (non-negative) integers, then N × N is the set of all possible pairs of natural integers. “Introduction to the Theory of Programming Languages”, Prentice Hall, 1991, ISBN 0-13-498510-9 (0-13-498502-8 pbk). = ∆ = ∆ = ∆
1076.5 THE CONCEPTS $32A.3 32A.3 RELATIONS Let X and Y be two sets.A relation with source set Y and target set Y is a set of pairs of the form <x,y>such that,in every such pair,x is a member of X and y is a member of y. In other words,a relation is one particular subset of the cartesian product Xx Y. For example.the set of pairs citizenship (<Kiyoko,Japan>,<Helene,France>,<Laura,Italy>, <Roberto,Italy>,<Helene,UK> is a relation with PERSON as source set and COUNTRY as target set.This relation could represent the intuitive notion"x is acitizen of y".Note that Helene would then be a person with dual citizenship.As indicated,this relation will be called citizenship. This example is a finite relation.We can also have infinite relations;for example with the set of natural integers N serving both as source set and target set,we can define the infinite set of pairs neighbors A {<0,>, <1,0>,<1,2>, <2,1>,<2,3>, <3,2>,<3,P, } denoted more precisely and concisely (with the bar used to mean"such that")as {<x,y>∈N×Nly=x+Iory=x-I} and representing the relation whose pairs all contain elements that differ from each other by either +1 or-1.This relation,as indicated,will be called neighbors. The set of all possible relations between two sets X and Y is written >Y.For example the relation citizenship is a member of the set PERSON>COUNTRY;and the relation neighbors is a member of NN.The precise definition of Y is that it is the set P (x Y),using the notation P(4),for any set A,to mean the powerset of 4,that is to say,the set of all possible subsets of 4. The domain of a relation is the set consisting of all elements x such that the relation contains a pair of the form <x,y>for some y-that is to say,a pair with x as its first element.The domain is a subset of the source set.In the case of relation citizenship,the source set is {Helene,Kiyoko,Laura,Roberto;it does not contain Helmut,even though this element has been listed as a member of the source set PERSON,because no pair in citizenship has it as its first element.(The relation does not give any information about the citizenship of Helmut. The range of a relation is the inverse notion:the set consisting of all members of the target set that appear as second element of at least one pair in the relation. A relation is total if its domain covers its entire source set-that is to say,if for every member x ofits source set there is at least one pair of the form <x,y>(for some y) in the relation.It is partial otherwise.If we say "relation"without further qualification
1076.5 THE CONCEPTS §32A.3 32A.3 RELATIONS Let X and Y be two sets. A relation with source set X and target set Y is a set of pairs of the form <x, y> such that, in every such pair, x is a member of X and y is a member of Y. In other words, a relation is one particular subset of the cartesian product X × Y. For example. the set of pairs citizenship {<Kiyoko, Japan>, <Hélène, France>, <Laura, Italy>, <Roberto, Italy>, <Hélène, UK>} is a relation with PERSON as source set and COUNTRY as target set. This relation could represent the intuitive notion “x is a citizen of y”. Note that Hélène would then be a person with dual citizenship. As indicated, this relation will be called citizenship. This example is a finite relation. We can also have infinite relations; for example with the set of natural integers N serving both as source set and target set, we can define the infinite set of pairs neighbors {<0, 1>, <1, 0>, <1, 2>, <2, 1>, <2, 3>, <3, 2>, <3, 4>, ...} denoted more precisely and concisely (with the bar | used to mean “such that”) as {<x, y> ∈ N × N | y = x + 1 or y = x – 1} and representing the relation whose pairs all contain elements that differ from each other by either +1 or –1. This relation, as indicated, will be called neighbors. The set of all possible relations between two sets X and Y is written X ↔ Y. For example the relation citizenship is a member of the set PERSON ↔ COUNTRY; and the relation neighbors is a member of N ↔ N. The precise definition of X ↔ Y is that it is the set P (X × Y), using the notation P (A), for any set A, to mean the powerset of A, that is to say, the set of all possible subsets of A. The domain of a relation is the set consisting of all elements x such that the relation contains a pair of the form <x, y> for some y — that is to say, a pair with x as its first element. The domain is a subset of the source set. In the case of relation citizenship, the source set is {Hélène, Kiyoko, Laura, Roberto}; it does not contain Helmut, even though this element has been listed as a member of the source set PERSON, because no pair in citizenship has it as its first element. (The relation does not give any information about the citizenship of Helmut.) The range of a relation is the inverse notion: the set consisting of all members of the target set that appear as second element of at least one pair in the relation. A relation is total if its domain covers its entire source set — that is to say, if for every member x of its source set there is at least one pair of the form <x, y> (for some y) in the relation. It is partial otherwise. If we say “relation” without further qualification = ∆ = ∆
$32A.4 FUNCTIONS 1076.6 the relation may be partial or total.Relation neighbors is total,but relation citizenship is not because Helmut,a member of its source set,is not in the relation's domain. Note that the notion of relation used here is limited to binary relations,that is to say relations between two sets(the source and the target).If necessary,we can model a more general notion of relations involving any number of sets by using this notion:for example we can capture relations between three sets X,Y and Z by taking relations in X←(Y←Z).This idea will further be applied below to“currying”. 32A.4 FUNCTIONS A function is a relation as just defined,with the extra property that for any x in the source set X,there is at most one pair of the form <x,y>for some y-that is to say,at most one pair with x as its first element-in the relation. The relations used above as examples are not functions.In the case of citizenship, there are two pairs with Helene as their first element.In the case of neighbors,for each number n except 0,there are two pairs with n as their first element:the pair <n,n+I> and the pair <n,n-1>. If we prohibit dual citizenship,that is to say if we remove one of the pairs for Helene,then citizenship becomes a function. The set of pairs <n,n +/>for all possible natural integers n,is a function.Let us call it next.(This is a subset of relation neighbors.) Like a relation,a function may be partial or total.As with relations,the word "function"without further qualification means a function that may be total or partial. Putting together the definitions of“function”and“total relation”we see that with a total function there is,for every member x of its source set,exactly one y in the target set such that <x,y>is in the function. More generally,if f is a function and x is a member of its domain,there is exactly one y such that <x,y>is in the function.This legitimates the usual notation for expressing the value of that y: f(x) For example,next(6)has the value 7;and,once we have made citizenship a function by removing one of the two pairs for Helene,citizenship(Kiyoko)has the value Japan. Remember,however,that the notation f(x)has a taboo associated with it:unless the function is known to be total,the notation is meaningless without a guarantee that x belongs to the domain off. The set of all possible functions with source set X and target set y is written >Y.Since every function is a relation,>Y is a subset of Y. The bar across the arrow in the symbol reminds us that the functions may be partial.The set of total functions from X to Y,a subset of>Y,is written>y without a bar
§32A.4 FUNCTIONS 1076.6 the relation may be partial or total. Relation neighbors is total, but relation citizenship is not because Helmut, a member of its source set, is not in the relation’s domain. Note that the notion of relation used here is limited to binary relations, that is to say relations between two sets (the source and the target). If necessary, we can model a more general notion of relations involving any number of sets by using this notion: for example we can capture relations between three sets X, Y and Z by taking relations in X ↔ (Y ↔ Z). This idea will further be applied below to “currying”. 32A.4 FUNCTIONS A function is a relation as just defined, with the extra property that for any x in the source set X, there is at most one pair of the form <x, y> for some y — that is to say, at most one pair with x as its first element — in the relation. The relations used above as examples are not functions. In the case of citizenship, there are two pairs with Hélène as their first element. In the case of neighbors, for each number n except 0, there are two pairs with n as their first element: the pair <n, n+1> and the pair <n, n – 1>. If we prohibit dual citizenship, that is to say if we remove one of the pairs for Hélène, then citizenship becomes a function. The set of pairs <n, n + 1>, for all possible natural integers n, is a function. Let us call it next. (This is a subset of relation neighbors.) Like a relation, a function may be partial or total. As with relations, the word “function” without further qualification means a function that may be total or partial. Putting together the definitions of “function” and “total relation” we see that with a total function there is, for every member x of its source set, exactly one y in the target set such that <x, y> is in the function. More generally, if f is a function and x is a member of its domain, there is exactly one y such that <x, y> is in the function. This legitimates the usual notation for expressing the value of that y: f (x) For example, next (6) has the value 7; and, once we have made citizenship a function by removing one of the two pairs for Hélène, citizenship (Kiyoko) has the value Japan. Remember, however, that the notation f (x) has a taboo associated with it: unless the function is known to be total, the notation is meaningless without a guarantee that x belongs to the domain of f. The set of all possible functions with source set X and target set Y is written X Y. Since every function is a relation, X Y is a subset of X ↔ Y. The bar across the arrow in the symbol reminds us that the functions may be partial. The set of total functions from X to Y, a subset of X Y, is written X → Y without a bar. | | | |
1076.7 THE CONCEPTS $32A.5 32A.5 FINITE FUNCTIONS Like any set,a relation or function may be finite or infinite.Finite functions,that is to say functions made of a finite set of pairs,will be of particular interest for the rest of this discussion. Function citizenship is finite;function next is infinite. If both X and y are finite,as in the case of citizenship,then their cartesian product Xx Y is also finite,so any function in X>Y(and more generally any relation in >)being a subset of Yx Y,will be finite.If X or Y or both are infinite,however,a function with source set X and target set y may be finite or infinite.So in spite of the next example you can have a finite function between infinite sets;for example,with N as both source and target,the function <0,1>,<237,118>)is finite even though N is infinite. A function is finite if and only if both its domain and its range are finite. The set of finite functions with source set X and target set Y,a subset of>Y, is written Y>Y,where the stands for"finite". 32A.6 VISUALIZING A FINITE FUNCTION Finite functions and relations are of particular interest for software applications because they can be easily represented in the memory of a computer.But for a graphical application builder such as EiffelBuild finite functions have an even more specifically useful property:they are easy to construct and manipulate visually,using an obvious graphical representation in the form of a table.For example you can graphically display the three-pair function{Helene,☐>，<Helmut,●>，<Kiyoko,.O>}-a function in PERSON>SHAPE where SHAPE is a set of graphical icons-as Helene Helmut Kiyoko This representation has the immediate visual advantage that for a reasonably small function it is easy to check visually that what is displayed is a function,not just a general relation:just look at the first column(the function's domain)and check that it has no duplicate.This will be even easier if the source set has a simple order relation so that elements in the first column can be kept sorted,as has been done above using alphabetic order
1076.7 THE CONCEPTS §32A.5 32A.5 FINITE FUNCTIONS Like any set, a relation or function may be finite or infinite. Finite functions, that is to say functions made of a finite set of pairs, will be of particular interest for the rest of this discussion. Function citizenship is finite; function next is infinite. If both X and Y are finite, as in the case of citizenship, then their cartesian product X × Y is also finite, so any function in X Y (and more generally any relation in X ↔ Y), being a subset of X × Y, will be finite. If X or Y or both are infinite, however, a function with source set X and target set Y may be finite or infinite. So in spite of the next example you can have a finite function between infinite sets; for example, with N as both source and target, the function {<0, 1>, <237, 118>} is finite even though N is infinite. A function is finite if and only if both its domain and its range are finite. The set of finite functions with source set X and target set Y, a subset of X Y, is written X Y, where the f stands for “finite”. 32A.6 VISUALIZING A FINITE FUNCTION Finite functions and relations are of particular interest for software applications because they can be easily represented in the memory of a computer. But for a graphical application builder such as EiffelBuild finite functions have an even more specifically useful property: they are easy to construct and manipulate visually, using an obvious graphical representation in the form of a table. For example you can graphically display the three-pair function {<Hélène, >, <Helmut, >, <Kiyoko, >} — a function in PERSON SHAPE where SHAPE is a set of graphical icons — as This representation has the immediate visual advantage that for a reasonably small function it is easy to check visually that what is displayed is a function, not just a general relation: just look at the first column (the function’s domain) and check that it has no duplicate. This will be even easier if the source set has a simple order relation so that elements in the first column can be kept sorted, as has been done above using alphabetic order. | | f f Hélène Kiyoko Helmut