Matematisk Lingvistik VT96:09

Class:   09
Date:    960208
Topic:   Exercise class 3

Exercise class 3

These exercises are supposed to be handed in on Monday February 12.

In these exercises we will use two relations:

R1 = { <1,1> , <2,2> , <3,3> , <4,4> }
R2 = { <1,3> , <1,4> , <2,1> , <2,2> , <2,3> , <3,4> , <4,2> }
domain and range: A = { 1 , 2 , 3 , 4 }

X =< Y means X is a subset of (and possibly equal to) Y.

1. Determine for both relations whether they are reflexive, nonreflexive or irreflexive.

2. Determine for both relations whether they are symmetric, nonsymmetric, asymmetric or anti-symmetric (more than one positive answer per relation are possible).

3. Determine for both relations whether they are transitive, nontransitive or intransitive.

4. Determine for both relations whether they are connected or nonconnected.

5. Determine if R1' is reflexive, nonreflexive or irreflexive (U=AxA). Is your result correct when you compare it with figure 3.2 of the book and exercise 1?

6. Determine if R2-1 (the inverse of R2) is symmetric, nonsymmetric, asymmetric or anti-symmetric. Is your result correct when you compare it with figure 3.2 of the book and exercise 2?

7. Determine for both relations whether they are equivalence relations.

8. Give the corresponding partition of A for any of the two relations that is a equivalence relation.

9. Determine for both relations whether they are weak or strict orders on A.

10. Create a superset R3 of R1 (so R1 =< R3) such that R3 is a total order on A. Now give the minimal, least, maximal and greatest elements of R3, if they exist.

Each exercise is worth 1 point.