Chapter 1 Relations (section 4.1, 4.2 and 4.4) ************************************************* 1.1 Introduction *=*=*=*=*=*=*=*=* A mere set of words would not make a good dictionary. It would be a pain to find a particular word! A usable dictionary has some structure: the words are sorted. In general, the more structure a set have, the more useful it is. A way to bring structure into this set is to describe the relations between its elements, or between its elements and the elements of another set. In this section we will see how we can formalize and study relations. Exemple 1 Imagine you want to build a house. Figure 1.1 shows the tasks that need to be completed. -------------------------------------------------------- [width=0.75@percent]house Figure 1.1: Tasks to build a house -------------------------------------------------------- Let S:={ F,W,E,I,O,R} be the set of all tasks. Problem: can we do the tasks in any order ? For example, it would be better to build the walls AFTER the foundations! S in itself does not contain enough information to choose a correct order. -------------------------------------------------------- [width=0.75@percent]house-PERT Figure 1.2: Constraints between the tasks to build a house -------------------------------------------------------- Set of constraints: rho:={(F,W),(W,O),(W,E),(R,E),(R,I)}. This set of constraints gives some structure to S, and makes it useful. 1.2 Relations *=*=*=*=*=*=*= 1.2.1 Definitions ================== Définition 1 A binary relation on a set S is a subset rho of S× S. Let x and y be two elements of S. Then x is in relation with y (denoted x rho y) iff (x,y)inrho. Exemple 2 Let rho be the relation ``is a prerequisite for'': rho:={(F,W),(W,O),(W,E),(R,E),(R,I)} Then, (F,W)inrho, but (I,O)not inrho. So, F rho W is true, whereas I rho O is false. A relation can be defined by a property. Exercice 1 Let S:={1,2,3,4,5}. Draw the relations defined by: 1. x rho_1 y iff x=y; 2. x rho_2 y iff x<= y; 3. x rho_3 y iff x divides y; 4. x rho_4 y iff x-y is even. Définition 2 A binary relation between two sets S and T is a subset rho of S× T. A n-ary relation between n sets S_1,...,S_n is a subset rho of S_1×···× S_n. Exemple 3 Let M be a set of male and F a set of female students. We can define the relation ``is married to''. 1.2.2 Basic properties of relations ==================================== Is there anything particular about the relation ``is married to'' ? Définition 3 Let rho be a relation between S and T. - S is one-to-one if any element of S and T appears at most once in rho; one-to-one - S is one-to-many if any element of T appears at most once in rho; one-to-many - S is many-to-one if any element of S appears at most once in rho; many-to-one - S is many-to-many in all other cases. many-to-many Exemple 4 Is x lower or equal to itself ? Définition 4 A relation rho on a set S is reflexive iff (for all xin S) x rho x. Exemple 5 Assume x is equal to y. Is y equal to x ? Définition 5 A relation rho on a set S is symmetric iff (for all xin S)(for all yin S) (x rho y)<->(y rho x). Exemple 6 Assume x<= y and y<= x. What can you say about x and y? Définition 6 A relation rho on a set S is antisymmetric iff (for all xin S)(for all yin S)[(x rho y) and (y rho x)]->(x=y). Exemple 7 Assume x(x rho z). Exemple 8 What are the properties of the following relations 1. <, <=, =; 2. ``is married to''; 3. ``is a friend of''; 4. ``has the same color than''. 1.2.3 Operations on relations ============================== A relation is basically a set. So, we can use all usual set operations on relations. Remarque 1 Let S and T be two sets. The powerset (S× T) is the set of all binary relations between S and T. Définition 8 Let rho and sigma be two relations between S and T. We can construct the following new relations: - union: rhounionsigma, - intersection: rhointersectsigma, - complement: rho', - ... Exemple 9 Let S:=N. 1. What is the union of ? 3. What is the union of < and >? 4. Is