Problem 1: Let X = {1, 2, 3, 4} and Y = {3, 4, 5, 6}.  Define a relation Q from X to Y  by the rule: x Q y if and only if x >= y.

a.  Which of the following statements are true of the relation Q? .

Statement

True or False?

Reason

2 Q 4

4 Q 3

(4,4) is in Q

(7,3) is in Q

b. Write Q as a set of ordered pairs. Be sure to use correct notation for both sets and ordered pairs.

Important hint: Check your answers to (a) and (b) for consistency with one another!

In Problems 2 and 3, you are given a binary relation on a set.  Determine whether the relation is (a) reflexive, (b) symmetric, (c) transitive.  If your answer to any of the questions about the relation is No, give a specific counterexample. (There is no need to give more than one counterexample to justify a "No".)

Problem 2:

Set: {0, 1, 2, 3}

Relation: {(0,0), (0,1), (1,1), (1,2), (2,2), (2,3), (3,3)}

Reflexive?

Symmetric?

Transitive?

Problem 3:

Set: the set Z of integers.

Relation O: m O n means m - n is odd.

Reflexive?

Symmetric?

Transitive?

Hint: Experiment with a couple dozen examples first.

Problem 4: Draw a directed graph to represent the relation R on A, where A = {1, 2, 3, 4, 5} and R = {(1,2), (1,3), (2,2), (2,4), (4,5)}.

Problem 5: Let A = {a, b, c, d, e, f} be partitioned into subsets {a, b}, {c, e, f}, and {d}. Illustrate the corresponding equivalence relation by a directed graph.

Problem 6. Define a relation L on R x R (i.e the Euclidean plane with the usual Cartesian coordinates) by the rule (x, y) L (z, w) if and only if x - y = z - w.  Show that L is an equivalence relation.  Then describe the equivalence classes.