Find all functions over naturals that they hold an equality

Question

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

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 01 '13 at 16:34
Oh, right. I just missed the identity function. That's embarassing. Thanks. — Krzysztof Lewko, Nov 01 '13 at 16:36
@DonAntonio this does not seem to help: not all permutations satisfy $\pi(0)=0$. — gt6989b, Nov 01 '13 at 16:38
Permutation is some bijection from $N$ to $N$ right? So, does zero really matter?
Thanks Andrew for new idea about it. — Krzysztof Lewko, Nov 01 '13 at 16:41
But i don't know if we can say that $f(n)$ can be any power of $\pi(n)$, cause $f(n)$ is somehow fixed and we want to test it with all permutations. So is it true if we say that $f(n) = \pi(n)$? It makes $f(n)$ pretty dynamic, not static, at least to my understanding of this. Am i right or false? — Krzysztof Lewko, Nov 01 '13 at 16:48
Do you want to find all $f$ that satisfy $f\circ \pi=\pi\circ f$ for all permutations $\pi$? Or for a given $\pi$, find all $f$ such that $f\circ \pi=\pi\circ f$? — Hagen von Eitzen, Nov 01 '13 at 16:50
Oh, duh, I should read the question. Of course. I was reading $\pi$ as the prime counting function. Never mind. Will delete my comments. — Thomas Andrews, Nov 01 '13 at 17:14

score 2 · Accepted Answer · answered Nov 01 '13 at 16:50

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.

Thanks a lot for nice and clear answer! I need to work more on those formal proofs ;) — Krzysztof Lewko, Nov 01 '13 at 21:59

Find all functions over naturals that they hold an equality

1 Answers1