I'm new to this website so forgive me for any formatting mistakes or other errors you encounter. I would appreciate it if you pointed them out. For anyone interested, the problem is from Algebra by Roger Godement.
I'm struggling with an exercise that aims to furnish a proof that the set $\mathbb{N^N}$ of functions from $\mathbb{N}$ to $\mathbb{N}$ is uncountable. The problem starts by assuming the existence of a sequence of functions $\left(f_n\right)_{n\in\mathbb{N}}$ from $\mathbb{N}$ to $\mathbb{N}$, and defining a mapping $f:\mathbb{N}\rightarrow\mathbb{N}$ by $f(n)=f_n(n)+1$ for all $n\in\mathbb{N}$.
The first part asks you to show that there is no number $p\in\mathbb{N}$ such that $f=f_p$, which is easy enough. For if $f=f_p$ for some $p$, then by definition we would have $f_p(p)+1=f(p)=f_p(p)$. But since any cardinal $x$ that satisfies $x=x+1$ is infinite, this implies $f_p(p)$ is infinite, which contradicts the fact that $f_p(p)\in\mathbb{N}$. Hence for all $p\in\mathbb{N}$ we have $f_p\neq f$.
From this, you are supposed to deduce the uncountability of $\mathbb{N^N}$, which one can proceed with by using the lack of surjectivity of $f$ to show that $f$ is not a bijection, as in the problem before this. In particular, since $f(p)\in\mathbb{N}$, we find that there exists $y=f_p(p)\in\mathbb{N}$ such that $\forall p\in\mathbb{N}$, $y\neq f(p)$, which is to say that $f$ is not surjective, hence not bijective (In the preceding discussion you can exchange $f$ and $f_p$; either way I haven't been able to figure it out).
Where this gets fuzzy for me is in trying to use this to show that any function from $\mathbb{N}$ to $\mathbb{N}$ cannot be bijective. I can't find a way to generalize the result to an arbitrary function from $\mathbb{N}$ to $\mathbb{N}$. I've tried two approaches so far.
The first is to show that for any function $h:\mathbb{N}\rightarrow\mathbb{N}$ we can find another function $g:\mathbb{N}\rightarrow\mathbb{N}$ such that $h=g\circ f$. A theorem from a previous chapter guarantees the existence of $g$ provided that if $m$,$n\in\mathbb{N}$, then $f(m)=f(n)\implies h(m)=h(n)$. And since $f$ isn't bijective, neither would $h$ be. But given that $h$ is supposed to be arbitrary, I'm not sure how to prove this implication.
The second approach is to find some way of showing that the sequence $\left(f_p\right)_{n\in\mathbb{N}}$ covers $\mathbb{N^N}$, in which case we could make use of the fact that $f_p$ isn't bijective. However, since no conditions are set on any of the $f_n$, I don't see any way of proving this.
Once you show that a bijection does not exist between $\mathbb{N}$ and $\mathbb{N^N}$, the result follows. Thanks in advance!