Define a relation on NxN by mRn...?

if and only if {p: p is prime and p|m} = {p: p is prime and p|n}. Show this is an equivalence relation and find three members of the equivalence class of 12

1 Answer

Relevance
  • 1 decade ago
    Favorite Answer

    Write PD(m) = { p : p is prime and p|m }. This just means "Prime Divisors" -- to make it easy, and we won't have to write out this silly set over and over and over.

    By the reflexive property of equality (that is, equality of sets):

          PD(m) = PD(m)

    and thus for any m, mRm. Thus R is reflexive.

    By the symmetric property of equality (equality of sets):

          PD(m) = PD(n)   ⇒   PD(n) = PD(m)

    and thus mRn ⇒ nRm. Thus R is symmetric.

    And by the transitive property of equality (equality of sets):

          PD(m) = PD(n) and PD(n) = PD(k)   ⇒   PD(m) = PD(k)

    and thus mRn and nRk ⇒ mRk. Thus R is reflexive.

    Now who has the same prime factors as 12? 2 and 3 are the prime factors of 12, so think of the equivalence class of 12 -- anybody who has only 2 and 3 as prime factors.

    This includes things like 12 itself, 6, 18, etc.

Still have questions? Get your answers by asking now.