Friday, 9 August 2013

Is this bijection between subsets of $\mathbb{Z}$ right?

Is this bijection between subsets of $\mathbb{Z}$ right?

I was trying to prove the following: For some fixed $n \in \mathbb{N}$
define the following set of integers $S_4(n) = \{k \in \mathbb{Z} : k =
n+j, j \in \{0,1,2,3\}\subset \mathbb{Z}\}$, then if $A =
\{0,1,2,3\}\subset \mathbb{Z}$, the function $f : S_4(n) \to A$ which
sends each number to the remainder of the division by $4$ is a bijection.
My proof was the following: write $n = 4q + r$ where $q$ is the quotient
of the division by $4$ and $r$ is the remainder. Then, $S_4(n) = \{n_k \in
\mathbb{Z} : n_k = 4q+(r+k), k \in \{0,1,2,3,4\}\subset \mathbb{Z}\}$.
First we prove injectivity. For some $n_i, n_j \in S_4(n)$ consider
$f(n_i) = f(n_j)$. But $n_i = 4q+(r+i)$ and $n_j = 4q + (r+j)$, and so
$f(n_i) = r+ i$ and $f(n_j) = r+j$ and in that case we have $i = j$
implying that $n_i = n_j$ and thus $f$ is injective.
To prove surjectivity we do as follows: given $a \in \{0,1,2,3,4\}$ we
want $n_k = 4q+(r+k)$ such that $f(n_k) = a$. But this means $r+k = a$ and
so we simply take $k = a - r$ which is the same as taking $n_{a -r}$, so
that we have $f(n_{a-r}) = r+(a-r)=a$ as desired, so that $f$ is
surjective.
Is this proof correct? I think there's just a problem. First, I didn't
prove that if $r$ is the remainder of $n$ by $4$ then $r+1$ is the
remainder of $n+1$ by $4$. Second, I didn't prove that $a - r \in
\{0,1,2,3,4\}$ which is necessary so that $n_{a-r} \in S_n(4)$. Are those
real problems with this proof? Are any other errors there? If some, how
can I make this better?
Thanks very much in advance!

No comments:

Post a Comment