Relations

Exemple 1   Imagine you want to build a house.

Figure 1.1 shows the tasks that need to be completed.

---

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.

---

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.

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'':

Then, (F,W)inrho, but (I,O)not inrho.

So, F rho W is true, whereas I rho O is false.

Exercice 1   Let S:={1,2,3,4,5}. Draw the relations defined by:

1. x rho₁ y iff x=y;
2. x rho₂ y iff x<= y;
3. x rho₃ y iff x divides y;
4. x rho₄ 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₁,...,S_n is a subset rho of S₁×···× 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''.

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;

• S is one-to-many if any element of T appears at most once in rho;
  

• S is many-to-one if any element of S appears at most once in rho;

• S is many-to-many in all other cases.

Exemple 4   Is x lower or equal to itself ?

Définition 4   A relation rho on a set S is reflexive iff

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

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

Exemple 7   Assume x<y and y<z. What can you say about x and z?

Définition 7   A relation rho on a set S is transitive iff

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''.

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 <and =?
2. What is the intersection of < and >?
3. What is the union of < and >?
4. Is <a sub relation of <= ?

Exemple 10   Lets come back to the example of the house building.

---

Figure 1.1: Constraints between the tasks to build a house

---

Do you have to do the electricity after the foundations ?

Foundations is not a direct prerequisite for electricity.

However, it still needs to be done before electricity.

The relation ``has to be done before'' is transitive, and contains the relation

``is a prerequisite for''. It's the transitive closure of ``is a prerequisite for''.

Définition 9   Let rho be a relation.

The transitive closure of rho is the smallest transitive relation rho^*containing rho.

Exercice 2   Draw the transitive closure of ``is a prerequisite for''.

Problem 1   Is there an algorithm for computing the transivite relation of a relation?

Algorithme 2   Construction of the transitive closure rho^*.

1. rho^*:=rho;
2. Find x, y, z such that (x rho^*y), (y rho^*z), and (x ¬ rho^*z);
3. If no such triple exists, rho^*is transitive; Exit;
4. rho^*:=rho^*union{(x,z)};
5. Repeat at step 2.

Remarque 2   The order in which you add the pairs to rho is irrelevant.

Exemple 11   Draw the relation ``has to be done before'' (Figure 1.1).

Définition 10   Let rho be a relation.

The reflexive closure of rho is the smallest reflexive relation containing rho.

The symmetric closure of rho is the smallest symmetric relation containing rho.

Exercice 3   Consider the following relation:

1. Draw its reflexive closure
2. Draw its symmetric closure
3. Draw its transitive closure
4. Draw its antisymmetric closure

Remarque 3   The antisymmetric closure of a relation cannot be uniquely defined!

Exemple 12   Consider a set of cars, and the relation ``has the same color as''.

What are the properties of this relation?

Définition 11   An equivalence relation is a relation which is

1. Reflexive
2. Symmetric
3. Transitive

Définition 12   Let rho be a relation on a set S, and x be an element of S.

The equivalence class of x is the set [x]of all elements y such that x rho y.

Exemple 13   The equivalence class of a car is the set of all cars having same color.

Remarque 4   If x rho y, then [x]=[y].

Exemple 14   Consider the relation same as₃ on N defined by xsame as₃y iff 3 divides x-y.

(we also say that x and y are congruent modulo 3: xsame as y (mod 3))

What are the equivalence classes?

Définition 13   A partition of a set S is a collection of subsets { A₁,...,A_k} of S such that:

1. A₁union···union A_k=S
2. A_iintersect A_j=Ø for any i, j.

Exemple 15   Consider a set S of car, whose color are either red, blue, or green.

Define the following subsets of S:

R (red cars), B (blue cars), and G (green cars) .

Then, { R,B,G} is a partition of S.

Théorème 1   In general:

1. An equivalence relation on S defines a unique partition of S.
2. A partition of S defines a unique equivalence relation on S.

Définition 14   Let S be a set, and rho be a relation on S.

The set of all the equivalence classes is called the quotient of S by rho.

Remarque 5   This method is used a lot in set theory:

Construction of Z from N.

Construction of Z/nZ (integers modulo n) from Z.

Construction of Q from Z.

Exemple 16   What are the properties of the relation ``has to be done before'' on the tasks to build a house ?

Définition 15   A partially ordered set (or poset) is a set S with a relation rho which is

1. Reflexive
2. Antisymmetric
3. Transitive

Exemple 17   Which of the following are posets ?

1. ({1,2,3,4},<=);
2. ({1,2,3,4},<);
3. ({1,2,3,4},=);
4. ({1,2,3,4},rho), with x rho y iff x divides y.
5. (({1,2,3,4}),included in or equal to).

Définition 16   Some names:

• Node (or vertex)
• Predecessor
• Immediate predecessor
• Maximal element
• Minimal element
• Least element
• Greatest element

Définition 17   The Hasse diagram of a poset is a drawing of this poset such that:

• If x rho y, then y is higher than x;
• The loops are not drawn;
• There is a segment linking x and y iff x is an immediate predecessor of y.

Exemple 18   Draw all posets on 1, 2, 3, 4 indistinct nodes.

How many such posets are there on 10 nodes ?

Exemple 19   Consider the house building problem, with the following assumptions:

• All tasks take the one day to complete;
• One worker can only work on one task every day;
• It does not save time to have two workers working on the same task.

---

Figure 1.1: Constraints between the tasks to build a house

---

Schedule the tasks between 2 workers to optimize the completion time:





What if there is one worker ?





What if there are three workers ?

Proposition 1   Consider the problem of scheduling n tasks on p processors, subject to precedence constraints, with the same assumptions and goal as above.