Mapping of equivalence classes of integers modulo $n$

264 Views Asked by At

This is an exercise problem from Essentials of Discrete Mathematics (3rd Edition) by David J. Hunter. The problem is as follows:

Consider the function $p : \mathbb{Z} \rightarrow \mathbb{Z}/n$ defined by $p(k) = [k]$. Prove that this function is onto but not one-to-one.

The answer is given as follows:

Onto: For any $[n], p(n) = [n]$. It is not one-to-one (for $n \neq 0$) because $p(0) = [0] = p(n)$.

I would be most grateful if someone could elaborate more upon this given answer.

From my understanding, for any given equivalence class $[k]_n$ for the set of integers modulo $n$, \begin{align} [k]_n &= \{ x \in \mathbb{Z} : x \equiv k\bmod{n}\} \\ &= \{\cdots, k-n, k, k+n, \cdots \} \end{align} In which case, I am not sure why $[0]$ does not satisfy the quality of being one-to-one.

EDIT: Thank you very much to all the answers. I am very dumb, the answer was staring at me right in the face.

2

There are 2 best solutions below

0
On BEST ANSWER

You have $[n] = [0]$, but $n \not=0$. This is why is it not 1-1; it does not preserve distinctness. Remember your domain is the integers.

0
On

The function is onto because any $[k] \in \mathbb{Z}/n$ is a value of the function $p$, namely $p(k) = [k]$. It is not one-to-one because $n \neq 0$ but $p(n) = [n]=[0]=p(0)$, two different elements of $\mathbb{Z}$ have the same image.