I'm struggling with this question and can't figure it out. The question was too long for the title so I will write it once more:

Does there exist a function $g : \mathbb{N} \longrightarrow \mathbb{N}$ such that the set $\{f\mid f : \mathbb{N} \longrightarrow \mathbb{N} \text{ and }f\circ f=g\}$ is not empty and finite?

Thank you.

  • $\begingroup$ Just thinking out loud here: what about $g: \mathbb{N} \rightarrow \mathbb{N}: n \mapsto 0$? $\endgroup$ – Riley Aug 27 '15 at 19:53
  • 2
    $\begingroup$ @Riley there are continuum-many $f$ in that case: Map any subset $A$ of $\mathbb N$ to $0$, map the rest somewhere into $A$. $\endgroup$ – Hagen von Eitzen Aug 27 '15 at 19:54
  • $\begingroup$ Dang. Too good to be true. $\endgroup$ – Riley Aug 27 '15 at 19:55
  • $\begingroup$ @Riley actually by $\mathbb{N}$ I meant $\mathbb{N}_+$ so $0$ is not in the values of the image of $g$ but for any $n\in \mathbb{N}_+$ if you will take the function $g$ to be $g(i)=n$ for any $i$ then the above set would be infinite $\endgroup$ – dorsh605 Aug 27 '15 at 19:56
  • $\begingroup$ @dorsh605 It doesn't matter if you consider $0$ as a natural number or not. $\mathbb{N}$ could be exchanged with any countably infinite set. $\endgroup$ – Dominik Aug 27 '15 at 19:59

$g(n)=n+2$ will do the trick.

Since this $g$ is injective, $f$ must be injective too, so under $f$ each natural number will have one successor and zero or one predecessor.

Also there are exactly two numbers that have no pre-predecessor, and that is only possible if there is exactly one number with no predecessor. There also can be no cycles in the action of $f$, because there are no cycles in the action of $g$. So the action of $f$ is fully specified by giving an enumeration of the natural numbers, and $f$ then just gives the successor of each of them.

The first two numbers in the enumeration must be the ones not hit by $g$, that is, $1$ and $2$. This makes the possible enumerations:

$$ 1,2,3,4,5,6,7,8,\ldots \quad \text{and}\quad 2,1,4,3,6,5,8,7\ldots $$ The first of these gives rise to $f(n)=n+1$, the other to $$ f(n) = \begin{cases} n-1 & \text{for even }n \\ n+3 & \text{for odd }n \end{cases}$$ and these are the only $f$ that produce $n\mapsto n+2$ when iterated twice.

  • $\begingroup$ Beat me to it: I was just investigating $n\mapsto n+2$! $\endgroup$ – Brian M. Scott Aug 27 '15 at 20:08
  • $\begingroup$ @Henning Makholm Thanks! would this example work if we change it from $g(n)=n+2$ to $g(n)=n+i$ for any $i>1$? $\endgroup$ – dorsh605 Aug 27 '15 at 20:25
  • $\begingroup$ @dorsh605: If $i$ is odd, then there is no possible $f$, but with $i=2k\ge 2$, the analysis here results in $(2k)!/k!$ different solutions. $\endgroup$ – hmakholm left over Monica Aug 27 '15 at 20:34
  • $\begingroup$ @HenningMakholm Got it. Thanks again. $\endgroup$ – dorsh605 Aug 27 '15 at 20:36

Don't shoot me if I'm wrong, but I think this would be a huge hint:

Let $X$ be a set. It holds that $\lvert X\rvert \leq 1$ if and only if for every function $f : X \to X$, there is a function $g : X\to X$ with $f = g\circ g$.

The proof of this can be found in this link: Is every function $f : \mathbb N \to \mathbb N$ a composition $f = g\circ g$?


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.