Set Relations Binary Relations

Relations

1. 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)  C  D, (x, y)  S  x  y.
a) Write S as a set of ordered pairs.
b) Is 2 S 4? Is 4 S 3? Is (4, 4)  S? Is (3, 2)  S?
2. Let A = {3, 4, 5} and B = {4, 5, 6} and let S be the "divides" relation. That is,
for all (x, y)  A  B, x S y  x | y.
State explicitly which ordered pairs are in S and S -1.

In the following 3 exercises binary relations are defined on the set A = {0, 1, 2, 3}. For each relation:
a) determine whether the relation is reflexive;
b) determine whether the relation is symmetric;
c) determine whether the relation is transitive.
Give a counterexample in each case in which the relation does not satisfy one of the proprieties, or justify why the property holds true.
3. R = {(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3)}.
4. R = {(0, 0), (0, 1), (0, 2), (1, 2)}.
5. R7 = {(0, 3), (2, 3)}.

6. Determine whether or not the following relation is reflexive, symmetric, transitive, or none of these. Justify your answer.
F is the congruence modulo 5 relation on Z: for all
m, n  Z, m F n  5 | (m - n).
7. Let A be the set with eight elements.
a) How many binary relations on A are reflexive?
b) How many binary relations on A are both reflexive and symmetric?
8. Determine which of the following congruence relations are true and which are false:
a) 4  -5 (mod 7).
b) -6 22 (mod 2).
9. Describe the distinct equivalence classes of the following equivalence relation.
F is the relation defined on Z as follows:
for all m, n  Z, m F n  4 | (m - n).
10. Give a real-world example of a relation which is (and justify why it is): symmetric