# Find all functions over naturals that they hold an equality

The task itself is not that hard i'd say. I have to find all functions $f: \mathbb N\rightarrow \mathbb N$ that equality $f(\pi(n)) = \pi(f(n))$ is true. Where $\pi(n)$ stands for ANY permutation over the naturals.

My idea is that, if $f(\pi(n))$ gives some number X, then if we want $\pi(f(n))$ to give same number, then $f(n)$ must be an inversion of our permutation, it is $\pi^{-1}(n)$. And i have checked this on few examples and it turnes out to be true.

And my conclusion is that there is no such function, because one function can not be inversion for more than one permutation.

And my question is: how to show that more mathematically correctly ( of course if only it's good solution )? Thanks for any effort from you ;-)

• Well, there's one obvious function which satisfies this. – Thomas Andrews Nov 1 '13 at 16:31
• What about $\;f(n)=0\;$ , if for you $\;0\in\Bbb N\;$ ? – DonAntonio Nov 1 '13 at 16:31
• Antonio, no, zero doesnt belong to naturals in this case. – Krzysztof Lewko Nov 1 '13 at 16:32
• There is at least one such function: if $f(n)=n$ for all $n\in\Bbb N$, then $f\big(\pi(n)\big)=\pi(n)=\pi\big(f(n)\big)$ for every $n\in\Bbb N$ and permutation $\pi$ of $\Bbb N$. – Brian M. Scott Nov 1 '13 at 16:34
• If $0$ is not a natural number, then what is $\pi(1)$? – Thomas Andrews Nov 1 '13 at 16:35

But there is at least one such function: if $f(n)=n$ for all $n\in\Bbb N$, then $f\big(\pi(n)\big)=\pi(n)=\pi\big(f(n)\big)$ for every $n\in\Bbb N$ and permutation $\pi$ of $\Bbb N$. The identity map is, however, the only such function.
Suppose that $f:\Bbb N\to\Bbb N$ is not the identity function; then there is some $n\in\Bbb N$ such that $f(n)\ne n$. Let $m=f(n)$, and let $k=f(m)$. If $k\ne n$, let $\pi$ be the permutation of $\Bbb N$ that interchanges $m$ and $n$; then $$f\big(\pi(n)\big)=f(m)=k\ne n=\pi(m)=\pi\big(f(n)\big)\;,$$ and $f$ does not have the desired property. If $k=n$, then $k\ne m$; let $\ell\in\Bbb N\setminus\{m,n\}$, and let $\pi$ be the permutation of $\Bbb N$ that interchanges $m$ and $\ell$; then
$$f\big(\pi(n)\big)=f(n)=m\ne\ell=\pi(m)=\pi\big(f(n)\big)\;,$$
and again $f$ does not have the desired property.