1. This question was inadvertently duplicated from 1104.

    Suppose that R is a relation on {1,2,3,4,5} defined by R = {(1,3), (2,4), (3,1), (3,5), (4,3), (5,1), (5,2), (5,4)}. What are

    1. the reflexive closure of R? {(1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (3,5), (4,3), (4,4), (5,1), (5,2), (5,4), (5,5)}

    2. the symmetric closure of R? {(1,3), (1,5), (2,4), (2,5), (3,1), (3,4), (3,5), (4,2), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4)}

    3. the transitive closure of R? {1, 2, 3, 4, 5} × {1, 2, 3, 4, 5}. That is, it contains all ordered pairs over {1, 2, 3, 4, 5}.

  2. Which of the following relations R on a set of people are equivalence relations?

    1. {(x, y) | x and y are the same age}

      Yes

    2. {(x, y) | x and y have the same parents}

      Yes, assuming that they must have both parents in common.

    3. {(x, y) | x and y share a common parent}

      No. This relation is not transitive.

    4. {(x, y) | x and y speak a common language}

      No. This relation is not transitive.

  3. What are the equivalence classes of each of the following equivalence relations on {1,2,3,4}?

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

      {1}, {2}, {3}, {4}

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

      {1, 3}, {2, 4}

  4. List the ordered pairs of the equivalence relation on {1,2,3,4,5,6,7} with partitions {1,2}, {3,4}, {5,6,7}.

    {(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4), (5,5), (5,6), (5,7), (6,5), (6,6), (6,7), (7,5), (7,6), (7,7)}

  5. Suppose that R is the relation on ordered pairs of positive integers {((a, b), (c, d)) | ad = bc}. Show that R is an equivalence relation.

    Variables a, b, c and d are positive integers. The easiest way to approach this problem is to think of a, b, c and d as positive real numbers, and to realize that equation ad = bc is equivalent to a/b = c/d.

    1. ((a, b), (a, b)) is in R because a/b = a/b. So R is reflexive.

    2. Suppose ((a, b), (c, d)) is in R. By the definition of R, a/b = c/d. So ((c, d), (a, b)) is in R.

      So R is symmetric.

    3. Suppose ((a, b), (c, d)) and ((c, d), (e, f )) are both in R.

      By the definition of R, a/b = c/d and c/d = e/f.

      So a/b = e/f, and ((a,b), (e,f)) is in R, and R is transitive.

  6. Which of the following is a partial ordering on {1,2,3,4}? For each that is not a partial ordering, list the properties of partial orderings that it lacks.

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

      This is not a partial ordering. It is not reflexive, since it does not contain (3,3).

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

      This is a partial ordering. In ASCII art, the Hasse diagram of this relation is

            1   4
       \ /
        3

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

      This is not a partial ordering. It is not transitive, since it contains (4,2) and (2,3) but not (4,3).

      If you draw a Hasse diagram of this relation, you get 

               3
         |
         2
         |
         4
      since (4,2) and (2,3) are in this relation. It is easy to inspect the Hasse diagram for transitivity.

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

      This is not a partial ordering. It is not transitive, since it contains (2,4) and (4,1) but not (2,1).

      If you draw a Hasse diagram of this relation, you get 

               1
         |
         4
         |
         3
         |
         2
      since (4,2) and (2,3) are in this relation. It is easy to inspect the Hasse diagram for transitivity.

  7. Say which of each of the following tuples is smaller in lexicographic order.

    We did not cover lexicographic order. It is similar to dictionary order. Find the leftmost component where one tuple has a smaller value.

    1. (1,1,2), (1,2,1)

      (1,1,2)

    2. (0,1,2,3), (0,1,3,2)

      (0,1,2,3)

    3. (1,0,1,0,1), (0,1,1,1,0)

      (0,1,1,1,0)