12
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Just thinking out loud here: what about $g: \mathbb{N} \rightarrow \mathbb{N}: n \mapsto 0$? $\endgroup$
    – Riley
    Aug 27, 2015 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$ Aug 27, 2015 at 19:54
  • $\begingroup$ Dang. Too good to be true. $\endgroup$
    – Riley
    Aug 27, 2015 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$
    – Vegetal605
    Aug 27, 2015 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, 2015 at 19:59

2 Answers 2

11
$\begingroup$

$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.

$\endgroup$
4
  • $\begingroup$ Beat me to it: I was just investigating $n\mapsto n+2$! $\endgroup$ Aug 27, 2015 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$
    – Vegetal605
    Aug 27, 2015 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$ Aug 27, 2015 at 20:34
  • $\begingroup$ @HenningMakholm Got it. Thanks again. $\endgroup$
    – Vegetal605
    Aug 27, 2015 at 20:36
1
$\begingroup$

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$?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .