Matematisk Lingvistik VT98:06

Exercise class 2

Deadline

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

Notation

Because of the limitation of the range of characters in HTML I cannot display every character I need. I will use the following replacements in this exercise:

   A'       the complement of set A
   idA      the identity function in set A
   R-1      the inverse of relation R
   AxB      the Cartesian product of set A and set B
   RoS      the composition of relation R and relation S
   x in A   x is an element of A

Definitions

In these exercises we will use the definitions for one set A and five relations R, S, T, U and V from A to A.

   A={a,b,d,k}
   R={<x,y>|<x,y> in AxA and (x=a or y=a)}
   S={<a,b>,<b,d>,<d,k>,<k,k>}
   T={<a,d>,<b,k>,<d,a>,<k,b>}
   U={<a,b>,<b,d>,<d,k>,<k,a>}
   V=AxA

Exercises

1. Compute the elements of the following Cartesian product: {{1,2},3} x {{a},b} .

2. List the elements of R.

3. List the elements of R' and R-1.

4. Is relation AxA a function from A to A? And is the empty relation Ø a function from A to A?

5. Relations S and T are functions. Determine if they are onto, one-to-one functions or one-to-one correspondences.

6. Give the elements of SoT and ToS.

7. If F is a function from set B to set C then F-1oF=idB and FoF-1=idC. Does this mean that idB=idC? Motivate your answer.

8. Determine if the relations U and V are reflexive, nonreflexive or irreflexive.

9. Determine if the relations U and V are symmetric, nonsymmetric, asymmetric or anti-symmetric.

10. Determine if the relations U and V are transitive, nontransitive or intransitive.

Each exercise is worth one point. Note that in exercises 5, 8, 9 and 10 the relations may have more than one property.