Matematisk Lingvistik VT98:09

Exercise class 3

Deadline

These exercises are supposed to be handed in on Tuesday April 21. Late exercises will receive one-point penalty per extra day. The exercises cover sections three, four and five of chapter three of the course book by Partee, Ter Meulen and Wall.

Definitions

In these exercises we will use the definitions for two sets A and B and seven relations R1, R2, R3, R4, R5, R6 and R7 from A to A.

   A={a,b,c,d}
   B={{a,c},{b,d}}
   R1={<a,a>,<b,b>,<c,c>,<d,d>}
   R2={<a,b>,<b,c>,<c,d>,<d,a>}
   R3={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<d,d>}
   R4={<a,b>,<c,d>}
   R5={<x,y>|x and y are humans and x is an ancestor of y}
   R6={<x,y>|x and y are subsets of A and x is a subset of y}
   R7=AxA

Exercises

1. R1' is the complement of relation R1. Is R1' reflexive? Motivate your answer.

2. R2-1 is the inverse of relation R2. Is R2-1 transitive? Motivate your answer.

3. Determine whether the relations R1 and R7 are equivalence relations. Motivate your answers.

4. Relation R3 is an equivalence relation. What partition corresponds with this relation?

5. Set B is a partition of A. What equivalence relation corresponds with this partition?

6. Relation R4 is a strong order. What is the weak order that corresponds to it?

7. Is relation R5 an order? Motivate your answer. If relation is an order then you should also determine whether it is a strong or a weak order.

8. Compute all least, greatest, minimal and maximal elements of the power set of A for the order R6.

9. Is order R6 a total order? Motivate your answer.

10. Can a reflexive relation be intransitive? Motivate your answer.

Each exercise is worth one point.

Extra optional exercises

If you want you can try the following optional exercises about chapter four of the course book. These exercises do not count for your grade.

11. A hotel has rooms with numbers 6, 16, 26, 36 and so on. The hotel is so large that contains a room for every natural number that has a six as the last digit. Prove that the hotel contains a countably infinite number of rooms.

12. One day the manager of the hotel of the previous question discovers that all rooms with a number that ends on 96 are occupied. However all other rooms turn out to be empty and this means that 90% of the hotel rooms is empty. To make things easier for the cleaning staff the hotel manager decides to move the guests. They all get a new room and the number of this room is computed by the following formula:

    ((OldRoomNumber-96)/10)+6

    What percentage of rooms will be free after the guests have moved? Motivate your answer.

13. A little girl gets a countably infinite number of different Lego bricks for her birthday. Each day she makes a different selection of the bricks and uses this selection for building some nice structure. Is the number of days that she can be occupied with this countably infinite? Motivate your answer. You may ignore the fact that a human life only lasts a final number of days.

Each of these optional exercises is worth 0 points.