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

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

• 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.. Commented Jan 22, 2018 at 9:34
• @chala That's just saying that it is true because it is true. Commented Jan 22, 2018 at 9:35
• 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. Commented Jan 22, 2018 at 9:44
• @chala I have edited my answer. Commented Jan 22, 2018 at 10:14