# Discrete Math: Binary Relations

Please see the attached file for the fully formatted problems.

2. Let C = {2, 3, 4, 5} and D = {3, 4} and define a binary relation S from C to D as follows:

for all (x, y) for all (x, y)  C  D, (x, y)  S  x  y

(Yes/No answers sufficient; explanation optional)

a. Is 2 S 4?

Is 4 S 3?

Is (4, 4)  S?

Is (3, 2)  S?

b. Write S as a set of ordered pairs.

5. The congruence modulo 3 relation, T, is defined from Z to Z as follows: for all integers m and n, m T n  3 | (m - n).

(Yes/No answers sufficient; explanation optional)

a. Is 10 T 1?

Is 1 T 10?

Is (2, 2)  T?

Is (8, 1)  T?

b. List five integers n such that n T 0.

c. List five integers n such that n T 1.

d. List five integers n such that n T 2.

e. (optional) Make and prove a conjecture about which integers are related by T to 0, which integers are related by T to 1, and which integers are related by T to 2.

9. Let X = {a, b, c}. Recall that P(X) is the power set of X. Define a binary relation R on P (X) as follows:

for all A, B  P (X), A R B  A has the same number of elements as B.

(Yes/No answers sufficient; explanation optional)

a. Is {a, b} R {b, c}?

b. Is {a} R {a, b}?

c. Is {c} R {b}?

12. Let A = {4, 5, 6} and B = {5, 6, 7} and define binary relations R, S, and T from A to B as follows:

for all (x, y)  A  B, (x, y)  R  x  y.

for all (x, y)  A  B, x S y  2 | (x - y)

T = {(4, 7), (6, 5), (6, 7)}.

a. Draw arrow diagrams for R, S, and T. (See Overview for Drawing tips)

b. Indicate whether any of the relations R, S, or T are functions.

24. Draw the directed graph of the binary relation described below. (See Overview for drawing tips)

Define a binary relation S on B = {a, b, c, d} as follows:

S = {(a, b), (a, c), (b, c), (d, d)}

#### Solution Summary

Binary relations are defined and graphs are drawn to explain them.