1. Determine whether each of the following relations R on a set of people is (a) reflexive, (b) symmetric, (c) antisymmetric and/or (d) transitive. For each one, list all properties that apply.

    1. x R y if x is taller than y. antisymmetric, transitive

    2. x R y if x and y were born on the same day. reflexive, symmetric and transitive

    3. x R y if x has the same first name as y. reflexive, symmetric and transitive

    4. x R y if x and y have a common grandparent. reflexive and symmetric

  2. Determine whether each of the following relations R on a set of all real numbers is (a) reflexive, (b) symmetric, (c) antisymmetric and/or (d) transitive. For each one, list all properties that apply.

    1. x R y if x + y = 0. symmetric

    2. x R y if x − y is a rational number. reflexive, symmetric, transitive

    3. x R y if x = 2y. antisymmetric (if x = 2y and y = 2x then x = y = 0)

    4. x R y if xy = 0. symmetric

    5. x R y if xy ≥ 0. reflexive, symmetric

    6. x R y if x = 1 or y = 1. symmetric

  3. Suppose R ⊆ A × B. The inverse R−1 of R is set {(y, x) | (x, y) ∈ R}. The complement R of R is set {(x,cy) | (x, y) ∉ R}. Suppose that R ⊆ Z × Z is defined by R = {(x, y) | x < y}. What are

    1. R−1

      R−1 = {(x, y) | y < x}.

    2. R

      R = {(x, y) | x ≥ y}.

  4. Suppose that the following relations are defined on the set of real numbers.

      R1 = {(x, y) | x > y}
      R2 = {(x, y) | x ≥ y}
      R3 = {(x, y) | x < y}
      R4 = {(x, y) | x ≤ y}

    What relation is each of the following?

    1. R1  °  R1

      R1 ° R1 = R1

      Since R1 = {(x, y) | x > y}, R1  °  R1 is relation {(x, y) | ∃z(x > z ∧ z > y}. But there is a real number between every pair of different real numbers. So saying that there is a z where x > z ∧ z > y is equivalent to saying that x > y.

    2. R1  °  R2

      R1 ° R2 = R1

    3. R1  °  R3

      R1 ° R3 = R × R

      Since R1 = {(x, y) | x > y} and R3 = {(x, y) | x < y}, R1  °  R3 is relation {(x, y) | ∃z(x < z ∧ z > y}. But there is always a real number that is larger than both x and y. So R1  °  R3 relates all pairs of real numbers x and y.

    4. R1  °  R4

      R1 ° R4 = R × R

    5. R2  °  R3

      R2 ° R3 = R × R

    6. R3  °  R3

      R3 ° R3 = R3

  5. Suppose that R = {(1,3), (2,4), (3,1), (3,5), (4,3), (5,1), (5,2), (5,4)}. What is R  °  R?

    R ° R = {(1,1), (1,5), (2,3), (3,1), (3,2), (3,3), (3,4), (4,1), (4,5), (5,3), (5,4)}

    (1,1) ∈ R  °  R because (1,3) ∈ R and (3,1) ∈ R.
    (1,5) ∈ R  °  R because (1,3) ∈ R and (3,5) ∈ R.
    (2,3) ∈ R  °  R because (2,4) ∈ R and (4,3) ∈ R.
    (3,1) ∈ R  °  R because (3,5) ∈ R and (5,1) ∈ R.
    (3,2) ∈ R  °  R because (3,5) ∈ R and (5,2) ∈ R.
    (3,3) ∈ R  °  R because (3,5) ∈ R and (5,3) ∈ R.
    (3,4) ∈ R  °  R because (3,5) ∈ R and (5,4) ∈ R.
    (4,1) ∈ R  °  R because (4,3) ∈ R and (3,1) ∈ R.
    (4,5) ∈ R  °  R because (4,3) ∈ R and (3,5) ∈ R.
    (5,3) ∈ R  °  R because (5,1) ∈ R and (1,3) ∈ R.
    (5,4) ∈ R  °  R because (5,2) ∈ R and (2,4) ∈ R.

  6. 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}.