We are looking at a function $F:\mathbb{N}^\mathbb{N}\to \mathbb{N}^\mathbb{N}$ $$F(h)=h\circ h$$ I want to show that $F$ is not surjective.

I have a solution, but I'm not quite sure if this is a proof or I just missed something. Let's take the function $h(x)=x$ and feed it to $F$. We will get $F(h(x))=h(h(x))$. The function $h(h(x))$ is always equal to $x$. So I say that $F$ is not surjective, because if I feed $h(x)$ in, some values like for instance $t(x)=x^2$ will not be hit in the codomain, so $F$ is not surjective.

I am really unsure whether this proves the statement. I feel like it's too easy. If it's wrong, I'd really appreciate some tipps!


Yes, it is wrong. For your function $h$ (which is the identity), it turns out that $h\circ h=h$; in other words, $F(h)=h$.

Define $f(n)=n+1$. There is no $g\in\mathbb{N}^{\mathbb N}$ such that $g\circ g=f$. In fact, if such a function $g$ existed, then:

  • $g$ would be injective, because$$g(a)=g(b)\implies g\bigl(g(a)\bigr)=g\bigl(g(b)\bigr)\iff a+1=b+1\iff a=b.$$
  • $g$ would not be surjective, because otherwise there would be a $a\in\mathbb N$ such that $g(a)=1$ and there would be a $b\in\mathbb N$ such that $g(b)=a$ and then $1=g(a)=g\bigl(g(b)\bigr)=b+1$, which is impossible.

So, let $G=g(\mathbb{N})$. You know that $G\varsubsetneq\mathbb{N}$. Take $a\in\mathbb{N}\setminus G$. Then there is no $b\in\mathbb N$ such that $g\bigl(g(b)\bigr)=g(a)$ because, since $g$ is injective, that would imply that $g(b)=a$, which is impossible. But then, neither $a$ nor $g(a)$ belong to the image of $g\circ g$. This is impossible, because $g\circ g=f$ and the image of $f$ Is $\mathbb{N}\setminus\{1\}$.

  • $\begingroup$ Would it be a legit proof to say that with values from $\mathbb{N}$ there is no way of combining a function with itself so that it comes out as n+1? I don't know how to prove it otherwise.. $\endgroup$ – chala Jan 22 '18 at 9:34
  • $\begingroup$ @chala That's just saying that it is true because it is true. $\endgroup$ – José Carlos Santos Jan 22 '18 at 9:35
  • $\begingroup$ I see. So how am I to prove it? $g(g(x))=x+1$ and I don't know how I could go on from this. I cannot take the inverse as g is not said to be bijective. $\endgroup$ – chala Jan 22 '18 at 9:44
  • $\begingroup$ @chala I have edited my answer. $\endgroup$ – José Carlos Santos Jan 22 '18 at 10:14

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.