Unit 20 Answers

1. S o R = {(a, b) | a is a parent of b and b has a sibling}, R o S = {(a, b)| a is an aunt or uncle of b}

2. Proof by mathematical induction on n. 
Basis step: Since R1 = R,  R1 is reflexive. 
Inductive step: Assume R n is reflexive.  Then for any a in.gif (889 bytes) A,   (a, a) in.gif (889 bytes) Rn  and (a, a) in.gif (889 bytes) R. 
Since R n + 1 =   R n o R,  (a, a) in.gif (889 bytes) R n o R  =   R n + 1. Hence R n + 1 is reflexive.

3.

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

4. { (a, b) | a is a multiple of b or b is a multiple of a }

5. Since R1 hence R   is a subset of R* and since R is reflexive, all the ordered pairs of form (a, a) are in R*. Hence R* is reflexive.