# 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

Relevance

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.