1
$\begingroup$

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 ;-)

$\endgroup$
  • 1
    $\begingroup$ Well, there's one obvious function which satisfies this. $\endgroup$ – Thomas Andrews Nov 1 '13 at 16:31
  • $\begingroup$ What about $\;f(n)=0\;$ , if for you $\;0\in\Bbb N\;$ ? $\endgroup$ – DonAntonio Nov 1 '13 at 16:31
  • $\begingroup$ Antonio, no, zero doesnt belong to naturals in this case. $\endgroup$ – Krzysztof Lewko Nov 1 '13 at 16:32
  • $\begingroup$ 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$. $\endgroup$ – Brian M. Scott Nov 1 '13 at 16:34
  • $\begingroup$ If $0$ is not a natural number, then what is $\pi(1)$? $\endgroup$ – Thomas Andrews Nov 1 '13 at 16:35
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot for nice and clear answer! I need to work more on those formal proofs ;) $\endgroup$ – Krzysztof Lewko Nov 1 '13 at 21:59
  • $\begingroup$ @Chris: You’re welcome! $\endgroup$ – Brian M. Scott Nov 2 '13 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.