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)}

Attached file(s):

section10-1.doc  View File