Unit 19 Exercises

1. For each of the following relations on the set {1, 2, 3, 4}, decide whether it is reflexive, symmetric, antisymmetric and/or transitive.

a) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}

b) {(1, 3), (1, 4), (2, 3), (3, 4)}

c) {(1, 1), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 3), (3, 4)}

2. Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric, and/or transitive,
where (x, y) R if and only if

a) x is divisible by y.

b) x y.

c) y = x + 2 or y = x - 2.

d) x = y² + 1.

3. Let A be the set of people in your town. Let R1 be the unary relation representing the people in your town who were registered in the last election  and R2 be the unary relation representing the people in your town who voted in the last election.  Describe the 1-tuples in each of the following relations.

a) R1 R2.

b) R1 R2.

4. Draw the directed graph that represents the relation {(a,b), (a, c), (b, c), (c, b), (c, c), (c, d), (d, a), (d, b)}.