Equivalence class for the relation of having the same set of prime divisors

Question

For an integer $n\in \mathbb{N}$ define $P(n) = \{p : p \mid n \text{, where $p$ is a prime} \}$. For example $P(12)=\{2,3\} $ and $P(1)=\emptyset$.

Question: Consider the relation $R$ on $\mathbb{Z}$ defined by $n R m$ $\iff$ $P(n) = P(m)$. Show that $R$ is an equivalence relation.

My answer: Let $a=b \pmod m$ and $b=c \pmod m$ Thus, $a-b=0 \pmod m$ and $b-c=0\pmod m$ Combining, $a-c=0 \pmod m$ Thus, $a=c \pmod m$

$\rightarrow$ How do I begin to describe the equivalence class [2] for the relation $R$? I don't quite understand... Any help or advice is appreciated.

Answer 1

Recall that being an equivalence relation by definition means to be reflexive, symmetric and transitive.

So you need to show for $m,n,k\in \mathbb{N}$ arbitrary:

1. (reflexivity) $mRm$
2. (symmetry) $mRn\Rightarrow nRm$
3. (transitivity) $mRn$ and $nRk \Rightarrow mRk$

These properties are just inherited from the $=$ in the definition of $R$ like this:

1. (reflexivity) $mRm\Leftrightarrow P(m)=P(m)$
2. (symmetry) $mRn\Leftrightarrow P(m)=P(n)\Leftrightarrow P(n)=P(m)\Leftrightarrow nRm$
3. (transitivity) \begin{align} &\space mRn\text{ and }nRk\\ \Leftrightarrow &\space P(m)=P(n)\text{ and } P(n)=P(k)\\ \Rightarrow &\space P(m)=P(k)\\ \Leftrightarrow &\space mRk \end{align}

So later u would not write this down but just say that $R$ being equivalence relation is inherited from equivalence relation $=$ used in its definition.

Answer 2

A useful general result is that if $A$ and $B$ are nonempty sets, and $f:A\longrightarrow B$ is a function from $A$ to $B$, then the following is an equivalence relation on $A$: For $a_1,a_2\in A$, $a_1 R a_2$ if and only if $f(a_1)=f(a_2)$.

That this is an equivalence relation is very easy to prove: For all $a\in a$, we have $f(a)=f(a)$ since $f$ is a function. For all $a_1, a_2 \in A$, $a_1 R a_2 \Rightarrow f(a_1)=f(a_2) \Rightarrow f(a_2)=f(a_1) \Rightarrow a_2 R a_1$. These show the reflexive and symmetric properties. I'll leave transitive to you.

Applying this in your specific situation, you have a function from $\mathbb{N}$ to the power set of the set of prime numbers, so the above general result holds.

Answer 3

I think it helps to remember that "equivalence" is only a fancy word for "same(ness)". Then you have practically answered the question yourself in the title that you wrote: "having the same set of prime divisors".

Of course something is the same as itself; and if A and B are the same, it is redundant to say that B and A are the same. And of course transitivity is a formalisation of the idea that A and B being the same, and B and C being the same says that A and C are the same.

In this case, the "sameness" consists of having the same set of prime divisors. It doesn't matter how complicated a property is, if the relation is defined as "having the same value for this property", then it must be an equivalence relation. The formal demonstration is only a formality[sic] once you have grasped this.

HTH