Question: Construct a permutation of the set N of all natural numbers that maps all the multiples of 3 onto the set of all even numbers.
I am confused as to how to get started on the problem. I have tried creating multiple mappings that map multiples of 3 into even numbers, but how do I include natural numbers in my permutation?
We satisfy the condition of the question first: $f(3k)=2k$ for $k\ge0$. Now just assign the rest of the domain (non-multiples of $3$) to the rest of the codomain (odd numbers) in order, which yields $$f(n)=\begin{cases} 2k&n=3k\\ 4k+1&n=3k+1\\ 4k+3&n=3k+2\end{cases}$$ where $k$ is also a natural number. That this is a permutation can be verified by noting that $\{3k,3k+1,3k+2\}$ and $\{2k,4k+1,4k+3\}$ both define complete residue systems.
Suppose in general you are given an arbitrary set $A$, together with two subsets $B, C \subseteq A$ and you are required to find a permutation $\sigma \in \Sigma(A)$ such that $\sigma(B)=C$. Quick inspection reveals that a necessary condition for such a $\sigma$ to exist is that $|B|=|C|$, as the restriction of said $\sigma$ to domain of definition $B$ and codomain $C$ would yield a bijection between the two. Furthermore, as bijections take complementaries to complementaries, you would also have $\sigma(A\setminus B)=A\setminus C$ and by the same token that $|A\setminus B|=|A\setminus C|$. Are these conditions also sufficient?, we come to ask. Indeed they are: if $\varphi: B \to C$ and $\psi: A\setminus B \to A\setminus C$ are bijections, then the map $$\sigma: A \to A,\\ \sigma(x)=\begin{cases} \varphi(x),& x \in B\\\psi(x),& x \in A\setminus B \end{cases}$$ is easily seen to be a permutation of $A$ mapping $B$ onto $C$.
In your particular case, $A=\mathbb{N}, B=3\mathbb{N}, C=2\mathbb{N}$, hence $A \setminus B=3\mathbb{N}+\{1, 2\},\ A\setminus C=2\mathbb{N}+1$. You can resort to the general fact that any infinite subset of $\mathbb{N}$ is equipotent to $\mathbb{N}$, or implement a more manual construction, by noticing that $$3\mathbb{N}+\{1, 2\} \approx \mathbb{N} \sqcup \mathbb{N} \approx 2\mathbb{N} \sqcup (2\mathbb{N}+1) \approx \mathbb{N} \approx 2\mathbb{N}+1$$
