Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Hints for the exercises on relations
Computer Laboratory > Course material > Discrete Mathematics > Hints for the exercises on relations

Please do try the questions by yourself before resorting to these hints!

  1. {(2,z), (3,x), (3,z)}.
  2. R ∪ {(3,3)}.
    R ∪ {(2,4)}.
    2R3 & 3R2 but 2 ≠ 3.
    R ∪ {(3,3), (4,3)}.
  3. 2km and 2kmn.
  4. 23.3 = 512 and 5.
  5. (y,x) ∈ (R∩S)-1 ⇔ (x,y) ∈ R∩S ⇔ (x,y) ∈ R ∧ (x,y) ∈ S ⇔ (y,x) ∈ R-1 ∧ (y,x) ∈ S-1 ⇔ (y,x) ∈ R-1∩S-1.
    Similarly.
  6. A = {1, 2} and R = {(1,2), (2,1)}, suitably extended for general n.
    A×A.
  7. R is reflexive and R ⊆ R ∪ S ⊆ t(R∪S), so that is reflexive too.
    (x,y) ∈ t(R∪S) ⇒ ∃ x0 = x, x1, x2, ... xn = y with (xi,xi+1) ∈ R∪S for 0 ≤ i < n. If (xi,xi+1) ∈ R then (xi+1,xi) ∈ R and if (xi,xi+1) ∈ S then (xi+1,xi) ∈ S, so (xi+1,xi) ∈ R∪S.Hence (y,x) ∈ t(R∪S), so that is symmetric.
    Clearly t(R∪S) is transitive, so it is an equivalence relation.
    Moreover, any equivalence relation containing R∪S must contain t(R∪S) so that is the smallest such.
  8. r(R) - treat 1 as a prime.
    s(R) - x is a multiple or divisor of y by a prime amount.
    t(R) - x is a strict factor of y.
  9. Yes, yes, no (t(s(R)) is reflexive for any elements related to anything at all, but s(t(R)) need not be).
    Yes, yes, no.
  10. t(s(r(R))).
    Divisibility order. No - symmetry precludes anti-symmetry in general.
  11. Diagonal order and lexicographic order.