How would I show that R is an equivalence relation?

Question

If I were to consider the relation R on ℤ defined by n R m if and only if P(n)=P(m). How would I show that R is an equivalence relation? Any help is appreciated.

Answer 1

Notice that any relation defined by an equality as in your relation

$$n\mathcal R m\iff \mathcal P(n)=\mathcal P(m)$$ is an equivalence relation and the proof is straightforward: just write.

Answer 2

For each $n$ we have $P(n)=P(n)$ (reflexivity).

If $P(n)=P(m)$ then $P(m)=P(n)$ (symmetry).

If $P(n)=P(m)$ and $P(m)=P(k)$ then $P(n)=P(k)$ (transitivity).

Above expressions like $P(n)=P(m)$ can be interchanged for expressions $nRm$.

In fact every function induces an equivalence relation this way. Conversely any equivalence relation is characterized by a function.

Answer 3

$nRn$ always holds cause $\mathcal P(n)=\mathcal P(n)$ is trivially true. The relation is thus reflexive.

Let $nRm$ holds. Then $\mathcal P(n)=\mathcal P(m)$ is true. Which shows $\mathcal P(m)=\mathcal P(n)\Rightarrow mRn$ holds. So relation is symmetric.

Finally if $nRm, mRl$ hold then $\mathcal P(n)=\mathcal P(m), \mathcal P(m)=\mathcal P(l)$ hold. Which means $\mathcal P(n)=\mathcal P(l)$ holds. Thus $nRL$ is true.

So the relation is transitive.

Answer 4

• Reflexivity: for any $n\in \mathbb{N}$ we trivially have $\mathcal{P}(n) = \mathcal{P}(n)$.
• Symmetry: suppose $(m,n)\in R$. So $\mathcal{P}(m) = \mathcal{P}(n)$, which implies $\mathcal{P}(n) = \mathcal{P}(m)$ therefore $(n,m) \in R$.
• Transitivity: suppose $(m,n), (n,p) \in R$. Then $\mathcal{P}(m) = \mathcal{P}(n) = \mathcal{P}(p)$ therefore $\mathcal{P}(m) = \mathcal{P}(p)$ so $(m,p)\in R$.

Answer 5

It is straightforward to prove relations of form $\rm\, x\sim y {\overset{\ def}{\color{#c00}\iff}} f(x) = f(y)\, $ are equivalence relations.

More generally, suppose $\rm\ u\sim v\ \smash[t]{\overset{\ def}{\color{#c00}\iff}}\, f(u) \approx f(v)\ $ for a function $\rm\,f\,$ and equivalence relation $\,\approx.\, \ $ Then the equivalence relation $\rm\color{#0a0}{properties\ (E)}\,$ of $\,\approx\,$ transport (pullback) to $\,\sim\,$ along $\rm\,f$ as follows

• reflexive $\rm\quad\ \color{#0a0}{\overset{(E)}\Rightarrow}\, f(v) \approx f(v)\:\color{#c00}\Rightarrow\:v\sim v$

• symmetric $\rm\,\ u\sim v\:\color{#c00}\Rightarrow\ f(u) \approx f(v)\:\color{#0a0}{\overset{(E)}\Rightarrow}\:f(v)\approx f(u)\:\color{#c00}\Rightarrow\:v\sim u$

• transitive $\rm\ \ \ u\sim v,\, v\sim w\:\color{#c00}\Rightarrow\: f(u)\approx f(v),\,f(v)\approx f(w)\:\color{#0a0}{\overset{(E)}\Rightarrow}\:f(u)\approx f(w)\:\color{#c00}\Rightarrow u\sim w$

Such relations are called (equivalence) kernels. One calls $\, \sim\,$ the $\,(\approx)\,$ kernel of $\rm\,f.$

Yours is the special case when $\,\approx\,$ is the equivalence relation of equality.