How do I show that $F(h) = h \circ h$ is surjective?

Question

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!

Answer 1

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