Unit 21 Answers

1.

    a) Equivalence relation

    b) Equivalence relation

    c) Not symmetric, not transitive

2.

  1. (x, x) in.gif 
(889 bytes) R since f(x) = f(x).  Hence R is reflexive. 
    (x, y) in.gif 
(889 bytes) R if and only if f(x) = f(y), which holds if and only if f(y) = f(x) . Hence (x, y) in.gif (889 bytes) R if and only if (y, x) in.gif (889 bytes) R.   Hence R is symmetric. 
    If (x, y) in.gif (889 bytes) R and   (y, z) in.gif (889 bytes) R, then f(x) = f(y) and f(y) = f(z).   Hence f(x) = f(z).  Thus (x, z) in.gif 
(889 bytes) R.   Hence R is transitive.
  2. The set f -1(b) for b in the range of f. That is the set of all elements of A that are mapped to the same element of the range by f.

3. Let   R = { (p, q) | p eqvT.gif (73 bytes) q and p and q are propositions }.  A proposition p is equivalent to q means that p and q always have the same truth value.  Since p has the same truth value as p, R is reflexive.  R is symmetric, since if p and q have the same truth value, then q and p have the same truth value.  If p and q have the same truth value and q and r have the same truth value, then p and r also have the same truth value. So R is transitive. Hence R is an equivalence relation.

4. { 6n + k | n in.gif (889 bytes) Z } for k in.gif (889 bytes) {0, 1, 2, 3, 4, 5}, where Z is the set of integers.

5. a) No   b) Yes   c) No   d) Yes

6. a) The set of integers   b) {n + 0.3 | n in.gif (889 bytes) Z}